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

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.

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