CCF03252008004

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, x2 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 2xl.—:xz = 2. Znajdujemy jej punkty przecięcia z osią Xi (x, = 1) oraz osią x2 (x2 = —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 (xlt x2), 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 4xt + 2x2 = 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 xt — 2,5, x2 = 3 jest rozwiązaniem optymalnym rozważanego zadania. Aby znaleźć te współrzędne, rozwiązujemy następujący układ równań:

2x, - x2 = 2 x2 = 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


Wyszukiwarka

Podobne podstrony:
PICT6401 Zależność może mieć kierunek dodatni lub ujemny. Kierunek dodatni występuje wtedy, gdy wzro
DSC00080 (2) Wapno wa nie • Wyznaczanie dawki wapna koniecznej do odkwaszenia gleby może mieć charak
PROCESY PROWADZĄCE DO KONDENSACJI PARY WODNEJ Ocliładzanie powietrza może mieć charakter adiabatyczn
Towar - produkt przeznaczony na sprzedaż, może mieć postać fizyczną lub usług. O cenie decyduje 5 el
-może mieć źródło ustawowe lub kontraktowe -może być wprowadzony ty lko na podstawie umowy -może
- wielodokumentowe. Kontrakt jednodokumentowy może mieć formę maszynopisu lub kontraktu typowego tzn
7.    Egzamin komisyjny może mieć formę ustną lub pisemną i ustną. Decyzję w tej
IMG34 270 Analiza dynamiki zjawisk Składowa systematyczna szeregu może mieć postać jednego lub złoż
DSC02057 Taśma niosąca materiał zależnie od ustawienia rolek podtrzymujących może mieć profil płaski
Rodzaje badań statystycznych Badanie statystyczne może mieć charakter PEŁNY lub NIEPEŁNY (badanie
10 6B i 6C. Element nadający ruch 56 może mieć postać podkładki lub kuli, lub przykładowo korzystnie
2 Ich zbiór jest dziedziną rozwiązań dopuszczalnych (lub dziedziną ekonomicznych możliwości). Takim
skanuj0023 (166) 46 Teoria wielostronnego kształcenia a modele lekcji rozwiązując zadania, których n

więcej podobnych podstron