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 P2 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 | + 2jc2 ^ 14,
A[ + 2a2 ^ 8,
4as < 16,
x„ x2 S5 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 r0 = 0. Otrzymujemy następujące zadanie programowania liniowego:
2a-, + 3x2 —» max,
2a, + 2a2+a3 =14,
X\ + 2a2 + a4 = 8,
4a, + a5=16,
A], a2, a3, a4, a5 > 0.
Rozwiązanie optymalne tego zadania jest następujące: a, =4, a, = 2, a( = 2, a4 = 0, a5 = 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 t0 = 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 to = 0. Są nimi zmienne: xt, x2 i x3. 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
Wyszukiwarka
Podobne podstrony:
Koszalin 2006 [BADANIA OPERACYJNE - PROGRAMOWANIE LINIOWE] Idziemy do kolejnej wolnej komórki, wpisu
[BADANIA OPERACYJNE - PROGRAMOWANIE LINIOWE] Koszalin 2006 Kolejny krok to doprowadzenie do postaci
082 083 82 Anna Kamińska. Artur Gas Zadanie 6 Określić taką wartość współczynnika wzmocnienia k(1 re
082 083 82 Anna Kamińska. Artur Gas Zadanie 6 Określić taką wartość współczynnika wzmocnienia k,, re
078 079 2 78 Programowanie liniowe Wykorzystując dualną metodę simpleks, wykonujemy kolejne iteracje
Po podaniu nazwy programu przez użytkownika, w pierwszej kolejności przeszukiwany będzie dysk
image 083 Jednorodny szyk liniowy anten 83 Szerokość wiązki głównej Na wstępie rozważymy szerokość w
cyjnego punktu stosowanego podczas pisania programów robota). Po napisaniu programu nie będzie potrz
DOOATEK A ZASADA DUALNOŚCI Wełny pod uwagę zodonle programowanie liniowego (pi t r-w o t n o); Należ
82 Programując retencję w zlewni Drwęcy należy mieć również na uwadze potrzeby województwa kujawsko
IMG2 083 (2) 82 4. Interpretacja wykresów układów równowagi b) Rys. 4.28. Układ mieszaniny składnik
instalacje160 7. ZASTOSOWANIA SILNIKÓW SKOKOWYCH 200 a = 1 13 "32 stopnia i będzie przeszukiwa
Instukcja odblokowania nieużywanej pamięci RAM Po uruchomieniu programu kliknij jak na kolejnych obr
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
(ruchy wykonywane pomiędzy kolejnymi zabiegami) stosuje się stoły podziałowe, obrotowe i liniowe,
więcej podobnych podstron