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