Примеры задач динамического программирования

из "Математические исследования операций в экономике "

Отдельно отметим, что данные вычислительные схемы, вообще говоря, достаточно часто используются для решения некоторых задач, которые уже были затронуты в других главах. Это, прежде всего, задача о ранце, задача о кратчайшем пути, задачи транспортного типа. [c.170]
Одним из важнейших классов задач, для которых применение динамического программирования оказывается плодотворным, являются задачи последовательного принятия решений. Их особенностью является то, что искомые переменные J P J 2. xk. должны определяться в строгой временной последовательности и не должны меняться местами. В качестве примера опишем так называемую задачу о найме работников (задачу об использовании рабочей силы). [c.170]
На основе сформулированной модели ставится задача минимизации целевой функции (издержек) (5.15). Добавим, что постановка задачи не будет корректной, если не задать начальное условие на количество работников. Существуют две модификации данной задачи, определяемые типом начального условия в первом случае задается исходное значение на первом этапе щ, а во втором — требуемое количество в я-м периоде тп. [c.171]
В заключение, как и в первом случае, подсчитывается минимальная величина издержек. [c.173]
Требуется найти оптимальные значения приращений численности работающих в конце каждого из первых трех месяцев, при которых суммарные издержки за весь рассматриваемый период будут минимальными. [c.173]
результаты расчета свидетельствуют, что при заданной системе расценок в третьем месяце выгоднее не брать 5-го работника, а компенсировать его отсутствие дополнительными выплатами за сверхурочную работу имеющимся сотрудникам. [c.178]
Особый интерес представляет частный случай задачи (5.24)-(5.25), при котором предполагается, что функции затрат на пополнение запаса k(xk) являются вогнутыми по xk, a функции затрат на хранение sk( k) являются линейными относительно объема хранимого запаса, т. е. sk( )k) = sk )k. Параллельно заметим, что обе предпосылки являются достаточно реалистичными. [c.181]
При дальнейших конкретизирующих предположениях о виде функций fk(xk, yk+l) можно получить еще более компактные формы для рекуррентных соотношений. Однако эти вопросы носят достаточно частный характер, и мы их рассматривать не будем. Отметим лишь, что приведенные в данном пункте преобразования неплохо иллюстрируют общие подходы, применяемые в динамическом программировании, а также те свойства задач, которые открывают возможности для эффективного и плодотворного использования соответствующих методов. [c.183]

Вернуться к основной статье