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

-

?2С -

Задача

о размещении

Задана

потребность в определенном продукте в территориальном

разрезе. Известны

пункты»^

которых можно построить предприятия,

выпускающие

данный

продукт.

Подсчитаны затраты на строительство и

рат, требующихся на строительство

и эксплуатацию

всех запланиро­

ванных объектов.

Решение аіой задачи может быть сведено к задаче по распределе­

нию ресурсов типа ( І З . і ' ) - (13.4'') .дополненной

условием

целочис-

ленности, налагаемым на переменные х^

Ц-

1,2,

• • • » " ) »

эконо­

мический смысл которого в данной

задаче

-

количество предприятий,

необходимое для строительства в і

-том пункте.

Для удобства расчетов будем считать, что планируется строи­

тельство предприятий одинаковой мощности.

Пример.

Б четырех областях необходимо построить восемь промышленных

таким образом, чтобы обеспечить суммарные

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

их

строительство

и эксплуатацию. При атом

значения

(х^ ) при­

ведены в таблице

(13.9).

Таблица 13.9

О

I

2

i

І

4

I

5

1

ь

r

—

(X)

3

7

i

8

1

28

25

49

97

144

г.

121

73

ІЬ8

194

И

28

«

50

74

96

121

143

Іь9

196

й , (X)

т

\>

(ху

28

22

47

42

95

120

145

170

195

i

!

а„

(X)

28

2ь

48

?^

98

122

І4Ь

ІЬ9

194

зависимости от количества размещаемых предприятий в [ -той области;

fK

(X) - наименьшая величина затрат, которые нужно произвести

при

строительстве и эксплуатации предприятий в первых "к" областях

(к =

1,2,3,4).

Для решения будем использовать рекуррентное соотношениѳ(І3.4').

Если все предприятия построить только в первой области,

то у ( (Х)=

m in

(Xj) =

^,(X) и минимально

возможные затраты при &8 рав­

ны 194 ден.ед.

Определяем

оптимальную стратегию при размещении предприятий

только в первых двух областях. При этом (13.4' ) будет

иметь вид:

f ü W - m, r? Sa ( Х 2 Ь f, ( X - X 2 ) ) .

Результаты

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

в таблицу ( В . 1 0 ) . Оче­

видно,

что

^fi СО) = 5ь. Чтобы определить

% (I)

надо

вычислить

q,j(D

+ f.(0) = 27 + 28 = 55, при Х> = I ,

%(0)

+ f i CD = 28 + 25 = 53, при х 2

= О,

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

fz

Ср -С Г1>С( {

+ f. tt-V }

=

U

СО) • f,

Ci) = 53, дри

Xg а О И Xj = I .

Вычисляем

f 2

C2) :

\ С 2 )

+

= 50 + 27 s'77, при х 2 = 2,

, ^СІ) +

f,

CD = г? + 25 = 52, при х 2

= I ,

1}гС0)

+

>f;C2) = 28 + 4Э = 77,

при х 2

= О,

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

Ѵ * >

{

+ Ï . ( ^ г ) J -

fcCO

+

f. CD - 52, при

x,

= I

и х т s

i .

- 222

-

Вычисляем

% (3} :

^ ^СЗ ) +

f,(OJ = 74

+ 28

= І02,при х 2

= 3,

ф г (2)

+

%(.!) = 50

+

25

=

Ѵ5,при X £

= 2,

г|г (І)

+

f, (2) = 27

+

49 =

76,ири x 2

= I ,

с г ( 0 )

+

ѴР (з) а

28 + 73 = ІОІ.при х 2

= О,

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

( 3

} = i S

{ M

V

+

*

(3 -*г> J *

№

* t . W = ''5,

при x 2

= 2 и

= I .

Аналогично

вычисляем

(4),

(5), . . .

,

(8).

Найдем,

например, еще

(8):

•f. ( О

= 198 + 28 = 224, при

х 2

=

8,

Фг(7)

+

% (I)

169*"+ 25 = 194, при х 2

=

7,

^ г ( б )

*

f,

(2)

*

143 + 49 = 192, при Х 2

= ь,

f , ( 3 (

= 121 + 73 = 194, при

*2 =

5,

<

Чі (*)

г

96 + 97 = 193, при

х 2

=

4,

+

^ ( 3 )

+

(5)

-

74

tl2 I

= 195, при

хг

=

з ,

0,2 (2)

+

Ч.

м

-

50 +144 = 194, при хг

=

2,

^г(І)

+

s

27 +168 -

195, при х 2

=

I ,

Ы О )

•

•

28 +194 =

222, при

=

0,

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

х2

( х 2 )

+

ч

(&-x2 )

°%(Ь)

+

Y . C Z )

= 192,

f,

f

ПРИ Х2 = 6 И Xj

= 2

Найденные

значения

fx(.%)

и х 2

заносим в соответствующие клеи

ки таблица (13.10). Строка

х 2

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

соответствующую

минимальным

затратан

(2) при размещении пред­

приятий только з первых двух

областях, при атом числе,

находящиеся

в строке х 2 , показывают

число

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

размещаемых во второй

области.

-

223

-

При х =

8,

числа

х 2 =

Ь и X j = 2,

определяет

оптимальную стра­

тегию при размещении

предприятий

только

в

первых двух

областях.

;

Переходим

к следующему этапу, на котором определиѳц оптималь­

ную стратегию

для случая,

когда

размещение предприятий распреде­

ляется

между первыми тремя областями по рекуррентной формуле

Оптимальная стратегия относительно первых двух областей уже

найдена.

Определяем

оптимальную

стратегию

при размещении предприя­

тий с третьей и одновременно

ь первых двух областях.

Очевидно,что

I

%(0)

»

84.

I

Вычислим,

например,

f j ( 5 ) :

f

(^(5)

+

(0)

=

120

t

5b

=

176,

при

X j

«= 5,

+

fa

(I)

=

95 + 53 = 148,

лри

%ъ

=

4,

+

fa

(2)

=

72 + 52 = 124,

при х 3

=

3,

<Ь(2)

+

f*

(3)

=

47 + 75 = 122,

при Xj

=

2,

ЩІ)

+

%

(4)

=

22 + 99 = 121,

при х 5

=

I ,

<Ь(0)

+

fz

(5)

=

28

+121

-

149,

при

х 3

=

О,

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

* М 5 '

в

Д ^ 5

{ î î { x 3 J

+

t i ( 5 - ï 3 ) } =

•

%(4)

a 121, при

x3

= I , x2

= 4 и Xj

- 0.

Вычислим

(8):

vj,3(8)

•

f*

(0)

»

195

+

5.6

=

251,

при

x3

=

8,'

<j,3(?)

+

f-2

(I)

~ 170

*

53

=

223,

при

x3

=

7,

ф3 (6)

+

f 2

(2)

=

145 + 52 = 197,

при

X 3

=

6,

^з(7)

+

fa,

(3)

=

120 + 75 = 195,

при x3

=

5,

S

<b(4)

+

f j

(4)

=

95 + 99 = 194,

при

X 3

=

4,

9-3 (3>

+

f

(5)

=

72 +121

=

193,

при x3

«

3,

lj,3(2>

f

^

(ь)

=

47

+145

=

192,

при x3 = 2,

І Ь Ш

*

vf?

(7)

=

22

+Ib8 =

190,

цри Xj в I ,

jj(Q)

+

f 2

(8)

=

28

*I92

=

220,

при х^ =

0.