Algoritmul Simplex Dual

Problemei de programare liniara:

(24)

i se asociaza problema:

(25) unde

Problema (24) se va numi primala iar problema (25) duala problemei (24) si reciproc.

Exemplul II.7.1

Folosind tabelul:

1 2 2 0

gasim duala:

Teorema II.7.1. Fie X o solutie posibila pentru problema (24) si Y o solutie posibila pentru problema (25). Atunci

Demonstratie: Din inmultind la stanga cu obtinem:

Pe de alta parte:

Dar cum ajungem la concluzia .

Teorema II.7.2. Daca (24) are optim finit atunci (25) are optim finit si avem unde este o solutie optima pentru (24) iar o solutie optima pentru (25).

Demonstatie: Din teorema II.7.1. pentru orice pereche de programe duale X,Y, avem . Deci are loc si . Cum f este o functie liniara, deci continua, atunci exista si are loc .

Pe de alta parte folosind (13) si teorema II.4.1. avem . Se demonstreaza ca este un program optim pentru duala (25). Atunci:

Teorema II.7.3. (teorema ecarturilor complementare)

Fie X,Y solutii ale problemelor (24), respectiv (25). Atunci X,Y sunt solutii optime daca si numai daca au loc relatiile:

Demonstratie. Avem:

Folosind teoremele II.7.2. si II.7.1. obtinem ca X,Y sunt programe optime daca si numai daca ceea ce conduce la:

sau:

Dualitatea se foloseste cel mai frecvent in cazul in care problema primala necesita calcule multe:

Exemplul II.7.2.

Pentru a rezolva aceasta problema cu algoritmul simplex trebuie introduse patru variabile de egalizare, dar scriind problema duala:

aceasta necesita numai doua variabile de egalizare. Obtinem:

2 1 3 2 1 0

1 1 3 0 1

-1 -1 -3 -1 0 0 0

1/2 -1/2 0 -5/2 1 -3/2

1/2 1/2 1 3/2 0 1/2

1/2 1/2 0 7/2 0 3/2 -3/2

deci

Pentru a putea formula duala unei probleme de minim am vazut ca restrictiile trebuie sa aiba forma (24). In acest caz, restrictiile sunt numite concordante, iar cele neconcordante. Pentru problema