2013-10-25

1

Badania operacyjne

Badania operacyjne

Wykład 2:

Wykład 2:

Zadania dualne PL i jego własno

ś

ci

Zadania dualne PL i jego własno

ś

ci

Algorytm simpleks

Algorytm simpleks

izabela.dziaduch@pwr.wroc.pl

Zadania dualne PL 

Zadania dualne PL 
i jego własności

i jego własności

ID,2013/2014 

2013-10-25

2

∑

=

→

n

j

j

j

MAX

x

c

1

0

≥

j

x

)

,...,

2

,

1

(

n

j

=

0

≥

i

b

)

,...,

2

,

1

(

m

i

=

∑

=

≤

n

j

i

j

ij

b

x

a

1

0

≥

j

x

)

,...,

2

,

1

(

n

j

=

0

≥

i

b

∑

=

→

n

j

j

j

MIN

x

c

1

∑

=

≥

n

j

i

j

ij

b

x

a

1

Ogólna postać ZPL

Ogólna postać ZPL

)

,...,

2

,

1

(

m

i

=

Nierówno

ść

 

≤

dla zadania na maksimum oraz nierówno

ść

 

≥

dla zadania 

na minimum nazywamy nierówno

ś

ciami typowymi

nierówno

ś

ciami typowymi.

ID,2013/2014 

Zasady konstrukcji zadań dualnych (1)

Zasady konstrukcji zadań dualnych (1)

Zadanie pierwotne (ZP)

∑

=

→

n

j

j

j

MAX

x

c

1

0

≥

j

x

)

,...,

2

,

1

(

n

j

=

)

,...,

2

,

1

(

m

i

=

∑

=

≤

n

j

i

j

ij

b

x

a

1

Zadanie dualne (ZD)

∑

=

→

m

i

i

i

MIN

y

b

1

0

≥

i

y

)

,...,

2

,

1

(

n

j

=

)

,...,

2

,

1

(

m

i

=

∑

=

≥

m

i

j

i

ij

c

y

a

1

ID,2013/2014 

2013-10-25

3

Zadanie pierwotne (ZP)

Zadanie dualne (ZD)

∑

=

→

m

i

i

i

MAX

y

b

1

∑

=

≤

m

i

j

i

ij

c

y

a

1

0

≥

i

y

)

,...,

2

,

1

(

n

j

=

)

,...,

2

,

1

(

m

i

=

0

≥

j

x

)

,...,

2

,

1

(

n

j

=

∑

=

→

n

j

j

j

MIN

x

c

1

∑

=

≥

n

j

i

j

ij

b

x

a

1

)

,...,

2

,

1

(

m

i

=

ID,2013/2014 

Zasady konstrukcji zadań dualnych (2)

Zasady konstrukcji zadań dualnych (2)

1.

W ZD jest tyle zmiennych, ile nierówno

ś

ci w ZP 

(ka

ż

demu warunkowi ZP odpowiada jedna 

zmienna ZD) i odwrotnie;

2.

Współczynniki funkcji celu ZP s

ą

 wyrazami 

wolnymi w ZD i odwrotnie;

3.

Macierz współczynników ZD jest transpozycj

ą

 

macierzy współczynników ZP, 

4.

Kierunek optymalizacji w ZD jest przeciwny do 
kierunku optymalizacji w ZP.

Zasady konstrukcji zadań dualnych (3)

Zasady konstrukcji zadań dualnych (3)

ID,2013/2014 

2013-10-25

4

Je

ż

eli w problemie pierwotnym wyst

ę

puj

ą

 ograniczenia 

typowe (nietypowe) dla kierunku optymalizacji, to w 
problemie dualnym na zmienne odpowiadaj

ą

ce tym 

warunkom nakłada si

ę

 warunki nieujemno

ś

ci 

(niedodatnio

ś

ci) i odwrotnie. 

Je

ż

eli na zmienne w zadaniu pierwotnym nie s

ą

 

nało

ż

one ograniczenia znakowe, to wtedy 

odpowiadaj

ą

ce im warunki przyjmuj

ą

 posta

ć

 równo

ś

ci i 

odwrotnie.

Warunek

Funkcja celu d

ąż

y do

MAX

MIN

Typowy

≤

≥

Nietypowy

≥

≤

Zasady konstrukcji zadań dualnych (4) 

Zasady konstrukcji zadań dualnych (4) 
–

– warunki znakowe

warunki znakowe

ID,2013/2014 

Zadanie pierwotne

Zadanie pierwotne

MAX

MAX

Ograniczenia

i-te: 

≥

i-te: 

≤

i-te: =

Zmienne

x

j

≥

 0

x

j

≤

0

x

j

dowolne

Zadanie dualne

Zadanie dualne

MIN

MIN

Zmienne

y

i 

≤

 0

y

i 

≥

 0

y

i  

dowolne

Ograniczenia

j-te: 

≥

j-te: 

≤

j-te: =

Zasady konstrukcji zadań dualnych (5) 

Zasady konstrukcji zadań dualnych (5) 
–

– warunki znakowe

warunki znakowe

ID,2013/2014 

2013-10-25

5

Zadanie pierwotne

Zadanie pierwotne

MIN

MIN

Ograniczenia

i-te: 

≥

i-te: 

≤

i-te: =

Zmienne

x

j

≥

 0

x

j

≤

0

x

j

dowolne

Zadanie dualne

Zadanie dualne

MAX

MAX

Zmienne

y

i 

≥

0

y

i 

≤

0

y

i  

dowolne

Ograniczenia

j-te: 

≤

j-te: 

≥

j-te: =

Zasady konstrukcji zadań dualnych (6) 

Zasady konstrukcji zadań dualnych (6) 
–

– warunki znakowe

warunki znakowe

ID,2013/2014 

Przykład 1: Utwórz ZD do danego ZP

Przykład 1: Utwórz ZD do danego ZP

Zadanie pierwotne (ZP)

F(x

F(x

1

1

,x

,x

2

2

,x

,x

3

3

) 

) = 2x

1

+3x

2

+x

3

→

MIN

(1) 

(1) 4x

1

-6x

2

+5x

3

≥

4

4

(2) 

(2) x

1

+2x

2

+4x

3

≥

7

7

(3) 

(3) x

1

≥

0

(4) 

(4) x

2

≥

0

(5) 

(5) x

3

≥

0

Zadanie dualne (ZD)

G(y

G(y

1

1

,y

,y

2

2

) 

) = 4

4y

1

+7

7y

2

→

MAX

(1)  

(1)  4y

1

+1y

2

≤

2

(2) 

(2) -6y

1

+2y

2

≤

3

(3)  

(3)  5y

1

+4y

2

≤

1

(4) 

(4) y

1

≥

0

(5) 

(5) y

2

≥

0

y

2

y

1

x

1

x

2

x

3

ID,2013/2014 

2013-10-25

6

Przykład 2: Utwórz ZD do danego ZP

Przykład 2: Utwórz ZD do danego ZP

Zadanie pierwotne (ZP)

F(x

F(x

1

1

,x

,x

2

2

,x

,x

3,

3,

x

x

4

4

) 

) = 

16x

1

+32x

2

+12x

3

+8x

4

→

MAX

(1) 

(1) 4x

1

+6x

2

+3x

3

≤

160

160

(2) 

(2) 2x

1

+8x

2

+8x

3

+2x

4

=40

40

(3) 

(3) x

1

≥

0

(4) 

(4) x

2

≥

0

(5) 

(5) x

3

≥

0

(6) x

4

≤

0

Zadanie dualne (ZD)

G(y

G(y

1

1

,y

,y

2

2

) 

) = 160y

1

+40y

2

→

MIN

(1) 4

(1) 4y

1

+2y

2

≥

16

16

(2) 6

(2) 6y

1

+8y

2

≥

32

32

(3) 

(3) 3

3y

1

+8y

2

≥

12

(4) 

(4) 

2y

2

≤

8

(5) 

(5) y

1

≥

0

(6) y

2

ϵ

R

ID,2013/2014 

y

2

y

1

x

1

x

2

x

3

x

4

Twierdzenia o dualności (1)

Twierdzenia o dualności (1)

1.

W rozwi

ą

zaniach optymalnych obu zada

ń

 warto

ś

ci funkcji 

celu s

ą

 sobie równe.

2.

a) 

Je

ż

eli i-ty warunek ZP jest (chocia

ż

 w jednym) 

optymalnym rozwi

ą

zaniu tego zadania spełniony 

nierówno

ś

ci

ą

 (ostro), to odpowiadaj

ą

ca mu i-ta zmienna –

y

i 

w (dowolnym) optymalnym rozwi

ą

zaniu ZD przyjmuje 

warto

ść

 zero;

b) 

Je

ż

eli j-ty warunek ZD jest (chocia

ż

 w jednym) 

optymalnym rozwi

ą

zaniu tego zadania spełniony 

nierówno

ś

ci

ą

 (ostro), to odpowiadaj

ą

ca mu j-ta zmienna –

x

j 

w (dowolnym) optymalnym rozwi

ą

zaniu ZP przyjmuje 

warto

ść

 zero;

Jest to tzw. twierdzenie o równowadze

twierdzenie o równowadze

..

ID,2013/2014 

2013-10-25

7

3.

Je

ż

eli ZD ma jedno rozwi

ą

zanie optymalne, to 

optymalna warto

ść

 i-tej zmiennej dualnej (y

i

) informuje 

jak wielki przyrost (spadek) warto

ś

ci funkcji celu ZP 

przypada na zwi

ę

kszenie (zmniejszenie) wyrazu 

wolnego w i-tym ograniczeniu (b

i

) o jednostk

ę

, przy 

niezmienionych pozostałych b.

Jest to tzw. twierdzenie o optymalno

ś

ci.

twierdzenie o optymalno

ś

ci.

Twierdzenia o dualności (2)

Twierdzenia o dualności (2)

ID,2013/2014 

Interpretacja ekonomiczna ZD (1)

Interpretacja ekonomiczna ZD (1)

ZP opisuje problem maksymalizacji przychodu 
osi

ą

ganego z produkcji n wyrobów. Zu

ż

ycie 

ś

rodków 

produkcji nie mo

ż

e przekroczy

ć

 zasobów, jakimi 

dysponujemy. Waga c

i

oznacza cen

ę

 j-tego wyrobu, 

współczynnik a

ij

– wielko

ść

 zu

ż

ycia i-tego

ś

rodka na 

produkcj

ę

 jednostki j-tego wyrobu, wyraz wolny b

i

–

zasób i-tego 

ś

rodka produkcji, a zmienna x

j

– wielko

ść

 

produkcji j-tego wyrobu.

ID,2013/2014 

∑

=

→

n

j

j

j

MAX

x

c

1

0

≥

j

x

)

,...,

2

,

1

(

n

j

=

)

,...,

2

,

1

(

m

i

=

∑

=

≤

n

j

i

j

ij

b

x

a

1

2013-10-25

8

ZD do ZP ma posta

ć

:

przy warunkach: 

W celu okre

ś

lenia interpretacji ekonomicznej ZD (1)-(3) okre

ś

li

ć

 nale

ż

y 

miano zmiennych dualnych

miano zmiennych dualnych. Miano mo

ż

na okre

ś

li

ć

 z nierówno

ś

ci (2), 

wiedz

ą

c, 

ż

e cj wyra

ż

aj

ą

 zysk jednostkowy ze sprzeda

ż

y j-tego wyrobu. 

Wobec tego wyst

ę

puj

ą

 one z mianem: 

Interpretacja ekonomiczna ZD (2)

Interpretacja ekonomiczna ZD (2)

∑

=

→

m

i

i

i

MIN

y

b

1

0

≥

i

y

)

,...,

2

,

1

(

n

j

=

)

,...,

2

,

1

(

m

i

=

∑

=

≥

m

i

j

i

ij

c

y

a

1

(1)

(2)

(3)

jednostki pieni

ęż

ne

ilo

ść

 wytworzonego wyrobu

ID,2013/2014 

Parametry a

ij

w ZD wyra

ż

aj

ą

 zu

ż

ycie i-tego

ś

rodka na produkcj

ę

 

jednostki j-tego wyrobu, mianem b

ę

dzie:

Aby nierówno

ś

ci (2) miały sens ekonomiczny, to zmienne dualne musz

ą

 

mie

ć

 mano:

Z miana zmiennej dualnej y

i 

wynika, 

ż

e wyra

ż

a ona w jednostkach 

pieni

ęż

nych produktywno

ść

 z zaanga

ż

owania jednostki 

ś

rodka i.

Warunki ograniczaj

ą

ce (2) oznaczaj

ą

, 

ż

e suma tych produktywno

ś

ci 

wyra

ż

ona jednostkowymi nakładami surowców na jeden wyrób j musi 

by

ć

 równa co najmniej zyskowi jednostkowemu ze sprzeda

ż

y j-tego

wyrobu.

Funkcja celu ZD wyra

ż

a ł

ą

czny efekt z wykorzystania wszystkich 

ś

rodków. Jest ona minimalizowana, poniewa

ż

 szukamy minimalnej  

sumarycznej produktywno

ś

ci wszystkich u

ż

ytych 

ś

rodków.

zu

ż

ycie i-tego

ś

rodka

ilo

ść

 wytworzonego wyrobu

Interpretacja ekonomiczna ZD (3)

Interpretacja ekonomiczna ZD (3)

jednostki pieni

ęż

ne

zu

ż

ycie i-tego

ś

rodka

ID,2013/2014 

2013-10-25

9

Przykład 3 

Przykład 3 –

– wybór optymalnego 

wybór optymalnego 

planu produkcji

planu produkcji

Zakład produkuj

ą

cy ustala plan produkcyjny, który mo

ż

e 

obejmowa

ć

 produkcj

ę

 mebli: szaf, regałów, stołów kuchennych. 

Mo

ż

na je sprzeda

ć

 odpowiednio za 500, 180, 90 PLN. Do 

produkcji mebli zu

ż

ywane s

ą

 ograniczone zasoby drewna i listew:

Ustali

ć

 plan produkcji na przyszły rok tak, aby zmaksymalizowa

ć

 

zysk ze sprzeda

ż

y mebli. 

Zbudowa

ć

 model matematyczny tego zagadnienia i zastosowa

ć

 

metod

ę

 geometryczn

ą

.

ID,2013/2014 

Przykład 3 

Przykład 3 –

– rozwiązanie

rozwiązanie

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce:

Warunki brzegowe:

Funkcja celu:

x

1

– wielko

ść

 produkcji szaf

x

2

– wielko

ść

 produkcji regałów

x

3

– wielko

ść

 produkcji stołów

[drewno]  4x

1

+2,5x

2

+1,5x

3 

≤

 1000

[listwy]     8x

1

+12x

2

+3x

3 

≤

 2500

x

1

,x

2

,x

3

≥

0

F(x

1

,x

2

,x

3

) = 500x

1

+180x

2

+90x

3

→

MAX

ZP

ZD

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce:

Warunki brzegowe:

Funkcja celu:

y

1

– cena drewna 

y

2

– cena listew

y

1

,y

2

≥

0

G(y

1

,y

2

) = 1000y

1

+2500y

2

→

MIN

4y

1

+8y

2

≥

500

2,5y

1

+12y

2

≥

180

1,5y

1

+3y

2

≥

90

ID,2013/2014 

Model matematyczny

2013-10-25

10

y

2

y

1

20

40

60

80

20

40

60

80

0

A

A

Bior

ą

c dowoln

ą

 wspóln

ą

 wielokrotno

ść

  

parametrów funkcji celu, tj. 1000 i 2500 np. 50000 
wyznaczamy lini

ę

 jednakowego przychodu.

G(y

1

,y

2

) = 1000y

1

+2500y

2

→

MIN

100

120

B

B

(1)  4y

1

+ 8y

2

≥

500

(2)  2,5y

1

+ 12y

2

≥

180

(3) 1,5y

1

+ 3y

2

≥

90

Przykład 3 

Przykład 3 –

– rozwiązanie (2)

rozwiązanie (2)

ID,2013/2014 

y

2

y

1

20

40

60

80

20

40

60

80

(1)  4y

1

+ 8y

2

≥

500

(2)  2,5y

1

+ 12y

2

≥

180

(3) 1,5y

1

+ 3y

2

≥

90

0

A

A

Nast

ę

pnie lini

ę

 t

ę

 przesuwamy równolegle w celu 

znalezienia punktu(ów) znajduj

ą

cych si

ę

 jak najbli

ż

ej od 

pocz

ą

tku układu współrz

ę

dnych

G(y

1

,y

2

) = 1000y

1

+2500y

2

→

MIN

100

120

B

B

Przykład 3 

Przykład 3 –

– rozwiązanie (3)

rozwiązanie (3)

ID,2013/2014 

2013-10-25

11

y

2

y

1

20

40

60

80

20

40

60

80

0

A

A

G(y

1

,y

2

) = 1000y

1

+2500y

2

→

MIN

100

120

B=(125,0)

B=(125,0)

G(y

1

,y

2

) = 125 000 zł

Rozwi

ą

zanie optymalne 

ZD

ID,2013/2014 

Przykład 3 

Przykład 3 –

– rozwiązanie (4)

rozwiązanie (4)

Sprawdzamy, w jaki sposób optymalne rozwi

ą

zanie ZD 

spełnia jego warunki ograniczaj

ą

ce

Warunek (1) jest słabo spełniony (zachodzi równo

ść

)

Warunek (2) i (3) jest ostro spełniony (zachodzi nierówno

ść

)

…st

ą

d wniosek, 

ż

e zmienna w ZP o nr 2 i 3 (czyli x

2

i x

3

) jest 

równa 0

Tak wi

ę

c, dla rozwi

ą

zana ZP mo

ż

na zapisa

ć

 układ równa

ń

:

(1) 4y

1

+ 8y

2

≥

500

500=500

(2)  2,5y

1

+ 12y

2

≥

180

312,5

≥

180

(3) 1,5y

1

+ 3y

2

≥

90

187,5

≥

90

4x

1

= 1000

8x

1

= 2500

x

1

= 250

F(x

1

,x

2

,x

3

) = 500x

1

+180x

2

+90x

3

= 125000 zł

Przykład 3 

Przykład 3 –

– rozwiązanie (5)

rozwiązanie (5)

ID,2013/2014 

B=(125,0)

B=(125,0)

2013-10-25

12

Z twierdzenia 1 wynika, 

ż

e:

Z twierdzenia 3 wynika, 

ż

e optymalna warto

ść

 zmiennej y

i

okre

ś

la nam, o ile wzro

ś

nie (zmniejszy si

ę

) przychód, je

ż

eli 

zwi

ę

kszymy (zmniejszymy) zasób i-tego 

ś

rodka produkcji o 

jednostk

ę

. 

Sprawd

ź

my:

G(y

1

,y

2

) = 125 000 zł

F(x

1

,x

2

,x

3

) = 500x

1

+180x

2

+90x

3

= 125000 zł

=

4x

1

= 1001

8x

1

= 2500

x

1

= 250,25

F(x

1

,x

2

,x

3

) = 500x

1

+180x

2

+90x

3

= 125125 zł

Rozwi

ą

zanie optymalne: ZD (y

1

=125, y

2

=0)

Przykład 3 

Przykład 3 –

– rozwiązanie (6)

rozwiązanie (6)

ID,2013/2014 

Metoda simpleks 

(uniwersalna metoda rozwiązywania ZPL)

ID,2013/2014 

2013-10-25

13

Kiedy stosować metodę simpleks?

Kiedy stosować metodę simpleks?

Liczba zmiennych decyzyjnych jest wi

ę

ksza ni

ż

 2

Du

ż

a liczba ogranicze

ń

 utrudnia dokładne 

wyznaczenie zbioru rozwi

ą

za

ń

 dopuszczalnych 

metod

ą

 graficzn

ą

ID,2013/2014 

Metoda simpleks - metoda iteracyjnego 

poprawiania wst

ę

pnego rozwi

ą

zania

Schemat post

ę

powania w przypadku wyznaczania rozwi

ą

za

ń

 za 

Schemat post

ę

powania w przypadku wyznaczania rozwi

ą

za

ń

 za 

pomoc

ą

 metod iteracyjnych o sko

ń

czonej liczbie kroków

pomoc

ą

 metod iteracyjnych o sko

ń

czonej liczbie kroków

ID,2013/2014 

Wyznaczenie startowego rozwi

ą

zania

Czy to jest 

rozwi

ą

zanie 

optymalne?

Czy mo

ż

na 

wyznaczy

ć

 

lepsze 

rozwi

ą

zanie?

Wyznaczenie nowego 

rozwi

ą

zania

Koniec

T

N

N

T

2013-10-25

14

Istota algorytmu simpleks

Istota algorytmu simpleks

Polega na badaniu kolejnych rozwi

ą

za

ń

 bazowych 

(rozwi

ą

za

ń

 dopuszczalnych) programu liniowego w 

postaci kanonicznej w taki sposób, 

ż

e : 

znajdujemy (dowolne) rozwi

ą

zanie bazowe zadania;

sprawdzamy, czy jest ono optymalne czy nie. 

je

ż

eli dane rozwi

ą

zanie nie jest optymalne, 

znajdujemy nast

ę

pne rozwi

ą

zanie bazowe lepsze 

(lub przynajmniej nie gorsze od poprzedniego), z 
którym to rozwi

ą

zaniem post

ę

pujemy tak samo jak z 

rozwi

ą

zaniem wyj

ś

ciowym - a

ż

 do momentu 

znalezienia rozwi

ą

zania optymalnego.

ID,2013/2014 

Przekształcamy warunki ograniczaj

ą

ce w równania dopisuj

ą

c do

nich

tzw.

zmienne

swobodne

i

zmienne

sztuczne

w nast

ę

puj

ą

cy sposób:

do ka

ż

dego warunku w postaci “

≤

” dodaje si

ę

zmienn

ą

swobodn

ą

z parametrem równym 1,

do ka

ż

dego warunku w postaci “

≥

” dodaje si

ę

zmienn

ą

swobodn

ą

ze współczynnikiem -1 oraz tzw. zmienn

ą

sztuczn

ą

z parametrem równym 1.

Zmienne

swobodne

posiadaj

ą

interpretacj

ę

ekonomiczn

ą

wynikaj

ą

c

ą

z informacji zawartej w warunkach ograniczaj

ą

cych,

do których zostały wprowadzone.
Dodane zmienne wchodz

ą

równie

ż

do nowej funkcji kryterium

(celu), gdzie parametry przy zmiennych swobodnych przyjmuj

ą

warto

ść

zero, natomiast zmienne sztuczne warto

ść

M (du

ż

a

liczba d

ążą

ca do niesko

ń

czono

ś

ci).

Sprowadzenie 

Sprowadzenie ZPL 

ZPL do postaci kanonicznej

do postaci kanonicznej

ID,2013/2014 

2013-10-25

15

Ile należy wykonać iteracji, aby 
osiągnąć rozwiązanie optymalne?

Dokładnej liczby iteracji, które nale

ż

y wykona

ć

 

rozwi

ą

zuj

ą

c model nie da si

ę

 precyzyjnie okre

ś

li

ć

.

Dla układu n zmiennych decyzyjnych i m
warunków ograniczaj

ą

cych jest co najwy

ż

ej                      

rozwi

ą

za

ń

 dopuszczalnych.

Metoda simpleks nie przeszukuje wszystkich 
rozwi

ą

za

ń

 bazowych, lecz tylko wybrane.

)!

(

!

!

m

n

m

n

m

n

−

=













ID,2013/2014 

Tablica simpleksowa 

Tablica simpleksowa –

– postać 

postać 

macierzowa

macierzowa

c

j

x

b

c

b

x

j

b

i

A           I                    

z

j

∆

j

=c

j

-z

j

Macierz współczynników 

wyst

ę

puj

ą

cych po lewej stronie 

warunków ograniczaj

ą

cych

Wektor kolumnowy 

wyrazów wolnych

Wektor wierszowy 

współczynników funkcji celu

Wektor kolumnowy 

zmiennych bazowych

Wektor kolumnowy 

współczynników funkcji 

celu dla zmiennych 

bazowych

Suma iloczynów współczynników 

odpowiadaj

ą

cych poszczególnym 

zmiennym (a

ij

) i współczynników 

funkcji celu dla zmiennych 

bazowych (c

b

)

∑

=

=

k

i

bi

ij

j

c

a

z

1

Wiersz zerowy 

(kryterium simpleks)

Macierz jednostkowa

ID,2013/2014 

Wektor wierszowy 

zmiennych

2013-10-25

16

Wiersz zerowy 

Wiersz zerowy 

Je

ż

eli funkcja celu jest MAX

funkcja celu jest MAX, rozwi

ą

zanie bazowe 

dot

ą

d nie b

ę

dzie optymalne, dopóki w wierszu 

zerowym b

ę

d

ą

 wyst

ę

powa

ć

 liczby nieujemne 

liczby nieujemne 

(dodatnie liczby 

ś

wiadcz

ą

, i

ż

 wprowadzenie do bazy 

zmiennej, której odpowiada dodatni współczynnik 
zwi

ę

kszy warto

ść

 funkcji celu);

Je

ż

eli funkcja celu jest MIN

funkcja celu jest MIN, kolejne rozwi

ą

zania 

bazowe dot

ą

d nie s

ą

 optymalne, dopóki w wierszu 

zerowym wyst

ę

puj

ą

 wielko

ś

ci niedodatnie 

wielko

ś

ci niedodatnie (co 

znaczy, 

ż

e warto

ść

 funkcji celu mo

ż

na obni

ż

y

ć

).

ID,2013/2014 

Schemat post

ę

powania 

Schemat post

ę

powania 

w algorytmie simpleks

w algorytmie simpleks

y

ik 

– wektor 

odpowiadaj

ą

cy 

zmiennej , która ma 
wej

ść

 do nowej bazy

2013-10-25

17

Przykład 4

Przykład 4

Zakład produkuje trzy wyroby przy u

ż

yciu dwóch 

surowców. Zasoby surowców, jednostkowe nakłady i 
ceny produktów podane s

ą

 w tabeli:

Wyrób A

Wyrób B

Wyrób C

Zasób

Surowiec 1

2

1

1

10

Surowiec 2

1

3

2

12

Cena

3

2

5

Wyznacz metod

ą

 simpleks plan produkcji 

maksymalizuj

ą

cy przychód przedsi

ę

biorstwa.

Wyznacz i zinterpretuj warto

ś

ci zmiennych dualnych.

ID,2013/2014 

Krok 1 

Krok 1 -- Zapisanie modelu liniowego problemu w postaci standardowej

Zapisanie modelu liniowego problemu w postaci standardowej

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce:

Warunki brzegowe:

Funkcja celu:

x

1

– wielko

ść

 produkcji wyrobu A

x

2

– wielko

ść

 produkcji wyrobu B

x

3

– wielko

ść

 produkcji wyrobu C

[s1] 2x

1

+1x

2

+1x

3

≤

10

[s2] 1x

1

+3x

2

+2x

3

≤

12

x

1,

x

2

, x

3

≥

0

F(x

1

,x

2

) = 3x

1

+2x

2

+5x

3

→

MAX

Przykład 4 

Przykład 4 –

– rozwiązanie

rozwiązanie

ID,2013/2014 

2013-10-25

18

Posta

ć

 standardowa

Posta

ć

 kanoniczna

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce:

Warunki brzegowe:

Funkcja celu:

x

1

– wielko

ść

 produkcji wyrobu A,

x

2

– wielko

ść

 produkcji wyrobu B,

x

3

– wielko

ść

 produkcji wyrobu C,

[s1] 2x

1

+1x

2

+1x

3

≤

10

[s2] 1x

1

+3x

2

+2x

3

≤

12

x

1,

x

2

, x

3

≥

0

F(x

1

,x

2

, x

3

) = 3x

1

+2x

2

+5x

3

→

MAX

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce:

Warunki brzegowe:

Funkcja celu:

x

1

– wielko

ść

 produkcji wyrobu A

x

2

– wielko

ść

 produkcji wyrobu B

x

3

– wielko

ść

 produkcji wyrobu C

x

4

– niewykorzystany zasób surowca 1

x

5

– niewykorzystany zasób surowca 2

[s1] 2x

1

+1x

2

+1x

3

+x

4

=10

[s2] 1x

1

+3x

2

+2x

3        

+x

5

=12

x

1,

x

2

, x

3, 

x

4, 

x

5

≥

0

F(x

1

,x

2, 

x

3

,x

4,

x

5

) = 3x

1

+2x

2

+5x

3

+0x

4

+0x

5

→

MAX

Krok

Krok 2

2 -- Sprowadzenie

Sprowadzenie zadania

zadania zz postaci

postaci standardowej

standardowej do

do kanonicznej

kanonicznej

Przykład 4 

Przykład 4 –

– rozwiązanie (2)

rozwiązanie (2)

ID,2013/2014 

Rozpoczynamy od przyj

ę

cia, 

ż

e te zmienne, które wyst

ę

puj

ą

 w 

wi

ę

cej ni

ż

 jednym ograniczeniu, s

ą

 równe zero, tj.

x

1

,x

2

,x

3

=0

W efekcie tego zało

ż

enia wszystkie zmienne dodatkowe maj

ą

 

warto

ś

ci takie jak wyrazy wolne stoj

ą

ce po prawej stronie 

odpowiednich ogranicze

ń

. Dla rozwa

ż

anego modelu otrzymujemy 

wi

ę

c:

x

4

=10, x

5

=12

Wst

ę

pnie okre

ś

lone rozwi

ą

zanie dopuszczalne nazywa si

ę

 

wst

ę

pnym rozwi

ą

zaniem bazowym, natomiast zmienne 

wchodz

ą

ce w jego skład (x

4

, x

5

) nazywamy zmiennymi 

bazowymi lub krótko - baz

ą

. Pozostałe zmienne nazywa si

ę

 

zmiennymi niebazowymi.

Krok

Krok 3

3 –

– Wstępne

Wstępne dopuszczane

dopuszczane rozwiązanie

rozwiązanie modelu

modelu

Przykład 4 

Przykład 4 –

– rozwiązanie (3)

rozwiązanie (3)

ID,2013/2014 

2013-10-25

19

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

x

5

0

1

3

2

0

1

12

z

j

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Krok

Krok 3

3 –

– Wstępne

Wstępne dopuszczane

dopuszczane rozwiązanie

rozwiązanie modelu

modelu ((2

2))

Tablica simpleks 1 

Warto

ś

ci wiersza z

j

dla wszystkich zmiennych s

ą

 równe zeru, bo współczynniki przy zmiennych bazowych 

s

ą

 równe zeru, np. x

1

: z

1

=2•0+1•0=0, dla x

2

: z

2

=1•0+3•0 itd. 

[s1] 2x

1

+1x

2

+1x

3

+x

4        

=10

[s2] 1x

1

+3x

2

+2x

3         

+x

5

=12

F(x

1

,x

2, 

x

3

,x

4,

x

5

) = 3x

1

+2x

2

+5x

3

+0x

4

+0x

5

→

MAX

Przykład 4 

Przykład 4 –

– rozwiązanie (4)

rozwiązanie (4)

ID,2013/2014 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

x

5

0

1

3

2

0

1

12

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Tablica simpleks 1 

Warto

ś

ci wiersza z

j

dla wszystkich zmiennych s

ą

 równe zeru, bo współczynniki funkcji celu przy 

zmiennych bazowych s

ą

 równe zeru, np. x

1

: z

1

=2•0+1•0=0, dla x

2

: z

2

=1•0+3•0 itd. 

Jak łatwo si

ę

 przekona

ć

, 

zaproponowane wst

ę

pne rozwi

ą

zanie dopuszczalne daje zysk FC=10•0+12•0=0. 

Krok

Krok 3

3 –

– Wstępne

Wstępne dopuszczane

dopuszczane rozwiązanie

rozwiązanie modelu

modelu ((3

3))

Przykład 4 

Przykład 4 –

– rozwiązanie (5)

rozwiązanie (5)

ID,2013/2014 

2013-10-25

20

Kryterium optymalności

Kryterium optymalności

Rozwi

ą

zanie jest optymalne, je

ż

eli warto

ś

ci wszystkich 

wska

ź

ników optymalno

ś

ci s

ą

 niedodatnie.

Rozwi

ą

zanie w bazie [x

4

, x

5

] nie jest rozwi

ą

zaniem 

optymalnym.

Nale

ż

y przej

ść

 do nast

ę

pnej bazy

ID,2013/2014 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

x

5

0

1

3

2

0

1

12

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Krok

Krok 4

4 –

– Zmiana

Zmiana bazy/

bazy/ kryterium

kryterium wejścia

wejścia do

do bazy

bazy

Tablica simpleks 1 

Poniewa

ż

 FC jest maksymalizowana, do kolejnego rozwi

ą

zania wejdzie zmienna o najwi

ę

kszej 

warto

ś

ci kryterium simpleks.

Je

ż

eli najwi

ę

ksza warto

ść

 wska

ź

nika optymalno

ś

ci odpowiada wi

ę

cej ni

ż

 jednej zmiennej, 

wybieramy zmienn

ą

 o ni

ż

szym indeksie.

W przykładzie kryterium wej

ś

cia spełnia zmienna x

3

.

Kolumna kluczowa

Przykład 4 

Przykład 4 –

– rozwiązanie (6)

rozwiązanie (6)

ID,2013/2014 

2013-10-25

21

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

10

x

5

0

1

3

2

0

1

12

6

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Tablica simpleks 1 

Obliczamy ilorazy wyrazów wolnych (kolumna b

i

) przez elementy (tylko dodatnie) kolumny 

zmiennej wchodz

ą

cej do bazy.

Baz

ę

 opuszcza ta zmienna, dla której obliczony iloraz jest najmniejszy.

Je

ż

eli najmniejsza warto

ść

 ilorazu wyst

ę

puje dla wi

ę

cej ni

ż

 jednej zmiennej, to jako zmienn

ą

 

opuszczaj

ą

c

ą

 baz

ę

 mo

ż

na wybra

ć

 dowoln

ą

 z nich.

W przykładzie kryterium wyj

ś

cia spełnia zmienna x

5

.

Kolumna kluczowa

Krok

Krok 5

5 –

– Zmiana

Zmiana bazy/

bazy/ kryterium

kryterium wyjścia

wyjścia zz bazy

bazy

x

4

: 10:1=10

x

5

: 12:2=6

Przykład 4 

Przykład 4 –

– rozwiązanie (7)

rozwiązanie (7)

ID,2013/2014 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

10

x

5

0

1

3

2

0

1

12

6

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Tablica simpleks 1 

Kolumna kluczowa

Wiersz 

kluczowy

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (8)

rozwiązanie (8)

2013-10-25

22

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

10

x

5

0

1

3

2

0

1

12

6

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Tablica simpleks 1 

Kolumna kluczowa

Wiersz 

kluczowy

Element 

rozwi

ą

zuj

ą

cy 

(centralny)

Przykład 4 

Przykład 4 –

– rozwiązanie (9)

rozwiązanie (9)

ID,2013/2014 

Algorytm simpleks 

Algorytm simpleks 

Elementy nowej tablicy simpleksowej wyznaczamy 
stosując się do następujących zasad:
1. Elementy „wiersza kluczowego” wchodzą do nowej 

tablicy po podzieleniu przez element rozwiązujący.

2. Pozostałe elementy tablicy simpleks wyznacza się ze 

wzoru:

gdzie:

NE – nowy element
WE – wybrany element
E

WK

– element wiersza kluczowego

W

KK

– element kolumny kluczowej

E

R

– element rozwiązujący

R

KK

WK

E

E

E

WE

NE

⋅

−

=

Metoda

Metoda zamiany

zamiany zmiennych

zmiennych

ID,2013/2014 

2013-10-25

23

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

x

3

5

z

j

c

j

-z

j

Tablica simpleks 2 

Krok

Krok 6

6 -- Zamiana

Zamiana zmiennych

zmiennych

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (10)

rozwiązanie (10)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

10

x

5

0

1

3

2

0

1

12

6

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Tablica simpleks 1 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

x

3

5

1/2 3/2

1

0

1/2

6

z

j

c

j

-z

j

Tablica simpleks 2 

Krok

Krok 6

6 -- Zamiana

Zamiana zmiennych

zmiennych ((2

2))

Przykład 4 

Przykład 4 –

– rozwiązanie (11)

rozwiązanie (11)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

10

x

5

0

1

3

2

0

1

12

6

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Tablica simpleks 1 

ID,2013/2014 

2013-10-25

24

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2 -1/2

0

1

-1/2

4

x

3

5

1/2

3/2

1

0

1/2

6

z

j

c

j

-z

j

Tablica simpleks 2 

Krok

Krok 6

6 -- Zamiana

Zamiana zmiennych

zmiennych ((3

3))

Przykład 4 

Przykład 4 –

– rozwiązanie (12)

rozwiązanie (12)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

2

1

1

1

0

10

10

x

5

0

1

3

2

0

1

12

6

z

j

0

0

0

0

0

0

c

j

-z

j

3

2

5

0

0

Tablica simpleks 1 

ID,2013/2014 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2 -1/2

0

1

-1/2

4

x

3

5

1/2

3/2

1

0

1/2

6

z

j

5/2 15/2

5

0

5/2

c

j

-z

j

Tablica simpleks 2 

Współczynniki z

j

oraz wiersza zerowego (c

j

-z

j

) obliczamy tak, jak w 

przypadku 1-szej tablicy simpleksowej 

Przykład 4 

Przykład 4 –

– rozwiązanie (13)

rozwiązanie (13)

ID,2013/2014 

2013-10-25

25

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2 -1/2

0

1

-1/2

4

x

3

5

1/2

3/2

1

0

1/2

6

z

j

5/2 15/2

5

0

5/2

30

c

j

-z

j

Tablica simpleks 2 

Przykład 4 

Przykład 4 –

– rozwiązanie (14)

rozwiązanie (14)

ID,2013/2014 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2

-1/2

0

1

-1/2

4

x

3

5

1/2

3/2

1

0

1/2

6

z

j

5/2

15/2

5

0

5/2

30

c

j

-z

j

1/2 -11/2

0

0

-5/2

Tablica simpleks 2 

Rozwi

ą

zanie w bazie [x

4

, x

3

,] nie jest rozwi

ą

zaniem optymalnym.

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (15)

rozwiązanie (15)

2013-10-25

26

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2

-1/2

0

1

-1/2

4

x

3

5

1/2

3/2

1

0

1/2

6

z

j

5/2

15/2

5

0

5/2

30

c

j

-z

j

1/2 -11/2

0

0

-5/2

Tablica simpleks 2 

Do bazy wchodzi zmienna x

1.

Krok

Krok 4

4*

* –

– Zmiana

Zmiana bazy/

bazy/ kryterium

kryterium wejścia

wejścia do

do bazy

bazy

Przykład 4 

Przykład 4 –

– rozwiązanie (16)

rozwiązanie (16)

ID,2013/2014 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2

-1/2

0

1

-1/2

4

8/3

x

3

5

1/2

3/2

1

0

1/2

6

12

z

j

5/2

15/2

5

0

5/2

30

c

j

-z

j

1/2

-11/2

0

0

-5/2

Tablica simpleks 2 

Z bazy wychodzi zmienna: x

4

Krok

Krok 5

5*

* –

– Zmiana

Zmiana bazy/

bazy/ kryterium

kryterium wyjścia

wyjścia zz bazy

bazy

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (17)

rozwiązanie (17)

2013-10-25

27

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2

-1/2

0

1

-1/2

4

8/3

x

3

5

1/2

3/2

1

0

1/2

6

12

z

j

5/2

15/2

5

0

5/2

30

c

j

-z

j

1/2

-11/2

0

0

-5/2

Tablica simpleks 2 

Kolumna kluczowa

Wiersz 

kluczowy

Element 

rozwi

ą

zuj

ą

cy 

(centralny)

Przykład 4 

Przykład 4 –

– rozwiązanie (18)

rozwiązanie (18)

ID,2013/2014 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

x

3

5

z

j

c

j

-z

j

Tablica simpleks 3 

Krok

Krok 6

6*

* -- Zamiana

Zamiana zmiennych

zmiennych

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (19)

rozwiązanie (19)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2

-1/2

0

1

-1/2

4

8/3

x

3

5

1/2

3/2

1

0

1/2

6

12

z

j

5/2

15/2

5

0

5/2

30

c

j

-z

j

1/2

-11/2

0

0

-5/2

Tablica simpleks 2 

2013-10-25

28

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

z

j

c

j

-z

j

Tablica simpleks 3 

ID,2013/2014 

Krok

Krok 6

6*

* -- Zamiana

Zamiana zmiennych

zmiennych ((2

2))

Przykład 4 

Przykład 4 –

– rozwiązanie (20)

rozwiązanie (20)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2

-1/2

0

1

-1/2

4

8/3

x

3

5

1/2

3/2

1

0

1/2

6

12

z

j

5/2

15/2

5

0

5/2

30

c

j

-z

j

1/2

-11/2

0

0

-5/2

Tablica simpleks 2 

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

0

5/3

1

-1/3

2/3

14/3

z

j

c

j

-z

j

Tablica simpleks 3 

ID,2013/2014 

Krok

Krok 6

6*

* -- Zamiana

Zamiana zmiennych

zmiennych ((3

3))

Przykład 4 

Przykład 4 –

– rozwiązanie (21)

rozwiązanie (21)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

4

0

3/2

-1/2

0

1

-1/2

4

8/3

x

3

5

1/2

3/2

1

0

1/2

6

12

z

j

5/2

15/2

5

0

5/2

30

c

j

-z

j

1/2

-11/2

0

0

-5/2

Tablica simpleks 2 

2013-10-25

29

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

0

5/3

1

-1/3

2/3

14/3

z

j

3

22/3

5

1/3

7/3

c

j

-z

j

Tablica simpleks 3 

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (22)

rozwiązanie (22)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

0

5/3

1

-1/3

2/3

14/3

z

j

3

22/3

5

1/3

7/3

94/3

c

j

-z

j

Tablica simpleks 3 

Przykład 4 

Przykład 4 –

– rozwiązanie (23)

rozwiązanie (23)

ID,2013/2014 

2013-10-25

30

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

0

5/3

1

-1/3

2/3

14/3

z

j

3

22/3

5

1/3

7/3

94/3

c

j

-z

j

0

-16/3

0

-1/3

-7/3

Tablica simpleks 3 

Rozwi

ą

zanie w bazie [x

1

, x

3

,] jest rozwi

ą

zaniem optymalnym.

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (24)

rozwiązanie (24)

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

0

5/3

1

-1/3

2/3

14/3

z

j

3

22/3

5

1/3

7/3

94/3

c

j

-z

j

0

-16/3

0

-1/3

-7/3

Tablica simpleks 3 

Zmienne bazowe: x

1

=8/3 i x

3

=14/3

Zmienne niebazowe: x

2

=0, x

4

=0, x

5

=0.

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (25)

rozwiązanie (25)

2013-10-25

31

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

0

5/3

1

-1/3

2/3

14/3

z

j

3

22/3

5

1/3

7/3

94/3

c

j

-z

j

0

-16/3

0

-1/3

-7/3

Tablica simpleks 3 

Rozwi

ą

zanie: 

x

1

=8/3, x

2

=0, x

3

=14/3, x

4

=0 i x

5

=0

F(x

1

, x

2

, x

3

,x

4

,x

5

) = 94/3

Odp. Przedsi

ę

biorstwo osi

ą

gnie maksymalny przychód równy 94/3 jednostek, je

ś

li 

b

ę

dzie produkowało 8/3 jednostki wyrobu A i 14/3 jednostki wyrobu C. Wyrobu B nie 

nale

ż

y produkowa

ć

, za

ś

 zasoby obu surowców zostan

ą

 w pełni wykorzystane .

Przykład 4 

Przykład 4 –

– rozwiązanie (26)

rozwiązanie (26)

ID,2013/2014 

Warto

ś

ci zmiennych dualnych odczytujemy w wierszu z

j

w 

tych kolumnach, które odpowiadały zmiennym bazowym w 
pierwszej tablicy,

…a wi

ę

c w kolumnie zmiennej x

4

i zmiennej x

5

. Wynika st

ą

d, 

ż

e y

1

=1/3 oraz y

2

=7/3

x

b

x

j

x

1

x

2

x

3

x

4

x

5

b

i

θ

i

c

b

/c

j

3

2

5

0

0

x

1

3

1

-1/3

0

2/3

-1/3

8/3

x

3

5

0

5/3

1

-1/3

2/3

14/3

z

j

3

22/3

5

1/3

7/3

94/3

c

j

-z

j

0

-16/3

0

-1/3

-7/3

ID,2013/2014 

Przykład 4 

Przykład 4 –

– rozwiązanie (27)

rozwiązanie (27)

2013-10-25

32

Przykład 5

Przykład 5

Racjonalna hodowla drobiu wymaga dostarczenia miesi

ę

cznie 

ka

ż

dej sztuce dwóch składników od

ż

ywczych: S

1

– co najmniej 

30 jednostek, S

2

– co najmniej 50 jednostek, zawartych w 

trzech paszach. Dane o zawarto

ś

ci składników i cenie 

poszczególnych pasz przedstawia tabela.

Ile paszy poszczególnego gatunku nale

ż

y dostarczy

ć

, aby 

zapewni

ć

 wła

ś

ciw

ą

 kombinacj

ę

 składników od

ż

ywczych przy 

mo

ż

liwie najni

ż

szych kosztach wy

ż

ywienia.

Pasze

Zawarto

ść

 składnika w 1 

kg paszy

Cena 

paszy

S

1

S

2

P

1

2

10

10

P

2

7,5

2,5

15

P

3

3

4

12

ID,2013/2014 

Krok 1 i 2 

Krok 1 i 2 -- Zapisanie modelu liniowego problemu w postaci 

Zapisanie modelu liniowego problemu w postaci 

standardowej i kanonicznej

standardowej i kanonicznej

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce:

Warunki brzegowe:

Funkcja celu:

x

1

– ilo

ść

 paszy P

1

, któr

ą

 nale

ż

y zakupi

ć

x

2

– ilo

ść

 paszy P

2

, któr

ą

 nale

ż

y zakupi

ć

x

3

– ilo

ść

 paszy P

3

, któr

ą

 nale

ż

y zakupi

ć

[s1] 2x

1

+7,5x

2

+3x

3

≥

30

[s2] 10x

1

+2,5x

2

+4x

3

≥

50

x

1,

x

2

, x

3

≥

0

F(x

1

,x

2

,x

3

) = 10x

1

+15x

2

+12x

3

→

MIN

Zmienne decyzyjne:

Warunki ograniczaj

ą

ce:

Warunki brzegowe:

Funkcja celu:

[s1] 2x

1

+7,5x

2

+3x

3

-x

4

+u

1

=30

[s2] 10x

1

+2,5x

2

+4x

3

-x

5

+u

2

=50

x

1,

x

2

, x

3

,x

4,

x

5,

u

1

,u

2

≥

0

F(x

1

,x

2

,x

3,

x

4,

x

5,

u

1

,u

2

) = 

10x

1

+15x

2

+12x

3

+0x

4

+0x

5

+Mu

1

+Mu

2

→

MIN

x

1

– ilo

ść

 paszy P

1

, któr

ą

 nale

ż

y zakupi

ć

x

2

– ilo

ść

 paszy P

2

, któr

ą

 nale

ż

y zakupi

ć

x

3

– ilo

ść

 paszy P

3

, któr

ą

 nale

ż

y zakupi

ć

x

4

, x

5 

–– ilo

ść

 składnika s1 i s2 

dostarczona ponad wymagane minimum
u

1

,u

2

– zmienne sztuczne

Przykład 5 

Przykład 5 –

– rozwiązanie (1)

rozwiązanie (1)

ID,2013/2014 

2013-10-25

33

Rozpoczynamy od przyj

ę

cia, 

ż

e te zmienne, które wyst

ę

puj

ą

 w wi

ę

cej ni

ż

 

jednym ograniczeniu, s

ą

 równe zero

x

1

,x

2

,x

3

=0

W efekcie tego zało

ż

enia wszystkie zmienne dodatkowe maj

ą

 warto

ś

ci 

takie jak wyrazy wolne stoj

ą

ce po prawej stronie odpowiednich 

ogranicze

ń

. Dla rozwa

ż

anego modelu otrzymujemy wi

ę

c:

x

4

=-30, x

5

=-50

Z uwagi na to, 

ż

e zmienne x

4

i x

5

s

ą

 ujemne to nie tworz

ą

 one bazowego 

rozwi

ą

zania dopuszczalnego. 

Dodajemy zmienne sztuczne (u

1

i u

2

) – otrzymamy wst

ę

pne 

rozwi

ą

zanie bazowe.

Dalsze post

ę

powanie jest identyczne jak przy rozwi

ą

zywaniu zadania 

metod

ą

 simpleks.

Krok

Krok 3

3 –

– Wstępne

Wstępne dopuszczane

dopuszczane rozwiązanie

rozwiązanie modelu

modelu

Przykład 5 

Przykład 5 –

– rozwiązanie (2)

rozwiązanie (2)

ID,2013/2014 

Parametry funkcji celu zmiennych sztucznych zale

żą

 

od kryteriów optymalno

ś

ci:

Je

ś

li funkcja celu jest minimalizowana

minimalizowana to parametr 

wynosi +M;

Je

ś

li funkcja celu jest maksymalizowana

maksymalizowana to 

parametr wynosi –M.

M – bardzo du

ż

a liczba dodatnia!!!

ID,2013/2014 

2013-10-25

34

Tablica simpleks 1 

Krok

Krok 3

3,,4

4,,5

5

Rozwi

ą

zanie w bazie [u

1

, u

2

] nie jest rozwi

ą

zaniem optymalnym.

[s1] 2x

1

+7,5x

2

+3x

3

-x

4

+u

1

=30

[s2] 10x

1

+2,5x

2

+4x

3

-x

5

+u

2

=50

F(x

1

,x

2

,x

3,

x

4,

x

5,

u

1

,u

2

) = 

10x

1

+15x

2

+12x

3

+0x

4

+0x

5

+Mu

1

+Mu

2

→

MIN

Przykład 5 

Przykład 5 –

– rozwiązanie (3)

rozwiązanie (3)

ID,2013/2014 

Tablica simpleks 2 

Krok

Krok 4

4,,5

5,,6

6

Rozwi

ą

zanie w bazie [u

1

, x

1

] nie jest rozwi

ą

zaniem optymalnym.

Przykład 5 

Przykład 5 –

– rozwiązanie (4)

rozwiązanie (4)

ID,2013/2014 

2013-10-25

35

Tablica simpleks 3

Rozwi

ą

zanie: 

x

1

=4,29, x

2

=2,86

Odp. Nale

ż

y zakupi

ć

 (dostarczy

ć

) 4,29 kg paszy P1 oraz 2,86 kg paszy P2, aby 

zapewni

ć

 wła

ś

ciw

ą

 kombinacj

ę

 składników od

ż

ywczych przy mo

ż

liwie najni

ż

szych 

kosztach wy

ż

ywienia, które wynios

ą

 85,71 zł.

F(x

1

,x

2

,x

3,

x

4,

x

5,

u

1

,u

2

) =85,71 

Krok

Krok 4

4,,5

5,,6

6;; rozwiązanie

rozwiązanie optymalne

optymalne

Przykład 5 

Przykład 5 –

– rozwiązanie (5)

rozwiązanie (5)

ID,2013/2014 

Ró

ż

nice w algorytmie metody 

Ró

ż

nice w algorytmie metody 

simpleks na  MAX i MIN

simpleks na  MAX i MIN

ID,2013/2014 

2013-10-25

36

Postać bazowa

Postać bazowa

Wszystkie ograniczenia w postaci równa

ń

;

W ka

ż

dym ograniczeniu znajduje si

ę

 zmienna, która po 

wyzerowaniu pozostałych zmiennych ma warto

ść

 

nieujemn

ą

;

Współczynnik przy zmiennej swobodnej ma warto

ść

 1;

Wprowadzone zmienne swobodne wprowadza si

ę

 do 

funkcji celu z zerowymi współczynnikami;
Wprowadzone zmienne sztuczne uwzgl

ę

dnia si

ę

 w funkcji 

celu ze współczynnikami M, których znak zale

ż

y od 

kierunku optymalizacji.

Dla zmiennych bazowych wska

ź

niki optymalno

ś

ci zawsze 

s

ą

 równe zero.

ID,2013/2014 

Kryterium wejścia do bazy

Kryterium wejścia do bazy

MAX:

Zmienna z najwi

ę

ksz

ą

 warto

ś

ci

ą

 wiersza 

zerowego

MIN:

Zmienna z najmniejsz

ą

 warto

ś

ci

ą

 wiersza 

zerowego

ID,2013/2014 

2013-10-25

37

Kryterium wyjścia z bazy

Kryterium wyjścia z bazy

MAX:

Zmienna, dla której iloraz elementu z wektora 

wyrazów wolnych przez współczynnik z kolumny 

zmiennej wchodz

ą

cej do bazy ma najmniejsz

ą

 

warto

ść

.

MIN:

Identycznie jak w zadaniu na MAX.

ID,2013/2014 

Gdy dwa lub wi

ę

cej wska

ź

ników 

θ

i posiada 

jednakow

ą

 minimaln

ą

 warto

ść

.

Pomocnicze wska

ź

niki 

θ

i - ich warto

ś

ci 

powstaj

ą

 poprzez podzielenie współczynników 

stoj

ą

cych w pierwszej kolumnie odpowiadaj

ą

cej 

wektorom jednostkowym przez odpowiednie 
współczynniki wektora zmiennych 
wprowadzanej do bazy.

Z bazy zostanie usuni

ę

ta zmienna, dla której 

obliczony wska

ź

nik pomocniczy 

θ

i ma 

najmniejsz

ą

 warto

ść

.

Degeneracja w algorytmie 

Degeneracja w algorytmie simpleksowym!!!

simpleksowym!!!

2013-10-25

38

Rozwiązanie optymalne

Rozwiązanie optymalne

MAX:

Wszystkie warto

ś

ci wiersza zerowego musz

ą

 by

ć

 

niedodatnie

MIN: 

Wszystkie warto

ś

ci wiersza zerowego musz

ą

 by

ć

 

nieujemne.

ID,2013/2014 

Na dzisiaj wystarczy…;)

Na dzisiaj wystarczy…;)

ID,2013/2014