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:
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
16
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000
=-3000
z1 = 0Å"9 + 0Å"1+ (-1000) Å"3
17
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000
=-2000
z2 = 0Å"7 + 0Å"1+ (-1000) Å" 2
18
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0
= 0
z3 = 0Å"1+ 0Å"0 + (-1000) Å"0
19
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0
= 0
z4 = 0Å"0 + 0Å"1+ (-1000) Å"0
20
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000
=1000
z5 = 0Å"0 + 0Å"0 + (-1000) Å"(-1)
21
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000 -1000
=-1000
z6 = 0Å"0 + 0Å"0 + (-1000) Å"1
22
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006
= 3006
c1 - z1 = 6 - (-3000)
23
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005
= 2005
c2 - z2 = 5 - (-2000)
24
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0
= 0
c3 - z3 = 0 - 0
25
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0 0
= 0
c4 - z4 = 0 - 0
26
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0 0 -1000
=-1000
c5 - z5 = 0 -1000
27
Metoda simplex
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
zj -3000 -2000 0 0 1000 -1000
cj - zj 3006 2005 0 0 -1000 0
= 0
c6 - z6 = -1000 - (-1000)
28
Metoda simplex
- wskaz
niki optymalności
cj - z
j
Dla zmiennych bazowych wskaz
niki optymalności zawsze
są równe 0.
29
Metoda simplex
Kryterium optymalności:
Rozwiązanie jest optymalne, jeżeli wartości wszystkich
wskaz
nikó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ść
wskaz
nika optymalności.
Jeżeli największa wartość wskaz
nika 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
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 971000 63
x4 0 1101008
x6 -1000 3200-1 16
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
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x3 0 01103-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 6400 -22
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
cTxMAX 6 5 0 0 0 -1000
bi
x(B) c(B)
x1 x2 x3 x4 x5 x6
x5 0 01/3 1/3 01-1 15
x4 0 02/9 -1/9 100 1
x1 6 17/9 1/9 000 7
zj 6 14/3 2/3 0 0 0
cj - zj 0 00
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
cTxMAX 6 5 0 0 0 -1000
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 651/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
cTxMAX 6 5 0 0 0 -1000
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 651/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ą wskaz
nika optymalności
MIN:
Zmienna z najmniejszą wartością wskaz
nika 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 wskaz
niki optymalności muszą być niedodatnie
MIN:
Wszystkie wskaz
niki optymalności muszą być nieujemne.
44
Metoda simplex
a zadanie dualne
Metoda simplex a zadanie dualne
Klasyczną metodę simplex można stosować tylko do
rozwiązania zadań dualnych, utworzonych z zadania
pierwotnego, w którym wszystkie ograniczenia są typu:
a1x1 + a2x2 +...+ anxn d" b
Uzasadnienie: tylko wtedy na wszystkie zmienne decyzyjne
zadania dualnego nałożone są warunki nieujemności.
Metoda simplex w postaci klasycznej nazywana jest prymalnÄ…
metodÄ… simplex.
46
Metoda simplex a zadanie dualne
Do zadań dualnych utworzonych z problemów o różnych typach
ograniczeń stosuje się dualną metodę simplex.
Różnice w stosunku do klasycznej metody simplex:
" kryterium wejścia
" kryterium wyjścia
" kryterium optymalności
47
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
49
Szczególne przypadki rozwiązań
50
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).
51
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
52
Szczególne przypadki rozwiązań
C(0,8) : Z(0,8) = 16
D(8,0) : Z(8,0) = 16
53
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 wskaz
ników
optymalności dla zmiennych niebazowych.
Rozwiązania optymalne można zidentyfikować przechodząc do
kolejnych baz.
54
Szczególne przypadki rozwiązań
Nieograniczony zbiór rozwiązań dopuszczalnych
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
55
Szczególne przypadki rozwiązań
56
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.
57
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.
58
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
59
The Happy End
60