To tylko jedna z 7 stron tej notatki. Zaloguj się aby zobaczyć ten dokument.
Zobacz
całą notatkę
Z każdym zadaniem programowania linowego sprzężone jest pewne inne zadanie programowania liniowego, zwane zadaniem dualnym.
Jeżeli pierwotnym zadaniem (ZP) jest:
Interpretacja ekonomiczna problemu dualnego
Zadanie pierwotne opisuje problem maksymalizacji przychodu osiąganego z produkcji wyrobów. Zużycie środków produkcji nie może przekroczyć przyjętych limitów. Sytuację tę przedstawia następujący model programowania liniowego:
Badania operacyjne ZiIP rok 2 ćwiczenia - zajęcia 3
Dualność w programowaniu liniowym
Z każdym zadaniem programowania linowego sprzężone jest pewne inne zadanie programowania liniowego, zwane zadaniem dualnym.
Jeżeli pierwotnym zadaniem (ZP) jest:
To zadaniem dualnym (ZD) jest:
Relacje zachodzące między ZP i ZD:
W każdym ZD jest tyle zmiennych, ile warunków w ZP (każdemu ograniczeniu w ZP odpowiada jedna zmienna w ZD).
W ZD jest tyle warunków, ile zmiennych w ZP.
Współczynniki w funkcji celu ZP są wyrazami wolnym (czyli prawymi stronami ograniczeń) w ZD.
Prawe strony ograniczeń w ZP są współczynnikami funkcji celu w ZD.
Macierz współczynników ZD jest transpozycją macierzy współczynników w ZP.
Kryteria decyzyjne ZP i ZD są odwrotne.
Reguły budowy ZD:
Jeżeli w ZP dany warunek jest równością, to odpowiadająca mu zmienna w ZD nie ma ograniczeń.
Jeżeli w ZP dany warunek jest nietypową nierównością, to w ZD odpowiadająca mu zmienna jest mniejsza od zera ().
Jeżeli w ZP na zmienną nie nałożono ograniczeń, to w ZD warunek jest równością.
Jeżeli w ZP zmienna , to w ZD warunek jest nietypową nierównością.
Zadanie pierwotne:
Zadanie dualne:
Zadanie pierwotne:
Zadanie dualne:
Zadanie pierwotne:
Zadanie dualne:
Zadanie pierwotne:
Zadanie dualne:
Zadanie pierwotne:
Zadanie dualne:
Z twierdzenia Dantziga-Ordena:
Jeżeli ograniczenie zadania dualnego jest spełnione jako nierówność ostra (zmienna osłabiająca ), to zmienna zadania pierwotnego jest równa 0 ().
Jeżeli zmienna zadania dualnego jest dodatnia (), to ograniczenie zadania pierwotnego jest równością (zmienna osłabiająca ).
Z tzw. warunków dopełniającej niesztywności:
Jeżeli ograniczenie zadania pierwotnego spełnione jest jako nierówność ostra, to zmienna zadania dualnego jest równa 0 ().
Zadanie 1.
Należy rozwiązać zadanie dualne i na tej podstawie wyznaczyć rozwiązanie zadania pierwotnego.
Zadanie pierwotne
... zobacz całą notatkę
Komentarze użytkowników (0)