076 077 2

76 Programowanie liniowe

nego, zapisanym w tablicy 1.7. Z kolei z tablicy tej odczytujemy wartości wskaż- J ników optymalności dla zmiennych niebazowych zadania prymalnego; wynoszą ' one odpowiednio -1,50 dla zmiennej x₄ i -0,125 dla zmiennej x₅. Wartości te są i takie same (z dokładnością do znaku) jak wartości odpowiadających im zmiennych s komplementarnych y₂ i y₃ w rozwiązaniu optymalnym zadania dualnego.

» :

1.7.2. Pierwsza optymalna postać bazowa

O ile w prymalncj metodzie simpleks pewną trudność mogło stanowić znalezienie pierwszego dopuszczalnego rozwiązania bazowego, to w dualnej tl metodzie simpleks nie zawsze łatwe jest znalezienie pierwszego bazowego roz- f • wiązania optymalnego. Jeżeli zaistnieje konieczność rozwiązania dualną metodą simpleks takiego zadania, w którym nie dysponujemy pierwszą optymalną postacią \ bazową, to do jej otrzymania możemy zastosować metodę sztucznego ograniczenia, będącą odpowiednikiem metody zmiennych sztucznych wykorzystywanej w prymalnej metodzie simpleks do konstrukcji pierwszego bazowego rozwiązania dopuszczalnego. Poniżej opiszemy tę metodę.

Przez dołączenie zmiennych bilansujących sprowadzamy zadanie do dowolnej postaci bazowej. Sprawdzamy, czy postać ta jest optymalna. Jeżeli nie jest, konstruujemy sztuczne ograniczenie. Lewą stronę tego ograniczenia stanowi suma zmiennych niebazowych, prawa to odpowiednio dobrana duża liczba. Dobór ten powinien uwzględniać konieczność spełnienia tego ograniczenia dla wszystkich dopuszczalnych wartości zmiennych, które tworzą to ograniczenie. Ponieważ j otrzymujemy nierówności typu <, aby ją zbilansować, do lewej strony dodajemy zmienną bilansującą.

Następnie dokonujemy jednokrotnej wymiany bazy. Z bazy usuwamy zmienną bilansującą skonstruowanego przed chwilą sztucznego ograniczenia, a na to miejsce wprowadzamy tę zmienną niebazową, która ma największy współczynnik optymalności. Rozwiązanie otrzymane po wykonaniu tego przekształcenia jest bazowym >' rozwiązaniem optymalnym.

Naszkicowany powyżej sposób wprowadzenia sztucznego ograniczenia wskazuje na to, że tablica simpleksowa rozpatrywanego zadania zostaje rozszerzona i zwiększa się liczba zmiennych bazowych, co powoduje, że w ogólnym przypadku to nowe zadanie nie jest równoważne zadaniu wyjściowemu. Będzie lak jedynie wówczas, gdy zmienna bilansująca sztucznego ograniczenia stanie się ponownie & zmienną bazową. Tak więc, jeżeli po zakończeniu stosowania dualnej metody simpleks okaże się, że zmienna bilansująca sztucznego ograniczenia nie jest zmienną bazową, ani nie da się jej wprowadzić do bazy (jako zmiennej bazowej w alternatywnym bazowym rozwiązaniu optymalnym i dopuszczalnym), oznacza to, że (zadanie ma funkcję celu nieograniczoną od dołu (w przypadku zadania minimalizacji) lub od góry (dla zadania maksymalizacji).

lAm U

Dualna metoda simpleks

"i

( } f    •%

a

/} ■

■ a) U f *' ‘    3 >• au

4Y

Przykład 1.18

¹ ■ ^

/ 'J ^v. :X'V ,

Stosując dualną metodę simpleks, należy rozwiązać zadanie rozpatrywane w przykładzie 1.1. Po wprowadzeniu zmiennych bilansujących x-,, x₄ i x₅ stwierdzamy, że są to zmienne bazowe pierwszego dopuszczalnego rozwiązania bazowego, które nie jest jednak optymalne. Do konstrukcji sztucznego ograniczenia wykorzystamy zmienne niebazowe x, i x₂. Otrzymujemy dodatkowy warunek ograniczający w postaci¹⁰:

x, +x₂ < 1600.

Dodajemy zmienną bilansującą x₆ i otrzymujemy warunek: x,+x₂+x₆= 1600,

który dołączamy do tablicy simpleksowej (tablica 1.26).

Tablica 1.26

cx —»	max	2	3	0	0	0	0
Baza	<-*»	X|	^X2	*3	x«	Xj	*6
*3	0	2	2	i	0	0	0	14
.	0	1	2	0	1	0	0	8
*5	0	4	0	0	0	1	0	16
	0	1	1	0	0	0	1	1 600
^cr	-Z/	2	3	0	0	0	0	0

Zmienną niebazową o największym współczynniku funkcji celu jest x₂, wprowadzamy więc ją do bazy na miejsce zmiennej x₆ i otrzymujemy (tablica 1.27):

Tablica 1.27

cx —	max	2	3	0	0	0	0
Baza	Cn	X\	*2		X*		x6
Jti	0	0	0	i	0	0	-2	-3 186
*4	0	-i	0	0	1	0	-2	-3 192
**	0	4	0	0	0	1	0	16
X2	3	1	1	0	0	0	1	1 600
^cr	-z;	-1	0	0	0	0	-3	4 800

Program DUAL.EXE jako najmniejszą wartość prawej slrony sztucznego ograniczenia dopuszcza dla tego zadania wartość 1600.