Sprowadzenie modelu
do postaci bazowej
Sprowadzenie modelu do postaci bazowej
Przykład 4.
Model matematyczny z Przykładu 1. sprowadzić do postaci
bazowej.
2
Sprowadzenie modelu do postaci bazowej
9x1 + 7x2 d" 63
Ograniczenie
Aby otrzymać ograniczenie w postaci równania
wprowadzamy dodatkowÄ… zmiennÄ… do ograniczenia:
9x1 + 7x2 + x3 = 63
x3 zmienna bilansujÄ…ca
Zmienna x3 określa ilość środka S1 jaki nie zostanie
wykorzystany w procesie produkcyjnym
3
Sprowadzenie modelu do postaci bazowej
9x1 + 7x2 + x3 = 63
x3 = 63 - 9x1 - 7x2
Gdyby przyjąć: x1=0 i x2=0:
x3 = 63 e" 0
Zmienna x3 spełnia postulat nieujemności.
4
Sprowadzenie modelu do postaci bazowej
x1 + x2 d" 8
Ograniczenie
Aby otrzymać ograniczenie w postaci równania
wprowadzamy dodatkowÄ… zmiennÄ… do ograniczenia
(analogicznie jak dla pierwszego ograniczenia):
x1 + x2 + x4 = 8
x4 zmienna bilansujÄ…ca
Zmienna x4 określa ilość środka S2 jaki nie zostanie
wykorzystany w procesie produkcyjnym
Dla x1=0 i x2=0: x4 = 8 e" 0
5
Sprowadzenie modelu do postaci bazowej
3x1 + 2x2 e" 6
Ograniczenie
Aby otrzymać ograniczenie w postaci równania
wprowadzamy dodatkowÄ… zmiennÄ… do ograniczenia:
3x1 + 2x2 - x5 = 6
x5 zmienna bilansujÄ…ca
Dla x1=0 i x2=0: x5 = -6 < 0
6
Sprowadzenie modelu do postaci bazowej
W postaci bazowej, w ka\dym ograniczeniu musi
znajdować się jedna zmienna, która po wyzerowaniu
wszystkich pozostałych zmiennych w ograniczeniu jest
nieujemna.
Wprowadzamy kolejnÄ… zmiennÄ…:
3x1 + 2x2 - x5 + x6 = 6
x6 zmienna sztuczna
Dla x1=0, x2=0 oraz x5=0: x6 = 6 e" 0
7
Sprowadzenie modelu do postaci bazowej
RozwiÄ…zanie zadania po wprowadzeniu zmiennej sztucznej
nie jest równowa\ne z rozwiązaniem zadania
poczÄ…tkowego.
Byłoby równowa\ne tylko wtedy, gdyby w rozwiązaniu
optymalnym zmienna sztuczna miała wartość zero.
8
Sprowadzenie modelu do postaci bazowej
Aby zapewnić x6=0 w rozwiązaniu optymalnym, ka\dą
zmiennÄ… sztucznÄ… wprowadza siÄ™ do funkcji celu.
Współczynnik przy zmiennej sztucznej w funkcji celu
dobiera się tak, aby niezerowa wartość tej zmiennej mocno
pogarszała wartość funkcji celu.
Z(x1, x2, x6) = 6x1 + 5x2 + Mx6 MAX
M = -1000
9
Sprowadzenie modelu do postaci bazowej
Czy zmienne bilansujące nale\y uwzględnić w funkcji celu?
Tak.
Z jakimi współczynnikami?
Wszystkie współczynniki przy zmiennych bilansujących w
funkcji celu są równe zero.
Z(x1, x2, x3, x4, x5, x6) = 6x1 + 5x2 + 0x3 + 0x4 + 0x5 -1000x6 MAX
10
Sprowadzenie modelu do postaci bazowej
Postać bazowa zadania z Przykładu 1:
FC:
Z(x1, x2, x3, x4, x5, x6) = 6x1 + 5x2 + 0x3 + 0x4 + 0x5 -1000x6 MAX
O:
9x1 + 7x2 + x3 = 63
x1 + x2 + x4 = 8
3x1 + 2x2 - x5 + x6 = 6
WB:
x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0, x5 e" 0, x6 e" 0
11
Sprowadzenie modelu do postaci bazowej
Sprowadzenie do postaci bazowej ograniczenia typu:
3x1 + 5x2 = 4
Wprowadzamy zmiennÄ… sztucznÄ…:
3x1 + 5x2 + x3 = 4
Nale\y ją uwzględnić w funkcji celu w podany poprzednio
sposób, czyli tak, aby jej niezerowa wartość mocno
pogarszała wartość funkcji celu.
12
Sprowadzenie modelu do postaci bazowej
Postać bazowa:
Wszystkie ograniczenia w postaci równań
W ka\dym ograniczeniu znajduje się zmienna, która po
wyzerowaniu pozostałych zmiennych ma wartość
nieujemnÄ…
Współczynnik przy tej zmiennej ma wartość 1
Wprowadzone zmienne bilansujÄ…ce wprowadza siÄ™ do
funkcji celu z zerowymi współczynnikami
Wprowadzone zmienne sztuczne uwzględnia się w
funkcji celu ze współczynnikami mocno pogarszającymi
jej wartość
13
METODA SIMPLEX
Metoda simplex
Przykład 5.
Rozwiązać zadanie z Przykładu 1. metodą simplex.
15
Metoda simplex
Tablica simplex:
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
16
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000
= -3000
z1 = 0Å"9 + 0Å"1+ (-1000) Å"3
17
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000
= -2000
z2 = 0Å"7 + 0Å"1+ (-1000) Å" 2
18
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0
= 0
z3 = 0Å"1+ 0Å" 0 + (-1000) Å" 0
19
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0
= 0
z4 = 0Å"0 + 0Å"1+ (-1000) Å"0
20
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000
=1000
z5 = 0Å"0 + 0 Å" 0 + (-1000) Å" (-1)
21
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
= -1000
z6 = 0Å" 0 + 0 Å"0 + (-1000) Å"1
22
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006
= 3006
c1 - z1 = 6 - (-3000)
23
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005
= 2005
c2 - z2 = 5 - (-2000)
24
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0
= 0
c3 - z3 = 0 - 0
25
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0 0
= 0
c4 - z4 = 0 - 0
26
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0 0 -1000
= -1000
c5 - z5 = 0 -1000
27
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0 0 -1000 0
= 0
c6 - z6 = -1000 - (-1000)
28
Metoda simplex
- wskazniki optymalności
cj - zj
Dla zmiennych bazowych wskazniki optymalności zawsze
są równe 0.
29
Metoda simplex
Kryterium optymalności:
Rozwiązanie jest optymalne, je\eli wartości wszystkich
wskazników optymalności są niedodatnie.
RozwiÄ…zanie w bazie [x3, x4, x6] nie jest rozwiÄ…zaniem optymalnym.
Nale\y przejść do następnej bazy
30
Metoda simplex
Kryterium wejścia do bazy:
Do bazy wchodzi zmienna, która ma największą wartość
wskaznika optymalności.
Je\eli największa wartość wskaznika optymalności
odpowiada więcej ni\ jednaj zmiennej, wybieramy zmienną
o najni\szym indeksie.
W przykładzie kryterium wejścia spełnia zmienna x1.
31
Metoda simplex
Kryterium wyjścia z bazy:
Obliczamy ilorazy wyrazów wolnych (kolumna bi) przez
elementy (tylko dodatnie) kolumny zmiennej wchodzÄ…cej do
bazy.
Bazę opuszcza ta zmienna, dla której obliczony iloraz jest
najmniejszy.
Je\eli najmniejsza wartość ilorazu występuje dla więcej ni\
jednej zmiennej, to jako zmiennÄ… opuszczajÄ…cÄ… bazÄ™
mo\na wybrać dowolną z nich.
32
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 9 7 1 0 0 0 63
x4 0 1 1 0 1 0 0 8
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0 0 -1000 0
x3 : 63/9 = 7 x4 : 8/1 = 8 x6 : 6/ 3 = 2
W przykładzie kryterium wyjścia spełnia zmienna x6.
33
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 0 1 1 0 3 -3 45
x4 0 0 1/3 0 1 1/3 -1/3 6
x1 6 1 2/3 0 0 -1/3 1/3 2
zj 6 4 0 0 -2 2
cj - zj 0 1 0 0 2 -1002
RozwiÄ…zanie w bazie [x3, x4, x1] nie jest rozwiÄ…zaniem optymalnym.
34
Metoda simplex
x5
Do bazy wchodzi zmienna:
Ilorazy:
x3 : 45/3 =15
x4 : 6/(1/ 3) =18
ujemny współczynnik nie liczymy ilorazu
x1 : -
Z bazy wychodzi zmienna:
x3
35
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x5 0 0 1/3 1/3 0 1 -1 15
x4 0 0 2/9 -1/9 1 0 0 1
x1 6 1 7/9 1/9 0 0 0 7
zj 6 14/3 2/3 0 0 0
cj - zj 0 0 0
1/3 -2/3 -1000
RozwiÄ…zanie w bazie [x5, x4, x1] nie jest rozwiÄ…zaniem optymalnym.
36
Metoda simplex
x2
Do bazy wchodzi zmienna:
Ilorazy:
x5 : 15/(1/ 3) = 45
x4 : 1/(2 / 9) = 4.5
x1 : 7 /(7 / 9) = 9
Z bazy wychodzi zmienna:
x4
37
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x5 0 0 0 1/2 -3/2 1 -1 27/2
x2 5 0 1 -1/2 9/2 0 0 9/2
x1 6 1 0 1/2 -7/2 0 0 7/2
zj 6 5 1/2 3/2 0 0
cj - zj
0 0 -1/2 -3/2 0 -1000
RozwiÄ…zanie w bazie [x5, x2, x1] jest rozwiÄ…zaniem optymalnym.
38
Metoda simplex
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x5 0 0 0 1/2 -3/2 1 -1 27/2
x2 5 0 1 -1/2 9/2 0 0 9/2
x1 6 1 0 1/2 -7/2 0 0 7/2
zj 6 5 1/2 3/2 0 0
cj - zj
0 0 -1/2 -3/2 0 -1000
Zmienne bazowe:
x5 = 27 / 2 x2 = 9/ 2 x1 = 7 / 2
Zmienne niebazowe:
x3 = 0 x4 = 0 x6 = 0
39
Metoda simplex
RozwiÄ…zanie:
x1 = 3.5 x2 = 4.5 x3 = 0 x4 = 0 x5 =13.5 x6 = 0
Funkcja celu:
Z(x1, x2, x3, x4, x5, x6) = 43.5
40
Ró\nice w algorytmie
metody simplex na
MAX i MIN
Ró\nice w algorytmie metody simplex na MAX i MIN
Kryterium wejścia
MAX:
Zmienna z największą wartością wskaznika optymalności
MIN:
Zmienna z najmniejszą wartością wskaznika optymalności
42
Ró\nice w algorytmie metody simplex na MAX i MIN
Kryterium wyjścia
MAX:
Zmienna, dla której iloraz elementu z wektora wyrazów wolnych
przez współczynnik z kolumny zmiennej wchodzącej do bazy
ma najmniejszą wartość.
MIN:
Identycznie jak w zadaniu na MAX.
43
Ró\nice w algorytmie metody simplex na MAX i MIN
RozwiÄ…zanie optymalne
MAX:
Wszystkie wskazniki optymalności muszą być niedodatnie
MIN:
Wszystkie wskazniki optymalności muszą być nieujemne.
44
Postępowanie, gdy zmienne
nie spełniają warunków
nieujemności
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
FC : Z(x) = 3x1 + 6x2 - 4x3 MAX
O : 3x1 - 5x2 - 2x3 e" -6
2x1 - 3x2 + 7x3 e"12
4x1 + 6x2 - 3x3 = 5
WB : x1 e" 0 x2 " R x3 d" 0
46
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
x2 " R
Zmienną x2 zastępujemy ró\nicą dwóch zmiennych
nieujemnych:
* * * *
x2 = x2 - x2*, x2 e" 0, x2* e" 0
47
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
x3 d" 0
Zmienną x3 zastępujemy ró\nicą dwóch zmiennych
nieujemnych:
* * * *
x3 = x3 - x3*, x3 e" 0, x3* e" 0
48
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
* * * * * * * *
FC : Z(x1, x2, x2*, x3, x3*) = 3x1 + 6(x2 - x2*) - 4(x3 - x3*) MAX
* * * *
O : 3x1 - 5(x2 - x2*) - 2(x3 - x3*) e" -6
* * * *
2x1 - 3(x2 - x2*) + 7(x3 - x3*) e"12
* * * *
4x1 + 6(x2 - x2*) - 3(x3 - x3*) = 5
* * * *
WB : x1 e" 0 x2 e" 0 x2* e" 0 x3 e" 0 x3* e" 0
49
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
Zmieniamy numery zmiennych:
Ć Ć Ć Ć Ć Ć Ć Ć Ć Ć
FC : Z(x1, x2, x3, x4, x5) = 3x1 + 6x2 - 6x3 - 4x4 + 4x5 MAX
Ć Ć Ć Ć Ć
O : 3x1 - 5x2 + 5x3 - 2x4 + 2x5 e" -6
Ć Ć Ć Ć Ć
2x1 - 3x2 + 3x3 + 7x4 - 7x5 e"12
Ć Ć Ć Ć Ć
4x1 + 6x2 - 6x3 - 3x4 + 3x5 = 5
Ć
WB : xj e" 0, j =1,2,3,4,5
50
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
Ograniczenia, w których wyraz wolny jest wartością ujemną
mno\ymy przez -1 (tutaj ograniczenie pierwsze):
Ć Ć Ć Ć Ć Ć Ć Ć Ć Ć
FC : Z(x1, x2, x3, x4, x5) = 3x1 + 6x2 - 6x3 - 4x4 + 4x5 MAX
Ć Ć Ć Ć Ć
O : -3x1 + 5x2 - 5x3 + 2x4 - 2x5 d" 6
Ć Ć Ć Ć Ć
2x1 - 3x2 + 3x3 + 7x4 - 7x5 e"12
Ć Ć Ć Ć Ć
4x1 + 6x2 - 6x3 - 3x4 + 3x5 = 5
Ć
WB : xj e" 0, j =1,2,3,4,5
51
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
Dalsze postępowanie identyczne jak przy sprowadzaniu do
postaci bazowej.
52
Szczególne przypadki rozwiązań
Szczególne przypadki rozwiązań
Zadanie sprzeczne
Z(x1, x2) = 6x1 + 5x2 MAX
x1 + x2 e" 8
3x1 + 2x2 d" 6
x1, x2 e" 0
W postaci bazowej:
Z(x1, x2, x3, x4, x5) = 6x1 + 5x2 -1000x4 MAX
x1 + x2 - x3 + x4 = 8
3x1 + 2x2 + x5 = 6
x1, x2, x3, x4, x5 e" 0
54
Szczególne przypadki rozwiązań
55
Szczególne przypadki rozwiązań
Zadanie sprzeczne:
" Nie ma rozwiązań dopuszczalnych
Objawy w metodzie simplex:
W rozwiÄ…zaniu optymalnym, zmienna sztuczna (w tym
przykładzie x4) będzie miała wartość niezerową (czyli będzie
w bazie).
56
Szczególne przypadki rozwiązań
Alternatywne rozwiÄ…zania optymalne
Z(x1, x2) = 2x1 + 2x2 MAX
x1 + x2 d" 8
3x1 + 2x2 e" 6
x1, x2 e" 0
W postaci bazowej:
Z(x1, x2, x3, x4, x5) = 2x1 + 2x2 -1000x5 MAX
x1 + x2 + x3 = 8
3x1 + 2x2 - x4 + x5 = 6
x1, x2, x3, x4, x5 e" 0
57
Szczególne przypadki rozwiązań
C(0,8) : Z(0,8) =16
D(8,0) : Z(8,0) =16
58
Szczególne przypadki rozwiązań
Alternatywne rozwiÄ…zania optymalne:
" Ka\dy punkt odcinka CD jest rozwiÄ…zaniem optymalnym
odpowiada alternatywnemu, optymalnemu rozwiÄ…zaniu
" Mo\e się zdarzyć, \e zadanie ma nieskończenie wiele
rozwiązań optymalnych
Objawy w metodzie simplex:
W rozwiązaniu optymalnym, zerowe wartości wskazników
optymalności dla zmiennych niebazowych.
Rozwiązania optymalne mo\na zidentyfikować przechodząc do
kolejnych baz.
59
Szczególne przypadki rozwiązań
Nieograniczona funkcja celu
Z(x1, x2) = 2x1 + 3x2 MAX
3x1 + 2x2 e" 6
x1 d" 7
x1, x2 e" 0
W postaci bazowej:
Z(x1, x2, x3, x4, x5) = 2x1 + 3x2 -1000x4 MAX
x1 + x2 - x3 + x4 = 6
x1 + x5 = 7
x1, x2, x3, x4, x5 e" 0
60
Szczególne przypadki rozwiązań
61
Szczególne przypadki rozwiązań
W tym zadaniu:
" Zbiór rozwiązań jest nieograniczony
" Funkcja celu jest nieograniczona od góry
Objawy w metodzie simplex:
W tablicy simplex kolumna zmiennej wchodzÄ…cej do bazy ma
wszystkie elementy niedodatnie.
62
Szczególne przypadki rozwiązań
Czy funkcja celu mo\e być nieograniczona od dołu?
Nie, poniewa\ wymagana jest nieujemność zmiennych
Czy, pomimo tego \e zbiór rozwiązań dopuszczalnych jest
nieograniczony mo\e istnieć dokładne rozwiązanie optymalne?
Mo\e, gdy zadanie jest zadaniem na MIN.
63
Szczególne przypadki rozwiązań
Z(x1, x2) = 2x1 + 3x2 MIN
3x1 + 2x2 e" 6
x1 d" 7
x1, x2 e" 0
Z poprzedniego rysunku:
MIN
A(2,0) : Z(2,0) = 4
B(0,3) : Z(0,3) = 9
C(7,0) : Z(7,0) =14
64
The Happy End
65
Wyszukiwarka
Podobne podstrony:
Wykład 1 Metoda geometryczna i zadania dualneMES1 Wykład 2 METODA RITZAwykład6 [metoda trzech momentów]Wykład Metoda siłComte Auguste Metoda pozytywna w 16 wykładachComte Auguste Metoda pozytywna w 16 wykładach [Wykład 1]06 mechanika budowli wykład 06 metoda ciezarow sprezystychWykład 03 Metoda Różnic Skończonych 101 A Comte, Metoda pozytywna w 16 wykładachwięcej podobnych podstron