1636661679

10

2. METODA SYMPLEKSOWA

3. Ograniczenia x > 0 mogą mieć inną postać:

(a)    ograniczenie Xj > dj zamieniamy na ograniczenie x'j > 0 wprowadzając nową zmienną x'j taką, że x'j — Xj — dj;

(b)    ograniczenie Xj < dj zamieniamy na ograniczenie x'j > 0 wprowadzając nową zmienną x'j taką, że x'j = dj — Xj\

(c)    ograniczenie Xj > dj zamieniamy na ograniczenia x'j, x" > 0 wprowadzając nowe zmienne x'j, x" takie, że Xj = x'j — x" (korzystamy tutaj z faktu, że każda liczba rzeczywista może być przedstawiona jako różnica liczb nieujemnych).

W dalszej części wykładu będziemy zakładać, że mamy dane zagadnienie programowania liniowego w postaci standardowej.

2.2. Punkty ekstremalne i wektory kierunkowe ekstremalne

Łatwo jest udowodnić (zadanie na ćwiczenia), że jeśli funkcja liniowa osiąga minimum (lub maksimum) na zbiorze wypukłym, to musi ona osiągać to ekstremum również w punktach ekstremalnych tego zbioru. Dlatego poniżej poniżej omówimy tematykę związaną z punktami ekstremalnymi. Głównie skupimy się na charakteryzacji punktów ekstremalnych zbiorów dopuszczalnych.

Niech X C Rⁿ będzie zbiorem wypukłym. Punkt x € X nazywamy ekstremalnym, jeśli

VWx''A₆(₀,i) p = (1 - \)x + Xy =*• x = y = p.

Przykład 2.4. Oznaczmy przez E zbiór punktów ekstremalnych zbioru

X.

(i) Dla zbioru X = •

dzącego z Przykładu 1.1, E -(ii) X = {(xi,x₂) G M²;zi +

{[:

1 1 3 1 1 0 0 1

]}■

■ pocho-

x\ <!},£’ = {(^1,^2) G M²;x² + x% = 1}.