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 înmultind la stânga 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 în cazul în 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). În acest caz, restrictiile sunt numite concordante, iar cele neconcordante. Pentru problema primala de maxim, restrictiile sunt cele concordante iar cele neconcordante.
În caz ca nu au aceasta forma pot fi aduse la forma (24) dupa urmatoarele reguli:
modelul dat
modelul dual
numar de variabile
numar de restrictii
numar de restrictii
numar de variabile
minim
maxim
maxim
minim
termeni liberi ai restrictiilor
coeficientii functiei obiectiv
coeficientii functiei obiectiv
termenii liberi ai restrictiilor
coloanele matricii restrictiilor
liniile matricii restrictiilor
restrictie concordanta
variabila nenegativa
restrictie neconcordanta
variabila nepozitiva
restrictie egalitate
variabila libera
variabila nenegativa
restrictie concordanta
variabila nepozitiva
restrictie neconcordanta
variabila libera
restrictie egalitate
Exemplul II.7.3.
Duala va fi:
...