B.Gładysz Badania operacyjne

2007

ALGORYTM SIMPLEX

Zagadnienie asortymentu produkcji

Firma produkuje dwa wyroby P1, P2. Ograniczeniem dla produkcji s

ą

trzy

surowce S1, S2 i S3.Nakłady jednostkowe surowców s

ą

nast

ę

puj

ą

ce:

-

4

S3

3

2

Zysk

jednostkowy

2

1

S2

2

2

S1

P2

P1

Firma dysponuje nast

ę

puj

ą

cym zapasem surowców: S1 – 14kg, S2 – 8kg,

S3 – 16kg. Zoptymalizuj struktur

ę

produkcji.

B.Gładysz Badania operacyjne

2007

Model matematyczny

Zmienne decyzyjne

- planowana wielko

ść

produkcji wyrobu P1,

- planowana wielko

ść

produkcji wyrobu P2,

• Funkcja celu

• Ograniczenia

max

3

2

2

1

→

+

x

x

0

,

16

4

8

2

14

2

2

2

1

1

2

1

2

1

≥

≤

≤

+

≤

+

x

x

x

x

x

x

x

1

x

2

x

B.Gładysz Badania operacyjne

2007

0 1 2 3 4 5 6 7 8

1

2

3

4

5

6

7

8

X1 –produkt1

X2 - produkt2

S3

S2

(4,2)
Z=14

(0,4)
Z=12

(0,0)
Z=0

(4,0)
Z=8

B.Gładysz, Badania operacyjne 2007

B.Gładysz Badania operacyjne

2007

Posta

ć

bazowa

0

,

,

,

,

16

4

8

2

14

2

2

3

2

1

2

1

3

1

2

2

1

1

2

1

≥

=

+

=

+

+

=

+

+

s

s

s

x

x

s

x

s

x

x

s

x

x

max

0

0

0

3

2

3

2

1

2

1

→

+

+

+

+

s

s

s

x

x

B.Gładysz Badania operacyjne

2007

Algorytm simpleks

0

0

0

3

2

cj-zj

Wska

ź

niki

optymalno

ś

ci

0

0

0

0

0

0

zj

16

1

0

0

0

4

s3

0

8

0

1

0

2

1

s2

0

14

0

0

1

2

2

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie

• Zmienne niebazowe = 0
X1=0, x2=0.

• Funkcja celu = 0

• Zmienne bazowe = bj.

S1=14, s2=8, s3=16.

B.Gładysz Badania operacyjne

2007

0 1 2 3 4 5 6 7 8

1

2

3

4

5

6

7

8

X1 –produkt1

X2 - produkt2

S3

S2

(4,2)
Z=14

(0,4)
Z=12

(0,0)
Z=0

(4,0)
Z=8

B.Gładysz, Badania operacyjne 2007

B.Gładysz Badania operacyjne

2007

Wska

ź

niki optymalno

ś

ci

∑

−

=

−

=

∆

=

m

i

iB

ij

j

j

j

j

c

a

c

z

c

1

B.Gładysz Badania operacyjne

2007

Kryterium optymalno

ś

ci

• Rozwi

ą

zanie jest optymalne (max),

gdy wszystkie wska

ź

niki s

ą

niedodatnie.

• Rozwi

ą

zanie jest optymalne (min),

gdy wszystkie wska

ź

niki s

ą

nieujemne.

B.Gładysz Badania operacyjne

2007

Zamiana zmiennych bazowych

j

0

=2

wchodzi
do bazy

max

0

0

0

3

2

cj-zj

0

0

0

0

0

0

zj

i

o

=2

-

16

1

0

0

0

4

s3

0

wychodzi
z bazy

min

8/2 = 4

8

0

1

0

2

1

s2

0

14/2 = 7

14

0

0

1

2

2

s1

0

s3

s2

s1

x2

x1

Baza

bi/aij

0

bi

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie w nowej bazie

0

0

0

0

j

i

j

i

j

i

a

a

a

=

′

Elementy wiersza zmiennej wychodz

ą

cej z bazy

Wiersz zmiennej wychodz

ą

cej z bazy dzielimy przez

główny element przekształcenia:

Elementy pozostałych wierszy

Od danego wiersza odejmujemy nowy wiersz zmiennej

wychodz

ą

cej z bazy pomno

ż

ony przez element tego wiersza

stoj

ą

cy w kolumnie zmiennej wychodz

ą

cej z bazy.

0

0

ij

j

i

ij

ij

a

a

a

a

′

−

=

′

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie w nowej bazie

nowy wiersz2 = stary wiersz2 : 2

s3

0

4

0

0,5

0

1

0,5

x2

3

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie w nowej bazie

nowy wiersz1 = stary wiersz1 – 2 * nowy wiersz2

s3

0

4

0

0,5

0

1

0,5

x2

3

6

0

-1

1

0

1

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie w nowej bazie

nowy wiersz3 = wiersz3 – 0 * nowy wiersz2

16

1

0

0

0

4

s3

0

4

0

0,5

0

1

0,5

x2

3

6

0

-1

1

0

1

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Wska

ź

niki optymalno

ś

ci

0

-1,5

0

0

0,5

Cj-zj

12

0

1,5

0

3

1,5

Zj

16

1

0

0

0

4

s3

0

4

0

0,5

0

1

0,5

x2

3

6

0

-1

1

0

1

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie

• Zmienne niebazowe = 0
X1=0, s2=0.

• Funkcja celu = 12

• Zmienne bazowe = bj.

X1 =4, S1=6, s3=16.

B.Gładysz Badania operacyjne

2007

0 1 2 3 4 5 6 7 8

1

2

3

4

5

6

7

8

X1 –produkt1

X2 - produkt2

S3

S2

(4,2)
Z=14

(0,4)
Z=12

(0,0)
Z=0

(4,0)
Z=8

B.Gładysz, Badania operacyjne 2007

B.Gładysz Badania operacyjne

2007

Zamiana zmiennych bazowych

j

0

=1

wchodzi
do bazy

max

0

-1,5

0

0

0,5

cj-zj

i

0

=3

12

0

1,5

0

3

1,5

zj

wychodzi
z bazy

min

16 : 4 = 4

16

1

0

0

0

4

s3

0

4 : 0,5 = 8

4

0

0,5

0

1

0,5

x2

3

6 : 1 = 6

6

0

-1

1

0

1

s1

0

s3

s2

s1

x2

x1

Baz

a

bi/aij

0

bi

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

nowy wiersz3= stary wiersz3 :4

4

0,25

0

0

0

1

x1

2

x2

3

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie w nowej bazie

nowy wiersz1 = stary wiersz1 – 1* nowy wiersz3

4

0,25

0

0

0

1

x1

2

x2

3

2

-0,25

-1

1

0

0

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie w nowej bazie

nowy wiersz2 = stary wiersz2 – 0,5 * nowy wiersz3

4

0,25

0

0

0

1

x1

2

2

-0,125

0,5

0

1

0

x2

3

2

-0,25

-1

1

0

0

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Wska

ź

niki optymalno

ś

ci

-0,125

-1,5

0

0

0

cj - zj

14

0,125

1,5

0

3

2

zj

4

0,25

0

0

0

1

x1

2

2

-0,125

0,5

0

1

0

x2

3

2

-0,25

-1

1

0

0

s1

0

s3

s2

s1

x2

x1

Baza

b

0

0

0

3

2

cj

B.Gładysz Badania operacyjne

2007

Rozwi

ą

zanie optymalne

• Zmienne niebazowe = 0
s2=0, s3=0.

• Funkcja celu = 14

• Zmienne bazowe = bj.

X1 =4, x2=2, s1=2.

B.Gładysz Badania operacyjne

2007

0 1 2 3 4 5 6 7 8

1

2

3

4

5

6

7

8

X1 –produkt1

X2 - produkt2

S3

S2

(4,2)
Z=14

(0,4)
Z=12

(0,0)
Z=0

(4,0)
Z=8

B.Gładysz, Badania operacyjne 2007

MAX

B.Gładysz Badania operacyjne

2007

Zagadnienie mieszaniny

Dziennie nale

ż

y spo

ż

y

ć

co najmniej 100g białka. Spo

ż

ycie chleba nie

powinno przekracza

ć

1 kg dziennie, za

ś

spo

ż

ycie ponad 200g tłuszczy jest

szkodliwe dla zdrowia. Wiedz

ą

c,

ż

e w jednym kg chleba zawiera si

ę

50g

białka i 20g tłuszczy oraz

ż

e w 1 kg mi

ę

sa zawiera si

ę

100g białka i 200g

tłuszczy nale

ż

y obni

ż

y

ć

do minimum koszty wy

ż

ywienia. Cena chleba za 1

kg wynosi 2 zł, za

ś

mi

ę

sa 20 zł.

Zmienne decyzyjne:

X1-dzienna racja chleba
X2 – dzienna racja tłuszczu

Funkcja celu:

z = 2 x1 + 20 x2

Ograniczenia:

50 x1 + 100 x2 >= 100
20 x1 + 200 x2 <= 200
x1 <= 1
x1 >= 0
x2 >= 0

B.Gładysz Badania operacyjne

2007

Zagadnienie mieszaniny

Funkcja celu:

z = 2 x1 + 20 x2+0 s1+0 s2+0 s3+M a1

->min

Ograniczenia:

50 x1 + 100 x2 – s1

+ a1

= 100

20 x1 + 200 x2

+ s2

= 200

x1

+s3 = 1

x1, x2, s1, s2, s3, a1>=0,

M – du

ż

a liczba

B.Gładysz Badania operacyjne

2007

0

-M

0

0

1

a1

-M

0

0

M

-20+100M

-2+50M

cj-zj

Wska

ź

niki

optymalno

ś

ci

-100M

0

0

M

-100M

-50M

zj

1

1

0

0

0

1

s3

0

200

0

1

0

200

20

s2

0

100

0

0

-1

100

50

a1

-M

s3

s2

s1

x2

x1

Baza

b

0

0

0

-20

-2

cj

Algorytm Simplex

Pierwsze rozwi

ą

zanie bazowe (max)