Wykłady z matematyki dla studentów kierunków ekonomicznych
Wykład 29
ZAGADNIENIA PROGRAMOWANIA LINIOWEGO (ZPL)
1. Zagadnienia programowania liniowego (ZPL)
W zagadnieniach programowania liniowego poszukuje się wartości optymalnej (największej lub
najmniejszej) tzw.
funkcji celu
mającej postać:
= +++
,
gdzie - stałe, - zmienne, przy założeniu, że zmienne te spełniają dodatkowo
pewien układ równań i/lub nierówności liniowych.
zcx cx
...
cx
11
2 2
nn
cc
,
, ...,
c
x
,
x
,
...,
x
12
n
1
2
n
Zadanie postaci
zcx cx
=
+++→
(maksymalizacja funkcji)
...
cx
max
11
2 2
nn
⎧
⎪
... ,
... ,
.................................................
...
ax ax
+
+ +
ax
≤
b
11
1
12
2
1
nn
1
ax ax
+
+ +
a x
≤
b
⎨
⎪
⎪
21
1
22
2
2
nn
2
(warunki ograniczające)
ax a x
+
+ +
ax b
≤
,
⎩
m
11
m
2 2
mn
n
m
xx
( warunki brzegowe)
nazywa się
standardowym zadaniem maksymalizacji
.
≥
0
≥
0
...
,
x
≥
0
1
2
n
Podobnie, zadanie
zcx cx
=
+++→
(minimalizacja funkcji)
...
cx
min
11
2 2
nn
⎧
⎪
... ,
... ,
.................................................
...
ax ax
+
+ +
ax
≥
b
11
1
12
2
1
nn
1
ax ax
+
+ +
a x
≥
b
⎨
⎪
⎪
21
1
22
2
2
nn
2
(warunki ograniczające)
ax a x
+
+ +
ax b
≥
,
⎩
m
11
m
2 2
mn
n
m
( warunki brzegowe)
x
≥
0
x
≥
0
...
,
x
≥
0
1
2
n
nazywa się
standardowym zadaniem minimalizacji
.
Funkcja celu jest funkcją liniową
n
zmiennych. Zbiór rozwiązań warunków ograniczających i warunków
brzegowych, który jest podzbiorem przestrzeni
R
n
, nazywać będziemy
zbiorem rozwiązań
dopuszczalnych
, i oznaczać
ZRD
. Rozwiązanie dopuszczalne
0
0
0
0
x xx
= , dla którego funkcja celu
osiąga wartość najkorzystniejszą (największą w przypadku maksymalizacji , najmniejszą w przypadku
minimalizacji) nazywa się
rozwiązaniem optymalnym
.
(
,
, ... ,
)
12
n
Jeżeli w warunkach ograniczających występują wyłącznie równania, to zadanie ma tzw.
postać
kanoniczną.
Jeżeli w warunkach ograniczających występują zarówno równania, jak i nierówności, to
zadanie ma tzw.
postać mieszaną
.
2
Wykład 29. Zagadnienia programowania liniowego
Zadanie PL może mieć rozwiązania dopuszczalne lub być zadaniem sprzecznym. Jeżeli ma ono
rozwiązania dopuszczalne, to zachodzi jedna z możliwości:
•
istnieje jedno rozwiązanie optymalne,
•
istnieje wiele rozwiązań optymalnych,
•
brak rozwiązania optymalnego.
2. Układanie zadań decyzyjnych
Układanie zadań decyzyjnych polega na „przełożeniu” słownego opisu sytuacji decyzyjnej na język
matematyki. W przypadku liniowego zadania decyzyjnego składa się z następujących etapów:
1.
Określenie zmiennych decyzyjnych.
2.
Sformułowanie celu decydenta, tj. ustalenie funkcji celu.
3.
Sformułowanie warunków ograniczających, jakie powinna spełniać decyzja dopuszczalna, tj.
podanie równań i nierówności wiążących zmienne decyzyjne.
Formułowanie zadania decyzyjnego jest sztuką i nie można – poza ogólnymi regułami – podać jakiejś
szczegółowej recepty. Zdarza się, że tę samą sytuację decyzyjną można opisać matematycznie na wiele
sposobów. Często też od osoby formułującej zadanie zależy jego postać i to, czy zadanie jest trudne, czy
łatwe do rozwiązania.
Przykład 1
. Przedsiębiorstwo wytwarza dwa wyroby, używając do tego celu dwóch surowców. Normy
zużycia, limity surowca, ceny produktów podaje tabela. Decydent ma określić, których wyrobów produkcję
i w jakiej wysokości podjąć, aby przychód uzyskany ze sprzedaży był możliwie wysoki. Sformułować
zadanie decyzyjne.
Surowiec
Wyroby
Ceny
I
II
1
8
6
18
2
4
9
15
Limity
52
69
Rozwiązanie.
Kolejne etapy zadania przedstawiają się następująco:
1.
Zmienne decyzyjne:
x
- wielkość produkcji wyrobu 1,
x
-wielkość produkcji wyrobu 2.
2.
Funkcja kryterium:
Przy założeniu, że cała produkcja jest sprzedawana, przychód ze sprzedaży
x
jednostek wyrobu 1 oraz
x
jednostek wyrobu 2 wynosi
zł. Celem decydenta jest maksymalizacja przychodu –
18
x
+
15
x
1
2
w zadaniu tym mamy więc:
z
=
18
x
+
15
x
→
.
max
1
2
3.
Warunki ograniczające (i brzegowe):
Z istoty zadania wynika, że oraz . Wielkość zmiennych decyzyjnych ograniczają też
czynniki produkcji. I tak: jeżeli przedsiębiorstwo wytworzy
x
≥
0
x
≥
0
1
2
x
jednostek wyrobu 1, to zużyje na to
8
x
1
jednostek surowca I, wytwarzając
x
jednostek wyrobu 2, zużyje
4
x
jednostek surowca I. Oznacza to,
2
że łącznie zużyte zostanie
x
+
jednostek surowca I. Z uwagi na to, że limit surowca I wynosi 52
jednostki, odpowiedni warunek ograniczający przyjmie postać:
1
84
2
+ ≤
.
Podobne rozważania w odniesieniu do surowca II prowadzą do nierówności:
84 5
x
x
2
1
2
69 6
x
+
x
≤
9
.
1
2
Wykład 29. Zagadnienia programowania liniowego
3
Reasumując, mamy tu do czynienia ze standardowym zadaniem maksymalizacji:
z
=
18
x
+
15
x
→
max
1
2
⎨
84 ,
69 9
,
x x
x x
xx
+≤
1
2
+≤
⎩
1
2
≥
0
12
3. Metoda graficzna rozwiązywania zagadnień programowania liniowego (ZPL)
Jedną z metod rozwiązywania zadania programowania liniowego jest tzw.
metoda graficzna.
Mimo, że
ma ona ograniczony zakres stosowania (dotyczy dwóch zmiennych), to jest wygodna do zilustrowania
ogólnych zasad stanowiących podstawy innych metod.
Metoda graficzna można przybrać jedną z dwóch postaci:
1.
metoda graficzna z izolinią.
2.
metoda przeglądania wartości funkcji celu w wierzchołkach.
Przykład 2.
Rozwiązać następujące ZPL:
z
=
2
x
+
3
x
→
max
1
2
−
x
+
x
≤
1
⎧
1
2
⎪
⎨
x
+
3
x
≤
11
,
1
2
2
x
−
x
≤
8
⎪
⎩
1
2
⎪
x
≥
0
x
≥
0
.
1
2
Rozwiązanie.
Wykreślimy w układzie
X
1
OX
zbiór rozwiązań dopuszczalnych tj. zbiór punktów
2
spełniających układ wszystkich nierówności.:
Zacznijmy od warunków nieujemności:
x
≥
0
,
x
≥
0
. Warunki te spełniają jedynie współrzędne
1
2
punktów leżących w I ćwiartce układu.
Rozpatrzmy kolejne warunki ograniczające. Interpretacją geometryczną nierówności
−+ ≤
xx
1
jest
1
2
półpłaszczyzna wyznaczona przez prostą
− +=
. Która z dwóch ewentualnych półpłaszczyzn jest
tą właściwą, możemy rozstrzygnąć obierając punkt spoza prostej (np. ) i sprawdzając, czy spełnia on
nierówność i tym samym należy do odpowiedniej półpłaszczyzny, czy nie. W tym przypadku punkt spełnia
nierówność, co oznacza, że pod uwagę bierzemy półpłaszczyznę zawierającą ten punkt, czyli leżącą pod
prostą (na rysunku zaznaczamy to w postaci strzałki prostopadłej do prostej i zwróconej grotem ku dołowi).
l
:
x
x
1
1
1
2
O
(0, 0)
X
2
X
2
l
1
l
1
l
3
l
3
C
C
B
B
l
2
l
2
D
D
ZRD
1
1
X
1
X
1
1
O
1
A
O
A
Rys.2
Rys.1
4
Wykład 29. Zagadnienia programowania liniowego
Podobne rozważania przeprowadzone dla nierówności
1
x
+
2
31
x
≤
prowadzą do wniosku, że opisuje ona
1
dolną półpłaszczyznę wyznaczoną przez prostą
l
21
:
+
3 1
x
=
. Na koniec, nierówność
2
x
−≤
8
opisuje
2
1
2
górną półpłaszczyznę wyznaczoną przez prostą
l x
− =
. Proste te przedstawione zostały na rys.1.
Ponieważ ZRD jest zbiorem punktów spełniających zarówno warunki nieujemności jak i warunki
ograniczające, zatem jest on wypukłym pięciokątem o wierzchołkach:
O, A, B, C
,
D
(patrz rys.2).
:2
8
3
1
2
Na rys.3 narysowane zostały warstwice (izolinie) funkcji celu odpowiadające wartościom
. Są to proste o równaniach odpowiednio:
z
===
0
,
z
6
,
z
1
2
23 0
x
+
x
=
,
23
x
+
x
=
6
,
23 2
x
+=
.
1
2
1
2
1
2
X
2
→
l
1
l
3
grad
z
=
[,]
23
C
B
l
2
D
ZRD
zz
=
1
max
X
1
O
1
A
Rys.3
z
= 12
z
= 0
z
= 6
Z analizy planu warstwicowego wynika, że wartość funkcji wzrasta wraz z przemieszczaniem się wzdłuż
→
wektora . Największą wartość funkcja osiąga w wierzchołku
B,
który jest najdalej
wysuniętym w kierunku gradientu punktem zbioru ZRD
.
Współrzędne punktu
B
stanowią rozwiązanie
optymalne naszego zagadnienia.
Ponieważ punkt
B
jest wspólnym punktem prostych
grad
z
=
[,]
23
+ = − =
,
to jego współrzędne znajdziemy rozwiązując układ utworzony z tych równań.
Tym samym:
l
:
x x
3
11,
l
: 2
xx
8
2
1
2
3
1
2
B
( 5 , 2 )
oraz
z
=
z
(5, 2)
=⋅+⋅=
.
2 5
3 2
16
max
Uwagi.
1.
Jeżeli istnieje rozwiązanie optymalne w zagadnieniu ZPL dwóch zmiennych, to osiągane jest ono w
pewnym wierzchołku zbioru dopuszczalnego.
2.
Jeżeli tę samą wartość funkcja celu przyjmuje w dwóch wierzchołkach, to przyjmuje ją również we
wszystkich punktach odcinka łączącego te wierzchołki.
Jeżeli ZRD jest zbiorem ograniczonym, to aby znaleźć wartość optymalną funkcji
z
wystarczy obliczyć
wartości funkcji we wszystkich wierzchołkach zbioru, a następnie wybrać odpowiednią wartość spośród
nich. Na tym spostrzeżeniu opiera się druga wersja metody graficznej - metoda przeglądania wartości funkcji
celu w wierzchołkach.
Przykład 3.
Rozwiązać następujące ZPL:
+→
z
=
57
x x
a
x
1
2
⎧
⎪
x x
xx
x
+≤
2 2
9,
,
1
2
+≤
⎨
⎪
1
2
≥
0,
x
≥
0
⎩
1
2
Wykład 29. Zagadnienia programowania liniowego
5
Rozwiązanie
.
Najpierw wykreślimy w układzie
X
1
OX
zbiór rozwiązań dopuszczalnych:
2
X
2
Obszar ZRD jest wypukłym czworokątem
o wierzchołkach:
O, A, B, C
, przy czym bezpośrednio
z rys.4 odczytujemy:
(0, 0),
x
+=
9
1
2
O A C
.
Współrzędne punktu
B
to rozwiązanie układu równań:
(9, 0),
(0, 6)
C
B
x x
xx
+=
2 2
9
,
⎧
⎨
1
2
+=
ZRD
x
2
2 2
+=
1
⎩
X
1
2
1
2
zatem
B
(6,3)
.
2
O
A
Rys. 4
Obliczamy wartości funkcji
z
w otrzymanych punktach – wierzchołkach ZRD podstawiając każdorazowo
współrzędne wierzchołka do wzoru:
z
=+
57
x x
.
1
2
z
=
z
(0,0)
=
,
0
z
=
z
(9, 0)
=
45
,
z
=
z
(6,3)
=
,
51
z
=
z
(0,6)
=
42
.
A
B
C
Spośród otrzymanych wartości największą jest:
z
=
51
. Rozwiązaniem optymalnym jest punkt
B
(6,3)
.
max
Przykład 4.
Zakład produkuje dwa wyroby zużywając do tego celu pewną ilość środków produkcji,
z których cztery: energia elektryczna, stal, drewno oraz praca są limitowane. Na wyprodukowanie jednostki
poszczególnych wyrobów środki te są zużywane w ilościach podanych w postaci tabelki:
Wyrób
Energia
Stal
Drewno
Praca
I
5
5
6
10
II
25
10
0
10
Zasoby poszczególnych środków wynoszą odpowiednio:
Energia
Stal
Drewno
Praca
Zasoby
1200
600
420
900
Zysk jednostkowy z produkcji wyrobu I jest równy 10 zł, wyrobu II - 21 zł.
Ile poszczególnych wyrobów powinien produkować zakład, aby jego zysk był maksymalny?
x
1
x
2
Rozwiązanie
.
Niech
oznacza ilość jednostek wyrobu I,
- ilość jednostek wyrobu II
produkowanych przez zakład. Zysk z produkcji jest wtedy równy:
z
=
10
x
+
21
x
.
1
2
Z warunków zadania wynika, że
z
=+→
10
x
21
x
max
z
=+→
10
x
21
x
max
1
2
1
2
⎧
5
x
+
25
x
≤
1200,
⎧
x
+
5
x
≤
240,
1
2
1
2
⎪
⎪
5 0 ,
x
+
x
≤
x
+
2 ,
x
≤
⎪
⎪
1
2
1
2
⎪
⎪
6
x
≤
420,
⇔
x
≤
70,
⎨
⎨
1
1
⎪
⎪
10
x
+
10
x
≤
900,
x
+
x
≤
90,
⎪
1
2
⎪
1
2
⎪
⎪
x
≥
0,
x
≥
0
x
≥
0,
x
≥
0
⎩
⎩
1
2
1
2
Interpretację ZRD przedstawia rys.5.