4. Dualizm w programowaniu liniowym
Jeżeli zadaniem pierwotnym (prymalnym) jest problem
to zadaniem dualnym (ZD) będzie zadanie:
-
W zadaniu dualnym jest tyle zmiennych ile nierówności w zadaniu pierwotnym.
-
W zadaniu dualnym jest tyle warunków ile zmiennych w zdaniu pierwotnym.
-
Wagi funkcji celu w zadaniu pierwotnym są wyrazami wolnymi w zadaniu dualnym.
-
Macierz współczynników zadania dualnego jest transpozycją macierzy współczynników zadania pierwotnego.
-
Jeżeli zadanie pierwotne jest na max to dualne na min i odwrotnie.
-
Nierówności warunków zmieniają znak na przeciwny.
-
Zadanie pierwotne jest zadaniem dualnym do dualnego.
Nierówności „” dla zadania max i „” dla min nazywamy typowymi.
Przykład 4.1.1.
W przypadku ogólnym stosujemy następujące reguły tworzenia ZD:
-
Jeżeli w ZP i – ty warunek jest równością to w ZD i – ta zmienna nie ma ograniczenia.
-
Jeżeli w ZP i – ty warunek jest nietypową nierównością to w ZD zmienna .
-
Jeżeli w ZP j – ta zmienna nie ma ograniczenia to j – ty warunek ZD jest równością.
-
Jeżeli w ZP to w ZD j – ty warunek jest nietypową nierównością.
Przykład 4.1.2.
ZP:
Wówczas ZD jest postaci:
4.2. Twierdzenia o dualności Twierdzenie 4.2.1
Jeżeli i są rozwiązaniami odpowiednich symetrycznych problemów dualnych to
Dowód
∎
Twierdzenie 4.2.2. o istnieniu (Gale’a – Kuhna – Tuckera)
Jeżeli jeden z symetrycznych problemów dualnych ma rozwiązanie optymalne to drugi też ma rozwiązanie optymalne.
Jeżeli oba mają rozwiązania dopuszczalne to wtedy oba mają rozwiązania optymalne.
Dla rozwiązania optymalnych zachodzi .
Twierdzenie 4.2.3. o optymalności
Jeżeli istnieją dwa rozwiązania dopuszczalne symetrycznych problemów dualnych takie że to obydwa rozwiązania są optymalne.
Twierdzenie 4.2.4. o komplementarności (Dantziga – Ordena)
Niech i będą rozwiązaniami dopuszczalnymi symetrycznych problemów dualnych, wówczas:
Twierdzenie 4.2.5. o równowadze
Jeśli jest i rozwiązaniem dopuszczalnym ZP i jest rozwiązaniem dopuszczalnym ZD, to aby były to rozwiązania optymalne potrzeba i wystarcza aby zachodziły następujące warunki:
Dowód
Z twierdzenia 4.2.4:
.
Ponieważ są dopuszczalne to
i
dla czyli
co daje nierówności dla dla .
Zatem .
Stąd wynikają jasno. Analogicznie dowodzimy . W drugą stronę twierdzenie jest oczywiste ( na podstawie tw. 4.2.4.).
∎
Przykład 4.2.1.
ZP:
ZD:
Rozwiązanie optymalne ZD: . Zmienna podpierająca nierówność : czyli . Zatem z mamy . Pierwszy problem się upraszcza
Twierdzenie 4.2.6. -
Jeżeli w ZP jest nieograniczona z góry to ZD jest sprzeczny.
-
Jeżeli z ZD jest nieograniczona z dołu to ZP jest sprzeczny.
Dowód (wynika z twierdzenia 4 .2.1)
Uwaga
Twierdzenie odwrotne do powyższego nie jest prawdziwe, ponieważ jeżeli jedno z zagadnień jest sprzeczne, to zagadnienie dualne może być sprzeczne lub jego funkcja celu może przyjmować nieograniczone wartości.
Odczytywanie rozwiązań ZD z tabeli simpleksowej dla ZP Twierdzenie 4.3.1.
Jeżeli istnieje skończone rozwiązanie optymalne ZP względem bazy , to wektor u, którego bazowe składowe określa wzór , jest rozwiązaniem optymalnym ZD.
Z powyższego twierdzenia oraz z podanego w części 3.2. sposobu obliczania wskaźników optymalności wynika, że wskaźniki optymalności odpowiadające zmiennym swobodnym wyznaczają optymalne wartości zmiennych dualnych, wskaźniki optymalności odpowiadające zmiennym decyzyjnym wyznaczają wartości zmiennych swobodnych w optymalnym rozwiązaniu ZD.
Dostları ilə paylaş: |