022 023 2

22 Programowanie liniowe

Przykład l.l³

Należy zaplanować produkcję zakładu w pewnym tygodniu w taki sposób, aby osiągnięty zysk był maksymalny. Zakład może wytwarzać dwa produkty: P, i P₂. leli produkcja jest limitowana dostępnymi zasobami trzech środków: 5j, S₂ i S₃. Zasoby tych środków wynoszą, odpowiednio, 14, 8 i 16 jednostek. Nakład środka Sj na wytworzenie jednostki produktu P, wynosi 2 jednostki, a na wytworzenie produktu P₂ — również 2 jednostki. Nakłady środka S₂ wynoszą, odpowiednio, I i 2 jednostki, natomiast środka S₃ —4 i 0 jednostek. Zysk osiągany z wytworzenia jednostki produktu P| wynosi 2 jednostki, a z wytworzenia jednostki produktu P₂ — 3 jednostki. Dane zadania przedstawiono w tablicy 1.1.

Tablica l.l

	P,	Pt	Zasoby
5,	2	2	14
S2	1	2	8
s.	4	0	16
Zysk	2	3

W rozważanym przez nas zagadnieniu programowania produkcji celem jest maksymalizacja zysku. Aby ten cel osiągnąć, można rozważać różne wielkości produkcji produktów P, i P₂. Produkcja związana jest z wykorzystaniem środków Sj, S₂ i których dostępność jest ograniczona. Tak więc w rozpatrywanym przez nas problemie decyzyjnym nie mamy możliwości zwiększenia ilości środków S„ S₂ i S₃, a zatem są to ustalone parametry zadania⁴.

Ponieważ decydujemy o wielkości produkcji wyrobów P, i P₂, zmiennymi decyzyjnymi są:

j(i — planowana wielkość produkcji wyrobu P,, x₂ — planowana wielkość produkcji wyrobu P₂.

Zysk otrzymany z wytworzenia produktu P, na poziomie x, wynosi 2jc,, natomiast zysk osiągany z wytworzenia produktu P₂ na poziomie x₂ wynosi 3j:₂. Funkcję celu, wyznaczającą łączny zysk, obliczymy z zależności:

/(x,, x₂) = 2x, + 3jc₂. g/oS&ł-w.' I    r :/■■■■    •<

i V

¹ Wartości liczbowe tego przykładu zaczerpnięto z książki W. Grabowskiego. Programowanie matematyczne» PWE, Warszawa 1480.

¹ Można również rozpatrywać możliwość zmiany zasobów produkcyjnych w interesującym nas odcinku czasu. Zagadnieniem takim zajmiemy się w podrozdziałach 1.8.2 i 1.9.3 oraz w rozdziale 2.

Ustalając plan produkcji, musimy uwzględnić dostępne zasoby środków ój, S₂ i S_y Wytwarzając l\ na poziomie x_h wykorzystamy 2x, jednostek środka S,, natomiast wytwarzając P₂ na poziomie x₂ wykorzystamy 2x₂ jednostek środka S,. Łączne wykorzystanie tego środka wynosi 2x, + 2x₂ i nie może być większe od 14 jednostek, stąd otrzymujemy nierówność:

2*, + 2*₂ « 14.    (l.l)

Podobne ograniczenia występują dla dwóch pozostałych środków. Dla S₂ otrzymujemy:

.y,+2jc₂<8,    (1.2)

natomiast dla S_} mamy:

4x, < 16.    (1.3)

Oczywiście wartości zmiennych decyzyjnych muszą być nieujemne, stąd mamy dodatkowo:

x,^0,    (1.4)

x₂>0.    (1.5)

Zauważmy, że określając w powyższy sposób funkcję celu i ograniczenia, wykorzystujemy założenie proporcjonalności i założenie addytywności. W przypadku funkcji celu założenie proporcjonalności pozwala przyjąć, że zysk zarówno dla produktu Pj, jak i produktu Pjjest proporcjonalny do skali produkcji. Założenie addytywności pozwala przedstawić łączny zysk jako sumę zysków otrzymanych z wytworzenia produktów P, i P₂. Te same założenia przyjęte są przy konstrukcji ograniczeń występujących w rozpatrywanym zadaniu. Oczywiście trzeba każdorazowo sprawdzić, czy przyjęcie tych założeń jest uzasadnione.

Łącząc ze sobą warunki (l.l)—(1.5), otrzymujemy następujące zadanie:

zmaksymalizować funkcję:

f(xi, x₂) = 2x_[ + 3x₂,

przy warunkach ograniczających:

2jc, + 2x₂    14,

+ 8, ^J 4jc, « 16, x, >0, x₂ 5* 0.

Jeżeli wszystkie warunki ograniczające są nierównościami, to mamy postać klasyczną zadania.