16
Lekcja 2. Graficzna metoda rozwiązania zadania planowania liniowego.
2.1. Graficzna interpretacja i rozwiązanie zadania planowania liniowego dla dwóch zmiennych objaśniających.
2.2. Właściwości rozwiązań zadania planowania liniowego.
2.3. Graficzne rozwiązanie zadania planowania liniowego całkowitoliczbowego dla dwóch zmiennych objaśniających.
2.4. Przykład graficznego rozwiązania zadania planowania liniowego.
Ćwiczenie 2. Graficzna metoda rozwiązania zadania planowania liniowego.
Zadania.
Zadania planowania liniowego, w których ilość zmiennych х1, х2, … хn jest większa niż ilość ograniczeń na 2 (lub na 3), mają geometryczną interpretację na płaszczyźnie (lub w trzy wymiarowej przestrzeni). Geometryczna interpretacja ekonomicznych zadań daje możliwość pokazać wyraziście ich strukturę, ujawnić osobliwości, pozwala w geometrycznych terminach wytłumaczyć różne metody rozwiązania.
Przypadek dwóch zmiennych nie ma dużego praktycznego znaczenia, jednak jego rozpatrywanie pokazuje właściwości zadań planowania liniowego, doprowadzi do rozumienia ich rozwiązania, robi geometrycznie obserwowalnym sposoby rozwiązania.
Rozpatrzymy zadanie planowania liniowego dwóch zmiennych х1, х2, dla którego możemy znaleźć graficzne rozwiązanie na płaszczyźnie.
Niech dane jest zadanie
max Z = c1*x1+c2*x2; (2.1)
(2.2)
Pokażemy geometryczną interpretację elementów tego zadania. Każde z ograniczeń (2.2) daje na płaszczyźnie х1Oх2 jedną półpłaszczyznę .
Definicja. Wypukłym nazywamy zbiór, który razem z dowolnymi swoimi punktami М1(х1,у1) i М2(х2,у2), zawiera wszystkie punkty М(х,у) odcinka [М1; М2], tj. punkty x=l*x1+ (1 - l)*х2, y=l*y1+ (1 - l)*y2, 0 ≤ l ≤ 1, które są wypukłymi liniowymi kombinacjami punktów M1 i M2.
Półpłaszczyzna — wypukły zbiór. Jednocześnie przecięcie dowolnej ilości wypukłych zbiorów jest wypukłym zbiorem. Stąd możemy wnioskować, że dziedzina dopuszczalnych rozwiązań (2.1) — (2.2) to jest wypukły zbiór.
Czasami tę właściwość zapisują inaczej: x=l1*x1+l2*х2, y=l1*y1+l2*y2, gdzie l1, l2 ≥0, l1 + l2 =1. Pojęcie wypukłego zbioru można uogólnić na przestrzeń n wymiarów.
Na rys. 2.1 pokazane są możliwe sytuacje, gdy dziedziną dopuszczalnych rozwiązań ZPL jest wypukły wielokąt (а), nieograniczona wypukła wielokątna dziedzina (b), tylko jedyny punkt (c), prosta (lub promień) (d), odcinek (e), pusty zbiór (f).
Przejdziemy do geometrycznej interpretacji celowej funkcji. Niech dziedziną dopuszczalnych rozwiązań ZPL jest niepusty zbiór, na przykład wielokąt А1А2А3А4А5 (rys. 2.1а). Dla dowolnej wartości celowej funkcji Z=Zo równanie Zo = c1*x1+c2*x2 jest równaniem prostej. Celowa funkcja dla wszystkich punktów tej prostej ma taką samą stałą wartość Zo. Zmieniając Zo , otrzymujemy zbiór równoległych prostych, które nazywają się poziomicami celowej funkcji (prostymi stałej wartości).
а)
b)
c)
d)
e)
f)
Rys. 2.1.
Żeby obliczyć kierunek wzrostu (malenia) celowej funkcji znajdziemy cząstkowe pochodne tej funkcji Z według х1 i x2:
(2.3)
Cząstkowe pochodne (2.3) funkcji Z pokazują szybkość jej wzrostu według odpowiednich osi. Na przykład c1 i с2 są szybkościami wzrostu Z według osi Ох1 i Ох2. Wektor c = nazywa się gradientem funkcji. Pokazuje on kierunek najszybszego wzrostu celowej funkcji. Dla liniowej celowej funkcji c = (c1; с2).
Wektor -с wskazuje kierunek najszybszego malenia celowej funkcji. Nazywa się on antygradientem.
Wektor c = (c1; с2) prostopadły do całego zbioru prostych Z = const = c1*x1+c2*x2.
Wykorzystując geometryczną interpretację elementów możemy wnioskować o następnej kolejności kroków w trakcie rozwiązania zadania:
1. Biorąc pod uwagę wszystkie ograniczenia budujemy dziedzinę dopuszczalnych rozwiązań.
2. Obliczamy wektor c = (c1; с2) najszybszego wzrostu celowej funkcji, inaczej mówiąc, wektor gradientowego kierunku.
3. Rysujemy dowolną poziomicę ze zbioru Z=Zo (najłatwiej narysować krzywą Z=0, prostopadłą do wektora с).
4. Jeżeli do rozwiązania zadania konieczne jest odszukanie maksimum celowej funkcji wtedy przesuwamy poziomicę Z=Zo w kierunku wektora с tak, żeby ona dotknęła dziedziny dopuszczalnych rozwiązań w jej brzegowym punkcie (na rys. 2.1а — do punktu А2).
Jeżeli do rozwiązania zadania konieczne jest odszukanie minimum celowej funkcji wtedy przesuwamy poziomicę Z=Zo w kierunku odwrotnym do wektora с (na rys. 2.1а — do punktu A5).
5. Wyznaczymy optymalny plan х* = (х1*; х2*) i ekstremalną wartość celowej funkcji Z* = Z(x*)= Z(х1*; х2*) (na rys. 2.1а – odpowiednio współrzędne punktów А2 i А5).
Możliwe są następujące przypadki:
1) optymalny plan jest jedyny: to znaczy poziomica i dziedzina dopuszczalnych rozwiązań, gdy pokazują one rozwiązanie mają tylko jedyny wspólny punkt;
2) optymalnych planów jest nieskończenie wiele: wtedy, gdy one pokazują rozwiązanie poziomica zawiera jeden odcinek brzegu dziedziny dopuszczalnych rozwiązań;
3) celowa funkcja nie jest ograniczona, jakkolwiek byśmy nie przesuwali poziomicę nie może ona zająć stanu, przy którym mamy rozwiązanie;
4) dziedzina dopuszczalnych rozwiązań zawiera tylko jedyny punkt, w którym celowa funkcja osiąga jednocześnie maksimum i minimum;
5) zadanie nie ma rozwiązania; dziedzina dopuszczalnych rozwiązań to jest pusty zbiór, czyli układ ograniczeń jest niezgodny.
Teraz rozpatrzymy geometryczną interpretację ZPL z п zmiennymi. Nie tracąc ogólności w rozważaniach możemy rozpatrzyć zadanie maksymalizacji:
max Z = c1*x1+c2*x2+ ... +cn*xn = (2.4)
ai1*x1+ai2*x2+ ... + ain*xn £ bi, lub , (i=1,2,...m) (2.5)
xj ³ 0, j=1,2, ... n (2.6)
Zbiór planów х = (х1, х...
kmichalo1