Этап 1. Х1Оптимальное решение 35−514 566 255 662 656 643 361 931 264
Этап 2. Х2Оптимальное решение64+5=9—9174+6=105+5=10−101,284+6=105+6=118+5=13 133
Этап 3. Х3Оптимальное решение80+13=133+9=12—131Максимальный доход от инвестиций в объеме 8 млн.
руб. составит 13 млн.
руб. оптимальное решение можно найти непосредственно из таблицы. Причем сначала рассматривается третья таблица (полученная на этапе 3), затем на этапах 2 и 1. В нашей задаче оптимальным решением является следующее сочетание проектов: {1,3,1}.Таким образом, на первом этапе мы расширяем первое предприятие, вкладывая в него 3 млн.
руб., на втором этапе — второе предприятие, вкладывая в него 5 млн.
руб. На третьем этапе принимаем к третьему предприятию первый проект с нулевыми затратами, т. е. отказываемся от расширения предприятия. Задача 2. Задача календарного планирования трудовых ресурсов
Решите задачу календарного планирования трудовых ресурсов при следующих данных:
Предприниматель составляет план регулирования численности рабочих на каждую из пяти недель. Он располагает сведениями о минимальном количестве рабочих, которое требуется для проведения работ на каждой неделе. Наем или увольнение, а также простой рабочих связаны с накладными расходами, величины которых известны. Пусть1. — количество рабочих имеющихся в наличии на j-й неделе;
2. — величина убытков, связанных СС тем, что превышает заданное значение ;3. — величина накладных расходов по найму новых рабочих. Необходимо определить, сколько рабочих следует нанимать или увольнять еженедельно, чтобы обеспечить минимум суммарных затрат для планируемого периода. Исходное количество рабочих к началу первой недели составляет. Обозначим через минимальную величину расходов, осуществляемых в течении недель 1,2,…, j при заданном значении. Тогда рекуррентное уравнение записывается в виде:
Определим границы для значений переменных. Так как в нашей задаче уравнение не требует накладных расходов, то достаточно рассмотреть следующие ситуации:.Пусть .Этап 1. ()Х1Оптимальное решение60+4+3*1=77 182*2+4+3*3=17 173
Этап 2. ()Х2 Оптимальное решение 5 0+2+1*(-1)+7=8 0+2+1*(-3)+17=16 8 -16 2*1+2+1*0+7=11 2*1+2+1*(-2)+17=19 11 08 2*3+4+3*2+7=23 2*3+2+1*0+17=25 23 2Этап 3. ()Х3 Оптимальное решение 3 0+2+1*(-2)+8=8 0+2+1*(-3)+11==10 0+2+1*(-5)+23=20 8 -25 2*2+2+1*0+8=14 2*2+2+1*(-1)+ +11=16 2*2+2+1*(-3)+ +23=26 14 06 2*3+4+3*1+8=21 2*3+2+1*0+11==19 2*3+2+1*(-2)+ +23=29 19 08 2*5+4+3*3+8=31 2*5+4+3*2+11=31 2*5+2+1*0+23=35 31 3,2Этап 4. ()Х4 Оптимальное решение 6 0+4+3*3+8=21 0+4+3*1+14=21 0+2+1*0+19=21 0+2+1*(-2)+31=31 21 3,1,08 2*2+4+3*5+8=23 2*2+4+3*3+14=31 2*2+4+3*2+19=33 2*2+2+1*0+31=37 23 5Этап 5. ()Х5 Оптимальное решение 8 0+4+3*2+21=31 0+2+1*0+23=25 25 0Так как, то
НеделяРешение166Никого не нанимать и не увольнять255Никого не нанимать и не увольнять333Никого не нанимать и не увольнять468Уволить двух рабочих588Никого не нанимать и не увольнять
Задача 3. Задача о замене оборудования
Одной из важных задач менеджмента машиностроительного предприятия является определение оптимальной стратегии в замене старого оборудования на новое. В процессе эксплуатации оборудования наступает момент, когда старое оборудование выгоднее заменить новым, чем эксплуатировать дальше. Критерием оптимальности может служить прибыль от эксплуатации оборудования. Будем считать, что решения о замене оборудования принимаются периодически в начале каждого промежутка времени, на которое разбит планируемый период. Основной характеристикой оборудования будем считать его возраст, та как от возраста зависит производительность, затраты на эксплуатацию и т. д.В начале каждого промежутка времени принимается решение либо о сохранении оборудования, либо о его замене, поэтому управление на j-м шаге:
Где — решение о сохранении оборудования;
о замене оборудования. Решите задачуо замене оборудования при следующих данных:
Показатель
Время, в течении которого используется оборудование1 234
Годовой выпуск продукции R (Xj-1), млн.
руб.9 085 756 560
Ежегодные затраты на ремонт и содержание оборудования Z (Xj-1), млн.
руб.2 530 354 045
Предположим, что на предприятии установлено новое оборудование. Зависимость производительности оборудования от времени его использования, а также зависимость затрат на содержание и ремонт оборудования от времени работы приведены выше в таблице. Затраты, связанные с приобретением и установкой нового оборудования, составляют C=40 млн.
руб., а заменяемое оборудование списывается. Необходимо составить такой план замены оборудования, при котором общая прибыль за рассматриваемый период (5 лет) — максимальная. Обозначим через — возраст оборудования в начале j-го года. Тогда Обозначим через — максимальную прибыль, полученную предприятием в течении j, j+1,…5 лет при заданном значении. Тогда рекуррентное соотношение для обратной вычислительной системы запишется в следующем виде:
1.Для j=1,2,3,4.
2.Для j=1,2,3,4.Этап 5. Следовательно, .Следовательно, .Следовательно, .Следовательно, .Возраст оборудования 155 240 325, 425Этап 4. Следовательно, .Следовательно, .Следовательно,.Возраст оборудования 195 280 380
Этап 3. Следовательно, .Следовательно, .Возраст оборудования 11 352 120, Этап 2. Следовательно, .Возраст оборудования 1175
Этап 1. Следовательно, .Таким образом, максимальная прибыль предприятия составит 240 млн руб. В задаче возможны два решения:
Список литературы
Акулич И. Л. Глава 4. Задачи динамического программирования // Математическое программирование в примерах и задачах. — М.: Высшая школа, 1986. —
319 с. Беллман Р. Динамическое программирование. — М.: Изд-во иностранной литературы, 1960. — 462с. Габасов Р., Кириллова Ф.
М. Основы динамического программирования. — Мн.: Изд-во БГУ, 1975.
— 262 с. Кормен, Т., Лейзерсон, Ч., Ривест, Р., Штайн, К. Глава 15. Динамическое программирование // Алгоритмы: построение и анализ = Introduction to Algorithms / Под ред. И. В. Красикова.
— 2-е изд. — М.: Вильямс
Мищенко А.В., Попов А. А. Некоторые подходы к оптимизации инвестиционного портфеля, «Менеджмент в России и за рубежом», № 2 / 2002
Щербина О. А. О несериальной модификации локального алгоритма декомпозиции задач дискретной оптимизации // Динамические системы, 2005, вып. 19., 2005. — 1296 с. Щербина О. А.
Методологические аспекты динамического программирования // Динамические системы, 2007, вып. 22. — c.21−36.
