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

Таблица

13.3

Виды

{

Цена единицы

Вес единиНЕ

грузов

1

груза і,

-го

груза ; -го

1.

вида

вида

I

!

I

!

*

"

2

t

в

3

і

i

-

5

j

Î8

4

1

4

1

26

5

Решение будем записывать в таблице

(13» 4). Для заполнения

строк

и

(х^ )

используем формулы

г.-« p^j

И

Q . ( X ; ) » С; X ,

*

С; [ Ж ]

'

? І

Ь

»•

"

t

К Pj,j

Для решения задача используем рекуррентное соотношение (D . I3) .

Если загружать судно только предметами первого типа, та

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

максимальная стоимость груза

при ѵѴ = 12, межes

быть равна 48 денежным единицам.

При загрузке

судна предметами только первых двух типов шшЗояь-

п а

ценность груза будег:

-

213

-

аналогично вычисляются

\-zW>

f., ( У , . . . .

fÄ

(12). Таким

образом, при загрузке

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

наибольшая ценность их при ѵѴ = 12 составляет 52

ден.ед.,при

Г

12 -

3.4 1

п

^

"

г

I

î

Г

°-

На следующем этапе определяем оптимальную стратегию в случае

загрузки

судна

предметами

только первых

трех

видов

по рекуррент­

ной формуле:

(13.14) f 5 fW) - ;5f4 Ä 1

- Ъ

Ы-Ъх2)}

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

|\(ѵѵ) и *з

таблицы (13.4). При этом

| 3

(12) =

54

ден . ед . ,

при x-j = 3, %2 - О и Xj = 0.

Затем приступаем к выполнению вычислений

(13.15)

f„

{^Ч

* U («•

Pi X ' ) }

и

заполняются

сяроки

|(

(ѵѵ)

и х^ таблицы

( D . 4 ) .

Таким образом; задача

решена. Наибольшая

ценность груза

(12) = ьО при х^ = 2.

Для двух

предметов

четвертого вида

потре­

буется

водоизмещение

2 .

5 = 1С весовых

единиц. Оставшееся

водо­

измещение

12-10 = 2 аес.ед. мы должны использовать

для загрузки

предметами остальных

видов. По таблице (13.4)

для W = 2 находим,

что

(2)

= 8,

при Xj = 0,

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

при оптимальной

стратегии

в данной

задаче

предметы третьего

вида

на судно

загру­

жать нельзя. Далее находим, что fi(2) = 8,

при х-> = 0,а

f,

(2)=8,

при Xj s

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

ври оптимальной

стратегии

Хр= 2,

х 2 =0,

х 3

= 0 и х^ = 2,. то есть

судно

нужно загрузить двумя

предметами

первого

вида

и Дд.умя

предметами четвертого

вида. При этом ценность

загруженных предметов

4 . 2

+ 2 ь .

2 = ьО ден.ед.

Оптимальная

стратегия

при W= 12 отмечена

в таблице

(13.4) кружочками.

Решение,

приведенное

в таблице

(13.4),

позволяет

определять

- 214 -

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

и в тех случаях, когда

грузоподъемность ко­

рабля будет составлять не только 12,

но и I I , 10, 9, . . .

весовых

единиц.

Например, при w

= 9 из таблицы (13.4)

находим, что

^ (9)=44,

при х^ = I . Вес одного

предмета четвертого вида равен

5 вѳсоьык

единицам. Оставшаяся часть грузоподъемности

9 - Ь = 4 дес.ед. может

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

этой же таблице находим, что

,*•) (4) = 18, при х^ = I . Так как

Pj = 4,

то грузоподъемность использована полностью. Оптимальная

стратегия: х^ = 0, х 2 = О, х^ = I , зц = I .

При W = V находим, что

} ч (7)

= 34 при х^ = I . Тогда

fi (2)

= 8 при Xj = 0, следовательно, нужно

находить

fi (2).

По таблице (13.4) значение

(2) = -8, при

= 0.

Тогда

нахо­

дим

(2), при этом Xj _ 2.

В этом

случае

оптимальная

стратегия

Xj = 2,

= 0, х 3 = 0 и х-4 = I .

Аналогично определяется

оптимальная стратегия

при любом до­

пустимом значении W .

Б тех случаях, когда значение w

достаточно

велико, пользо­

ением допустимых

значений

грузоподъемности w

на ряд отрезков,

в которых

fj. (w)

= c û n i t

. Методику решения

задач таким спосо­

бом рассмотрим на следующем примере.

Пример

2.

Пусть

водоизмещение судна w = .4? весовым

единицам. Данные

о ьидах грузов,цене и весе

единицы груза приведены ь таблице

(ІЗ . Ь) .