Programowanie matematyczne

Interpretacja graficzna

Zadanie 1

Rozważmy zadanie programowania liniowego

Zadanie to jest modelem następującego problemu ekonomicznego. Zakład produkcyjny wytwarza dwa rodzaje produktów: W₁ i W₂. Na produkcję tych wyrobów zużywa się trzy surowce: S₁, S₂, S₃. Zasoby surowców są ograniczone. Dostępne jest 21 jednostek surowca S₁, 8 jednostek surowca S₂ i 20 jednostek surowca S₃. Jednostkowe nakłady surowców na produkcję poszczególnych wyrobów są następujące: 3S₁, 1S₂ i 5S₃ dla wyrobu W₁, 3S₁ i 2S₂ dla wyrobu W₂.

Zakład chce osiągnąć maksymalny zysk. Wiadomo, że zysk osiągany w wyniku wyprodukowania jednostki wyrobu W₁ wynosi 400 zł, a zysk jednostkowy dla wyrobu W₂ wynosi 600 zł. Należy znaleźć strukturę produkcji, która pozwala osiągnąć największy zysk.

W modelu matematycznym x₁ - oznacza liczbę produkowanych jednostek wyrobu W₁, x₂ -oznacza liczbę produkowanych jednostek wyrobu W₂.

Rozwiązanie graficzne

Ponieważ w modelu występują tylko dwie zmienne decyzyjne, można przedstawić cały problem na płaszczyźnie w układzie współrzędnych x₁, x₂. Zbiór dopuszczalny leży w pierwszej ćwiartce układu współrzędnych i jest częścią wspólną pięciu półpłaszczyzn.

Aby narysować półpłaszczyznę
czyli
, należy zamienić nierówność na równanie
, z którego otrzymamy
. Gdy
, to
. Gdy
, to
. Zatem prosta
przechodzi przez punkty o współrzędnych (0; 7) i (7; 0). Półpłaszczyzna odpowiadająca nierówności
leży "poniżej" tej prostej (i na niej). Łatwo ją przedstawić na rysunku (kierunek zaznaczony strzałką na rys. 1).

W analogiczny sposób znajdujemy półpłaszczyzny odpowiadające nierównościom
oraz
(czyli
). Po uwzględnieniu warunków brzegowych
,
otrzymujemy wielokąt przedstawiony (zakreskowany) na rysunku. Wszystkie punkty czworokąta OABC (w szczególności wierzchołki O, A, B, C) reprezentują rozwiązania dopuszczalne zadania. Widzimy tu, że półpłaszczyzna
(obrazująca ograniczenie surowca S₁) nie ma wpływu na kształt otrzymanego wielokąta. Oznacza to, że przy każdej decyzji dopuszczalnej surowiec S₁ nie będzie wykorzystany w pełni. Ograniczenie
można opuścić i nie zmieni to zbioru dopuszczalnego.

Aby rozwiązać zadanie optymalizacyjne, należy narysować dowolną prostą o równaniu
, gdzie C jest pewną stałą (wybieramy ją arbitralnie w ten sposób, żeby łatwo było narysować prostą np. weźmy tu C = 1200). Prosta
, czyli
wyznacza wszystkie punkty płaszczyzny, w których funkcja celu przyjmuje stałą wartość C. Prosta ta nazywa się warstwicą tzn. linią tych samych wartości funkcji celu. Jeżeli funkcja celu przyjmie inną wartość, to otrzymamy odpowiednią warstwicę przesuwając równolegle otrzymaną prostą.

Rys.1. Rozwiązanie graficzne zadania 1

Ponieważ interesuje nas możliwie największa wartość funkcji celu, przesuńmy prostą równolegle w ten sposób, aby miała jeszcze punkty wspólne ze zbiorem rozwiązań dopuszczalnych. Otrzymujemy prostą mającą jeden punkt B=(4; 2), wspólny ze zbiorem dopuszczalnym. Prosta ma równanie
, czyli
. W ten sposób znaleźliśmy rozwiązanie optymalne zadania
oraz maksymalną wartość funkcji celu
.

Uwaga 1

Kierunek, wzdłuż którego należy przesuwać równolegle prostą odpowiadającą funkcji celu, jest wyznaczony przez gradient
. Dla funkcji liniowych gradient wyznacza się bardzo łatwo. Jeżeli
, to
. Jest to wektor prostopadły do prostej
. Jeżeli interesuje nas minimalizacja funkcji celu na podanym zbiorze dopuszczalnym, to należy przesuwać prostą równolegle w kierunku przeciwnym do
, czyli w kierunku
. W naszym przykładzie minimalna wartość funkcji celu na zbiorze dopuszczalnym jest osiągana w punkcie
i wynosi
.

Uwaga 2

Rozwiązanie zadania nie musi być jednoznaczne. Zmieńmy w zadaniu 1 funkcję celu na następującą:
(Zadanie 1A). Jeżeli narysujemy prostą o równaniu
, czyli
i będziemy ją równolegle przesuwać, to zauważymy, że maksymalna wartość funkcji celu na zbiorze dopuszczalnym zostanie osiągnięta nie tylko w punkcie B=(4; 2), ale również w punkcie
i na całym odcinku AB. Zbiór rozwiązań optymalnych zadania składa się z punktów postaci
.

Uwaga 3

Zauważmy, że nie zawsze, gdy funkcja celu przedstawia prostą równoległą do jednego z ograniczeń, mamy wiele rozwiązań optymalnych. W zadaniu 1A minimalna wartość funkcji celu na zbiorze dopuszczalnym jest wciąż w punkcie O. Jeżeli weźmiemy funkcję celu
(Zadanie 1B), maksimum jest osiągane tylko w punkcie B, natomiast funkcja celu jest równoległa do jednego z ograniczeń.

Zadanie 2

Rozważmy zadanie programowania liniowego

• Zbiór dopuszczalny zadania jest nieograniczony.

• Nie istnieje rozwiązanie zadania z maksymalizacją funkcji celu

• Istnieje rozwiązanie zadania z minimalizacją funkcji celu na całym odcinku BC, gdzie
  ,
  .

Zadanie 3

Rozważmy zadanie programowania liniowego

Rozwiązanie

Zbiór rozwiązań dopuszczalnych jest zbiorem pustym, gdyż układ nierówności jest sprzeczny. Zatem zadanie nie ma rozwiązania optymalnego (dla każdej funkcji celu).

Uwaga 4

Jeżeli wśród ograniczeń występuje równanie, to zbiór dopuszczalny na ogół redukuje się do zbioru mającego o jeden wymiar mniej. Jeżeli w zadaniu 1 zamiast nierówności
weźmiemy równanie
, to zbiór dopuszczalny składa się z punktów odcinka BC (rys. 1). Funkcja
osiąga maksimum w punkcie B, a minimum w punkcie C. Jeżeli natomiast nierówność
zamienimy na równość, to zbiór dopuszczalny będzie pusty.

Zadanie 4

Metodę graficzną można stosować również do zadań nieliniowych, jeżeli mamy dwie zmienne decyzyjne i umiemy narysować odpowiednie zbiory i funkcje na płaszczyźnie.

Rozważmy zadanie nieliniowe

Ponieważ ograniczenia są liniowe, zbiór dopuszczalny, podobnie jak w przypadku zadania programowania liniowego, jest wielokątem. Jednak funkcja celu jest nieliniowa (kwadratowa). Warstwice funkcji celu są okręgami o coraz większych wartościach, gdy oddalamy się od punktu
. Minimum bezwarunkowe funkcji celu wynosi 0 i jest osiągane w punkcie O (ale ten punkt nie jest dopuszczalny). Minimum warunkowe leży na prostej przechodzącej przez punkty A=(4; 0) i B=(0; 6). Jest to styczna do okręgu będącego warstwicą funkcji celu (rys. 2). Punkt styczności można wyznaczyć analitycznie rozwiązując układ równań:

Prosta o równaniu
jest prostą prostopadłą do odcinka AB i przechodzącą przez punkt O. Rozwiązaniem układu równań jest punkt
. Zatem
,
,
.

Zauważmy, że rozwiązanie optymalne nie leży w wierzchołku wielokąta, lecz na jednym z jego boków. W ogólnym przypadku rozwiązanie optymalne może też leżeć wewnątrz zbioru dopuszczalnego (rys. 2b)

Rys.2. Rozwiązanie graficzne zadania 4

Literatura

1. Ewa Wasilewska, Badania operacyjne. Wybrane zagadnienia z programowania liniowego, Wydawnictwo "2000", Warszawa 2001.

2. Alpha C. Chiang, Podstawy ekonomii matematycznej, PWE, Warszawa 1994.

BAD_OPER02

1

(2)

(1)

(3)

B

A

C

O

x₁

x₂

f

---