1 Programowanie liniowe: metoda sympleks
1.1 Sprowadzanie (ZPL) do postaci standardowej
Przypadek 1:
Jeżeli w (ZPL) istnieją ograniczenia nierównościowe postaci:
a11x1 + a12x2 + ... + a1nxn b1
a21x1 + a22x2 + ... + a2nxn b2
.............................. ...
to wprowadzamy nowe zmienne y1, y2, ... nieujemne (y1 0, y2 0, ...), aby zamienić nierówności na równania:
a11x1 + a12x2 + ... + a1nxn + y1 = b1
a21x1 + a22x2 + ... + a2nxn + y2 = b2
.............................. = ...
Przykład 1:
Sprowadzić poniższe (ZPL) do postaci standardowej:
min(2x1 + 3x2 - 4x4)
Å„Å‚
x1 + 5x2 - 3x3 + x4 = 7
ôÅ‚
ôÅ‚
òÅ‚
x2 - 4x4 3
x1 + 5x2 - 4x3 2
ôÅ‚
ôÅ‚
ół
x1 0, x2 0, x3 0, x4 0
RozwiÄ…zanie:
Wprowadzamy nowe zmienne y1 0, y2 0 i zapisujemy (ZPL) w postaci:
min(2x1 + 3x2 - 4x4)
Å„Å‚
x1 + 5x2 - 3x3 + x4 = 7
ôÅ‚
ôÅ‚
òÅ‚
x2 - 4x4 + y1 = 3
x1 + 5x2 - 4x3 + y2 = 2
ôÅ‚
ôÅ‚
ół
x1 0, x2 0, x3 0, x4 0, y1 0, y2 0
Przypadek 2:
Podobnie, jeżeli w (ZPL) istnieją ograniczenia nierównościowe postaci:
a11x1 + a12x2 + ... + a1nxn b1
a21x1 + a22x2 + ... + a2nxn b2
.............................. ...
to wprowadzamy nowe zmienne y1, y2, ... nieujemne (y1 0, y2 0, ...), aby zamienić nierówności na równania:
a11x1 + a12x2 + ... + a1nxn - y1 = b1
a21x1 + a22x2 + ... + a2nxn - y2 = b2
.............................. = ...
1
Przykład 2:
Sprowadzić poniższe (ZPL) do postaci standardowej:
min(2x1 + 3x2 - 4x4)
Å„Å‚
x1 + 5x2 - 3x3 + x4 7
ôÅ‚
ôÅ‚
òÅ‚
x2 - 4x4 = 3
x1 + 5x2 - 4x3 2
ôÅ‚
ôÅ‚
ół
x1 0, x2 0, x3 0, x4 0
RozwiÄ…zanie:
Wprowadzamy nowe zmienne y1 0, y2 0 i zapisujemy (ZPL) w postaci:
min(2x1 + 3x2 - 4x4)
Å„Å‚
x1 + 5x2 - 3x3 + x4 - y1 = 7
ôÅ‚
ôÅ‚
òÅ‚
x2 - 4x4 = 3
x1 + 5x2 - 4x3 + y2 = 2
ôÅ‚
ôÅ‚
ół
x1 0, x2 0, x3 0, x4 0, y1 0, y2 0
Przypadek 3:
Jeżeli w (ZPL) istnieją tzw. zmienne swobodne, tzn. nie ma któregoś z ograniczeń typu x1 0, x2 0, ..., to w celu sprowadzenia
(ZPL) do postaci standardowej możemy postąpić na dwa sposoby.
Sposób 1.
Dla każdej zmiennej swobodnej xi wprowadzamy dwie nowe zmienne ui 0, vi 0, przyjmujemy
xi = ui - vi
i zastępujemy xi tym podstawieniem w funkcji celu i we wszystkich ograniczeniach.
Przykład 3:
Sprowadzić poniższe (ZPL) do postaci standardowej:
min(2x1 + 3x2 - 4x4)
Å„Å‚
x1 + 5x2 - 3x3 + x4 = 7
ôÅ‚
ôÅ‚
òÅ‚
x2 - 4x4 = 3
x1 + 5x2 - 4x3 -2
ôÅ‚
ôÅ‚
ół
x1 0, x4 0
RozwiÄ…zanie:
Ponieważ w trzecim ograniczeniu występuje nierówność, wprowadzamy nową zmienną y1 0 i zapisujemy to
ograniczenie w postaci:
x1 + 5x2 - 4x3 + y1 = -2
Po prawej stronie jest liczba ujemna (-2), zatem trzeba jeszcze pomnożyć to ograniczenie przez -1. Otrzymamy
wtedy:
-x1 - 5x2 + 4x3 - y1 = 2
Ponadto, w rozważanym (ZPL) brak jest ograniczeń x2 0, x3 0.
Możemy zatem wprowadzić dodatkowe zmienne u2 0, v2 0, u3 0, v3 0 takie, że
x2 = u2 - v2 i x3 = u3 - v3,
następnie zastępujemy x2 i x3 w funkcji celu i we wszystkich ograniczeniach równościowych. Ostatecznie mamy:
min(2x1 + 3u2 - 3v2 - 4x4)
Å„Å‚
x1 + 5u2 - 5v2 - 3u3 + 3v3 + x4 = 7
ôÅ‚
ôÅ‚
òÅ‚
u2 - v2 - 4x4 = 3
ôÅ‚ -x1 - 5u2 + 5v2 + 4u3 - 4v3 - y1 = 2
ôÅ‚
ół
x1 0, x4 0, u2 0, v2 0, u3 0, v3 0, y1 0
2
Sposób 2.
Jeżeli np. x1 jest zmienną swobodną, to z dowolnego ograniczenia równościowego, powiedzmy:
a11x1 + a12x2 + ... + a1nxn = b1
wyznaczamy
1
x1 = (b1 - a12x2 - ... - a1nxn)
a11
i wstawiamy do wszystkich takich ograniczeń, które w postaci standardowej (ZPL) mają być przedstawione w postaci równań.
Przykład 4:
Sprowadzić poniższe (ZPL) do postaci standardowej:
min(2x1 + 3x2 - 4x4)
Å„Å‚
x1 + 5x2 - 3x3 + x4 = 7
ôÅ‚
ôÅ‚
òÅ‚
x2 - 4x4 = 3
x1 + 5x2 - 4x3 = 2
ôÅ‚
ôÅ‚
ół
x1 0, x4 0
RozwiÄ…zanie:
Z drugiego równania:
x2 = 4x4 + 3 (1)
a z trzeciego:
x3 = 0, 25(x1 + 5x2 - 2) = 0, 25(x1 + 20x4 + 13) =
= 0, 25x1 + 5x4 + 3, 25 (2)
Wstawiając (1) i (2) do funkcji celu i pierwszego ograniczenia równościowego otrzymamy (ZPL) w postaci standardowej:
min(2x1 + 8x4)

0, 25x1 + 6x4 = 1, 75
x1 0, x4 0
Uwaga:
W rzeczywistości funkcja celu po wyeliminowaniu zmiennych x2 i x3 ma postać
f(x1, x4) = 2x1 + 8x4 + 9,
jednak dodanie stałej do funkcji celu nie wpływa na optymalne rozwiązanie bazowe, tzn. takie, dla którego funkcja f osiąga
minimum. Wystarczy zatem rozwiązać powyższe (ZPL) w postaci standardowej z funkcją celu 2x1 + 8x4, a następnie dodać 9
do otrzymanej wartości tej funkcji.
Przypadek 4:
Jeżeli w (ZPL) jest max zamiast min, to korzystamy ze wzoru:
max f(x1, x2, ..., xn) = - min(-f(x1, x2, ..., xn))
Przykład 5:
Sprowadzić poniższe (ZPL) do postaci standardowej:
max(2x1 + 8x2)

x1 + 6x2 = 1
x1 0, x2 0
RozwiÄ…zanie:
Otrzymujemy (ZPL) postaci:
min(-2x1 - 8x2)

x1 + 6x2 = 1
x1 0, x2 0
Po jego rozwiązaniu należy pamiętać o tym, że minimalna wartość funkcji celu w ostatnim sformułowaniu
zadania jest równa minus wartości maksymalnej z pierwotnego sformułowania zadania.
3
1.2 Dwufazowa metoda sympleks.
Przykład 6:
Stosując dwufazową metodę sympleks, rozwiązać (ZPL):
min(2x1 + 3x2)
Å„Å‚
x1 + 4x2 + x3 = 1
òÅ‚
x1 + x2 + 2x3 = 2
ół
x1 0, x2 0, x3 0
I faza:
Jest to zadanie w postaci standardowej. W pierwszej fazie wprowadzamy sztuczne zmienne y1, y2 i formułujemy
poniższe pomocnicze (ZPL):
min(y1 + y2)
Å„Å‚
x1 + 4x2 + x3 + y1 = 1
òÅ‚
x1 + x2 + 2x3 + y2 = 2
ół
x1 0, x2 0, x3 0, y1 0, y2 0
Tworzymy poczÄ…tkowÄ… tabelÄ™ metody sympleks:
x1 x2 x3 y1 y2 b
Pierwsze ograniczenie (wiersz w1): 1 4 1 1 0 1
Drugie ograniczenie (wiersz w2): 1 1 2 0 1 2
Funkcja celu (wiersz w): 0 0 0 1 1 0
Liczby zaznaczone niebieskim kolorem tworzÄ… kolumny jednostkowe. Zmieniamy wiersz funkcji celu tak, aby pod
kolumnami jednostkowymi otrzymać same zera (w miejscu liczb czerwonych), wykonując działanie na wierszach:
w - w1 - w2. Otrzymamy wtedy:
x1 x2 x3 y1 y2 b
1 4 1 1 0 1
1 1 2 0 1 2
-2 -5 -3 0 0 -3
Powyższej tabeli odpowiada dopuszczalne rozwiązanie bazowe
= [x1, x2, x3, y1, y2]T = [0, 0, 0, 1, 2]T
x
(pierwsze trzy kolumny nie są jednostkowe, dlatego przyjmujemy x1 = x2 = x3 = 0, pozostałe dwie są
jednostkowe - stanowią bazę, zatem wartości zmiennych y1 = 1 i y2 = 2 odczytujemy z ostatniej kolumny).
Wartość funkcji celu dla powyższego dopuszczalnego rozwiązania bazowego wynosi f( = 3 (niebieska liczba
x x)
z przeciwnym znakiem).
Wybieramy najmniejszÄ… ujemnÄ… liczbÄ™ w ostatnim wierszu (liczba czerwona) - nie bierzemy pod uwagÄ™ przy
tym wyborze liczby niebieskiej. Ponieważ wybrana w ten sposób liczba jest w drugiej kolumnie, wprowadzamy
tę kolumnę do bazy (chcemy uczynić ją kolumną jednostkową).
Gdyby wszystkie liczby w ostatnim wierszu (z wyjątkiem niebieskiej) były nieujemne, nie moglibyśmy
utworzyć kolumn jednostkowych związanych ze zmiennymi innymi niż sztuczne (y1 i y2) - wtedy pierwotne
(ZPL) nie miałoby rozwiązania.
Obliczamy ilorazy liczb z ostatniej kolumny (zielone) przez odpowiednie liczby z kolumny wprowadzanej do
bazy (drugiej - liczby zielone):
1 2
, = 2
4 1
przy czym w obliczeniach bierzemy pod uwagÄ™ tylko liczby dodatnie z kolumny wprowadzanej do bazy. Wy-
1
bieramy z tych ilorazów najmniejszy, czyli . Ponieważ powstał on przez dzielenie liczb w pierwszym wierszu,
4
więc wyrzucamy z bazy tę kolumnę, która ma jedynkę właśnie w pierwszym wierszu, czyli kolumnę związaną
ze zmiennÄ… y1.
4
Gdyby wszystkie liczby w kolumnie wprowadzanej do bazy były ujemne, pierwotne (ZPL) byłoby nie-
ograniczone (min f( = -").
x)
1
Chcemy, aby teraz druga kolumna stała się kolumną jednostkową. Mnożymy zatem pierwszy wiersz przez ,
4
1
aby liczba w ramce stała się równa 1 (działanie: w1):
4
x1 x2 x3 y1 y2 b
1 1 1 1
1 0
4 4 4 4
1 1 2 0 1 2
-2 -5 -3 0 0 -3
Otrzymujemy teraz zera w drugiej kolumnie tam, gdzie są liczby czerwone (działania: w2 - w1, w + 5w1):
x1 x2 x3 y1 y2 b
1 1 1 1
1 0
4 4 4 4
3 7 1 7
0 - 1
4 4 4 4
3 7
- 0 -7 5 0 -
4 4 4 4
Powyższej tabeli odpowiada dopuszczalne rozwiązanie bazowe
T
1 7
= [x1, x2, x3, y1, y2]T = 0, , 0, 0,
x
4 4
(kolumny: pierwsza, trzecia i czwarta nie są jednostkowe, dlatego przyjmujemy x1 = x3 = y1 = 0, pozostałe dwie
1 7
są jednostkowe - stanowią bazę, zatem wartości zmiennych x2 = i y2 = odczytujemy z ostatniej kolumny).
4 4
7
Wartość funkcji celu dla powyższego dopuszczalnego rozwiązania bazowego wynosi f( = (niebieska liczba
x x)
4
z przeciwnym znakiem).
Wybieramy najmniejszą ujemną liczbę w ostatnim wierszu (liczba czerwona). Ponieważ ta liczba jest w trzeciej
kolumnie, wprowadzamy tÄ™ kolumnÄ™ do bazy.
Obliczamy ilorazy liczb z ostatniej kolumny (zielone) przez odpowiednie liczby z kolumny wprowadzanej do
bazy (trzeciej - liczby zielone):
1 1 7 7
: = 1, : = 1
4 4 4 4
Ilorazy są identyczne, więc możemy wyrzucić z bazy kolumnę drugą (związaną ze zmienną x2) lub piątą (zwią-
zaną ze zmienną y2). Zależy nam jednak na tym, aby w bazie nie było kolumn związanych ze zmiennymi
sztucznymi, zatem wyrzucamy z bazy kolumnÄ™ piÄ…tÄ….
4 4
Mnożymy drugi wiersz przez , aby liczba w ramce stała się równa 1 (działanie: w2):
7 7
x1 x2 x3 y1 y2 b
1 1 1 1
1 0
4 4 4 4
3 1 4
0 1 - 1
7 7 7
3 7
- 0 -7 5 0 -
4 4 4 4
1 7
Otrzymujemy zera w trzeciej kolumnie tam, gdzie są liczby czerwone (działania: w1 - w2, w + w2):
4 4
x1 x2 x3 y1 y2 b
1 2 1
1 0 - 0
7 7 7
3 1 4
0 1 - 1
7 7 7
0 0 0 1 1 0
Ponieważ w ostatnim wierszu wszystkie liczby są nieujemne, więc kończymy obliczenia I fazy. Jednocześnie
otrzymaliśmy bazę nie związaną ze zmiennymi sztucznymi, zatem możemy przejść do II fazy.
5
II faza:
Teraz bierzemy pod uwagę tylko te kolumny z ostatniej tabeli, które nie są związane ze zmiennymi sztucznymi.
Powracamy do pierwotnej funkcji celu, tzn. f( = 2x1 + 3x2:
x)
x1 x2 x3 b
1
1 0 0
7
3
0 1 1
7
2 3 0 0
Dalej postępujemy analogicznie, jak w I fazie, tzn. na początku zmieniamy wiersz funkcji celu tak, aby pod
kolumnami jednostkowymi otrzymać same zera (w miejscu liczb czerwonych), wykonując działanie na wierszach:
w - 3w1. Otrzymamy:
x1 x2 x3 b
1
1 0 0
7
3
0 1 1
7
11
0 0 0
7
Kończymy obliczenia, gdyż wszystkie liczby w ostatnim wierszu są nieujemne. Otrzymaliśmy rozwiązanie opty-
malne pierwotnego (ZPL) w punkcie = [0, 0, 1]T . Wartość pierwotnej funkcji celu dla powyższego dopuszczal-
x
nego rozwiÄ…zania bazowego wynosi f( = 0 (niebieska liczba z przeciwnym znakiem).
x x)
.
Opracował: Krzysztof Piekarski
Katedra Matematyki
Wydział Informatyki PB
6