Przykład rozwiązania zadania programowania liniowego metodą SIMPLEX

Znaleźć min[f(x)=-2x1-3x3]

przy ograniczeniach

x1+2x2+x3 ≤ 3

3x2+4x3 ≤ 4

2x2+x3 = 1

x1, x2, x3 ≥ 0

Rozwiązanie.

Przede wszystkim musimy sprowadzić zadanie do postaci kanonicznej, to znaczy do postaci, w której poszukujemy maximum funkcji przy ograniczeniach równościowych i wszystkich zmiennych nieujemnych, przy czym w tablicy ograniczeń musi dać się wyróżnić macierz jednostkowa, a prawe strony muszą być dodatnie.

W tym przypadku zaczynamy od funkcji. Poszukiwanie minimum funkcji f(x) jest równoważne poszukiwaniu maksimum tej funkcji wziętej z przeciwnym znakiem, a więc funkcji f1(x) = - f(x) = 2x1+3x3. min f(x) = - max f1(x), x - wektor argumentów.

Aby ograniczenia przekształcić w równości, dodajemy do lewych stron (lub odejmujemy) zmienne uzupełniające o wartościach dodatnich.

W naszym przykładzie prawe strony ograniczeń i wszystkie zmienne są już dodatnie. Ograniczenia przyjmą postać:

x1+2x2+ x3 +x4 = 3

3x2+4x3 +x5 = 4

2x2+x3 = 1

x1, x2, x3 , x4, x5 ≥ 0

Tablica ograniczeń - czyli tablica współczynników przy ograniczeniach - ma postać:

1 2 1 1 0

0 3 4 0 1

0 2 1 0 0

W tablicy tej nie można jednak jeszcze wyróżnić macierzy jednostkowej - brak wektora kolumnowego [0 0 1]. Po lewej stronie trzeciego ograniczenia trzeba więc dodać zmienną sztuczną x6, która nam ten brak wyrówna. Aby nie miała ona wpływu na rozwiązanie i aby można ją było szybko wyeliminować z zadania w trakcie jego rozwiązywania, uzupełniamy funkcję celu o składnik -wx6 z bardzo dużym współczynnikiem dodatnim w. W ten sposób niejako "pogarszamy" znacznie funkcję celu "oddalając" jej wartość (znacznie zmniejszając) od prawdziwego maksimum.

Nasze zadanie przyjmie więc postać (kanoniczną):

Znaleźć max[(f1(x)=2x1+3x3-wx6]

przy ograniczeniach

x1+2x2+ x3 +x4 = 3

3x2+4x3 +x5 = 4

2x2+x3 +x6 = 1

x1, x2, x3 , x4, x5 , x6 ≥ 0

Budujemy pierwszą tablicę simplexów. W górnym wierszu - nad wektorami A1 do A6 - wpisujemy współczynniki cj występujące przy zmiennych w funkcji celu f1(x).

W kolumnie b wpisujemy prawe strony ograniczeń. Następnie w kolumnach A1 do A6 wpisujemy współczynniki lewych stron ograniczeń. Spośród tych kolumn wybieramy jednostkowe wektory do bazy. W naszym przykładzie mamy alternatywę wyboru pierwszego wektora bazowego - może nim być zarówno A1, jak i A4. Wybrano A1.

W kolumnie cb wpisujemy wartości współczynników funkcji celu dla zmiennych bazowych.

W ostatnim wierszu wpisujemy iloczyny skalarne <cb,b> oraz wskaźniki <cb,Aj>-cj.

Iloczyn skalarny <cb,b> określa wartość funkcji celu w danym kroku, wektor b wartości zmiennych bazowych.

Tablica 1

 

2

0

3

0

0

-w

Baza

cb

b

A1

A2

A3

A4

A5

A6

A1

2

3

1

2

1

1

0

0

A5

0

4

0

3

4

0

1

0

A6

-w

1

0

2

1

0

0

1

wskaźniki

6-w

0

4-2w

-1-w

2

0

0

Najmniejsza (najbardziej ujemna) wartość wskaźnika w dolnym wierszu wyznacza wektor, jaki w następnym kroku wprowadzimy do bazy. W naszym przypadku będzie to wektor A2.

Wektor usuwany z bazy wyznaczymy obliczając ilorazy charakterystyczne dla wszystkich dodatnich elementów tej kolumny:

r10 = b1/a12 = 3/2

r50 = b5/a52 = 4/3

r60 = b6/a62 = 1/2 = r0

Najmniejszą wartość spośród nich ma ostatni - zatem usuwamy z bazy wektor A6. Ponieważ jest to wektor odpowiadający zmiennej sztucznej, usuwamy go nie tylko z bazy, ale z całej tablicy simplexów.

Wyznaczony iloraz r0 podaje jednocześnie nową wartość elementu wektora b w tym wierszu.

Pozostałe dwa nowe elementy kolumny b wyznaczamy z zależności:

b1'= b1- r0 a12 = 3 - 0.5 *2 = 2

b5'= b5- r0 a52 = 4 - 0.5 *3 = 5/2

Możemy już wyznaczyć nową wartość funkcji celu - jest ona równa 4, a więc jest znacznie większa niż w poprzednim kroku. Znamy też wektory bazowe i możemy je wstawić do nowej tablicy simplexów. Wskażniki odpowiadające wektorom bazowym (dolny wiersz) są zawsze równe zeru.

Następnie wyznaczamy ilorazy kolumnowe dla wektorów poza-bazowych

r3 = a63/a62 = 1/2, r4 = a64/a62 = 0/2 = 0.

Tablica 1a

 

2

0

3

0

0

Baza

cb

b

A1

A2

A3

A4

A5

A1

2

2

1

0

 

 

0

A5

0

5/2

0

0

 

 

1

A2

0

1/2

0

1

1/2

0

0

wskaźniki

4

0

0

 

 

0

Ilorazy kolumnowe pozwolą nam wyznaczyć nowe wartości kolumn w tablicy simplexów.

a13'= a13- r3 a12 = 1 - 0.5 *2 = 0

a14'= a14- r4 a12 = 1 - 0*2 = 1

a53'= a53- r3 a52 = 4 - 0.5 *3 = 5/2

a54'= a54- r4 a52 = 0 - 0*2 = 0

Druga tablica simplexów będzie miała postać:

Tablica 2

 

2

0

3

0

0

Baza

cb

b

A1

A2

A3

A4

A5

A1

2

2

1

0

0

1

0

A5

0

5/2

0

0

5/2

0

1

A2

0

1/2

0

1

1/2

0

0

wskaźniki

4

0

0

-3

2

0

Najmniejsza (najbardziej ujemna) wartość wskaźnika w dolnym wierszu wyznacza wektor, jaki w następnym kroku wprowadzimy do bazy. W naszym przypadku będzie to wektor A3.

Wektor usuwany z bazy wyznaczymy obliczając ilorazy charakterystyczne dla wszystkich dodatnich elementów tej kolumny:

r10 = b1/a13 = 2/0

r50 = b5/a53 = (5/2)/(5/2)= 1

r20 = b2/a23 = (1/2)/(1/2) = 1 = r0

Najmniejszą wartość spośród nich mają dwa ostatnie - stoimy więc przed koniecznością wyboru jednego z nich. Wybieramy A2.

Wyznaczony iloraz r0 podaje jednocześnie nową wartość elementu wektora b w tym wierszu.

Pozostałe dwa nowe elementy kolumny b wyznaczamy z zależności:

b1'= b1- r0 a13 = 2 - 1 *0 = 2

b5'= b5- r0 a53 = 5/2 - 1 *(5/2) = 0

Możemy już wyznaczyć nową wartość funkcji celu - jest ona równa 7, a więc wzrosła.

Następnie wyznaczamy ilorazy kolumnowe dla wektorów poza-bazowych

r2 = a22/a23 = 1/2, r4 = a24/a23 = 0/(1/2) = 0.

Ilorazy kolumnowe pozwolą nam wyznaczyć nowe wartości kolumn w tablicy simplexów.

a12'= a12- r2 a13 = 0 - 2 *0 = 0

a14'= a14- r4 a13 = 1 - 0*0 = 1

a52'= a52- r2 a53 = 0 - 2 *(5/2) = -5

a54'= a54- r4 a53 = 0 - 0*(5/2) = 0

Trzecia tablica simplexów będzie miała postać:

Tablica 3

 

2

0

3

0

0

Baza

cb

b

A1

A2

A3

A4

A5

A1

2

2

1

0

0

1

0

A5

0

0

0

-5

0

0

1

A3

3

1

0

2

1

0

0

wskaźniki

7

0

6

0

2

0

W dolnym wierszu (wskaźnikowym) nie ma już elementów ujemnych, a więc jest to koniec zadania.

Wartość funkcji f1(x) jest równa 7, a wartości zmiennych x1=2, x5=0, x3=1.

Pozostałe zmienne (nie występujące w kolumnie b ostatniej tablicy simplexów) są równe zeru.

Zatem pomijając zmienne sztuczne otrzymujemy ostateczne rozwiązanie zadania dla funkcji f(x),

dla której poszukiwaliśmy minimum: min [f(2,0,1)] = -7.

Proszę sprawdzić, że wybór wektora A5 w ostatnim kroku (zamiast A2) prowadzi do tego samego wyniku,

choć ostatnia tablica simplexów będzie miała inną postać.

 

Test programów optymalizacji liniowej

  1. Czy program sam wprowadza zmienne uzupełniające?
  2. Czy program sam wprowadza zmienne sztuczne?
  3. Czy program sam wybiera bazę?
  4. Czy możliwy jest wybór max/min?
  5. Czy możliwe są ograniczenia nierównościowe?
  6. Czy prawe strony są przekształcane w dodatnie?
  7. Czy program czyta dane z pliku?
  8. Czy program zapisuje wyniki do pliku?
  9. Czy możliwy jest wybór nazwy pliku?
  10. Czy możliwa jest edycja danych on-line?
  11. Czy po zakończeniu pracy następuje powrót do edycji danych?
  12. Czy program reaguje na wpisywanie błędnych znaków?
  13. Czy pokazuje się obraz zbioru dopuszczalnego?
  14. Czy pokazane są kolejne przejścia po wierzchołkach bazy?