4. Dualizm w programowaniu liniowym Reguły tworzenia zadania dualnego



Yüklə 29,07 Kb.
tarix17.11.2018
ölçüsü29,07 Kb.

4. Dualizm w programowaniu liniowym

4.1. Reguły tworzenia zadania dualnego


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:



  1. Jeżeli w ZP i – ty warunek jest równością to w ZD i – ta zmienna nie ma ograniczenia.

  2. Jeżeli w ZP i – ty warunek jest nietypową nierównością to w ZD zmienna .

  3. Jeżeli w ZP j – ta zmienna nie ma ograniczenia to j – ty warunek ZD jest równością.

  4. 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.


  1. Jeżeli w ZP jest nieograniczona z góry to ZD jest sprzeczny.

  2. 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.
    1. 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.


ZP







zmienne

optymalne wartości zmiennych

wskaźniki optymalności







decyzyjne




















swobodne

















decyzyjne







wskaźniki optymalności

optymalne wartości zmiennych

zmienne







ZD


Dostları ilə paylaş:


Verilənlər bazası müəlliflik hüququ ilə müdafiə olunur ©genderi.org 2019
rəhbərliyinə müraciət

    Ana səhifə