CCF03252008004

2.5

Metoda geometryczna

Zadanie PL może mieć rozwiązania dopuszczalne lub być zadaniem sprzecznym, nie mającym rozwiązania dopuszczalnego. Jeżeli zadanie PL ma rozwiązania dopuszczalne, to zachodzi jedna z trzech możliwości:

1)    istnieje jedno rozwiązanie optymalne,

2)    istnieje wiele rozwiązań optymalnych,

3)    brak rozwiązania optymalnego.

W przypadku dwóch zmiennych bardzo łatwo jest znaleźć rozwiązanie optymalne lub pokazać, że go nie ma. Stosujemy wówczas metodę geometryczną. Ze względu na ograniczenie dotyczące liczby zmiennych nie ma ona jednak dużego znaczenia praktycznego, ważne są natomiast jej walory dydaktyczne. Pozwala doskonale zilustrować procedurę znajdowania rozwiązania optymalnego. Istotę tej metody wyjaśnimy w przykładzie 2.9.

PRZYKŁAD 2.9

Rozważmy zadanie PL z dwiema zmiennymi:

4x, + 2x2 -> max,	(FC)	/) J - i' j
2x, —'x, < 2, 0	(I)
x2 < 3, 0	(II)	y •- /
2x, + x2 ^ 2, 0	(III)
W p	(IV)

, ■! — ? -

Aby rozwiązać zadanie PL metodą geometryczną, rysujemy układ współrzędnych; na osiach Xj, x₂ nanosimy jednostki. Następnie rysujemy proste odpowiadające poszczególnym nierównościom zadania. Z nierównością I związana jest prosta o równaniu 2x_l.—_:x_z = 2. Znajdujemy jej punkty przecięcia z osią Xi (x, = 1) oraz osią x₂ (x₂ = —2). Ponieważ nierówności I odpowiada półpłaszczyzna punktów leżących zarówno na tej prostej, jak i na lewo od niej, więc obszar ten zaznaczamy strzałką. Z kolei nanosimy proste odpowiadające nierównościom II i III oraz warunkom nieujemności zmiennych. Uzyskujemy w ten sposób pięć pólplaszczyzn. Część wspólna pólplaszczyzn, czyli zbiór punktów o współrzędnych (x_lt x₂), spełniających wszystkie warunki ograniczające, jest zbiorem rozwiązań dopuszczalnych. Zbiór ten to wielokąt o wierzchołkach A, B, C, D. Na rys. 2.1 zaznaczono go jako obszar zakresko-wany.

Aby znaleźć rozwiązanie optymalne zadania PL, przyjmujemy dowolną, lecz dogodną wartość funkcji celu, np. 8, i rysujemy prostą o równaniu 4x_t + 2x₂ = 8. Na rys. 2.1 zaznaczono ją linią przerywaną (FC). Jest to izokwanta, czyli linia tych samych wartości funkcji celu. Jeżeli weźmiemy większą wartość funkcji celu, to uzyskamy prostą równoległą, która będzie leżała powyżej prostej FC. Jeżeli przyjmiemy mniejszą wartość, to nowa 32 izokwanta będzie leżała poniżej prostej FC. Jeżeli izokwantę przesuniemy równolegle w górę, to będzie ona styczna do obszaru rozwiązań w punkcie B (2,5; 3); w tym punkcie osiąga ona wartość największą w zbiorze rozwiązań dopuszczalnych (ZRD). Punkt B o współrzędnych x_t — 2,5, x₂ = 3 jest rozwiązaniem optymalnym rozważanego zadania. Aby znaleźć te współrzędne, rozwiązujemy następujący układ równań:

2x, - x₂ = 2 x₂ = 3.

Gdybyśmy szukali minimum tej samej funkcji, to rozwiązaniem optymalnym byłby każdy punkt na odcinku [A, £)].

Problem znajdowania rozwiązania zadania PL metodą geometryczną sprowadza się do:

1)    wyznaczania pólplaszczyzn odpowiadających poszczególnym nierównościom,

2)    znalezienia części wspólnej dla wszystkich pólplaszczyzn, czyli ZRD,

3)    wyszukania w ZRD rozwiązania najlepszego dla przyjętej funkcji celu.

Jeżeli ZRD jest zbiorem pustym lub zbiorem nieograniczonym w kierunku

wzrostu wartości funkcji celu dla zadania na maksimum bądź spadku dla zadania na minimum, to zadanie nie ma rozwiązania optymalnego.

I

/.    i"-    • ■/    .

'2 i ■;    - ,.A

V., '=\X,

,'/D

(O

y

i

33