Metoda simpleks
Gliwice
1
Sprowadzenie modelu
do postaci bazowej
Gliwice
2
Sprowadzenie modelu do postaci bazowej
Przykład 4
Model matematyczny z Przykładu 1 sprowadzić do
postaci bazowej.
Gliwice 2006
3
Sprowadzenie modelu do postaci bazowej
9x1 + 7x2 d" 63
Ograniczenie
1
Aby otrzymać ograniczenie w postaci równania wprowadzamy
dodatkową zmienną do ograniczenia:
9x1 + 7x2 + x3 = 63
x3  zmienna bilansująca
Zmienna bilansująca x3 określa ilość środka S1 jaki nie zostanie
wykorzystany w procesie produkcji.
Gliwice 2006
4
Sprowadzenie modelu do postaci bazowej
9x1 + 7x2 + x3 = 63
Gliwice 2006
5
Sprowadzenie modelu do postaci bazowej
x1 + x2 d" 8
Ograniczenie
2
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 bilansująca x4 określa ilość środka S2 jaki nie zostanie
wykorzystany w procesie produkcji.
Gliwice 2006
6
Sprowadzenie modelu do postaci bazowej
3x1 + 2x2 e" 6
Ograniczenie
3
Aby otrzymać ograniczenie w postaci równania wprowadzamy
dodatkową zmienną do ograniczenia:
3x1 + 2x2 - x5 = 6
x5  zmienna bilansująca
Gliwice 2006
7
Sprowadzenie modelu do postaci bazowej

Gliwice 2006
8
Sprowadzenie modelu do postaci bazowej


Gliwice 2006
9
Sprowadzenie modelu do postaci bazowej


Gliwice 2006
10
Sprowadzenie modelu do postaci bazowej
Czy zmienne bilansujące należy uwzględnić w funkcji celu?
Gliwice 2006
11
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
1
x1 + x2 + x4 = 8
2
3x1 + 2x2 - x5 + x6 = 6
3
WB:
x1 e" 0, x2 e" 0, x3 e" 0, x4 e" 0, x5 e" 0, x6 e" 0
Gliwice 2006
12
Sprowadzenie modelu do postaci bazowej
Sprowadzenie do postaci bazowej ograniczenia typu:
x1 + 2x2 = 4
Wprowadzamy zmienną sztuczną:
x1 + 2x2 + x3 = 4
Zmienną sztuczną x3 należy uwzględnić w funkcji celu w podany
poprzednio sposób, czyli tak, aby jej niezerowa wartość mocno
pogarszała wartość funkcji celu.
Gliwice 2006
13
Metoda simpleks
Gliwice 2006
14
Metoda simpleks
Przykład 5
Rozwiązać zadanie z Przykładu 1 metodą simpleks.
Gliwice 2006
15
Metoda simpleks
Tablica simpleks:
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
Gliwice 2006
16
Metoda simpleks
cj  zj wskaz
niki optymalności
Dla zmiennych bazowych wskaz
niki optymalności zawsze

są równe 0.
Gliwice 2006
17
Metoda simpleks
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
Gliwice 2006
18
Metoda simpleks
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ż jednej zmiennej, wybieramy zmienną
o niższym indeksie.
W przykładzie kryterium wejścia spełnia zmienna x1.
Gliwice 2006
19
Metoda simpleks
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.
Gliwice 2006
20
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0 0 -1000 0
Gliwice 2006
21
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x6 -1000 3 2 0 0 -1 1 6
zj -3000 -2000 0 0 1000 -1000
cj  zj 3006 2005 0 0 -1000 0
Gliwice 2006
22
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 01101008
x1 6
zj
cj  zj
3 2 0 0 -1 16
Gliwice 2006
23
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 097100063
x4 0
x1 6 1 2/3 0 0 -1/3 1/3 2
zj
cj  zj
1 1 0 1 0 08
Gliwice 2006
24
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 0
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
cj  zj
9 7 1 0 0 063
Gliwice 2006
25
Metoda simpleks
6 5 0 0 0 -1000
cTxMAX
bi
x(B) c(B) x1 x2 x3 x4 x5 x6
x3 001103-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
cj  zj
Rozwiązanie w bazie [x3, x4, x1]
Gliwice 2006
26
Metoda simpleks
Do bazy wchodzi zmienna:
Ilorazy:
Z bazy wychodzi zmienna:
Gliwice 2006
27
Metoda simpleks
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 61 7/9 1/9 0007
zj 6 14/3 2/3 0 0 0
cj  zj 0 1/3 -2/3 0 0 -1000
Rozwiązanie w bazie [x5, x4, x1] nie jest rozwiązaniem optymalnym.
Gliwice 2006
28
Metoda simpleks
Do bazy wchodzi zmienna:
Ilorazy:
Z bazy wychodzi zmienna:
Gliwice 2006
29
Metoda simpleks
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 501 -1/2 9/2 00 9/2
x1 6 1 0 1/2 -7/2 0 0 7/2
zj 65 1/2 3/2 00
cj  zj 0 0 -1/2 -3/2 0 -1000
Rozwiązanie w bazie [x5, x2, x1] jest rozwiązaniem optymalnym.
Gliwice 2006
30
Metoda simpleks
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 501 -1/2 9/2 00 9/2
x1 6 1 0 1/2 -7/2 0 0 7/2
zj 65 1/2 3/2 00
cj  zj 0 0 -1/2 -3/2 0 -1000
Zmienne bazowe:
Zmienne niebazowe:
Gliwice 2006
31
Metoda simpleks
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
( )
Gliwice 2006
32
Różnice w algorytmie
metody simpleks na
MAX i MIN
Gliwice 2006
33
Różnice w algorytmie metody simpleks na MAX i MIN
Kryterium wejścia do bazy
MAX:
Zmienna z największą wartością wskaz
nika optymalności.
MIN:
Zmienna z najmniejszą wartością wskaz
nika optymalności.
Gliwice 2006
34
Różnice w algorytmie metody simpleks na MAX i MIN
Kryterium wyjścia z bazy
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.
Gliwice 2006
35
Różnice w algorytmie metody simpleks 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.
Gliwice 2006
36
Szczególne przypadki rozwiązań
Gliwice 2006
37
Szczególne przypadki rozwiązań
Zadanie sprzeczne
Z x1, x2 = 6x1 + 5x2 MAX
( )
x1 + x2 e" 8
1
3x1 + 2x2 d" 6
2
x1, x2 e" 0
W postaci bazowej:
Gliwice 2006
38
Szczególne przypadki rozwiązań
x2
10
9
8
7
6
5
4
3
2 2
1
1
x1
1 2 3 4 5 6 7 8 9 10
Gliwice 2006
39
Szczególne przypadki rozwiązań
Zadanie sprzeczne:
Nie ma rozwiązań dopuszczalnych
Objawy w metodzie simpleks:
W rozwiązaniu optymalnym, zmienna sztuczna (w tym
przykładzie zmienna x4) będzie miała wartość niezerową (czyli
będzie w bazie).
Gliwice 2006
40
Szczególne przypadki rozwiązań
Alternatywne rozwiązania optymalne
Z x1, x2 = 2x1 + 2x2 MAX
( )
x1 + x2 d" 8
1
3x1 + 2x2 e" 6
2
x1, x2 e" 0
W postaci bazowej:
Z x1, x2, x3, x4, x5 = 2x1 + 2x2 + 0x3 + 0x4 -1000x5 MAX
( )
x1 + x2 + x3 = 8
1
3x1 + 2x2 - x4 + x5 = 6
2
x1, x2, x3, x4, x5 e" 0
Gliwice 2006
41
Szczególne przypadki rozwiązań
x2
10
9
C (0, 8): Z(0, 8) = 16
C
8
D (8, 0): Z(8, 0) = 16
7
6
5
4
B
1
3
2
1
2
A D
x1
1 2 3 4 5 6 7 8 9 10
Gliwice 2006
42
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 simpleks:
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.
Gliwice 2006
43
Szczególne przypadki rozwiązań
Nieograniczony zbiór rozwiązań dopuszczalnych
Z x1, x2 = 2x1 + 3x2 MAX
( )
3x1 + 2x2 e" 6
1
x1 d" 7
2
x1, x2 e" 0
W postaci bazowej:
Z x1, x2, x3, x4, x5 = 2x1 + 3x2 + 0x3 -1000x4 + 0x5 MAX
( )
3x1 + 3x2 - x3 + x4 = 6
1
x1 + x5 = 7
2
x1, x2, x3, x4, x5 e" 0
Gliwice 2006
44
Szczególne przypadki rozwiązań
x2
10
9
8
7
6
5
4
2
B
3
2
1
1
C
A
x1
1 2 3 4 5 6 7 8 9 10
Gliwice 2006
45
Szczególne przypadki rozwiązań
W tym zadaniu:
Zbiór rozwiązań jest nieograniczony
Funkcja celu jest nieograniczona z góry
Objawy w metodzie simpleks:
W tablicy simpleks kolumna zmiennej wchodzącej do bazy ma
wszystkie elementy niedodatnie.
Gliwice 2006
46
Szczególne przypadki rozwiązań
Czy funkcja celu może być nieograniczona od dołu?
Czy pomimo tego, że zbiór rozwiązań dopuszczalnych jest
nieograniczony może istnieć  dokładne rozwiązanie optymalne?
Gliwice 2006
47
Szczególne przypadki rozwiązań
Z x1, x2 = 2x1 + 3x2 MIN
( )
3x1 + 2x2 e" 6
1
x1 d" 7
2
x1, x2 e" 0
3
Z poprzedniego rysunku:
A (2, 0): Z(2, 0) = 4 MIN
B (0, 3): Z(0, 3) = 9
C (7, 0): Z(7, 0) = 14
Gliwice 2006
48