Динамическое программирование
Волго-Вятская академия государственной службы
Кафедра «Системного анализа и математики»
Разработка управленческих решений
Методические указания к решению типовых задач
Нижний Новгород 2003г.
УДК 519.95
Ломакина Л.С., Прохорова Е.С. Разработка управленческих решений. Методические указания к решению типовых задач: Учебное пособие. – Нижний Новгород, Издательство Волго-Вятской академии государственной службы, 2003. -
Учебное пособие рассчитано на студентов, обучающихся по специальностям управленческого профиля («Государственное и муниципальное управление», «Менеджмент» и т.п.) всех форм обучения. В то же время оно может представлять определённый интерес для научных и инженерно-технических работников, управленцев и аспирантов, занимающихся вопросами разработки, принятия и реализации решений.
Волго-Вятская академия
государственной службы, 2003г.
Содержание
Введение…………………………………………………………………………...4
1. Принятие решений в условиях полной определённости
1.1. Линейное программирование………………………………………………..5
1.2. Транспортная задача…………………………………………………………7
1.3. Задача о назначениях……………………………………………………….11
1.4. Динамическое программирование…………………………………………12
1.5. Управление запасами……………………………………………………….15
|
|
|
2. Принятие решений в условиях неопределённости
2.1. Принятие решений в условиях неопределённости и риска………………17
2.2. Теория игр…………………………………………………………………...19
3. Планирование и прогнозирование
3.1. Сетевое планирование………………………………………………………22
3.2. Прогнозирование……………………………………………………………25
Приложение………………………………………………………………………27
Список литературы………………………………………………………………36
Введение
Как принять наилучшее решение в реальных условиях? Как получить практические рекомендации в целом ряде случаев, когда наши желания вступают в борьбу с нашими возможностями…? Но снова формулы, уравнения, функции? Не проще ли действовать так, как это делает основная масса людей, считая, что решая задачу, всегда полезно знать ответ? Известен и другой путь – если есть способ отложить принятие решения, то почему им не воспользоваться?
Но уже настала пора принимать обоснованные решения и критически анализировать всевозможные обещания.
Предупреждение. Закон Мерфи гласит: «Если четко ставится цель исследования и выделяется конкретная сумма денег, то нельзя предусмотреть, когда эта цель будет достигнута».
|
|
|
Об остальном читайте в этом пособие.
Принятие решений в условиях полной определённости
Линейное программирование
Линейное программирование – наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.
Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
Оптимальным решением задачи линейного программирования называется решение системы ограничений, удовлетворяющее условию, при котором целевая функция принимает оптимальное (максимальное или минимальное) значение.
К основным задачам линейного программирования относятся:
· задача об использовании ресурсов (задача планирования производства),
· задача составления рациона (задача о диете, задача о смесях),
· задача об использовании мощностей (задача о загрузке оборудования),
· задача о раскрое материалов,
· транспортная задача и т.д.
Задача. Для производства двух видов изделий А и В предприятие использует три вида сырья (I,II,III). Условия задачи приведены в таблице. Необходимо составить такой план выпуска продукции, при котором прибыль предприятия от реализации продукции будет максимальной.
|
|
|
| Вид сырья | Нормы расхода сырья на 1 изделие (кг) | Общее количество сырья (кг) | |
| А | В | ||
| I | 12 | 4 | 300 |
| II | 4 | 4 | 120 |
| III | 3 | 12 | 252 |
| Прибыль от 1 изделия (д.ед.) | 30 | 40 | |
Решение:
1.Составим экономико-математическую модель задачи.
Обозначим: x 1 – число единиц изделий вида А, планируемых к производству;
x 2 – число единиц изделий вида В, планируемых к производству.
Тогда, система ограничений на использование сырья имеет следующий вид:
Целевая функция:
2. Построим многоугольник допустимых решений.
OABCD – область допустимых решений. Строим вектор n(30;40) и перпендикулярную ему линию уровня F=0. Перемещаем линию уровня по направлению вектора n и находим последнюю точку касания линии уровня с областью допустимых решений. Из графика видно, что такой точкой является точка B, найдём её координаты:
Решая систему получаем координаты точки B(12; 18), в которой и будет оптимальное решение, т.е.:
при этом
Ответ: Таким образом, предприятие должно выпускать 12 изделий вида А и 18 изделий вида В, при этом прибыль предприятия от реализации продукции будет максимальной и составит 1080 д.ед.
|
|
|
Транспортная задача
Транспортная задача – одна из распространенных задач линейного программирования. Её цель – разработка наиболее рациональных путей и способов транспортирования товаров, устранение чрезмерно дальних, встречных, повторных перевозок. Всё это сокращает время продвижения товаров, уменьшает затраты предприятий, фирм, связанные с осуществлением процессов снабжения сырьём, материалами, топливом, оборудованием и т.д.
Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. К таким задачам относятся следующие:
· оптимальное закрепление за станками операций по обработке деталей. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей.
· оптимальные назначения, или проблема выбора. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности.
· задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции
· увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега.
Задача. Пусть имеется 3 поставщика и 4 потребителя. Запасы продукта у поставщиков, спрос потребителей и транспортные расходы на доставку единицы продукта от i-го поставщика к j-му потребителю заданы в таблице.
| Поставщик | Потребитель | Запас | |||
| 1 | 2 | 3 | 4 | ||
| 1 | 3 | 5 | 6 | 2 | 170 |
| 2 | 6 | 4 | 7 | 5 | 250 |
| 3 | 5 | 4 | 6 | 5 | 180 |
| Спрос | 150 | 230 | 160 | 60 | |
Требуется составить такой план перевозки, чтобы обеспечить минимум общей суммы транспортных расходов.
Решение:
Обозначим 
- количество продукта, доставляемого от i-го поставщика к j-му потребителю. Тогда модель имеет следующий вид:
Определим начальный план перевозок с помощью метода северо-западного угла, по которому транспортная матрица заполняется слева - направо и сверху – вниз.
Мы должны заполнить m+n-1 клеток, где m – число поставщиков, а n – число потребителей. Если число заполненных клеток меньше m+n-1, то недостающие клетки выбираются произвольно и заполняются нулями.
| Поставщик | Потребитель | Запас | ||||||||
| 1 | 2 | 3 | 4 | |||||||
|
|
|
|
| |||||||
| 1 |
| 3 | 5 | 6 | 2 | 170 | ||||
| 150 | 20 | |||||||||
| 2 |
| 6 | 4 | 7 | 5 | 250 | ||||
| 210 | 40 | |||||||||
| 3 |
| 5 | 4 | 6 | 5 | 180 | ||||
| 120 | 60 | |||||||||
| Спрос | 150 | 230 | 160 | 60 | ||||||
(ден. ед.) – общая сумма транспортных расходов.
Рассчитаем потенциалы на основе равенства:
Присвоим первому поставщику потенциал равный нулю. Значения потенциалов заносим в таблицу.
Проверим первоначальный план на оптимальность. План считается оптимальным, если для всех свободных клеток выполняется условие:
Осуществляем проверку:
Условие оптимальности не выполняется. Для улучшения плана необходимо переместить перевозку в клетку, где условие оптимальности нарушено больше всего, т.е. разность 
максимальна. Такой клеткой является клетка (1;4).
Перемещение производится так, чтобы по отношению к выбранной клетке образовать связку. Для этого необходимо провести замкнутую ломаную линию, состоящую из горизонтальных и вертикальных линий, в которой одной из вершин полученного многоугольника является свободная клетка, а в остальных вершинах должны находиться занятые клетки. Далее каждой клетке в связке поочередно присваиваются знаки плюс и минус, начиная со свободной. Из клеток со знаком минус перемещаем перевозки в клетки со знаком плюс. Чтобы не получить отрицательных перевозок, перемещаем наименьшее количество продукта, которое находится в клетках связки со знаком минус.
Последовательное улучшение плана представлено в таблицах.
| Поставщик | Потребитель | Запас | ||||||||
| 1 | 2 | 3 | 4 | |||||||
|
|
|
|
| |||||||
| 1 |
| 3 | 5 | 6 | 2 | 170 | ||||
| 150 | 20 | |||||||||
| 2 |
| 6 | 4 | 7 | 5 | 250 | ||||
| 230 | 20 | |||||||||
| 3 |
| 5 | 4 | 6 | 5 | 180 | ||||
| 140 | 40 | |||||||||
| Спрос | 150 | 230 | 160 | 60 | ||||||
(ден. ед.) – общая сумма транспортных расходов.
| Поставщик | Потребитель | Запас | ||||||||
| 1 | 2 | 3 | 4 | |||||||
|
|
|
|
| |||||||
| 1 |
| 3 | 5 | 6 | 2 | 170 | ||||
| 130 | 40 | |||||||||
| 2 |
| 6 | 4 | 7 | 5 | 250 | ||||
| 20 | 230 | |||||||||
| 3 |
| 5 | 4 | 6 | 5 | 180 | ||||
| 160 | 20 | |||||||||
| Спрос | 150 | 230 | 160 | 60 | ||||||
(ден. ед.) – общая сумма транспортных расходов.
| Поставщик | Потребитель | Запас | ||||||||
| 1 | 2 | 3 | 4 | |||||||
|
|
|
|
| |||||||
| 1 |
| 3 | 5 | 6 | 2 | 170 | ||||
| 110 | 60 | |||||||||
| 2 |
| 6 | 4 | 7 | 5 | 250 | ||||
| 20 | 230 | |||||||||
| 3 |
| 5 | 4 | 6 | 5 | 180 | ||||
| 20 | 160 | |||||||||
| Спрос | 150 | 230 | 160 | 60 | ||||||
(ден. ед.) – общая сумма транспортных расходов.
В последней таблице условие оптимальности выполняется для всех свободных клеток. Следовательно, это решение является оптимальным.
Ответ: Оптимальный план содержит шесть перевозок: от первого поставщика – 110 ед. к первому потребителю и 60 ед. к четвёртому; от второго поставщика – 20 ед. к первому и 230 ед. ко второму; от третьего поставщика – 20 ед. к первому и 160 ед. к третьему потребителю. При этом общая сумма транспортных расходов минимальна и составляет 2550 ден. ед.
Задача о назначениях
Задача заключается в выборе такого распределения ресурсов по объектам, при котором минимизируется стоимость назначений или максимизируется прибыль (производительность). Предполагается, что каждый ресурс назначается ровно один раз и каждому объекту приписывается ровно один ресурс.
Возможные применения задачи о назначениях представлены в таблице.
| Ресурсы | Объекты | Критерии эффективности |
| Рабочие | Рабочие места | Время |
| Автомобили | Маршруты | Затраты |
| Станки | Участки | Объем переработанной продукции |
| Экипажи | Рейсы | Время простоя |
| Коммивояжер | Города | Товарооборот |
Задача. У предприятия для выполнения некоторых программ имеется пять инвестиционных проектов. Однако предприятие не может финансировать все проекты: суммы денег, выделенные на текущий год и последующие два, меньше необходимых для инвестирования в полном объёме. При этом оставшиеся денежные средства не могут быть перенесены на следующий годы, также не предусмотрено более одного финансирования одного и того же проекта. Требуется распределить выделенные средства в инвестиционные проекты оптимальным способом.
| № проекта | Чистая приведённая стоимость, ден. ед. | Требуемые вложения, ден. ед. | ||
| 1 год | 2 год | 3 год | ||
| 1 | 40 | 12 | 8 | 17 |
| 2 | 60 | 17 | 17 | 20 |
| 3 | 38 | 10 | 7 | 21 |
| 4 | 50 | 7 | 22 | 6 |
| 5 | 55 | 17 | 14 | 20 |
| Выделенный объём денежных средств для инвестиций | 54 | 62 | 70 | |
Решение:
Обозначим через 
долю вложения в j-й проект, где j=1,2,3,4,5. Тогда чистая приведённая стоимость инвестиций в 1-й проект составит 
, во 2-й проект - 
и т.д. При этом необходимо учитывать, что инвестиции не должны превышать 54, 62 и 70 ден. ед. в первый, второй и третий годы соответственно. Требуется выбрать один или группу проектов с наибольшей совокупной чистой приведённой стоимостью.
Математическая модель этой задачи имеет вид:
при ограничениях:
причем 
или 1, j=1,2,3,4,5 (проект либо финансируется, либо нет).
Решая задачу симплексным методом, получаем 
. При этом потребуются денежные средства в объёме 177 ден. ед., а сумма чистой приведённой стоимости проекта будет максимальной и составит 205 ден.ед.
Ответ: Необходимо производить финансирование 1, 2, 4 и 5-го проектов. При этом потребуются денежные средства в объёме 177 ден. ед. в течение трёх лет (при выделяемом предприятием объёме 186 ден. ед.), а сумма чистой приведённой стоимости проекта будет максимальной и составит 205 ден.ед.
Динамическое программирование
Динамическое программирование – метод оптимизации, в котором процесс принятия решения и управления может быть разбит на отдельные этапы (шаги).
В отличии от линейного программирования, в котором симплексный метод является универсальным методом решения, в динамическом программировании такого универсального метода не существует. Одним из основных методов динамического программирования является метод рекуррентных соотношений, который основывается на использовании принципа оптимальности Беллмана. Принцип состоит в том, что, каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придёт система в конце данного шага. Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
К основным задачам динамического программирования относятся:
· оптимальная стратегия замены оборудования,
· оптимальное распределение ресурсов,
· распределение инвестиций для эффективного использования потенциала предприятия,
· минимизация затрат на строительство и эксплуатацию предприятий,
· нахождение рациональных затрат при строительстве трубопроводов и транспортных артерий и т.д.
Задача. Планируется деятельность четырёх промышленных предприятий на очередной год. Начальные средства: 
усл. ед. Размеры вложения в каждое предприятие кратны 1 усл. ед. Средства x, выделенные k-му предприятию (k=1, 2, 3, 4), приносят в конце года прибыль 
. Функции заданы таблично. Принято считать, что:
· Прибыль не зависит от вложения средств в другие предприятия;
· прибыль от каждого предприятия выражается в одних условных единицах;
· суммарная прибыль равна сумме прибылей, полученных от каждого предприятия.
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была максимальной.
| X | 
| 
| 
| 
|
| 1 | 8 | 6 | 3 | 4 |
| 2 | 10 | 9 | 4 | 6 |
| 3 | 11 | 11 | 7 | 8 |
| 4 | 12 | 13 | 11 | 13 |
| 5 | 18 | 15 | 18 | 16 |
Решение:
Обозначим через 
количество средств, выделенных k-му предприятию. Тогда суммарная прибыль равна:
Переменные x удовлетворяют ограничениям:
Процесс распределения средств рассматриваем как 4-шаговый, номер шага совпадает с номером предприятия. Уравнения состояний в данной задаче имеют вид:
где 
- параметр состояния – количество средств, оставшихся после k-го шага, т.е. средства, которые остается распределить между оставшимися 4-k предприятиями.
Введем в рассмотрение функцию 
- условную оптимальную прибыль, полученную от k–го, (k+1)-го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства 
. Допустимые управления на k-м шаге удовлетворяют условию: 
(либо k-му предприятию ничего не выделяем, 
, либо не больше того, что имеем к k-му шагу, 
).
Уравнения Беллмана имеют вид:
Последовательно решаем записанные уравнения, проводя условную оптимизацию каждого шага. Результаты представим в таблице:
| K=3 | k=2 | k=1 | |||||||||
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
| 
|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 0+4=4 | 4 | 0 | 0+4=4 | 0+6=6 | ||||
| 1 | 0 | 3+0=3 | 6+0=6 | 6 | 1 | 8+0=8 | 8 | 1 | |||
| 2 | 0 | 2 | 0+6=6 | 0+7=7 | 0+10=10 | ||||||
| 1 | 1 | 3+4=7 | 7 | 1 | 6+4=10 | 10 | 1 | 8+6=14 | 14 | 1 | |
| 2 | 0 | 4+0=4 | 9+0=9 | 10+0=10 | |||||||
| 3 | 0 | 3 | 0+8=8 | 0+9=9 | 0+13=13 | ||||||
| 1 | 2 | 3+6=9 | 9 | 1 | 6+7=13 | 13 | 1 | 8+10=18 | 18 | 1 | |
| 2 | 1 | 4+4=8 | 9+4=13 | 2 | 10+6=16 | ||||||
| 3 | 0 | 7+0=7 | 11+0=11 | 11+0=11 | |||||||
| 4 | 0 | 4 | 0+13=13 | 13 | 0 | 0+13=13 | 0+16=16 | ||||
| 1 | 3 | 3+8=11 | 6+9=15 | 8+13=21 | |||||||
| 2 | 2 | 4+6=10 | 9+7=16 | 16 | 2 | 10+10=20 | 20 | 2 | |||
| 3 | 1 | 7+4=11 | 11+4=15 | 11+6=17 | |||||||
| 4 | 0 | 11+0=11 | 13+0=13 | 12+0=12 | |||||||
| 5 | 0 | 5 | 0+16=16 | 0+18=18 | 0+19=19 | ||||||
| 1 | 4 | 3+13=16 | 6+13=19 | 19 | 1 | 8+16=24 | 24 | 1 | |||
| 2 | 3 | 4+8=12 | 9+9=18 | 10+13=23 | |||||||
| 3 | 2 | 7+6=13 | 11+7=18 | 11+10=21 | |||||||
| 4 | 1 | 11+4=15 | 13+4=17 | 12+6=18 | |||||||
| 5 | 0 | 18+0=18 | 18 | 5 | 15+0=15 | 18+0=18 | |||||
Ответ: Максимум суммарной прибыли равен 24 усл. ед. средств при условии, что 1-му предприятию выделено 1 усл. ед.; 2-му предприятию – 2 усл. ед.; 3-му предприятию - 1 усл. ед.; 4-му предприятию - 1 усл. ед.
Управление запасами
Предприятие, фирмы имеют различные запасы: сырьё, комплектующие изделия, готовую продукцию, предназначенную для продажи, и т.д. Совокупность подобных материалов, представляющих временно не используемые экономические ресурсы, называют запасами предприятия. Запасы создаются по различным причинам. Одна из них состоит в том, что если в некоторый момент производства потребуется какой-то вид деталей, который поставляется другим предприятием, и он отсутствует на складе, то процесс производства может остановиться. Поэтому на складе всегда должно быть нужное количество деталей данного вида. Однако если запасы увеличить, то возрастает стоимость их хранения. Задача управления запасами состоит в выборе для предприятия целесообразного решения.
Управление запасами состоит в отыскании такой стратегии пополнения и расхода запасами, при котором функция затрат принимает минимальное значение.
Задача. Интенсивность равномерного спроса выпускаемых фирмой видеомагнитофонов составляет 2000 шт. в год. Организационные издержки равны 20 тыс. р. Цена видеомагнитофона составляет 1 тыс. р., издержки хранения равны 0,1 тыс. р. в расчете на один видеомагнитофон в год. Запасы на складе пополняются со скоростью 4000 видеомагнитофонов в год. Производственная линия начинает действовать, как только уровень запасов на складе становится равным нулю, и продолжает работу до тех пор, пока не будет произведено q видеомагнитофонов. Найти размер партии, который минимизирует все затраты. Определить число поставок в течение года, время, в течение которого продолжается поставка, продолжительность цикла, максимальный уровень запасов и средний уровень запасов при условии, что размер поставки оптимален.
Решение:
Данная модель задачи является моделью производственных поставок со следующими параметрами:
g =2000, b =20, h =0,1, s =1, p =4000.
Число партий в течении года:
n = g / q =2000/ q .
Продолжительность поставки:
t = q / p = q /4000.
Продолжительность цикла:
L =1/ n = q / g = q /2000.
Максимальный уровень запасов:
RT =( p - g ) t =2000 q /4000= q /2.
Средний уровень запасов:
RT /2= q /4.
Уравнение издержек:
C = C 1+ C 2+ C 3= bn + sg + gh /4.
Решив уравнение dC / dq =0, получим:
видеомагнитофонов.
Найдём оптимальные значения поставок, продолжительность поставки, продолжительность цикла:
Ответ: За каждую поставку необходимо доставлять на склад 1265 видеомагнитофонов, оптимальное число поставок составляет 1,6, продолжительность поставки – 115 дней, продолжительность цикла – 230 дней.
Дата добавления: 2021-01-21; просмотров: 267; Мы поможем в написании вашей работы! |
Мы поможем в написании ваших работ!