Twierdzenie o dualności – rezultat przedstawiający cztery możliwości dotyczące istnienia rozwiązań optymalnych i dopuszczalnych problemu programowania liniowego w postaci standardowej.
Wypowiedź Spełniony jest jeden z czterech warunków: (S) oraz (DS) mają rozwiązania optymalne, odpowiednio i spełniające równość:
(S) nie ma rozwiązania dopuszczalnego, natomiast (DS) ma taki ciąg rozwiązań dopuszczalnych że:
(DS) nie ma rozwiązania dopuszczalnego, natomiast (S) ma taki ciąg rozwiązań dopuszczalnych że:
(S) oraz (DS) nie mają rozwiązań dopuszczalnych, gdzie (S) jest problemem programowania liniowego zapisanym w postaci standardowej:
natomiast (DS) jest postacią standardową problemu do niego dualnego:
Kategoria:Metody optymalizacji Kategoria:Twierdzenia matematyczne