Динамическое программирование

Динамическое программирование связано с возможностью представления процесса управления в виде цепочки последовательных действий или шагов, развернутых во времени и ведущих к цели. Таким образом, процесс управления можно разделять на части и представить его в виде динамической последовательности и интерпретировать в виде пошаговой программы, развернутой во времени. Это позволяет спланировать программу будущих действий. Поскольку вариантов возможных планов — программ множество, то, необходимо из них выбрать лучший, оптимальный по какому-либо критерию в соответствии с поставленной целью.

Целью данной курсовой работы является научиться применять различные методы и способы решения задач линейного программирования.

Перед нами стоят следующие вопросы: рассмотреть задачу целочисленного и частично целочисленного линейного программирования, провести анализ модели расчета производственной программы по разным экономическим критериям, решить задачу о раскрое материала методами линейного программирования и провести анализ управляющих решений методами нелинейного программирования.

1. Теоретическая часть

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

Динамическое программирование представляет собой математический аппарат, который подходит к решению некоторого класса задач путем их разложения на части, небольшие и менее сложные задачи. При этом отличительной особенностью является решение задач по этапам, через фиксированные интервалы, промежутки времени, что и определило появление термина динамическое программирование. Следует заметить, что методы динамического программирования успешно применяются и при решении задач, в которых фактор времени не учитывается. В целом математический аппарат можно представить как пошаговое или поэтапное программирование. Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального решения.

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

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

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

Динамическое программирование (ДП) является одним из разделов оптимального программирования. Для него характерны специфические методы и приемы, применительные к операциям, в которых процесс принятия решения разбит на этапы (шаги). Методами ДП решаются вариантные оптимизационные задачи с заданными критериями оптимальности, с определенными связями между переменными и целевой функцией, выраженными системой уравнений или неравенств. При этом, как и в задачах, решаемых методами линейного программирования, ограничения могут быть даны в виде равенств или неравенств. Однако если в задачах линейного программирования зависимости между критериальной функцией и переменными обязательно линейны, то в задачах ДП эти зависимости могут иметь еще и нелинейный характер. ДП можно использовать как для решения связанных с динамикой процесса или системы, так и для статических задач, связанных, например, с распределением ресурсов. Это значительно расширяет область применения ДП для решения задач управления. А возможность упрощения процесса, которая достигается за счет ограничения области и количества исследуемых при переходе к очередному этапу вариантов увеличивает достоинства этого комплекса методов.

Вместе с тем ДП свойственны и недостатки. Прежде всего в нем нет единого универсального метода решения. Практически каждая задача, решаемая этим методом, характеризуется своими особенностями и требует проведения поиска наиболее приемлемой совокупности методов для ее решения. Кроме того, большие объемы и трудоемкость решения многошаговых задач, имеющих множество состояний, приводят к необходимости отбора задач малой размерности либо использования сжатой информации. Последнее достигается с помощью методов анализа вариантов и переработки списка состояний. Для процессов с непрерывным временем ДП рассматривается как предельный вариант дискретной схемы решения. Получаемые при этом результаты практически совпадают с теми, которые получаются методами максимума Л. С. Понтрягина или Гамильтона — Якоби — Беллмана. ДП применяется для решения задач, в которых поиск оптимума возможен при поэтапном подходе, например, распределение дефицитных капитальных вложений между новыми направлениями их использования; разработка правил управления спросом или запасами, устанавливающими момент пополнения запаса и размер пополняющего заказа; разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию; составления календарных планов текущего и капитального ремонтов оборудования и его замены; поиск кратчайших расстояний на транспортной сети, формирование последовательности развития коммерческой операции и т. д. [1]

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

Общая постановка задачи динамического программирования формулируется следующим образом. Имеется некоторая управляемая система, характеризующаяся определенным набором параметров. В этой системе происходят какие-то процессы (экономические, производственные, технологические и т. п.), которые можно представить как многошаговые. На каждом шаге процессам в системе соответствуют определенные значения параметров, описывающих состояние системы. Заданы условия, позволяющие определять или начальное, или конечное состояние системы, или оба этих состояния. Иногда задаются области начальных и конечных состояний. Поскольку управление системой осуществляется для достижения конкретной цели, то указан показатель эффективности управления, называемый целевой функцией, численно выражающий эффект («выигрыш»), получаемый при тот или ином управлении из множества допустимых управлений.

В экономических системах целевая функция может определять прибыль, затраты, рентабельность, объем производства и т. п.

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

Постановку задачи динамического программирования рассмотрим на примере инвестирования, связанного с распределением средств между предприятиями. В результате управления инвестициями система последовательно переводится из начального состояния в конечное. Предположим, что управление можно разбить на n шагов и решение принимается последовательно на каждом шаге, а управление представляет собой совокупность n пошаговых управлений. На каждом шаге необходимо определить два типа переменных — переменную состояния системы и переменную управления. Переменная определяет, в каких состояниях может оказаться система на рассматриваемом k-м шаге. В зависимости от состояния S на этом шаге можно применить некоторые управления, которые характеризуются переменной, которые удовлетворяют определенным ограничениям и называются допустимыми.

Допустим, — управление, переводящее систему из состояния в состояние, а — есть состояние системы на k-м шаге управления. Тогда последовательность состояний системы можно представить в виде графа, представленного на рис. 1.

Рис. 1. График состояний системы

Применение управляющего воздействия, на каждом шаге переводит систему в новое состояние S1 (S,) и приносит некоторый результат (S,). Для каждого возможного состояния на каждом шаге среди всех возможных управлений выбирается оптимальное управление, такое, чтобы результат, который достигается за шаги с k-го по последний n-й, оказался бы оптимальным.

Числовая характеристика этого результата называется функцией Беллмана и зависит от номера шага k и состояния системы S.

Задача динамического программирования формулируется следующим образом: требуется определить такое управление

переводящее систему из начального состояния в конечное состояние при котором целевая функция принимает наибольшее (наименьшее) значение

.

Особенности математической модели динамического программирования заключаются в следующем:

1) задача оптимизации формулируется как конечный многошаговый процесс управления;

2) целевая функция (выигрыш) является аддитивной и равна сумме целевых функций каждого шага:

3) выбор управления на каждом шаге зависит только от состояния системы k этому шагу и не влияет на предшествующие шаги (нет обратной связи);

4) состояние системы после каждого шага управления зависит только от предшествующего состояния системы и этого управляющего воздействия (отсутствие последействия) и может быть записало в виде уравнения состояния

5) на каждом шаге управление зависит от конечного числа управляющих переменных, а состояние системы зависит — от конечного числа параметров;

6) оптимальное управление представляет собой вектор, определяемый последовательностью оптимальных пошаговых управлений

число которых и определяет количество шагов задачи.

1.3 Оптимальное распределение инвестиций

Требуется распределить имеющиеся В единиц средств среди n предприятий, доход от которых в зависимости от количества вложенных средств определяется матрицей (nn) приведенной в таблице 1, так, чтобы суммарный доход со всех предприятий был бы максимальным.

целочисленный нелинейный экономический управленческий

Таблица 1

Запишем математическую модель задачи.

Определить, удовлетворяющий условиям

и обеспечивающий максимум целевой функции

Очевидно, эта задача может быть решена простым перебором всех возможных вариантов распределения В единиц средств по n предприятиям, например на сетевой модели. Однако решим ее более эффективным методом, который заключается в замене сложной многовариантной задачи многократным решением простых задач с малым количеством исследуемых вариантов.

С этой целью разобьем процесс оптимизации на n шагов и будем на каждом k-м шаге оптимизировать инвестирование не всех предприятий, а только предприятий с kго по nе. При этом естественно считать, что в остальные предприятия (с первого по k- 1)-е тоже вкладываются средства, и поэтому на инвестирование предприятий с kго по nе остаются не все средства, а некоторая меньшая сумма. Эта величина и будет являться переменной состояния системы. Переменной управления на kм шаге назовем величину, средств, вкладываемых в kе предприятие. В качестве функции Беллмана на kм шаге можно выбрать макcимально возможный доход, который можно получить с предприятий с kго по nе при условии, что на их инвестирование осталось средств. Очевидно, что при вложении в kе предприятие, средств будет получена прибыль, а система к (k+1)-му шагу перейдет в состояние, и, следовательно, на инвестирование предприятий с (k+1)-го до nго останется средств.

Таким образом, на первом шаге условной оптимизации при k= n функция Беллмана представляет собой прибыль только с nго предприятия. При этом на его инвестирование может остаться количество средств,. Чтобы получить максимум прибыли с этого предприятия, можно вложить в него все эти средства, т. е. и .

На каждом последующем шаге для вычисления функции Беллмана необходимо использовать результаты предыдущего шага. Пусть на kм шаге для инвестирования предприятий с kго по nе осталось, средств (). Тогда от вложения в kе предприятие, средств будет получена прибыль, а на инвестирование остальных предприятий (с kго по nе) останется средств. Максимально возможный доход, который может быть получен с предприятий (с kго по nе), будет равен:

Максимум этого выражения достигается на некотором значении, которое является оптимальным управлением на kм шаге для состояния системы, действуя таким образом, можно определить функции Беллмана и оптимальные управления до шага k = 1.

Значение функции Беллмана представляет собой максимально возможный доход со всех предприятий, а значение на котором достигается максимум дохода, является оптимальным количеством средств, вложенных в первое предприятие. Далее на этапе безусловной оптимизации для всех последующих шагов вычисляется величина и оптимальным управлением на kм шаге является то значение, которое обеспечивает максимум дохода при соответствующем состоянии системы. [2]

Пример

Задача распределения денежных средств между предприятиями

Методом динамического программирования решить задачу распределения ресурсов между предприятиями. 40 млн руб. необходимо распределить между 4 предприятиями так, что бы получить max прирост выпуска продукции. Доходность от вложений заданы в таблице, а вложения кратны 8 млн руб.

Решение:

Запишем задачу в математической форме

При ограничениях

где количество средств, выделяемых каждому предприятию.

ожидаемый прирост продукции от выделенных средств, млн. руб.

Разбиваем процесс решения на 4 этапа. Начальное состояние объекта 40 млн руб., конечное 0 млн руб. Состояние это имеющиеся наом этапе средства, возможные инвестиции вое предприятие. Очевидно

.

1 этап

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

.

2 этап

Выделенную сумму 40 млн руб. распределяем между первым и вторым предприятиями.

Рекуррентное уравнение имеет вид

Поиск ведётся по переменной, которая в зависимости от числа может принимать значения 8; 16; 24; 32; 40, таким образом

3 этап

Решается задача распределения средств между тремя предприятиями, рекуррентная формула имеет вид:

Поиск ведётся по переменной, которая в зависимости от числа может принимать значения 8; 16; 24; 32; 40, таким образом

4 этап

На данном этапе решается исходная задача, распределения суммы 40 млн руб. между четырьмя предприятиями, на основе рекуррентного уравнения вида

Итак, полученный max ожидаемый прирост выпуска продукции равен 216 млн руб. Необходимо определить, при каких вариантах вложений получен этот результат, для этого нужно пройти от 4 этапа к 1 и проследить, как получено max значение целевой функции. На 4 этапе получен max вариант при, фиксируем это значение переменной. Заметим, что, где — этот результат получен на 3 этапе, при, фиксируем это значение переменной. Заметим, что, где — этот результат получен при. Аналогично получаем, таким образом инвестиции целесообразно выделять первому и четвёртому предприятиям, в количестве 8 и 32 млн руб. Оптимальный прирост составляет 216 млн руб.

2. Практическая часть

2.1 Расчет целочисленной закупки станков методом ветвей и границ

Администрация фирмы желает увеличить производство своих изделий за счет привлечения дополнительной производственной площади в объеме S м2, а также покупки у машиностроительных фирм современных станков-автоматов по производству аналогичной продукции на сумму С млн.руб. После изучения соответствующих рекламных проспектов, подходящими для покупки признаны автомат фирмы А, занимающий площадь S1м2, имеющий цену С1 млн руб. и обладающий производительностью Р1 изделий в час; автомат фирмы В, занимающий S2м2, имеющий цену С2 млн руб. и дающий производительность Р2 изделий в час. В каких количествах нужно приобрести автоматы названных фирм, чтобы созданная дополнительная мощность имела наибольшую производительность?

S=15;

С=94;

S1=1;

С1=5;

Р1=14;

S2=1;

С2=8;

Р2=22.

Решение:

Пусть x1 — количество станков фирмы А;

x2 — количество станков фирмы В.

Тогда под стратегией закупки будем понимать вектор удовлетворяющий следующим ограничениям:

· по площади:

· по финансам:

x1, x2 0 — целые числа.

Первый этап

Найдем координаты Хmaxточки пересечения прямых заданных уравнениями Второй этап Ветвление вспомогательной задачи на 4 вспомогательные подзадачи нижнего уровня.

Так как полученное решение не целочисленной, то оно дает верхнюю границу F (x) = для максимума целевой функции искомого оптимального решения исходной задачи.

Задача 1.1

Хmaxточки пересечения прямых:

Задача 1.2

Хmaxточки пересечения прямых:

Задача 2.1

Хmaxточки пересечения прямых:

Задача 2.2

Хmaxточки пересечения прямых:

Задача 1.1.1

Хmaxточки пересечения прямых:

Задача 1.1.2

Хmax-точки пересечения прямых:

Задача 2.2.1

Хmaxточки пересечения прямых:

Задача 2.2.2

Данная задача решений не имеет.

Задача 1.1.2.1

Задача 1.1.2.2

Данная задача решений не имеет.

Задача 2.2.1.1

Задача 2.2.1.2

Задача 1.1.2.1.1

Задача 1.1.2.1.2

Ответ:

при. Максимальная производительность всех закупленных станков (260 изделий в час) будет достигнута, если у фирмы, А приобрести 6 станков, а у фирмы В — 8 станков.

2.2 Анализ модели расчета производственной программы по разным экономическим критериям Администрации компании необходимо установить еженедельную программу производства фасонных отливов, А и В, которая дает максимально чистого дохода на один рубль всех сделанных затрат. Отливка, А гарантирована реализуется по цене С1 (руб), отливка В по цене С2 (руб). Расход электроэнергии на отливку, А составляет А11 (кВт-час), на отливку В составляет А12 (кВт-час), расход угля на, А составит А21 кг, а на В — А22 кг. Минимальные затраты электроэнергии и угля, при которых не произойдут остановки литейного производства равны соответственно D1 кВт/час и D2 кг/нед. Недельный запас компании В1 (кВт-час) и В2 (кг) угля. Себестоимость отливки, А и В без учета заработной платы составляет соответственно S1 и S2 (руб). Сумма оплаты рабочих и служащих компании вместе с другими рабочими составляет S (тыс. руб.) в неделю. Администрация желает исследовать еженедельный выпуск изделий, А и В по трем критериям:

1) максимальный объем продаж;

2) минимальная совокупность затрат;

3) максимальность чистого дохода на рубль всех сделанных затрат.

C1 = 358,24

C2 = 154,36

A11 = 4

A12 = 2

A21 = 5

A22 = 5

D1 = 400

D2 = 500

B1 = 800

B2 = 1000

S1 = 285,2

S2 = 150

S=16,18Решение:

Пусть х1 — программа выпуска изделий А; х2 — программа выпуска изделий В.

Под производственной программой понимаем вектор искомых неизвестных х = {х1,х2}.

Ограничения:

400? 4×1 + 2×2? 800

500? 5×1 + 5×2 ?1000

х1? 0, х2? 0

Приведем систему ограничений к стандартному виду.

Целевая функция первой модели выражает ожидаемый объем продаж компании и стремление к максимуму.

Решим систему графическим способом.

1)

3)

4)

5)

6)

Х1* = 200; Х2* = 0. Z0 = 71,648 (тыс. руб.).

Целевая функция второй модели выражает все понесенные компанией затраты за неделю, которые минимизируются.

Х1* = 100;

Х2* = 0.

Z2 = 42 (тыс. руб.).

Чистые доходы компании за неделю это разность ожидаемой выручки и ожидаемых совокупных затрат, т. е.

(тыс. руб.).

Эквивалентная замена дробно-линейной модели на линейную модель.

Целевая функция третьей модели является не линейной и рассчитывается как отношение чистого недельного дохода ко всем затратам компании, приходящимся на эту неделю.

Экономико-математическая модель с набором ограничений и с критерием выбора производственной программы представляет собой задачу дробно-линейного программирования. Для того, что бы свести такую задачу необходимо ввести следующие замены переменных:

Умножим все ограничения на t0 > 0, что сохраняет направленность всех неравенств и делает замену переменных, при этом получаем дополнительные ограничения.

Целевая функция новых переменных принимает вид линейной функции.

Выразим из дополнительных ограничений Подставим t0 в целевую функцию и ограничения и получим.

Запишем задачу линейного программирования в стандартной форме.

Решим систему графическим методом.

1)

2)

3)

4)

5)

6)

В результате решения графическим методом получим Сделаем обратную замену переменных, для чего найдем значение переменной t0.

Максимизация по дробно-линейному уравнению показывает, что максимальное отношение дохода на один рубль затрат Zmax=0,0532 возможен при программе х*=(147; 0). Понятно, что компанию не удовлетворяет такой ожидаемый результат ее производственной деятельности.

Сведем для сравнительного анализа результаты решения по трем разным критериям в таблицу.

2.3 Решение задачи о раскрое материала методами линейного программирования Из листа стекла размером 4?8 метра требуется нарезать заготовки размерами 2?2 метра и 5?0,5 метра в количестве 100 и 200 штук соответственно.

Для решения задачи рассмотрим 4 схемы раскроя.

1. 2.

3. 4.

Согласно первой схеме раскроя получаем 6 листов первого типа, 3 листа второго типа и отходов 0,5 м².

При второй схеме раскроя получаем 8 листов первого типа, 0 листов второго типа и отходов 0 м².

При третьей схеме раскроя получаем 0 листов первого типа, 12 листов второго типа и отходов 2 м².

При четвертой схеме раскроя получаем 2 листа первого типа, 9 листов второго типа и отходов 1,5 м².

Для формализации задачи обозначим:

Хi — число листов стекла раскроенных по i методу;

ai и bi — число заготовок первого и второго типа раскроенных по i способу;

А — необходимое количество заготовок первого типа;

В — необходимое количество заготовок второго типа.

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

Матрица раскроя

Целевая функция может быть определена по-разному. Например, требуется найти такое решение, которое бы давало минимальное число используемых листов или минимальное количество отходов. Эти две постановки не эквивалентны, так как требования минимальности отходов дает большее количество и соответственно требует расхода большего количества используемого материала.

Допустим, требуется использовать минимальное количество листов, тогда целевая функция будет иметь вид:

Подставляя значение и из матрицы раскроя, приходим к следующей системе ограничений:

Приведем исходную задачу к канонической форме.

Таким образом оптимальное решение имеет вид:

Х = (0; 12,5; 50/3; 0).

Это означает, что по первой схеме раскроя должно быть разрезано 12,5 листов, а по третьей схеме листа.

Такой раскрой даст заготовок первого типа, — второго типа.

Сверхплановых заготовок нет, так как Х5=0, Х6=0.

Отходы составляют: м2.

2.4 Анализ управленческих решений методами нелинейного программирования Производственная фирма может выпускать изделий двух видов: А и Б. Статистическое исследование показало, что из-за брака в процессе производства, средний расход сырья и средняя себестоимость в расчете на 1000 изделий, А и Б не остаются постоянными, а зависят от достигнутого уровня производства. Регрессионным анализом установлено, что средний расход сырья и средняя себестоимость в расчете на 1000 выпускаемых изделий, А линейно зависит от достигнутого объема производства x1 изделий, А по формулам где а1 — 49 тонн, расход сырья, на 1-ю тыс. шт. изделий А;

S1 — 151 тыс. руб., себестоимость 1-ой тыс. шт. изделий А.

Аналогично средний расход сырья и среднюю себестоимость в расчете на тысячу изделий выпущенного объема x2 изделий Б нужно считать по формулам где а2 — 145 тонн, расход сырья, на 1-ю тыс. шт. изделий Б;

S2 — 21 тыс. руб., себестоимость 1-ой тыс. шт. изделий Б.

Пусть сбыт изделий фирмы гарантированно ценам с1=174 тыс. руб., с2=92 тыс. руб. на каждую тысячу штук изделий, А и Б соответственно.

Фирма располагает сырьем b=7200 тонн, продукция может выпускаться в любых пропорциях, но изделий, А должно быть изготовлено не менее 1 тысячи штук. В каком количестве следует производить названное изделие в этих условиях, чтобы прибыль фирмы достигла максимума?

Составим экономико-математическую модель расчета производственной программы, максимизирующую прибыль предприятия в условиях непропорционального роста затрат ресурса и себестоимости выпускаемых продуктов. Формула расхода сырья на изготовление планируемых выпускаемых объемов x1 и х2 тысяч единиц изделий, А и Б имеет вид В результате реализации х1 единиц изделий, А предприятие получит среднюю прибыль:

В результате реализации х2 единиц изделий Б предприятие получит среднюю прибыль:

Тогда суммарную прибыль предприятия можно получить по формуле Получим задачу нелинейного программирования.

Графический анализ задачи нелинейного программирования:

Продифференцируем по х1:

1.

Таким образом, оптимальной производственной программой будет выпуск изделий, А в количестве 12 тыс. шт., а Б — 36 тыс. шт. При этом будет достигнут максимум прибыли в размере 1440 тыс. руб.

Расчет оптимального управляющего решения методом множителей Лагранжа Функция Лагранжа Составим функцию Лагранжа:

)

.

Ответ:

Заключение

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

— в экономике — для решения больших макроэкономических моделей (типа модели Леонтьева и др.), микроэкономических моделей или моделей предпринимательства, для оптимизации технико-экономических систем (планирование, эконометрика), транспортные задачи, в теории принятия решений, теории игр и т. п.;

— в технике — управление размерами и оптимизация структур, оптимальное планирование сложных технических систем, как информационные системы, сети компьютеров, транспортные и телекоммуникационные сети и др.;

— в автоматике — распознавание систем и объектов, оптимальное управление системами, фильтрация, роботы, автоматизированные линии и т. п.;

— в медицине, политике, социологии и т. п., и т. д.

В этой курсовой работе мы изучили различные методы расчета задач линейного программирования и научились применять их на практике.

1. Визгунов Н. П. — Динамическое программирование в экономических задачах — Н. Новгород: ННГУ, 2011.

.ur