Jeżeli zadanie PL opisane jest macierzą, która nie ma postaci tablicy sympleks, to by móc stosować metodę sympleks stosujemy chwyt genialny w swej prostocie - dopisujemy macierz jednostkową. Dokładniej:

Dwufazowa metoda sympleks

Badamy zadanie:

M⁢a⁢x⁢⁢x0=c⁢x

A⁢x=b

x≥0

macierzą układu jest [A|b]

Mnożąc w razie potrzeby niektóre równania przez -1 możemy przyjąć, że b≥0. Aby uzyskać T⁢S dopisujemy macierz jednostkową i otrzymujemy tablicę sympleks T⁢S=A⁢I⁢b.

Odpowiada temu układ równań

A⁢x+I⁢y=b

gdzie y=y1y2⋮yt⁢⁢A=a1,1a1,2…a1,n⋮⋮⋱⋮at,1at,2…a1⁢t,n

Pierwsza faza

Rozwiązujemy  zadanie PL(∗):Maxy0=-y=-y1-y2-…-yt

A⁢x+I⁢y=b

x≥0⁢⁢y≥0

zadanie (∗) jest ograniczone ponieważ y≥0⇒y0≤0. Dodatkowo jeżeli p należy do obszaru dopuszczalnego zadania pierwotnego, czyli A⁢p=b p≥0 to

p¯=p,0,…,0 jest punktem optymalnym (∗) gdyż

[A|I]p¯=A[p1⋮pn]+I[0⋮]=b

zaś y0⁢p¯=0

I Przypadek:

Jeżeli w rozwiązaniu optymalnym zadania (∗) y0⁢m⁢a⁢x<0 to wielościan W=x∈Rn⁢|⁢A⁢x=b⁢⁢x≥0 jest zbiorem pustym (zadanie pierwotnie sprzeczne).

II Przypadek:

Jeżeli y0⁢m⁢a⁢x=0 to T⁢S opisująca wierzchołek optymalny zadania (∗) pozwala nam opisać wierzchołek zadania pierwotnego.

T=A¯⁢D⁢b¯

a) Jeżeli wszystkie zmienne y1,y2,…,yt są niebazowe to macierz powstała po wykreśleniu kolumn z nimi związanych jest T⁢S opisująca wierzchołek obszaru dopuszczalnego zadania pierwotnego.

Rzeczywiście. Jeżeli (p1,..,pn,y1,…,yt) jest wierzchołkiem opisanym A¯⁢D⁢b¯ to y1=0,…,yt=0, A¯⁢p=b¯

(A¯ zawiera macierz jednostkową)

[A¯|b¯] powstała z [A|b] przez operacje elementarne na wierszach, więc opisuje ten sam wielościan.

b) Niech yi będzie zmienną bazowa. Przyjmijmy, że kolumna odpowiadająca yi ma jedynkę w j-tym wierszu i pozostałe współrzędne =0.

10  jeżeli wiersz j-ty ma tylko jeden element niezerowy ( j⁢- ty wiersz A¯ jest zerowy ) to znaczy, że [A|b] i A były układem zależnym. Taki wiersz i kolumny można wykreślić ( w praktyce zostaje).

20  Jeżeli oprócz jedynki odpowiadającej yi istnieje aj,r≠0 w j-tym wierszu macierzy A¯ to wybieramy go jako element centralny i po przekształceniach elementarnych otrzymujemy T⁢S, w której yj jest niebazowe, zaś xr jest dołączone do bazy.

Po wykonaniu I fazy otrzymujemy T⁢S opisującą wierzchołek obszaru dopuszczalnego T lub informację, że zadanie było sprzeczne.

Druga faza:

Najpierw budujemy wiersz kosztów zredukowanych

M⁢a⁢x⁢⁢x0=c⁢x

Koszty zredukowane to x0=d⁢x+b0 gdzie d=d1,…,dn to dj=0 gdy xj - bazowa. Wektor d wyliczamy wstawiając do równania x0=c⁢x

równania xj=bj¯-aj⁢i⁢xi pochodzące z T⁢S [A*|b*] = a1,1a1,2…a1nb1*⋮⋮⋱⋮⋮at,1at,2…at,nbt*

Dalej zadanie rozwiązujemy prosta metodą sympleks.

1. Metoda częściowej bazy sztucznej

W metodzie dwufazowej wystarczy dodać tylko tyle zmiennych sztucznych, by otrzymać macierz jednostkową.

np.

M⁢a⁢xx0=c⁢x

A1⁢x≤b1

A2⁢x=b2

x≥0

W tym przypadku mamy t1 zmiennych bazowych i gdy b1≥0 dodajemy tylko t2 zmiennych sztucznych.

M⁢a⁢x⁢⁢x0=c⁢x

A1⁢x+It1⁢x¯=b1

A2⁢x+It2⁢y=b2

x≥0

x¯≥0

y≥0

W przypadku rzeczywistych obliczeń ( na maszynach) zwykle nie stosuje się częściowej bazy sztucznej. Nie trzeba wówczas wyszukiwać w macierzy A kolumn zero - jedynkowych.

2. Można obie fazy rozwiązać na jednej T⁢S. W zadaniu:

M⁢a⁢x⁢⁢x0=c⁢x

A⁢x=b

x≥0

Rozważamy obie funkcje celu jednocześnie.

M⁢a⁢x⁢⁢x0=c⁢x

M⁢a⁢x⁢⁢y0=-y

A⁢x+I⁢y=b

x≥0⁢⁢y≥0

Budujemy tablicę sympleks mającą dwa wiersze nad kreską.

T⁢S=B-1¯⋅x0y0x1x2…xny1…ytw⁢w10-c0…000100…01…1000AIb,

gdzie

B¯=100...0011...100I

W fazie 1 maksymalizujemy y0 i w rezultacie otrzymujemy, że zadanie jest sprzeczne lub T⁢S opisująca wierzchołek startowy (łącznie z kosztami zredukowanymi funkcji x0).

Ta metoda nigdy nie prowadzi do zmniejszenia liczby operacji (np. wyszło, że zadanie jest sprzeczne, więc naliczyliśmy się zupełnie niepotrzebnie).

3 Metoda dużego M.

Czasami potrafimy oszacować wartość x0 i m⁢a⁢x⁢⁢xi. Szczególnie w zagadnieniach całkowitoliczbowych np. transport ciężarówkami i gdy wśród warunków są 0≤xi≤bi.

Aby rozwiązać zadanie: M⁢a⁢x⁢⁢x0=c⁢x

A⁢x=b

x≥0

wybieramy liczbę M dostatecznie dużą i rozpatrujemy zadanie M⁢a⁢x⁢⁢x0¯=c⁢x-M⁢y

A⁢x+I⁢y=b

x≥0⁢⁢y≥0.

Teraz poprawione zadanie opisane jest tablicą sympleks:

T⁢S=-c-d⁢M0...0-M⋅∑biAIb,

gdzie wektor d jest sumą wierszy macierzy A.

Rozwiązanie zawsze istnieje, ale czasami w opisie kosztów zredukowanych wierzchołka optymalnego występuje M - oznacza to, że zadanie wyjściowe jest sprzeczne. W stosunku do poprzednich metod zyskujemy to, że mamy jedną fazę i jedną funkcję celu.