3. Задача о загрузке машины.

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

В качестве примера рассмотрим задачу о загрузке машины (мы уже упоминали о ней в предыдущей главе): имеется определенный набор предметов (каждый в единственном экземпляре); известны их веса и стоимости . Грузоподъемность машины равна Q. Спрашивается, какие из предметов нужно взять в машину, чтобы их суммарная стоимость (при суммарном весе Q) была максимальна?

Нетрудно заметить, что эта задача, в сущности, ничем не отличается от предыдущей (распределение ресурсов между предприятиями), но несколько проще ее. В самом деле, процесс загрузки машины можно представлять себе как состоящий из шагов; на каждом шаге мы отвечаем на вопрос: брать данный предмет в машину или не брать? Управление на i-м шаге равно единице, если мы данный предмет берем, и нулю — если не берем. Значит, на каждом шаге у нас всего два управления, а это очень приятно.

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

Затем эти условные рекомендации должны быть прочтены, дело с концом!

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

Таблица 13.4

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

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

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

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

Но при большом числе предметов это было бы затруднительно: число комбинаций неумеренно растет при увеличении числа предметов. Для метода же динамического программирования увеличение числа шагов не страшно: оно только приводит к пропорциональному возрастанию объема расчетов.

Таблица 13.5