E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
WYKA
AD 4
METODA GRAFICZNA
INTERPRETACJA GEOMETRYCZNA ZADAC
PROGRAMOWANIA LINIOWEGO
Rozwiązanie zadania programowania liniowego, które posiada dwie zmienne decyzyjne:
x1 i x2, mo\
na przedstawić graficznie.
Zadanie przyjmuje postać:
z ( x ) = c1 x1 + c x ekstremum ,
2 2
a11 x1 + a12 x = b1
2
a x1 + a x = b
21 22 2 2
.......... .......... ........
a x1 + a x = b
n 1 n 2 2 n
x1 , x e" 0
2
W układzie współrzędnych Ox1x2, wyznacza się zbiór rozwiązań dopuszczalnych X. Będzie
to iloczyn wszystkich prostych i półpłaszczyzn odpowiadających równaniom
i nierównościom kolejnych ograniczeń zadania. Je\
eli ograniczenia sÄ… podane tylko w postaci
nierówności, obszarem rozwiązań dopuszczalnych będzie wielobok wypukły.
Rozwiązaniem dopuszczalnym będą współrzędne wierzchołka wieloboku, dla których
funkcja celu przyjmuje wartość ekstremalną  tzw. wierzchołka optymalnego.
W celu odnalezienia wierzchołka optymalnego wykreśla się w układzie współrzędnych
Ox1x2 gradient "z(x) funkcji celu z(x)  zaczepiając go w początku układu współrzędnych.
Jego składowymi są pochodne cząstkowe względem kolejnych zmiennych decyzyjnych,
czyli ogólnie dla n zmiennych:
îÅ‚ Å‚Å‚
"z(x) "z(x) "z(x)
"z( x) = , ,...,
ïÅ‚
"x1 "x2 "xn śł
ðÅ‚ ûÅ‚
Gradient pokazuje kierunek najszybszego wzrostu wartości funkcji z(x). Dla liniowej
funkcji celu z(x), gradient "z(x) jest wektorem, którego składowe są współczynnikami funkcji
celu. Dla n zmiennych jest to:
" = [c1 , c , . . . , c ]
z ( x ) 2 n
Kierunek przez niego wskazywany jest niezale\
ny od zmiennych decyzyjnych x1, x2, & , xn.
1
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
Następnie rysujemy prostą prostopadłą do gradientu funkcji celu, przechodzącą przez
początek układu współrzędnych, czyli prostą o równaniu:
L(x) = 0 = c1x1 + c2x2
Nadając funkcji L(x) coraz większe wartości przesuwa się ona równolegle wzdłu\
kierunku
wyznaczonego przez gradient, przecinając wielobok będący zbiorem rozwiązań
dopuszczalnych. Otrzymane proste równoległe dla ró\
nych wartości funkcji L(x) są nazywane
liniami izocelowymi.
Na rysunku 1. przedstawiono opisane postępowanie dla przykładowego zbioru rozwiązań
zadania programowania liniowego dla dwóch zmiennych x1 i x2.
X2
C
D
B
E
A
X1
Rys. 1. Interpretacja graficzna zadania programowania liniowego
W momencie  zerwania kontaktu prostej ze zbiorem rozwiązań, ostatni punkt wspólny
zbioru i prostej jest wierzchołkiem optymalnym. Rozwiązanie to będzie maksymalizować
funkcje celu z(x). W przypadku poszukiwania minimum, postępuje się podobnie, przesuwając
prostą prostopadłą do gradientu, w kierunku przeciwnym do tego jaki wskazuje gradient.
Na rysunku 1 pole wieloboku ABCDE to zbiór rozwiązań zadania programowania liniowego.
Współrzędne wierzchołków wieloboku reprezentują dopuszczalne rozwiązania bazowe.
Współrzędne wierzchołka A stanowią rozwiązanie optymalne minimalizujące funkcję
celu z(x), natomiast współrzędne wierzchołka D maksymalizuję funkcje celu. A i D są
wierzchołkami optymalnymi.
2
)
x
(
z
L
(
x
)
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
W przypadku kiedy jedna z prostych izocelowych będzie równoległa do jednego z boków
wieloboku wypukłego będzie to oznaczać, \
e rozwiązanie optymalne znajduje się w dwóch
punktach wierzchołkowych. Sytuację taką przedstawia rysunek 2.
X2
C
B
D
E
A
X1
Rys. 2. Przypadek z nieskończenie wielką liczbą rozwiązań zadania programowania liniowego
Dla przypadku z rysunku 2 wierzchołkami optymalnymi maksymalizującymi funkcję
celu z(x) są wierzchołki C i D. Rozwiązaniami optymalnymi będą równie\
wszystkie punkty
boku CD, które mo\
na wyznaczyć jako wypukłą kombinacje liniową obydwu wierzchołków,
(wektorów z R2):
Xi = X1 + (1- )X , 0 d"  d" 1, gdzie:
2
X1, X2,  wektory, których składowymi są współrzędne wierzchołków C i D,
  współczynnik kombinacji liniowej wypukłej,
Xi  i-ty wektor optymalnych wartości zmiennych decyzyjnych (i = 1, 2, & , ").
Przy wykreślaniu zbioru rozwiązań mo\
e wystąpić jeden z czterech przypadków:
" rozwiÄ…zanie zadania programowania liniowego jest sprzeczne,
" rozwiązanie zadanie nie posiada skończonego rozwiązania optymalnego,
" rozwiązanie zadania posiada dokładnie jedno rozwiązanie optymalne,
" rozwiązanie zadania posiada wiele rozwiązań optymalnych.
3
)
x
(
z
L
(
x
)
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
Ka\
dy z przypadków przedstawiono graficznie dla konkretnych przykładów
liczbowych.
Przypadek pierwszy  zadanie jest sprzeczne.
Maksymalizujemy funkcjÄ™ celu postaci:
z(x) = x1 + x2 max
przy ograniczeniach:
- 2x1 + x2 e" 2 (I )
x1 - 2x2 e" 2 (II)
x1 + x2 e" 2 (III)
x1, x2 e" 0
Rysunek 3 przedstawia geometrycznÄ… interpretacjÄ™ rozwiÄ…zania przypadku pierwszego.
Zbiór rozwiązań dopuszczalnych jest pusty (X="). Układ warunków ograniczających jest
sprzeczny.
(I)
X2
(II)
X1
(III)
Rys. 3. Interpretacja geometryczne przypadku sprzecznego zadania programowania liniowego
Przypadek drugi  brak skończonego rozwiązania.
Maksymalizujemy funkcjÄ™ celu postaci:
z(x) = 2x1 + 2x2 max
przy ograniczeniach:
4
L
(
x
)
)
x
(
z
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
- 2x1 + x2 e" 2 (I )
x1 - 2x2 e" 2 (II)
x1 + x2 e" 2 (III)
x1, x2 e" 0
Rysunek 4 przedstawia geometrycznÄ… interpretacjÄ™ rozwiÄ…zania przypadku drugiego.
Prosta izocelowa przesuwana jest w kierunku zgodnym z gradientem. Nie mo\
e jednak trafić
na wierzchołek zbioru rozwiązań dopuszczalnych.
(I)
X2
(II)
X1
(III)
Rys. 4. Interpretacja geometryczne braku skończonego rozwiązania zadania programowania
liniowego
Przypadek trzeci  skończone jednoznaczne rozwiązanie.
Maksymalizujemy funkcjÄ™ celu postaci:
z(x) = -3x1 + x2 max
przy ograniczeniach:
- 2x1 + x2 e" 2 (I )
x1 - 2x2 e" 2 (II)
x1 + x2 e" 2 (III)
x1, x2 e" 0
5
L
(
x
)
)
x
(
z
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
Rysunek 5 przedstawia geometrycznÄ… interpretacjÄ™ rozwiÄ…zania przypadku trzeciego. Istnieje
równanie prostej izocelowej, które przecina zbiór rozwiązań dopuszczalnych dokładnie w
jednym punkcie. Punkt ten jest wierzchołkiem optymalnym, a jego współrzędne
maksymalizujÄ… funkcjÄ™ celu.
2
(II)
X1
(III)
Rys. 5. Interpretacja geometryczne skończonego jednoznacznego rozwiązania zadania
programowania liniowego
Przypadek czwarty  niejednoznaczne rozwiÄ…zanie zadania.
Przypadek ten posiada dwa warianty rozwiÄ…zania. Wariant pierwszy dotyczy sytuacji,
w której jedna z prostych izocelowych pokrywa się z jednym z boków obszaru rozwiązań.
Rozwiązaniami optymalnymi są współrzędne skrajnych punktów boku oraz ka\
de współrzędne
będące liniową wypukłą ich kombinacją. Sytuację tą przedstawia rysunek 6. Dotyczy ona
minimalizacji funkcji celu postaci:
z(x) = 2x1 + 2x2 min
przy ograniczeniach:
- 2x1 + x2 e" 2 (I )
x1 - 2x2 e" 2 (II)
x1 + x2 e" 2 (III)
x1, x2 e" 0
6
z
(
x
)
)
x
(
L
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
(I)
X2
(II)
X1
(III)
Rys. 6. Interpretacja geometryczne niejednoznacznego rozwiÄ…zania zadania programowania
liniowego dla wariantu pierwszego
Prosta L(x) przesuwana jest przeciwnie do kierunku wskazywanego przez gradient w
celu znalezienia wartości zmiennych minimalizujących funkcję celu.
Drugi z wariantów przypadku czwartego dotyczy sytuacji, w której zadanie
programowania liniowego posiada jedno rozwiązanie optymalne wierzchołkowe oraz
nieskończenie wiele rozwiązań optymalnych. Rozwiązania te znajdują się na prostej
o równaniu jednego z ograniczeń.
Maksymalizujemy funkcjÄ™ celu postaci:
z(x) = -2x1 + x2 max
przy ograniczeniach:
- 2x1 + x2 e" 2 (I )
x1 - 2x2 e" 2 (II)
x1 + x2 e" 2 (III)
x1, x2 e" 0
7
L
(
x
)
)
x
(
z
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
(I)
X2
(II)
X1
(III)
Rys. 7. Interpretacja geometryczne niejednoznacznego rozwiÄ…zania zadania programowania
liniowego dla wariantu drugiego
Dochodzenie do rozwiÄ…zania zadania programowania liniowego w metodzie graficznej
przebiega dwuetapowo:
" wykreślenie zbioru rozwiązań dopuszczalnych,
" wyznaczenie w tym zbiorze rozwiÄ…zania optymalnego.
Geometrycznie mo\
na rozwiązać równie\
zadanie programowania liniowego posiadajÄ…ce
trzy zmienne decyzyjne. Obszarem rozwiązań dla takiego zadania będzie wielościan wypukły
w przestrzeni trójwymiarowej R3. W przypadku wystąpienia trzech i więcej zmiennych
decyzyjnych, do rozwiązania zadania stosuje się ró\
nego rodzaju algorytmy ułatwiające
poszukiwanie rozwiązań optymalnych. Kilka z takich algorytmów zostało opisanych w
następnym rozdziale.
8
z
(
x
)
)
x
(
L
E. Michlowicz: MOPM  Optymalizacja liniowa. Metoda graficzna
DYSKRETYZACJA
rozwiązania ciągłego
W technice często chcemy, by wynik był liczbą całkowitą (programowanie całkowito
liczbowe).
PRZYKA
AD:
Dla zadanej funkcji celu i narzuconych ograniczeń nale\
y znalez
ć rozwiązanie
optymalne  ciągłe.
Nale\
y zaokrąglić wynik do wartości dyskretnych - całkowitoliczbowych
i przeprowadzić analizę rozwiązania.
Funkcja celu:
z = f(x1, x2, ) = 4x1 + x2
Ograniczenia:
g1 = g1 (x1, x2) = 5x1 + x2< 26.5
g2 = g2 (x1, x2) = x1 + 5x2 < 26.5
g3 = g3 (x1) = x1 >= 0
g4 = g4 (x2) = x2 >=0
ROZWI
ZANIE  GRAFICZNE
(wykonać) - ciągłe :
x1 = 4.417
x2 = 4.417
z = 22.083
Przykładowo:
liczba potrzebnych środków transportowych
Dyskretyzacja D1:
x1 = 4
x2 = 4
funkcja celu: z = 20
Dyskretyzacja D2:
x1 = 5
x2 = 1
funkcja celu: z = 21
WNIOSEK:
zaokrąglenie z rozwiązania ciągłego do dyskretnego mo\
e
prowadzić do błędnych wyników.
9