46

CAPITOLUL III

PROGRAMARE LINEARĂ

FORMULAREA PROBLEMELOR

Introducere.
Programarea liniară este o parte a programării matematice care, aș a cum sugerează numele său,
indica, manevrează ecuaț ii liniare, adică acelea în care toate variabilele implicate au ca
exponente la unitate în toate termenii săi.
În acest capitol vom vedea modalitatea de a formula o problemă dată, exprimând-o sub formă
matematică.
Nu se va proceda la rezolvarea sa, ci doar la formularea acestuia, care va consta în transformarea unei
serie de date ș i informaț ii referitoare la problema din ecuaț iile matematice.

Definiț ii.
Pentru a facilita înț elegerea terminologiei folosite, vom oferi mai jos câteva definiț ii
utile:
Func ț ia Obiectiv.- Aceasta este o variabilă, de obicei simbolizată prin litera Z, care reprezintă
ceea ce se doreș te să fie optimizat, de exemplu, un cost care se urmăreș te să fie minimizat, sau bine, o utilitate care
se caută maximizarea.
Variabilele problemei - sunt acele variabile care nu sunt cunoscute ș i care, în momentul de a rezolva
problema, acestea trebuie să fie definite astfel încât să realizeze optimizarea funcț iei obiectiv.
aceste variabile sunt cunoscute ș i sub numele de variabile de decizie.
Coeficientii funcț iei obiectiv.- Sunt cantităț i constante care apar în ecuaț ia funcț iei
obiectiv multiplicând variabilele problemei.
Restric ț ii.- Sunt limitările fizice sau condi ț iile pe care trebuie să le îndeplinească problema, de exemplu,
cantitate disponibilă de materiale, timp, muncă, etc. De asemenea, sunt adesea numite restric ț ii
funcț ionale.
Restricț ii neexplicite.- Acestea sunt condiț ii ascunse în problemă, care nu apar în
informaț ii disponibile, dar care trebuie luate în considerare atât în formulare cât ș i în
rezolvarea acestuia. Cele mai frecvente exemple de acest tip de restricț ii sunt non-negativitatea
variabilele problemei sau ca acestea trebuie să fie numere întregi.

Metodologie.
Pentru a formula o problemă, pot fi aplicate următorii paș i:
Pasul 1.- Definirea variabilelor problemei. Acest pas constă în identificarea acestor variabile ș i
denotarlas prin litere.
Pasul 2.- Definirea funcț iei obiectiv. Acesta va fi identificarea acelei variabile care trebuie optimizată, care
vom reprezenta ca Z ș i vom exprima ecuaț ia sa matematică în funcț ie de variabilele problemei ș i ale sale
coeficien ț i. În acest pas trebuie să se stabilească, de asemenea, dacă optimizarea este o maximă sau o
minimizare.
Pasul 3.- Definirea restricț iilor. Aceasta va fi stabilirea unei ecuaț ii pentru fiecare restricț ie în funcț ie de
de variabilele problemei. Este frecvent ca ecuaț iile restricț iilor să fie inegalităț i ale
tip mai mare sau egal cu (>) ș i/sau mai mic sau egal cu (<).
Este convenabil să men ț ionăm aici că nu toate variabilele problemei pot apărea în fiecare
restricț ie, aceasta va depinde de tipul particular de problemă de care este vorba.
Pasul 4.- Definirea restricț iilor neexprimate. Constă în identificarea ș i exprimarea acestor restricț ii în
formularea problemei.
 47
În continuare, vom prezenta mai multe exemple rezolvate:
Exemplu III.1.- Un magazin naturist î ș i pregăte ș te alimentele pe care le vinde publicului bazându-se pe 3
materii prime ale căror conț inuturi sunt prezentate în următoarea tabelă:

Materie primă Cost, N$/kg % Zuccheri % Grasos % Proteine % Inerte

A 2.35 12 10 60 18
B 2.00 10 10 50 30
C 1,70 8 6 44 42

Cât de mult trebuie să amestece din fiecare dintre cele 3, dacă se doreș te minimizarea costului de preparare a 1 kg de
alimente al căror conț inut de zahăr nu este mai mic de 10%, conț inutul de grăsimi nu este mai mare de 9,5% ș i
conț inutul de proteine nu mai mic de 52%?
Soluț ie: Conform metodologiei descrise anterior, vom merge la primul pas, adică să definim
variabilele problemei.
Aceste variabile vor fi con ț inuturile necesare fiecărei dintre cele 3 materii prime, care
definim în felul următor:
X1 = Frac ț iunea de kilogram din materia primă A
X2 = Frac ț ie de kilogram din materia primă B
X3 = Frac ț iunea de kilogram de materie primă C
Prin aceasta se finalizează pasul 1.
Continuând cu pasul 2, vom defini funcț ia obiectiv Z care va fi costul unui kg de hrană,
cual va trebui minimizat ș i a cărei ecuaț ie în funcț ie de variabilele X, 1X, X2va fi:
3
Min Z = 2.35 X1 + 2.00 2X + 1.70 3X
Aici, coeficientii variabilelor sunt costurile unitare ale fiecărei materii prime.
Continuând cu metodologia ș i conform pasului 3, există limitări în ceea ce priveș te conț inutul de
zaharuri, grăsimi ș i proteine, motiv pentru care va exista o restricț ie pentru fiecare limitare, acestea vor fi:
Conț inut de Zaharuri: 12 X + 110 X + 8 X
2 > 10.0 3
Conț inut de Grăsimi: 10 X1+ 10 X + 26 X < 9.53
Conț inut de proteine: 60 X + 50
1 X + 44 2X > 52.0 3
În plus, va exista o condiț ie suplimentară, în ceea ce priveș te suma celor 3 variabile X,1X ș2i X, care
3
trebuie să fie unitatea, adică:
X1 + X2 + 3X = 1
În cele din urmă, când ajungem la pasul 4, singura restricț ie non-exprimată va fi că variabilele X, X ș i X trebuie să fie
1 2 3
a nu fi negative, căci nu ar avea niciun sens fizic să vorbim despre o X negativă, aceasta înseamnă:
X1, X2 , X3 , Nu negative
Prin gruparea ecuaț iilor, vom lăsa problema formulată, care va fi:
Min Z = 2.35 X1 + 2.00 2X + 1.70 3X
sub restricț ii:
12 X1+ 10 X + 28 X 10.0 3
10 X1+ 10 X + 26 X < 9.53
60 X1+ 50 X + 244X 3 > 52.0
X1 + X2 + X3 = 1
Con X1, X 2, X ,3No negative

Vom prezenta un alt exemplu:

Exemplul III.2.-O fabrică de încălț ăminte dispune de 45 de unităț i de piele ș i 20 de ore de timp pentru a produce
2 tipuri de cizmă, dintre care primul tip necesită 6 unităț i de piele ș i 2.5 ore, vânzându-se la N$
140/par; în timp ce al doilea tip necesită 5 unităț i de piele ș i 2 ore, vânzându-se la N$ 115/par.
Câte perechi de cizme din fiecare tip ar trebui fabricate pentru a maximiza veniturile?
48
Soluț ie: Primul lucru va fi să definim variabilele problemei, care vor fi cantităț ile de produs.
de fiecare tip de botă, adică:
X 1 = Cantitate de produs pentru primul tip de cizme, numărul de perechi.
X2 = Cantidad a producir del segundo tipo de bota, número de pares.
Următorul pas este definirea funcț iei obiectiv Z, care va reprezenta venitul din vânzarea celor 2 tipuri de cizme,
cel care trebuie maximizat ș i a cărui ecuaț ie în funcț ie de variabile va fi dată de:
Max Z = 140 X 1+ 115 X 2
Unde coeficientii variabilelor sunt preț urile de vânzare pentru fiecare tip de botă.
Acum vom proceda la definirea restricț iilor, care vor fi două în acest caz, una pentru cantitate
de piele ș i alta pentru timpul disponibil, atunci vom avea:
Unidades de Piel : 6 X1+ 5 X 2< 45
Timp disponibil ore: 2.5 X + 2 1X < 20 2
Aici cele 2 restricț ii sunt de tipul mai mic sau egal cu ( < ) deoarece atât unităț ile de piele
cum timpul disponibil în ore are un maxim posibil de 45 de unităț i ș i 20 de ore respectiv.
În cele din urmă, vom defini restricț iile non-explicite, care sunt:
X1, X2 , Introduce ț i ș i Ne-négativ
Variabilele trebuie să fie întregi deoarece nu ar avea sens să vorbim de o fracț iune dintr-o pereche de cizme.
a spune 0,33 perechi de botine. Non-negativitatea variabilelor este de asemenea evidentă, având în vedere că nu ar exista nici
sensul de a vorbi despre un număr negativ de perechi de bocanci.
Prin urmare, formularea completă a problemei va rămâne sub următoarea formă:
Max Z = 1401 X + 2115 X
subiectă la restricț ii:
6 X1+ 5 X < 245
2.5 X 1+ 2 X < 20
2
Con X1ș i X, Entere
2 ș i Non-negativ.

A continuación prezentăm un alt exemplu:

Exemplul III.3.-Compania Agropec caută să producă o hrană pentru animale la un cost minim.
Pentru aceasta, dispune de 3 produse ca materii prime care au următoarele caracteristici:
Materia primă Cost, N$/kg % Vitamine % Minerale % Proteine
A1 4.50 12 30 18
A2 3.70 10 30 15
A3 3,00 8 25 15

Cum va trebui să amestece aceste 3 materii prime pentru a pregăti 1 kilogram de produs dacă acesta va trebui
să conț ină cel puț in 11% vitamine, 28% minerale ș i 17% proteine?
Solu ț ie: În primul rând, vom defini variabilele problemei, care sunt în acest caz
cantităț ile materiilor prime A, A ș i A
1 de2amestecat
3 pentru a prepara 1 kilogram de produs, adică:
X1 = Cantitatea materiei prime 1A
X2 = Cantitatea materiei prime 2A
X3 = Cantitatea materiei prime 3A
Acum vom defini funcț ia obiectiv Z, care va fi costul de 1 kilogram din produs, care
trebuie să fie minimizat, atunci:
Min Z = 4.50 X1 + 3.70 X2 + 3.00 X 3
Fiindcosturile unitare ale materiilor prime coeficientii variabilelor.
Pasul următor este definirea restricț iilor, dintre care va exista una pentru conț inutul minim de
vitamine, una pentru minerale ș i alta pentru proteine, pe lângă faptul că suma variabilelor
trebuie să fie la unitate (1 kilogram), atunci vom avea:
Conț inut de vitamine: 12 X + 101 X + 8 X > 2 11 3
 49
Conț inutul de Minerale: 30 X +130 X + 252 X > 28 3
Conț inut de proteine: 18 X + 151 X + 15 X2 > 17 3
Sumatoria a Variabilelor: X1 + X2 + X3 = 1
În cele din urmă, restricț iile neexplicitate; care în acest caz sunt doar non-negativitatea lui
variabilele.
Aș adar, formularea completă a problemei este:
Min Z = 4.50 X1 + 3.70 X2 + 3.00 X3
Supusă restricț iilor:
12 X1+ 10 X + 28 X > 11 3
30 X1+ 30 X + 225 X > 283
18 X1+ 15 X + 215 X > 173
X1 + X2 + X3 = 1
Făcând X,1 X, 2X, Nu
3 negative.

Exemplu III.4.-O fabrică de săpunuri caută un program de produc ț ie care să maximizeze

venituri.
Are opț iunea de a elabora 3 tipuri diferite de săpunuri, care necesită ore-maș ină, acid
grăsime ș i sodă caustică în următoarele cantităț i:

Tip de săpun Preț , N$/u Ore-Maș ină Acid Gras, grs Soda Caustică, grs
1 5.18 18 418 32
2 4.37 14 350 24
3 3,29 10 310 20

Si fabrica dispune de 5000 de ore-maș ină, de 120 de kilograme de acid gras ș i de 10 kilograme de
soda caustică. Câte săpunuri va trebui să producă din fiecare tip?
Soluț ie: În acest caz, variabilele vor fi unităț ile fiecărui tip de săpun ce urmează a fi produse, adică:
X1 = Unită ț i de produs din primul tip de săpun.
X2 = Unidades a producir del segundo tipo de jabón.
X3 = Unită ț i de produs din al treilea tip de săpun.
Pe de altă parte, funcț ia obiectiv Z va fi venitul, care va fi dat de:
Max Z = 5.18 1X + 4.37 2 X + 3.29 3 X
Fiind preț urile unitare coeficientii variabilelor.
Restricț iile vor fi disponibilităț ile de Ore-Maș ină, Acid Gras ș i Sodă Caustică, adică:
Horas Máquina: 18 X1 + 14 X2+ 10 X < 3 5.000
Acid gras, grs: 418 X + 350
1 X + 310 2X < 120.000
3
Sosa Cáustică, grs: 32 X + 124 X + 20 X
2 < 10.0003
Fie X, X, 1X, întregi
2 3 ș i non-negative.

Exemplul III.5.- Proprietarul unui camion cu o capacitate de încărcare de 10 tone se gândeș te la

întrebare despre cum să încarci camionul astfel încât să obț ii venitul maxim. În următoarea tabelă se
prezintă diferitele încărcături posibile ș i venitul din conceptul de transport pe care l-ar genera:
Material Peso, kgs Ingreso, N$
Portocale 2500 220
Pepeni 1800 170
Pepeni 2100 210
Pepeni 1850 170
Nuci 1650 210
50
Morcovi 2100 200

Care ar fi modul de a încărca camionul? Trebuie menț ionat că nu se poate transporta niciun material pe.
fracț ii, adică se transportă tot materialul sau nimic din el.
Soluț ie: Aici variabilele problemei vor fi câte una pentru fiecare tip de material, aș adar:
X1 = Variabilă de probabilitate de a aduce portocale
X = Variabilă de probabilitate de a transporta castrave ț i
2
X3 = Variabilă de probabilitate de a căra pepeni
X 4 = Variabila de probabilitate de a transporta pepeni
X5 = Variabilă de probabilitate de a transporta nuci
X6 = Variabilă de probabilitate de a transporta morcovi
Funcț ia obiectiv Z, care va trebui să fie maximizată, va fi venitul total din transport, care va fi dat de
prin:
Max Z = 220 X1 + 170 X 2+ 210 X 3+ 170 X +4 210 X +5 200 X 6
Restricț iile vor fi una pentru greutatea totală încărcată în camion, adică:
2500 X1+ 1800 X + 22100 X + 1850 3 X + 16504X + 2100 X5< 10,000 6
la care este de tipul mai mic sau egal decât (<), având în vedere că camionul nu poate fi suprasolicitat peste
capacitate.
În plus, fiecare variabilă poate avea o pereche de valori posibile: să fie zero sau o unitate dacă este transportată de
acest tip de material sau nu, punem acest lucru pentru restricț iile în forma următoare:

X1 < 1
X2 < 1
X3 < 1
X4 < 1
X5 < 1
X6 < 1
con X 1, X ,2X , X
3 , X4, X 5, Enteras
6
În ceea ce priveș te restricț iile non-explicite, acestea implică non-negativitatea variabilelor ș i că acestea
vor trebui să fie zero sau unul.
În acest mod, formularea completă a problemei va fi în următoarea formă:
Max Z = 220 X1 + 170 X 2+ 210 X 3+ 170 X +4 210 X +5 200 X 6
Subiectă la restricț ii:
2500 X1+ 1800 X + 22100 X + 1850
3 X + 16504X + 2100 X5< 10,000 6
X1 < 1
X2 < 1
X3 < 1
X4 < 1
X5 < 1
X6 < 1
Cu variabilele X, X,1X, X,
2 X,3X, întregi
4 5 ș 6i nenegative.
 51
PROBLEME PROPUSE.

III.1.- Un restaurant caută să- ș i optimizeze veniturile din vânzarea deserturilor, poate dispune de 4
diferite tipuri: natillas, gelatină, budincă ș i dulciuri, care necesită zahăr ș i lapte condensat în
cantităț ile care sunt menț ionate în următoarea tabelă:
Desert Zahăr, grs Lapte, ml Preț , N$/u
Natilla 60 120 3.50
Gelatina 70 135 3.60
Budincă 90 170 4.00
Dulce 120 200 4.60

Ș i restaurantul dispune de o livrare de 10 kg de zahăr ș i 18 litri de lapte condensat, cât

va trebui să pregătească fiecare tip de desert?

III.2.- O clinică de diete caută să minimizeze costurile de preparare a unui aliment echilibrat. Pentru aceasta
dispune de 3 produse ca materii prime, care au următoarele specificaț ii:
Materia Primă % Grase % Zaharuri Cost, N$/kg
1 20 17 3.00
2 18 15 3.30
3 15 15 3.50

Ș i alimentul echilibrat trebuie să conț ină maximum 18,5 % grăsimi ș i 16 % zaharuri. Cum
va trebui să amestece clinica materiile sale prime pentru a satisface aceste condiț ii la un cost minim?

III.3.- Un atelier de fierărie caută să-ș i îmbunătăț ească utilităț ile fabricând 2 tipuri diferite de uș i. El
atelierul dispune de 150 de kilograme de fier ș i 70 de ore de timp disponibil. Uș a tip numărul 1
necesită 10 kilograme de fier ș i 6 ore de timp, oferind un beneficiu de N$ 180, în timp ce
Al doilea tip necesită 12 kilograme de fier ș i 7 ore de timp, cu un profit de N$ 200.
Câte uș i din fiecare tip ar trebui să fabrice atelierul pentru a-ș i maximiza profiturile?

III.4.- Fabrica Chimică de la Rioverde caută să respecte legile ecologice, pentru care i s-au oferit
2 tipuri diferite de echipamente anticontaminare. Primul echipament vă oferă un control de 70% ș i
costul este de N$ 7.500,00, în timp ce al doilea echipament oferă 80% control ș i costă N$
8.500,00
Ș i compania trebuie să instaleze un total de 4 echipamente anti-poluare cu un control global de 75%,
Câte echipamente de fiecare tip ar trebui să achiziț ioneze, astfel încât costul de achiziț ie să fie minim?

III.5.- O tâmplărie dispune de 100 metri cubi de lemn ș i 40 de ore de timp liber. Caută
fabricarea a 3 tipuri diferite de scaune, care pot fi vândute acceptabil pe piaț ă, fiecare tip
are următoarele cerinț e ș i preț uri de vânzare:
Tip de scaun Lemn, m 3 Tiempo, horas Precio, N$/u
1 2.5 1.20 15.20
2 2.0 1.00 13.00
3 2.2 1.05 13.50

Câte scaune din fiecare tip ar trebui să fabrice, pentru a-ș i maximiza veniturile?
52
O fabrică de brânzeturi trebuie să elaboreze acestea cu un conț inut de grăsimi de cel mult 20%, pentru a
poate achizi ț iona 2 tipuri diferite de lapte: Primul tip are 25% grăsimi ș i costă N$
1.20/litru, în timp ce al doilea tip conț ine 16% grăsimi ș i costul său este de N$ 1.70/litru. Cum
Trebuie să amestece aceste lapte pentru a pregăti brânză la un cost minim?

III.7.- Un supermarket poate pune pe rafturile sale 3 produse noi, care ar ocupa 3, 4 ș i
5 etaje respectiv, ș i le-ar oferi 6, 7 ș i 8.5 N$ de venituri suplimentare respectiv. Dacă
supermarketul dispune de 80 de rafturi pentru a plasa aceste produse, câte produse din fiecare tip
trebuie să plaseze astfel încât să-ș i maximizeze veniturile suplimentare?

III.8.- Un furnizor de materiale de construcț ie doreș te să pregătească gravă care să conț ină cel puț in
65% din material de 1/2", pentru aceasta dispune de 3 tipuri de materii prime, care conț in 80, 60 ș i
58% din material de 1/2", cu un cost de 10, 7 ș i 6,50 N$/tonă respectiv.
Cum ar trebui să amestece aceste 3 materii prime pentru a pregăti o tonă de pietriș la un cost minim?

III.9.- Un constructor are 3 tipuri diferite de zidari: MB, R ș i P care pot monta
400, 300 ș i 250 de cărămizi pe zi, având salarii de 35, 28 ș i 20 N$/zi, respectiv. Dacă
Constructorul trebuie să plaseze 3000 de cărămizi pe zi ș i dispune de 4 zidari de tip MB, 6 de tip R ș i 8 de tip P.
Cum aș aloca 10 zidari pentru a aș eza cele 3000 de cărămizi la un cost salarial minim?

III.10.- O radiodifuzor are 2 ore de timp liber pentru a putea programa reclame. Există 3
tipuri diferite de comerciale, care ar dura 2, 1.7 ș i 1.5 minute fiecare, generând un venit de
18, 15 ș i 13 N$ respectiv. Câte comerciale de fiecare tip ar trebui să programeze astfel încât
veniturile din acest concept să fie maximizate?