8107620633

Definicja 3 Rozwiązaniem optymalnym nazywamy rozwiązanie dopuszczalne minimalizujące funkcję celu (1), tj. wektor x E D spełniający warunek cx = min cx. Zbiór rozwiązań optymalnych oznaczamy symbolem T>_opi.

Zadanie PL polega więc na tym, aby ze zbioru rozwiązań układu m równań, spełniających warunki nieujemności, wyznaczyć takie rozwiązanie, przy którym funkcja celu osiąga wartość minimalną. W postaci skalarnej problem PL możemy zapisać następująco: zminimalizować wyrażenie

ClXi + . . . + CnX_n

^all^l+	+ciinxn = bi
Oml^l +	+amnxn = b„
X! > 0
xn > 0.

przy warunkach

Problem (1) - (3) nazywany jest problemem programowania liniowego w postaci standardowej (dla odróżnienia od innych postaci). Inne postacie problemu PL można sprowadzić do postaci (1) -(3). Wyróżniamy trzy sytuacje:

(i)    Funkcja cx ma być zmaksymalizowana. Wtedy minimalizujemy funkcję — cx.

(ii)    Niektóre z warunków (2) mają postać nierówności liniowych. Rozpatrzmy na przykład warunek postaci anaą +... + ai„:c_n < b\. Warunek ten zastępujemy warunkami dnX\ +... + ai„a;_n + x_n+i = b\ oraz a:_n+i > 0, czyli do problemu PL wprowadzamy nową zmienną x_n+\ := bi — (an^i + • • • + ai„a;_n), która na podstawie początkowego warunku daje nierówność x_n+i > 0.

(iii)    Niektóre zmienne przyjmują dowolne wartości rzeczywiste (mogą być ujemne). Niech na przykład x\ E R, czyli może przyjmować wartości ujemne. Wówczas do problemu wyjściowego podstawiamy: x\ = x\ — x[ gdzie x\,x'[ > 0, otrzymując równoważny problem.

Definicja 4 Problem PL nazywamy sprzecznym, jeśli zbiór rozwiązań dopuszczalnych V określony w (4) jest zbiorem pustym.

Uwaga 1 W dalszym ciągu rozważać będziemy wyłącznie problem PL, w którym macierz A jest rzędu m, czyli problem PL, który nie zawiera równań liniowo zależnych (można je wyeliminować i nie zmieni to zbioru rozwiązań).

Załóżmy teraz, że X := M_nil dla dowolnie ustalonego n e N.

Definicja 5 Niech a € Mi,„, x G X, b £ R. Jeśli a ^ 0, to zbiór

:= {x : ax < b}    (5)

nazywamy półprzestrzenią domkniętą, zaś zbiór

{x : ax = b}    (6)

nazywamy hiperpłaszczyzną.

3