084 085 2
84 Programowanie liniowe
simpleks. Zmienną opuszczającą bazę jest x2. Otrzymujemy wówczas (tablica 1.36):
Tablica 1.36
|
c(/)x —» max |
2 + 3/ |
3-/ |
0 |
0 |
0 | ||
|
Baza |
CB |
-n |
X2 |
*3 |
x4 |
X5 | |
|
X.\ |
0 |
0 |
2 |
1 |
0 |
-0,5 |
6 |
|
X, |
0 |
0 |
2 |
0 |
1 |
-0,25 |
4 |
|
r, |
2 + 3/ |
1 |
0 |
0 |
0 |
0.25 |
4 |
|
cr |
-Z; |
0 |
3-/ |
0 |
0 |
-0,5-0,75/ |
8+12/ |
Zbadamy, dla jakich wartości t to nowe rozwiązanie pozostanie rozwiązaniem optymalnym. Ponownie rozwiążemy układ nierówności liniowych, wyznaczony przez wartości współczynników optymalności dla zmiennych niebazowych. Otrzymujemy:
3-fsSO,
- 0,5-0,75/<0.
Układ ten jest spełniony dla każdej wartości / takiej, żc z ^ 3.
Powróćmy teraz do wyjściowej wartości /„ = 0. Wiemy już, że rozwiązanie optymalne odpowiadające tej wartości t pozostanie optymalne dla -0,143 ^ f <3. Podstawiając za / wartość -0,143, otrzymujemy następującą tablicę simpleksową (tablica 1.37):
Tablica 1.37
|
cx —» |
max |
1,5712 |
3,143 |
0 |
0 |
0 |
b |
|
Baza |
C„ |
JC, |
■*2 |
•Ti |
Xą |
*5 | |
|
Jf.ł |
0 |
0 |
0 |
1 |
-I |
-0,25 |
2 |
|
*2 |
3,143 |
0 |
1 |
0 |
0,5 |
-0,125 |
2 |
|
X, |
1,571 |
1 |
0 |
0 |
0 |
0,25 |
4 |
|
CJ~ |
0 |
0 |
0 |
-1,571 |
0 |
12,57 |
Ponieważ wartość współczynnika optymalności zmiennej niebazowej jc5 jest równa 0, więc istnieje optymalne alternatywne rozwiązanie bazowe. Wykonamy ponownie jeden krok prymalnej metody simpleks. Zmienną wchodzącą do bazy jest x5, zmienną opuszczającą bazę jest x,. Otrzymujemy następującą tablicę simpleksową (tablica 1.38):
Tablica 1.38
|
C(f)x |
-» max |
2 + 31 |
3 — 1 |
0 |
0 |
0 |
i) |
|
Ba?.a |
C« |
«*l |
x2 |
X, |
Xą | ||
|
0 |
1 |
0 |
1 |
-1 |
0 |
6 | |
|
x2 |
3-t |
0,5 |
1 |
0 |
0,5 |
0 |
4 |
|
X* |
0 |
4 |
0 |
0 |
0 |
1 |
16 |
|
CJ- |
-Zr |
0,5 + 3,5/ |
0 |
0 |
-1,5+ 0,5/ |
0 |
12-4/ |
oraz rozwiązanie bazowe: jc,=0, x2 = 4. jc3 = 6, x4 = 0, x5 = 16. Rozwiązanie to pozostaje rozwiązaniem optymalnym wówczas, gdy spełniony jest układ nierówności:
0,5 + 3,5r<0,
-1,5 + 0,5r < 0.
Układ ten jest spełniony dla każdej wartości t <-0,143.
Reasumując, podamy rozwiązanie optymalne w zależności od wartości parametru i:
(I) Dla r<-0,143 mamy:
x, = 0, x2 = 4, x3 = 6, x4 = 0, xs= 16.
(II) Dla / = — 0.143 rozwiązaniami są punkty leżące na odcinku między rozwiązaniami (I) a (III).
(III) Dla -0,0143 </<3 mamy:
x, = 4, x2 - 2, x2 = 2, x4 = 0, jc5 = 0.
(IV) Dla t-3 rozwiązaniami są punkty leżące na odcinku między rozwiązaniami (111) a (V).
(V) Dla 3 mamy:
x,=4, x2 = 0, jc3 = 6, x4 = 4, x5 = 0.
Rozwiązanie zadania możemy zilustrować graficznie. Ponieważ sparamet-ryzowana została jedynie funkcja celu, zbiór rozwiązań dopuszczalnych pozostaje bez zmian. Dla początkowej wartości parametru r0 = 0 funkcja celu ma postać:
/i(z,, x2) = 2xl+3x2,
a rozwiązaniem optymalnym jest wierzchołek B (rys. 1.20). Dla wartości parametru t-3 funkcja celu ma postać: /->(•*!> x2)= lLc,.
Wyszukiwarka
Podobne podstrony:
DSC84 (3) Przykład programowania liniowego — zagadnienia dualne zagadnienie prymame f(xx,x2) = lx}
2 Postać bazowa problemu programowania liniowego Definicja 9 Mówimy, że problem (l)-(3) jest problem
038 039 2 38 Programowanie liniowe ograniczających miała postać: ~o~ 1 . o W tym celu wiersz drugi w
094 095 2 94 Programowanie liniowe (III) Dla i-0,286 mamy: x, =4,571, x2= 1,143, X
Rozdział 1. Programowanie liniowe Preferowanym formatem wprowadzania danych jest zwykły skoroszyt,
Zagadnienie programowania liniowego Oznaczenia: x, - ilość wyprodukowanych wieszaków STANDARD x2 -
Twierdzenia programów liniowych 1) Zbiór rozwiązań dopuszczalnych MPL jest zbiorem
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
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
032 033 2 32 Programowanie liniowe W rozpatrywanym przez nas zadaniu występuje 5 zmiennych (decyzyjn
050 051 2 50 Programowanie liniowe Pierwsza tablica simpleksowa ma postać (tablica 1.14): Tablica 1.
078 079 2 78 Programowanie liniowe Wykorzystując dualną metodę simpleks, wykonujemy kolejne iteracje
1.2. Rozwiązywanie zadań programowania liniowego metodą geometryczną Dla każdej zmiennej decyzyjnej
Klasyfikacja metod optymalizacji programowanie liniowe [metoda Simplex1 c^jjrogramowanie nieliniowej
ZmienneModel matematyczny ZPL - zadanie programowania liniowego f(x) - CjXi + c2x2 —> max
więcej podobnych podstron