Metoda Simpleks

Pierwszym

algorytmem

programowania

liniowego

był

algorytm

simplex,

opublikowany przez George’a Dantziga w

1947 roku.

Algorytm Simpleks realizuje tzw. podejście

local search: zaczyna od dowolnego

wierzchołka wielościanu (zbioru rozwiązań

dopuszczalnych) i w każdej kolejnej iteracji

przemieszcza się do takiego sąsiedniego

wierzchołka, że wartość funkcji celu

poprawia się (lub przynajmniej nie

pogarsza).

Postać bazowa:

w macierzy A

występuje podmacierz

jednostkowa (oczywiście kwadratowa).

T

FC:

c x

MAX (MIN)

O: Ax

b

b

0

WB: x

0

Z

=

→

=

≥

≥

Jeżeli nie są spełnione warunki brzegowe

na

przykład

jedna

ze

zmiennych

decyzyjnych może przyjmować dowolną

wartość

, to tę zmienną zastępujemy

różnicą dwóch dodatkowych zmiennych

nieujemnych:

x

0

≥

R

k

x

∈

*

**

k

k

k

x

x

x

=

−

*

0

k

x

≥

**

0

k

x

≥

Sprowadzenie dowolnego problemu

optymalizacji liniowej do postaci

bazowej:

• jeżeli po prawej stronie ograniczenia

występuje liczba ujemna, to należy je

pomnożyć

obustronnie przez –1 (dla

nierówności oczywiście trzeba zmienić

znak na przeciwny),

• do

lewej

strony

ograniczenia

nierównościowego „

” należy dodać

nieujemną zmienną bilansującą,

• od

lewej

strony

ograniczenia

nierównościowego „

” należy odjąć

nieujemną zmienną bilansującą, a następnie

do lewej strony tego ograniczenia dodać

nieujemną zmienną sztuczną,

≤

≥

• do

lewej

strony

ograniczenia

równościowego

„

”

należy dodać

nieujemną zmienną sztuczną

• zmienne bilansujące wprowadza się do

funkcji celu z zerowymi współczynnikami

=

• zmienne sztuczne wprowadza się

ze

współczynnikami znacznie pogarszającymi
wartość funkcji celu – nie mogą one
wpływać

na

rozwiązanie

problemu

wyjściowego,

czyli

w

rozwiązaniu

optymalnym

muszą

przyjąć

wartości

zerowe

(w

przypadku

maksimum

współczynniki te to „duże”

wartości

ujemne, a w przypadku minimum – „duże”
wartości dodatnie).

Algorytm metody simpleks

Załóżmy,

ż

e

podmacierz

jednostkową

macierzy A tworzy m ostatnich wektorów

kolumnowych:

11

12

1

22

22

2

1

2

1

0

0

0

1

0

0

0

1

A

k

k

m

m

mk

a

a

a

a

a

a

a

a

a













=













…

…

…

…

⋮

⋮

⋱

⋮

⋮

⋮

⋱

⋮

…

…

oczywiście, baza składa się z wektorów:

gdzie:

[

]

1

2

B

a

a

a

k

k

k m

+

+

+

=

…

1

1

0

,

0

a

k

+

 

 

 

=

 

 

 

⋮

2

0

1

,

0

a

k

+

 

 

 

=

 

 

 

⋮

0

0

1

..., a

k m

+

 

 

 

=

 

 

 

⋮

Funkcję celu możemy wtedy zapisać jako:

Jak

widać,

wyodrębniliśmy

zmienne

niebazowe

oraz zmienne bazowe

1 1

1

1

...

...

MAX

k k

k

k

k m k m

Z

c x

c x

c

x

c

x

+

+

+

+

=

+ +

+

+ +

→

1

2

,

,...,

k

x x

x

1

2

,

,...,

k

k

k m

x

x

x

+

+

+

Ograniczenia są następujące:

11 1

1

1

1

21 1

2

2

2

1 1

...

...

...

k k

k

k k

k

m

mk k

k m

m

a x

a x

x

b

a x

a

x

x

b

a

x

a

x

x

b

+

+

+

+ +

+

=

+ +

+

=

+ +

+

=

⋮

uzupełnimy je warunkami brzegowymi:

, j=1,2,...,k+m

oraz warunkami nieujemności prawych

stron ograniczeń:

,

i=1,2,...,m

jest

to

tzw.

przedstawienie

bazowe

problemu optymalizacji liniowej

0

j

x

≥

0

i

b

≥

Korzystając teraz z ograniczeń każdą

zmienną bazową wyrazimy tylko przez

zmienne niebazowe:

1

1

11 1

1

2

2

21 1

2

1 1

...

...

...

k

k k

k

k k

k m

m

m

mk k

x

b

a x

a x

x

b

a x

a

x

x

b

a

x

a

x

+
+

+

= −

− −

=

−

− −

=

−

− −

⋮

Zależności te wprowadzamy do funkcji

celu:

1 1

2 2

1 1

11 1

12 2

1

2

2

21 1

22 2

2

1 1

2 2

...

(

...

)

(

...

)

(

...

)

k k

k

k k

k

k k

k m

m

m

m

mk k

Z

c x

c x

c x

c

b

a x

a x

a x

c

b

a x

a

x

a

x

c

b

a

x

a

x

a

x

+
+

+

=

+

+ +

+

−

−

− −

+

−

−

− −

+

−

−

− −

⋮

i po przekształceniach mamy:

1 1

2 2

1

1 11

2 22

1

1

2

1 12

2 22

2

2

1 1

2 2

...

(

...

)

(

...

)

(

...

)

k

k

k m m

k

k

k m m

k

k

k m m

k

k

k

k

k

k m mk

k

Z

c

b

c

b

c

b

c

c

a

c

a

c

a

x

c

c

a

c

a

c

a

x

c

c

a

c

a

c

a

x

+

+

+

+

+

+

+

+

+

+

+

+

=

+

+ +

+

−

−

− −

+

−

−

− −

+

−

−

− −

⋮

definiujemy

wektor

zawierający

współczynniki funkcji celu, znajdujące się

przy zmiennych bazowych

1

2

c

k

k

B

k m

c

c

c

+
+

+













=

















⋮

Funkcję celu możemy teraz zapisać w

następujący sposób:

1 1

2 2

1

1

1

...

(

)

... (

)

c a

c a

k

k

k m m

T

T

B

k

B

k

k

Z

c b

c

b

c

b

c

x

c

x

+

+

+

=

+

+ +

+

−

+ +

−

11

21

1

1

,

a

m

a

a

a













=













⋮

12

22

2

2

,

a

m

a

a

a













=













⋮

1

2

..., a

k

k

k

mk

a

a

a













=













⋮

oraz

jest macierzą transponowaną do

Iloczyn wektora

i wektora kolumnowego

oznaczymy przez

, czyli:

j=1,2,...,k

co po wstawieniu do wyrażenia na funkcję

celu daje:

c

T

B

c

B

c

T

B

a

j

j

z

c a

T

j

B

j

z

=

1 1

2 2

1

1

1

2

2

2

...

(

)

(

)

... (

)

k

k

k m m

k

k

k

Z

c b

c

b

c

b

c

z x

c

z x

c

z x

+

+

+

=

+

+ +

+

−

+

−

+ +

−

wprowadzamy jeszcze jedno oznaczenie:

lub macierzowo:

oraz: , j=1,2,...,k

i ostatecznie funkcję celu zapisujemy

następująco:

1 1

2 2

...

k

k

k m m

C

c b

c

b

c

b

+

+

+

=

+

+ +

c b

T

B

C

=

j

j

j

e

c

z

= −

1 1

2

2

...

k

k

Z

C

e x

e x

e x

= +

+

+ +

Rozwiązanie

bazowe

otrzymujemy

przyjmując dla zmiennych niebazowych

wartości zerowe, czyli:

[

]

1

2

0

0

0

x

T

B

m

b

b

b

=

…

…

Biorąc pod uwagę założenia o nieujemności

prawych

stron

ograniczeń,

jest

to

rozwiązanie bazowe dopuszczalne. Wartość

funkcji celu dla tego rozwiązania jest

równa:

( )

x

c b

T

B

B

Z

C

= =

Kryterium optymalności:

Jeżeli

[

]

1

2

0

0

0

x

T

B

m

g

g

g

=

…

…

jest dopuszczalnym rozwiązaniem bazowym

(

dla i=1,2,...,m) problemu

optymalizacji liniowej oraz funkcja celu dla

danego

przedstawienia

bazowego

ma

postać:

przy czym

, j=1,2,...,k

to rozwiązanie jest rozwiązaniem

maksymalizującym funkcję celu.

0

i

g

≥

1 1

2

2

...

k

k

Z

C

e x

e x

e x

= +

+

+ +

0

j

e

≤

x

B

Na podstawie kryterium optymalności

wiadomo, że znaki współczynników

decydują o tym, czy otrzymane rozwiązanie

bazowe jest optymalne, czy tez nie.

Współczynniki te nazywa się wskaźnikami

optymalności. Dla zmiennych bazowych

wskaźniki optymalności są równe zero.

j

e