Unitatea de învăţare 3 PROGRAMAREA LINIARĂ Obiectivele unităţii de învăţare: • înţelegerea şi însuşirea principalelor (celor mai uzuale) metode de rezolvare a problemelor de programare liniară; • însuşirea cunoştinţelor teoretice privind variantele de formulări generale ale unei probleme de programare liniară, domeniile sale de aplicare, teoremele matematice fundamentale, problematica programelor duale. • însuşirea cunoştinţelor de bază şi deprinderilor practice necesare pentru aplicarea metodei programării liniare la rezolvarea problemelor specifice ingineriei sistemelor de producţie. Cuprinsul unităţii de învăţare: 3.1. Formularea problemei de programare liniară. Domenii de aplicare 2 3.1.1. Formularea generală a problemei programării liniare 2 3.1.2. Domeniile de aplicare a programării liniare 5 Teste de autoevaluare (secţiunea 3.1) 6 3.2. Metode de rezolvare a problemelor de programare liniară 7 3.2.1. Teoremele fundamentale ale programării liniare 7 3.2.2. Metoda grafică şi metoda variabilelor de ecart 9 Teste de autoevaluare (secţiunea 3.2) 15 Problemă propusă (secţiunea 3.2) 15 3.3. Metoda simplex pentru rezolvarea problemelor de programare liniară. Programe duale 16 3.3.1. Metoda simplex 16 3.3.2. Programe duale. Reguli pentru construirea programului dual 23 Teste de autoevaluare (secţiunea 3.3) 24 Probleme propuse (secţiunea 3.3) 25 Bibliografie 25 Soluţiile problemelor propuse (secţiunea 3.3) 26
Transcript
Unitatea de învăţare 3
PROGRAMAREA LINIARĂ
Obiectivele unităţii de învăţare: • înţelegerea şi însuşirea principalelor (celor mai uzuale) metode de
rezolvare a problemelor de programare liniară; • însuşirea cunoştinţelor teoretice privind variantele de formulări
generale ale unei probleme de programare liniară, domeniile sale de aplicare, teoremele matematice fundamentale, problematica programelor duale.
• însuşirea cunoştinţelor de bază şi deprinderilor practice necesare pentru aplicarea metodei programării liniare la rezolvarea problemelor specifice ingineriei sistemelor de producţie.
Cuprinsul unităţii de învăţare:
3.1. Formularea problemei de programare liniară. Domenii de aplicare 2 3.1.1. Formularea generală a problemei programării liniare 2 3.1.2. Domeniile de aplicare a programării liniare 5
Teste de autoevaluare (secţiunea 3.1) 6 3.2. Metode de rezolvare a problemelor de programare liniară 7
3.2.1. Teoremele fundamentale ale programării liniare 7 3.2.2. Metoda grafică şi metoda variabilelor de ecart 9
Teste de autoevaluare (secţiunea 3.2) 15 Problemă propusă (secţiunea 3.2) 15
3.3. Metoda simplex pentru rezolvarea problemelor de programare liniară. Programe duale 16 3.3.1. Metoda simplex 16 3.3.2. Programe duale. Reguli pentru construirea programului dual 23
Teste de autoevaluare (secţiunea 3.3) 24 Probleme propuse (secţiunea 3.3) 25
În continuare, în cadrul următoarelor părţi ale cursului, se va pune accent pe prezentarea unora din metodele cercetării operaţionale, care (după cum s-a arătat în subsecţiunea 1.4.2, unde s-a realizat o caracterizare generală a acestora) sunt principalele metode matematice specifice ingineriei sistemelor de producţie. În cadrul unităţilor de învăţare 3 şi 4, vor fi studiate metodele programării matematice (liniară – abordată în continuare, neliniară şi dinamică), dezvoltate ca metode de rezolvare a problemei programării de optimizare, a cărei formulare generală este prezentată în subsecţiunea 1.4.3.
Programarea liniară este poate cea mai răspândită şi utilizată metodă a cercetării operaţionale, destinată rezolvării unei clase speciale – deseori întâlnită în practică – de probleme ale programării de optimizare, şi anume cele în care funcţia obiectiv este o funcţie liniară, iar sistemul de restricţii cuprinde inecuaţii liniare nestricte.
Prezentăm, în cele ce urmează, variante ale formulării generale a unei probleme de programare liniară, care mai este numită şi program liniar, iar apoi sunt abordate principalele domenii de aplicare ale acestui tip de probleme
3.1.1. Formularea generală a problemei programării liniare
Formularea unei probleme de programare liniară se poate obţine prin particularizarea formulării generale prezentate în subsecţiunea 1.4.3, rezultând enunţul de mai jos:
Să se determine valorile numerice pentru mulţimea de variabile (necunoscute ale problemei) xj, 1 ≤ j ≤ n, care satisfac următorul sistemul de m (in)egalităţi liniare:
ai1x1 + ai2x2 + ... + ainxn ≤ [ ≥ , = ] bi, 1 ≤ i ≤ m , aij, bi ∈R (3.1)
şi condiţiile de nenegativitate:
x1 ≥ 0 , x2 ≥ 0 ,... , xn ≥ 0 , (3.2)
pentru care funcţia liniară
F = c1x1 + c2x2 +...+ cnxn cj ∈R (3.3)
îşi atinge maximul sau minimul. Precizăm că, în formularea prezentată mai sus, (3.1) reprezintă sistemul
de restricţii al problemei (inegalităţi şi/sau egalităţi); (3.3) – funcţia obiectiv, iar xj – variabilele de stare ale sistemului (problemei) analizat, ce au sens în cazurile practice doar dacă sunt pozitive (mai mari sau egale cu zero), adică îndeplinesc condiţiile (3.2).
Definiţia 1: Se spune că o problemă de programare liniară este în (are) forma canonică dacă toate restricţiile ei sunt inegalităţi concordante şi tuturor variabilelor li se impun condiţii de nenegativitate. (O restricţie – de tip inegalitate – a unei probleme de programare liniară se numeşte concordantă dacă este o inegalitate de tipul „≤” când se cere maximizarea
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
3
funcţiei obiectiv şi de tipul „≥” când se cere minimizarea acestei funcţii. În caz contrar, restricţia se numeşte neconcordantă.)
În consecinţă, o problemă în formă canonică de maximizare se poate scrie condensat (folosind simboluri de însumare) astfel:
∑=
≤n
jijij bxa
1
, i = 1, 2, …, m
xj ≥ 0 , j = 1, 2, …, n (3.4)
∑=
=n
jjj xcF
1= maxim ,
iar o problemă în formă canonică de minimizare se va scrie astfel:
∑=
≥n
jijij bxa
1 , i = 1, 2, …, m
xj ≥ 0 , j = 1, 2, …, n (3.5)
∑=
=n
jjj xcF
1= minim .
Observaţia A: Orice problemă de programare liniară poate fi pusă sub o formă canonică de orice tip (de maximizare sau de minimizare), fără a fi afectată soluţia problemei. Astfel:
• o egalitate se poate înlocui cu două inegalităţi de sens contrar; • o inegalitate neconcordantă devine concordantă prin înmulţire cu „-1”; • problema minimizării funcţiei F se poate reduce la problema
maximizării funcţiei -F, prin relaţia de mai jos:
min F = -max (-F), în care: -F = (-c1) x1 + (-c2) x2 +...+ (-cn) xn . (3.6)
Definiţia 2: Se spune că o problemă de programare liniară este în (are) forma standard dacă toate restricţiile sunt egalităţi (ecuaţii) şi tuturor variabilelor li se impun condiţii de nenegativitate.
Observaţia B: Orice problemă de programare liniară poate fi adusă la forma standard, deoarece sistemul de inegalităţi (3.1) se poate transforma într-un sistem de ecuaţii prin ataşarea de variabile de ecart, yi = xn+i ≥ 0, la partea stângă a fiecărei inecuaţii. Numărul variabilelor de ecart, care – la rândul lor – trebuie să îndeplinească condiţii de nenegativitate, al unei probleme de programare liniară este întotdeauna egal cu numărul de restricţii m din sistemul de inecuaţii (3.1).
Forma standard a unei probleme de programare liniară, pe baza observaţiei de mai sus, este alcătuită din aceleaşi trei elemente, şi anume:
• funcţia obiectiv (în care variabilele de ecart introduse nu apar sau apar cu coeficienţi egali cu zero, ca în relaţia de mai jos):
• sistemul de restricţii, devenit un sistem de m ecuaţii (cu n + m necunoscute):
Conf. dr. ing. Andrei Dumitrescu
4
ai1x1 + ai2x2 + ... + ainxn + yi = bi, 1 ≤ i ≤ m . (3.9)
Relaţia (3.9) este valabilă pentru inecuaţii cu semnul „≤”. Dacă inegalităţile au sens contrar (≥ bi), în forma standard se vor folosi variabile de ecart cu semnul minus (- xn+i).
Forma condensată standard a unei probleme de programare liniară cu variabilele de ecart xn+i = yi este următoarea:
Forma matriceală a unei probleme de programare liniară se obţine definind următorii vectori şi matrice:
• vectorul linie al coeficienţilor funcţiei obiectiv: C = [c1 c2 ... cn] ;
• vectorul coloană al termenilor liberi din (3.1): B =
⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢
⎣
⎡
nb
bb
...2
1
;
• vectorul coloană al variabilelor de stare: X =
⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢
⎣
⎡
nx
xx
...2
1
;
• vectorul coloană al variabilelor de ecart: E =
⎥⎥⎥⎥
⎦
⎤
⎢⎢⎢⎢
⎣
⎡
+
+
+
mn
n
n
x
xx
...2
1
;
• matricea coeficienţilor sistemului (3.1): A = [aij] njmi
≤≤≤≤
11 .
Cu aceste notaţii, forma canonică matriceală de maximizare, respectiv cea de minimizare, se pot scrie astfel:
⎩⎨⎧
≥≤⋅=⋅=
OXBXAXC ,
.maxF ; (3.10)
⎩⎨⎧
≥≥⋅=⋅=
,min.
OXBXAXC,
F (3.11)
unde O este vectorul coloană nul (toate elementele sale sunt egale cu zero). Forma standard matricială este:
⎪⎩
⎪⎨
⎧
≥≥=⋅+⋅=⋅+⋅=
OEOXBEIXA
EOXC
,
.maxtF , (3.12)
unde I este matricea unitate. Prin alipirea vectorilor X şi E (în X’), C şi O (în C’) şi a matricelor A şi
I (în A’), forma standard devine:
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
5
F = C’⋅X’ = max. (min.) (3.13) A’⋅X’ = B X’ ≥ O .
3.1.2. Domeniile de aplicare a programării liniare Principalul domeniu de aplicare al programării liniare îl constituie
problemele de alocare optimă a resurselor limitate (repartiţie de resurse), care apar frecvent în activitatea de conducere a sistemelor de producţie. Astfel, sunt disponibile mai multe resurse (materii prime, utilaje, forţă de muncă, energie, capital etc.) în cantităţi limitate. Cu ajutorul acestor resurse, trebuie să se desfăşoare mai multe activităţi (de regulă economice, ca de exemplu realizarea unor procese de producţie). Problema constă în determinarea nivelului fiecărei activităţi considerate, astfel încât toate activităţile să se încadreze în limitările precizate ale resurselor şi să fie asigurată satisfacerea unui anumit criteriu, unic, de optimizare (exprimat printr-o funcţie obiectiv), cum ar fi: maximizarea profitului, minimizarea cheltuielilor etc.
Se consideră că avem la dispoziţie m resurse diferite, pentru realizarea a n activităţi (fabricarea unor produse). Se notează cu bi cantitatea disponibilă din resursa de ordin i (1 ≤ i ≤ m), iar cu xj nivelul (necunoscut iniţial) de desfăşurare al activităţii de rang j (sau cantitatea în care este realizat un anumit produs, j) din cele n considerate (1 ≤ j ≤ n). În mod evident, variabilele xj trebuie să satisfacă condiţiile de nenegativitate (3.2). Atunci, aij reprezintă cantitatea de resursă i necesară realizării unei unităţi cantitative a produsului (activităţii) j. Dacă se face ipoteza că aij nu depinde de cantitatea produsă xj (ceea ce constituie o simplificare), sistemul de restricţii (3.1) – toate inegalităţi de tipul „≤” – exprimă condiţia ca nivelul disponibil din resursa i, bi, să nu fie depăşit de cantitatea totală necesară din resursa i. Se urmăreşte determinarea variabilelor xj în vederea obţinerii unui profit maxim (exprimat prin funcţia obiectiv, F). Dacă se urmăreşte maximizarea profitului, în expresia (3.3) a lui F, cj = ej - dj , unde ej este preţul de vânzare şi dj reprezintă cheltuielile de producţie (costul), ambele pentru unitatea cantitativă de produs j. Şi aici se face ipoteza simplificatoare că ej şi dj nu depind nici ele de cantitatea produsă din sortimentul j. Pentru acest caz, se poate da o interpretare precisă şi variabilelor de ecart (numite uneori şi variabile de abatere), yi; astfel, yi reprezintă cantitatea neutilizată (neconsumată) din resursa i.
Alte aplicaţii importante ale programării liniare sunt următoarele: 1) Lansarea în fabricaţie (utilizarea optimă a capacităţii utilajelor
disponibile): se dă un număr de operaţii ce se pot executa pe un număr de utilaje diferite şi se cere repartizarea optimă a operaţiilor pe utilaje, astfel încât timpul (cheltuielile) de producţie să fie minime.
2) Problema de transport sau de distribuire (a se vedea secţiunea 4.1): distribuţia unui produs de la m centre de aprovizionare (depozite, unităţi productive etc.) la n centre de consum (unităţi productive, puncte de desfacere, magazine etc.), cu minimizarea costurilor de transport.
3) Problema amestecurilor (a dietei): determinarea modului de amestecare (cantitatea xj din fiecare element disponibil j) a n elemente disponibile sau substanţe necesare într-un amestec (aliaj, ulei etc.), ce trebuie să aibă anumite proprietăţi (exprimate matematic prin m restricţii liniare), urmărindu-se minimizarea cheltuielilor de obţinere a produsului final (amestecului), exprimate prin funcţia obiectiv F, în care cj este preţul unitar al
Conf. dr. ing. Andrei Dumitrescu
6
elementului j. Problema se aplică şi în cazul dietei unei colectivităţi (animalele dintr-o crescătorie, personalul unei unităţi militare etc.), caz în care restricţiile se referă la anumite cerinţe de nutriţie ale unui „amestec” de alimente.
4) Planificarea investiţiilor într-un sistem de producţie. În cazul celei mai simple formulări, se consideră că dispunem de o sumă totală, S, ce poate fi investită în diverse activităţi j, fiecare producând un profit unitar cj. Se pune problema stabilirii sumei xj, investită în activitatea j, astfel încât profitul total să fie maxim. Din punctul de vedere matematic, problema cuprinde funcţia obiectiv (3.3), condiţiile de nenegativitate (3.2) şi o singură restricţie, exprimată prin egalitatea:
x1 + x2 + … + xn = S . (3.14)
5) Amplasarea unei unităţi de producţie în funcţie de cerinţele pieţei (cu scopul maximizării profitului, a minimizării riscului etc.).
6) Evaluarea muncii depuse de angajaţi sau a salariilor acestora. 7) Manipularea materialului cu minimizarea pierderilor. 8) Planificarea producţiei (în vederea minimizării preţului de cost). 9) Ordonanţarea producţiei / fabricaţiei (în timp).
În încheiere, menţionăm că domeniile de aplicare enunţate mai sus sunt valabile pentru toate domeniile programării matematice (programare neliniară, pătratică, dinamică, stohastică etc.). O aplicaţie concretă se poate modela atât cu ajutorul programării liniare – în general, dacă se fac unele ipoteze simplificatoare ce conduc la liniarizarea problemei – cât şi cu al celei neliniare, dacă se adoptă un model mai complex şi deci mai apropiat de realitate. De multe ori, în practică, se preferă adoptarea ipotezelor de liniaritate, deoarece modelele matematice liniare sunt mai simple, iar pe baza acestora se pot formula concluzii calitative care îşi menţin valabilitatea –în anumite limite– şi într-un context neliniar.
Teste de autoevaluare (secţiunea 3.1)
1. Care este diferenţa dintre forma standard şi forma canonică a unei probleme de programare liniară?
2. De ce sunt necesare condiţiile de ne-negativitate în formularea unei probleme de programare liniară? Credeţi că ele sunt necesare şi în formularea unei probleme de programare neliniară?
3. Ce reprezintă inegalităţile concordante în cazul unei probleme de programare liniară? De ce este necesară definirea acestei noţiuni?
4. Ce avantaje credeţi că prezintă forma matriceală a unei probleme de programare liniară?
5. Indicaţi o aplicaţie concretă a programării liniare. Consideraţi că aplicaţia indicată poate fi rezolvată şi cu ajutorul programării neliniare?
6. Care sunt principalele domenii de aplicare ale programării liniare în domeniul ingineriei sistemelor de producţie?
7. Care este rolul variabilelor de ecart în formularea unei probleme de programare liniară?
8. Prezentaţi succint formularea problemei amestecurilor şi indicaţi o situaţie concretă care să corespundă acestei probleme.
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
7
3.2. Metode de rezolvare a problemelor
de programare liniară
În cele ce urmează, după enunţarea teoremelor care stau la baza tuturor metodelor de rezolvare a problemelor de programare liniară, vor fi abordate, în principal cu scop didactic, metoda grafică şi metoda variabilelor de ecart, a căror înţelegere este esenţială pentru însuşirea tuturor celorlalte metode, dintre care va fi studiată metoda simplex, în secţiunea 3.3.
3.2.1. Teoremele fundamentale ale programării liniare În această subsecţiune, vor fi enunţate, fără demonstraţie (demonstraţiile,
pur matematice, nu prezintă interes din punctul de vedere al acestui curs), o serie de teoreme ce reprezintă baza matematică a metodelor de rezolvare a problemelor de programare liniară. Înainte de a enunţa aceste teoreme, sunt necesare însă câteva definiţii şi observaţii importante, care se referă la o problemă de programare liniară formulată sub forma standard corespunzătoare relaţiilor (3.7), (3.8) şi (3.9).
Definiţia 1: Se numeşte soluţie a unei probleme de programare liniară (exprimată în forma standard) o mulţime de n+m valori ale variabilelor xj (inclusiv cele de ecart) care satisfac sistemul restricţiilor (3.9). Definiţia 2: Se numeşte soluţie admisibilă (posibilă) a aceleiaşi probleme o soluţie ce verifică, în plus, şi condiţiile de nenegativitate (3.8). Definiţia 3: Se numeşte soluţie optimală (optimă) acea soluţie admisibilă (de regulă unică) pentru care funcţia - obiectiv F, dată de relaţia (3.7), îşi atinge maximul / minimul (care optimizează funcţia obiectiv, F). Definiţia 4: O problemă de programare liniară se numeşte incompatibilă dacă mulţimea soluţiilor admisibile (numită şi mulţimea programelor), A , este vidă. Dacă A ≠ Ø, problema se numeşte compatibilă. Definiţia 5: Dacă funcţia obiectiv a unei probleme compatibile este nemărginită pe A, se spune că problema are un optim infinit. Dacă problema are cel puţin o soluţie (reală finită), se spune că prezintă un optim finit. Definiţia 6: O soluţie, corespunzătoare formei standard a unei probleme de programare liniară, nu neapărat admisibilă, se numeşte soluţie de bază dacă mulţimea coloanelor din matricea A’, corespunzătoare componentelor xj nenule, 1 ≤ j ≤ n + m, este liniar independentă. Definiţia 7: Se numeşte soluţie nedegenerată o soluţie de bază care are exact m componente nenule. Se numeşte soluţie degenerată o soluţie de bază care are mai puţin de m componente nenule. Definiţia 8: Variabilele corespunzătoare componentelor nenule ale unei soluţii de bază se numesc variabile de bază, iar cele corespunzătoare componentelor nule se numesc variabile secundare (din afara bazei).
Observaţia A: Sistemul de restricţii (inecuaţii sau ecuaţii liniare) al problemei, adică – în cazul formei standard – sistemul (3.9) de m ecuaţii cu n + m necunoscute, poate avea o infinitate de soluţii, o singură soluţie sau nici una (în cazul în care sistemul restricţiilor este contradictoriu). Dacă problema a fost formulată corect, cel mai frecvent este cazul cu o infinitate de soluţii (lipsa
Conf. dr. ing. Andrei Dumitrescu
8
de soluţii indică faptul că s-au formulat prea multe restricţii, astfel că practic ele nu pot fi îndeplinite simultan în totalitate).
Observaţia B: Problema de programare liniară poate avea soluţii, dar nici una dintre ele să fie admisibilă, caz în care A = Ø. În situaţia în care A ≠ Ø, este posibil ca funcţia F să fie nemărginită pe A, adică să existe un şir de soluţii admisibile de-a lungul căruia funcţia obiectiv să tindă spre +/- ∞ (o valoare optimală infinită).
Observaţia C: O consecinţă a definiţiilor 6 şi 7 de mai sus este că, în condiţiile în care restricţiile (3.9) sunt liniar independente, fiecare dintre soluţiile de bază ale problemei este nedegenerată, deci prezintă m componente xj nenule şi n componente xj nule, 1 ≤ j ≤ n + m.
Teorema 1: Un sistem de ecuaţii / inecuaţii liniare, de tipul (3.9) determină o mulţime convexă care este fie vidă, fie poliedrică şi nemărginită (cu un număr finit de vârfuri însă), fie un poliedru convex. Această mulţime este mulţimea soluţiilor admisibile, A.
Teorema 2: Dacă mulţimea (poliedrul) convexă a soluţiilor admisibile nu este o mulţime vidă, fiecare vârf al poliedrului (mulţimii A) determină o soluţie de bază şi reciproc (o soluţie admisibilă este un vârf al poliedrului soluţiilor dacă şi numai dacă este o soluţie de bază).
Teorema 3: A) Dacă mulţimea soluţiilor admisibile, A, este nevidă şi mărginită, problema (programul liniar) are un optim finit.
B) Dacă mulţimea soluţiilor admisibile, A, este nevidă şi nemărginită, funcţia - obiectiv poate avea valoarea optimală infinită ( ∞± ) sau finită.
C) Dacă mulţimea soluţiilor admisibile, A, este vidă, programul liniar nu are soluţii (este incompatibil, deoarece sistemul restricţiilor este contradictoriu).
Teorema 4 (fundamentală): Dacă un program liniar are un optim finit, atunci funcţia obiectiv, F, îşi atinge optimul (maximul sau minimul) într-o soluţie de bază (vârf al poliedrului) sau eventual într-o combinaţie convexă de soluţii de bază (pe o „faţă” a poliedrului). Practic, soluţia optimă se află în unul dintre vârfurile poliedrului convex al soluţiilor admisibile, A.
Observaţia D: De cele mai multe ori, soluţia optimală este unică. În acest caz, conform teoremei fundamentale enunţate mai sus, soluţia optimală corespunde unei soluţii de bază. Dacă soluţia optimală nu este unică, ea poate corespunde unei combinaţii liniare de soluţii de bază
Principala consecinţă a teoremelor enunţate mai sus şi în special a celei fundamentale este că va fi deci suficient să căutăm soluţia optimă a problemei de programare liniară printre elementele mulţimii finite a soluţiilor de bază - vârfurile poliedrului soluţiilor admisibile (în număr de n
mnC + ), şi nu în mulţimea A, în general infinită. De aici rezultă cea mai simplă metodă de rezolvare (a descrierii totale sau a variabilelor de ecart), descrisă în subsecţiunea 3.2.2.
În cazul n = 2 (problemă cu două variabile), se poate utiliza şi metoda grafică de rezolvare, prezentată în aceeaşi subsecţiune 3.2.2, în principal cu scop didactic (pentru o mai bună înţelegere a celorlalte metode).
Aceste prime două metode de rezolvare nu pot fi aplicate cu succes în cazurile uzuale, datorită numărului mare de restricţii m şi de variabile n întâlnite în practică. De aceea, metodele uzuale de rezolvare a problemelor de programare liniară au ca scop simplificarea algoritmului metodei variabilelor de ecart, prin folosirea unor metode iterative cu reducerea numărului de
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
9
încercări pentru obţinerea soluţiilor optime. Cea mai răspândită dintre aceste metode este metoda simplex (descrisă în subsecţiunea 3.3.1), care este fundamentată teoretic pe forma explicită a unui program liniar (în raport cu o bază dată) şi pe o serie de teoreme mai complexe, pe care (din acest motiv) nu le vom mai prezenta.
Există multe alte metode de rezolvare a problemelor de programare liniară, unele cu caracter general, cum ar fi utilizarea programelor duale (vezi subsecţiunea 3.3.2) şi altele adaptate unor probleme de structură specială, cum ar fi procedeul pas cu pas sau metoda fluxului într-o reţea pentru problemele de transport (a se vedea secţiunea 4.1). Există, de asemenea, unele extinderi ale programării liniare, cum este programarea liniară parametrică sau cea în numere întregi. S-au dezvoltat, de asemenea, metode şi algoritmi pentru analiza sensibilităţii şi postoptimizare, care studiază stabilitatea soluţiei optime în cazul (frecvent întâlnit în practică) în care constantele problemei (aij, bi, cj) înregistrează unele variaţii.
3.2.2. Metoda grafică şi metoda variabilelor de ecart După cum s-a arătat mai sus, cea mai simplă metodă de rezolvare,
consecinţă directă a teoremelor prezentate, este cea a descrierii totale sau a variabilelor de ecart, ce presupune parcurgerea a două etape:
1. determinarea soluţiilor de bază ale sistemului de m ecuaţii ale formei standard (corespunzător celor m restricţii) cu n+m necunoscute (cele n variabile iniţiale şi cele m variabile de ecart);
2. calculul valorii funcţiei F pentru fiecare soluţie de bază admisibilă (având doar valori pozitive ale variabilelor) şi compararea acestor valori în vederea determinării soluţiei optimale.
Observaţie. Etapa 1 de mai sus presupune rezolvarea unui sistem format din m ecuaţii cu m + n variabile. Un astfel de sistem are un număr infinit de soluţii. Pentru a obţine o soluţie a sistemului, se aleg valori pentru n dintre variabile şi se obţin apoi celelalte (rezolvând un sistem de m ecuaţii cu m necunoscute). Un procedeu simplu de a alege valori iniţiale pentru câte n necunoscute constă în a le anula (a le lua egale cu zero). În acest fel, se obţin cel mult n
mnC + soluţii cu m variabile nenule, între care se află şi soluţiile de bază ale problemei.
În cazul n = 2 (problemă de programare liniară cu numai două variabile), se poate utiliza şi metoda grafică de rezolvare, care presupune reprezentarea grafică a restricţiilor (3.1) şi a condiţiilor de nenegativitate, în planul de coordonate x1 şi x2. Rezultatul unei astfel de reprezentări este un poligon convex, care poate fi, în anumite cazuri, nemărginit sau redus la un punct sau chiar la o mulţime vidă.
Definiţie: Un poligon închis se numeşte convex dacă, o dată cu două puncte, conţine şi segmentul care le uneşte (dacă punctele A şi B aparţin poligonului, atunci orice punct de pe segmentul AB aparţine, de asemenea, poligonului).
Observaţie. Definiţia de mai sus se poate extinde la un poliedru convex (în spaţiul n-dimensional) sau la o mulţime convexă în general. Poligonul convex obţinut prin aplicrea metodei grafice este, de atfel, o reprezentare grafică a mulţimii soluţiilor admisibile, A, care este o mulţime convexă.
Conf. dr. ing. Andrei Dumitrescu
10
În continuare, se reprezintă grafic şi funcţia F, ca o familie de drepte paralele, iar soluţia optimală va corespunde de regulă unui vârf al poligonului convex şi anume cel pentru care distanţa de la dreapta corespunzătoare a familiei F la origine este maximă. Este însă posibil ca, în cazul în care o latură a poligonului convex este paralelă cu familia de drepte corespunzătoare funcţiei F, să se obţină o infinitate de soluţii (o combinaţie convexă de soluţii de bază) corespunzătoare mulţimii punctelor segmentului de dreaptă ce defineşte acea latură a poligonului, definită de două soluţii de bază (vârfuri).
În cazul problemei cu n > 2 variabile (x1, ..., xn), planul x1 - x2 devine un spaţiu n – dimensional, iar poligonul devine un poliedru convex, obţinut din intersecţia hiperplanelor reprezentând restricţile. În acest caz însă, problema nu mai poate fi efectiv rezolvată prin aplicarea metodei grafice.
Aplicaţia 3.1: Un mic atelier produce două tipuri de piese de automobil. Atelierul cumpără piese turnate pe care le strunjeşte, le găureşte şi le şlefuieşte. Se cunosc următoarele date:
• Costul pieselor turnate: A – 2 €/buc.; B – 3 €/buc. • Preţurile de vânzare (de piaţă) ale produselor: A – 5 €/buc.; B – 6 €/buc. • Cheltuielile necesare pentru o oră de utilizare a celor trei maşini:
- pentru strung: 20 €/oră; - pentru maşina de găurit: 14 €/oră; - pentru maşina de şlefuit: 17,5 €/oră.
• Capacităţile de prelucrare ale celor trei maşini, indicate în tabelul 3.1.
Tabelul 3.1. Capacităţi [buc./oră] Piesa A Piesa B
a strungului 25 40
a maşinii de găurit 28 35
a maşinii de şlefuit 35 25
Să se determine valoarea producţiei (a celor două piese, A şi B) astfel încât profitul obţinut să fie maxim.
Definirea funcţiei-obiectiv: În acest scop, se calculează profilul adus de fiecare piesă, conform tabelului 3.2 (valorile sunt exprimate în euro/buc.).
Tabelul 3.2. Operaţia Piesa A Piesa B
Strunjire Găurire Şlefuire Achiziţie
20/25 = 0,8 14/28 = 0,5
17,5/35 = 0,5 2,0
20/40 = 0,5 14/35 = 0,4
17,5/25 = 0,7 3,0
Total cheltuieli Preţ vânzare
3,8 5,0
4,6 6,0
Profit/piesă 1,2 1,4
Dacă se produc, în medie, x piese de tip A şi y piese de tip B pe oră, profitul pe oră va fi (acesta reprezintă şi funcţia – obiectiv a problemei):
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
11
F = 1,2 x + 1,4 y = maxim .
Determinarea restricţiilor se face pe baza capacităţii de producţie orare:
D1 (strunjire) x/25 + y/40 ≤ 1 ⇔ 40 x + 25 y ≤ 1000 D2 (găurire) x/28 + y/35 ≤ 1 ⇔ 35 x + 28 y ≤ 980 D3 (şlefuire) x/35 + y/25 ≤ 1 ⇔ 25 x + 35 y ≤ 875
Se adaugă condiţiile de ne-negativitate: x ≥ 0 , y ≥ 0 .
Rezolvarea prin metoda grafică este ilustrată în figura 3.1. Dreptele Di, i=1,2,3 , corespund celor trei restricţii ale problemei. Dacă am reprezenta şi familia de drepte reprezentând funcţia F (pentru a nu încărca fig. 3.1, acestea nu au mai fost incluse pe grafic), se obţine ca soluţie optimală cea corespunzătoare punctului B, şi anume:
xopt = 17 buc./oră , yopt = 13 buc./oră .
Fig. 3.1. Rezolvarea grafică a Aplicaţiei 3.1 Rezolvarea cu metoda variabilelor de ecart: În formularea modelului de optimizare, se introduc variabilele de ecart
xn+i (n = 2, i = 1, ..., m ; m = 3, n + m = 5) obţinând, din sistemul de restricţii al problemei, următorul sistem de ecuaţii (la care am adăugat condiţiile de nenegativitate şi în care s-au folosit notaţiile: x1 = u; x2 = v; x3 = w):
0 , ,0 ,
8753525980283510002540
≥≥
⎪⎩
⎪⎨
⎧
=++=++=++
wvuyx
wyxvyxuyx
S-a obţinut astfel un sistem cu m = 3 ecuaţii şi m + n = 5 necunoscute. Numărul maxim de soluţii de bază obţinute este, în acest caz:
1021452
25 =
/⋅/⋅
==+ CC nmn .
Soluţiile de bază obţinute sunt prezentate în tabelul 3.3. Dintre cele 10 soluţii, 6 (menţionate ca imposibile în tabel) nu sunt admisibile, deoarece prezintă şi valori negative ale variabilelor de bază: soluţiile 2, 3, 6, 7, 8 şi 10. Celelalte 4 soluţii sunt soluţiile de bază admisibile (şi anume 1, 4, 5 şi 9), care
y O (0, 0) 40 A (0, 25) B (17, 13) → D1∩D3 30 C (25, 0) A 20 B 10
C O 10 20 30 40 x D1 D2 D3
Conf. dr. ing. Andrei Dumitrescu
12
corespund vârfurilor poligonului convex OABC obţinut anterior prin metoda grafică (a se vedea fig. 3.1).
Tabelul 3.3.
Soluţia x y u v w F Comentarii
1
2
3
4
5
0 0 1000 980 875
0 40 0 - 140 - 525
0 35 125 0 - 350
0 25 375 280 0
25 0 0 105 250
0
-
-
35
30
Sol. bază (pct. O)
Sol. impos.(v, w < 0)
Sol. impos.(w < 0)
Sol. bază (pct. A)
Sol. bază (pct. C)
6
7
8
9
10
28 0 - 120 0 175
35 0 - 400 - 245 0
100/7 120/7 0 0 - 125
16,94 12,90 0 25,9 0
56/3 35/3 - 115/3 0 0
-
-
-
38,39
-
Sol. impos.(u < 0)
Sol. impos.(u, v < 0)
Sol. impos.(w < 0)
Sol. optimă (pct. B)
Sol. impos.(u < 0)
Dintre soluţiile de bază admisibile, una singură este soluţia finală
(optimă), cea care face ca funcţia obiectiv F să-şi atingă valoarea sa maximă. Această soluţie este soluţia 9, corespunzătoare punctului B din figura 3.1, deci rezultă:
Aplicaţia 3.2 (problemă cu domeniul OABC nemărginit): Să se rezolve următoarea problemă de programare liniară.
.max43
0,
)( 22)( 22)( 1243
21
21
321
221
121
=+=
≥
⎪⎩
⎪⎨
⎧
≤−≤+−≤+−
xxF
xx
dxxdxxdxx
Rezolvarea cu metoda grafică, ilustrată în figura 3.2, arată că domeniul soluţiilor posibile este nemărginit, deci valoarea maximă a funcţiei – obiectiv F se atinge la +∞. În acest caz, nu există practic o soluţie optimă. Se poate considera o soluţie variabilă, ca în figură, definită de dreapta d1 şi depinzând de parametrul a, care, pentru a → +∞, conduce la valoarea maximă a lui F (+∞).
Sistemul obţinut prin introducerea variabilelor de ecart este următorul:
...,5 1,i ,0
22221243
521
421
321
=≥
⎪⎩
⎪⎨
⎧
=+−=++−=++−
ixxxxxxxxxx
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
13
Fig. 3.2. Rezolvarea grafică a Aplicaţiei 3.2
Aplicaţia 3.3: Se consideră un banc de lucru al unui atelier de reparaţii ce execută două categorii de reparaţii. Resursele disponibile luate în considerare sunt materialele şi forţa de muncă. Se notează cu x1 şi x2 volumul (în bucăţi) al celor două categorii de reparaţii. Resursele necesare sunt indicate în tabelul 3.4.
Tabelul 3.4.
Categorii de reparaţii x1 x2 Total disponibil
resurse Resurse materiale* [kg/buc.] 3 5 15 kg Forţa de muncă** [ore/buc.] 6 2 24 ore
Preţ unitar de reparaţie [€/buc] 200 300 - * consum unitar de materiale; ** consum unitar de manoperă.
Să se determine cantitatea optimă de produse reparate, x1 şi x2, astfel încât preţul (valoarea) producţiei realizate să fie maximă.
Formularea modelului de optimizare (al problemei de programare liniară): 1) funcţia – obiectiv (preţul): F = 200x1 + 300x2 = max.
Rezolvarea prin metoda grafică este ilustrată în figura 3.3. Observaţie: Coordonatele vârfurilor poligonului convex OABC
(punctele O, A, B, C), împreună cu laturile poligonului şi întregul domeniu OABC, reprezintă soluţiile posibile ale sistemului de restricţii.
Dacă reprezentăm grafic şi familia de drepte ⎭⎬⎫
⎩⎨⎧ =+ dxxF
cc 2121
300200 ,
corespunzătoare funcţiei – obiectiv F, observăm că valoarea maximă a funcţiei F se atinge în acel vârf al poligonului pentru care distanţa de la dreapta corespunzătoare a familiei F la origine este maximă. Astfel, rezultă că soluţia optimală a problemei este cea corespunzătoare vârfului B (în figura de mai sus
-4
x2 d2 d1 A (0, 2) soluţie variabilă B (4/5, 18/5)→d1∩d2
3 B ax54
54
1 += C (2, 0)
2 A ax53
518
2 +=
d3 C
-1 O 2 x1
-1
Conf. dr. ing. Andrei Dumitrescu
14
sunt reprezentate două drepte ale familiei F, una pentru d = 100 şi cealaltă pentru d = 975, care trece prin B). Soluţia optimală este deci:
x1opt = 3,75 buc. , x2
opt = 0,75 buc. , Fmax = 975 €.
Fig. 3.3. Rezolvarea grafică a Aplicaţiei 3.3
Rezolvarea cu metoda variabilelor de ecart: Se introduc variabilele de ecart xn+i (n = 2, i = 1, 2) obţinând, din sistemul de restricţii, următorul sistem de ecuaţii (la care am adăugat condiţiile de nenegativitate):
0,0,0,0 24261553
4321421
321 ≥≥≥≥⎩⎨⎧
=++=++
xxxxxxxxxx
Observaţie: Sistemul obţinut este format din m = 2 ecuaţii cu m + n = 4 variabile. Un astfel de sistem are un număr infinit de soluţii. Pentru a obţine o soluţie a sistemului, se aleg valori pentru n = 2 dintre variabile şi se obţin apoi celelalte (rezolvând un sistem de m = 2 ecuaţii cu m = 2 necunoscute). Un procedeu simplu de a alege valori iniţiale pentru câte două necunoscute constă în a le anula (a le lua egale cu zero). În acest fel, se obţin cel mult 62
4 ==+ CC mmn
soluţii cu m = 2 variabile nenule, între care se află şi soluţiile de bază ale problemei.
Cele 6 soluţii obţinute sunt prezentate în tabelul 3.5, împreună cu valorile corespunzătoare ale funcţiei F şi cu precizarea tipului de soluţie (pentru soluţiile de bază, s-a indicat şi vârful corespunzător al poligonului OABC).
Observăm că cele patru soluţii posibile obţinute prin această metodă de rezolvare (1, 2, 5 şi 6) au proprietatea de a coincide cu vârfurile poligonului convex OABC obţinut la rezolvarea prin metoda grafică. Aceste soluţii reprezintă deci soluţiile de bază ale problemei. Dintre soluţiile de bază, una singură este soluţia finală (OPTIMALĂ), cea care face ca funcţia – obiectiv F să atingă valoarea maximă. Această soluţie este soluţia 6 (corespunzătoare punctului B): x1
opt = 3,75 buc. ; x2opt = 0,75 buc.
Valoarea maximă a funcţiei obiectiv, corespunzătoare acestei soluţii, este: Fmax = 200 x1
opt + 300 x2opt + 0⋅x3 + 0⋅x4 = 975 €.
x2 x1 = 0 A (0; 3) B (3,75; 0,75) C (4; 0)
A F = max. [d=975]
3 2 - F [d=100] B x2 = 0 O C
3 4 5 x1
3x1 + 5x2 = 15
6x1 + 2x2 = 24
(la x2 = 12)
A (0; 3)
B (3,75; 0,75)
C (4; 0)
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
1. Care este diferenţa dintre o soluţie admisibilă şi o soluţie de bază ale unei probleme de programare liniară?
2. Enunţaţi principalele teoreme ale programării liniare şi comentaţi rolul fiecăreia dintre ele.
3. Care este teorema fundamentală a programării liniare şi care este scopul pentru care a fost enunţată?
4. Ce se înţelege prin mulţime convexă? Indicaţi un exemplu concret pentru cazul unui spaţiu tridimensional (n = 3).
5. Care este diferenţa dintre variabilele de bază şi cele din afara bazei? În ce scop credeţi că au fost introduse aceste noţiuni?
6. În ce situaţii poate fi rezolvată o problemă de programare liniară cu metoda grafică? Pot fi întâlnite astfel de situaţii în practică?
7. Care consideraţi că este principalul dezavantaj al metodei variabilelor de ecart, care îi limitează aplicabilitatea?
8. Comparaţi cele două metode de rezolvare propuse pentru cazul n = 2. Pe care dintre acestea o preferaţi?
Problemă propusă (secţiunea 3.2)
Să se rezolve, utilizând succesiv metoda grafică şi metoda variabilelor de ecart (comparându-se apoi rezultatele obţinute), problema de programare liniară caracterizată de următorul model matematic:
3010648412
21
21
⎭⎬⎫
⎩⎨⎧
≤+≤+
xxxx
x1 ≥ 0 , x2 ≥ 0 . F = 200x1 + 100x2 = max.
Conf. dr. ing. Andrei Dumitrescu
16
3.3. Metoda simplex pentru rezolvarea problemelor
de programare liniară. Programe duale
În cele ce urmează, va fi prezentată cea mai răspândită metodă de rezolvare a problemelor de programare liniară, şi anume metoda simplex, urmată de prezentarea problematicii programelor duale, pe baza cărora s-au dezvoltat alte metode.
3.3.1. Metoda simplex Metoda SIMPLEX, al cărei algoritm a fost elaborat iniţial de către G. B.
Dantzig, în anul 1947, s-a impus ca fiind cea mai utilizată metodă de rezolvare a problemelor de programare liniară. Această metodă iterativă permite o explorare sistematică a mulţimii soluţiilor de bază ale problemei, enunţată în forma standard, cu „îmbunătăţirea” soluţiei (prin „apropierea” de soluţia optimă) de la o iteraţie la alta. Metoda furnizează, de asemenea, criterii pentru stabilirea problemelor cu optim infinit sau pentru care mulţimea soluţiilor admisibile este o mulţime vidă.
Aplicarea metodei simplex unei probleme de programare liniară presupune parcurgerea, în esenţă, a următoarelor etape de rezolvare (după ce, iniţial, problema a fost enunţată în forma standard):
I. determinarea unei soluţii de bază iniţiale (baza iniţială); II. trecerea la o altă soluţie de bază (alt vârf al poliedrului convex
definit de mulţimea soluţiilor admisibile), plecând de la baza iniţială / precedentă (vârful iniţial / precedent), astfel încât să se obţină o valoare mai mare / mai mică a funcţiei obiectiv (să se „îmbunătăţească” valoarea funcţiei obiectiv de maximizat / minimizat);
III. se consideră ca soluţie optimală o soluţie de bază obţinută după etapa II, atunci când nu mai este posibil să se mărească / micşoreze valoarea funcţiei obiectiv.
Rezolvarea etapei I presupune practic determinarea unei baze (numită baza iniţială) b în matricea A’ – din sistemul (3.13). Cea mai simplă variantă de rezolvare a acestei etape este să se adopte baza iniţială definită astfel:
xj = 0 (pentru 1 ≤ j ≤ n) şi xn+i = bi (pentru 1 ≤ i ≤ m) . Această soluţie nu este însă aplicabilă pentru orice program liniar, deşi
este valabilă pentru cazul în care restricţiile problemei (3.1) sunt liniar independente (ceea ce este greu de verificat în practică). De aceea, s-au elaborat o serie de metode de găsire a unei baze iniţiale, dintre care amintim metoda celor două faze (ce utilizează aşa-numita bază artificială, etapa II a problemei de programare liniară rezolvându-se în două faze).
Etapa II este iterativă şi porneşte de la forma explicită a programului liniar în raport cu baza iniţială. Aceasta, de fapt, exprimă funcţia obiectiv a problemei şi variabilele de bază ale soluţiei iniţiale (cele nenule xn+i definite în etapa I) în funcţie de celelalte variabile, cu valori nule (variabilele din afara bazei, numite şi variabile secundare). Forma explicită algebrică a unui program liniar poate fi scrisă astfel:
bix + ∑
∈
⋅Jj
jij xa = ib , i ∈ I , (3.15)
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
17
F = F – ∑∈
⋅Jj
jj xc , (3.16)
în care bix sunt variabilele de bază, I – mulţimea indicilor variabilelor de bază,
J – mulţimea indicilor variabilelor secundare, ib – valorile variabilelor de bază (egale cu termenii liberi ai formei explicite), F – valoarea funcţiei obiectiv,
ija – coeficienţii sistemului de restricţii ai formei explicite, jc – coeficienţii funcţiei obiectiv din forma explicită.
În continuare, etapa II urmăreşte stabilirea unei noi soluţii de bază, obţinută prin înlocuirea uneia dintre variabilele de bază (numită variabila ce „iese” din bază) ale soluţiei iniţiale cu una din variabilele secundare (variabila ce „intră” în bază). Această schimbare a soluţiei de bază urmăreşte ca valoarea funcţiei obiectiv să crească/scadă. În acest scop, etapa implică realizarea următorilor trei paşi:
10. se alege variabila secundară care să „intre” în bază (să devină variabilă de bază la iteraţia următoare), prin aplicarea criteriilor de intrare în bază;
20. se alege apoi variabila de bază care să „iasă” din bază (să devină variabilă secundară la iteraţia următoare), prin aplicarea criteriilor de ieşire din bază;
30. se exprimă variabilele de bază ale noii soluţii de bază şi funcţia obiectiv în funcţie de noile variabile secundare (din afara bazei), adică se determină forma explicită a problemei asociată noii baze.
Criterii de intrare în bază (de a alege noua variabilă de bază la etapa II): • pentru problemele de maxim: în noua bază intră acea variabilă
secundară pentru care coeficientul corespunzător din expresia funcţiei obiectiv are cea mai mare valoare pozitivă;
• pentru problemele de minim: în noua bază intră acea variabilă secundară pentru care coeficientul corespunzător din expresia funcţiei obiectiv negativ şi cel mai mare în valoare absolută.
Algoritmul simplex este descris, matematic, de următorii paşi: 10. se determină o bază iniţială în matricea A’ şi se calculează
coeficienţii formei explicite a programului liniar în raport cu această bază iniţială, ija , ib , jc , F din relaţiile (3.15) şi (3.16);
20. se aplică testul de optimalitate, care stabileşte dacă s-a obţinut soluţia optimă: dacă jc ≥ 0, oricare ar fi j ∈ J, atunci soluţia de bază curentă este cea optimă; în caz contrar (există cel puţin un j ∈ J, pentru care jc < 0), se trece la pasul următor;
30. se aplică criteriul de intrare în bază: se determină k ∈ J, astfel încât: ( )jJjk cc
∈= min ; variabila secundară xk este cea care „intră” în bază;
40. se aplică testul pentru optim infinit ce stabileşte dacă problema are un optim infinit: dacă ika ≤ 0, oricare ar fi i ∈ I, atunci problema are un optim infinit; în caz contrar (există cel puţin un i ∈ I, pentru care
ika > 0), se trece la pasul următor; 50. se aplică criteriul de ieşire din bază: se determină r ∈ I (variabila xr
fiind cea care „iese” din bază), prin aplicarea relaţiei de mai jos:
Conf. dr. ing. Andrei Dumitrescu
18
⎭⎬⎫
⎩⎨⎧
=>∈
ik
i
aIirk
r
ab
ab
ik 0;min ; (3.17)
60. se realizează schimbarea bazei, adică se construieşte forma explicită a programului liniar în raport cu noua bază şi se revine la pasul 20.
Observaţie: Testul de optimalitate (pasul 20) formulat mai sus se referă la o problemă de maximizare. Pentru o problemă de minimizare, s-a obţinut soluţia optimă dacă jc ≤ 0, oricare ar fi j ∈ J. În plus, criteriul de intrare în bază (pasul 30) se modifică pentru o problemă de minimizare astfel: ( )jJjk cc
∈= max .
Pentru a simplifica aplicarea metodei şi a obţine mai rapid soluţia optimală, se construieşte un tabel, numit tabel simplex, care cuprinde următoarele coloane:
• prima coloană, notată CO, conţine coeficienţii cj ai variabilelor de bază de la iteraţia curentă în funcţia obiectiv iniţială a problemei;
• a doua coloană, notată VB, conţine variabilele de bază, bix , de la
iteraţia respectivă (cea curentă); • a treia coloană, notată VVB, conţine valorile variabilelor de bază, ib ,
în condiţiile în care cele secundare (din afara bazei) au valoarea zero; • coloanele următoare (x1, x2, ..., xn+m) conţin coeficienţii ija ai
sistemului de restricţii al formei explicite a programului liniar corespunzător soluţiei de bază a iteraţiei curente.
Sub liniile corespunzătoare celor m variabile de bază, se introduce o linie ce conţine valoarea funcţiei obiectiv la iteraţia respectivă, F , şi coeficienţii formei explicite a problemei corespunzătoare iteraţiei curente, jc .
Prezentăm câteva precizări privind modul de rezolvare a problemei, dacă se utilizează exclusiv tabelul simplex:
• la prima iteraţie (corespunzătoare bazei iniţiale – dacă se poate considera ca soluţie de bază iniţială cea caracterizată prin xj = 0 şi xn+i = bi), în coloana VB se trec variabilele de ecart, în coloana VVB se scriu valorile acestora (corespunzătoare termenilor liberi din sistemul de restricţii al problemei, bi), iar în coloanele xi se trec coeficienţii sistemului de restricţii scris în forma standard (cu variabile de ecart); în linia corespunzătoare funcţiei obiectiv, se scriu coeficienţii jc = –cj ;
• se alege noua variabilă care să „intre” în bază ca fiind (în cazul unei probleme de maximizare) cea pentru care coeficientul negativ al liniei funcţiei obiectiv este mimim (adică maxim în valoare absolută); dacă toţi coeficienţii liniei funcţiei obiectiv sunt pozitivi sau nuli, soluţia obţinută la iteraţia respectivă este soluţia optimă a problemei;
• se alege variabila care iese din bază pe baza coeficienţilor rezultaţi din împărţirea valorilor ib din coloana VVB la valorile ika din coloana variabilei ce „intră” în bază; variabila ce „iese” corespunde valorii pozitive minime a coeficientului astfel calculat; dacă toţi coeficienţii astfel calculaţi sunt negativi, problema are optim infinit;
• se evidenţiază (prin încercuire sau eventual încadrându-l într-un dreptunghi) pivotul transformării bazei pentru iteraţia următoare; acesta este
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
19
coeficientul rka aflat la intersecţia coloanei variabilei ce „intră” în bază cu linia variabilei ce „iese” din bază;
• se scrie întâi linia noii variabile de bază (cea care „intră” în bază), xk, care cuprinde coeficienţii calculaţi prin împărţirea coeficienţilor liniei variabilei ce „iese” din bază, xr, la pivotul transformării;
• se calculează ceilalţi coeficienţi utilizând pivotul şi coeficienţii de pe coloana variabilei ce „intră” în bază prin aplicarea regulii dreptunghiului: dacă ne imaginăm dreptunghiul a cărui diagonală este determinată de pivot şi de coeficientul ce trebuie „transformat”, atunci noua valoare a acestuia se obţine împărţind la pivot diferenţa dintre produsul coeficienţilor de pe diagonala considerată şi produsul coeficienţilor situaţi pe cealaltă diagonală a dreptunghiului. Aceeaşi regulă se va aplica şi liniei funcţiei obiectiv, pentru determinarea noilor valori de pe aceasta.
Valorile din coloana VVB de la iteraţia corespunzătoare soluţiei optimale sunt valorile optime ale necunoscutelor problemei.
În încheiere, precizăm că există şi un algoritm simplex dual, care rezolvă programul liniar dual al problemei date. O altă problemă deosebită este cea a convergenţei algoritmului simplex. De asemenea, în cadrul algoritmului simplex, poate apare fenomenul de ciclare (se ajunge la o bază deja procesată la o iteraţie anterioară), dar există tehnici pentru evitarea acestui fenomen
Aplicaţia 3.4: Să se rezolve următoarea problemă de programare liniară:
⎩⎨⎧=≥
⎪⎩
⎪⎨
⎧
≤+−≤++≤++
3,2,10
5313227
321
321
321
ix
xxxxxx
xxxi
maxim532 321 =++= xxxf
Forma standard a problemei se obţine din cea canonică din enunţul de mai sus, prin introducerea variabilelor de ecart (funcţia - obiectiv f este aceeaşi):
⎪⎪⎩
⎪⎪⎨
⎧
≤≤≥=++−=+++=+++
61 ,0 5313227
6321
5321
4321
ixxxxxxxxx
xxxx
i
Rezolvare: Prezentăm iniţial, cu scop didactic, rezolvarea problemei fără a utiliza tabelul simplex, cu exprimarea clară a formei explicite a problemei pentru fiecare bază. În mod uzual însă, acest tabel este întotdeauna utilizat.
Etapa 10: Baza iniţială este: x4 = 7, x5 = 13, x6 = 5, pentru care f = 0. Variabilele din afara bazei sunt necunoscutele iniţiale ale problemei: x1, x2, x3.
Etapa 20, iteraţia 1: Variabilele bazei iniţiale şi f se exprimă în funcţie de variabilele din afara bazei, pornind de la forma standard a problemei, obţinându-se astfel forma explicită în raport cu baza iniţială:
(*)
⎪⎪⎩
⎪⎪⎨
⎧
====
⇒
⎪⎪⎭
⎪⎪⎬
⎫
−−−−==+−+=+++
=+++
===
05
137
)532(053
13227
6
5
4
pentru
000
321
3216
3215
3214
3
2
1
fxxx
xxxfxxxx
xxxxxxxx
xxx
Conf. dr. ing. Andrei Dumitrescu
20
Se alege apoi noua variabilă care să intre în bază, astfel încât f să crească cel mai rapid. Această variabilă este x3, ce are coeficientul pozitiv cel mai mare în expresia funcţiei obiectiv f.
Se alege variabila din baza iniţială care să „iasă” din bază. Această variabilă este cea pentru care raportul dintre termenul liber şi coeficienţii noii variabile de bază, x3, este pozitiv şi minim. Aceşti coeficienţi sunt:
• pentru x4 → 7/1 = 7; • pentru x5 → 13/2 = 6,5; • pentru x6 → 5/1 = 5.
Rezultă deci că x6 este variabila care „iese” din „bază”. Noua bază este x3, x4, x5, iar noile variabile din afara bazei sunt x1, x2, x6.
Etapa 20, iteraţia 2: Se exprimă noua bază şi f în funcţie de noile variabile din afara bazei. Din a treia ecuaţie (*), se exprimă x3 şi se înlocuieşte apoi în celelalte ecuaţii. Rezultă astfel următorul sistem, ce reprezintă forma explicită în raport cu noua bază:
⎪⎪⎩
⎪⎪⎨
⎧
>====
⇒
⎪⎪⎩
⎪⎪⎨
⎧
−+−==−+−=−+−=+−+
∗∗
===
0)( 25325
5813253245222
53
)(5
4
3
000
621
6215
6214
6213
3
2
1
fxxx
xxxfxxxxxxxx
xxxxpentru
xxx
Noua variabilă care intră în bază este acum x2, unica ce are un coeficient pozitiv în expresia lui f. Valorile coeficienţii variabilelor de bază ce trebuie determinaţi pentru a stabili variabila ce „iese” din bază sunt:
• pentru x3 → 5/-1 = - 5 (<0); • pentru x4 → 2/2 = 1; • pentru x5 → 3/4 = 0,75.
Rezultă deci că variabila care „iese” din bază este x5. Etapa 20, iteraţia 3: Noua bază, care este acum x2, x3, x4, se exprima
(alături de f) în funcţie de noile variabile din afara bazei, x1, x5, x6, obţinând forma explicită în raport cu baza de la această iteraţie:
( )
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
>=
==
==
==
⇒
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
−−−=
=−+
=+++
=−+−
∗∗∗
===
25)( 31
5,021
75,5423
75,043
233121
21
21
423
21
41
47
43
21
41
45
4
3
2
000
651
514
6513
6512
6
5
1
f
x
x
x
xxxf
xxx
xxxx
xxxx
pentru
xxx
Etapa 30: Observăm că toţi coeficienţii funcţiei obiectiv f, obţinută după iteraţia 3 din etapa precedentă, sunt acum negativi, deci nu mai este posibil, schimbând baza, să mărim valoarea lui f. Rezultă că soluţia obţinută mai sus (după iteraţia 3) este soluţia OPTIMALĂ:
x1opt = 0 ; x2
opt = 0,75 ; x3opt = 3,75 .
Valoarea maximă a funcţiei obiectiv rezultă deci: fmax = 31.
Tabelul simplex corespunzător aplicaţiei studiate, care conţine toate cele trei iteraţii ale rezolvării, este tabelul 3.6, prezentat pe pagina următoare.
După cum se poate observa, coloanele (x1, ... , x6) din tabelul 3.6 conţin coeficienţii sistemului corespunzător iteraţiei respective – (*) pentru iteraţia 1,
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
21
(**) pentru iteraţia 2 şi (***) pentru iteraţia 3. Linia de sub cele trei variabile de bază conţine valoarea funcţiei obiectiv la iteraţia respectivă şi coeficienţii cu semn schimbat ai lui f din forma explicită corespunzătoare iteraţiei.
Tabelul 3.6. Iteraţia CO VB VVB x1 x2 x3 x4 x5 x6
0
0
0
x4
x5
x6
7
13
5
1 1 1 1 0 0
1 2 2 0 1 0
3 -1 1 0 0 1
1
(*)
0 -2 -3 -5 0 0 0
5
0
0
x3
x4
x5
5
2
3
3 -1 1 0 0 1
-2 2 0 1 0 -1
-5 4 0 0 1 -2
2
(**)
25 13 -8 0 0 0 5
3
5
0
x2
x3
x4
3/4
23/4
1/2
-5/4 1 0 0 1/4 -1/2
7/4 0 1 0 1/4 1/2
1/2 0 0 1 -1/2 0
3
(***)
31 3 0 0 0 2 1
Prezentăm, în încheiere, un exemplu de calcul al coeficienţilor utilizând regula dreptunghiului (pentru trecerea de la iteraţia 1 la iteraţia 2):
621
5
4
VVB
51
1(-5)-10 81
(-1)(-5)-13- 131
3(-5)-12- 251
5(-5)-10 :
21
12-10 41
(-1)2-12 51
32-11 31
52-113 :
11
11-10 21
(-1)1-11 21
31-11 21
51-17 :
xxx
f
x
x
=⋅⋅
−=⋅⋅
=⋅⋅
=⋅⋅
−=⋅⋅
=⋅⋅
−=⋅⋅
=⋅⋅
−=⋅⋅
=⋅⋅
−=⋅⋅
=⋅⋅
Aplicaţia 3.5: Să se rezolve următoarea problemă de programare liniară:
10834
1242723
321
21
321
⎪⎩
⎪⎨
⎧
≤++−≤+−≤+−
xxxxx
xxx
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 maxim23 321 =−+−= xxxf
Conf. dr. ing. Andrei Dumitrescu
22
Forma standard a problemei, obţinută din cea canonică de mai sus, prin introducerea variabilelor de ecart, este următoarea (funcţia - obiectiv f fiind aceeaşi, nu a mai fost scrisă din nou):
⎪⎪⎩
⎪⎪⎨
⎧
≤≤≥=+++−
=++−=++−
61 ,0 10834
1242723
6321
521
4321
ixxxxx
xxxxxxx
i
Rezolvare: Baza iniţială este: x4 = 7, x5 = 12, x6 = 10, pentru care f = 0. Variabilele din afara bazei sunt necunoscutele iniţiale ale problemei: x1, x2, x3.
Se trece la întocmirea tabelului simplex (tabelul 3.7 de mai jos) începând cu prima iteraţie, prin aplicarea regulilor enunţate mai sus.
La iteraţia 1, variabila care „intră” în bază este x2, singura care prezintă coeficient negativ în linia funcţiei-obiectiv. Variabila ce „iese” din baza iniţială este x5, deoarece prin împărţirea coloanei VVB la coloana variabilei x2, se obţin valorile: pentru x4 → -7 (valoare negativă); pentru x5 → 3 (cea mai mică valoare pozitivă); pentru x6 → 3,33. Pivotul transformării este evidenţiat în tabel, iar coeficienţii pentru iteraţia următoare s-au calculat conform regulilor explicate mai sus.
Tabelul 3.7.
Iteraţia Coef. fcţ. ob.
VB VVB x1 x2 x3 x4 x5 x6
0
0
0
x4
x5
x6
7
12
10
3 -1 2 1 0 0
-2 4 0 0 1 0
-4 3 8 0 0 1 1
0 1 -3 2 0 0 0
3
0
0
x2
x4
x6
3
10
1
-1/2 1 0 0 1/4 0
5/2 0 2 1 1/4 0
-5/2 0 8 0 -3/4 1 2
9 -1/2 0 2 0 3/4 0
-1
3
0
x1
x2
x6
4
5
11
1 0 4/5 2/5 1/10 0
0 1 2/5 1/5 3/10 0
0 0 10 1 -1/2 1 3
11 0 0 12/5 1/5 4/5 0
La iteraţia 2, variabila care „intră” în bază este x1, singura care prezintă
coeficient negativ în linia funcţiei-obiectiv. Variabila ce „iese” din baza iniţială este x4, deoarece prin împărţirea coloanei VVB la coloana variabilei x1, se obţine o valoare pozitivă doar pentru variabila x4.
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
23
La iteraţia 3, se constată că s-a obţinut soluţia optimă, deoarece toţi coeficienţii din linia funcţiei obiectiv f sunt acum pozitivi sau nuli. Ca urmare, soluţia optimă a problemei este: x1
3.3.1. Programe duale. Reguli pentru construirea programului dual
În principiu, oricărei probleme de programare liniară i se poate asocia o alta, numită duala sa, construită în funcţie de structura problemei iniţiale, numită problemă primală. Întotdeauna sensul optimizării în cele două probleme este diferit: dacă una este o problemă de maximizare, cealaltă este de minimizare. Teoria dualităţii studiază relaţiile dintre programul liniar primal şi cel dual.
În continuare, vom considera doar programe liniare în forma canonică, având condiţii de nenegativitate. Astfel, programele liniare de mai jos sunt programe duale:
⎪⎪
⎩
⎪⎪
⎨
⎧
≤≤≤
≤≤≥
==
⎪⎪⎪
⎩
⎪⎪⎪
⎨
⎧
≤≤≥
≤≤≥
==
∑
∑
∑
∑
=
=
=
=
m
ijjij
i
m
iii
n
jijij
j
n
jjj
njcya
miy
ybG
(D)
mibxa
njx
xcF
P
1
1
1
1
1 ,
1 ,0
immax
1 ,
1 ,0
immin
)( (3.18)
În relaţiile (3.18), programul primal este un program de minimizare, (P), şi are funcţia obiectiv F, iar programul dual al său este unul de maximizare, (D), ce prezintă funcţia obiectiv G.
Prezentăm, în continuare, principalele reguli pentru construirea programului dual, reguli ilustrate şi de relaţiile de mai sus:
10. Dacă programul primal (P) este o problemă de maximizare (minimizare), programul dual (D) va fi o problemă de minimizare (maximizare).
20. Fiecărei restricţii din (P) îi corespunde în (D) o variabilă. Ca urmare, numărul variabilelor duale yi este egal cu numărul restricţiilor programului primal m (în afara condiţiilor de ne-negativitate); fiecare variabilă duală yi poate fi deci pusă în corespondenţă cu restricţia primală i.
30. Fiecărei variabile din (P) îi corespunde o restricţie în (D). Ca urmare, numărul n al restricţiilor din programul dual este egal cu numărul variabilelor primale xj; fiecare variabilă primală xj poate fi deci pusă în corespondenţă cu restricţia duală j.
40. Termenii liberi bi din (P) devin coeficienţi ai funcţiei obiectiv în (D), iar coeficienţii funcţiei obiectiv cj din (P) devin termeni liberi în (D). Matricea coeficienţilor sistemului de restricţii din (D) este transpusa matricei coeficienţilor sistemului de restricţii din (P).
50. Dualul programului dual este programul primal. Utilizarea programelor duale, construite conform regulilor de mai sus, la
rezolvarea problemelor de programare liniară se bazează pe următoarea: Teoremă fundamentală: Se consideră un program primal (P) şi dualul
său (D). Atunci:
Conf. dr. ing. Andrei Dumitrescu
24
A) Dacă (P) are o soluţie optimă finită, atunci (D) are o soluţie optimă finită, iar minF = maxG (valorile optime ale funcţiilor obiectiv ale celor două programe sunt egale).
B) Dacă (P) − respectiv (D) − are soluţie optimă infinită, atunci (D) − respectiv (P) − nu are soluţie.
C) Dacă (P) − respectiv (D) − nu are soluţie, (D) − respectiv (P) − fie nu are soluţie, fie are soluţie optimă infinită.
Consecinţă (pentru enunţul A): Dacă )( jxx = şi )( iyy = sunt un cuplu de soluţii de bază, atunci există relaţia:
( ) ( )yGybxcxFm
iii
n
jjj =≥= ∑∑
== 11 . (3.19)
Dacă x şi y sunt soluţii optime, simbolul “≥” din relaţia de mai sus se înlocuieşte cu simbolul “=”.
Concluzie: Oricărei probleme de programare liniară i se poate ataşa un program dual. Rezolvând problema, se determină implicit şi soluţia programului dual. De multe ori, rezolvarea problemei duale este mai simplă sau mai rapidă.
Exemplu: Următoarele două programe sunt duale:
32121
321
32
321
21
21
211
32min 21max
0,,1
21y
1
30, 2
yyygxxf
yyyyyyy
xxxx
xxx
++=+=
⎪⎩
⎪⎨
⎧
≥≥+≥−+
←→
⎪⎩
⎪⎨
⎧
≤+−≤+
≥≤
Teste de autoevaluare (secţiunea 3.3)
1. Comparaţi cele trei metode de rezolvare a problemelor de programare liniară prezentate. Care credeţi că este cea mai eficientă?
2. Cum se defineşte forma explicită a unei probleme de programare liniară şi cu ce scop a fost aceasta definită?
3. Care sunt etapele de rezolvare a unei probleme de programare liniară cu metoda simplex?
4. Care este criteriul de intrare în bază la rezolvarea unei probleme de programare liniară cu metoda simplex? De ce este necesară utilizarea unui astfel de criteriu?
5. Care este criteriul de ieşire în bază la rezolvarea unei probleme de programare liniară cu metoda simplex? Care este rolul acestui criteriu?
6. Care credeţi că sunt avantajele utilizării tabelului simplex pentru rezolvarea unei probleme de programare liniară?
7. Ce sunt programele duale şi în ce scop credeţi că au fost definite? 8. Enunţaţi principalele reguli pentru construirea unui program dual.
Bazele Ingineriei Sistemelor de Producţie 3. Programarea Liniară
25
Probleme propuse (secţiunea 3.3)
1. Să se rezolve, utilizând metoda simplex, problema de programare liniară propusă la finele secţiunii 3.2. Să se compare rezultatele şi durata necesară pentru obţinerea soluţiilor cu cele din cazul aplicării metodelor prezentate în secţiunea precedentă.
2. Să se rezolve, utilizând metoda simplex, următoarea problemă de programare liniară:
622
42532
321
321
321
⎪⎩
⎪⎨
⎧
≤++≤++≤++
xxxxxxxxx
x1 ≥ 0, x2 ≥ 0, x3 ≥ 0 maxim20105 321 =++= xxxf
Bibliografie
1. Baciu, A., Pascu, A., Puşcaş, E., Aplicaţii ale cercetării operaţionale, Editura Militară, Bucureşti, 1988.
2. Bărbatu, Gh., Ionescu, V., Cercetarea operaţională în întreprinderile industriale, Editura Tehnică, Bucureşti, 1981.
3. Bebea, N., Metode pentru rezolvarea problemelor de optimizare, Editura Didactică şi Pedagogică, Bucureşti, 1976.
4. Dumitrescu, A., Bazele ingineriei sistemelor, Editura Universităţii din Ploieşti, 2005.
5. Dumitrescu, I., ş.a., Aplicaţii inginereşti ale calculatoarelor, Vol. 2 – Optimizări, Editura Didactică şi Pedagogică, Bucureşti, 1976.
6. Kaufmann, A., Metode şi modele ale cercetării operaţionale, Editura Ştiinţifică, Bucureşti, 1967.
8. Oprişan, Gh., Simion, E., Elemente de cercetări operaţionale şi criptologie, Editura Politehnica Press, Bucureşti, 2002.
9. Rendi, Dorina-Marieta, Metode ale cercetării operaţionale: programare liniară, teoria jocurilor, teoria grafurilor, Editura Orizonturi Universitare, Timişoara, 2002.
10. Vrânceanu, Gh., Mititelu, Şt., Probleme de cercetare operaţională, Editura Tehnică, Bucureşti, 1978.
