1

METODA ANALITYCZNA

Postać klasyczna:
z =

5 x

1

+ 6x

2

→

→

→

→

MAX

0,2 x

1

+ 0,3x

2

< 18

0,6 x

1

+ 0,6x

2

< 48

x

1

, x

2

> 0

cx

→

→

→

→

MAX

Ax < b
x > 0

Postać standardowa (kanoniczna):

z =

5 x

1

+ 6x

2

+ 0x

3

+ 0x

4

→

→

→

→

MAX

0,2 x

1

+ 0,3x

2

= 18

- x

3

0,6 x

1

+ 0,6x

2

= 48

- x

4

x

3

, x

4

– zmienne swobodne (niewykorzystane

moce produkcyjne przy produkcji frytek x

3

oraz przy produkcji puree x

4

)

z =

5 x

1

+ 6x

2

+ 0x

3

+ 0x

4

→

→

→

→

MAX

0,2 x

1

+ 0,3x

2

+ x

3

= 18

0,6 x

1

+ 0,6x

2

+ x

4

= 48

x

1

, x

2

, x

3

, x

4

> 0

2

cx

→

→

→

→

MAX

Ax = b
x > 0

A

–

macierz współczynników o wymiarach

(

m

×

n

),

x

–

n

-wymiarowy wektor zmiennych,

b

–

m

-wymiarowy wektor wyrazów wolnych,

c

–

n

-wymiarowy wektor wag funkcji celu.

B

– macierz kwadratowa

m

-tego stopnia,

składająca się z

m

liniowo niezależnych

kolumn macierzy

A

.

det (

B

)

≠

0

Macierz

B

–

baza

,

kolumny macierzy

B

–

kolumny

bazowe

,

pozostałe

kolumny

macierzy

A

–

kolumny niebazowe

.

Zmienne związane z kolumnami bazowymi

–

zmienne bazowe

,

pozostałe zmienne

–

zmienne niebazowe

.

Z każdą bazą

B

układu

Ax = b

jest związane

rozwiązanie bazowe.

3

Jeżeli układ

Ax = b

jest niesprzeczny oraz

n > m

to układ ten ma nieskończenie wiele

rozwiązań, ale skończoną liczbę rozwiązań
bazowych.

Układ

m

równań z

n

zmiennymi ma

co

najwyżej













m

n

rozwiązań bazowych, czyli:

)!

m

n

(

!

m

!

n

−

Rozwiązanie bazowe układu

Ax = b

:

- wybieramy

m

liniowo niezależnych kolumn

macierzy

A

, czyli bazę

B

,

- zmienne niebazowe przyjmują wartości
zerowe (

x

n

= 0

),

- wartości zmiennych bazowych ustalamy
rozwiązując

układ

m

równań

z

m

niewiadomymi:

Bx

b

= b.

Jeżeli każda zmienna bazowa jest różna od
zera, to takie rozwiązanie bazowe jest
niezdegenerowane.

Jeżeli zadanie programowania liniowego ma
rozwiązanie

optymalne,

to

ma

także

rozwiązanie optymalne bazowe

.

4

Rozwiązania optymalnego wystarczy szukać
wśród rozwiązań bazowych, których liczba
jest skończona

.

Można

znaleźć

rozwiązanie

optymalne

dokonując

przeglądu

zupełnego

zbioru

wszystkich rozwiązań bazowych.

Przykład:

z =

5 x

1

+ 6x

2

+ 0x

3

+ 0x

4

→

→

→

→

MAX

0,2 x

1

+ 0,3x

2

+ x

3

= 18

0,6 x

1

+ 0,6x

2

+ x

4

= 48

x

1

x

2

x

3

x

4

Macierz

A

:

0,2 0,3

1

0

0,6 0,6

0

1

m=2, n=4

mamy zatem co najwyżej:

n

4

n!

4!

6

m

m!(n m)!

2

2!2!





 

=

=

=

=





 

−





 

rozwiązań bazowych.

x

1,

x

2

x

1,

x

3

x

1,

x

4

x

2,

x

3

x

2,

x

4

x

3,

x

4

5

x

1,

x

2:

0,2x

1

+ 0,3x

2

= 18

0,6x

1

+ 0,6x

2

= 48

x

1

= 60, x

2

= 20, z = 420

x

1,

x

3:

0,2x

1

+ x

3

= 18

0,6x

1

= 48

x

1

= 80, x

3

= 2, z = 400

x

1,

x

4:

0,2x

1

= 18

0,6x

1

+ x

4

= 48

x

1

= 90, x

4

= -6

rozw. sprzeczne

x

2,

x

3:

0,3x

2

+ x

3

= 18

0,6x

2

= 48

x

2

= 80, x

3

= -6

rozw. sprzeczne

6

x

2,

x

4:

0,3x

2

= 18

0,6x

2

+ x

4

= 48

x

2

= 60, x

4

= 12, z = 360

x

3,

x

4:

x

3

= 18

x

4

= 48

x

3

=18, x

4

= 48, z = 0

Zmienne

Zmienne bazowe

x

1,

x

2

x

1,

x

3

x

1,

x

4

x

2,

x

3

x

2,

x

4

x

3

x

4

x

1

60

80

90

0

0

0

x

2

20

0

0

80

60

0

x

3

0

2

0

-6

0

18

x

4

0

0

-6

0

12

48

wartość

funkcji celu

z

420

D

MAX

400

B

sprz.

C

sprz.

E

360

F

0

A

7

Przykład:
Firma

produkująca

3

rodzaje

soków

owocowych (wieloowocowe, pomarańczowe i
jabłkowe) dostała zamówienie na dokładnie 40
tys. kartonów 1-litrowych. Zleceniodawca
miał określone preferencje co do struktury
asortymentowej

zamówienia.

Soków

wieloowocowych ma być w partii co najmniej
5 tys. kartonów, zaś soków jabłkowych nie
więcej niż 16 tys. kartonów. Zysk netto przy
produkcji każdego rodzaju z soków wynosi
odpowiednio 8, 9 i 10 groszy/karton. Ile
soków każdego rodzaju należy wyprodukować
aby zmaksymalizować całkowity zysk netto ze
sprzedaży?

Jak

kształtuje

się

struktura

8

asortymentowa zrealizowanego zamówienia?
Zastosować

w

rozwiązaniu

metodę

analityczną.

x

1

– wielkość dostawy soków wieloowocowych,

x

2

– wielkość dostawy soków pomarańczowych,

x

3

– wielkość dostawy soków jabłkowych.

Postać klasyczna:

z =

8x

1

+ 9x

2

+10 x

3

→

→

→

→

MAX

x

1

+ x

2

+ x

3

= 40

x

1

> 5

x

3

< 16

x

1

, x

2

, x

3

> 0

Postać standardowa:

z =

8x

1

+ 9x

2

+10x

3

+0x

4

+ 0x

5

→

→

→

→

MAX

x

1

+ x

2

+ x

3

= 40

x

1

= 5

+ x

4

x

3

= 16

- x

5

x

4

– nadwyżka dostawy soków wieloowocowych

ponad minimalny limit,
x

5

– niedobór dostawy soków jabłkowych w

stosunku do maksymalnego limitu.

9

z =

8x

1

+ 9x

2

+10x

3

+0x

4

+ 0x

5

→

→

→

→

MAX

x

1

+ x

2

+ x

3

= 40

x

1

- x

4

= 5

x

3

+ x

5

= 16

x

1

, x

2

, x

3

, x

4

, x

5

> 0

x

1

x

2

x

3

x

4

x

5

Macierz

A

:

1

1

1

0

0

1

0

0

-1

0

0

0

1

0

1

m=3, n=5

mamy zatem

co najwyżej

:

5

5!

10

3

3!2!

 

=

=

 

 

rozwiązań bazowych:

1)

x

1

, x

2

, x

3

x

1

+ x

2

+ x

3

=40

x

1

=5

x

3

=16

x

1

=5, x

2

=19, x

3

=16, z=371

10

2)

x

1

, x

2

, x

4

x

1

+ x

2

=40

wektory
liniowo
zależne

x

1

- x

4

=5

x

1

x

2

x

4

mnożymy

x

2

przez (-1)

x

1

x

2

x

4

suma

1

1

0

1

-1

0

0

1

0

-1

1

0

-1

0

0

0

0

0

0

0

0

3)

x

1

, x

2

, x

5

x

1

+ x

2

=40

x

1

=5

x

5

=16

x

1

=5, x

2

=35, x

5

=16, z=350

4)

x

1

, x

3

, x

4

5)

x

1

, x

3

, x

5

6)

x

1

, x

4

, x

5

7)

x

2

, x

3

, x

4

8)

x

2

, x

3

, x

5

11

x

2

+x

3

=40

wektory
liniowo
zależne

x

3

+ x

5

=16

x

2

x

3

x

5

mnożymy

x

3

przez (-1)

x

2

x

3

x

5

suma

1

1

0

1

-1

0

0

0

0

0

0

0

0

0

0

1

1

0

-1

1

0

9)

x

2

, x

4

, x

5

10)

x

3

, x

4

, x

5

mamy

więc

dokładnie

8

rozwiązań

bazowych:

Zmienne

Zmienne bazowe

1

3

4

5

6

7

9

10

x

1

5

5

24

5

40

0

0

0

x

2

19

35

0

0

0

24

40

0

x

3

16

0

16

35

0

16

0

40

x

4

0

0

19

0

35

-5

-5

-5

x

5

0

16

0

-19 16

0

0

16

z

371

MAX

355 352 sprz. 320 sprz. sprz. sprz.

z =

8x

1

+ 9x

2

+10 x

3

→

→

→

→

MAX

x

1

+ x

2

+ x

3

= 40

x

1

> 5

x

3

< 16

x

1

, x

2

, x

3

> 0

12

Zadania do rozwiązania

Zadanie 1:

z=

1,2x

1

+1,8x

2

→

MIN

2 x

1

+ x

2

> 40

x

1

+3x

2

> 60

x

1

+x

2

> 30

x

1,

x

2

> 0

Rozwiązać przykład metodą graficzną i
analityczną. Sprawdzić rozwiązanie w winqsb.

Rozwiązanie:
x

1

=15, x

2

=15, x

3

=5, x

4

=0, x

5

=0, z

MIN

=45

Zadanie 2:

z=

2x

1

+3x

2

+0x

3

+0x

4

→

MAX

x

1

+2x

2

+x

3

= 4

x

1

-x

4

= 2

x

1,

x

2

,x

3

, x

4

> 0

Rozwiązać przykład metodą analityczną.
Sprawdzić rozwiązanie w winqsb.

Rozwiązanie:
x

1

=4, x

2

=0, x

3

=0, x

4

=2, z

MAX

=8