068 069 2

68 Programowanie liniowe

Z powyższych warunków wynikają następujące wnioski:

Warunek (1-14)

Jeżeli 2y,+>s + 4y₃-2 > 0 (co oznacza, że pierwszy warunek ograniczający : w zadaniu dualnym jest spełniony jako ostra nierówność), to zmienna komplementarna JC] =0.

Jeżeli jc, > 0, to 2y,+y₂ + 4y₃ —2 = 0. Oznacza to, że pierwszy warunek ograniczający w zadaniu dualnym, komplementarny do zmiennej > 0, musi być spełniony jako równanie.

Warunek (1.15)

Jeżeli 2y, +2y₂ — 3 > 0, co oznacza, że drugi warunek ograniczający w zadaniu dualnym jest spełniony jako ostra nierówność, to zmienna komplementarna ,r₂ = 0.

Jeżeli x₂>0, to 2y, +2y₂ - 3 = 0. Oznacza to, że drugi warunek ograniczający w zadaniu dualnym, komplementarny do zmiennej x₂ > 0. musi być spełniony jako równanie.

Otrzymane powyżej zależności można uogólnić następująco:

1.    Jeżeli dowolna zmienna w rozwiązaniu optymalnym zadania prymalnego lub dualnego jest dodatnia, to odpowiadający jej komplementarny warunek ograniczający spełniony jest jako równanie.

2.    Jeżeli dowolny warunek ograniczający dla rozwiązania optymalnego zadania prymalnego lub dualnego spełniony jest jako ostra nierówność, to odpowiadająca temu warunkowi zmienna komplementarna przyjmuje wartość zero.

Wnioski z twierdzenia o komplcmentarności można wykorzystać m.in. do rozwiązywania metodą geometryczną zadania programowania liniowego o dowolnej liczbie zmiennych, w którym występują dwa warunki ograniczające. Tworzymy wówczas zadanie dualne. Znajdujemy geometrycznie jego rozwiązanie optymalne i wykorzystujemy twierdzenie o komplementarności do odtworzenia składowych rozwiązania optymalnego zadania prymalnego.

Przykład 1.13

Pokażemy zastosowanie sformułowanych powyżej zależności, wykorzystując znane już wcześniej rozwiązanie z przykładu 1.1: JC|=4, x₂ = 2. Zadanie to jest zadaniem prymalnym do sformułowanego w przykładzie 1.12 zadania dualnego.

Ponieważ zmienne jc, i x₂ przyjmują wartości dodatnie, więc odpowiadające im j warunki komplementarne muszą być spełnione jako równania. Mamy zatem: 2yi+y₂ + 4y₃ = 2,

2>'t +2 _y₂ = 3.

Sprawdzamy teraz, które z warunków ograniczających zadania prymalnego są spełnione jako ostre nierówności. Podstawiając a, =4 i x₂ = 2, otrzymujemy:

2-4 + 2-2< 14, 4 + 2-2 = 8, 4-4= 16.

Ponieważ pierwszy z warunków ograniczających zadania prymalnego spełniony jest jako ostra nierówność, więc odpowiadająca mu w zadaniu dualnym zmienna komplementarna y,=0. Podstawiając tę wartość do utworzonego wcześniej układu równań, otrzymujemy układ:

y₂+4y₃=2,

2y₂ = 3,

z którego wyliczamy pozostałe dwie składowe rozwiązania optymalnego zadania dualnego: y₂=l,5, y₃ = 0,125. Zauważmy, że dodatnie ceny dualne dla środków S₂ i S₃ pociągają za sobą całkowite zużycie zasobów tych środków przy realizacji planu maksymalizacji zysku, natomiast niepełne zużycie środka 5, w planie optymalnym powoduje, że cena dualna tego środka jest równa 0.

Zadanie dualne można sformułować nie tylko dla zadania prymalnego w postaci klasycznej.

Przykład 1.14

Zapisać zadanie dualne do zadania prymalnego:

3x| + 2x₂ + 4x_} —> max,

2x, - 2x₂ + 3jc₃ ^ 15,

2x, - lx₂ + 3.rj ^ 18,

-2x, -x₂ + x₃ = 5,

x, ^ 0, x₂ < 0, x₃ — dowolne.

Podane uprzednio związki między zadaniem prymalnym i dualnym wymagają pewnego uzupełnienia. W zadaniu prymalnym pierwsze ograniczenie jest typu (co oznacza, że lewa strona tego ograniczenia jest mniejsza od prawej lub jej równa). Odpowiadająca mu zmienna w zadaniu dualnym spełnia związek y, > 0. Drugie z ograniczeń jest typu    a odpowiadająca mu zmienna w zadaniu

dualnym spełnia związek y₂^0. Trzecie ograniczenie jest w postaci równości, a odpowiadająca mu zmienna dualna y₃ jest nieograniczona co do znaku.

Nieco inaczej kształtują się zależności pomiędzy zmiennymi zadania prymalnego i ograniczeniami zadania dualnego. Zachodzi związek x, > 0, stąd wynika, że odpowiadająca tej zmiennej pierwsze ograniczenie zadania dualnego jest typu Ponieważ x₂ <0, drugie ograniczenie zadania dualnego jest typu „ Zmienna x₃ jest nieograniczona co do znaku, stąd odpowiadający tej zmiennej trzeci warunek ograniczający zadania dualnego ma postać równości. Uwzględniając powyższe uwagi, otrzymujemy zadanie: