038 039 2

38 Programowanie liniowe

ograniczających miała postać:

~o~

1 .

W tym celu wiersz drugi w tablicy 1.3 dzielimy przez 2. Otrzymujemy: x₂ x₃ x₄ x_s b

2 0 i 0 8 |: 2

= “05 i 0 05 Ó 4~

Wynik zapisujemy w tablicy 1.4.

Tablica 1.4

cx	max	2	3	0	0	0	\|)
Baza	C_B		x₂	xJ	*4	X,
*3	0		0
*2	3	0.5	1	0	0,5	0	4
X,	0		0

Z kolei ten przekształcony wiersz mnożymy przez. (-2) i dodajemy do wiersza pierwszego z tablicy 1.3. Otrzymujemy:

xi x₂ x₄ x_s b

—2 o ~\ o

+ 2 2 1 O O 14

= ^—i ó i ~i ó 6

Wynik zapisujemy w tablicy 1.5.

Tablica 1.5

cx —> max		2	3	0	0	0	b
Baza	^CB		*2	Xy	*4	*5
■*)	0	1	0	1	-1	0	6
X₂	3	0,5	1	0,5	0	4	4
Xi	0		0

Trzeci wiersz tablicy i.3 nie wymaga żadnych przekształceń, więc przepisujemy go bez zmian do tablicy 1.6. Z kolei doliczamy wskaźniki optymalności i wpisujemy je do ostatniego wiersza tej tablicy.

Tablica 1.6

cx —	max	2	3	0	0	0
Baza	^CB		Xl	X}	x_t	x>
X}	0	1	0	1	-1	0	6
X2	3	0,5	1	0	0,5	0	4
Xs	0	4	0	0	0	l	16
cr	~Xj	0,5	0	0	-1,5	0	12

1.3.6. Kolejne iteracje

Iteracja 2

Zgodnie z omówionym wcześniej kryterium optymalności otrzymane rozwiązanie nie jest optymalne, ponieważ wartość współczynnika optymalności dla zmiennej x, jest dodatnia. Jednocześnie kryterium wejścia metody simpleks wskazuje, że istnieje tylko jedna możliwość wprowadzenia do bazy nowej zmiennej, aby poprawić wartość funkcji celu w nowym rozwiązaniu. Tą zmienną jest x„ a przyrost funkcji celu odpowiadający jednostce wprowadzonej zmiennej ze, wynosi 0,5. Stosując kryterium wyjścia, obliczamy odpowiednie ilorazy, otrzymując:

dla wiersza 1: 6:1=6,

dla wiersza 2: 4: (0,5) = 8,

dla wiersza 3: 16:4 = 4.

Minimalną wartość otrzymujemy dla wiersza 3, co wskazuje na to, że z bazy należy usunąć zmienną x₅. Po wykonaniu odpowiednich operacji elementarnych i obliczeniu współczynników optymalności otrzymujemy (tablica 1.7):

Tablica 1.7

cx —>	max	2	3	0	0	0	b
Baza	<-•»		*2	X*	x_t		b
*»	0	0	0	i	-1	-0,25	2
x₂	3	0	1	0	0,5	-0,125	2
x,	2	1	0	0	0	0,25	4
Cj-	-z,'	0	0	0	-1,5	-0,125	14