2010-11-02

1

EKONOMETRIA 1

wykład 4

dr Beata Madras-Kobus

Algorytm SYMPLEKS

Metoda sztucznej bazy

W dotychczas rozwiązywanych przykładach

macierz

A

była

w

postaci

bazowej

dopuszczalnej, czyli istniała taka baza, dla
której

wektory

macierzy

odpowiadające

zmiennym

bazowym

tworzyły

macierz

jednostkową. Nie zawsze jednak tak jest.

Metoda sztucznej bazy polega na dodawaniu

pewnych zmiennych po to, aby znaleźć bazę z
macierzą jednostkową

.

Schemat metody

Zakładamy, że zadanie zostało sprowadzone
do postaci standardowej
i macierz A nie jest w postaci bazowej (nie
występuje w niej macierz jednostkowa)

1. Rozważamy i‐te ograniczenie,
2.

Jeśli w ograniczeniu i‐tym występuje

współczynnik 1, przy czym dla każdego
ograniczenia j, j ≠ i w wybranej kolumnie
występują same 0 to przechodzimy do
punktu 4,

3. W przeciwnym wypadku do ograniczenia

i‐tego dodajemy zmienną sztuczną x

k+1

s

,

gdzie k jest aktualną liczbą zmiennych w
zadaniu,

4. Jeżeli i‐te ograniczenie nie jest ostatnim, to

rozważamy kolejne

i przechodzimy do punktu 1,

5. Rozwiązujemy następnie zadanie stosując

standardową metodę sympleks.

2010-11-02

2

Do funkcji celu zmienne sztuczne wchodzą 

z tzw. współczynnikami ‐M, gdzie M jest 

liczbą bardzo dużą (M→∞)

Możliwe rozwiązania

Rozwiązując

zagadnienie

przy

użyciu

metody sztucznej bazy możemy otrzymać
następujące rozwiązania:

1. W bazie rozwiązania optymalnego nie

występują zmienne sztucznej bazy –
znalezione

rozwiązanie

jest

dopuszczalnym

rozwiązaniem

optymalnym

2. W bazie rozwiązania optymalnego

występuje

chociaż

jedna

zmienna

sztucznej bazy – zadanie jest sprzeczne

Przykład

Rozwiązać

następujące

zadanie

programowania

liniowego

metodą

sympleks:

Zadanie jest w postaci standardowej, więc
nie musimy go do niej sprowadzać.

Układ nie zawiera żadnego wektora
jednostkowego,

stąd

potrzebne

jest

dodanie dwóch zmiennych sztucznych.

Po dodaniu zmiennych sztucznych otrzymujemy 

następujące zadanie PL:

2010-11-02

3

Macierz A i wektor b przyjmują więc postać:

Krok 1

Krok 2

-2

-1

2

-M -M

C

B

x

B

x

1

x

2

x

3

x

4

s

x

5

s

b

c

j

-z

j

Krok 3

-2

-1

2

-M -M

C

B

x

B

x

1

x

2

x

3

x

4

s

x

5

s

b

c

j

-z

j

Rozwiązaniem bazowym zadania jest
punkt

Wartość funkcji celu dla x

1

B

wynosi -8.

Nie wszystkie c

j

– z

j

≤ 0, więc nie jest to

rozwiązanie optymalne.

-2

-1

2

-M

-M

C

B

x

B

x

1

x

2

x

3

x

4

s

x

5

s

b

c

j

-z

j

Krok 4

2010-11-02

4

Rozwiązaniem optymalnym zadania jest
punkt

Optymalna wartość funkcji celu wynosi -6.

Jest to rozwiązanie optymalne

jednoznaczne.