Исследование операций. Линейное, динамическое программирование



         

Исследование операций - часть 85


Значит, па каждом шаге у пас всего два управления, а это очень приятно.

А чем мы будем характеризовать состояние системы S перед очередным шагом? Очевидно, весом S, который еще остался в нашем распоряжении до конца (полной загрузки машины) после того, как предыдущие шаги выполнены (какие-то предметы погружены в машину). Для каждого из значений S мы должны найти Wi (S) — суммарную максимальную стоимость предметов, которыми можно «догрузить» машину при данном значении S,

и положить xi (S) = 1, если мы данный (i-й) предмет берем в машину, и xi (S) = 0,если не берем. Затем эти условные рекомендация должны быть прочтены, и дело с концом!

Решим до конца конкретный числовой пример: имеется шесть предметов, веса и стоимости которых указаны в таблице 13.4.

Таблица 13.4

Предмет Пi

П1

П2

П3

П4

П5

П6

Вес qi

4

7

11

12

16

20

Стоимость ci

7

10

15

20

27

34

Суммарная грузоподъемность машины Q == 35 единиц веса. Требуется указать номера предметов, которые нужно включить в груз, чтобы их суммарная стоимость была максимальна1).

Как и ранее, будем придавать S только целые значения. Условная оптимизация решения показана в таблице 13.5, где в каждой строке для соответствующего номера шага (номера предмета) приведены: условное оптимальное управление xi (0 или 1) и условный оптимальный выигрыш Wi (стоимость всех оставшихся до конца предметов при оптимальном управлении, но всех шагах). Как эта таблица составляется, мы уже объяснять не будем — тут полная аналогия с предыдущей задачей, с той разницей, что возможные управления только 0 или 1.

В таблице 13.5 выделены: оптимальный выигрыш W* = 57 и оптимальные шаговые управления, при которых этот выигрыш достигается:

т. е. загрузить машину надо предметами 2, 4 и 5, суммарный вес которых равен в точности 35 (вообще это необязательно; при оптимальном выборе грузов может быть и некоторый общий «недогруз»).

Заметим, что в нашем элементарном примере, возможно, было бы проще искать решение «простым перебором»), пробуя все возможные комбинации предметов, проверяя на каждой из них, «влезают» ли они в заданный вес, и выбирая ту, для которой стоимость максимальна.


Содержание  Назад  Вперед