1

Programowanie liniowe: metoda sympleks

1.1

Sprowadzanie (ZPL) do postaci standardowej

Przypadek 1:

Jeżeli w (ZPL) istnieją ograniczenia nierównościowe postaci:

a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

6 b

1

a

21

x

1

+ a

22

x

2

+ ... + a

2n

x

n

6 b

2

..............................

6 ...

to wprowadzamy nowe zmienne y

1

, y

2

, ... nieujemne (y

1

> 0, y

2

> 0, ...), aby zamienić nierówności na równania:

a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

+ y

1

=

b

1

a

21

x

1

+ a

22

x

2

+ ... + a

2n

x

n

+ y

2

=

b

2

..............................

=

...

Przykład 1:
Sprowadzić poniższe (ZPL) do postaci standardowej:

min(2x

1

+ 3x

2

− 4x

4

)















x

1

+ 5x

2

− 3x

3

+ x

4

=

7

x

2

− 4x

4

6 3

x

1

+ 5x

2

− 4x

3

6 2

x

1

> 0, x

2

> 0, x

3

> 0, x

4

> 0

Rozwiązanie:
Wprowadzamy nowe zmienne y

1

> 0, y

2

> 0 i zapisujemy (ZPL) w postaci:

min(2x

1

+ 3x

2

− 4x

4

)















x

1

+ 5x

2

− 3x

3

+ x

4

=

7

x

2

− 4x

4

+ y

1

=

3

x

1

+ 5x

2

− 4x

3

+ y

2

=

2

x

1

> 0, x

2

> 0, x

3

> 0, x

4

> 0, y

1

> 0, y

2

> 0

Przypadek 2:

Podobnie, jeżeli w (ZPL) istnieją ograniczenia nierównościowe postaci:

a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

> b

1

a

21

x

1

+ a

22

x

2

+ ... + a

2n

x

n

> b

2

..............................

> ...

to wprowadzamy nowe zmienne y

1

, y

2

, ... nieujemne (y

1

> 0, y

2

> 0, ...), aby zamienić nierówności na równania:

a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

− y

1

=

b

1

a

21

x

1

+ a

22

x

2

+ ... + a

2n

x

n

− y

2

=

b

2

..............................

=

...

1

Przykład 2:
Sprowadzić poniższe (ZPL) do postaci standardowej:

min(2x

1

+ 3x

2

− 4x

4

)















x

1

+ 5x

2

− 3x

3

+ x

4

> 7

x

2

− 4x

4

=

3

x

1

+ 5x

2

− 4x

3

6 2

x

1

> 0, x

2

> 0, x

3

> 0, x

4

> 0

Rozwiązanie:
Wprowadzamy nowe zmienne y

1

> 0, y

2

> 0 i zapisujemy (ZPL) w postaci:

min(2x

1

+ 3x

2

− 4x

4

)















x

1

+ 5x

2

− 3x

3

+ x

4

− y

1

=

7

x

2

− 4x

4

=

3

x

1

+ 5x

2

− 4x

3

+ y

2

=

2

x

1

> 0, x

2

> 0, x

3

> 0, x

4

> 0, y

1

> 0, y

2

> 0

Przypadek 3:

Jeżeli w (ZPL) istnieją tzw. zmienne swobodne, tzn. nie ma któregoś z ograniczeń typu x

1

> 0, x

2

> 0, ..., to w celu sprowadzenia

(ZPL) do postaci standardowej możemy postąpić na dwa sposoby.

Sposób 1.
Dla każdej zmiennej swobodnej x

i

wprowadzamy dwie nowe zmienne u

i

> 0, v

i

> 0, przyjmujemy

x

i

= u

i

− v

i

i zastępujemy x

i

tym podstawieniem w funkcji celu i we wszystkich ograniczeniach.

Przykład 3:
Sprowadzić poniższe (ZPL) do postaci standardowej:

min(2x

1

+ 3x

2

− 4x

4

)















x

1

+ 5x

2

− 3x

3

+ x

4

=

7

x

2

− 4x

4

=

3

x

1

+ 5x

2

− 4x

3

6 −2

x

1

> 0, x

4

> 0

Rozwiązanie:
Ponieważ w trzecim ograniczeniu występuje nierówność, wprowadzamy nową zmienną y

1

> 0 i zapisujemy to

ograniczenie w postaci:

x

1

+ 5x

2

− 4x

3

+ y

1

= −2

Po prawej stronie jest liczba ujemna (-2), zatem trzeba jeszcze pomnożyć to ograniczenie przez -1. Otrzymamy
wtedy:

−x

1

− 5x

2

+ 4x

3

− y

1

= 2

Ponadto, w rozważanym (ZPL) brak jest ograniczeń x

2

> 0, x

3

> 0.

Możemy zatem wprowadzić dodatkowe zmienne u

2

> 0, v

2

> 0, u

3

> 0, v

3

> 0 takie, że

x

2

= u

2

− v

2

i

x

3

= u

3

− v

3

,

następnie zastępujemy x

2

i x

3

w funkcji celu i we wszystkich ograniczeniach równościowych. Ostatecznie mamy:

min(2x

1

+ 3u

2

− 3v

2

− 4x

4

)















x

1

+ 5u

2

− 5v

2

− 3u

3

+ 3v

3

+ x

4

=

7

u

2

− v

2

− 4x

4

=

3

−x

1

− 5u

2

+ 5v

2

+ 4u

3

− 4v

3

− y

1

=

2

x

1

> 0, x

4

> 0, u

2

> 0, v

2

> 0, u

3

> 0, v

3

> 0, y

1

> 0

2

Sposób 2.
Jeżeli np. x

1

jest zmienną swobodną, to z dowolnego ograniczenia równościowego, powiedzmy:

a

11

x

1

+ a

12

x

2

+ ... + a

1n

x

n

=

b

1

wyznaczamy

x

1

=

1

a

11

(b

1

− a

12

x

2

− ... − a

1n

x

n

)

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(2x

1

+ 3x

2

− 4x

4

)















x

1

+ 5x

2

− 3x

3

+ x

4

=

7

x

2

− 4x

4

=

3

x

1

+ 5x

2

− 4x

3

=

2

x

1

> 0, x

4

> 0

Rozwiązanie:
Z drugiego równania:

x

2

= 4x

4

+ 3

(1)

a z trzeciego:

x

3

=

0, 25(x

1

+ 5x

2

− 2) = 0, 25(x

1

+ 20x

4

+ 13) =

=

0, 25x

1

+ 5x

4

+ 3, 25

(2)

Wstawiając (1) i (2) do funkcji celu i pierwszego ograniczenia równościowego otrzymamy (ZPL) w postaci standardowej:

min(2x

1

+ 8x

4

)



0, 25x

1

+ 6x

4

=

1, 75

x

1

> 0, x

4

> 0

Uwaga:
W rzeczywistości funkcja celu po wyeliminowaniu zmiennych x

2

i x

3

ma postać

f (x

1

, x

4

) = 2x

1

+ 8x

4

+ 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 2x

1

+ 8x

4

, 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 (x

1

, x

2

, ..., x

n

) = − min(−f (x

1

, x

2

, ..., x

n

))

Przykład 5:
Sprowadzić poniższe (ZPL) do postaci standardowej:

max(2x

1

+ 8x

2

)



x

1

+ 6x

2

=

1

x

1

> 0, x

2

> 0

Rozwiązanie:
Otrzymujemy (ZPL) postaci:

min(−2x

1

− 8x

2

)



x

1

+ 6x

2

=

1

x

1

> 0, x

2

> 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(2x

1

+ 3x

2

)







x

1

+ 4x

2

+ x

3

=

1

x

1

+ x

2

+ 2x

3

=

2

x

1

> 0, x

2

> 0, x

3

> 0

I faza:
Jest to zadanie w postaci standardowej. W pierwszej fazie wprowadzamy sztuczne zmienne y

1

, y

2

i formułujemy

poniższe pomocnicze (ZPL):

min(y

1

+ y

2

)







x

1

+ 4x

2

+ x

3

+ y

1

=

1

x

1

+ x

2

+ 2x

3

+ y

2

=

2

x

1

> 0, x

2

> 0, x

3

> 0, y

1

> 0, y

2

> 0

Tworzymy początkową tabelę metody sympleks:

x

1

x

2

x

3

y

1

y

2

b

Pierwsze ograniczenie (wiersz w

1

):

1

4

1

1

0

1

Drugie ograniczenie (wiersz w

2

):

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 − w

1

− w

2

. Otrzymamy wtedy:

x

1

x

2

x

3

y

1

y

2

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

~

x = [x

1

, x

2

, x

3

, y

1

, y

2

]

T

= [0, 0, 0, 1, 2]

T

(pierwsze trzy kolumny nie są jednostkowe, dlatego przyjmujemy x

1

= x

2

= x

3

= 0, pozostałe dwie są

jednostkowe - stanowią bazę, zatem wartości zmiennych y

1

= 1 i y

2

= 2 odczytujemy z ostatniej kolumny).

Wartość funkcji celu dla powyższego dopuszczalnego rozwiązania bazowego ~

x wynosi f (~

x) = 3 (niebieska liczba

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 (y

1

i y

2

) - 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

4

,

2

1

= 2

przy czym w obliczeniach bierzemy pod uwagę tylko liczby dodatnie z kolumny wprowadzanej do bazy. Wy-
bieramy z tych ilorazów najmniejszy, czyli

1
4

. Ponieważ powstał on przez dzielenie liczb w pierwszym wierszu,

więc wyrzucamy z bazy tę kolumnę, która ma jedynkę właśnie w pierwszym wierszu, czyli kolumnę związaną
ze zmienną y

1

.

4

Gdyby wszystkie liczby w kolumnie wprowadzanej do bazy były ujemne, pierwotne (ZPL) byłoby nie-
ograniczone (min f (~

x) = −∞).

Chcemy, aby teraz druga kolumna stała się kolumną jednostkową. Mnożymy zatem pierwszy wiersz przez

1
4

,

aby liczba w ramce stała się równa 1 (działanie:

1
4

w

1

):

x

1

x

2

x

3

y

1

y

2

b

1
4

1

1
4

1
4

0

1
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: w

2

− w

1

, w + 5w

1

):

x

1

x

2

x

3

y

1

y

2

b

1
4

1

1
4

1
4

0

1
4

3
4

0

7
4

−

1
4

1

7
4

−

3
4

0

−

7
4

5
4

0

−

7
4

Powyższej tabeli odpowiada dopuszczalne rozwiązanie bazowe

~

x = [x

1

, x

2

, x

3

, y

1

, y

2

]

T

=



0,

1

4

, 0, 0,

7

4



T

(kolumny: pierwsza, trzecia i czwarta nie są jednostkowe, dlatego przyjmujemy x

1

= x

3

= y

1

= 0, pozostałe dwie

są jednostkowe - stanowią bazę, zatem wartości zmiennych x

2

=

1
4

i y

2

=

7
4

odczytujemy z ostatniej kolumny).

Wartość funkcji celu dla powyższego dopuszczalnego rozwiązania bazowego ~

x wynosi f (~

x) =

7
4

(niebieska liczba

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

4

:

1

4

= 1,

7

4

:

7

4

= 1

Ilorazy są identyczne, więc możemy wyrzucić z bazy kolumnę drugą (związaną ze zmienną x

2

) lub piątą (zwią-

zaną ze zmienną y

2

). 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ą.
Mnożymy drugi wiersz przez

4
7

, aby liczba w ramce stała się równa 1 (działanie:

4
7

w

2

):

x

1

x

2

x

3

y

1

y

2

b

1
4

1

1
4

1
4

0

1
4

3
7

0

1

−

1
7

4
7

1

−

3
4

0

−

7
4

5
4

0

−

7
4

Otrzymujemy zera w trzeciej kolumnie tam, gdzie są liczby czerwone (działania: w

1

−

1
4

w

2

, w +

7
4

w

2

):

x

1

x

2

x

3

y

1

y

2

b

1
7

1

0

2
7

−

1
7

0

3
7

0

1

−

1
7

4
7

1

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 (~

x) = 2x

1

+ 3x

2

:

x

1

x

2

x

3

b

1
7

1

0

0

3
7

0

1

1

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 − 3w

1

. Otrzymamy:

x

1

x

2

x

3

b

1
7

1

0

0

3
7

0

1

1

11

7

0

0

0

Kończymy obliczenia, gdyż wszystkie liczby w ostatnim wierszu są nieujemne. Otrzymaliśmy rozwiązanie opty-
malne pierwotnego (ZPL) w punkcie ~

x = [0, 0, 1]

T

. Wartość pierwotnej funkcji celu dla powyższego dopuszczal-

nego rozwiązania bazowego ~

x wynosi f (~

x) = 0 (niebieska liczba z przeciwnym znakiem).

.

Opracował: Krzysztof Piekarski
Katedra Matematyki
Wydział Informatyki PB

6