3582323610

BAD OPER02

Programowanie matematyczne Interpretacja graficzna

Zadanie 1

Rozważmy zadanie programowania liniowego

f(x₁, x₂) = 400x₁ + 600x₂ —> max 3x_x + 3x₂ <, 21 x₁ -f 2x₂ <, 8 5x_x S 20 x₁ 5: 0, x₂ 2:0

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

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

W modelu matematycznym xi - oznacza liczbę produkowanych jednostek wyrobu Wi, X2 -oznacza liczbę produkowanych jednostek wyrobu W2.

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 xju X2- 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ę 3x_t -t-3x₂ <121 czyli 4-x₂ <17, należy zamienić nierówność na równanie Xj +x₂ = 7, z którego otrzymamy x₂ = 7 - x₁ . Gdy Xj = 0, to *2=7. Gdy = 7, to ⁼ 0 . Zatem prosta x₁ + x₂ =7 przechodzi przez punkty o współrzędnych (0; 7) i (7; 0). Półpłaszczyzna odpowiadająca nierówności 3x_x -t-3x₂ <121 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 Xj +2x₂ <18 oraz 5x^20 (czyli >^^4). Po uwzględnieniu warunków brzegowych x, SrO, x₂2 0 otrzymujemy wielokąt przedstawiony (zakreskowany) na rysunku Wszystkie punkty czworokąta O ABC (w szczególności wierzchołki O, A, B, C) reprezentują rozwiązania dopuszczalne zadania. Widzimy tu, że półpłaszczyzna 3Xj -t-3x₂ <121 (obrazująca ograniczenie surowca Si) nie ma wpływu na kształt otrzymanego wielokąta. Oznacza to, że przy każdej decyzji dopuszczalnej surowiec Si nie będzie wykorzystany w pełni. Ograniczenie 3x_x -f-3x₂ <121 można opuścić i nie zmieni to zbioru dopuszczalnego.

1