042 043 2

42 U Programowanie liniowe

42 U Programowanie liniowe

Tablica 1.8

Baza	*1	x2	Xy	*4	'*5	b
X,	2	2	1	0	0	14
x4	1	2	0	1	0	8
X,	4	0	0	0	1	16

Zmiennymi bazowymi są x_}, x₄ i x_s. dlatego też kolumny odpowiadające tym zmiennym tworzą w dalszych iteracjach macierze odwrotne do macierzy A_B.

W drugiej iteracji odpowiedni fragment tablicy simpleksowej ma postać • (tablica 1.9):    f! ■

H

Tablica 1.9

Baza	*1	Xt	Xy	X4	*5	b
Xy	1	0	1	-1	0	6
*2	0,5	1	0	0,5	0	4
*5	4	0	0	0	1 /•	16

Zmiennymi bazowymi są x₃, x₄, x_s, dlatego też podmacierz macierzy A, odpowiadającą tej bazie odczytujemy z tablicy 1.8, wybierając kolumny odpowiadające zmiennym bazowym w takiej kolejności, w jakiem występują one w tablicy 1.9. Otrzymujemy:

	/l	Yf	. r		£ r - vc> r<t>
1	2	0		A /	ó,k/b:0^:u.; ?
0	2	0	. €* # C A .	00tf&W> O.OcOtf tfcCJCA-A
			.bej* t * 2	^VT )	tCJ O Vvy tę-; &V V < • 14
0	0	1	Y'i{y L^s i t M £rvi	X)

Macierz odwrotną A^-1 do macierzy A„ znajdujemy w tablicy 1.9. Tworzą ją kolumny odpowiadające zmiennym bazowym rozwiązania początkowego, czyli x₃, x₄ i x₅. Z tablicy 1.9 odczytujemy:

A„' =

0    0,5

0

0 .

0 0 1

r po    tfk C-. *

<1'jo 1 - tri C- 4 u.ff bO# . ( yfę Xt>,

Skfv--J

,,    f".> fJ

Łatwo przekonać się, że iloczyn macierzy A_B i A _B daje macierz jednostkową, gdyż:

	~1	2	0~		~1	-1	o~		1	0	o^-
Ab Ab-	0	2	0		0	0,5	0	=	0	1	0
	0	0	1		0	0	I		0	0	1

Korzystając ze wzoru (1.6), obliczamy:

		-1	0		14		6
XB =	0	0,5	0	•	8	=	4
	0	0	1		16		16

(/Jtwoiv--e z ^jX newscy

1.3.9. Pierwsza dopuszczalna postać bazowa

Chcąc rozpocząć obliczenia za pomocą metody simpleks, trzeba wyznaczyć pierwszą dopuszczalną postać bazową zadania. W poprzednio rozpatrywanym przykładzie otrzymaliśmy ją, wprowadzając zmienne bilansujące. Często jednak otrzymane zadanie nie ma jeszcze tej postaci. Wykonując przekształcenia elementarne, możemy wówczas starać się uzyskać pierwszą dopuszczalną postać bazową. Najczęściej nie jest to jednak wygodne, dlatego też do jej określenia wykorzystamy zmienne sztuczne.

Przykład 1.2

Zarząd firmy ustalił, że łączne rozmiary produkcji nie mogą być mniejsze od 3 jednostek. Wszystkie pozostałe założenia są takie same, jak w przykładzie 1,1. Otrzymujemy zatem zadanie:

/(je,, x₂) = 2x, +3*2 —> max, 2x_] +2x₂ ^ 14, x| + 2*2 < 8,

4z,    < 16,

*i +    3,

x, ^ 0, jc₂ > 0.

Ilustrację graficzną zbioru rozwiązań dopuszczalnych przedstawiono na rys. 1.12.