Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

1

Metody numeryczne - laboratorium

Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

Zadanie programowania liniowego ZPL

Definiuje się N niezależnych zmiennych x

1

, x

2

, ..., x

N

wraz z liniową funkcją celu

N

N

x

a

x

a

x

a

z

0

2

02

1

01

... +

+

+

=

.

Poszukuje się maksymalnej wartości funkcji celu z przy następujących ograniczeniach:

- N podstawowych:

,

0

,...,

0

,

0

2

1

≥

≥

≥

N

x

x

x

- M=m

1

+m

2

+m

3

dodatkowych:

i

N

iN

i

i

b

x

a

x

a

x

a

≤

+

+

+

...

2

2

1

1

,

0

≥

i

b

,

1

,...,

1

m

i =

j

N

jN

j

j

b

x

a

x

a

x

a

≥

+

+

+

...

2

2

1

1

,

0

≥

j

b

,

2

1

1

,...,

1

m

m

m

j

+

+

=

k

N

kN

k

k

b

x

a

x

a

x

a

=

+

+

+

...

2

2

1

1

,

0

≥

k

b

,

3

2

1

2

1

,...,

1

m

m

m

m

m

k

+

+

+

+

=

Wektor x, który spełnia wszystkie ograniczenia nazywa się wektorem dopuszczalnym. Wektor, który

maksymalizuje funkcję celu nazywa się optymalnym wektorem dopuszczalnym. Wektor, który

reprezentuje punkt wierzchołka obszaru ograniczonego nazywa się bazowym wektorem

dopuszczalnym.

Rozwiązanie ZPL może nie istnieć z dwóch powodów:

- nie istnieją wektory dopuszczalne (ograniczenia są sprzeczne),

- nie ma wartości maksymalnej (jedna ze zmiennych może dążyć do nieskończoności).

Przykład 1

Dane jest ZPL o następujących parametrach: N=4, m

1

=2, m

2

=m

3

=1, stąd M=4. Znaleźć maksimum

funkcji

4

3

2

1

2

1

3

x

x

x

x

z

−

+

+

=

przy ograniczeniach podstawowych

0

,

0

,

0

,

0

4

3

2

1

≥

≥

≥

≥

x

x

x

x

oraz dodatkowych

9

2

1

2

0

7

2

740

2

4

3

2

1

4

3

2

4

2

3

1

=

+

+

+

≥

+

−

≤

−

≤

+

x

x

x

x

x

x

x

x

x

x

x

Rozwiązaniem tak postawionego zadania jest następujący wektor: x

1

=0, x

2

=3.33, x

2

=4.73, x

4

=0.95.

Twierdzenie 1 (Podstawowe twierdzenie optymalizacji liniowej)

Jeżeli istnieje optymalny wektor dopuszczalny, to istnieje bazowy wektor dopuszczalny, który jest

optymalny.

Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

2

Wyobraźmy sobie, że ZPL określone jest na N wymiarowej przestrzeni. Ograniczenia określają pewną

dopuszczalną podprzestrzeń, której granice są opisane hiperpłaszczyznami. Ponieważ funkcja celu

jest liniowa (ma niezerowy gradient), optymalny wektor dopuszczalny nigdy nie będzie umiejscowiony

wewnątrz podprzestrzeni (poruszając się wzdłuż gradientu funkcji celu zawsze natkniemy się na

płaszczyznę ograniczającą).

Brzeg dowolnego obszaru geometrycznego ma wymiar o jeden mniejszy niż jego wnętrze.

Analogicznie poruszając się wzdłuż gradientu rzutowanego na N-1 wymiarową płaszczyznę

ograniczającą, otrzymuje się punkt będący brzegiem tej płaszczyzny. Kontynuując ten proces

dochodzimy do sytuacji, gdy brzeg obszaru został zredukowany do punktu. Ponieważ wektor

reprezentujący ten punkt opisany jest przez N zmiennych oraz leży on na płaszczyźnie ograniczającej

obszar dopuszczalny, to jest on jednocześnie rozwiązaniem N równości wynikających ze wszystkich

ograniczeń.

Wektory dopuszczalne, które spełniają N ograniczeń równościowych nazywane są bazowymi

wektorami dopuszczalnymi i reprezentują punkty wierzchołkowe obszaru dopuszczalnego. Jeżeli

N>M, to dopuszczalny wektor bazowy ma przynajmniej N-M składowych równych zero (ponieważ

przynajmniej tyle ograniczeń będzie dopełniać N współrzędnych wektora, które muszą spełniać

ograniczenia równościowe). Oznacza to, że najwyżej M składowych wektora będzie niezerowych.

W przykładzie 1 można sprawdzić (przez podstawienie), że otrzymane rozwiązanie spełnia 3 pierwsze

ograniczenia w sposób równościowy oraz dodatkowo ograniczenie na

0

1

≥

x

. W ten sposób

optymalny wektor dopuszczalny ma 4 składowe, które spełniają 4 ograniczenia równościowe. Jest to

jednocześnie bazowy wektor dopuszczalny.

Powyższe rozumowanie pozwala na zamianę zadania optymalizacji na problem

kombinatoryczny, w którym należy stwierdzić, które N ograniczeń (ze wszystkich M+N ograniczeń)

powinno być spełnione przez wektor dopuszczalny, aby otrzymać rozwiązanie optymalne. Oznacza to

wybór wektora reprezentującego odpowiedni wierzchołek obszaru dopuszczalnego (wektora

bazowego). Rozwiązanie tego problemu otrzymuje się na przykład przez zastosowanie algorytmu

simplex.

Algorytm simplex (Dantzig, 1948)

Zakłada się, że zadanie programowania liniowego zapisane jest w postaci, w której (normalna postać

ZPL):

- występują tylko ograniczenia równościowe,

- każde ograniczenie posiada zmienną z dodatnim współczynnikiem, który występuje tylko w tym

ograniczeniu.

Jeżeli powyższe założenia nie są spełnione, to ZPL trzeba sprowadzić do takiej postaci.

Dzięki powyższym założeniom można wybrać tzw. zmienne bazowe, względem których zostaną

rozwiązane M równania reprezentujące ograniczenia równościowe. Pozostałe N-M zmiennych nazywa

się zmiennymi niebazowymi. Funkcja celu zapisana jest wyłącznie za pomocą zmiennych

niebazowych (w tak postawionym problemie każdą funkcję celu można przedstawić za pomocą

zmiennych niebazowych przez podstawienie).

Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

3

Przykład 2 (postać normalna ZPL)

Dane jest ZPL o następujących parametrach: N=4, m

1

=2, m

2

=m

3

=0, stąd M=2. Znaleźć maksimum

funkcji

3

2

4

2

x

x

z

−

=

przy ograniczeniach podstawowych

0

,

0

,

0

,

0

4

3

2

1

≥

≥

≥

≥

x

x

x

x

oraz dodatkowych

3

2

4

3

2

1

4

3

8

6

2

x

x

x

x

x

x

−

+

=

+

−

=

Zmienne bazowe przy tej postaci to x

1

, x

4

, a niebazowe to x

2

, x

3

. Z postaci normalnej ZPL w każdym

momencie można bardzo łatwo odczytać dopuszczalny wektor bazowy (który niekoniecznie jest

optymalny). Robi się to podstawiając wartość zero za wszystkie zmienne niebazowe. W ten sposób

otrzymuje się wektor, dla którego ograniczenia równościowe są spełnione. Metoda simplex polega na

przeprowadzeniu wymienianiu zmiennych bazowych z niebazowymi tak, aby zachowane były

ograniczenia oraz wartość funkcji celu rosła. Zadanie w postaci normalnej może zostać zapisane w

następującej tabeli:

x

2

x

3

z

0

2

-4

x

1

2

-6

1

x

4

8

3

-4

Ustala się wartość zmiennych niebazowych na zero. Powstaje pytanie, jak zmieni się wartość funkcji

celu, gdy jedna ze zmiennych bazowych zostanie zwiększona (przy pozostałych cały czas równych 0).

Jeżeli współczynniki przy tej zmiennej są dodatnie, to przy jej zwiększaniu również funkcja celu

zwiększy swoją wartość. Dlatego rozpatrujemy tylko kolumny, w których współczynniki przy zmiennych

niebazowych są dodatnie. Jeżeli takiej kolumny nie ma, to znaczy, że funkcja celu nie może dalej

wzrosnąć, czyli jest już maksymalna.

Dla danej kolumny (dla której współczynnik jest dodatni) pytamy, jak bardzo możemy

zwiększyć wartość danej zmiennej, aby zmienne bazowe nie stały się ujemne (co jest niedozwolone

ze względu na podstawowe ograniczenia). Jeżeli element tablicy na przecięciu analizowanej kolumny i

danej zmiennej bazowej jest dodatni, to znaczy, że nie ma ograniczeń. Jeżeli wszystkie elementy w

każdej kolumnie niebazowej są dodatnie, to znaczy, że zadanie jest nieograniczone.

Jeżeli jeden z elementów analizowanej kolumny jest ujemny (element centralny), to będzie on

miał wpływ na maksymalne możliwe zwiększenie wartości elementu niebazowego. Granica ta

określona jest przez podzielenie składowej wektora bazowego przez element centralny. Największe

ograniczenie wprowadzi najmniejsza wartość wyznaczona dla każdego rozpatrywanego wiersza.

Ograniczenie to określa się dla każdej z kolumn, która ma dodatni współczynnik. Jako kolumnę

centralną można wybrać tą, której zamiana powoduje powiększenie funkcji celu o największą wartość.

W ten sposób wybrany zostaje element centralny.

Zmienne niebazowe x

2

, x

3

Zmienne bazowe x

1

, x

4

Funkcja celu

Aktualna wartość f. celu

Element centralny y

rk

Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

4

W rozpatrywanym przykładzie jedynie kolumna x

2

ma niezerowy współczynnik o wartości 2.

Dodatkowo jest tylko jeden element ujemny w tej kolumnie (o wartości -6), który zostanie elementem

centralnym. Wartość w kolumnie stałej wynosi 2. Stąd takie przestawienie pozwoli, aby składowa x

2

wzrosła o 2/6, natomiast wartość funkcji celu wzrośnie o (2*2)/6.

Trzecim krokiem procedury jest wykonanie zaplanowanej zamiany. Oznacza to, że wartość

wybranego elementu bazowego zostanie zmniejszona do 0, przez co stanie się on elementem

niebazowym. Natomiast poprzedni element niebazowy wzrośnie o zadaną wartość (w tym wypadku o

1/3) i zostanie nowym elementem bazowym. Wartość funkcji celu również wzrośnie. Wymaga to

aktualizacji pozostałych współczynników ze względu na następującą zamianę zmiennych:

3

2

1

6

2

x

x

x

+

−

=

→

3

1

2

6

1

6

1

3

1

x

x

x

+

−

=

3

1

3

3

1

4

2

7

2

1

9

4

6

1

6

1

3

1

3

8

x

x

x

x

x

x

−

−

=

−













+

−

+

=

Aktualizacja funkcji celu:

3

1

3

3

1

3

2

3

11

3

1

3

2

4

6

1

6

1

3

1

2

4

2

x

x

x

x

x

x

x

z

−

−

=

−













+

−

=

−

=

Powyższe równania tworzą nową tabelę sympleksową:

x

1

x

3

z

2/3

-1/3

-11/3

x

2

1/3

-1/6

1/6

x

4

9

-1/2

-7/2

Powyższa procedura jest powtarzana tak długo, aż istnieją zmienne niebazowe, które mają

dodatnie współczynniki. W powyższym przykładzie nie ma możliwości dalszego zwiększania funkcji

celu. Rozwiązanie może być odczytane wprost z tablicy:

9

,

0

,

3

1

,

0

4

3

2

1

=

=

=

=

x

x

x

x

Optymalna wartość funkcji celu wynosi z=1/3.

Kolejne kroki algorytmu simplex (dla tablicy składającej się z elementów a

ij

):

1.

Określ element centralny dla kolejnej iteracji a

rk

(znajduje się on na przecięciu

kolumny k oraz wiersza r).

2.

Wiersz r-ty podziel przez minus element centralny -a

rk.

3.

Do każdego i-tego z pozostałych wierszy dodaj wiersz centralny pomnożony przez

a

ik.

4.

Oryginalną kolumnę k-tą podziel przez element centralny a

rk.

5.

Element centralny a

rk

zastąp jego odwrotnością 1/a

rk.

6.

Powtarzaj procedurę dopóki możliwe jest określenie elementu centralnego.

8+3*(1/3)=9

-4+3*(1/6)=-7/2

-4+2*(1/6)=-11/3

2/(-6)=-1/3

Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

5

Może się zdarzyć, że jeden z elementów wektora bazowego jest zerowy. Jest to tak zwany

zdegenerowany wektor dopuszczalny. W takim wypadku należy tak długo wymieniać zdegenerowaną

składową bazową z niebazową, aż otrzyma się wektor niezdegenerowany.

Sprowadzanie problemu do postaci normalnej

Zamiana na ograniczenia równościowe

Postać normalna ZPL wymaga, aby występowały jedynie ograniczenia równościowe. Jeżeli w zadaniu

występuje inny rodzaj ograniczeń, możliwe jest sprowadzenie ich do ograniczeń równościowych przez

wprowadzenie tak zwanych zmiennych dopełniających. Ich znak zależy od rodzaju ograniczenia w

zadaniu początkowym. Dla przykładu 1 ograniczenia w postaci normalnej przyjmują postać:

9

2

1

2

0

7

2

740

2

4

3

2

1

3

4

3

2

2

4

2

1

3

1

=

+

+

+

=

−

+

−

=

+

−

=

+

+

x

x

x

x

y

x

x

x

y

x

x

y

x

x

Znajdowanie początkowego dopuszczalnego wektora bazowego

Aby możliwe było zapoczątkowanie metody simplex, konieczne jest określenie M wektorów bazowych,

czyli znalezienie dowolnego dopuszczalnego wektora bazowego. W tym celu wprowadza się do

zadania M dodatkowych zmiennych dopełniających (sztucznych). Rozpatrywany przykład przyjmuje

postać

4

3

2

1

4

3

4

3

2

3

2

4

2

2

1

3

1

1

9

2

2

1

7

2

2

740

x

x

x

x

z

y

x

x

x

z

y

x

x

z

y

x

x

z

−

−

−

−

=

+

−

+

−

=

−

+

−

=

−

−

−

=

Tak określone zadanie będzie równoważne zadaniu poprzedniemu tylko wtedy, gdy wszystkie

zmienne z

i

są równe 0. Stąd w pierwszej fazie rozwiązywania problemu wprowadza się dodatkową

funkcję celu określoną jako













+

−

−

+

−

−

−

−

=

−

−

−

−

≡

3

2

1

4

3

2

1

4

3

2

1

4

2

4

2

2

1

749

'

y

y

y

x

x

x

x

z

z

z

z

z

Następnie uruchamia się procedurę simplex dla tak zdefiniowanego zadania. Celem jest

maksymalizacja pomocniczej funkcji celu z`, która powinna przyjąć wartość zero dla pewnego

wierzchołka bazowego. Jeżeli taki wierzchołek istnieje (istnieje przynajmniej jeden dopuszczalny

wektor bazowy), to wszystkie zmienne pomocnicze staną się zmiennym niebazowymi. Można je wtedy

pominąć, a otrzymana tablica opisuje początkowe zadanie w postaci normalnej ze zmiennymi x

i

, y

i

z

określonym dopuszczalnym wektorem bazowym.

Tablica sympleksowa opisująca przykładowe zadanie pomocnicze rozwiązywane w pierwszej fazie

wygląda następująco:

Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

6

x

1

x

2

x

3

x

4

y

1

y

2

y

3

z

0

1

1

3

-1/2

0

0

0

z

1

740

-1

0

-2

0

-1

0

0

z

2

0

0

-2

0

7

0

-1

0

z

3

1/2

0

-1

1

-2

0

0

1

z

4

9

-1

-1

-1

-1

0

0

0

z’

-749,5

2

4

2

-4

1

1

-1

Jest to więc tylko inny sposób zapisania zadania początkowego. Ostateczna postać tablicy dla

rozpatrywanego przykładu (po wykreśleniu zmiennych pomocniczych) przyjmuje postać:

x

1

y

2

y

3

z

17.03

-0.95

-0.05

-1.05

x

2

3.33

-0.35

-0.15

0.35

x

3

4.73

-0.55

0.05

-0.45

x

4

0.95

-0.10

0.10

0.10

y

1

730.55

0.10

-0.10

0.90

Pierwsza kolumna tablicy zawiera optymalny wektor będący rozwiązaniem zadania wraz z wartością

funkcji celu osiąganą dla tego punktu. Zmienne, które są niebazowe przyjmują w rozwiązaniu wartość

zero. Zmienne dopełniające o wartości zero reprezentują ograniczenia, które są spełnione jako

równości. Wartość zmiennych dopełniających określa, do jakiej wartości odpowiadające im

ograniczenia nierównościowe są spełnione.

Ć

wiczenie 9,10: Programowanie liniowe – metoda simplex

7

Zadania laboratoryjne

Napisać program rozwiązujący zadanie programowania liniowego. Za pomocą napisanego programu

rozwiązań następujące problemy.

a)

3

2

1

2

3

max

x

x

x

z

+

+

=

przy ograniczeniach:

0

,

0

,

0

3

2

1

≥

≥

≥

x

x

x

4

2

3

3

2

1

=

+

+

x

x

x

5

4

2

3

2

1

=

+

−

x

x

x

b)

4

3

2

1

4

3

2

max

x

x

x

x

z

+

−

+

=

przy ograniczeniach:

0

,

0

,

0

,

0

4

3

2

1

≥

≥

≥

≥

x

x

x

x

1

2

2

4

2

1

=

+

+

x

x

x

3

2

3

4

3

2

=

+

+

x

x

x

c)

2

1

11

7

max

x

x

z

+

=

przy ograniczeniach:

0

,

0

2

1

≥

≥

x

x

20

4

2

21

3

3

2

1

2

1

≤

+

≤

+

x

x

x

x

d)

2

1

max

x

x

z

−

=

przy ograniczeniach:

0

,

0

2

1

≥

≥

x

x

2

2

2

1

≥

− x

x

5

2

1

≤

+ x

x

Dla jednego z przykładów pokazać kolejne operacje wykonywane na tablicy sympleksowej.

Literatura

[1] Press W., Teukolsky S., Vetterling W., Flannery B. Numerical Recipes in C, Cambridge University

Press, 2002

[2] Findeisen W., Szymanowski J. Teoria i metody obliczeniowe optymalizacji, PWN, 1980

[3] Stachurski A., Wierzbicki A.P., Podstawy optymalizacji, WPW, 1999