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



         

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


в третье предприятие заполняется по столбцу (

 таблицы 13.1). В четвертом столбце — оптимальный выигрыш на всех оставшихся шагах (четвертом и пятом) при условии, что мы подошли к четвертому шагу с оставшимися средствами (заполняется по столбцу i •= 4 таблицы 13.2). В пятом столбце — сумма двух выигрышей: шагового и оптимизированного дальнейшего при данном вложении х в третий шаг.

Из всех выигрышей последнего столбца выбирается максимальный (в таблице 13.3 он равен W3(7) = 3,6, а соответствующее управление х(7) = 2).

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

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

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

 Q) была максимальна?

Нетрудно заметить, что эта задача, в сущности, ничем не отличается от предыдущей (распределение ресурсов между п

предприятиями), но несколько проще со. В самом деле, процесс загрузки машины можно представлять себе как состоящий из п

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


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