Programowanie liniowe rachunek Nieznany

background image

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

...

...

...

...

...

...

...

...

...

...

...

Rozwi

Rozwi

ą

ą

zanie algorytmu SIMPLEKS

zanie algorytmu SIMPLEKS

metod

metod

ą

ą

rachunku macierzowego

rachunku macierzowego

Zagadnienie programowania liniowego w ogólnej postaci:

background image

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

=

Zagadnienie programowania liniowego w postaci macierzowej:

background image

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

Postać pierwszej tablicy simpleksowej w postaci ogólnej

background image

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

Postać tablicy simpleksowej po

l

-tej iteracji:

background image

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

l

l

V

B

=

−1

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

l

-tej iteracji )

l

V

background image

Rozwiązać zagadnienie programowania liniowego w postaci kanonicznej:

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

[

]

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

background image

Rozwiązać zagadnienie programowania liniowego w postaci kanonicznej:

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

[

]

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

background image

Wartości

c

j

– z

j

nazywamy

wskaźnikiem optymalności

(kryterium simpleks)

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

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

j

0

0

0

0

0

0

c

j

- z

j

2

3

0

0

0

0

b

Tablica simpleks w pierwszej postaci bazowej

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

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

j

0

0

0

0

0

0

c

j

- z

j

2

3

0

0

0

0

b

Tablica simpleks w pierwszej postaci bazowej

kryterium wejścia

kryterium wyjścia

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

z

j

c

j

- z

j

b

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

x

2

x

5

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

x

2

3

x

5

0

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

=

1

0

0

0

2

0

0

2

1

2

B

x

3

x

2

x

5

=

1

0

0

0

5

,

0

0

0

1

1

2

V

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

-1

0

x

2

3

0

0,5

0

x

5

0

0

0

1

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

=

1

0

0

0

2

0

0

2

1

2

B

x

3

x

2

x

4

=

1

0

0

0

5

,

0

0

0

1

1

2

V

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

-1

0

x

2

3

0

0,5

0

x

5

0

0

0

1

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

=



=

0

4

1

5

,

0

0

1

0

2

4

1

2

2

1

0

0

0

5

,

0

0

0

1

1

A

V

s

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

0

1

-1

0

x

2

3

0,5

1

0

0,5

0

x

5

0

4

0

0

0

1

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

0

1

-1

0

x

2

3

0,5

1

0

0,5

0

x

5

0

4

0

0

0

1

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

=

=

16

4

6

16

8

14

1

0

0

0

5

,

0

0

0

1

1

2

b

V

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

0

1

-1

0

6

x

2

3

0,5

1

0

0,5

0

4

x

5

0

4

0

0

0

1

16

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

12

0

3

0

16

4

6

2

2

=

=

b

V

c

B

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

0

1

-1

0

6

x

2

3

0,5

1

0

0,5

0

4

x

5

0

4

0

0

0

1

16

z

j

12

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

[

]

0

0

0

3

5

,

1

0

4

5

,

0

3

0

1

0

3

0

2

2

=

=

A

V

c

B

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

0

1

-1

0

6

x

2

3

0,5

1

0

0,5

0

4

x

5

0

4

0

0

0

1

16

z

j

1,5

3

0

1,5

0

12

c

j

- z

j

b

Tablica simpleksowa w trakcie II iteracji

[

] [

]

[

]

0

5

,

1

0

0

5

,

0

0

0

0

3

5

,

1

0

5

,

1

0

3

2

2

2

=

=

=

A

V

c

c

B

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

0

1

-1

0

6

x

2

3

0,5

1

0

0,5

0

4

x

5

0

4

0

0

0

1

16

z

j

1,5

3

0

1,5

0

12

c

j

- z

j

0,5

0

0

-1,5

0

b

Tablica simpleksowa po II iteracji

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

0

1

-1

0

6

x

2

3

0,5

1

0

0,5

0

4

x

5

0

4

0

0

0

1

16

z

j

1,5

3

0

1,5

0

12

c

j

- z

j

0,5

0

0

-1,5

0

b

Tablica simpleksowa w trakcie II iteracji

kryterium wejścia

kryterium wyjścia

background image

cx →max

2

3

0

0

0

Baz

a

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

x

2

3

x

1

2

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie III iteracji

=

4

0

0

1

2

0

2

2

1

3

B

x

3

x

2

x

1

=

25

,

0

0

0

13

,

0

5

,

0

0

25

,

0

1

1

3

V

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

-1

-0,25

x

2

3

0

0,5

-0,13

x

1

2

0

0

0,25

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie III iteracji

=

4

0

0

1

2

0

2

2

1

3

B

=

25

,

0

0

0

13

,

0

5

,

0

0

25

,

0

1

1

3

V

x

3

x

2

x

1

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

1

-1

-0,25

x

2

3

0

0,5

-0,13

x

1

2

0

0

0,25

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie III iteracji

=

=

1

0

0

1

0

0

0

4

2

1

2

2

25

,

0

0

0

13

,

0

5

,

0

0

25

,

0

1

1

3

A

V

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

0

0

1

-1

-0,25

x

2

3

1

0

0

0,5

-0,13

x

1

2

0

1

0

0

0,25

z

j

c

j

- z

j

b

Tablica simpleksowa w trakcie III iteracji

=

=

4

2

2

16

8

14

25

,

0

0

0

13

,

0

5

,

0

0

25

,

0

1

1

3

b

V

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

0

0

1

-1

-0,25

2

x

2

3

1

0

0

0,5

-0,13

2

x

1

2

0

1

0

0

0,25

4

z

j

14

c

j

- z

j

b

Tablica simpleksowa w trakcie III iteracji

14

2

2

=

b

V

c

B

background image

cx →max

2

3

0

0

0

Baza

c

B

x

1

x

2

x

3

x

4

x

5

x

3

0

0

0

1

-1

-0,25

2

x

2

3

1

0

0

0,5

-0,13

2

x

1

2

0

1

0

0

0,25

4

z

j

3

2

0

1,5

0,13

14

c

j

- z

j

0

0

0

-1,5

-0,13

b

Tablica simpleksowa w trakcie III iteracji

Kryterium simpleks

(wartości nieujemne)

Wartość funkcji

kryterium

Wartości zmiennych

decyzyjnych

Spe

ł

niaj

ą

ce warunek

maksymalizacji FC


Wyszukiwarka

Podobne podstrony:

więcej podobnych podstron