Rozdział 2

Programowanie liniowe

2.1

Formalizacja zadań programowania liniowego

Zacznijmy od przykładowego zadania sformułowanego w poniższym przykładzie.

Przykład 1. Pewien mały zakład produkuje dwa rodzaje gipsowych krasnali. Do wypro-

dukowania jednego krasnala każdego rodzaju potrzeba 5 kilogramów gipsu. Po wyjęciu

„surowego” krasnala z formy maluje się go używając czerwonego i niebieskiego lakieru. Na

pomalowanie jednego krasnala pierwszego typu potrzeba 0, 1 litra lakieru czerwonego i 0, 3

litra lakieru niebieskiego, zaś na pomalowanie jednego krasnala drugiego typu potrzeba

0, 3 litra lakieru czerwonego i 0, 2 litra lakieru niebieskiego. Dzienne zużycie surowców jest

ograniczone i nie może przekroczyć 60 kg gipsu i 3 litrów lakieru obu rodzajów. Poza tym,

ze względu na zawartą umowę handlową, należy wyprodukować dziennie co najmniej dwa

krasnale drugiego typu. Zysk ze sprzedaży jednego krasnala pierwszego rodzaju wynosi 40

złotych, a ze sprzedaży krasnala drugiego rodzaju – 30 złotych. Znaleźć plan produkcji kra-

snali obu rodzajów zapewniający maksymalny dzienny zysk, przy założeniu że cała dzienna

produkcja zostanie sprzedana.

Pierwszym krokiem na drodze do uzyskania odpowiedzi na pytanie: ile krasnali każ-

dego rodzaju należy dziennie wyprodukować, aby zysk z ich sprzedaży był maksymalny,

jest formalizacja zadania, tzn. stworzenie modelu matematycznego uwzględniającego

wszystkie dane zawarte w zadaniu. Przedstawimy teraz kolejne etapy konstrukcji takiego

modelu. Posłużymy się danymi z powyższego zadania, ale w każdym innym przypadku

sposób postępowania jest analogiczny.

1) Określenie zmiennych decyzyjnych

Oznaczmy:

x

1

— liczba produkowanych dziennie krasnali pierwszego rodzaju (w sztukach),

1

x

2

— liczba produkowanych dziennie krasnali drugiego rodzaju (w sztukach).

Zmienne x

1

i x

2

nazywamy zmiennymi decyzyjnymi. Ich wartości są takie, że para

(x

1

, x

2

) należy do pewnego zbioru, który zostanie określony poniżej.

2) Zdefiniowanie funkcji celu

Celem zadania jest znalezienie takich wartości zmiennych decyzyjnych x

1

i x

2

(czyli usta-

lenie liczby produkowanych dziennie krasnali obu typów), dla których maksymalny jest

zysk otrzymany ze sprzedaży x

1

krasnali pierwszego typu i x

2

krasnali drugiego typu. Zysk

ze sprzedaży jednego krasnala pierwszego typu wynosi 40 złotych, a ze sprzedaży krasnala

drugiego rodzaju – 30 złotych, wobec czego zysk ze sprzedaźy całodziennej produkcji wyno-

si 40x

1

+ 30x

2

złotych. W takim razie należy znaleźć takie wartości zmiennych decyzyjnych

(spełniające warunki narzucone w zadaniu), dla których funkcja

f (x

1

, x

2

) = 40x

1

+ 30x

2

przyjmie największą wartość. Tak określoną funkcję nazywamy funkcją celu, a konieczność

znalezienia jej największej wartości zapisujemy następująco:

f (x

1

, x

2

) = 40x

1

+ 30x

2

→ max .

3) Zapisanie ograniczeń

Zmienne decyzyjne mogą przybierać tylko takie wartości, dla jakich będą spełnione wa-

runki opisane w zadaniu. Warunki takie nazywamy ograniczeniami. W rozpatrywanym

przykładzie mamy trzy ograniczenia surowcowe (ograniczone zapasy gipsu i lakierów:: czer-

wonego i niebieskiego) i jedno ograniczenie wynikające z zawartej umowy. Ograniczenia te

zapisujemy w postaci układu nierówności:

5x

1

+ 5x

2

¬ 60,

[kg]

(ograniczenie zapasów gipsu)

0, 1x

1

+ 0, 3x

2

¬ 3,

[l]

(ograniczenie zapasów czerwonego lakieru)

0, 3x

1

+ 0, 2x

2

¬ 3,

[l]

(ograniczenie zapasów niebieskiego lakieru)

x

2

­ 2.

[szt.]

(ograniczenie wynikające z umowy handlowej)

Przy kolejnych ograniczeniach podane są jednostki, w jakich wyrażana jest liczba stojąca

po prawej stronie nierówności. Jak widać, różne ograniczenia mogą być wyrażane w różnych

jednostkach.

Zbiór D wszystkich rozwiązań powyższego układu nierówności jest wielokątem leżącym

w pierwszej ćwiartce układu współrzędnych. Para liczb x

1

, x

2

spełnia wszystkie te nierów-

ności wtedy i tylko wtedy, gdy punkt (x

1

, x

2

) należy do zbioru D. Zbiór ten nazywamy

zbiorem rozwiązań dopuszczalnych.

2

4) Zapisanie warunków brzegowych

Każda dopuszczalna wartość zmiennej decyzyjnej jest nieujemna, co wynika z natury zagad-

nienia — nie można wyprodukować ujemnej liczby krasnali. W konsekwencji do ograniczeń

dopisujemy warunki brzegowe:

x

1

­ 0,

x

2

­ 0.

Przytoczony powyżej przykład jest typowym zadaniem programowania liniowego (w

skrócie: ZPL). Każde zadanie tego typu, z danymi podanymi w postaci opisowej, można

sformalizować określając następujące jego składowe:

1) Zmienne decyzyjne reprezentujące poszukiwane wielkości. Dla ich oznaczenia bę-

dziemy w dalszym ciągu posługiwać się symbolami x

1

, x

2

, . . ., x

n

.

2) Funkcja celu, która jest funkcją liniową postaci:

f (x

1

, x

2

, . . . , x

n

) = c

1

x

1

+ c

2

x

2

+ . . . + c

n

x

n

,

gdzie c

1

, c

2

, . . ., c

n

są ustalonymi liczbami rzeczywistymi o wartościach wynikających

z treści zadania, przy czym przynajmniej jedna z tych liczb jest różna od 0 Celem

rozwiązania ZPL jest znalezienie takich wartości zmiennych decyzyjnych, dla których

funkcja celu f osiągnie wartość największą albo najmniejszą. Fakt ten zapisujemy

umieszczając strzałkę „→” i jeden z dwóch symboli: max lub min z prawej strony

wzoru funkcji celu:

f (x

1

, x

2

, . . . , x

n

) = c

1

x

1

+ c

2

x

2

+ . . . + c

n

x

n

→ max

(odpowiednio : min).

W pierwszym przypadku mówimy o ZPL typu maksimum (w skrócie: ZPL(max)), w

drugim — o ZPL typu minimum (w skrócie: ZPL(min)).

3) Ograniczenia zapisywane w postaci układu nierówności liniowych nieostrych (tzn.

typu „¬” lub „­”) lub równości liniowych:

a

11

x

1

+ a

12

x

2

+ . . . + a

1n

x

n

¬

b

1

,

. . .

a

k1

x

1

+ a

k2

x

2

+ . . . + a

kn

x

n

¬

b

k

,

a

k+1 1

x

1

+ a

k+1 2

x

2

+ . . . + a

k+1 n

x

n

­

b

k+1

,

. . .

a

l1

x

1

+ a

l2

x

2

+ . . . + a

ln

x

n

­

b

l

,

a

l+1 1

x

1

+ a

l+1 2

x

2

+ . . . + a

l+1 n

x

n

=

b

l+1

,

. . .

a

m1

x

1

+ a

m2

x

2

+ . . . + a

mn

x

n

=

b

m

(2.1)

3

gdzie współczynniki a

ij

oraz b

i

są ustalonymi liczbami rzeczywistymi o wartościach

wynikających z treści zadania. W dalszym ciągu będziemy zawsze zakładać, że

b

i

­ 0

dla każdego

i = 1, 2, . . . , m.

Gdyby w ograniczeniu zapisanym zgodnie z warunkami zadania powyższy warunek

nie zachodził, należy obie strony nierówności pomnożyć przez −1.

4) Warunki brzegowe, które zawsze mają taką samą postać:

x

1

­ 0,

x

2

­ 0,

. . . ,

x

n

­ 0.

2.2

Podstawowe postaci ZPL

Zadania programowania liniowego dzielimy ze względu na rodzaj optymalizacji funkcji celu

(ZPL typu maksimum i ZPL typu minimum, o których była mowa wyżej) oraz ze względu

na postać nierówności opisujących ograniczenia. Pamiętamy przy tym o umowie, że prawe

strony tych nierówności b

i

są liczbami nieujemnymi. Wyróżniamy trzy zasadnicze rodzaje

takich zadań:

1) ZPL w postaci standardowej to zadanie, w którym wszystkie ograniczenia dane

są nierównościami typu „¬”,

2) ZPL w postaci kanonicznej to zadanie, w którym wszystkie ograniczenia dane są

równościami,

3) ZPL w postaci ogólnej lub mieszanej to zadanie, w którym występują ogranicze-

nia różnych typów.

ZPL w postaci kanonicznej może zostać rozwiązane przy użyciu algorytmu sympleks, któ-

ry zostanie omówiony w dalszej części wykładu. Zadania programowania liniowego pozo-

stałych dwóch rodzajów mogą zostać przekształcone do równoważnych zadań w postaci

kanonicznej. Przekształcenie to polega na dodaniu w każdej nierówności tzw. zmiennej

bilansującej, która wystąpi tylko w tym ograniczeniu, i wprowadzeniu tej zmiennej do

funkcji celu ze współczynnikem 0. W zależności od postaci nierówności w ograniczeniu

postępujemy następująco:

4

• ograniczenie typu:

a

i1

x

1

+ a

i2

x

2

+ . . . + a

in

x

n

¬ b

i

zastępujemy ograniczeniem

a

i1

x

1

+ a

i2

x

2

+ . . . + a

in

x

n

+ s

i

= b

i

,

gdzie s

i

­ 0 jest właśnie zmienną bilansującą swoistą dla danego ograniczenia —

numer ograniczenia jest indeksem tej zmiennej;

• ograniczenie typu:

a

i1

x

1

+ a

i2

x

2

+ . . . + a

in

x

n

­ b

i

zastępujemy ograniczeniem

a

i1

x

1

+ a

i2

x

2

+ . . . + a

in

x

n

− s

i

= b

i

,

gdzie s

i

­ 0 jest właśnie zmienną bilansującą.

W obu przypadkach do funkcji celu dodajemy składnik postaci 0 · s

i

:

c

1

x

1

+ c

2

x

2

+ . . . + c

n

x

n

+ 0s

i

→ max (min).

Należy zwrócić uwagę na następujące fakty (przyjmujemy oznaczenia ze wzoru (2.1)):

1) Oprócz zmiennych decyzyjnych, które występowały w pierwotnym ZPL, w zmodyfiko-

wanym zadaniu pojawi się tyle nowych zmiennych (bilansujących), ile ograniczeń w po-

staci nierówności zawiera zadanie pierwotne. Poza tym każda z wprowadzonych zmiennych

bilansujących występuje tylko w jednym ograniczeniu zmodyfikowanego zadania ze współ-

czynnikiem +1 lub −1.

2) Dowolne dopuszczalne (a więc również optymalne) rozwiązanie

(x

1

, . . . , x

n

, s

1

, . . . , s

l

)

zadania zmodyfikowanego wyznacza dopuszczalne rozwiązanie zadania pierwotnego

(x

1

, . . . , x

n

),

które można otrzymać poprzez odrzucenie wartości zmiennych bilansujących. Wartości od-

powiednich funkcji celu dla obu rozwiązań są takie same, gdyż w zmodyfikowanej funkcji

celu współczynniki przy zmiennych bilansujących są równe 0. W konsekwencji optymalne

rozwiązanie zadania zmodyfikowanego wyznacza optymalne rozwiazanie zadania pierwot-

nego.

5

3) Jeżeli

(x

∗
1

, . . . , x

∗
n

, s

∗
1

, . . . , s

∗
l

)

jest rozwiązaniem optymalnym zadania zmodyfikowanego, to dla każdego i ¬ l:

s

∗
i

=








b

i

−

n

X

j=1

c

j

x

∗
j








,

a więc s

∗
i

jest równe wartości bezwzględnej różnicy pomiędzy wartościami prawej i lewej

strony i-tego ograniczenia w zadaniu pierwotnym, obliczonymi dla rozwiązania optymal-

nego (x

∗
1

, . . . , x

∗
n

).

Przykład 2. Rozważmy następujące ZPL w postaci ogólnej:

f (x

1

, x

2

) = 3x

1

+ 2x

2

→ max

x

1

+ x

2

¬

11,

x

1

¬

6,

x

1

+ 3x

2

­

9,

x

j

­ 0,

j = 1, 2.

(2.2)

Wprowadzając w opisany powyżej sposób do każdego ograniczenia zmienną bilansującą s

i

,

i = 1, 2, 3, zapisujemy ZPL (2.2) w postaci kanonicznej:

f (x, s) = 3x

1

+ 2x

2

+ 0s

1

+ 0s

2

+ 0s

3

→ max

x

1

+ x

2

+ s

1

=

11,

x

1

+ s

2

=

6,

x

1

+ 3x

2

− s

3

=

9,

x

j

­ 0,

j = 1, 2,

s

i

­ 0,

i = 1, 2, 3,

(2.3)

gdzie dla wygody zapisu przyjmujemy oznaczenia: x = (x

1

, x

2

) oraz s = (s

1

, s

2

, s

3

).

Zauważmy, że ograniczenia w ZPL (2.3) tworzą układ trzech równań z pięcioma nie-

wiadomymi. Nie jest to jednak układ równań w postaci bazowej bo macierz główna tego

układu ma postać:








1 1 1 0

0

1 0 0 1

0

1 3 0 0 −1








,

w której odnajdujemy tylko dwie kolumny macierzy jednostkowej I

3

(są to kolumny trzecia

i czwarta), ale nie ma w niej kolumny








0

0

1








.

6

Nie można poprawić tej sytuacji poprzez pomnożenie obu stron trzeciego ograniczenia

przez −1, bo wtedy prawa strona w tym ograniczeniu stałaby się liczbą ujemną. Istnieje

jednak inny sposób na to, aby ograniczenia w zmodyfikowanym zadaniu tworzyły bazowy

układ równań liniowych z nieujemnymi prawymi stronami. Polega on na wprowadzeniu do

ograniczenia typu:

a

i1

x

1

+ a

i2

x

2

+ . . . + a

in

x

n

­ b

i

zmiennej bilansującej s

i

ze znakiem minus oraz, dodatkowo, zmiennej sztucznej t

i

ze

znakiem plus: zastępujemy ograniczeniem

a

i1

x

1

+ a

i2

x

2

+ . . . + a

in

x

n

− s

i

+ t

i

= b

i

,

gdzie t

i

­. Funkcję celu należy zmodyfikować w taki sposób, żeby wszystkie zmienne sztucz-

ne w końcowym rozwiązaniu optymalnym (o ile takie istnieje) miały wartość 0. Można to

osiągnąć poprzez wprowadzenie do funkcji celu składnika:

• 0s

i

− M t

i

w przypadku ZPL(max),

• 0s

i

+ M t

i

w przypadku ZPL(min),

gdzie M oznacza pewną dostatecznie dużą liczbę dodatnią. Istotnie, rozpatrzmy pierwszy

przypadek. Jeżeli otrzymamy rozwiązanie dopuszczalne (x, s, t)(x, s, t) ZPL zmodyfikowa-

nego w powyższy sposób i w tym rozwiązaniu t

i

> 0, to możemy poprawić to rozwiązanie

przyjmując t

inowe

= 0. Wówczas wartość funkcji celu wzrośnie o M t

i

> 0, a więc roz-

wiązanie ze zmienną sztuczną t

i

> 0 nie może być rozwiązaniem optymalnym ZPL(max).

Podobne rozumowanie uzasadnia sensowność opisanej modyfikacji funkcji celu w przypadku

ZPL(min).

Pomysł z wprowadzaniem zmiennych sztucznych ma zastosowanie także w przypadku,

gdy wśród ograniczeń zadania pierwotnego znajdują się również warunki dane przez rów-

ności. Oczywiście, formalnie nie ma powodu, aby takie warunki przekształcać. Ale jeżeli

chcemy z ograniczeniem danym w postaci równości związać zmienną speczyficzną tylko dla

tego warunku, należy warunek ten zmodyfikować przez wprowadzenie sztucznej zmiennej,

która w rozwiązaniu optymalnym będzie miała wartość 0. Dodanie takiej zmiennej gwa-

rantuje, że w macierzy współczynników układu równań liniowych będących ograniczeniami

zmodyfikowanego ZPL znajdą się wszystkie kolumny macierzy jednostkowej I

m

.

Przykład 3. Uwzględniając powyższą procedurę ZPL (2.2) z poprzedniego przykładu mo-

7

dyfikujemy następująco:

f (x, s) = 3x

1

+ 2x

2

+ 0s

1

+ 0s

2

+ 0s

3

− M t

3

→ max

x

1

+ x

2

+ s

1

=

11,

x

1

+ s

2

=

6,

x

1

+ 3x

2

− s

3

+ t

3

=

9,

x

j

­ 0,

j = 1, 2,

s

i

­ 0,

i = 1, 2, 3,

t

3

­ 0,

(2.4)

Przykład 4. Zmienimy teraz ZPL (2.2) z dodając jedno ograniczenie w postaci równości:

f (x

1

, x

2

) = 3x

1

+ 2x

2

→ max

x

1

+ x

2

¬

11,

x

1

¬

6,

x

1

+ 3x

2

­

9,

−2x

1

+ 3x

2

=

0,

x

j

­ 0,

j = 1, 2.

(2.5)

Wprowadzając zmienne bilansujące i sztuczne otrzymujemy postać kanoniczną tego ZPL:

f (x, s) = 3x

1

+ 2x

2

+ 0s

1

+ 0s

2

+ 0s

3

− M t

3

− M t

4

→ max

x

1

+ x

2

+ s

1

=

11,

x

1

+ s

2

=

6,

x

1

+ 3x

2

− s

3

+ t

3

=

9,

−2x

1

+ 3x

2

+ t

4

=

0,

x

j

­ 0,

j = 1, 2,

s

i

­ 0,

i = 1, 2, 3,

t

k

­ 0,

j = 3, 4.

(2.6)

Macierz współczynników ZPL (2.6) zawiera wszystkie kolumny macierzy jednostkowej I

4

,

a więc ograniczenia tego zadania tworzą bazowy układ równań liniowych.

Postać ZPL, w której wprowadzono (w sposób opisany powyżej) zmienne bilansujące

oraz sztuczne bedziemy nazywać bazową postacią kanoniczną ZPL.

2.3

Istnienie rozwiązań ZPL

Zbiór rozwiązań dopuszczalnych ZPL może być zbiorem pustym. W takim przypadku zada-

nie nazywamy sprzecznym i oczywiście nie rozwiązujemy go. W dalszym ciągu będziemy

więc zakładać, że rozważane ZPL jest niesprzeczne, czyli D 6= ∅.

8

Rozważmy ponownie ZPL w postaci ogólnej (2.1). Niepusty zbiór rozwiązań dopusz-

czalnych D tego zadania jest zawarty w pierwszym ortancie układu współrzędnych w R

n

:

R

n
+

= {(x

1

, x

2

, . . . , x

n

) : ∀

j=1, 2, ..., n

x

j

­ 0 }

i jest częścią wspólną skończonej ilości półprzestrzeni ograniczonych hiperpłaszczyznami

zawartymi w R

n

. Konsekwencją tych uwag jest następujące twierdzenie.

Twierdzenie 1. Zbiór D rozwiązań dopuszczalnych niesprzecznego ZPL (2.1) jest do-

mkniętym (wielowymiarowym) wielościanem wypukłym o skończonej liczbie wierzchołków

zawartym w pierwszym ortancie układu współrzędnych.

Uwaga 1. Zbiór D może być ograniczony lub nie. W pierwszym przypadku, wobec jego

domkniętości, jest zbiorem zwartym i z twierdzenia Weierstrassa wynika, że funkcja celu,

która jest ciągła (jako liniowa), przyjmuje na zbiorze D swoje ekstrema globalne. W drugim

przypadku funkcja celu może nie mieć ekstremów na zbiorze D, a co za tym idzie ZPL (2.1)

może nie mieć rozwiązania pomimo, że zbiór rozwiązań dopuszczalnych nie jest pusty.

Przykład 5. Jeżeli f (x

1

, x

2

) = x

1

− x

2

i D = R

2
+

jest pierwszą ćwiartką układu współ-

rzędnych, to funkcja f nie osiąga swoich kresów na zbiorze D, bo np. wartości funcji celu

dążą do +∞ wzdłuż półprostej {(2t, t) : t ­ 0} oraz dążą do do −∞ wzdłuż półprostej

{(t, 2t) : t ­ 0} dla t → ∞.

Zgodnie z poczynionym wcześniej założeniem przynajmniej jeden współczynnik c

j

linio-

wej funkcji celu jest różny od 0. Wynika stąd, że przynajmniej jedna pochodna cząstkowa

funkcji f jest różna od zera, a więc funkcja f nie osiaga ekstremum lokalnego (i, tym bar-

dziej, globalnego) wewnątrz obszaru D. Jeżeli funkcja f osiąga największą (lub najmniejszą)

wartość w jakimś punkcie x

∗

∈ D, to x

∗

leży na brzegu tego obszaru. Przypuśćmy, że x

∗

jest

punktem wewnętrzym pewnej ściany S wielościanu D. Wtedy obcięcie funcji f do ściany

S jest funkcją liniową powiększoną o pewną stałą. Jeżeli funkcja ta jest stała na ścianie

S, to istnieje wierzchołek tej ściany, w którym funkcja f osiąga największą (najmniejszą)

wartość. Jeżeli obcięcie funkcji f do S nie jest funkcją stałą, to poprzedni argument daje

sprzeczność z założeniem, że punkt x

∗

jest punktem wewnętrznym ściany S. Wtedy punkt

ten leży na brzegu tej ściany. Indukcyjne zastosowanie przytoczonego argumentu prowa-

dzi do wniosku, że funkcja f osiąga ekstremum w pewnym wierzchołku wielościanu D.

Podsumowując zachodzi twierdzenie.

Twierdzenie 2. Jeżeli funcja celu f ZPL (2.1) osiąga maksimum (odpowiednio: minimum)

na zbiorze D, to istneje wierzchołek wielościanu D, w którym to maksimum (odpowiednio:

minimum) jest osiągane.

9

Wniosek 1. Jeżeli niepusty zbiór rozwiązań dopuszczalnych D jest ograniczony, to istnieją

wierzchołki x

max

i x

min

wielościanu D takie, że

f (x

max

) = max{f (x) : x ∈ D} i f (x

min

) = min{f (x) : x ∈ D}.

Załóżmy teraz, że funkcja celu osiąga swoje maksimum f

max

w dwóch wierzchołkach x

1

i x

2

wielościanu D. Wierzchołki te leżą na tej samej poziomicy

{x ∈ D : f(x) = f

max

}

funkcji f , a więc odcinek o końcach x

1

i x

2

zawiera się w tej poziomicy. Oznacza to,

że w każdym punkcie tego odcinka funkcja celu przyjmuje wartość f

max

. Wynika stąd

następujące twierdzenie.

Twierdzenie 3. Jeżeli funkcja celu f osiąga swoją największą (odpowiednio: najmniejszą)

wartość w dwóch różnych wierzchołkach x

1

i x

2

wielościanu D, to osiąga ją również w

każdym punkcie

x = tx

1

+ (1 − t)x

2

,

t ∈ [0, 1].

2.4

Rozwiązywanie ZPL metodą geometryczną

Zajmijmy się teraz szczególnym przypadkiem (niesprzecznego) ZPL z dwiema zmiennymi

decyzyjnymi. Z twierdzenia 1 wynika, że zbiór rozwiązań dopuszczalnych D takiego za-

dania jest wielokątem wypukłym zawartym w pierwszej ćwiartce układu współrzędnych.

Obszar ten może zostać narysowany w układzie współrzędnych w R

2

jako część wspólna

półpłaszczyzn opisanych ograniczeniami i warunkami brzegowymi. Wierzchołki wielokąta

D można wyznaczyć znajdując punkty przecięcia prostych, które są brzegami odpowiednich

półpłaszczyzn.

Jeżeli wielokąt D jest ograniczony, to można znaleźć wszystkie jego wierzchołki, obliczyć

w nich wartości funkcji celu, a następnie z obliczonych wartości wybrać liczbę największą

(w przypadku ZPL(max)) lub najmniejszą (w przypadku ZPL(min)) — odpowiedni wierz-

chołek wyznacza rozwiązanie optymalne rozważanego ZPL.

W przypadku, gdy wielokąt D nie jest ograniczony, rozwiazanie optymalne ZPL może

nie istnieć. W celu sprawdzenia, czy rozwiązanie istnieje i, ewentualnego, znalezienia tego

rozwiazania należy rozważyć rodzinę poziomic funkcji celu f , czyli zbiorów zdefiniowanych

następująco:

W

p

(f ) +

n

(x

1

, x

2

) ∈ R

2

: f (x

1

, x

2

) = p

o

dla

p ∈ R.

10

Przyjmijmy dla ustalenia uwagi, że rozwiązywane ZPL polega na maksymalizowaniu funkcji

celu f (x

1

, x

2

) = c

1

x

1

+ c

2

x

2

. Wartości funkcji celu wzdłuż każdej poziomicy są stałe, zaś

poziomice są prostopadłe do gradientu tej funkcji:

∇f = [c

1

, c

2

].

Wiadomo z analizy matematycznej, że wartości funkcji (różniczkowalnej) rosną najszyb-

ciej w kierunku wyznaczonym przez gradient tej funkcji. Wobec tego ∇f = [c

1

, c

2

] jest

kierunkiem najszybszego wzrostu funkcji celu. Rozważmy półprostą

L = {(tc

1

, tc

2

) ∈ R

2

: t ­ 0}

i oznaczmy p(t) = (tc

1

, tc

2

) dla t ­ 0. Oczywiście istnieje taka liczba t

0

, że D∩W

p(t

0

)

(f ) 6= ∅.

Ustalmy taką liczbę t

0

i zauważmy, że możliwe są dwa przypadki:

1) dla każdego t ­ t

0

poziomica W

p(t)

przecina się ze zbiorem rozwiązań dopuszczalnych:

W

p(t)

∩ D 6= ∅,

2) istnieje taka liczba t

1

­ t

0

, że W

p(t

1

)

∩ D 6= ∅ oraz W

p(t)

∩ D = ∅ dla każdego t > t

1

.

W pierwszym z tych przypadków nie istnieje rozwiązanie optymalne rozważanego ZPL —

wartości funkcji celu rosną nieograniczenie w kierunku półprostej L. W drugim przypad-

ku poziomica W

p(t

1

)

musi zawierać pewien wierzchołek wielokąta D i w tym wierzchołku

funkcja f osiąga największą wartość na zbiorze D. Wierzchołek ten wyznacza optymalne

rozwiązanie rozważanego ZPL. Podsumowując, w celu znalezienia rozwiązania optymal-

nego ZPL(max) należy rozważyć rodzinę poziomic W

p(t)

, t ­ 0, i sprawdzić, czy istnieje

w kierunku wektora ∇f = [c

1

, c

2

] „najdalsza” poziomica W

p(t

1

)

mająca punkty wspólne

ze zbiorem rozwiązań dopuszczalnych D. Jeżeli taka poziomica istnieje, to punkty zbio-

ru W

p(t

1

)

∩ D wyznaczają rozwiązania optymalne ZPL. W szczególności, w zbiorze tym

znajduje się co najmniej jeden wierzchołek wielokata D.

Analogiczne rozważania można przeprowadzić w przypadku ZPL(min), należy tylko

zastąpić w rozważaniach wektor ∇f przez wektor do niego przeciwny −∇f . Ten ostatni

wektor wskazuje kierunek, w którym funkcja celu f maleje najszybciej.

Przykład 6. Wróćmy do zadania rozważanego w przykładzie 1. W zadaniu tym zbiór roz-

wiązań dopuszczalnych D określony jest następujacymi ograniczeniami:

5x

1

+ 5x

2

¬ 60,

0, 1x

1

+ 0, 3x

2

¬ 3,

0, 3x

1

+ 0, 2x

2

¬ 3,

x

2

­ 2

11

oraz warunkami brzegowymi x

1

­ 0, x

2

­ 0. Łatwo sprawdzić, że zbiór ten jest zwartym

pieciokątem o wierzchołkach:

A = (0, 3),

B = (8, 3),

C = (6, 6),

D = (3, 9),

E = (0, 10).

Ponieważ funkcją celu jest

f (x

1

, x

2

) = 40x

1

+ 30x

2

,

więc ∇f = [40, 30] wyznacza kierunek, w którym funkcja celu rośnie najszybciej. Poziomice

funkcji celu są prostymi o równaniach postaci

30x

1

+ 40x

2

= p,

p ∈ R.

Poziomice te mają punkty wspólne z obszarem D dla p ∈ [90, 420] (zauważmy, że 90 =

f (A), 420 = f (C)). Wobec tego, poziomicą, która ma część wspólną z obszarem D i na

której funkcja celu przyjmuje największą możliwą warość równą 420, jest prosta o równaniu

30x

1

+ 40x

2

= 420.

Jedynym punktem wspólnym tej poziomicy z wielokatem D jest wierzchołek C = (6, 6) i

on wyznacza rozwiązanie zadania:

Optymalny dzienny plan produkcji gipsowych krasnali przewiduje wyproduko-

wanie 6 krasnali pierwszego rodzaju i 6 krasnali drugiego rodzaju, co zapewni

dzienny zysk w wysokości 420 złotych.

12