030 031 2

30 Programowanie liniowe

Ze względu na to, że funkcja celu jest liniowa, wartości pochodnych cząstkowych są stale. Wykreślamy gradient funkcji celu, zaczepiając jego początek w początku układu współrzędnych. Każda warstwica funkcji celu jest prostopadła do wykreślonego gradientu. Jego zwrot wskazuje na to, w jaki sposób należy rozpatrywać kolejne (równolegle do siebie) warstwice funkcji celu, by znaleźć rozwiązanie dopuszczalne, maksymalizujące jej wartość (rys. 1.10)^s.

Rysunek 1.10

A

Z;

1.3. Metoda simpleks

1.3.1. Postać bazowa

Rozwiązywanie zadań programowania liniowego metodą geometryczną, choć nie nastręcza kłopotów, nie jest jednak sposobem zadowalającym w przypadku poszukiwania rozwiązań optymalnych problemów praktycznych, gdyż zazwyczaj liczba zmiennych decyzyjnych jest w nich znacznie większa od dwóch. Wykorzystujemy wówczas metodę simpleks. Aby ją zastosować, należy najpierw przekształcić zbiór warunków ograniczających do postaci układu równań liniowych. Zadanie, w którym wszystkie warunki ograniczające są w postaci równości, nazwiemy zadaniem w postaci standardowej.

W przykładzie 1.1 mamy ograniczenie związane z wykorzystaniem zasobu środka ,Sj:

2*1 + 2jc₂ < 14.

⁵ W przypadku zadania minimalizacji należy zmienić zwrot wektora gradientu na przeciwny i następnie postępować w analogiczny sposób.

Możemy zapisać je w postaci równania:

2x, + 2x₂+x₃ = 14,

dodając do lewej strony zmienną bilansującą x₃, określoną jako różnicę wartości prawej i lewej strony rozpatrywanej nierówności, czyli: jc₃= 14— 2jc, —0.

Wartość x₃ określa, jaka ilość środka S, pozostanie niewykorzystana w przypadku realizacji planu (jc,, x₂).

Dwa pozostałe warunki ograniczające przekształcamy do postaci równań liniowych przez wprowadzenie dodatkowych zmiennych bilansujących: x_A do warunku (1.2) oraz x₃ do warunku (1.3). Otrzymujemy:

X_|+2x₂+J.₄=8, przy czym: j = 8—jc i — 2*2 > 0, oraz

4x, + x₅ = 16, przy czym: x₅ = 16 — 4jc , > 0.

Wartości x₄ i .c₅ określają, jakie ilości środków, odpowiednio, S₂ i S₃ pozostaną niewykorzystane w przypadku realizacji planu (.r,, x₂).

W dalszych rozważaniach rozpatrzymy zadanie w postaci standardowej, w której wszystkie warunki ograniczające (z wyjątkiem warunków nieujemności) są równaniami. Dla rozpatrywanego przez nas zadania postać ta jest następująca:

(~)

/(jc,, x₂, x₃, x₄, xj) = 2x, + 3x₂ —¥ max, 2x,+2x₂+X3    =14,

x, + 2x₂    +.c₄    = 8,

4x,    +x_s=16,

x_b x₂, x,, x₄, x₅ > 0.

Współczynniki funkcji celu tworzą wektor funkcji celu c, współczynniki warunków ograniczających wchodzą w skład macierzy współczynników A., prawe strony warunków ograniczających przedstawiamy w postaci wektora warunków ograniczających b, natomiast zmienne występujące w zadaniu — jako wektor zmiennych x. Ponadto symbolem 0 oznaczymy wektor, którego wszystkie składowe są zerami. Problem programowania liniowego możemy zapisać jako zadanie w postaci macierzowej. Mamy:

cx —> max, Ax= b. x2ł0.