Każdemu planowi produkcji (x

1

,x

2

) na płaszczyźnie

O

(x

1

,x

2

) przyporządkowany jest w sposób

jednoznaczny punkt P o współrzędnych x

1

oraz x

2,

który zapisujemy jako P(x

1

,x

2

).

P

1

P

2

ZASOBY

S

1

2

2

14

S

2

1

2

8

S

3

4

0

16

ZYSK

2

3

I odwrotnie każdemu punktowi P(x

1

,x

2

) płaszczyzny

O

(x

1

,x

2

) odpowiada pewien plan produkcji (x

1

,x

2

).

Wyznaczanie dopuszczalnych planów produkcji –

rozwiązania dopuszczalne

Rozwiązaniem problemu optymalizacyjnego nazwiemy

rozwiązaniem dopuszczalnym

,

jeżeli spełnia ono wszystkie warunki ograniczające występujące w rozpatrywanym
problemie.

Należy zatem znaleźć część wspólną zbioru utworzonego wszystkich rozwiązań
dopuszczalnych która jednocześnie spełni wszystkie warunki ograniczające.

2x

1

+2x

2

≤ 14

x

1

+2x

2

≤ 8

4x

1

≤ 16

(1)

(2)
(3)

oraz warunek nieujemności zmiennych

x

1

≥ 0

X

2

≥ 0

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(0,7)

(0,7)

(7,0)

2x

1

+2x

2

=14

X

1

X

2

Warunek ograniczający

(1)

-

2x

1

+2x

2

≤14

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(0,7)

(7,0)

X

2

X

1

Warunek ograniczający

(1)

-

2x

1

+2x

2

≤14

2x

1

+2x

2

=14

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(0,4)

(8,0)

x

1

+2x

2

=8

X

2

X

1

Warunek ograniczający

(2)

-

x

1

+2x

2

≤ 8

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(0,4)

(8,0)

x

1

+2x

2

=8

X

2

X

1

Warunek ograniczający

(2)

-

x

1

+2x

2

≤ 8

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(0,7)

4x

1

=16

X

2

X

1

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(0,7)

4x

1

=16

X

2

X

1

O

(0,0)

4

2

8

10

12

14

4

6

X

1

2

4

6

8

10

12

1

x

1

≥0

X

2

(0,7)

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(0,7)

x

2

≥0

X

2

X

1

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

(7,0)

X

2

X

1

A

ograniczenie środka S

1

ograniczenie środka S

2

ograniczenie środka S

3

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

Do znalezienia rozwiązania optymalnego, w którym funkcja
celu

f(x

1

,x

2

)=2x

1

+3x

2

przyjmuje wartości największe

należy wykorzystać metodę „prób i błędów”.

Załóżmy, w pierwszym kroku, pewną wartość zysku np. 6
czyli wartość funkcji celu

2x

1

+3x

2

= 6

Czy istnieje

przynajmniej jedno rozwiązanie dopuszczalne pozwalające
zrealizować zysk na poziomie 6 jednostek?

2x

1

+3x

2

= 6

Istnieje nieskończenie wiele punktów tej prostej
leżących wewnątrz obszaru dopuszczalnego.

Odpowiedź na pytanie dotyczące istnienia
rozwiązania dopuszczalnego dającego wartość 6
jest pozytywna

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

Podejmiemy teraz próbę znalezienia lepszych rozwiązań.,
Wybierzmy większą wartość zysku np. 12 wartość funkcji
celu

2x

1

+3x

2

= 12

2x

1

+3x

2

= 6

2x

1

+3x

2

= 12

Ponownie stwierdzamy, że istnieją wspólne punkty
prostej ze zbiorem rozwiązań dopuszczalnych- czyli
istnieje możliwość poprawy rozwiązania

Otrzymana prosta jest równoległa do rozpatrywanej
poprzednio. Przesuwając ją coraz wyżej, polepszamy
wartość funkcji celu

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

Rysując prostą przedstawiającą funkcję celu w postaci

2x

1

+3x

2

= 21

stwierdzamy, że nie istnieją punkty

wspólne tej prostej ze zbiorem rozwiązań dopuszczalnych
– nie istnieje więc taki plan produkcji, który dawałby zysk
równy

21

2x

1

+3x

2

= 6

2x

1

+3x

2

= 12

2x

1

+3x

2

= 21

Prosta przedstawiająca funkcję kryterium
została przesunięta zbyt daleko

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

Wierzchołek

B

stanowi przecięcie prostych

x

1

+2x

2

=8

oraz

4

x

1

=16

.

Rozwiązując ten układ warunków, stwierdzamy, że

x

1

=4

i

x

2

=2

stąd

wartość funkcji celu w punkcie

B

wynosi

14

2x

1

+3x

2

= 6

2x

1

+3x

2

= 12

2x

1

+3x

2

= 21

W rozpatrywanym zagadnieniu optymalnym rozwianiem
jest wierzchołek

B

(4,2) zbioru dopuszczalnych

rozwiązań (

OABC

)

2x

1

+3x

2

= 14

Algorytm simpleks

Algorytm simpleks

Istota algorytmu simpleks polega na badaniu kolejnych

rozwiązań bazowych

(stanowiących wierzchołki zbioru rozwiązan dopuszczalnych) programu
liniowego o postaci kanonicznej (standardowej) w taki sposób, że:

1. znajdujemy (dowolne) rozwiązanie bazowe programu:

2. sprawdzamy, czy jest ono optymalne,

3. jeśli dane rozwiązanie nie jest optymalne, znajdujemy następne

rozwiązanie bazowe lepsze (lub przynajmniej nie gorsze od
poprzedniego)

Algorytm simpleks jest więc procedurą iteracyjną, etapową; w każdym etapie
wyznacza się rozwiązanie bazowe i sprawdza, czy można go jeszcze poprawić.

Postępowanie kończy się w momencie stwierdzenia, że aktualnego rozwiązania
bazowego nie można już poprawić, czyli że jest

optymalne

Sposób przechodzenia do kolejnych rozwiązan bazowych (kolejnych tablic
simpleks) oparty jest na przekształceniach macierzowych.

Każdy program liniowy, np.:

max

2

2

1

1

→

+

+

+

n

n

x

c

x

c

x

c

...

0

,

,

2

1

2

2

1

1

1

1

2

12

1

11

≥

≤

+

+

+

≤

+

+

+

n

m

n

mn

m

m

n

n

x

x

x

b

x

a

x

a

x

a

b

x

a

x

a

x

a

...

...

...

...

...

...

...

...

...

...

...

można zapisać w postaci macierzowej:

0

max

≥

≤

→

x

b

Ax

cx

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎣

⎡

=

mn

m

m

n

a

a

a

a

a

a

A

...

...

...

...

...

...

2

1

1

12

11

⎥

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎢

⎣

⎡

=

n

x

x

x

x

...

2

1

gdzie:

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎣

⎡

=

m

b

b

b

...

1

[

]

n

c

c

c

...

1

=

Postać bazowa

Zadanie liniowe w postaci standardowej (kanonicznej)

ograniczenie zasobu

S

1

w postaci nierówności:

2x

1

+ 2x

2

≤ 14

ograniczenie zasobu

S

1

w postaci kanonicznej:

2x

1

+ 2x

2

+ x

3

= 14

dodając do lewej strony zmienną bilansującą

x

3

określoną jako

różnicę wartości lewej i prawej strony równania czyli:

x

3

= 14 - 2x

1

- 2x

2

≥ 0

Wartość

x

3

określa, jaka ilość środka

S

1

pozostanie niewykorzystana w

przypadku realizacji planu

Dwa pozostałe warunki ograniczające przekształcamy do postaci kanonicznych
przez wprowadzenie zmiennych bilansujących

x

4

i

x

5

Dla środka S

2

x

1

+ x

2

+ x

4

= 8

x

4

= 8 – x

1

– 2x

2

≥ 0

Dla środka S

3

x

1

+ x

5

= 16

x

5

= 16 – x

1

≥ 0

Wartości

x

4

i

x

5

określają jakie ilości środków, odpowiednio

S

2

i

S

3

pozostaną

niewykorzystane w przypadku realizacji planu (

x

1

, x

2

)

Oznacza to, rozpatrywane zadanie programowania liniowego jest

zadaniem w

postaci bazowej

, a

zmiennymi bazowymi

są zmienne

x

3

, x

4

i

x

5

.

Ponieważ wszystkie wartości zmiennych bazowych są nieujemne, jest to

bazowe rozwiązanie dopuszczalne

Przyjrzyjmy się rozwiązaniu bazowemu odpowiadającemu tej bazie

Przyjmując dla zmiennych niebazowych

x

1

i

x

2

wartości równe zeru, otrzymujemy

x

1

= 0, x

2

= 0, x

3

= 14, x

4

= 8, x

5

= 16

w rozwiązaniu tym wartość funkcji celu jest równa 0

max

3

2

)

,

,

,

,

(

2

1

5

4

3

2

1

→

+

=

x

x

x

x

x

x

x

f

W dalszych rozważaniach rozpatrzymy zadanie w postaci standardowej, w której
wszystkie warunki ograniczające (z wyjątkiem warunku nieujemności) są równaniami.

Dla rozpatrywanego zadania postać ta jest następująca:

max

3

2

)

,

,

,

,

(

2

1

5

4

3

2

1

→

+

=

x

x

x

x

x

x

x

f

0

,

,

,

,

16

4

8

2

14

2

2

5

4

3

2

1

5

1

4

2

1

3

2

1

≥

=

+

=

+

+

=

+

+

x

x

x

x

x

x

x

x

x

x

x

x

x

W dalszych rozważaniach rozpatrzymy zadanie w postaci standardowej, w której
wszystkie warunki ograniczające (z wyjątkiem warunku nieujemności) są równaniami.

Dla rozpatrywanego zadania postać ta jest następująca:

max

3

2

)

,

,

,

,

(

2

1

5

4

3

2

1

→

+

=

x

x

x

x

x

x

x

f

0

,

,

,

,

16

4

8

2

14

2

2

5

4

3

2

1

5

1

4

2

1

3

2

1

≥

=

+

=

+

+

=

+

+

x

x

x

x

x

x

x

x

x

x

x

x

x

współczynniki

funkcji celu

współczynniki

warunków

ograniczających

prawe strony

warunków

ograniczających

zmienne w

zadaniu

W rozpatrywanym przez nas zadaniu występuje

5

zmiennych i

3

warunki

ograniczające, stąd składowe wektorów i elementy macierzy są następujące

[

]

c

0

0

0

3

2

=

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎣

⎡

=

1

0

0

0

4

0

1

0

2

1

0

0

1

2

2

A

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎣

⎡

=

16

8

14

b

⎥

⎥

⎥

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎢

⎢

⎢

⎣

⎡

=

5

4

3

2

1

x

x

x

x

x

x

W rozpatrywanym przez nas zadaniu występuje

5

zmiennych i

3

warunki

ograniczające, stąd składowe wektorów i elementy macierzy są następujące

[

]

c

0

0

0

3

2

=

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎣

⎡

=

1

0

0

0

4

0

1

0

2

1

0

0

1

2

2

A

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎣

⎡

=

16

8

14

b

⎥

⎥

⎥

⎥

⎥

⎥

⎦

⎤

⎢

⎢

⎢

⎢

⎢

⎢

⎣

⎡

=

5

4

3

2

1

x

x

x

x

x

x

Widzimy, że wybierając z macierzy

A

kolumny trzecią, czwartą i piątą

otrzymujemy macierz jednostkową

Oznacza to, że układ równań odpowiadający warunkom ograniczającym
rozpatrywanego problemu jest w postaci bazowej

oraz, że zmiennymi bazowymi są zmienne

x

3

,

x

4

, i

x

5

, a zmiennymi niebazowymi

są zmienne pozostałe –

x

1

i

x

2

Ze względu na to, że przyjmując to rozwiązanie, nie uruchamiamy produkcji

(

x

1

= 0 i

x

2

= 0) zmienne bilansujące, określające niewykorzystane zasoby

środków

S

1

,

S

2

i

S

3

, są równe wielkościom zasobów tych środków.

w dalszych rozważaniach będziemy wykorzystywać

tablicę simpleksową

będącą

pewną modyfikacją

postaci macierzowej

zadania.

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

współczynniki funkcji celu c

nazwy zmiennych

macierz

współczynników A

wektor wyrazów

wolnych b

wykaz zmiennych

bazowych

wektor wartości

współczynników funkcji

celu c

B

odpowiadający

zmiennym bazowym

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

Z tablicy simpleksowej można odczytać wartość funkcji celu odpowiadającą
rozwiązaniu bazowemu, w którym zmiennymi bazowymi są

x

3

,

x

4

,

x

5

.

c

B

· b

wartość funkcji celu

0·14 + 0·8 + 0·16 = 0

Metoda simpleks

Metoda simpleks

Metoda simpleks polega na rozpatrzeniu ciągu

sąsiednich rozwiązań

bazowych

, czyli takich rozwiązań bazowych, dla których dwie kolejno

rozpatrywane bazy różnią się od siebie dokładnie o jedną zmienną.

Doboru

bazy sąsiedniej

dokonujemy w taki sposób aby zagwarantować

otrzymanie coraz lepszych (przynajmniej nie gorszych) wartości funkcji celu.

Przejście z jednej bazy do drugiej odbywa się przy wykorzystaniu

przekształceń

elementarnych

układu warunków ograniczających w postaci standardowej

(kanonicznej)

Przekształceniami elementarnymi

są: podzielenie dowolnie wybranego

warunku ograniczającego przez dowolną liczbę (różną od zera) oraz dodanie
do dowolnie wybranego warunku , pomnożonego przez dowolną liczbę (różną
od zera) innego warunku pomnożonego przez dowolna liczbę (różną od zera)

W wyniku przekształceń elementarnych układu warunków ograniczających
programowania liniowego otrzymujemy równoważny mu układ warunków,
generujących ten sam zbiór rozwiązań dopuszczalnych

Aby wykonać jeden krok (

iterację

) algorytmu metody simpleks należy:

1. stwierdzić czy rozwiązanie bazowe jest optymalne, czy też nie,

2. w przypadku gdy nie jest optymalne, wyznaczyć nową bazę sąsiednią,

3. przekształcić za pomocą przekształceń elementarnych macierz warunków

ograniczających do postaci bazowej względem bazy sąsiedniej.

Iteracja 1

Zbadamy jaki wpływ na dotychczasowe rozwiązanie (

x

3

, x

4

, x

5

, - zmienne

bazowe oraz

x

1

i

x

2

– zmienne niebazowe) miałoby przyjęcie przez jedną ze

zmiennych niebazowych np. zmienną

x

1

, wartości równej 1 (druga zmienna

niebazowa

x

2

przyjmuje cały czas wartość 0

Pierwszy warunek ograniczający w postaci kanonicznej:

Kryterium optymalno

Kryterium optymalno

ś

ś

ci

ci

14

2

2

3

2

1

=

+

+

x

x

x

14

2

3

=

+ x

ponieważ

x

1

= 1 oraz

x

2

= 0

12

3

=

x

wartość zmiennej bazowej

x

3

zmniejszyła się o 2 jednostki – z 14 do 12

Wprowadzanie do rozwiązania coraz większych wartości zmiennej

x

1

będzie się odbywało kosztem zmiennej bazowej

x

3

każdej dodanej jednostce zmiennej

x

1

odpowiada spadek zmiennej bazowej

x

3

o 2 jednostki

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

macierz współczynników

warunków ograniczających A

Zmiana ta odpowiada wartości
współczynnika

a

11

= 2

W podobny sposób sprawdźmy, jak na wartość zmiennej bazowej

x

4

wpłynie

przyjęcie założenia, że

x

1

= 1 – przy ciągłym trwaniu założenia, że

x

2

= 0

8

2

4

2

1

=

+

+

x

x

x

8

1

4

=

+ x

7

4

=

x

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

każdej zmianie wartości zmiennej

x

1

odpowiada spadek wartości

zmiennej

x

4

o wartość zapisaną w macierzy

A

(współczynnika

a

21

)

Rozpatrując w taki sam sposób trzeci warunek ograniczający, który ma postać:

16

4

5

1

=

+ x

x

16

4

5

=

+ x

12

5

=

x

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

każdej zmianie wartości zmiennej

x

1

odpowiada spadek wartości

zmiennej

x

5

o wartość zapisaną w macierzy

A

(współczynnika

a

31

)

Analogicznie możemy przeprowadzić rozważania dla drugiej zmiennej
niebazowej

x

2

przyjmując jej wartość równą jedności przy założeniu, że druga

zmienna niebazowa

x

1

jest równa 0

Zastanówmy się teraz w jaki sposób zmieni się

wartość funkcji celu

, która w

rozwiązaniu początkowym była równa 0.

ponieważ mamy

x

1

= 1 więc wzrost ten wyniesie:

2

1

2

1

1

=

⋅

=

⋅ x

c

0

2

0

11

3

=

⋅

=

⋅ a

c

Z drugiej strony możliwy jest

spadek

wartości funkcji celu związany z

obniżeniem dotychczasowych wartości przez zmienne bazowe.

Z pierwszym warunkiem ograniczającym związana jest zmiana:

0

1

0

21

4

=

⋅

=

⋅ a

c

0

4

0

31

5

=

⋅

=

⋅ a

c

Podobnie dla warunku drugiego i trzeciego

oraz

Dodając uzyskane wyniki, otrzymamy
łączną zmianę na poziomie 0

Z jednej strony spodziewamy się

wzrostu

wartość funkcji celu

związanego z tym, że współczynnik funkcji celu

c

1

= 2

Zauważmy jednocześnie, że zmianę tę oznaczoną dla rozpatrywanej
zmiennej

x

j

symbolem

z

j

obliczyliśmy jako iloczyn skalarny dwóch

wektorów będących kolumnami tablicy simpleksowej:

cx

→max

2

3

0

0

0

Ba

za

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

Oznaczmy zmianę wartości funkcji celu spowodowaną zmianami w
wartościach zmiennych bazowych przez

z

j

Zauważmy jednocześnie, że zmianę tę oznaczoną dla rozpatrywanej
zmiennej

x

j

symbolem

z

j

obliczyliśmy jako iloczyn skalarny dwóch

wektorów będących kolumnami tablicy simpleksowej:

cx

→max

2

3

0

0

0

Ba

za

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

Oznaczmy zmianę wartości funkcji celu spowodowaną zmianami w
wartościach zmiennych bazowych przez

z

j

W taki sam sposób obliczamy zmiany wartości funkcji celu przy
wprowadzeniu do rozważania zmiennej niebazowej

x

2

=1

(pamiętamy, że wówczas zmienna niebazowa

x

1

= 0)

0·2 + 0·2 + 0·4 = 0

Różnica

c

j

– z

j

określa zmiany netto w wartościach funkcji celu, jeżeli

jedna jednostka zmiennej

x

j

zostanie wprowadzona do aktualnie

rozpatrywanego rozwiązania bazowego.

Wartości

c

j

– z

j

nazywamy

wskaźnikiem optymalności

wartości te dopisujemy jako ostatni wiersz tablicy simpleksowej.

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

zj

0

0

0

0

0

c

j

- z

j

2

3

0

0

0

0

ostatnim elementem w tym wierszu jest wartość funkcji celu
odpowiadająca rozpatrywanemu rozwiązaniu bazowemu

Różnica

c

j

– z

j

określa zmiany netto w wartościach funkcji celu, jeżeli

jedna jednostka zmiennej

x

j

zostanie wprowadzona do aktualnie

rozpatrywanego rozwiązania bazowego.

Wartości

c

j

– z

j

nazywamy

wskaźnikiem optymalności

wartości te dopisujemy jako ostatni wiersz tablicy simpleksowej.

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

c

j

- z

j

2

3

0

0

0

0

Wartości wskaźników optymalności dla zmiennych

x

1

i

x

2

są dodatnie, co

oznacza, ze jeżeli wprowadzimy którąkolwiek z tych zmiennych do bazy, to
wartość funkcji celu będzie

wzrastać

Kryterium optymalno

Kryterium optymalno

ś

ś

ci dla zadania maksymalizacji

ci dla zadania maksymalizacji

Je

Je

ż

ż

eli warto

eli warto

ść

ść

wszystkich wska

wszystkich wska

ź

ź

nik

nik

ó

ó

w optymalno

w optymalno

ś

ś

ci s

ci s

ą

ą

niedodatnie, to

niedodatnie, to

rozpatrywane rozwi

rozpatrywane rozwi

ą

ą

zanie jest optymalne.

zanie jest optymalne.

Je

Je

ż

ż

eli cho

eli cho

ć

ć

jeden ze wska

jeden ze wska

ź

ź

nik

nik

ó

ó

w optymalno

w optymalno

ś

ś

ci jest dodatni, to istnieje

ci jest dodatni, to istnieje

mo

mo

ż

ż

liwo

liwo

ść

ść

poprawy tego rozwi

poprawy tego rozwi

ą

ą

zania

zania

Wyb

Wyb

ó

ó

r zmiennej wprowadzanej do bazy

r zmiennej wprowadzanej do bazy

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

c

j

- z

j

2

3

0

0

0

0

wprowadzając do początkowego
rozwiązania bazowego zmiennej

x

1

= 1 powoduje wzrost

funkcji celu o

2

jednostki

x

2

= 1 powoduje wzrost

funkcji celu o

3

jednostki

Kryterium wej

Kryterium wej

ś

ś

cia

cia

Wybieramy największą wartość wskaźnika optymalności. Odpowiadająca mu
zmienną wprowadzamy do nowej bazy.
Jeśli największej wartości wskaźnika optymalności odpowiada więcej niż jedna
zmienna, to do nowej bazy wprowadzamy zmienną o najniższym numerze.

w rozpatrywanym prze nas przypadku do

nowej bazy wprowadzimy zmienną

x

2

Wyb

Wyb

ó

ó

r zmiennej

r zmiennej

opuszczaj

opuszczaj

ą

ą

cej baz

cej baz

ę

ę

14

2

2

3

2

1

=

+

+

x

x

x

14

2

3

2

=

+ x

x

Zastanówmy się teraz jaką największa wartość może przyjąć zmienna

x

2

,

którą zdecydowaliśmy się wprowadzić do nowej bazy.
Musi ona być tak dobrana aby były spełnione wszystkie warunki ograniczające

Pierwszy warunek ograniczający

14

2

2

=

x

ponieważ zmienna

x

1

jako niebazowa jest równa zeru, więc:

Zwiększając wartość

x

2

, możemy doprowadzić do tego, że dotychczasowa

zmienna bazowa

x

3

przyjmie wartość zero. Będzie tak wówczas, gdy:

7

2

=

x

czyli

dalsze zwiększanie wartości zmiennej

x

2

doprowadziłoby do tego, że

x

3

byłoby

ujemne, co jest niedopuszczalne.

Największa dopuszczalna wartość zmiennej

x

2

dla pierwszego warunku

ograniczającego jest równa 7

Drugi warunek ograniczający

8

2

4

2

1

=

+

+

x

x

x

8

2

4

2

=

+ x

x

8

2

2

=

x

4

2

=

x

W związku z tym, że mamy

x

1

= 0 otrzymujemy:

Zwiększając wartość

x

2

,

możemy doprowadzić do tego, że dotychczasowa

zmienna bazowa

x

4

przyjmie wartość zero. Będzie tak wówczas, gdy

czyli

Największa dopuszczalna wartość zmiennej

x

2

ze względu na drugi

warunek ograniczający wynosi 4

Trzeci warunek ograniczający

16

0

4

5

2

1

=

+

+

x

x

x

Ponieważ współczynnik przy

x

2

jest równy 0, zwiększanie wartości zmiennej

x

2

nie ma żadnego wpływu na zmienną

x

5

, tak więc zmiennej

x

5

nie możemy

wyprowadzić z bazy poprzez wprowadzenie do bazy zmiennej

x

2

Największa dopuszczalna wartość zmiennej

x

2

musi być tak dobrana, aby były

spełnione wszystkie warunki ograniczające. Ponieważ warunek drugi
ogranicza ją najbardziej (

x

2

= 4 ). Odpowiadająca temu warunkowi zmienna

x

4

przyjmie wartość 0, stając się zmienną niebazową.

Kryterium wyj

Kryterium wyj

ś

ś

cia

cia

Obliczamy ilorazy kolejnych wyraz

Obliczamy ilorazy kolejnych wyraz

ó

ó

w wolnych przez odpowiadaj

w wolnych przez odpowiadaj

ą

ą

ce im

ce im

elementy kolumny wchodz

elementy kolumny wchodz

ą

ą

cej do bazy dla tych element

cej do bazy dla tych element

ó

ó

w kolumny

w kolumny

wprowadzanej do bazy, kt

wprowadzanej do bazy, kt

ó

ó

re s

re s

ą

ą

dodatnie.

dodatnie.

Baz

Baz

ę

ę

opuszcza ta zmienna, dla kt

opuszcza ta zmienna, dla kt

ó

ó

rej odpowiadaj

rej odpowiadaj

ą

ą

cy jej iloraz jest

cy jej iloraz jest

najmniejszy. Je

najmniejszy. Je

ż

ż

eli minimum jest przyjmowane przez wi

eli minimum jest przyjmowane przez wi

ę

ę

cej ni

cej ni

ż

ż

jeden

jeden

raz, to jako zmienn

raz, to jako zmienn

ą

ą

opuszczaj

opuszczaj

ą

ą

c

c

ą

ą

baz

baz

ę

ę

wybieramy zmienn

wybieramy zmienn

ą

ą

o

o

najni

najni

ż

ż

szym numerze.

szym numerze.

Przej

Przej

ś

ś

cie do rozwi

cie do rozwi

ą

ą

zania bazowego s

zania bazowego s

ą

ą

siedniego

siedniego

Ponieważ doszliśmy do wniosku, że z dotychczasowej bazy (

x

3

,

x

4

, i

x

5

) należy

usunąć zmienną

x

4

oraz na jaj miejsce wprowadzić zmienną

x

2

, naszym celem

jest obecnie otrzymanie odpowiadającego nowej bazie rozwiązania bazowego
sąsiedniego

cx →max

2

3

0

0

0

Ba

za

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

c

j

- z

j

2

3

0

0

0

0

Ze względu na to, że zmienna

x

2

staje się zmienna bazową, musimy wykonać

operacje przekształceń elementarnych w taki sposób aby druga kolumna
przekształconej macierzy warunków ograniczających miała postać

0

1

0

cx

→max

2

3

0

0

0

Ba

za

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

c

j

- z

j

2

3

0

0

0

0

0

0

0

0

3

2

c

j

- z

j

16

1

0

0

0

4

0

x

5

4

0

0,5

0

1

0,5

3

x

2

14

0

0

1

2

2

0

x

3

x

5

x

4

x

3

x

2

x

1

c

B

Ba

za

b

0

0

0

3

2

cx

→max

W tym celu drugi wiersz tabeli simpleksowej
dzielimy przez 2 i zapisujemy go w nowej
tabeli

4

0

0,5

0

1

0,5

0

0

0

0

3

2

c

j

- z

j

16

1

0

0

0

4

0

x

5

8

0

1

0

2

1

0

x

4

14

0

0

1

2

2

0

x

3

x

5

x

4

x

3

x

2

x

1

c

B

Ba

za

b

0

0

0

3

2

cx

→max

12

0

-1,5

0

0

0,5

c

j

- z

j

16

1

0

0

0

4

0

x

5

3

x

2

6

0

-1

1

0

1

0

x

3

x

5

x

4

x

3

x

2

x

1

c

B

Ba

za

b

0

0

0

3

2

cx

→max

z koli przekształcony wiersz mnożymy przez
-2 i dodajemy do wiersza pierwszego z
pierwszej tablicy simpleksowej.
Wynik zapisujemy w tablicy simpleksowej II

x(

-2)

8

0

-1

0

-2

-1

(+)

4

0

0,5

0

1

0,5

12

0

-1,5

0

0

0,5

c

j

- z

j

16

1

0

0

0

4

0

x

5

3

x

2

6

0

-1

1

0

1

0

x

3

x

5

x

4

x

3

x

2

x

1

c

B

Baza

b

0

0

0

3

2

cx →max

Tablica simpleksowa po I iteracji

Tablica simpleksowa po I iteracji

wartość funkcji celu

po I iteracji

Zgodnie z kryterium optymalności otrzymane rozwiązanie

nie jest optymalne

,

ponieważ wartość współczynnika optymalności dla zmiennej

x

2

jest dodatnia

Iteracja 2

Kryterium wejścia dla metody simpleks wskazuje, że istnieje tylko jedna
możliwość wprowadzenia do bazy nowej zmiennej, aby poprawić wartość
funkcji celu w nowym rozwiązaniu. Tą zmienną jest

x

1

przyrost funkcji celu odpowiadający jednostce wprowadzanej zmiennej

x

1

wynosi

0,5

Stosując kryterium wyjścia, obliczamy odpowiednie ilorazy,
otrzymując:

dla wiersza 1 –

dla wiersza 2 –

6:1 = 6

4:(0,50) = 8

dla wiersza 3 –

16:4 = 4

Minimalną wartość otrzymujemy dla wiersza 3, co oznacza, że z bazy
należy usunąć zmienną

x

5

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

0

0

1

-1

-0,25

2

x

2

3

0

1

0

0,5

-0,125

2

x

1

2

1

0

0

0

0,25

4

c

j

- z

j

0

0

0

-1,5

-0,125

14

Tablica simpleksowa po II iteracji

Tablica simpleksowa po II iteracji

Iteracja 3

Sprawdzamy, czy otrzymane rozwiązanie bazowe jest optymalne;

0

0

2

2

4

5

4

3

2

1

=

=

=

=

=

x

x

x

x

x

,

,

,

,

Ponieważ wszystkie wskaźniki optymalności zapisane w ostatnim wierszu tablicy
simpleksowej są

niedodatnie

, zgodnie z kryterium optymalności jest to

rozwiązanie

optymalne

– co kończy procedurę optymalizacji.

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

Interpretacja graficzna

Interpretacja graficzna

Rozwiązanie początkowe:

x

1

=0, x

2

=0, x

3

=14, x

4

=8, x

5

=16

Rozwiązanie nie jest optymalne

warunek ograniczający III

warunek
ograniczający II

warunek
ograniczający I

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

wprowadzając do I rozwiązania bazowego
za x

1

=1 otrzymujemy punkt

P

1

(1,0)

za x

2

=1 otrzymujemy punkt

P

2

(0,1)

P

1

(1,0)

P

2

(0,1)

warunek
ograniczający II

warunek
ograniczający I

warunek ograniczający III

Z

kryterium wejścia

wiemy, że

x

2

powoduje

szybszy wzrost funkcji celu zatem wprowadzamy
ją do bazy i poruszamy się w kierunku jej wzrostu

Kryterium wyjścia

podpowiada jak daleko

możemy się posunąć po osi x

2

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

wprowadzając do I rozwiązania bazowego
za x

1

=1 otrzymujemy punkt

P

1

(1,0)

za x

2

=1 otrzymujemy punkt

P

2

(0,1)

P

1

(1,0)

P

2

(0,1)

warunek
ograniczający II

warunek
ograniczający I

warunek ograniczający III

Z

kryterium wejścia

wiemy, że

x

2

powoduje

szybszy wzrost funkcji celu zatem wprowadzamy
ją do bazy i poruszamy się w kierunku jej wzrostu

Kryterium wyjścia

podpowiada jak daleko

możemy się posunąć po osi x

2

x

1

=0, x

2

=4, x

3

=6, x

4

=0, x

5

=0

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

P

1

(1,0)

P

2

(0,1)

warunek
ograniczający II

warunek
ograniczający I

warunek ograniczający III

Po drugiej iteracji wiemy, że należy wprowadzić
do nowej bazy zmienną

x

1

Nowe

kryterium wyjścia

podpowiada jak daleko

możemy się posunąć po osi x

2

Rozpatrywane są

wierzchołki

H

O

(0,0)

2

4

6

8

10

12

14

2

8

10

12

14

4

6

F

X

2

X

1

A

B

C

D

E

P

1

(1,0)

P

2

(0,1)

warunek
ograniczający II

warunek
ograniczający I

warunek ograniczający III

Po drugiej iteracji wiemy, że należy wprowadzić
do nowej bazy zmienną

x

1

H

Wierzchołki

F

i

H

pozostają poza obszarem rozwiązań

dopuszczalnych pozostaje więc wierzchołek

B

x

1

=2, x

2

=4, x

3

=3, x

4

=0, x

5

=0

Wierzchołkowi

B

w pięciowymiarowej

przestrzeni odpowiada rozwiązanie

Algorytm simpleks polega na badaniu rozwiązań bazowych programu o

postaci

kanonicznej

(wszystkie warunki ograniczające maja postać równości), zatem przed

przystąpieniem do budowy pierwszej tablicy simpleksowej (postaci bazowej) należy
zmienić wszystkie nierówności na równania przez wprowadzenie pewnych
dodatkowych

zmiennych bilansujących

.

Wykorzystując zapis macierzowy, pierwszą tablicę simpleks można zapisać
następująco:

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

b

x

3

0

2

2

1

0

0

14

x

4

0

1

2

0

1

0

8

x

5

0

4

0

0

0

1

16

Algorytm simpleks polega na badaniu rozwiązan bazowych programu o

postaci

kanonicznej

(wszystkie warunki ograniczające maja postać równości), zatem przed

przystąpieniem do budowy pierwszej tablicy simpleksowej (postaci bazowej) należy
zmienić wszystkie nierówności na równania przez wprowadzenie pewnych
dodatkowych

zmiennych bilansujących

.

Wykorzystując zapis macierzowy, pierwszą tablicę simpleks można
zapisać następująco:

c

b

x

b

z

j

c

j

-z

j

c

A

I

0

c

b

c

b

x

b

z

j

c

j

-z

j

c

A

I

0

c

b

A

– jest macierzą współczynników występujących po lewej stronie

warunków ograniczających

b

– jest wektorem wyrazów wolnych warunków ograniczających

c

– jest wektorem wierszowym współczynników funkcji celu (zdefiniowanej

po wprowadzeniu zmiennych bilansujących)

x

b

– jest wektorem zmiennych bazowych

c

b

– jest wektorem kolumnowym współczynników funkcji celu dla zmiennych

bazowych

I

– jest macierzą jednostkową o wymiarach (

m x m) –

macierz

ą

współczynników

przy zmiennych występujących w pierwszej bazie

0

– jest wektorem zer

c

b

x

b

z

j

c

j

-z

j

c

A

I

0

c

b

Zasadnicza część tablicy składa się z

m

wierszy (

m

jest liczba warunków

ograniczających i z tylu właśnie zmiennych skład się każde rozwiązanie
bazowe)

c

b

x

b

z

j

c

j

-z

j

c

A

I

0

c

b

Zasadnicza część tablicy składa się z

m

wierszy (

m

jest liczba warunków

ograniczających i z tylu właśnie zmiennych skład się każde rozwiązanie
bazowe)

Liczba kolumn odpowiada łącznej liczbie zmiennych w modelu w postaci
kanonicznej (decyzyjnych i bilansujących) przy czym współczynniki przy
zmiennych bazowych tworzą macierz jednostkową

c

b

x

b

z

j

c

j

-z

j

c

A

I

0

c

b

Zasadnicza część tablicy składa się z

m

wierszy (

m

jest liczba warunków

ograniczających i z tylu właśnie zmiennych skład się każde rozwiązanie
bazowe)

Liczba kolumn odpowiada łącznej liczbie zmiennych w modelu w postaci
kanonicznej (decyzyjnych i bilansujących) przy czym współczynniki przy
zmiennych bazowych tworzą macierz jednostkową

Wartość

z

j

dla poszczególnych zmiennych (kolumn tablicy) oblicza się jako

sumę iloczynów współczynników odpowiadających poszczególnym
zmiennym (

a

ij

) i współczynników funkcji celu dla zmiennych bazowych (

c

b

i

)

czyli

∑

=

=

m

i

bi

ij

j

c

a

z

1

c

b

x

b

z

j

c

j

-z

j

c

A

I

0

c

b

Zasadnicza część tablicy składa się z

m

wierszy (

m

jest liczba warunków

ograniczających i z tylu właśnie zmiennych skład się każde rozwiązanie
bazowe)

Liczba kolumn odpowiada łącznej liczbie zmiennych w modelu w postaci
kanonicznej (decyzyjnych i bilansujących) przy czym współczynniki przy
zmiennych bazowych tworzą macierz jednostkową

Wartość

z

j

dla poszczególnych zmiennych (kolumn tablicy) oblicza się jako

sumę iloczynów współczynników odpowiadających poszczególnym
zmiennym (

a

ij

) i współczynników funkcji celu dla zmiennych bazowych (

c

b

i

)

czyli

∑

=

=

m

i

bi

ij

j

c

a

z

1

Ostatni wiersz tablicy simpleksowej c

j

– z

j

zwany jest wierszem zerowym

lub

kryterium simpleks

.

Elementy wiersza zerowego (kryterium simpleks) odpowiadające poszczególnym
zmiennym (kolumnom) informują, o ile zmieni się aktualna w danej iteracji wartość
funkcji celu, jeżeli jedną jednostkę tej zmiennej wprowadzimy do nowej (kolejnej)
bazy.
Innymi słowy służy on do sprawdzenia, czy aktualne rozwiązanie bazowe jest
rozwiązaniem optymalnym.

W przypadkach, gdy funkcja celu jest maksymalizowana, rozwiązanie dotąd nie
będzie optymalne, dopóki w wierszu zerowym będą występować liczby nieujemne

.

(dodatnie liczby świadczą, iż wprowadzenie do bazy zmiennej, której odpowiada
dodatni współczynnik zwiększy wartość funkcji celu)

wartość zmiennych
bazowych

wartość funkcji celu

zmienne

bazowe

rozwiązanie

A

B

l

1

−

1

−

l

B

b

B

l

1

−

A

B

c

b

T

b

1

−

1

−

b

T

b

B

c

b

B

c

b

T

b

1

−

A

B

c

c

b

T

b

1

−

−

1

−

−

b

T

b

B

c

j

j

z

c

−

j

z

bl

x

bl

c

c

l

B

Macierz jest macierz współczynników ograniczających stojących przy aktualnych
(w

l

-tej iteracji) zmiennych bazowych

Odwrotność tej macierzy w postaci zajmuje pozycję macierzy jednostkowej w
tablicy początkowej. Ponieważ zmienne bazowe zmieniają się w każdej iteracji,
również macierz a tym samym jej odwrotność macierz są w każdej iteracji
inne, stąd indeks

l

.

1

−

l

B

l

B

1

−

l

B

Również każdą pośrednią i każdą końcową tablice simpleks można przedstawić za
pomocą zapisu macierzowego.
W

l

-tej iteracji algorytmu tablica simpleks może być zapisana następująco:

zmienne

bazowe

rozwiązanie

A

V

l

l

V

b

V

l

A

V

c

l

T

b

l

T

b

V

c

b

V

c

l

T

b

A

V

c

c

l

T

b

−

l

T

b

V

c

−

j

j

z

c

−

j

z

bl

x

bl

c

c

Oznaczmy dla uproszczenia, macierz odwrotną

przez

Zatem w

l

-tej iteracji algorytmu tablica simpleks może być zapisana następująco:

1

−

l

B

l

V

Macierz jest macierzą odwrotną współczynników ograniczających
stojących przy aktualnych zmiennych bazowych ( w

l

-tej iteracji )

l

V