DUALITATEA IN PROBLEMELE DE PROGRAMARE LINIARA

DUALITATEA IN PROBLEMELE DE PROGRAMARE LINIARA

1. Dualitate. Problemele de programare liniara primala si duala

In cadrul acestei sectiuni vom trata modalitatea de a asocia o problema de minim unei probleme de programare liniara exprimata in forma standard. In general, o problema in forma standard este de tipul planificarea productiei, in care un numar redus de resurse trebuie alocate astfel incat profitul obtinut sa fie maxim. Problema asociata este cea de minimizare a costurilor.

Definitia 1. Fie perechea de probleme de programare liniara,

(1) maximizeaza

cu restrictiile,

si

(2) minimizeaza

cu restrictiile,

unde este o matrice , sunt vectori cu n componente si sunt vectori cu m componente. Problemele (1) si (2) se numesc duale. Problema (1) se numeste problema primala, iar problema data prin (2) se numeste problema duala.

Teorema 1. Fie (1) problema primala. Problema duala asociata problemei (2) este problema (1).

Teorema 2. Fie problema de programare liniara in forma canonica,

maximizeaza

cu restrictiile,

Forma duala este problema de programare liniara,

minimizeaza

cu restrictiile,

w nerestrictionat.

Teorema Fie problema de programare liniara,

maximizeaza

cu restrictiile,

nerestrictionat

Forma duala este problema de programare liniara,

minimizeaza

cu restrictiile,

Exemplul 1. Fie problema primala,

Maximizeaza

cu restrictiile

Problema duala asociata este,

Minimizeaza

cu restrictiile

In urmatorul tabel sunt prezentate relatiile dintre problema primala si problema duala.

Tabelul 1

2. Interpretarea economica a problemei duale

In functie de punctul de vedere abordat, problema duala a unei probleme de programare liniara poate avea o serie de interpretari economice, in continuare fiind prezentata unele dintre cele mai uzuale dintre acestea.

Exemplul 2. Vom considera in continuare problema de tip analiza productiei prezentata in Exemplul 2.1, capitolul 2, sectiunea 2.1. Modelul matematic este problema de programare liniara in forma standard,

Maximizeaza

cu restrictiile

Prima restrictie a sistemului se refera la numarul de ore pe zi in care fierastraul este disponibil. Cea de-a doua constrangere este relativa la numarul de ore din zi in care poate fi utilizata rindeaua industriala.

In general, in cea de-a i-a restrictie din (1),

,

este interpretat ca stocul maxim disponibil din cea de-a i-a resursa (material sau, generic, intrare). Coeficientul reprezinta cantitatea din cea de-a i-a intrare necesara unei unitati din cel de-al j-lea produs (sau, generic, iesire).

In exemplul 2, are semnificatia de numar de ore de utilizare a rindelei industriale necesare producerii a 1000 de metri de scanduri finisate.

Variabila este cantitatea (necunoscuta) din cea de-a j-a iesire care trebuie produsa. Coeficientul din functia obiectiv reprezinta profitul sau valoarea derivata in urma producerii unei unitati din cea de-a j-a iesire.

In exemplul 2 solutia optimala maximizeaza valoarea totala a tuturor iesirilor,

.

Problema duala a problemei de programare liniara din exemplul 2 rezulta,

Minimizeaza

cu restrictiile

.

Coeficientii primei restrictii reprezinta cantitatile necesare din fiecare intrare pentru a produce o unitate din primul produs (iesire).

Pe exemplul considerat, pentru a produce 1000 de metri de scandura finisata, sunt necesare 2 ore de taiere si 5 ore de rindeluire. Membrul drept al primei constrangeri este profitul sau valoarea generata per unitate din prima iesire. Prin rezolvarea problemei duale, obtinem .

Problema duala a unei probleme de programare liniara in forma standard (1) este,

minimizeaza

cu restrictiile,

Cea de-a j-a constrangere a problemei duale este,

Similar interpretarii din problema primala, reprezinta cantitatea din cea de-a i-a intrare necesara producerii unei unitati din cea de-a j-a iesire, iar membrul drept al inegalitatii este valoarea generata per unitate de iesire j. Cu alte cuvinte, unitatile din variabila duala au semnificatia de valoare per unitate de intrare i. Variabilele problemei duale, numite in continuare variabile duale au semnificatia de preturi, costuri, respectiv valori ale fiecarei unitati din fiecare intrare (resursa) i si sunt referite, functie de context, prin preturi contabile, preturi fictive, preturi ascunse sau valori imputate.

In cazul unei solutii optimale a problemei primale, profitul, egal cu , este dat si prin (din teorema dualitatii, prezentata in sectiunea 3). Astfel, cresterea cu o unitate a celei de-a i-a intrari determina cresterea cantitatii (si deci a profitului) cu unitati. Rezulta ca cea de-a i-a componenta a unei solutii optimala a problemei duale, , reprezinta contributia adusa profitului de o unitate din cea de-a i-a intrare. Valorile variabilelor duale nu sunt direct legate de costurile reale ale resurselor (intrarilor).

Pe exemplul considerat, 2, faptul ca solutia optima a problemei duale, , nu implica un cost de rindeluire de 35 lei per ora si un cost de taiere de 10 lei per ora. Costurile reale sunt inglobate in modalitatea in care a fost stabilit faptul ca profitul obtinut din producerea a 1000 unitati de produs este de 120 lei in cazul scandurii finisate, respectiv 100 de lei in cazul scandurii de constructii (o ipoteza de lucru a problemei). In acest sens, rezulta ca variabilele duale nu reprezinta costuri reale, ci fictive.

Membrul stang al celei de-a j-a constrangeri a problemei duale semnifica valoarea totala a intrarilor utilizate pentru producerea unei unitati din cea de-a j-a iesire, notata in continuare cu VT. Aceasta restrictie semnifica faptul ca VT trebuie sa fie cel putin la fel de mare ca si profitul adus de o unitate din cea de-a j-a iesire. In cazul unei solutii optimale, valoarea membrului stang al celei de-a j-a constrangeri a problemei duale reprezinta contributia totala adusa profitului de o unitate din cea de-a j-a iesire, deci este de asteptat sa fie utilizata solutia optimala in cazul in care contributia la profit este cel putin la fel de mare ca profitul actual (real). In caz contrar, decizia corecta pe care trebuie sa o ia producatorul este de a utiliza intrarile disponibile intr-o alta maniera.

In concluzie, in problema duala sunt calculate preturile ascunse ale fiecarei resurse (intrari) astfel incat costul total sa fie minim, cu constrangerea ca aceste preturi sa determine obtinerea unor valori corespunzatoare pentru fiecare unitate de iesire produsa mai mari sau egale cu profiturile fiecarei unitati de produs.

O alta varianta de interpretare a variabilelor duale este bazata pe ideea ca, pentru w solutie optimala a problemei duale, profitul este dat de (pe baza teoremei dualitatii, prezentata in sectiunea urmatoare). Pentru a creste profitul, producatorul trebuie sa mareasca disponibilitatea a cel putin uneia din resurse. Daca pentru o intrare data, i, creste cu o unitate, profitul este marit cu . Rezulta ca reprezinta valoarea marginala a celei de-a i-a intrari. Pe baza aceluiasi tip de rationament, este pierderea suportata in cazul in care o unitate din cea de-a i-a resursa ramane neutilizata, deci semnifica, de asemenea, valoarea de inlocuire corespunzatoare resursei i, in scopuri asiguratorii. Spre exemplu, o companie de asigurari va folosi problema duala in cazul pretentiilor reclamate in cazul pierderii unor resurse asigurate, in sensul in care va incerca sa plateasca cat mai putin posibil pentru a rezolva solicitarea.

Teorema dualitatii. Relatiile dintre solutiile problemei primale si solutiile problemei duale

Fie P1 o problema generala de programare liniara si P varianta canonica a lui P1, rezultata prin eventuala introducere a variabilelor slack si a variabilelor artificiale. P este data prin,

(3) maximizeaza

cu restrictiile,

unde este o matrice care contine o submatrice unitate , este matrice este matrice . Daca este variabila slack, atunci . De asemenea, este utilizata metoda in doua faze pentru variabilele artificiale, deci dacaeste variabila artificiala, atunci .

Consideram in continuare tabelul simplex pentru rezolvarea problemei (3) la un moment al aplicarii metodei simplex, prin intermediul caruia este reprezentata o solutie de baza admisibila, S. Obiectivul este acela de a deriva o varianta alternativa a criteriului de optimalitate a solutiei S.

Fie multimea indicilor variabilelor de baza, componente ale lui S. Fie N multimea indicilor variabilelor non-baza si cea de-a j-a coloana a matricei , . Sistemul de restrictii din (3) este exprimat prin,

(4)

Variabilele non-baza sunt setate pe valoarea 0, deci din (4) obtinem,

(5)

Fie B matricea patratica de ordin m cu coloanele si . Din relatia (5) rezulta,

(6)

Deoarece coloanele matricei B sunt liniar independente, rezulta ca B este inversabila, deci, pe baza relatiei (6) obtinem,

(7)

Relatia (7) semnifica faptul ca m-tuplul variabilelor de baza are valoarea in tabelul simplex.

Deoarece cei m vectori coloane ale lui B sunt liniar independenti, rezulta ca formeaza o baza a spatiului R^m si, pentru fiecare , vectoruleste exprimat in termenii vectorilor baza prin,

(8)

Vectorul coeficientilor dezvoltarii (8), , este cea de-a j-a coloana a tabelului simplex curent.

Relatia (8) este exprimata in termenii matricei B prin,

(9) ,

deci

(10) .

Relatia (10) exprima faptul ca fiecare coloana a tabelului simplex curent rezulta prin inmultirea la stanga cu a coloanei corespunzatoare din tabelul simplex initial.

Prin utilizarea notatiilor folosite, definim,

(11)

Pe baza relatiei (10), rezulta,

(12)

si, in continuare, pentru orice ,

.

Functia obiectiv este,

(13)

In vederea testarii criteriului de optimalitate tabelului simplex de la momentul curent, relatia (13) este modificata astfel incat coeficientii variabilelor baza sa devina nuli, prin aplicarea urmatorului procedeu. Relatiei (13) ii sunt adaugate , pentru orice si este obtinuta (14); cea de-a r-a linie a tabelului curent este exprimata prin,

,

unde este cea de-a r-a componenta a vectorului.

(14) .

Din (14) obtinem,

si, din (11),

(15).

Deoarece, pentru orice ,, (15) este echivalenta cu,

,

deci elementele liniei obiectiv a tabelului curent sunt,

(16) .

In concluzie, criteriul de optim al metodei simplex poate fi reformulat astfel: tabelul curent reprezinta o solutie optimala daca si numai daca, pentru orice .

Relatiile dintre solutiile problemelor primala si duala

Asa cum a rezultat in capitolul 2, tentativa de rezolvare a unei probleme de programare liniara are urmatoarele rezultate alternative:

Nu exista solutii admisibile

Exista o solutie optimala finita

Exista solutii admisibile, dar functia obiectiv este nemarginita.

Teorema 4. Teorema dualitatii in sens slab

Daca este solutie admisibila a problemei primale definite de (1) si este solutie admisibila a problemei duale (2), atunci,

Teorema 5

1. Daca problema primala are solutii admisibile, dar functia obiectiv este nemarginita, atunci problema duala nu are solutii fezabile.

2. Daca problema duala are solutii fezabile, dar functia obiectiv este nemarginita, atunci problema primala nu are solutii admisibile.

Teorema 6 Daca este solutie admisibila a problemei primale (1) si este solutie admisibila a problemei duale (2) si daca , atunci si sunt solutii optimale ale problemei (1), respectiv (2).

Teorema 7 Teorema dualitatii

1. Daca fie problema primala/duala are o solutie admisibila si functia obiectiv are o valoare optima finita, atunci problema duala/primala are o solutie admisibila cu aceeasi valoare obiectiv.

2. Daca problema primala (1) are solutii admisibile si daca problema duala (2) are solutii admisibile, atunci

(i) problema primala are o solutie optimala,

(ii) problema duala (2) are o solutie optimala, si

(iii) .