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

[e-mail]

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