PRZYKŁAD AP-2

Dana jest tablica rozwiązania optymalnego

C

B

BAZA

Niewiadome

bazowe

50

1

x

1

p

100

2

x

2

p

80

3

x

3

p

0

1

S

p

4

0

S

2

5

p

M

1

t

6

p

M

2

t

7

p

Wartości
niewiadomych
bazowych

80

3

p

3

x

0

0

1

-1

1

1

-1

10

50

1

p

1

x

1

1

0

1

-2

-1

2

20

∆∆∆∆

j

j

j

z

c

=

−

0

-50

0

-30

-20

30

-M

20

-M

1800

następującego zadania optymalizacyjnego:

Znaleźć wartość najmniejszą funkcji

3

2

1

3

2

1

80

100

50

)

,

,

(

x

x

x

x

x

x

f

+

+

=

na zbiorze

rozwiązań układu nierówności:











≥

≥

+

+

≥

+

+

0

,

,

30

40

2

3

2

1

3

2

1

3

2

1

x

x

x

x

x

x

x

x

x

.

Wiadomo, że bazę w startowej tablicy simpleks tworzyły wektory (

6

p ,

7

p

).

a) Jakie wartości może przyjmować współczynnik

2

c

przy niewiadomej

2

x

, aby rozwiązanie

optymalne nie uległo zmianie?

b) Jakie wartości może przyjmować wartość ograniczenia

1

b aby rozwiązanie optymalne było

w dalszym ciągu wyznaczane przez wektory (

3

p

,

1

p

)?

Rozwiązanie

:

Ad a) Załóżmy, że nowa wartość współczynnika przy niewiadomej

2

x

będzie równa

2

2

100

c

c

∆

+

=

. Ponieważ w rozwiązaniu optymalnym niewiadoma

2

x nie jest niewiadomą

bazową, to wystarczy aby

50

2

2

2

−

≥

∆

⇒

∆

≥

∆

c

c

. Stąd wynika, że

)

,

50

2

∞

+

−

<

∈

∆

c

,

czyli współczynnik

2

c

przy niewiadomej

2

x

może przyjmować wartości z przedziału

)

,

50

∞

+

<

i rozwiązanie optymalne

20

1

=

op

x

,

0

2

=

op

x

10

3

=

op

x

nie ulegnie zmianie, nie

zmieni się także wartość funkcji celu.

Ad b) Załóżmy, że nowa wartość ograniczenia

1

b

będzie równa

1

1

40

b

b

∆

+

=

. Dopuszczalne

zmiany wartości

1

b , przy których nie zmienia się baza wyznaczająca rozwiązanie optymalne

(ale zmieniać się mogą wartości zmiennych w rozwiązaniu bazowym) otrzymujemy
rozwiązując układ nierówności

0

b

B

≥

⋅

.

Z tablicy rozwiązania optymalnego odczytujemy elementy macierzy B jako współrzędne
wektorów (

6

p ,

7

p ), które tworzyły bazę w startowej tablicy simpleks, zatem













−

−

=

2

1

1

1

B

oraz













∆

+

=

30

40

1

b

b

.

Rozwiązując układ nierówności







≥

⋅

+

∆

+

⋅

−

≥

⋅

−

+

∆

+

⋅

0

30

2

)

40

(

)

1

(

0

30

)

1

(

)

40

(

1

1

1

b

b

Otrzymujemy, że

>

−

<

∈

∆

20

,

10

1

b

, a stąd

>

<

∈

60

,

30

1

b

. Rozwiązanie optymalne będzie

wówczas wyznaczone przez te same wektory (

3

p

,

1

p

)

i będzie ono następujące

0

,

0

,

0

,

0

,

10

,

0

,

20

2

1

2

1

1

3

2

1

1

=

=

=

=

∆

+

=

=

∆

−

=

t

t

S

S

b

x

x

b

x

op

op

op

op

op

. Funkcja celu dla

tego rozwiązania optymalnego ma wartość

1

30

1800

b

∆

⋅

+

.