To tylko jedna z 2 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
DUALIZM W PROGRAMOWANIU MATEMATYCZNYM Para symetrycznych zadań dualnych PL Prymalne ZPL : Dualne ZPL : max c T ⋅ x min b T ⋅ y przy ograniczeniach przy ograniczeniach
A ⋅ x ≤ b A T ⋅ y ≥ c x ≥ 0 y ≥ 0
gdzie: x - zmienne prymarne, y - zmienne dualne
Przykład: Zakład ma zapasy dwóch surowców I i II. Surowca I - 90 jednostek, surowca II - 240. Może podjąć produkcję dwóch wyrobów I i II lub surowce sprzedać. Jeżeli podejmie produkcję wyrobów musi zdecydować ile wyprodukować wyrobu I (x 1 ), a ile wyrobu II (x 2 ). Cena wyrobu I to 150 zł, a wyrobu II 100 zł. Do produkcji wyrobu I potrzeba 0,5 jednostki surowca I i 1 surowca II. Do produkcji wyrobu II natomiast potrzeba 2 jednostki surowca I i 1 surowca II.
Jeżeli zdecyduje się sprzedać surowce za jaką minimalną cenę powinien to zrobić, aby zyskać więcej niż na produkcji wyrobów.
Zadanie prymarne ZP (produkcja): Fc: Maksymalne przychody ze sprzedaży wyrobów I i II
max(150· x 1 +100· x 2 )
Ograniczenia: Zapasy surowców
0,5· x 1 +1· x 2 ≤90
2· x 1 +1· x 2 ≤240
x 1 ≥0, x 2 ≥0
Zadanie dual ne ZD (sprzedaż surowców): Fc: Minimalne przychody ze sprzedaży surowców I i II
min(90· y 1 +240· y 2 )
Ograniczenia: Cena sprzedaży surowców zużytych na produkcję wyrobów I i II, musi przekroczyć ceny uzyskane za wyroby
0,5· y 1 +2· y 2 ≥150 1· y 1 +1· y 2 ≥100
y 1 ≥0, y 2 ≥0
Zadanie prymalne
Zadanie dualne
Rozwiązanie: x 1 =100 i x 2 =40
Rozwiązanie: y 1 =33,33 i y 2 =66,67
Fc: 19000
Fc: 19000
Można udowodnić, że rozwiązaniem zadania dualnego jest wektor:
=c B ·B -1 gdzie: c B - wektor współczynników funkcji celu dla rozwiązania optymalnego ZP,
B -1 - macierz bazowa dla rozwiązania optymalnego ZP
Elementy wektora nazywane są cenami dualnymi .
W przykładzie można je interpretować jako minimalne ceny surowców, przy których jeszcze opłaca się produkcja.
1
... zobacz całą notatkę
Komentarze użytkowników (0)