METODA SYMPLEKS
Model zagadnienia programowania liniowego jest w postaci
standardowej:
max(min)z = c1x1 + c2x2 + · · · + cnxn
a11x1 + a12x2 + · · · + a1nxn = b1
. . .
am1x1 + am2x2 + · · · + amnxn = bm
xi e" 0, i = 1, . . . , n
Ax b x
Zbiór ograniczeń można zapisać w postaci macierzowej Ax = b x e" 0.
Ax b, x
A
ZakÅ‚adamy, że rz¸ macierzy A jest równy m, czyli żadne równanie
ad A
nie wynika z innych równań.
1
Każdy model liniowy można sprowadzić do równoważnej postaci
standardowej w następujący sposób:
1. Ograniczenie postaci ai1x1 + ai2x2 + · · · + ainxn d" bi
zast¸
epujemy dwoma ograniczeniami:
ai1x1 + ai2x2 + · · · + ainxn + si = bi, si e" 0.
2. Ograniczenie postaci ai1x1 + ai2x2 + · · · + ainxn e" bi
zast¸
epujemy dwoma ograniczeniami:
ai1x1 + ai2x2 + · · · + ainxn - si = bi, si e" 0.
3. Jeżeli zmienna xi może przyjmować wartości ujemne to
wykonujemy podstawienie: xi = ui - vi i dodajemy ograniczenia
ui e" 0, vi e" 0.
2
Przykład 1. Sprowadzić do postaci standardowej problem:
max z = 2x1 + 3x2 - x3
x1 - 2x2 d" 5
x2 + 3x3 e" 3
x1 + x2 - 2x3 = 20
x1, x2 e" 0
Przekształcamy ograniczenia 1 i 2 oraz wykonujemy podstawienie x3 = u3 - v3 co daje postać standardową:
max z = 2x1 + 3x2 - u3 + v3
x1 - 2x2 + s1 = 5
x2 + 3u3 + 3v3 - s2 = 3
x1 + x2 - 2u3 + 2v3 = 20
x1, x2, s1, s2, u3, v3 e" 0
3
Ax b
Definicja 1. Rozpatrzmy układ ograniczeń Ax = b Wybierzmy
Ax b.
dokładnie m zmiennych i nadajmy pozostałym n - m zmiennym
wartości zerowe. Otrzymujemy w ten sposób układ m równań o m
niewiadomych. Jednoznaczne rozwi¸
azanie tego układu nazywamy
rozwi¸
azaniem bazowym. Wybrane zmienne nazywamy
zmiennymi bazowymi i oznaczamy przez ZB natomiast pozostałe
zmienne (tj. te, którym przypisano wartości 0) nazywamy
zmiennymi niebazowymi i oznaczamy przez NB.
Uwaga: Wybrane zmienne s¸ bazowe wtedy i tylko wtedy, gdy
a
A
odpowiadajace im kolumny w macierzy A s¸ liniowo niezależne. Zbiór
¸ A a
tych kolumn nazywamy baz¸ i oznaczamy przez B. Przez B bÄ™dziemy
a
również oznaczać macierz utworzoną z tych kolumn.
4
PrzykÅ‚ad 2. Wyznaczyć kilka rozwi¸
azań bazowych układu
ograniczeń:
x1 + x2 + 2x4 = 3
2x1 - x2 - x3 + 4x4 = 1
Układ ma 4 zmienne i 2 ograniczenia. Wybieramy zmienne bazowe
ZB = {x1, x2}. Podstawiamy x3 = x4 = 0 (NB = {x3, x4}).
Otrzymujemy układ:
x1 + x2 = 3
2x1 - x2 = 1
4
Rozwi¸ ac ukÅ‚ad otrzymujemy rozwi¸
azuj¸ azanie bazowe: x1 = ,
3
x2 = 12, x3 = 0, x4 = 0. Bazą są wektory współczynników macierzy
3
A
A układu równań przy zmiennych bazowych x1, x2 tj.
A
îÅ‚ Å‚Å‚
1 1
ðÅ‚ ûÅ‚.
B =
2 -1.
5
Wybierzmy teraz zmienne x2 i x3 jako bazowe tj. ZB = {x2, x3}
podstawiamy x1 = x4 = 0(ZN = {x1, x4}). BazÄ… jest
îÅ‚ Å‚Å‚
1 0
ðÅ‚ ûÅ‚
B = .
-1 -1
Otrzymujemy układ:
x2 = 3
-x2 - x3 = 1
Rozwi¸ ac ukÅ‚ad otrzymujemy rozwi¸
azuj¸ azanie bazowe: x1 = 0, x2 = 3,
x3 = -4, x4 = 0.
Wybierzmy teraz zmienne x1 i x4 i podstawmy x2 = x3 = 0.
Otrzymujemy układ:
x1 + 2x4 = 3
2x1 + 4x4 = 1
6
Układ ten jest sprzeczny. Zmienne x1 i x4 nie mogą być zmiennymi
bazowymi a macierz
îÅ‚ Å‚Å‚
1 2
ðÅ‚ ûÅ‚
B =
2 4
nie jest bazÄ…(wyznacznik jej jest zerem).
7
Definicja 2. Rozwi¸ azaniem bazowym
azanie bazowe nazywamy rozwi¸
dopuszczalnym (BRD) jeżeli wszystkie zmienne przyjmuj¸ w nim
a
wartości nieujemne.
Zbiór bazowych rozwiazaÅ„ dopuszczalnych pokrywa si¸ ze zbiorem
¸ e
punktów wierzchołkowych (ekstremalnych) zbioru rozwiazań
¸
dopuszczalnych. Dokładniej między zbiorami wierzchołków zbioru
rozwiązań dopuszczalnych a bazowymi rozwiązaniami dopuszczalnymi
istnieje odwzorowanie wzajemnie jednoznaczne takie, że każdemu
wierzchołkowi odpowiada bazowe rozwiązanie dopuszczalne i na odwrót.
Definicja 3. Dwa bazowe rozwiÄ…zania dopuszczalne nazywamy
sąsiednimi jeśli mają m - 1 zmiennych bazowych wspólnych.
Geometrycznie odpowiadają im wierzchołki sąsiednie zbioru
rozwiązań dopuszczalnych.
8
Twierdzenie 1 (Podstawowe twierdzenie programowania liniowego).
Jeżeli problem w postaci standardowej ma rozwiązanie optymalne to
ma również rozwiązanie bazowe optymalne.
Obserwacja 1. Aby wyznaczyć rozwiązanie optymalne zagadnienia
programowania liniowego wystarczy inteligentnie przeglądnąć
wierzchołki zbioru rozwiązań dopuszczalnych (lub równoważnie
bazowe rozwiązania dopuszczalne) i wybrać wierzchołek w którym
funkcja celu przyjmuje wartość maksymalną lub minimalną (dla
zagadnienia z minimum)
W algorytmie sympleks rozpoczyna siÄ™ przeglÄ…danie od poczÄ…tkowego
BRD i iteracyjnie przechodzi do sÄ…siedniego bazowego rozwiÄ…zania
dopuszczalnego. Proces ten kończy się, gdy otrzymamy rozwiązanie
optymalne lub stwierdzimy, że nie ma rozwiązania skończonego.
9
Idea algorytmu SYMPLEKS:
Wyznacz
pierwsze BRD
TAK
Czy aktualne BRD jest
KONIEC
optymalne?
NIE
Wyznacz kolejne,
niegorsze BRD
10
W algorytmie SYMPLEKS należy określić trzy elementy:
1. Wyznaczenie pierwszego BRD.
2. Stwierdzenie czy aktualne BRD jest optymalne (kryterium
optymalności).
3. Przejście do kolejnego, sąsiedniego i niegorszego BRD(iteracja
sympleksowa) lub stwierdzenie, że zagadnienie nie ma
skończonego rozwiązania optymalnego.
11
PrzykÅ‚ad 3. Rozwi¸
azać problem:
x2
max z = 4x1 + 3x2
x1 + x2 d" 40
D
40
2x1 + x2 d" 60
x1, x2 e" 0
C
20
B
A
x1
20 40
30
10
12
Przekształcamy model do postaci standardowej:
max z = 4x1 + 3x2
s1 +x1 +x2 = 40
s2 +2x1 +x2 = 60
x1, x2, s1, s2 e" 0
Powyższy model jest w tzw. postaci bazowej - układ ograniczeń jest
rozwiazany wzgl¸
¸ edem bazy skÅ‚adajÄ…cej siÄ™ z wektorów macierzy
ograniczeń stojących przy zmiennych bazowych ZB = {s1, s2} (są
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚to
1 1 1 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚), tj. B = ðÅ‚ ûÅ‚.
wektory jednostkowe e1 = i e2 =
0 0 0 1
Pierwsze BRD: s1 = 40, s2 = 60, x1 = 0, x2 = 0, z = 0. Rozwiazanie
¸
to odpowiada wierzchołkowi A.
13
Zapisujemy powyższy model w postaci układu równań (zmienne
bazowe nie wyst¸ ¸ w funkcji celu - ukÅ‚ad jest rozwiazany
epuja ¸
wzgl¸
edem s1, s2 i z):
z -4x1 -3x2 = 0
s1 +x1 +x2 = 40
(1)
s2 +2x1 +x2 = 60
x1, x2, s1, s2 e" 0
Zapis układu równań w postaci tablicy sympleksowej :
s1 s2 x1 x2
0 s1 1 0 1 1 40
0 s2 0 1 2 1 60
z 0 0 -4 -3 0
14
Ostatni wiersz zawiera współczyniki optymalności poszczególnych
zmiennych. Zmienna x1 ma ujemny współczynnik optymlności.
Wprowadzaj¸ t¸ zmienn¸ do bazy (czyli nadajac jej wartość
ac a a ¸
wie¸ a od 0) możemy powi¸ a
eksz¸ ekszyć wartość funkcji celu z. Jak¸
maksymaln¸ wartość może przyj¸ zmienna x1? Z pierwszego
a ać
ograniczenia otrzymujemy maksymaln¸ wartośćx1 = 40/1 = 40 a z
a
drugiego x1 = 60/2 = 30. Wybieramy wi¸ mniejsz¸ wartość 30 co
ec a
oznacza że baz¸ opuszcza (zostaje wyzerowana) zmienna s2.
e
s1 s2 x1 x2

0 s1 1 0 1 1 40 40/1 = 10
0 s2 0 1 2 1 60 60/2 = 30

z 0 0 -4 -3 0
Wykonujemy eliminacj¸ Gaussa wzgl¸
e edem elementu 2 czyli
15
rozwiazujemy ukÅ‚ad (1) wzgl¸
¸ edem nowych zmiennych bazowych
îÅ‚ Å‚Å‚
1 0
ðÅ‚ ûÅ‚). Wykonujemy
{s1, x1} (czyli nowej bazy B =
1 2
przekształcenia elementarne na wierszach układu (1):
1. Dzielimy trzeci wiersz przez 2.
z -4x1 -3x2 = 0
s1 +x1 +x2 = 40
1
s2 +x1 +1x2 = 30
2 2
2. Od drugiego wiersza odejmujemy trzeci wiersz podzielony przez 2.
z -4x1 -3x2 = 0
s1 -1s2 +1x2 = 10
2 2
1
s2 +x1 +1x2 = 30
2 2
16
3. Do pierwszego wiersza dodajemy trzeci wiersz pomnożony przez
2.
z +2s2 -1x2 = 120
s1 -0.5s2 +0.5x2 = 10
0.5s2 +x1 +0.5x2 = 30
Obliczenia te wygodnie jest wykonywać bezpośrednio na tablicy
sympleksowej. Otrzymujemy drug¸ tablic¸
a e:
s1 s2 x1 x2
0 s1 1 -0.5 0 0.5 10
4 x1 0 0.5 1 0.5 30
z 0 2 0 -1 120
Odczytujemy BRD: s1 = 10, x1 = 30, s2 = 0, x2 = 0 o wartościu
funkcji celu z = 120. Rozwiazanie to odpowiada wierzchołkowi B.
¸
17
Rozwiązanie to nie jest optymalne ponieważ zmienna x2 ma ujemny
współczynnik optymalności.
s1 s2 x1 x2

0 s1 1 -0.5 0 0.5 10 10/0.5 = 20

4 x1 0 0.5 1 0.5 30 30/0.5 = 60
z 0 2 0 -1 120
Do zbioru zmiennych bazowych wchodzi zmienna x2 a z tego zbioru
wychodzi zmienna s1. Wykonujemy eliminacj¸ Gaussa wzgl¸
e edem
18
elementu 0.5 (teraz już bezpośrednio na tablicy sympleksowej).
s1 s2 x1 x2
3 x2 2 -1 0 1 20
4 x1 -1 1 1 0 20
z 2 1 0 0 140
Odczytujemy BRD: x2 = 20, x1 = 20, s1 = 0, s2 = 0 i wartościu
funkcji celu z = 140. Ponieważ wszystkie wspó:
czynniki optymalności
s¸ nieujemne to rowiazanie to jest optymalne. Rozwiazanie to
a ¸ ¸
odpowiada wierzchołkowi C.
19
Przykład 4. Nieograniczona funkcja celu.
max z = 2x1 + x2 + x3
s1 +3x1 - x2 = 60
s2 +x1 - 2x2 + 2x3 = 10
x1, x2, x3, s1, s2 e" 0
Tablica sympleksowa ma nast¸ ac¸ postać:
epuj¸ a
s1 s2 x1 x2 x3
0 s1 1 0 3 -1 0 60
0 s2 0 1 1 -2 2 10
z 0 0 -2 -1 -1 0
Zmienna x2 ma ujemny współczynnik optymalnoÅ›ci. Wchodzi wi¸ do
ec
bazy. Jak¸ maksymaln¸ wartość może przyj¸ x2? Z pierwszego
a a ać
20
ograniczenia wynika że x2 może być dowolnie duże. Podobnie z
drugiego ograniczenia. Wartość zmiennej x2 (i jednocześnie funkcji
celu) może być dowolnie duża.
Uwaga: Jeżeli dla pewnej zmiennej wskaz
nik optymalności jest
ujemy i wszystkie współczynniki dla tej zmiennej s¸ niedodatnie to
a
funkcja celu jest nieograniczona.
21
ALGORYTM SYMPLEKS
1. Na wejściu podajemy model w postaci bazowej:
max(min)z = c1x1 + c2x2 + · · · + cnxn
x1 +a1m+1xm+1 + · · · + a1nxn = b1
x2 +a2m+1xm+1 + · · · + a2nxn = b2
. . .
xm +a2m+1xm+1 + · · · + a2nxn = bm
xi e" 0, i = 1, . . . , n
gdzie zmienne x1, . . . , xm s¸ bazowe i bi e" 0, i = 1, . . . m.
a
22
2. Konstuujemy pocz¸ a e a:
atkow¸ tablic¸ sympleksow¸
x1 x2 . . . xm xm+1 . . . xn
c1 x1 1 0 . . . 0 a1m+1 . . . a1n b1
c2 x2 0 1 . . . 0 a2m+1 . . . a2n b2
,
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
cm xm 0 0 . . . 1 amm+1 . . . amn bm
z 0 0 . . . 0 cm+1 . . . cn b0
gdzie:
m

ck = ciaik - ck, k = 1, . . . , n (2)
i=1
m

b0 = cibi (3)
i=1
23
3. Jeżeli wszystkie wskaz
niki optymalnoÅ›ci c1, . . . , cn s¸ nieujemne
a
to KONIEC - aktualna baza jest optymalna. W przeciwnym
wypadku przejdz
do 4.
4. Jeżeli dla pewnej zmiennej wskaz
nik optymalności jest ujemny i
wszystkie współczynniki w kolumnie odpowiadajacej tej zmiennej
¸
s¸ niedodatnie to KONIEC - funkcja celu jest nieograniczona. W
a
przeciwnym wypadku przejdz
do 5.
5. Wybierz zmienn¸ z ujemnym wskaz
nikiem optymalności np: xp.
a
Zmienna ta wchodzi do bazy. Znajdz
zmienn¸ bazow¸ xr tak¸ że:
a a a

br bi
= min
aip>0
arp aip
Zmienna xr wychodzi z bazy.
6. Wykonaj eliminacj¸ Gaussa wzgl¸
e edem elementu arp. Wróć do 3.
24
PrzykÅ‚ad. Rozwiazać algorytmem SYMPLEKS nast¸ ¸ problem:
¸ epujacy
max z = 2x1 + x2 + x3
3x1 + x2 + x3 d" 60
x1 - x2 + 2x3 d" 10
x1 + x2 - x3 d" 20
x1, x2, x3 e" 0
Przekształcamy do postaci standardowej i bazowej:
max z = 2x1 + x2 + x3
s1 +3x1 + x2 + x3 = 60
s2 +x1 - x2 + 2x3 = 10
s3 +x1 + x2 - x3 = 20
x1, x2, x3, s1, s2, s3 e" 0
25
Konstruujemy pierwsz¸ tablic¸ sympleksow¸
a e a.
s1 s2 s3 x1 x2 x3
0 s1 1 0 0 3 1 1 60
0 s2 0 1 0 1 -1 2 10
0 s3 0 0 1 1 1 -1 20
z 0 0 0 -2 -1 -1 0
Uwaga: Współczynniki optymalności wygodnie jest obliczać za
pomoc¸ wzoru (2). Na przykÅ‚ad dla zmiennej x1 otrzymujemy:
a
0 " 3 + 0 " 1 + 0 " 1 - 2 = -2.
26
s1 s2 s3
x1 x2 x3
0 s1 1 0 0 3 1 1 60 60/3 = 20
0 s2 0 1 0 1 -1 2 10 10/1 = 10

0 s3 0 0 1 1 1 -1 20 20/1 = 20
z 0 0 0 -2 -1 -1 0
Wykonujemy eliminacj¸ Gaussa wzgl¸
e edem 1 :
s1 s2 s3 x1 x2 x3
0 s1 1 -3 0 0 4 -5 30
2 x1 0 1 0 1 -1 2 10
0 s3 0 -1 1 0 2 -3 10
z 0 2 0 0 -3 3 20
27
Poprawność obliczeÅ„ można sprawdzić korzystaj¸ ze wzoru (2). Na
ac
przykład współczynnik optymalności dla x2 obliczamy:
0 " 4 + 2 " (-1) + 0 " 2 - 1 = -3. Wartość funkcji celu (z) sprawdzamy
obliczaj¸ 0 " 30 + 2 " 10 + 0 " 10 = 20. Kolejne iteracje wygladaja
ac: ¸ ¸
nastcepujaco:
¸
s1 s2 s3 x1 x2 x3

0 s1 1 -3 0 0 4 -5 30 30/4 = 7.5
2 x1 0 1 0 1 -1 2 10 -
0 s3 0 -1 1 0 2 -3 10 10/2 = 5

z 0 2 0 0 -3 3 20
28
s1 s2 s3 x1 x2 x3

0 s1 1 -1 -2 0 0 1 10 10/1 = 10

2 x1 0 0.5 0.5 1 0 0.5 15 15/0.5 = 30
1 x2 0 0.5 0.5 0 1 -1.5 5 -
z 0 -0.5 0.5 0 0 -1.5 35
s1 s2 s3 x1 x2 x3

1 x3 1 -1 -2 0 0 1 10 -
2 x1 -0.5 1 1.5 1 0 0 10 10/1 = 10

1 x2 1.5 -2 -2.5 0 1 0 20 -
z 1.5 -1 -1.5 0 0 0 50
29
s1 s2 s3 x1 x2 x3

1 x3 0.5 0 -0.5 1 0 1 20
0 s2 -0.5 1 1.5 1 0 0 10
1 x2 0.5 0 0.5 2 1 0 40
z 1 0 0 1 0 0 60
Ostatnia tablica jest optymalna. Optymalne rozwiazanie
¸
odczytujemy: x3 = 20, s2 = 10, x2 = 40, x1 = 0, s1 = 0, s2 = 0.
Maksymalna wartość funkcj celu z = 60.
30
Alternatywne rozwi¸
azania optymalne. Jeżeli w końcowej tablicy
sympleksowej współczynnik optymalności dla pewnej zmiennej
niebazowej wynosi 0 to istniejÄ… alternatywne rozwiazania optymalne.
¸
PrzykÅ‚ad 5. Rozpatrzmy ostatniÄ… tablic¸ z przykÅ‚adu 4. Zmienna
e
niebazowa s3 ma zerowy współczynnik optymalności. Wprowadzamy
tÄ™ zmiennÄ… do bazy wykonujÄ…c jednÄ… iteracjÄ™ sympleksowÄ…:
s1 s2 s3 x1 x2 x3

1 x3 0.5 0 -0.5 1 0 1 20 -
0 s2 -0.5 1 1.5 1 0 0 10 10/1.5 = 62

3
1 x2 0.5 0 0.5 2 1 0 40 40/0.5 = 80
z 1 0 0 1 0 0 60
31
s1 s2 s3 x1 x2 x3

1
1 x3 1 0 11 0 1 231
3 3 3 3
2
0 s3 -1 2 1 0 0 62
3 3 3 3
1 x2 2 -1 0 12 1 0 362
3 3 3 3
z 1 0 0 1 0 0 60
Otrzymujemy alternatywne rozwi¸
azanie optymalne: x3 = 231,
3
s3 = 62, x2 = 362, x1 = 0, s1 = 0, s2 = 0. Wartość funkcji celu
3 3
z = 60.
Uwaga: Problem posiada nieskoÅ„czenie wiele rozwi¸
azań optymalnych
32
postaci:
x1 = 0
x2 = 362t + 40(1 - t)
3
x3 = 231t + 20(1 - t)
3
t " [0, 1]
33
Algorytm SYMPLEKS dla problemu minimalizacji różni si¸ tylko
e
tym, że do bazy wchodzi zmienna z dodatnim współczynnikiem
optymalności.
PrzykÅ‚ad 6. Rozwi¸
azać problem.
min z = -3x1 + x2
3x1 + x2 d" 6
-x1 + 2x2 d" 1
x1, x2 e" 0
34
Sprowadzamy do postaci standardowej i bazowej:
min z = -3x1 + x2
s1 +3x1 + x2 = 6
s2 -x1 + 2x2 = 1
x1, x2 e" 0
s1 s2 x1 x2

0 s1 1 0 3 1 6 6/3 = 2

0 s2 0 1 -1 2 1 -
z 0 0 3 -1 0
35
s1 s2 x1 x2

3 x1 1/3 0 1 1/3 2
0 s2 1/3 1 0 7/3 3
z -1 0 0 -2 -6
Tablica ta jest optymalna (wszystkie współczynniki optymalnoÅ›ci s¸
a
niedodatnie). Optymalne rozwi¸
azanie: x1 = 2, x2 = 0, s1 = 0, s2 = 3.
Minimalna wartość funkcji celu z = -6.
36
Metoda sztucznej bazy: M-metoda
Przykład. Rozwiazać problem:
¸
max z = 2x1 + x2 - 3x3
x1 + x2 + x3 e" 6
2x1 + x2 = 14
x1, x2, x3 e" 0
Sprowadzamy do postaci standardowej:
max z = 2x1 + x2 - 3x3
x1 + x2 + x3 - s1 = 6
2x1 + x2 = 14
x1, x2, x3, s1 e" 0
37
UkÅ‚ad nie jest w postaci bazowej - nie można wi¸ rozpocz¸
ec ać
algorytmu sympleks. Sprowadzamy układ do postaci bazowej dodajac
¸
sztuczne zmienne bazowe a1 i a2. Do funkcji celu dodajemy składniki
-Ma1 i -Ma2, gdzie M jest jak¸ bardzo duż¸ liczb¸ Robimy to aby
aÅ› a a.
zmienne sztuczne nie wyst¸ ¸
apiły w rozwiazaniu (zostały wyzerowane).
max z = 2x1 + x2 - 3x3 - Ma1 - Ma2
a1 +x1 + x2 + x3 - s1 = 6
a2 +2x1 + x2 = 14
x1, x2, x3, s1, a1, a2 e" 0
Konstruujemy pierwsz¸ tabli¸ sympleksow¸ (współczynniki
a e a
38
optymalnoÅ›ci obliczamy za pomoc¸ wzoru (2)).
a
a1 a2 x1 x2 x3 s1

-M a1 1 0 1 1 1 -1 6 6/1 = 6

-M a2 0 1 2 1 0 0 14 14/2 = 7
z 0 0 -3M - 2 -2M - 1 -M + 3 M -20M
a1 a2 x1 x2 x3 s1

2 x1 1 0 1 1 1 -1 6 -
-M a2 -2 1 0 -1 -2 2 2 2/2 = 1

z 3M + 2 0 0 M + 1 2M - 1 -2M - 2 -2M + 12
39
a1 a2 x1 x2 x3 s1
1 1
2 x1 0 1 0 0 7
2 2
1
0 s1 -1 0 -1 -1 1 1
2 2
z M M + 1 0 0 3 0 14
Ostatnia tablica jest optymalna. Optymalne rozwiazanie: x1 = 7,
¸
s1 = 1, x2 = x3 = 0. Wartość funkcji celu z = 14.
Uwagi:
1. Dla problemu minimalizacji do funkcji celu dodajemy składniki
+Ma1, +Ma2...
2. Jeżeli w końcowej (optymalnej) tablicy sympleksowej któraś ze
zmiennych sztucznych a1, a2, . . . jest bazowa o dodatniej
wartości, to wyjściowy model jest sprzeczny.
40
Przykład. Rozwiazać problem:
¸
max z = 2x1 + 2x2
6x1 + 4x2 d" 24
x1 e" 5
x1, x2 e" 0
Postać standardowa:
max z = 2x1 + 2x2
6x1 + 4x2 + s1 = 24
x1 - s2 = 5
x1, x2, s1, s2 e" 0
41
Stosujemy M-metod¸
e:
max z = 2x1 + 2x2 - Ma1 - Ma2
a1 +6x1 + 4x2 + s1 = 24
a2 +x1 - s2 = 5
x1, x2, s1, s2 e" 0
a1 a2 x1 x2 s1 s2

-M a1 1 0 6 4 1 0 24 24/6 = 4

-M a2 0 1 1 0 0 -1 5 5/1 = 5
z 0 0 -7M - 2 -4M - 2 -M M -29M
42
a1 a2 x1 x2 s1 s2
1 2 1
2 x1 0 1 0 4
6 3 6
-M a2 -1 1 0 -2 -1 -1 5
6 3 6
7 1 2 1
z M + 0 0 M - 22 1M + M -5M + 8
6 3 3 3 6 3
Tablica ta jest optymalna (wszystkie współczynniki optymalności
s¸ nieujemne). Zmienna sztuczna a2 jest bazowa o dodatniej
a
wartości czyli model wyjściowy jest sprzeczny.
43
Elementy analizy wrażliwości.
Przykład. Rozpatrzmy problem z pierwszego wykładu (zapisany w
postaci bazowej):
max z = 3x1 + 2x2 [Maksymalizacja zysku]
s1 +2x1 + x2 = 100 [Zużycie surowca S1]
s2 +x1 + x2 = 80 [Zużycie surowca S2]
s3 +x1 = 40 [Popyt na W1]
x1, x2, s1, s2, s3 e" 0
Optymalnym rozwiazaniem jest x1 = 20, x2 = 60. W jakim zakresie
¸
może si¸ zmienić cena wyrobu W1 aby rozwiazanie to pozostaÅ‚o
e ¸
optymalne? Rozwiazujemy problem algorytmem sympleks. Ostatnia,
¸
44
optymalna tablica ma postać:
s1 s2 s3 x1 x2
3 x1 1 -1 0 1 0 20
2 x2 -1 2 0 0 1 60
0 s3 -1 1 1 0 0 20
z 1 1 0 0 0 180
Załóżmy, że zysk z W 1 wynosi 3 + ´. Mamy wówczas:
s1 s2 s3 x1 x2
3 + ´ x1 1 -1 0 1 0 20
2 x2 -1 2 0 0 1 60
0 s3 -1 1 1 0 0 20
z 1 + ´ -´ + 1 0 0 0 180
45
Rozwiazanie pozostanie optymalne wtedy i tylko wtedy gdy
¸
wszystkie współczynniki optymalnoÅ›ci b¸ a nieujemne, czyli:
ed¸
Å„Å‚
òÅ‚
1 + ´ e" 0
ół
-´ + 1 e" 0
St¸ ´ " [-1, 1]. Czyli rozwiazanie pozostanie optymalne dla cen
ad ¸
wyrobu W1 należ¸
acych do przedziału [2, 4].
W jakim zakresie e
îÅ‚ Å‚Å‚może si¸ zmienić zapas surowca S1 aby baza
2 1 0
ïÅ‚ śł
ïÅ‚ śł
B = odpowiadajÄ…ca zmiennym bazowym {x1, x2, s3}
1 1 0
ðÅ‚ ûÅ‚
1 0 1
pozostała optymalna (czyli aby struktura produkcji była
zachowana)? Zmiana prawej strony ograniczeń nie wpływa na
46
współczynniki optymalności. Wynika z tego, że baza B ( dla
zmiennych bazowych {x1, x2, s3}) pozostanie optymalna wtedy i
tylko wtedy gdy pozostanie dopuszczalna. St¸ szukamy wartoÅ›ci ´
ad
dla których poniższy układ jest niesprzeczny:
Å„Å‚
ôÅ‚
2x1 + x2 = 100 + ´
ôÅ‚
ôÅ‚
ôÅ‚
ôÅ‚
òÅ‚
x1 + x2 = 80
ôÅ‚
ôÅ‚ s3 + x1 = 40
ôÅ‚
ôÅ‚
ôÅ‚
ół
x1, x2, s1, s2, s3 e" 0
Zapiszmy ten układ w postaci macierzowej:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
2 1 0 x1 100 + ´
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
=
1 1 0 x2 śł ïÅ‚ 80
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
1 0 1 s3 40
47
St¸
ad:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚-1
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
x1 2 1 0 100 + ´ 0
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
= e"
x2 śł ïÅ‚ 1 1 0 80 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
s3 1 0 1 40 0
Odpowiednia macierz odwrotn¸ odczytujemy z ostatniej tablicy
¸ a
sympleksowej. Tworz¸ j¸ kolumny współczynników dla pierwszego
a a
rozwiazania bazowego:
¸
îÅ‚ Å‚Å‚-1
îÅ‚ Å‚Å‚
2 1 0 1 -1 0
ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł
=
1 1 0 -1 2 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
1 0 1 -1 1 1
48
St¸
ad:
îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚ îÅ‚ Å‚Å‚
1 -1 0 100 + ´ 0
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
ïÅ‚ śł ïÅ‚ śł ïÅ‚ śł
e"
-1 2 0 80 0
ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚ ðÅ‚ ûÅ‚
-1 1 1 40 0
Wykonujac mnożenie macierzy otrzymujemy układ nierówności:
¸
20 + ´ e" 0
100 - ´ e" 0
20 - ´ e" 0
czyli ´ " [-20,20] i zapas surowca S1 należy do przedziaÅ‚u [80,120].
49