Exemple de probleme de programare liniara

Exemple de probleme de programare liniara

a) Problema planului optim de productie.

Fie masinile care fabrica sau consuma produsele , in cantitati date pe unitatea de timp, anume din pentru masina . (Daca produce in unitatea de timp cantitatea din atunci , daca consuma atunci , iar daca ,nu produce si nu consuma ). Productia (respectiv consumul) produsului nu trebuie sa fie sub limita (respectiv sa depaseasca) (respectiv daca ) pentru .

Fie timpul de functionare al masinii , iar beneficiul obtinut prin functionarea lui in unitatea de timp, . Un sistem de numere reale constituie un plan optim de productie, daca maximizeza beneficiul total adica functia:

in conditiile restrictive:

.

Daca reprezinta costul functionarii masinii in unitatea de timp, atunci se va cere minimizarea functiei de cost .

b) Problema dietei (a amestecului).

Sa se determine cantitatile din alimentele , , alcatuind o dieta astfel incat costul acesteia sa fie minim, unde reprezinta costul unitar al alimentului , daca se mai cunoaste componenta in substante nutritive (cum ar fi: glucide, lipide, vitamine) a alimentelor , , data prin matricea: unde este cantitatea de substanta continuta in unitatea din alimentul si se cere ca fiecare dieta sa contina cel putin cantitatile din substanta , . Deci, matematic problema se transcrie:

c) Problema folosirii optime a resurselor.

O unitate economica trebuie sa produca produsele avand la dispozitie cel mult cantitatile din resursele . Stiind ca producerea unei unitati din produsul necesita cantitatea din resursa si ca prin livrarea unei unitati din acelasi produs se obtine beneficiul , se cere sa se determine cantitatile din produsele astfel ca beneficiul sa fie maxim. Deci:

d) Problema de transport.

Se dau depozitele , avand disponibila o marfa in cantitatile ; consumatorii solicitand marfa in cantitatile b'₁, b'₂, , b'_m; si costul unitar de transport al marfii de la depozitul la consumatorul .

Se cere sa se gaseasca un sistem de numere nenegative unde este cantitatea de marfa transportata de la la , care sa faca minim costul de transport, adica functia si sa nu depaseasca disponibilul din nici un depozit, adica: si sa satisfaca macar cererea fiecarui consumator, adica:

Sistemul care indeplineste aceste conditii se numeste program de transport. Evident, existenta unui program de transport impune conditia ca disponibilul total sa depaseasca sau sa fie macar egal cu cererea totala, adica:

Daca restrictiile problemei sunt date ca egalitati atunci si relatia (1) devine egalitate, si in acest caz problema de transport se numeste echilibrata.

In caz contrar spunem ca avem o problema de transport neechilibrata.

Datele problemei de transport pot fi inscrise intr-un tablou de forma:

Tabelul (T)