Файл: Говар В.М. Математическое программирование учеб. пособие.pdf

-

224 -

Следовательно,

при Х3 s

I i x 2 r 6

и

Х Г

Аналогично

вычисляем

f } ( I ) ,

fj(2),

%(3), ^ ( 4 ) ,

т \ ( 5 ) »

? } ( 6 ) »

1^(7)

и

заполняем

строки

^(Х)

и х 3 таблицы

( D . I O ) .

только в первых трех областях

составляет: Xj »

I ,

х^ = 6 и х^ = I .

Таблица

13.10

; 0

I

!

г

—i

i

5 !

i

1-

8

i

»

2

3

i

4

6

! 7 î

ь

28 j (g) ! 49

73

!

97

І2І

j

144

i

168

1 194

с »

28

27

J

5 0

74

121

143

!

I b 9 1 196

Ь

(X)

28

(S)

i

4 7

72

!

95

120

i

145

!

IVO 1

195

j

1 146

<h

(X)

28

26

®

75

j

98

122

І

169

!

194

i

Y* С»

56

53

52

75

i!

99

121

145

Іь8

i

192

x 2

0

0

!

i

2

1

0

* '

4

6 1 6

i!

f 3

С»

84

78

| 7 5 -

74

972

121

143

!

167

i

190

х з

0

I

i

I

I Г * 4

I

i

!

I

f .

»

112

106

103

JIOI

iICO

122

145

169

i

191

'

1

1

0

0

!

0

I

i

1

2

2

j

2

На следующем этапе

находим

оптимальную

стратегию

при размеще­

Очевидно, что f 4 ( 0 ) = 112. Вычислим, например,

fw (8 ) :

-

225

-

'<< (8)

•

f,

(0)

194

•*• 84 = 278,

при

x 4

=

8,

Ь

(7)

+

(I )

169

+ 78 = 247,

при

X 4

«

7,

§ч(ь)

+

f,

(2)

146

+ 75 = 221,

при

x 4

=

6,

(5)

•

f-

(3)

122

+ 74 = 196,

при

x 4

< ^

С*) *

^

(4)

98

+ 97 = 195,

при x 4

Ç4

(3) +

% (5)

75 +121 = 196,

при

x 4

<h (2)

+

% (b)

48

+143 = 191,

при

X 4

=

2,

ifч CD + ii

(7)

26

+16? = 193,

при

x 4

=

I ,

J 4 ( 0 )

+

% (8)

28 +190 = 218,

при %k

=

0,

следовательно,

ч ( ^ ) +

f 4

( £ - х 4 ) j =

if4

(2)

+

%(6>

= 191,

при х 4

= 2»

Аналогично вычисляем

-ft(I),

f4 <2),

^ ч

(3),

*рч

(7) и

результаты вычислений заносим в строки

W

и х 4

таблицы ( В .10)

Итак,

минимально возможная величина затрат при размещении

восьми предприятий

в четырех

областях

равна

191 ден.ед. По резуль­

татам решения в четвертой

области

нужно разместить

х 4

* 2 предпри­

ятия,

при атом

'^ч (2) в 48.

Тогда

в первых

трех

областях надо

разместить х т

+ х 2

+ х^ = 8 -

х 4

= 6 предприятий. По таблице (ІЗ.Щ

находим

ѵр3

(6) = 143, при х 3

= I , следовательно.,

в іретьей об ­

ласти нужно разместить одно предприятие,

при эюм

fy3

(I) = 22.

В первых двух областях надо

разместить X j + Ig *

6 - х 5 = 5 пред­

приятий. По таблице (13.10)

находим

<f2

(5)

= 121,

при х 2

= 4»

следовательно,

во второй

области

необходимо

разместить

четыре пред­

приятия,

при этом

і} 2 (4) = 96.

В первой

области

размещается

Xj = 5 -

х 2

= I

предприятие,

при этом

ij,, (I ) -

25.

Таким образом,оптимальная стратегия заключается в размещений

предприятий

следующим образом: Xj = I , %2 =

% = I» % s

2*

нечное

состояние

системы должно

быть в точке M на

тринадцатом

шагеПосмотрим,

откуда

мы можем переместиться ь

точку М"на

этом шаге.

Рассмотрим

отдельно

правый

верхний

угол прямоугольной сетки

с конечной точкой M на таблице

(13 . II),

изображенной

на

рисунке

( І З . І ) .

Ь точку

M можно

переместиться из

Двух соседних точек bj

или Ср причем из каждой

- только

одним

способом. Таким

образом,

если при планировании процесса на

предпоследнем (двенадцатом)

шаге система попадет в точку г>р

то мы должны Двигаться

по гори­

зонтали

при затратах, равных ІЬ;

если ке

в точку

Ср

то,

переме­

минимальные затраты

в квадратах,

которые поставим

в

точках b.j и

Ср

что изображено

на рисунке (13.2). Запись "12"

в

квадратике

у Cj означает минимальные затраты

при переходе

системы из состо­

яния Cj в состояние М. Аналогичный смысл имеет

запись в квадра­

тике

Бр

Рис.13.I

Рис.13.2