programare liniara
Post on 07-Aug-2015
224 Views
Preview:
DESCRIPTION
TRANSCRIPT
Programare liniară
Matematici aplicate in economie
17
Programare liniară Programarea liniară este un capitol important al cercetărilor operaţionale, cu o
largă aplicare în practica de zi cu zi, dar mai ales în economie.Vom ilustra câteva
direcţii de aplicare ale programării liniare in activitatea productivă.
A. Problema utilizării optime a unor resurse Se urmăreşte producerea reperelor
R1,R2,…Rn
în fabricarea cărora se utilizează materiile prime (resursele)
E1,E2,….Em (resursele mai pot fi: disponibil de forţă de muncă, disponibil de
capital, energie).
Resursele sunt disponibile în cantităţi limitate; asfel din resursa Ej dispunem
de o cantitate maximă bj, cunoscută în prealabil.
Se mai cunosc:
- consumurile tehnologice: ∀ i = n,1 şi ∀ j= m,1 aij ≥ 0 este cantitatea din
resursa Ej ce se consumă pentru a fabrica o unitate din produsul Ri;
-beneficiile unitare: ∀i= n,1 ci este suma obţinută prin vânzarea unei unităţi
de produs Ri;
-costurile unitare de achiziţie pentru materiile prime: ∀j= m,1 αj este suma
necesară cumpărării unei unităţi din materia prima Ej;
-capital total disponibil: S reprezinta suma totală disponibilă pentru achiziţionarea de resurse in vederea realizării producţiei.
Vom nota cu xi (i= n,1 ) cantitatea de produs ce va fi fabricată.
• Cunoaşterea mărimilor xi, i= n,1 reprezintă scopul final într-o problemă de
planificarea producţiei.
În aceste condiţii:
-încasările totale rezultate din vânzarea produselor sunt date de:
f(x1,x2,…xn) = ∑=
n
iii xc
1
-din resursa Ej s-a consumat în total cantitatea , ∑=
n
iiij xa
1mj ,1=∀ ;
-costul total al materiei prime Ej consumate este ∀ j = ∑=
n
iiijj xa
1α m,1 ;
Programare liniară
Matematici aplicate in economie
18
-cheltuielile totale pentru achiziţionarea tuturor materiilor prime necesare realizării
producţiei vor fi . ∑∑= =
m
j
n
ijiij xa
1 1α
Se pot prezenta două modele diferite, care au ca scop determinarea mărimilor
x1,x2,…xn.
1)Dacă unitatea are materiile prime E1,E2,….Em în cantităţile b1,b2,…bm
cunoscute, se pune problema utilizării acestora într-un mod care să conducă la
încasări totale cât mai mari.
În acest caz modelul matematic poate fi scris:
maxim f(x1,x2,…xn) = ∑ ; =
n
iii xc
1 ⎪⎩
⎪⎨⎧
=≥
=≤∑=
nix
mjbxa
i
n
ijiij
,10
,11
2)Dacă unitatea productivă dispune de un capital S, care va folosi la
achiziţionarea materiilor prime necesare pentru fabricarea produselor R1,R2,…Rn,
asfel încât încasările totale să fie cât mai mari şi să se recupereze capitalul investit.
Modelul matematic va fi :
maxim f(x1,x2,…xn) = ∑ ; =
n
iii xc
1
⎪⎪⎩
⎪⎪⎨
⎧
=≥≥
≤
∑
∑∑
=
= =
nixSxc
Sxa
i
n
iii
n
i
m
jjiij
,10;1
1 1α
Aceste modele pot fi completate cu numeroase detalii reprezentând condiţii
suplimentare de care trebuie să se ţină seama.
B.Problema aprovizionării (cu o singură marfă) Se ia în considerare un sistem de depozite D1,D2,…Dn: în depozitul Di se află
cantitatea ai de marfă (i= n,1 ). Se ştie că această marfa este destinată unor
consumatori C1,C2,…Cm. Beneficiarul Cj are nevoie de cantitatea bj de marfă (j= m,1 ).
Notăm cu cij (0 ∞≤≤ ijc ) costul transportului unei unitaţi de marfă de la depozitul Di
la consumatorul Cj. Acest model are scopul de a determina cantitaţile xij
( mjni ,1,,1 == ) de marfă ce vor fi scoase din depozitul Di şi trimise beneficiarului Cj,
astfel încât costul transportului întregii cantităţi de produse să fie cât mai mic. Cazul
‘’cij=∞’’ arată că transportul de la Di la Cj este imposibil. Vom prezenta modele care
vor conţine ca restricţii condiţiile ca totalul mărfii extrase dintr-un depozit să nu
Programare liniară
Matematici aplicate in economie
19
depaşească marfa existentă în acel depozit, iar cantitatea totală de marfă primită de
un beneficiar să nu fie sub necesarul acelui beneficiar.
Costul total de transport are forma: . ∑∑= =
n
i
m
jijij xc
1 1
Modelele sunt : minim ; ∑∑= =
n
i
m
jijij xc
1 1
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
==∀≥
=∀=
=∀=
∑
∑
=
=
mjnix
mjbx
niax
ij
n
ijij
m
jiij
,1,,10
,1
,1
1
1
pentru problema echilibrată, în care ∑ ∑= =
=n
i
m
jji ba
1 1
şi pentru problema neechilibrată
minim ; ∑ ∑= =
n
i
m
jijij xc
1 1
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
==∀≥
=∀≥
=∀≤
∑
∑
=
=
mjnix
mjbx
niax
ij
n
ijij
m
jiij
,1,,10
,1
,1
1
1
.
C.Problema de nutriţie
Se ştie din cercetările nutriţioniştilor că un sistem de alimentaţie, într-un
anumit interval de timp trebuie să conţină anumite substanţe active, care se găsesc
în diverse tipuri de alimente.
Notăm cu Si substanţele active necesare i= m,1 ,
Aj alimentele care trebuie procurate j= n,1 şi care conţin aij cantitate
din substanţa Si pe unitatea de aliment Aj.
Notăm cu xj cantitatea din alimentul Aj, cu cj costul unitar al alimentului Aj şi cu
bi necesarul din substanţa Si.
Se pune problema: care sunt cantităţile de alimente xj, care pot fi procurate
mai ieftin, fără abatere de la alimentaţia ştiinţifică.
Modelul matematic este:
minim f(x1,x2,…xn) = ; ∑=
n
iii xc
1 ⎪⎩
⎪⎨⎧
=≥
=≥∑=
nix
mibxa
i
n
jijij
,10
,11 .
Programare liniară
Matematici aplicate in economie
20
Un model asemănător cu acesta prezentat mai sus este problema
amestecurilor de benzine, impunând drept condiţie alegerea celor mai ieftine
amestecuri cu condiţia obţinerii unui produs final cu anumite caracteristici tehnice
(putere calorică, temperatură de aprindere, grad de rafinare) care să fie inferioare
sau superioare unor anumite mărimi prestabilite. Se poate rezolva şi problema
alcătuirii celui mai ieftin amestec din diferite sortimente de cărbune pentru încălzirea
cazanelor cu aburi, cu anumite caracteristici tehnice.
O problema de programare liniară (model de programare liniară) este formata
din:
- o funcţie obiectiv (funcţie scop) care este o funcţie liniară reala cu variabilele
x1,x2,…xn
f(x1,x2,..xn)=c1x1+c2x2+…..+cnxn
- un sistem de restricţii format din ecuaţii şi inecuaţii liniare
- condiţii asupra variabilelor
( de obicei, condiţii de nenegativitate x1 0≥ ,x2 0≥ ,…xn 0≥ )
- un criteriu de optim, care poate fi ‘’minim’’ sau ‘’maxim’’.
Vom folosi matricele
C= , b = , A = , X = . (1)
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
nc
c
.
.1
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
mb
b
.
.1
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
mnm
n
aa
aa
..........
..
1
111
⎟⎟⎟⎟⎟
⎠
⎞
⎜⎜⎜⎜⎜
⎝
⎛
nx
x
.
.1
Se numeşte o restricţie concordantă , o restricţie care:
- în problemele de maxim are semnul “≤ ”
- în problemele de minim are semnul “ ” . ≥
În celelalte cazuri restricţiile se numesc neconcordante.
Din modelele prezentate mai sus s-au dedus două forme particulare ale problemei
de programare liniară, numite forme canonice.
Programare liniară
Matematici aplicate in economie
21
Acestea sunt:
[max] f =TCX; (2) ⎩⎨⎧
≥≤0XbAX
şi [min] f =TCX ; . (3) ⎩⎨⎧
≥≥0XbAX
Am notat cu ‘’X ”, condiţiile care arată că toate componentele vectorului X sunt
nenegative.
0≥
Observaţie. În formele canonice (2) sau (3) ale problemei de programare
liniară, restricţiile sunt concordante.
Se numeşte forma standard a problemei de programare liniară, forma
[min] f =TCX ( sau [max] f = TCX ); . (4) ⎩⎨⎧
≥=0XbAX
Evident că sistemul de restrictii AX=b poate fi incompatibil, compatibil unic
determinat sau compatibil nedeterminat. Numai ultimul caz este cu adevărat
interesant, pentru că numai atunci se pune efectiv problema de a alege din mai
multe soluţii pe cea bună.
Pentru a aduce o problema de programare liniară la forma standard, singura
forma pe care ştim să o rezolvăm, vom adăuga sau scădea noi variabile pozitive
in restrictiile problemei, numite variabile de compensare sau variabile de ecart.
Observaţii.
1) Se poate trece de la o problemă de maxim la una de minim folosind relaţia:
max f = - min (-f ) si invers.
2) Dacă problema de programare liniară nu are forma canonica, atunci se
adaugă sau se scad variabilele de compensare, după cum cere restricţia respectivă.
Exemplu. Să se aducă la forma standard problema de programare liniară
următoare
Programare liniară
Matematici aplicate in economie
22
[max] f = 16x1+20 x2 –2x3+3x4 ; ⎪⎩
⎪⎨
⎧
=≥≥+−≤−++
4,1,010022002
421
4321
jxxxxxxxx
j
Se adaugă o variabilă de compensare la prima restricţie şi se scade o variabilă din a
doua restricţie. Forma standard este
[max] f = 16x1+20 x2 –2x3+3x4; ⎪⎩
⎪⎨
⎧
=≥=−+−=+−++
6,1,010022002
6421
54321
jxxxxx
xxxxx
j
.
Se poate demonstra că orice problemă de programare liniară se poate aduce
la forma standard şi că aceasta are aceleaşi soluţii ca şi problema iniţială.
Soluţiile unei probleme de programare liniară Fie problema de programare liniară (P.L)
[min] f =TCX ; . ⎩⎨⎧
≥=0XbAX
• Un vector X0∈Rn care verifică sistemul de restricţii AX=b, cât şi condiţiile de
nenegativitate X 0 ale unei (P.L) se numeşte soluţie posibilă a problemei
(admisibilă sau realizabilă sau “program”).
≥
• O soluţie posibilă X0 cu numărul de componente nenule, r≤m, iar vectorii matricei
A care corespund componentelor nenule sunt liniar independenţi, se numeşte
soluţie de bază; dacă r< m, soluţia de bază se numeşte degenerată.
• Un vector X0∈Rn, soluţie posibilă pentru (P.L) se numeşte soluţie optimă
(“program optim’’) a problemei (P.L) dacă optimizează funcţia f, adică dacă
pentru orice soluţie posibilă X are loc relaţia TC X0 ≤ TCX.
Toţi algoritmii de rezolvare a unei probleme liniare au o caracteristică
comună: metoda iterativă - se porneşte de la o soluţie posibilă iniţială care se
modifică treptat, până când funcţia de eficienţă devine optimă sau se dovedeşte că
optimul nu există. Esenţa fiecărei metode este determinarea soluţiei iniţiale şi
îmbunatăţirea ei cu un algoritm de calcul. Noi vom prezenta algoritmul lui Dantzig
numit algoritmul simplex.
Metoda simplex, pentru prima dată publicată de americanul G. B. Dantzig în
1947, presupune analizarea anumitor soluţii realizabile de bază şi trecerea de la o
Programare liniară
Matematici aplicate in economie
23
soluţie la alta mai bună, prin schimbarea unui vector din bază. Mai exact, se
porneşte de la o soluţie realizabilă de bază (care se deduce cât mai simplu posibil),
se testează optimalitatea acestei solutii folosind un test de optimalitate. Dacă soluţia
este optimă metoda ia sfârşit, dacă nu, se trece la o altă soluţie de bază,
corespunzătoare unei baze care diferă de precedenta printr-un singur vector.
Alegerea vectorului se face prin criteriul de intrare în bază. Vectorul, pe care acesta
îl înlocuieşte se alege conform criteriului de ieşire din bază.
Criteriul de ieşire din bază se deduce din condiţia de admisibilitate a noii
soluţii; criteriul de intrare în bază se obţine din condiţia ca noua soluţie să
îmbunătăţească valoarea funcţiei de eficienţă.
Determinarea unei soluţii iniţiale de bază Fie problema de programare liniară cu forma canonică:
max f=c1x1+c2x2+…+cnxn ;
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
≥≥≥≤+++
≤+++≤+++
0.....,0,0...
.................................................
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxxbxaxaxa
bxaxaxabxaxaxa
şi presupunem că toţi termenii liberi sunt pozitivi, adică b1 ≥ 0,...,bm ≥ 0, adăugăm
variabilele de compensare: xn+1,xn+2,…xn+m ≥0 şi se obţine forma standard:
max f=c1x1+c2x2+…+cnxn; .
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
≥≥≥=++++
=++++=++++
+
+
+
+
0.....,0,0...
.................................................
21
2211
222222121
111212111
mn
mmnnmnmm
nnn
nnn
xxxbxxaxaxa
bxxaxaxabxxaxaxa
Rangul matricei sistemului de ecuaţii de mai sus este m, deoarece matricea
sistemului conţine exact m vectori unitari, pe care îi vom nota: an+1,an+2,…,an+m.
O soluţie de bază trebuie să aibă maxim m componente nenule. Drept
soluţie iniţială vom lua o soluţie foarte uşor de determinat şi anume: x1=x2-
=….=xn=0, xn+1=b1, xn+2=b2,…, xn+m=bm.
Cum toate componentele termenului liber sunt pozitive, rezultă că soluţia
sistemului de restricţii al problemei de programare liniară:
XT=(0,0,…,0,b1,b2,…bm)∈Rn+m serveşte drept soluţie iniţială de bază.
Programare liniară
Matematici aplicate in economie
24
Observaţie. Se ştie că problema de programare liniară se poate aduce mereu
la forma standard, totuşi condiţia suplimentară b1 ≥ 0 ,...,bm≥0 face ca întotdeauna
soluţia iniţială să poată fi dedusă ca mai sus.
Metoda simplex are în vedere testarea optimalităţii soluţiei de bază (iniţiale)
curente; în caz că soluţia este optimă, algoritmul se opreşte; dacă nu este optimă,
soluţia se modifică prin modificarea unui vector din baza curentă, aplicând criteriul
de intrare în bază; acest nou vector care se alege prin criteriul de intrare în bază,
înlocuieşte un vector din vechea bază, care se alege prin criteriul de ieşire din bază.
Noua soluţie se calculează utilizând metoda Gauss-Jordan. Această soluţie
se va testa la rândul ei, cu criteriul de optimalitate, etc. Algoritmul ia sfârşit după un
număr finit de paşi.
Organizarea calculelor - tabelul simplex Presupunem, fara a reduce generalitatea, că baza curentă B este formată din
primii m vectori ai matricei sistemului de restricţii din forma standard, a1,a2,…,am,
deci primele m componente ale soluţiei x1,x2,…,xm sunt diferite de 0.
Vom nota CB subvectorul lui C format cu componentele lui C corespunzătoare bazei
B. Se observă că vectorii bazei se exprimă în felul următor în baza B:
a1=1⋅a1+0⋅a2+…+0⋅am;a2=0⋅a1+1⋅a2+…+0⋅am;….,am =0⋅a1+0⋅a2+…+1⋅am.
De asemenea, aşa cum am văzut mai sus, toţi vectorii care nu aparţin
bazei se pot exprima prin:
ja
, ∀ j=mj
mjj
j aaaa ααα +++= ......2211 nmm ++ ,1 .
Tabelul simplex pentru baza curentă este următorul:
c1 c2…cr…cm…cj… cm+n θ
CB B xB a1 a2…ar…am…aj… am+n
c1 a1 x1 1 0…..0….0….α1j… α1
m+n
c2 a2 x2 0 1…..0….0….α2j… α2
m+n
. . . ………………………………
cr ar xr 0 0…..1…0…..αrj…. αr
m+n
. . . ……………………………..
cm am xm 0 0…..0…1…..αmj…. αm
m+n
Δk f0 0…0….0….0… Δj … Δm+n
Programare liniară
Matematici aplicate in economie
25
Reguli practice pentru aplicarea algoritmului simplex
1.Criteriul de optimalitate. Dacă toate diferenţele Δk=ck-fk (pentru problema
de maxim) sau Δk= fk-ck (pentru problema de minim) corespunzătoare vectorilor care
nu sunt în baza curentă B sunt negative sau egale cu 0, soluţia XB este optimă şi
algoritmul se opreşte. (fk=TCB⋅aB k)
2.Criteriul de intrare in bază. Dacă cel puţin una dintre diferenţele
corespunzătoare vectorilor care nu se află în baza curentă, este pozitivă, Δk=ck-fk>0
(pentru problema de maxim) sau Δk =fk-ck>0 (pentru problema de minim), atunci
soluţia XB nu este optimă. Se alege max { Δ k | Δ k >0} = Δj . Vectorul aj intră în
bază.
Criteriu de optim infinit. Dacă toate componentele vectorului care intră în
bază (la o anumită iteraţie a simplexului) sunt negative sau nule, problema admite
optim infinit.
3.Criteriul de ieşire din bază. Se aplică după aplicarea criteriului de intrare
în bază. Se adaugă o nouă coloană în tabelul simplex, coloana θ, în care se scriu
rapoartele jk
kxα
, pentru care > 0. Se alege raportul minim: jkα
min ⎭⎬⎫
⎩⎨⎧
⟩0, jkj
k
kxα
α= j
r
rxα
care indică vectorul ar care iese din bază.
4.Stabilirea pivotului. La intersecţia liniei vectorului ar, care iese din bază, cu coloana vectorului aj, care
intră în bază, se află pivotul > 0, care se foloseste în metoda lui Gauss-Jordan jrα
pentru obţinerea noului tabel simplex.
Elementele noului tabel simplex se vor calcula astfel:
-linia pivotului se împarte la pivot;
-coloana pivotului are elementele egale cu 0, cu excepţia elementului de pe locul
pivotului, care este 1;
-celelalte elemente se calculează după regula dreptunghiului: pentru calculul unui
element se formează un dreptunghi care intr-un vârf are pivotul, în vârful opus
Programare liniară
Matematici aplicate in economie
26
elementul pe care vrem să-l înlocuim din vechiul tabel; acest dreptunghi se
calculează ca un determinant de ordin 2, dar cu precizarea că diagonala care se ia
cu semnul + este mereu cea pe care se află pivotul.Valoarea obtinuta se împarte la
pivot si astfel se calculeaza fiecare element din noul tablou simplex.
Se obţine o nouă soluţie. Noua bază B1, va conţine în locul lui ar vectorul aj, iar
coloana lui aj va deveni vector unitar, cu coordonata de ordin r egala cu 1 şi celelalte
0.
E xem plu.Să se rezolve problema de programare liniară, utilizând algoritmul
simplex: max f = 5x1 + 4x2 + 3x3
x1 + 2x2 + 2x3 ≤ 10
2x1 + x2 ≤ 8
2x2 - x3 ≤ 8 x1, x2 ,x3 ≥ 0.
Soluţie. Se aduce problema la forma standard, adăugându-se variabilele de
compensare x4, x5, x6 ≥ 0. Funcţia de eficienţă rămâne neschimbată.
max f = 5x1 + 4x2 + 3x3+0x4+0x5+0x6
x1 + 2x2 + 2x3 + x4 =10
2x1 + x2 +x5 = 8
2x2 - x3 +x6 = 8 xj ≥ 0 , j= 6,1 .
Baza iniţială este baza unitară, formată cu vectorii coloană a4,a5,a6 din
matricea sistemului de restricţii. Soluţia iniţială de bază se alege astfel: x1=x2=x3=0,
x4=10(din prima restricţie), x5=8(din a doua restricţie), x6=8(din a treia restricţie).
Construim tabelul simplex iniţial, în care apare soluţia iniţială de bază, matricea
sistemului de restricţii, baza initiala:
c1= 5 c2= 4 c3= 3 c4= 0 c5 =0 c4 =0
CB B XB a1 a2 a3 a4 a5 a6 θ
0 a4 10 1 2 2 1 0 0 10/1
0 a5 8 (2) 1 0 0 1 0 8/2→
0 a6 8 0 2 -1 0 0 1 -
Δk=ck-fk 0 Δ1=5↑ Δ2=4 Δ3=3 Δ4=0 Δ5 =0 Δ6 =0
Ultima linie a diferenţelor se calculează conform definiţiei , astfel:
Programare liniară
Matematici aplicate in economie
27
f1 = CBT a1 =(0, 0, 0) =0 ; c
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
021
1-f1= 5 – 0 =5
f2 = CBT a2 =(0, 0, 0) =0; c
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
212
2 – f2 = 4 - 0=4
f3= CBT a3 =(0, 0, 0) =0; c
⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
−102
3 – f3 = 3 - 0=3;f4=0; c4-f4=0; f5=0, c5-f5 =0; f6=0, c6-f6=0.
Criteriul de optimalitate se aplică după calcularea diferenţelor Δj. Soluţia nu
este optimă, deoarece nu toate diferenţele sunt negative sau egale cu 0. Vom
schimba baza curentă, prin inlocuirea unui vector în bază. Criteriul de ieşire din bază
indică alegerea max { 5,4,3 } = 5 =c1–f1, deci vectorul a1 intră în bază, j=1. Vom
stabili vectorul care iese din bază şi pentru aceasta adăugăm coloana θ.
Criteriul de ieşire din bază arata ca vectorul care va fi inlocuit in baza este a5,
deoarece min {10,4} = 4= 15
5
αx . Pivotul iteraţiei este 2. Noua bază va fi formată din
vectorii a4, a1, a6.
Calculul elementelor noului tabel se va efectua cu metoda Gauss - Jordan.
Tabloul simplex este urmatorul:
c1= 5 c2= 4 c3= 3 c4= 0 c5 =0 c4 =0
CB B XB a1 a2 a3 a4 a5 a6 θ
0 a4 6 0 3/2 (2) 1 -1/2 0 3→
5 a1 4 1 1/2 0 0 1/2 0 -
0 a6 8 0 2 -1 0 0 1 -
Δk=ck-fk 20 Δ1 =0 Δ2 =3/2 Δ3 =3↑ Δ4 =0 Δ5 =-5/2 Δ6 =0
Soluţia indicată de acest tabel este XT=(4,0,0,6,0,8), iar valoarea funcţiei este
de 20. Aplicăm iar criteriile de optimalitate pentru a studia această soluţie .
Linia diferenţelor arată că soluţia nu este optimă şi intră în bază a3; coloana lui θ
arată ieşe din bază vectorul a4. Pivotul este 2.Noua bază va fi formată din vectorii a3,
a1, a6. Iteraţia corespunzătoare este dată de tabelul de mai jos:
Programare liniară
Matematici aplicate in economie
28
c1= 5 c2= 4 c3= 3 c4= 0 c5 =0 c4 =0
CB B XB a1 a2 a3 a4 a5 a6 θ
3 a3 3 0 3/4 1 1/2 -1/4 0
5 a1 4 1 1/2 0 0 1/2 0
0 a6 11 0 11/4 0 1/2 -1/4 1
Δk=ck-fk 29 Δ1 =0 Δ2=-3/4 Δ3 =0 Δ4=-3/2 Δ5 =-7/4 Δ6 =0
Soluţia corespunzătoare este XT = (4,0,3,0,0,11), iar valoarea functiei de eficienţă
este 29.Testul de optimalitate indică faptul că această soluţie este optimă.
Determinarea unei soluţii iniţiale de bază, când problema are forma canonică: min f=c1x1+c2x2+…+cnxn
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
≥≥≥≥+++
≥+++≥+++
0.....,0,0...
.................................................
21
2211
22222121
11212111
n
mnmnmm
nn
nn
xxxbxaxaxa
bxaxaxabxaxaxa
Presupunem că termenii liberi sunt pozitivi: b1 ≥ 0 ,b2 ≥ 0,…, bm ≥ 0.
Aducem problema la forma standard:
min f=c1x1+c2x2+…+cnxn
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
+=≥=++++
=−+++=−+++
+
+
+
mnjxbxxaxaxa
bxxaxaxabxxaxaxa
j
mmnnmnmm
nnn
nnn
,1,0...
.................................................
2211
222222121
111212111
Dacă procedăm ca in cazul anterior, vom lua drept soluţie iniţială de bază, soluţia:
x1=x2=….=xn=0, xn+1= -b1,xn+2= - b2,…,xn+m= - bm,
însă acesta nu este şi realizabilă, pentru că ea nu satisface condiţiile algoritmului
simplex.
Pentru a obţine o soluţie admisibilă de bază, vom introduce în fiecare
egalitate o nouă variabilă pozitiva, care să înlesnească alegerea soluţiei iniţiale.
Aceste m variabile pe care le introducem se numesc variabile artificiale, iar metoda
de lucru pe care o expunem se numeşte metoda variabilelor artificiale sau
metoda penalizării .
Programare liniară
Matematici aplicate in economie
29
Se modifică şi funcţia de eficienţă astfel :
-dacă problema este de minim, atunci se adaugă la funcţia de eficienţă iniţială,
variabilele artificiale cu coeficienţii de penalizare M (M pozitiv, foarte mare);
-dacă problema este de maxim, atunci se adaugă la funcţia de eficienţă iniţială,
variabilele artificiale cu coeficienţii de penalizare -M (negativ, -∞)
Astfel, după adăugarea variabilelor artificiale xn+m+1, xn+m+2,… xn+2m sistemul
de restricţii devine :
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
+=≥=+++++
=+−+++=+−+++
++
+++
+++
mnjxbxxxaxaxa
bxxxaxaxabxxxaxaxa
j
mmnmnnmnmm
mnnnn
mnnnn
2,1,0...
.................................................
22211
2222222121
1111212111
.
Soluţia iniţială de bază pentru problema cu restricţiile de mai sus poate fi
acum una convenabilă şi anume: x1=x2=….=xn=…=xn+m=0,
xn+m+1=b1,xn+m+2=b2,…xn+2m=bm.
Iniţial, variabilele artificiale sunt în bază; le putem elimina treptat din bază
dacă asociem fiecarei variabile artificiale un coeficient foarte mare în funcţia de
eficienţă, practic ∞, care se numeşte coeficient de penalizare si se notează cu M.
În concluzie, funcţia de eficienţă se modifică, devenind:
min w = c1x1+c2x2+…+cnxn+Mxn+m+1+Mxn+m+2+…Mxn+2m.
Dacă totuşi, la finalul rezolvării problemei de programare liniară prin metoda
variabilelor artificiale cel putin una din variabilele artificiale are vector în baza
optimă, rezultă că problema dată nu admite soluţie.
Exemplu.
Să se rezolve problema de programare liniară, utilizând algoritmul simplex:
min f = 4x1 + 3x2 + 5x3
2x1 + x2 -5x3 ≥300;
x1 + x2 + x3 ≥ 75; x1, x2 ,x3 ≥ 0.
Soluţie. Aducem problema la forma standard fără a modifica f
min f = 4x1 + 3x2 + 5x3
2x1 + x2 -5x3 – x4 =300
x1 + x2 + x3 - x5 = 75; xj ≥ 0 5,1=j .
Programare liniară
Matematici aplicate in economie
30
Vom adăuga variabilele artificiale x6, x7, introducându-le în restricţii cu
coeficientul 1 şi în funcţia de eficienţă cu coeficientul de penalizare M:
min w = 4x1 + 3x2 + 5x3+Mx6+Mx7
2x1 + x2 - 5x3 – x4+ x6 =300
x1 + x2 + x3 - x5 + x7= 75
xI ≥ 0, l=1,7.
Soluţia iniţială de bază este x1=x2=x3=x4=x5=0, x6=300, x7=75.
Calculele aferente algoritmului simplex sunt redate în tabelul următor. Pentru calculul
liniei diferenţelor şi stabilirea criteriilor de optimalitate şi de intrare în bază se
foloseşte Δj=fj–cj. La prima iteraţie, se calculeaza max {Δ1=3M–4, Δ2=2M-3}=Δ1, a1
intră în bază.
c1= 4 c2= 3 c3= 5 c4= 0 c5= 0 c6= M c7= M
CB B XB a1 a2 a3 a4 a5 a6 a7 θ
M a6 300 2 1 - 5 -1 0 1 0 150
M a7 75 (1) 1 1 0 - 1 0 1 75→
Δk=fk- ck 3M-4↑ 2M-3 -4M-5 - M - M 0 0
M a6 150 0 -1 -7 -1 (2) 1 - 75
4 a1 75 1 1 1 0 -1 0 - -
Δk=fk- ck 0 -M+1 -7M-1 -M 2M-4↑ 0 -
0 a5 75 0 -1/2 -7/2 - 1/2 1 - -
4 a1 150 1 1/2 - 5/2 - 1/2 0 - -
Δk=fk- ck 600 0 -1 - 15 -2 0 - -
O variabilă artificială care iese din bază, nu va mai intra în bază, fapt care justifică
eliminarea din calcul a coloanelor a7 şi a8 din tabelul de mai sus.
Soluţia optimă a problemei este: x1=150, x2=x3=x4=0, x5=75, min f =600.
Soluţie optimă multiplă.Calcul soluţiei optime generale
Dacă o problemă de programare liniară are mai multe soluţii optime de bază, atunci
orice combinaţie liniară convexă a acestor soluţii este de asemenea o soluţie optimă.
O soluţie este multiplă dacă în iteraţia optimă Δj=0 pentru un vector aj care nu
aparţine bazei, atunci este posibil să introducem în bază vectorul aj pentru a
determina altă soluţie optimă care va conduce la aceeaşi valoare a funcţiei de
eficienţă.
Programare liniară
Matematici aplicate in economie
31
Exemplu. Se face un amestec de uleiuri minerale U1,U2,U3,U4, în vederea obtinerii unui
produs finit cu anumite calităţi şi în cantitate de cel puţin 800 l. Amestecul trebuie să
conţină substanţele S1 şi S2 în cantitate de cel puţin 18000 g, respectiv 21000
g.Conţinutul de substanţe S1 şi S2 ale fiecărui tip de ulei şi costurile unitare sunt date
in tabelul urmator:
Uleiuri (conţinut în g/ l)
Substanţe
U1
U2
U3
U4
Necesar (g)
S1 20 10 30 20 18000
S2 10 20 10 30 21000
Cost unitar(Mii u.m./t) 5 4 4,5 3
Cum trebuie făcut amestecul cu cost total minim? Ce cantitate din fiecare ulei trebuie
pusă in acest amestec?
Soluţie.
Fie xi, 4,1=i cantităţile din uleiurile Ui care trebuie puse în amestec. Funcţia de
eficienţă este costul total al amestecului. Ea trebuie minimizată:
min f = 5 x1+4x2+4,5 x3+3x4 (mii u.m.)
Restricţia referitoare la cantitate este:
x1+x2+x3+x4 ≥ 800.
Celelalte două restricţii se referă la substanţele S1 şi S2 necesare
amestecului:
20 x1+10x2+30x3+20x4 ≥ 18000
10 x1+20x2+10x3+30x4 ≥ 21000.
Condiţiile de nenegativitate asupra variabilelor sunt:x1 ,x2 , x3, x4 ≥ 0.
Deci, modelul matematic al problemei de amestec este :
min f = 5x1+4x2+4,5 x3+3x4
x1+x2+x3+x4 ≥ 800; 20 x1+10x2+30x3+20x4 ≥ 18000;10 x1+20x2+10x3+30x4 ≥ 21000
x1 ,x2 , x3 , x4 ≥ 0.
Împărţim cu 10 restricţiile doi şi trei si se aduce problema la forma standard :
Programare liniară
Matematici aplicate in economie
32
min f =5 x1+4x2+4,5 x3+3x4
x1+x2+x3+x4 –x5 = 800
2 x1+x2+3x3+2x4 – x6 = 1800
x1+2x2+x3+3x4 – x7 = 2100; xj ≥ 0, 7,1=j
Pentru a reduce calculele, vom scădea din ecuaţia cu termenul liber cel mai mare,
pe rând fiecare dintre ecuaţiile sistemului de restricţii, adică din ecuaţia a treia se
scade prima şi apoi a doua şi astfel se obţine un sistem echivalent cu cel dat.
Matricea ataşată acestui ultim sistem este :
A= ⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
−−−−−
100312111012111012010
conţine doi vectori unitari a5 şi a6; nu este nevoie pentru determinarea soluţiei iniţială
de bază decât de o singură variabilă artificială, x8 şi va fi adăugată la ultima restricţie.
Problema de programare liniară devine :
min f =5 x1+4x2+4,5 x3+3x4+Mx8
x2 +2x4 +x5 –x7 = 1300
- x1+x2 - 2x3+x4 + x6 – x7 = 300
x1+2x2+x3+3x4 – x7 +x8= 2100; xj ≥ 0, j=1,..,8.
5 4 4,5 3 0 0 0 M
CB B XB a1 a2 a3 a4 a5 a6 a7 a8 θ
0 a5 1300 0 1 0 2 1 0 -1 0 650
0 a6 300 -1 1 -2 (1) 0 1 -1 0 300→
M a8 2100 1 2 1 3 0 0 -1 1 700
Δk=fk- ck M-5 2M-4 M-4,5 3M-3↑ 0 0 -M 0
0 a5 700 2 -1 4 0 1 -2 1 0 700/4
3 a4 300 -1 1 -2 1 0 1 -1 0 -
M a8 1200 4 -1 (7) 0 0 -3 2 1 1200/7→
Δk=fk–ck 4M-8 -M-1 7M-0,5↑ 0 0 -3M+3 2M-3 0
0 a5 100/7 -2/7 -3/7 0 0 1 -2/7 -1/7 -
3 a4 4500/7 1/7 5/7 0 1 0 1/7 -3/7 -
4,5 a3 1200/7 4/7 -1/7 1 0 0 -3/7 2/7 --
Δk=fk–ck 2700 -2 -2,5 0 0 0 -1,5 0*
Programare liniară
Matematici aplicate in economie
33
Soluţia optimă este XoT=(0,0,
71200 ,
74500 ,
7100 , 0 ,0), iar valoarea minimă a funcţiei
de eficienţă este f min = 2700.
Pe linia diferenţelor f7- c7 = 0, fără ca vectorul a7 să fie în bază. Pentru a determina o
altă soluţie optimă vom introduce în bază vectorul a7 şi vom construi un nou tabel
simplex
5 4 4,5 3 0 0 0
CB B XB a1 a2 a3 a4 a5 a6 a7 θ
0 a5 100 0 -1/2 1/2 0 1 -1/2 0
3 a4 900 1 1/2 3/2 1 0 -1/2 0
0 a7 600 2 -1/2 7/2 0 0 -3/2 1
Δk =fk –ck 2700 -2 -2,5 0 0 0 -1,5 0
Soluţia optimă obţinută este X1T=( 0 , 0 , 0, 900, 100, 0 , 600) .
Se poate construi o combinaţie liniară convexă a celor două soluţii optime care
reprezintă soluţia optimă generală:
X(λ) = λX0+(1-λ)X1, λ∈[0,1]
Pentru orice λ∈[0,1], f(X(λ))=4,5⋅ λ7
1200 +3⋅(900 - λ7
1800 ) = 2700, adică valoarea
funcţiei de eficienţă rămâne minimă.
Rezolvarea unei probleme de programare liniară care nu are forma canonica. In acest caz, se aduce problema la forma standard, cu toţi termenii liberi
ai sistemului de restricţii pozitivi. Matricea sistemului corespunzător problemei adusă
la forma standard va indica care sunt vectorii coloană unitari existenţi si daca este
necesar se va aplica metoda penalizării.
Vom construi tabelul simplex, cu baza iniţială formată din vectori unitari, care pot fi:
- vectori corespunzători variabilelor problemei sau
- vectori corespunzători variabilelor de compensare sau
- vectori corespunzători variabilelor artificiale.
Exemplu. Să se rezolve problema de programare liniară:
max f = 10x1 + 6x2 -2x3+ 4x4
2x1 + x2 -2x4 =300
2x2 + x3+x4 ≤ 600
x1 +2x2+ x3 +x4 ≥ 120 ; x1, x2 ,x3 ,x4 ≥ 0.
Programare liniară
Matematici aplicate in economie
34
Soluţie. Aducem problema la forma standard, prin adăugarea variabilelor de
compensare x5 şi x6:
2x1 + x2 -2x4 = 300 2x2 +x3+ x4 +x5 = 600 x1 +2x2+ x3 + x4 - x6 = 120; xj ≥ 0, j= 6,1 .
Matricea sistemului de restricţii este acum : A= . ⎟⎟⎟
⎠
⎞
⎜⎜⎜
⎝
⎛
−
−
101121011120002012
Ea conţine un singur vector unitar, vom adăuga două variabile artificiale, notate x7 şi
x8 la restricţia întâi şi a treia. Astfel, problema devine:
max f = 10x1 + 6x2 -2x3+ 4x4 -Mx7 – Mx8 2x1 + x2 -2x4 +x7 = 300 2x2 +x3+ x4 +x5 = 600 x1 +2x2+ x3 + x4 -x6 +x8 = 120; xj ≥ 0, j= 8,1 . Acum baza iniţială va fi formată din vectorii unitari a5,a7, a8
10 6 -2 4 0 0 -M -M
CB B XB a1 a2 a3 a4 a5 a6 a7 a8 θ
-M a7 200 (2) 1 0 -2 0 0 1 0 100→
0 a5 600 0 2 1 1 1 0 0 1 -
-M a8 120 1 2 1 1 0 -1 0 0 120
cj-fj 10+3M↑ 6+3M -2+M 4-M 0 -M 0 0
10 a1 100 1 1/2 0 -1 0 0 - 0 -
0 a5 600 0 2 1 1 1 0 - 0 600
-M a8 20 0 3 /2 1 (2) 0 -1 - 1 10→
cj-fj 0 3/2M+1 -2+M 2M+14↑ 0 -M - 0
10 a1 110 1 5/4 1/2 0 0 - 1/2 - - -
0 a5 590 0 5/4 1/2 0 1 (1/ 2) - - 1180→
4 a4 10 0 3/4 1/2 1 -1/2 - - -
cj-fj 1140 0 -19/2 -9 0 0 7↑ - -
10 a1 700 1 5/2 1 0 1 0 - -
0 a6 1180 0 5/2 1 0 2 1 - -
4 a4 600 0 2 1 1 1 0 - -
cj-fj 9400 0 -27 -16 0 -14 0
Solutia optima este XT=( 700 , 0 , 0, 600, 0, 1180 ).
Programare liniară
Matematici aplicate in economie
35
Exemplu de problemă care nu admite soluţie Să se rezolve problema de programare liniară, utilizând algoritmul simplex:
max f = 2x1 + x2 + 2x3
5x1 + x2 + x3 ≤ 20
-x1 + x2 + x3 = 30 ; x1, x2 ,x3 ≥ 0.
Soluţie. Aducem problema la forma standard adăugând variabila de compensare x4
la restricţia întâi şi variabila artificială x5 la restricţia a doua .
max w = 2x1 + x2 + 2x3 - Mx5
5x1 + x2 + x3+ x4 =20
-x1 + x2 + x3 +x5 =30; xj ≥ 0 5,1=j .
c1=2 c2=1 c3=2 c4=0 c4= - M
CB B XB a1 a2 a3 a4 a5 θ
0 a4 20 5 1 (1) 1 0 20→
-M a5 30 -1 1 1 0 1 -
cj-fj 2-M 1+M 2+M↑ 0 0
2 a3 20 5 1 1 1 0
-M a5 10 -6 0 0 -1 1
cj-fj -8-6M -1 0 -2-M 0
Ultima iteraţie a tabelului de mai sus indică optimalitatea soluţiei datorită faptului că
toate diferenţele sunt Δj = c j- fj sunt negative sau 0.
Totuşi variabila artificială x5 , a rămas în bază cu valoarea 10, x5≠0; deci problema
initiala nu admite soluţie.
Probleme propuse
1. O întreprindere fabrică trei tipuri de produse folosind gaz metan şi apă.
Consumurile specifice, disponibilul de apă şi gaz, precum şi beneficiile nete unitare
sunt date în tabelul de mai jos:
Produse Consumuri specifice
Resurse P1 P2 P3 Disponibil
Apă 2 3 2 40.000 t
Gaz metan 10 50 30 500.000 mc
Beneficiu unitar 10 15 25
Programare liniară
Matematici aplicate in economie
36
a) Cum se organizează producţia, dacă se urmăreşte maximizarea
beneficiului total?
b) Dacă îşi propune acelaşi scop, cu aceleaşi resurse, dar trebuie să
producă cel puţin 3000 unităţi din P1,cum trebuie organizată producţia?
2. Să se rezolve problemele:
a) min f = 3x1 - 2x2 + x3 b) max f = 3x1 + 2x2 – x3 +16 x4
3x1 + x2 - 2 x3 = 2 3x1+2x2+5x3+4x4≤ 8
4x1 +3x2 +2 x3= 1 x1+x2+2x3+x4 ≤ 4
x1, x2 , x3 ≥ 0 x1, x2 , x3 ,x4 ≥ 0 .
3. O maşină produce trei produse P1,P2,P3.Produsul P1 aduce întreprinderii un venit
de 3 u.m. pe unitatea de produs, P2 de 12 u.m. iar P3 de 4 u.m. Randamentul maşinii
este de 75, 25 şi respectiv 50 bucăţi/oră pentru P1,P2,P3. Vânzările sunt limitate
pentru P1 la 1500, pentru P2 la 500 şi pentru P3 la 1000 bucăţi.Ştiind că maşina
lucreză săptămânal 45 ore, să se determine repartiţia producţiei, astfel încât
beneficiul să fie maxim.
4.Să se rezolve următoarele probleme de programare liniară:
a) min f = 4x1 + 8x2 +3x3 b) max f = 10 x1 +15 x2
2x1 + x2 +3x3 ≥ 4 2x1 +4x2 ≤ 40
5x1 + 2x2 +7x3 ≥ 8 6x1 +2x2 ≤ 60
x1, x2,x3 ≥ 0 x1, x2 ≥ 0
c) max f = 4x1 + x2 +6 x3 d) min f = x1 +3x2 –4x3 - 2x4 -9x5
2x1 +3x2 +x3 ≥ 7 x1 + x3 – x4 – x5 = 3 3x1 + x2 +x3 ≤ 11 x1 +x2 –2x3 - 3x5 = -1
x1, x2, x3 ≥ 0 x1, x2, x3 ,x4, x5 ≥ 0
e) min f = 9x1 + 3x2 +2 x3 f) max f = x1 + 2x2 +3x3 - x4
4x1 + x2 +5 x3 = 7 x1 +2x2 +3x3 =15
3x1 + x2 +4 x3 ≥ 5 2 x1+ x2 + 5x3 =20
x1, x2 , x3 ≥ 0 x1 +2x2 + x3 +x4 =10; x1, x2 ,x3,x4 ≥ 0.
g) max f = x1 + 3x2 +6x3 h) min f = 6x1 + x2
5x1 +2x2 +3x3 =11 x1 +2 x2 ≥ 3
3x1 + x2 +2x3 ≤ 8 3x1 + x2 ≥ 4
x1, x2 , x3 ≥ 0 x1, x2 ≥ 0
Programare liniară
Matematici aplicate in economie
37
5. Să se determine valoarea maximă şi minimă a funcţiei
f = 9x4 -14x5 -8 x6
cu restricţiile
x1 + x4 – x5 – x6 = 2
x2 - 5x4 + 4x5 + 7x6 = 2
x3 + 2x3 + x5 – x6 = 5
x1, x2, x3 ,x4, x5, x6 ≥ 0
6. Să se determine maximul funcţiei f = x1 + 2x2 +2x3 +x4 cu restricţiile
x1 – x3 + 21 x4 = 1;
x2 + x3 – x4 = 1;
x1, x2, x3 ,x4 ≥ 0
7. Să se determine minimul funcţiei f = x2 -2 x3 + 2 x5
in condiţiile
x1 + 3x2 - x3 + 2x5 = 7
-2x2 + 4x3 +x4 = 12
-4x2 + 3x3 + 8x5 + x6 = 10
x1, x2, x3 ,x4, x5, x6 ≥ 0
top related