MOO wykład – Programowanie

Liniowe

i Algorytm Sypleks I

• Przykład
Zadania Programowania Liniowego
(ZPL);

Rysunek 1

Uwagi –

- dla obszaru dopuszczalnego

zamkniętego

• Rozwiązania ZPL znajdują się w wierzchołkach

obszaru dopuszczalnego (rozwiązanie pojedyncze)

lub na jego krawędzi (wtedy jest ich nieskończenie

wiele, ale 2 są również w wierzchołkach).

• Algorytm Sympleks polega na przeszukiwaniu

wierzchołków ograniczeń tak, aby wartość funkcji

docelowej rosła (dla problemu maksymalizacji).

• Uwaga: ZPL musi mieć tzw. Formę standardową

Forma standardowa ZPL

• Jeśli ZPL nie ma formy standardowej,

to wprowadzamy dodatkowe zmienne
zwane zmiennymi bilansującymi
pamiętając, że muszą być one
nieujemne.

Ilustracja dla przykładu z rysunku 1

Kroki alg. Sympleks

• Spośród zmiennych ZPL wyodrębnij tzw. zmienne bazowe i

zmienne swobodne.

• Sprowadź ograniczenia do tzw. postaci kanonicznej, tzn.

takiej, w której zmienna bazowa występuje tylko w 1

ograniczeniu i współczynnik przy niej wynosi 1.

• Przyrównaj zmienne swobodne do zera, w ten sposób

otrzymasz tzw. Pierwsze rozwiązanie bazowe, jeśli jego

współrzędne są nieujemne, to jest to tzw. Pierwsze

rozwiązanie bazowe dopuszczalne.

• Rozwiązanie to, to nic innego jak współrzędne jednego z

wierzchołków ograniczeń

Kolejne kroki Algorytmu

Sympleks

• Teraz trzeba znaleźć metodę, aby przeskakiwać z

wierzchołka na wierzchołek (zmieniać bazy) tak, aby

wartość funkcji docelowej rosła.

• Służy do tego tzw. Tablica Sympleksowa

Tablica dla zadania z rysunku 1

• Aby poprawnie zapisać pierwszą tablicę, funkcja docelowa

musi być wyrażona poprzez zmienne swobodne.

• Współczynniki przy tych zmiennych informują, czy bieżąca

baza jest rozwiązaniem optymalnym ZPL.

•

Zdecyduj, czy tablica ta opisuje rozwiązanie optymalne

Zadania.

•

Uwaga. 1 tablica dla przykładu z rys.1 nie opisuje rozw. ZPL,

ponieważ współczynniki przy zmiennych swobodnych w

funkcji docelowej są dodatnie ( w wierszu wskaźnikowym

tablicy są ujemne).

•

Oznacza to, że po przejściu do innej bazy, w której to zmienna

swobodna będzie zmienną bazową, jej wartość będzie >= 0,

co wynika z ograniczeń. Skoro tak, to wartość funkcji

docelowej wzrośnie (bo współczynnik przy niej jest dodatni).

•

Tak więc tablica sympleksowa opisuje rozwiązanie optymalne

(bazę optymalną), gdy współczynniki w wierszu

wskaźnikowym tablicy są nieujemne.

Kolejne kroki Algorytmu

Sympleks

• Jeśli tak nie jest, stosuj dwa warunki

sympleksowe do określenia nowej bazy

i buduj nowe tablice sympleksowe aż

do rozwiązania Zadania.

• Na podstawie ostatniej tablicy

sympleksowej wskaż rozwiązanie

Zadania (wartości zmiennych i wartość

funkcji docelowej).

Kolejne kroki Algorytmu

Sympleks