072 073 2

72

Programowanie liniowe

Maksymalne zwiększenie wykorzystania środka S₂ pozwala na uzyskanie zysku na poziomie 16 + 4 = 20 jednostek.

1.7. Dualna metoda simpleks

Rozważmy ponownie zadanie sformułowane w przykładzie 1.12 i sprowadźmy je do postaci bazowej. Przypomnijmy, że ma ono postać:

14y, + 8y₂ + 16y₃ —» min,

2y, + y₂ + 4y₃ ^ 2,

2y,+2y₂    ^3,

y„ >₂,    0.

Po wprowadzeniu zmiennych bilansujących y₄ i y₅, otrzymujemy zadanie:

14y, + 8y₂+ 16y₃ —> min,

2y,+ y₂+ 4y₃—y₄ =2,

2y, + 2 y₂    ->5 = 3,

>1, >2, >3, >4, ys ^ 0.

Aby otrzymać postać bazową tego zadania, mnożymy obydwa warunki ograniczające przez liczbę -1. Mamy:

14y, + 8y₂ + 16y₃ —> min,

-2y,— y₂- 4v₃ + y₄    =-2,

-2y,-2y₂    +>s = “3,

y\, y₂, ys- >4, y.4 > 0.

Otrzymujemy w len sposób zadanie w postaci bazowej. Zmiennymi bazowymi są y₄ i y₅, zmiennymi niebazowymi — zmienne y,, y₂ i y₃. Rozwiązanie bazowe odpowiadające tej bazie ma postać:

y, =0, y₂ = 0, y₃ = 0, y₄ = -2, y₅ = -3.

Ponieważ wartości y₄ i y₅ są ujemne, rozwiązanie to nie jest rozwiązaniem dopuszczalnym. Możemy jednak sprawdzić, czy spełnia ono kryterium optymalno-ści metody simpleks. Zapisujemy rozpatrywane zadanie w tablicy simpleksowej i obliczamy współczynniki optymalności (tablica 1.23).

Widzimy, że wszystkie wskaźniki optymalności są nieujemne. Rozważamy zadanie minimalizacji, a zatem interesująca nas baza jest optymalna.

Przypomnijmy, że w metodzie simpleks (którą będziemy nazywali dalej prymalną metodą simpleks) konstruujemy kolejne bazowe rozwiązania dopuszczalne. Postępowanie kończymy wtedy, kiedy stwierdzimy, że otrzymane rozwiązanie jest jednocześnie rozwiązaniem optymalnym.

73

W rozpatrywanym przez nas przykładzie mamy odmienną sytuację. Pierwsze

Dualna metoda simpleks

Tablica 1.23

CX —i	min	14	8	16	0	0	b
Baza	^CB	y>	yi		y*	y>
y4	0	-2	-i	-4	i	0	-2
y.i	0	-2	-2 j	0	0	i	-3
^cr	-z,	14	8 J	16	0	0	0

<*e •

■< t.

rozwiązanie bazowe jest,optymalne, natomiast nie jest dopuszczalne. Pojawia się więc pytanie: Czy istnieje możliwość „odwrócenia” sposobu rozwiązania zadania programowania liniowego, proponowanego w prymalnej metodzie simpleks, i konstruowania ciągu rozwiązań optymalnych lak długo, aż ostatnie rozwiązanie okaże się również rozwiązaniem dopuszczalnym?

Taką możliwość daje dualna metoda simpleks. Po dokładniejszym poznaniu dualnej metody simpleks można stwierdzić, że rozwiązanie problemu prymalnego dualną metodą simpleks polega na stosowaniu prymalnej metody simpleks do problemu dualnego. Dualna metoda simpleks jest szczególnie warta polecenia dla zadania minimalizacji, gdy wszystkie współczynniki funkcji celu są nicujemne, a warunki ograniczające zadania są w postaci nierówności typu > (jak to występuje w zadaniu z przykładu 1.10); wtedy bowiem na pewno pierwsze rozwiązanie bazowe, otrzymane po wprowadzeniu zmiennych bilansujących, jest rozwiązaniem optymalnym (lecz niedopuszczalnym).

1.7.1. Przebieg obliczeń

W każdej iteracji dualnej metody simpleks wykorzystujemy kolejno: kryterium dopuszczalności, kryterium wyjścia i kryterium wejścia. Kolejne iteracje wykonujemy tak długo, aż stwierdzimy, że otrzymaliśmy rozwiązanie dopuszczalne rozważanego zadania lub też, że jest ono sprzeczne. Poniżej przedstawimy kryteria wykorzystywane w dualnej metodzie simpleks. Są one następujące:

C&ż?    ’• Q

Kryterium dopuszczalności

Jeżeli wartości wszystkich wyrazów wolnych są nieujemne, to rozpatrywane rozwiązanie jest dopuszczalne.

I Kryterium wyjścia

Ze wszystkich wyrazów wolnych wybieramy najmniejszy. Odpowiadająca mu ; zmienna jest zmienną opuszczającą bazę. Jeżeli jest więcej niż jedna najmniejsza l wartość, to wybieramy zmienną o najniższym numerze.

I