Algorytm sympleks wymaga by obszar dopuszczalny, na którym badamy ekstrema funkcji celu, był wielościanem z wierzchołkiem. Dowolny wielościan możemy ”przerobić” na wielościan z wierzchołkiem przechodząc do zadania równoważnego i zamieniając zmienne tak by były nieujemne.

Jeżeli xi≤0 to zastępujemy je nową zmienną xi′=-xi, gdzie xi′≥0.

Jeżeli xi∈R jest nieograniczone to zastępujemy je różnicą xi=xi+-xi-, gdzie xi+=≥0 oraz xi-=≥0.

W szczególności w tym rozdziale będziemy badać wielościany zapisane w postaci kanonicznej czyli W=x∈Rn⁢|⁢A⁢xT=b,⁢x≥0.

Opis wierzchołków i krawędzi zadania P⁢L w postaci kanonicznej.

Niech W=x∈Rn⁢|⁢A⁢xT=b,⁢x≥0 będzie wielościanem. Dodatkowo zakładamy, że równania opisujące W są liniowo niezależne - czyli r⁢z⁢A=t= liczba równań.

Niech p będzie wierzchołkiem W. Ze zbioru równań i ”nierówności spełnionych jako równości” które spełnia wierzchołek p wybieramy n liniowo niezależnych w specjalny sposób. Po pierwsze wybieramy t równań A⁢xT=b opisujących wielościan a potem uzupełniamy do n liniowo niezależnych równań dodając pewne xi=0.

Wynika to z lematu Steinitza o bazie. Dokładniej: ze zbioru równań spełnianych przez p wybieramy dowolnie bazę A - n liniowo niezależnych równań. Następnie zbiór liniowo niezależny A⁢xT=b uzupełniamy do bazy równaniami z A. Muszą to być równania typu xi1=0,xi2=0,…,xin-t=0 Otrzymaliśmy układ n liniowo niezależnych równań z n niewiadomymi, którego jedynym rozwiązaniem jest punkt p. Macierz tego układu oznaczmy literą U.

Zmienne i1,…,in-t nazywamy niebazowymi zaś pozostałe bazowymi.

Współrzędne niebazowe wierzchołka p są równe 0.

Uwaga: Wierzchołek ma co najwyżej t niezerowych współrzędnych.

Dla ułatwienia przenumerujmy tak zmienne by 1,2,…,n-t były zmiennymi niebazowymi oraz n-t+1,…,n zmiennymi bazowymi.

Wtedy macierz równania opisującego W składa się z 3 części A=N⁢B⁢b, gdzie B jest macierzą kwadratową.

r⁢z⁢U=n⇒r⁢z⁢B=t⇒B jest odwracalna.

Mnożąc układ równań A⁢xT=b z lewej strony przez macierz B-1 otrzymujemy równoważny opis wielościanu W

[B-1N|I]xT=B-1b=[b1⋮bt]

Zaś wierzchołek ma współrzędne p=0,…,0,b1,b2,…,bt.

Podsumowując, każdemu wierzchołkowi, przez wybór zmiennych bazowych przyporządkowujemy układ równań o macierzy zawierającej podmacierz jednostkową.

Jak pokazaliśmy poprzednio każdemu wierzchołkowi odpowiada co najmniej jedna tablica sympleks pierwotnie dopuszczalna. Dokładniej tyle tablic ile jest możliwości wyboru zmiennych (nie)bazowych.

W jest opisane układem nierówności:

2⁢x1+x3≤2

2⁢x2+x3≤2

x1,x2,x3≥0

Przerabiamy nierówności na równania dodając nowe zmienne i otrzymujemy postać kanoniczna:

2⁢x1+x3+x4=2

2⁢x2+x3+x5=2

x1,x2,x3,x4,x5≥0

Zapiszmy w postaci tablicy sympleks:

T⁢S1=x1x2x3x4x5w⁢w201102021012

Zmiennymi bazowymi są x4 i x5 zaś T⁢S1 opisuje wierzchołek:

p1¯=(0,0,0| 2,2),

Poruszamy się w kierunku wierzchołka p5¯ krawędzią wyznaczoną przez x3:

T⁢S1=↓x1x2x3x4x5w⁢w201102021012.

Szukamy elementu centralnego.

M⁢i⁢n⁢21,21=2 zatem możemy wybrać dowolny element kolumny 3-ciej.

T⁢S2=k1k2k32-201-10021012. Zmiennymi bazowymi są teraz x3 i x4 zaś T⁢S2 opisuje wierzchołek p5¯=(0,0,2| 0,0)

Ile krawędzi wychodzi z W?

Z rysunku widać, że 4, zaś tablica T⁢S2 opisuje tylko trzy krawędzie o wektorach kierunkowych
k1→1,0,0,-2,0 - krawędź zdegenerowana (długość 0) gdyż Min{02,∗}=0
k2→0,1,-2,2,0 w kierunku wierzchołka p3¯
k3→0,0,-1,1,1 w kierunku wierzchołka p1¯

Wędrując wzdłuż krawędzi zdegenerowanej k1 znajdujemy nową TS opisującą p.

Otrzymujemy k12-201-10021012→1-1012-120021012BB=T⁢S3

Tablica T⁢S3 opisuje dalej wierzchołek p5¯ i krawędzie:

k4k5k61-1012-120021012BB

k4→1,1,-2,0,0 w kierunku wierzchołka p4¯

k5→-12,0,0,1,0 - zdegenerowana k6=-12⁢k1

k6→12,0,-1,0,1 w kierunku wierzchołka p2¯

Wędrowanie między wierzchołkami, eliminacja Gaussa - Jordana.

W zadaniu PL mamy wierzchołek p opisany tablicą sympleks. Dla ustalenia uwagi przyjmijmy x0x1…xtxt+1…xi…xnw⁢w10…0-ct+1…-ci…-cnb001…0a1,t+1…a1,i…a1,nb1⋮⋮⋱⋮⋮⋱aj,i⋱⋮⋮00…1at,t+1…at,i…at,nbt

Zakładamy, że krawędź odpowiadająca zmiennej xi jest skończona i szukamy tablicy sympleks opisującej drugi koniec tej krawędzi.

Wyliczamy minimum po wszystkich dodatnich aj,i z liczb bjaj,i czyli liczbę

M⁢i⁢nj⁢bjaj,i⁢⁢⁢aj,i⁢0. Wybieramy dowolny współczynnik aj,i, na którym osiągane jest minimum. Nazywamy go elementem centralnym. Na następnej tablicy zaznaczony będzie nawiasem.

x0x1…xj…xtxt+1…xi…xnw⁢w10…0…0-ct+1…-ci…-cnb001…0…0a1,t+1…a1,i…a1,nb1⋮⋮⋱⋮⋱⋮⋮⋱…⋱⋮⋮00…1…0aj,t+1…aj,i…aj,nbj⋮⋮⋱⋮⋱⋮⋮⋱…⋱⋮⋮00…0…1at,t+1…at,i…at,nbt

Teraz j - ty wiersz dzielimy przez aj,i zaś od każdego innego wiersza k odejmujemy poprawiony j-ty wiersz pomnożony przez ak,i - czyli zerujemy pozostałe miejsca k-tej kolumny. Otrzymujemy macierz:

x0x1…xj…xtxt+1…xi…xnw⁢w10…d0…0-ct+1*…0…-cn*b0*01…d1…0a1,t+1*…0…a1,n*b1*⋮⋮⋱⋮⋱⋮⋮⋱…⋱⋮⋮00…dj…0aj,t+1*…1…aj,n*bj*⋮⋮⋱⋮⋱⋮⋮⋱…⋱⋮⋮00…dt…1at,t+1*…0…at,n*bt*,

gdzie d0=ciaj,i,d1=-a1,iaj,i,…,⁢dj-1=-aj-1,iaj,i,dj=1aj,i,dj+1=-aj+1,iaj,i,…,dt=-at,iaj,i

Otrzymaliśmy tablicę sympleks. Z bazy wypadła zmienna xj a doszła zmienna xi.

Test optymalności i koszty zredukowane. Rozważamy zadanie typu

opisane tablicą sympleks TS. Oznacza to, że w górnym wierszu TS mamy kolejno liczby

. Ponieważ jest to tablica sympleks wszystkie współczynniki ci odpowiadające zmiennym bazowym są równe 0.

Jeżeli koszt zredukowany -cj odpowiadający zmiennej niebazowej xj jest <0 ( cj>0 ) to krawędź wyznaczona przez zmienną xj jest poprawiająca. Ponieważ wędrując tą krawędzią zmieniamy tylko zmienne bazowe nie mające wpływu na funkcję celu i zwiększamy liczbę x0=cj⁢xj+b0.

Jeżeli koszt zredukowany -cj odpowiadający zmiennej niebazowej xj jest = 0 ( cj=0 ) to krawędź wyznaczona przez zmienną xj jest neutralna.

Jeżeli koszt zredukowany -cj odpowiadający zmiennej niebazowej xj jest >0 ( cj<0 ) to krawędź wyznaczona przez zmienną xj jest pogarszająca. Ponieważ wędrując tą krawędzią zmieniamy tylko zmienne bazowe nie mające wpływu na funkcję celu i zmniejszamy liczbę

.

Z twierdzenia 5.4 otrzymujemy bezpośrednio: