082 083 2

82 Programowanie liniowe

Będziemy znajdowali kolejne przedziały, posuwając się po osi liczbowej najpierw w prawo, a po wyczerpaniu wszystkich możliwości — w lewo od wybranej uprzednio wartości początkowej. W obliczeniach wykorzystamy prymalną metodę simpleks. Proponowany sposób postępowania zilustrujemy za pomocą przykładu.

Przykład 1.21

Rozpatrujemy ponownie problem programowania produkcji, opisany w przykładzie 1.1. Przyjmiemy teraz, że zyski jednostkowe zależą od pewnego parametru t w taki sposób, że zysk jednostkowy dla produktu P, jest równy 2 + 3f, natomiast zysk jednostkowy dla produktu P₂ wynosi 3 -t. Należy sprawdzić, jak wartość parametru 1 wpływa na rozwiązanie optymalne otrzymanego zadania. Zadanie zapisujemy następująco:

(2 + 3/jjt, + (3 - t)x2 —> max,

2x | + 2jc₂ ^ 14,

A[ + 2a₂ ^ 8,

4a_s < 16,

x„ x₂ S⁵ 0.

Wprowadzając zmienne bilansujące, otrzymujemy tablicę simpleksową (tablica 1.33):

Tablica 1.33

cx —>	max	2 + 3/	3-r	0	0	0	b
Baza	<+	X,	*2	x*	Aą	*s
A'3	0	2	2	1	0	0	14
a.,	0	1	2	0	1	0	8
X*	0	4	0	0	0	1	16
^cr	~Zf	2 + 3/	2-t	0	0	0	0

Przyjmujemy dowolną wartość początkową parametru. Najbardziej dogodną wartością jest r₀ = 0. Otrzymujemy następujące zadanie programowania liniowego:

2a-, + 3x₂ —» max,

2a, + 2a₂+a₃    =14,

X\ + 2a₂ + a₄ = 8,

4a, +    a₅=16,

A], a₂, a₃, a₄, a₅ > 0.

Rozwiązanie optymalne tego zadania jest następujące: a, =4, a, = 2, a₍ = 2, a₄ = 0, a₅ = 0.

Możemy zapisać ostatnią tablicę simpleksową dla tego rozwiązania, uwzględniając założenie, ż.e zarówno współczynniki funkcji celu, jak i współczynniki optymalności są zależne od t. Otrzymujemy (tablica 1.34):

Tablica 1.34

c (r) x	-> max	2 + 3/	3-t	0	0	0
Baza	^c»	x,	*7	*3	x.
Xy	0	0	0	1	-1	-0,25	2
*2	3-t	0	1	0	0,5	-0,125	2
	2 + 3/	I	0	0	0	0,25	4
^cj-	-Z;	0	0	0	-1,5+ 0,5/	-0,125-0,875/	14 + 10/

Interesuje nas, dla jakich wartości t rozwiązanie optymalne, otrzymane dla wartości początkowej t₀ = 0, pozostanie rozwiązaniem optymalnym. Będzie tak dopóty, dopóki wartości współczynników optymalności pozostaną niedodatnie. Trzeba więc rozwiązać układ nierówności:

-1,5 + 0,5/ <0,

-0,125 — 0,875f <0.

Otrzymujemy — 0,143 </<3. Oznacza to, że dla każdej wartości t z tego przedziału zmienne bazowe są takie same, jak dla wartości początkowej t_o = 0. Są nimi zmienne: x_t, x₂ i x₃. Dla wartości parametru t— 3 otrzymujemy następującą tablicę simpleksową (tablica 1.35):

Tablica 1.35

cx —>	max	11	0	0	0	0
Baza	C«		x2	-*•3	*4	•*5
*3	0	0	0	i	-1	-0,25	2
*2	0	0	1	0	0,5	-0,125	2
X,	11	1	0	0	0	0,25	4
cr	-z,	0	0	0	0	-2,75	44

Ponieważ współczynnik optymalności dla zmiennej niebazowej x_Ą jest równy 0, oznacza to, że zmienna ta wchodzi w skład alternatywnej bazy optymalnej. Zgodnie z przedstawionym uprzednio sposobem znajdowania optymalnych bazowych rozwiązań alternatywnych należy wykonać jeden krok prymalnej metody