070 071 2
70
r
Programowanie liniowe
15jy, + 18y2 + 5y3 —> min,
y. + ^2 - 2y3 > 3.
-2y, + 2y2 - y3 < 2,
3yi - y2 + >3 = 4,
y, > 0, y2 < 0, _y3 — 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„ S2 lub Sv Która z nich jest najkorzystniejsza przy założeniu, że będziemy wytwarzać zarówno produkt Pu jak i P2?
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 x2. 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 hu wyznaczony w przykładzie 1.11 to [12, oo). Dla wartości bt = 14 \ (przy niezmienionych wielkościach b2 = 8 i b3 = 16) mamy x, = 4, x2 = 2, x3 = 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 S2 dostępny jest w ilości b2 - 8 jednostek. Przedział zmienności dla b2, wyznaczony w przykładzie 1.11 to [4, 10]. W przedziale tym cena dualna y2= 1,5, wyznaczona w przykładzie 1.13 określa zmianę zysku A/ zgodnie z zależnością:
A/= y2Ab2,
gdzie Ab, oznacza zmianę dostępnego zasobu (wyjściowy poziom zasobu to b2 - 8). Mamy Ab2 = 10-8 = 2. Wykorzystujemy obliczoną w przykładzie 1.13 wartość ceny dualnej y2 = 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 b2 w ilości 10 jednostek.
Środek S3 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 S3 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,, x2 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 S2 pozwoli na zwiększenie zysku odpowiednio o 3 jednostki lub l jednostkę. Wynika stąd, że korzystniejsze jest zwiększenie limitu środka S2 do poziomu 10 jednostek.
Przykład ł.16
Rozpatrujemy zagadnienie programowania produkcji, opisane w przykładzie 1.4 (jednostkowy zysk dla produktu P4 wynosi teraz c2 = 4). Zaistniała ponownie możliwość zwiększenia dostępności jednego ze środków produkcji S,, S2 lub Sy Którą z nich wybrać, jeżeli chcemy wytwarzać zarówno produkt P,, jak i P2?
Korzystając z tablicy 1.16, znajdujemy macierz odwrotną do macierzy bazowej. Mamy:
Ar1 =
Jest ona taka sama, jak w przykładzie 1.11, stąd mamy /?, e [12, oo], b2 e [4, 10], 6,6 10, 24]. Wartości cen dualnych są na podstawie Twierdzenia 1.4 równe:
y = [0 4 2] •
= [0 2 01.
0 0,5 -0,125
Widać stąd, że jedynie zwiększenie limitu środka S2 skutkuje zwiększeniem zysku. Mamy:
A/= 2-2 = 4.
Wyszukiwarka
Podobne podstrony:
070 071 70 Przykład. 3.3 Narysować graf układu sekwencyjnego Moore a, obliczającego prędkość na pod
070 071 70 Przykład. 3.3 Narysować graf układu sekwencyjnego Moore a, obliczającego prędkość na pods
DOOATEK A ZASADA DUALNOŚCI Wełny pod uwagę zodonle programowanie liniowego (pi t r-w o t n o); Należ
str 070 071 (3) 46. KTO PIERWSZY U NAS? Literaturę ludową nazywamy często wymiennie literaturą trady
Slajd35 4 Metoda simpleks Uniwersalną metodą rozwiązywania programów liniowych jest algorytm simplek
Slajd40 3 Metoda simpleks Najogólniej ujmując, wyznaczenie rozwiązania zadania programowania liniowe
Slajd49 4 Metoda simpleks Jak już wspomniano, program liniowy może mieć więcej niż jedno rozwiązanie
10. Geometryczne przedstawienie modeli i rozwiązań zadań programowania liniowego Przy pomocy metody
2 Postać bazowa problemu programowania liniowego Definicja 9 Mówimy, że problem (l)-(3) jest problem
Wielokryterialne programowanie liniowe. 3. Przykłady zastosowań teorii gier i programowania
Postaci i przykłady zadań programowania liniowego. Metoda geometryczna rozwiązywania zadań programow
Zad. 20. programowanie liniowe Znajdź metodą simpleks maksimum liniowej funkcji celu F(x) przy linio
2012-09-30Model programowania liniowego Postać ogólna + Symbol* Xj j-ta zmienna
Dane jest zadanie programowania liniowego przy nieujemnych zmiennych decyzyjnych: Xi - X2 -> max
wyklad1e Matematyczny model problemu optymalnego wyboru jest zadaniem programowania liniowego,
więcej podobnych podstron