Picture4

7.9. Metoda gni liczna dla zagadnienia programowania

liniowego

Każde zagadnienie, w którym należy znaleźć nieujemne rozwiązanie układu równań liniowych (nierówności liniowych), przy których funkcja liniowa /(v, r) a\ l by + c osiąga wartość najmniejszą lub największą, nazywamy za gadnicniem programowania liniowego (szczegółowe omówienie tego zagadnienia można znaleźć np. w książce T. Stanisza pt. Zastosowanie matematyki w ekonomii, Trapez, Kraków 1998).

Przykład 7.12

Pewien zakład produkuje dwa wyroby 1 i II. Do produkcji tych wyrobów wykorzystywane są dwa surowce S| i Si. Nakłady surowców potrzebne do wyprodukowania jednostki każdego z wyrobów' podaje tabela:

Surowiec	Wyrób		Zasoby surowca
	I	II
5,	1	2	6
s2	2	1	9

Zysk jednostkowy dla wyrobu I wynosi 4, dla wyrobu II - 3. Należy ustalić plan produkcji zapewniający maksymalny zysk.

Budujemy najpierw model matematyczny tego zagadnienia. Niech x oznacza planowaną liczbę jednostek wyrobu I, y-planowaną liczbę jednostek wyrobu II. Naturalnie x > 0 iy > 0.

Warunki ograniczające wynikające z ograniczonych zasobów surowcowych są następujące:

jx+2y<6 [2x + y<9

zaś funkcja zysku: f(x, y) = 4x + 3y.

Zadanie więc wygląda następująco: znaleźć wartość największą funkcji: f(x, y) = 4x + 3y,

przy warunkach •

x + 2y < 6, 2x + y< 9, x > 0, y> 0.

KnAdy / powyższych warunków (nierówności) określa pcwni| pólpliis/c/> /n\ w przestrzeni dwuwymiarowej Układ tych warunków wyznacza pewien obs/m l> na płaszczyźnie. Obszai len nazywamy zbiorem rozwii|z,iiń dopuszc/alnyUi (>bszar I) z powyższego przykładu przedstawia rys. 7.3.

Rys. 7.3. Zbiór ograniczeń z przykładu 7.12

Obszar ten jest ograniczony, a więc funkcja f(x,y) osiąga w nim wartość największą i najmniejszą, przy czym te wartości - na podstawie odpowiedniego twierdzenia dotyczącego rozwiązań zagadnień programowania liniowego osią ga w wierzchołkach tego zbioru D.

Wyznaczamy więc współrzędne punktów A, B \ C. A - to punkt przecięciu się prostej x + 2y = 6 z osią 0y, stąd A(0, 3), C - to punkt przecięcia się prostej 2x +y = 9 z osią 0x, więc C(4,5; 0), B - to punkt przecięcia się obu wymieniu nych prostych ograniczających zbiór D. Z układu równań:

f jc + 2y = 6 \lx + y = 9

znajdujemy współrzędne punktu B{4, 1). Obliczamy wartości funkcji w punk tach 0, A, B, C:

/(O) =/0; 0) = 0; f{A) =/(0, 3) = 9; f(B) =/(4, 1) = 19; /(C) =/(4,5; 0) = IX.

Największą wartość funkcja f(x,y) = 4x + 3y przy zadanych warunkach (czyli w obszarze D) osiąga w punkcie B(4, 1). Czyli aby osiągnąć największy zysk. należy wyprodukować 4 jednostki produktu 1 i 1 jednostkę produktu II.