070 071 2

70

r

Programowanie liniowe

15jy, + 18y₂ + 5y₃ —> min,

y. + ^2 - 2y₃ > 3.

-2y, + 2y₂ - y₃ < 2,

3yi - y₂ + >3 = 4,

y, > 0, y₂ < 0, _y₃ — dowolne.

W podobny sposób można sformułować zadanie dualne w przypadku dowolnej liczby ograniczeń i zmiennych danego typu. Tak utworzone zadania dualne mają takie same własności jak te, które omówiliśmy w niniejszym podrozdziale.

i:

j:

:

1.6.2. Ceny dualne i analiza wrażliwości w kształtowaniu optymalnych planów produkcji

Znajomość cen dualnych wraz z analizą wrażliwości pozwala na przewidywanie skutków zmian zasobów środków produkcji oraz konsekwencji zmian zysków jednostkowych.

Przykład 1.15

Zaistniały możliwości zwiększenia dostępności jednego ze środków produkcji:

S„ S₂ lub S_v Która z nich jest najkorzystniejsza przy założeniu, że będziemy wytwarzać zarówno produkt P_u jak i P₂?

Wymóg wytwarzania obu produktów na poziomie niezerowym powoduje, że interesuje nas rozwiązanie optymalne, w którym zmiennymi bazowymi są zmienne jc, i x₂. Rozwiązanie przykładu 1.1 wskazuje na to, że trzecią zmienną bazową \ jest *3.

Aktualnie środek S, dostępny jest w ilości />, = 14 jednostek. Przedział j zmienności dla h_u wyznaczony w przykładzie 1.11 to [12, oo). Dla wartości b_t = 14 \ (przy niezmienionych wielkościach b₂ = 8 i b₃ = 16) mamy x, = 4, x₂ = 2, x₃ = 14 + J - 12 = 2. Obliczona w przykładzie 1.13 cena dualna _y, = 0 wskazuje na to, że zwiększenie dostępności środka 5, nie zwiększy zysku rozpatrywanego zakładu. Środek S₂ dostępny jest w ilości b₂ - 8 jednostek. Przedział zmienności dla b₂, wyznaczony w przykładzie 1.11 to [4, 10]. W przedziale tym cena dualna y₂= 1,5, wyznaczona w przykładzie 1.13 określa zmianę zysku A/ zgodnie z zależnością:

A/= y₂Ab₂,

gdzie Ab, oznacza zmianę dostępnego zasobu (wyjściowy poziom zasobu to b₂ - 8). Mamy Ab₂ = 10-8 = 2. Wykorzystujemy obliczoną w przykładzie 1.13 wartość ceny dualnej y₂ = 1,5 i otrzymujemy:

A/= 1,5 ■ 2 = 3.

Dualizm w programowaniu liniowym

71

Aby uzyskać zysk na poziomie 14 + 3=17 jednostek, należy wykorzystać środek b₂ w ilości 10 jednostek.

Środek S₃ dostępny jest w ilości b_} = 16 jednostek. Przedział zmienności dla b), wyznaczony w przykładzie 1.11 to [12. 24], W przedziale tym mamy cenę dualną y? = 0,125. Ponieważ wyjściowy poziom zasobu S₃ to 16 jednostek, stąd

= 24 - 16 = 8 oraz

A/=0,125-8= 1.

Przeprowadzone obliczenia wskazują na to, że dla rozwiązania bazowego o zmiennych bazowych x,, x₂ i x, zwiększenie limitu środka S, nie wpływa na wielkość zysku, natomiast maksymalne możliwe, wynikające z analizy wrażliwości zwiększenie limitu środka S, lub S₂ pozwoli na zwiększenie zysku odpowiednio o 3 jednostki lub l jednostkę. Wynika stąd, że korzystniejsze jest zwiększenie limitu środka S₂ do poziomu 10 jednostek.

Przykład ł.16

Rozpatrujemy zagadnienie programowania produkcji, opisane w przykładzie 1.4 (jednostkowy zysk dla produktu P₄ wynosi teraz c₂ = 4). Zaistniała ponownie możliwość zwiększenia dostępności jednego ze środków produkcji S,, S₂ lub S_y Którą z nich wybrać, jeżeli chcemy wytwarzać zarówno produkt P,, jak i P₂?

Korzystając z tablicy 1.16, znajdujemy macierz odwrotną do macierzy bazowej. Mamy:

1    -1    -0,25

Ar¹ =

0,5 -0,125 . 0    0,25

Jest ona taka sama, jak w przykładzie 1.11, stąd mamy /?, e [12, oo], b₂ e [4, 10], 6,6 10, 24]. Wartości cen dualnych są na podstawie Twierdzenia 1.4 równe:

1    -1    -0,25

y = [0 4 2] •

= [0 2 01.

0    0,5 -0,125

0    0    0,25

Widać stąd, że jedynie zwiększenie limitu środka S₂ skutkuje zwiększeniem zysku. Mamy:

A/= 2-2 = 4.