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

- 215 -

Таблица

13.5

t

Ьиды

î

Цена

единицы

j

Вес единицы

грузо*,

!

груза -

с.

і

груза

- р ,

І

I

23

i

10

1

2

32

j

14

3V

J

Іъ

1

3

Из рекуррентной

формула

(13.13)

лидно,

что для вычисления

fui*') ВДзюо иметь

^(vv - ji,

x,.J

> поэтому

будем находить после­

довательно

значения

£ (w), f^(w)

'•J f3 (w)

Для нахождения

максимальной стоимости

груза,

если

вся грузопсд-

емность

w

(0 ^

w

s

4?) расходуется только на перевоаку

предметов

первого типа,

то есть

f,

(w j

,

находим

Составляем

таблицу(ІЗ.ь)

для значений

|>ДѵѴ) при Xj = 0,1,2,3,4.

ность может использоваться ь следующих замкнутых

промежутках

0 - 9, 10 - 19, 20 - 29,

30 - 29, 40 - 47.

Таблица 13,ь

!

о -

9

с

0

!

ю -

19

23

I

J

20 -

29

4Ь

2

j

3 0 -

39

о9

3

{

40 -

47

92

4

Далее

находим f* (w) по формуле

' Л 2 >

f.. j » : m их

У j

С х 2 ) , f,

^ / - ; \ X,) J

° - Л 2 -

— I »•

'

J

-

216

-

где <jz

(хг)

= с ^ г .

Находки

пии

х^[~Ѵг\=

3'

1

0

е с І

Ь

» для рассматриваемого примера

х^

=

0,1,2»3.

Используя

значения

при

0 £

W -È

47, записанные в

іаблице(ІЗ.б),

приступаем

к заполнению

таблицы

(13.7),

определяя

оптимальную

стратегию

при загрузке

судна

предметами

только первы

дь-ух видов. В этом случае грузоподьемность разбивается

на отрезке

(0-9, 10-13,

14-19,

20-23,

24-27, 28-29,

30-33, 34-37,

38-39,

40-41, 42-43, 44-47), в которых fa (w)

принимает

одни

и те же

численные

значения. Для каждого из этих

отрезков

находим суммы

С 2Х 2 +

Ь

^w

-»2^2)

П Р К в с е

х

допустимых

целочисленных значе­

ниях

Наибольшее значение, so есть f2 (wj,

для каждого из рассматривае-

мых отрезков

заносим л таблицу

(13.7).

Таблица

13.7

W

{

/ 2 ( w j

j

х 2

0-9

i

0

0

10-13

23

І

0

14-19

32

I

20-23

4b

о

1

24-27

55

I

28-29

Ь4

2

30-33

69

0

34-37

78

I

38-39

87

j

2

40-41

92

0

42-43

96

3

44-47

101

I

Для рассматриваемого примера рекуррентное соотношение (13.12)

примет вид: f 2

W r

w o x ^

| 3 2

X

t +

j»

J

,

При значениях

0

£

w

£

Э

max х 2 =4Ï4~] =

°*

П 0 Э І 0 1 , у

f 2 (9)

= 3

2

• 0

+ f

i

(9 -

14 .

0)

»

0,

при атом

= С. Значения

-

217 -

(, (9) и X j , равные

нулю,

находим

из таблицы

(13.6)

При значениях

ІО =• w

в

m<.i*x2

= [ р ~ | -

0,

поэтому

j \ z (I3)

= 32

. О *

f,

(13 - 14 . О ) =

fi (13) = 23, при этом

х 2 = О. Значения

f,

(13)

= 23 и x-j- = I

находим

также из

таб­

лицы

(13. ь).

(191

При значениях 14 S ѵѴ -а 19

гшдх2

=vj% = I , to

есть x-2 может

принимать

значения

0 и I . Вычисляем

f„ (19)

при допустимых

значениях

х 2

:

I

32.0 +

(19-14*0)

=0

+

f,

(19) =

0 + 23,при х 2

= О,

I

32 Л +

(I9 - I4 . I)

=32

+

f,

(5)

= 32 +

0 при * 2

= I .

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

fA

(19)

= 32,

при х 2

= I

и X j = 0.

При значениях 20 é

w

-

23

гпилХ2 =

j| Ц |

= I , то есть

х 2 может принимать

значения

0 и I . Вычисляем

f., (23; при допус­

тимых

значениях

х 2 :

!

32.0 +

jl. (23-14.0)

= 0 +

f,

(23) = О + 46 =

4ь,при

Х£

= О,

[

31.1 +

(23-I4.I)

=32 +

f,

(9)

=32 +

0 = 32,при

х 2

= I .

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

(23)

= 46,

при х ? = 0 и Xj- = 2.

Вычисляя аналогично

значения

f2 (w;

в остальных промежутках

и заполняя

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

строки

таблицы

(13.7),

находим и

fz(V7):

при 44 ^

\Ѵ

47

maxx 2

=

= 5 » 5 0

e c

ï b

х 2

=

0,1,2,3.

32'0 •+ } t

(47-14*0) = 0+1;

(47)

= О + 92 = 92,

при Х 2

= О,

<

32*1 *

f.

(47-14*I) =32 t (,

(33)

=32 + Ь9 =101,

при Х£

= I ,

32*2 +

f,

(47-14*2)

=fc>4 + f,

(19)

=64 + 23 = 87, при х 2

= 2,

32*3

t

(t, (47-14.3)

=9b + f,(

5)

=9b +

0 = 96,

при x 2

= 3.

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

fa

(47) = 101 при x 2

=

I и Xj = 3.

Таким

образом,

оптимальная

стратегия

при загрузке судна пред­

метами только

первых Двух типов: Xj = з и х^ = I . Действительно,

при х-, = I , на долю предметов первого

типа остается грузоподъем­

ность, равная 33 вес.ед.(47-14*1)-Из

таблицы

( В , ь )

fj (33)

= Ь9

при X j = 3.

- 218 -

Переходим к отысканию оптимальной стратегии при загрузке

судна

предметами трех видов по рекуррентному соотношению:

( 13. 14)

^ (vv)

= ^ m eu ( | 9 . ( N ) r}z{«-

К x,) j

,

где

| 3 { Х з ) =

c 3 x 3 .

При заполнении корабля предметами всех трех ^идов грузоподь-

емноегь разбивается на отрезки (0-9, 10-13, 14-15,

Іь-І9,

20-23,

24-25,'2b-2Y, 28-29, 30-31, 32-33,

34-35, Зь-ЗѴ,

38-39,

4 0 - « ,

42-43, 44-45, 4ь-4У), и которых

iwj

принимает

одни и

те же

численные значения. Для каждого из зтих

отрезков

находим суммы

с3*3 *

С ^

~ Рзх 3^ п р

и " с

е х

Д°п Ус г имых целочислен­

ных значениях i L . Наибольшее значение,

то есть f-) (w;

, для каж­

дого

из рассматриваемых

отрезков заносим

и таблицу(13.8)

Таблица 13.8

W

h M

*3

!

0-9

0

0

i

10-13

23

0

i

н

14-15

32

0

•f

Ib-I9

37

I

1

1

20-23

4b

0

-

і

!

24-25

55

0

1

2b-27

60

I

1

28-29

64

0

]

i

30-31

b9

I1• •

,

I

i

32-33

74

2

1

34-35

78

!

0

!

Зь-ЗУ

83

i

1

38-39

87

0

40-41

92

i

ï

42-43

97

2

44-45

101

1

0

1 4ь-4Ѵ

IOb

2 или I

Для рассматриваемого примера рекуррентное соотношение (13.14)

примет вид: ІЛЫ)-

шох^ J3 ?X 3 - t -

f - (W - І С л 3 ) | >

Так, например, при 4ь ^ w « 47

ци.».х3 = | - j £ ~|= 2 ' 10

есгь

х 3 = 0,1,2.

Вычисляем

(47) при допусгимых

значениях х 3 :

[37'0 1-

?й (47-ІЬ'О)

= 0 + h (47)

= О + ІОІ = ІОІ.при Х3 = О,

І З Ѵ І

+

^ ( 4 7 - І ь * І )

=ЗУ + f 2 (3I)

=37 +

ь9 = ІОЬ.при х3 = I ,

[37.2 +

^ ( 4 7 - І Ь ' 2 )

=74 + ^(15)

= 74+

32 = 106,при

х3 = 2.

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

(47) = 106 либо при х 3 = J , либо при х 3

= 2.

Таким образом, в рассматриваемом

примере допустимы Две опти­

мальные стратегии:

а)

(Xj; Х 2 ; Х 3 ) =

( 3 ; 0 ; І ) ,

б)

( X j ; х 2 ; х 3 ) = (0*1,2).