ZADANIE 7

ZADANIE 7 (5.1) Rozwiąż program liniowy: f.c.:

7 x1 + 2 x 2 → max

8 x1 + 4 x 2 ≤ 40 2 x + 16 x ≤ 30  1 2   x1 + x 2 ≤ 5 6 x1 − 4 x 2 ≤ 0

x1 , x 2 ≥ 0 Rozwiązanie Zadanie rozwiązujemy metodą graficzną. Nanosimy ograniczenia na układ współrzędnych x1,x2:

8 x1 + 4 x2 ≤ 40 Obrazem tego ograniczenia na płaszczyźnie x1,x2 jest prosta 8 x1 + 4 x 2 = 40 , która przechodzi m.in. przez punkty (0; 10), (5; 0) wraz z obszarem leżącym poniżej tej prostej.

2 x1 + 16 x 2 ≤ 30 Obrazem tego ograniczenia na płaszczyźnie x1,x2 jest prosta 2 x1 + 16 x 2 ≤ 30 , która przechodzi m.in. przez punkty (15; 0), (7; 1) wraz z obszarem leżącym poniżej tej prostej.

x1 + x2 ≤ 5 Obrazem tego ograniczenia na płaszczyźnie x1,x2 jest prosta x1 + x2 ≤ 5 , która przechodzi m.in. przez punkty (0; 5), (5; 0) wraz z obszarem leżącym poniżej tej prostej.

6 x1 − 4 x2 ≤ 0 Obrazem tego ograniczenia na płaszczyźnie x1,x2 jest prosta 6 x1 − 4 x2 ≤ 0 , która przechodzi m.in. przez punkty (0; 0), (4; 6) wraz z obszarem leżącym powyżej tej prostej.

Warunki

brzegowe

współrzędnych.

x1 , x 2 ≥ 0

ograniczają

obszar

do

pierwszej

ćwiartki

układu

Obszar dopuszczalny zadania jest częścią wspólną wszystkich wyszczególnionych wyżej obszarów. Przedstawiono go na poniższym rysunku (zaznaczono na żółto) – jest nim pewien trójkąt AOB.

Wewnątrz obszaru dopuszczalnego nanosimy gradient funkcji celu – jest nim wektor r o składowych równych współczynnikom funkcji celu (u nas u = [7; 2] ). Prostopadle do gradientu rysujemy izokwantę funkcji celu. Gradient wskazuje kierunek przesuwania się izokwanty wraz ze wzrostem wartości funkcji celu. Ostatni fragment obszaru dopuszczalnego, przez który przesuwająca się izokwanta opuści ten obszar, odpowiada rozwiązaniu optymalnemu. Jak widać na rysunku, punktem tym jest punkt A, będący punktem wspólnym (punktem przecięcia) się prostych: 6 x1 − 4 x 2 = 0 oraz 2 x1 + 16 x 2 = 30 . Jego współrzędne znajdujemy rozwiązując układ równań:

 6 x1 − 4 x 2 = 0  2 x1 + 16 x 2 = 30 4 x 2 = 6 x1 / : 4  2 x1 + 16 x 2 = 30

 x 2 = 1,5 x1  2 x1 + 16 x 2 = 30  x 2 = 1,5 x1  26 x1 = 30 / : 26 3   x 2 = 2 ⋅ x1  15  x1 = 13  15   x1 = 13 = 1,1538  45  x2 = = 1,7308 26 

Optymalnym rozwiązaniem jest zatem:

15   x1 = 13 = 1,1538  45  x2 = = 1,7308 26 

Optymalna wartość funkcji celu wynosi: 15 45 150  15 45  f max  ;  = 7 ⋅ + 2 ⋅ = = 11,538 13 26 13  13 26  Podane z treścią rozwiązanie (x1 = 2; x2 = 3; fmax = 20) jest nieprawdziwe – nie spełnia ograniczenia 2 x1 + 16 x 2 ≤ 30 .