Динамическое программирование. Задача оптимального распределения ресурсов

1. Основные понятия

1.1. Модель динамического программирования

1.2. Принцип оптимальности. Уравнение Беллмана

2. Оптимальное распределение ресурсов

2.1 Постановка задачи

2.2 Двумерная модель распределения ресурсов

2.3 Дискретная динамическая модель оптимального распределения ресурсов

2.4 Учет последействия в задачах оптимального распределения ресурсов

Заключение

Список используемых источников

Приложение 1. Листинг программы для решения задачи оптимального распределения ресурсов с заданными параметрами. Результаты работы программы

Введение

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

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

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

Как раздел математического программирования, динамическое программирование (ДП) начало развиваться в 50-х годах XX в. благодаря работам Р. Беллмана и его сотрудников. Впервые этим методом решались задачи оптимального управления запасами, затем класс задач значительно расширился. Как практический метод оптимизации, метод динамического программирования стал возможен лишь при использовании современной вычислительной техники.

В основе метода динамического программирования лежит принцип оптимальности, сформулированный Беллманом. Этот принцип и идея включения конкретной задачи оптимизации в семейство аналогичных многошаговых задач приводят к рекуррентным соотношениям - функциональным уравнениям - относительно оптимального значения целевой функции. Их решение позволяет последовательно получить оптимальное управление для исходной задачи оптимизации.

1. Основные понятия

1.1 Модель динамического программирования

Дадим общее описание модели динамического программирования.

Рассматривается управляемая система, которая под влиянием управления переходит из начального состояния

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

Рисунок 1

Состояние

системы после k-го шага ( k = 1,2 …,n ) характеризуется параметрами , ,…, которые называются фазовыми координатами. Состояние можно изобразить точкой s-мерного пространства называемого фазовым пространством. Последовательное преобразование системы (по шагам) достигается с помощью некоторых мероприятий , ,…, , которые составляют управление системой

, где - управление на k -м шаге, переводящее систему из состояния в состояние (рис. 1). Управление на k -ом шаге заключается в выборе значений определенных управляющих переменных .

Предполагаем впредь, что состояние системы в конце k-го шага зависит только от предшествующего состояния системы

и управления на данном шаге (рис. 1). Такое свойство получило название отсутствия последействия. Обозначим эту зависимость в виде

, (1.1)

Равенства (1.1) получили название уравнений состояний. Функции

полагаем заданными.

Варьируя управление U , получим различную «эффективность» процесса , которую будем оценивать количественно целевой функцией Z , зависящей от начального состояния системы

и от выбранного управления U : . (1.2)

Показатель эффективности k-го шага процесса управления, который зависит от состояния

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

. (1.3)

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

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

Обычно условиями процесса на управление на каждом шаге

накладываются некоторые ограничения. Управления, удовлетворяющие этим ограничениям называются допустимыми .

Задачу пошаговой оптимизации можно сформулировать так: определить совокупность допустимых управлении

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Задача распределения ресурсов методом динамического программирования

Для расширения производственных мощностей трех предприятий А, В и С выделяется некоторое количество единиц дополнительной электроэнергии в объеме х 0 =8 единиц. Электроэнергия может выделяться в виде 1, 2, 3, 4, 5, 6, 7 и 8 единиц. Вкладывая в развитие i-того предприятия х i единиц электроэнергии можно получить доход у i единиц на предприятии. Существуют разные варианты х i (к) выделения дополнительной электроэнергии. Они приносят доход у i (к), к=1,n. Возможные варианты развития предприятий приведены в табл.1. Суммарный доход по всем предприятиям должен быть максимальным, т.е у=? у i (к)>max

Табл. 1. Варианты развития предприятий

Вариант к	Предриятие А	Предприятие В	Предприятие С

Математическая постановка задачи:

у=? у i (к)> max

?х i (к)?х 0

Решение:

Начнем рассмотрение процедуры решения поставленной задачи с последнего (3 шага) этапа (Табл.2), на котором инвестиции выделяются предприятию С. Условно-оптимальное управление на третьем этапе ищется как решение уравнения

g C (S 2)=max k f c , x C (k)?S 2 , k=1,2,3,4

Табл. 2. Условно-оптимальные решения(шаг 3)

Состояние		Управление

Имеется четыре возможности вложения средств - четыре шаговых управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед. и девять теоретически возможных состояний системы S 2 , предшествующих выделению средств предприятию С, - объемы не распределенных к 3-му этапу инвестиций: 0,1,2,3,4,5,6,7,8.

Предположим, что система находилась в состоянии S 2 =2.Тогда, для шагового управления х С (2)=1 доход у С (2) будет равен 3ед. (Табл.3), а шаговое управление х С (3)=2 будет оптимальным для этого состояния, дающим условно-максимальный выигрыш g c (S 2)=5. Если система находилась в состоянии S 2 =3, то допустимы все шаговые управления х С (1)=0ед., х С (2)=1ед., х С (3)=2ед., х С (4)=3ед., а оптимальным будет управление х С (4)=3, которое обеспечивает условно максимальный выигрыш g c (S 2)=6.

Табл.3 динамический программирование распределение инвестиция

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

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

g А (S 1)=max k f А +g c ], x А (k)?S 1 , k=1,2,3,4

Так, для состояния S 1 =3 с шаговым управление х A (2)=1 получаем:

g А (S 1)=max k f А +g c ]

Max k 4+g c =4+5=9, где находим из таблицы 1, а g c из таблицы 3. Аналогично заполняются все состояния.

Табл. 4. Условно-оптимальные решения(шаг 2)

Состояние	f А +g c	Управление

Здесь возникают ситуации, при которых оптимальное решение будет не единственным, Так в состояние S 1 =3 условно оптимальными будут шаговые управления х A (2)=1 и х A (3)=2, дающие один и тот же выигрыш g A (S 1)=9

Табл. 5. Безусловно-оптимальные решения (шаг 1)

На первом этапе (Табл.5)-выделение инвестиций предприятию В - есть только одно предшествующее состояние системы, соответствующее начальному состоянию S 0 =8. Безусловно оптимальный выигрыш определяется выражением:

у * = g В (S 0)= max k {f А +g А } x в (k)?S 0 =x 0 , k=1,2,3,4,5

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

Схема нахождения всех оптимальных вариантов распределения инвестиций между предприятиями (Табл.6) представлена на рисунке 1.

Табл. 6. Оптимальные распределения инвестиций.

Рисунок 1. Схема оптимального распределения инвестиций между предприятиями

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

Размещено на Allbest.ru

...

Подобные документы

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

курсовая работа , добавлен 25.04.2015

Многошаговые процессы в динамических задачах. Принцип оптимальности и рекуррентные соотношения. Метод динамического программирования. Задачи оптимального распределения средств на расширение производства и планирования производственной программы.

курсовая работа , добавлен 30.12.2010

Метод динамического программирования и его основные этапы. Оптимальная стратегия замены оборудования. Минимизация затрат на строительство и эксплуатацию предприятий. Оптимальное распределение ресурсов в ООО "СТРОЙКРОВЛЯ" и инвестиций ПКТ "Химволокно".

курсовая работа , добавлен 08.01.2015

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

дипломная работа , добавлен 07.08.2013

Расчет стоимости перевозок методом минимальных затрат. Нахождение условного оптимального равенства в процессе динамического программирования. Линейное алгебраическое уравнение Колмогорова для среднего времени безотказной работы резервированной системы.

курсовая работа , добавлен 14.01.2011

Графический метод решения задачи оптимизации производственных процессов. Применение симплекс-алгоритма для решения экономической оптимизированной задачи управления производством. Метод динамического программирования для выбора оптимального профиля пути.

контрольная работа , добавлен 15.10.2010

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

курсовая работа , добавлен 16.12.2013

Характерные черты задач линейного программирования. Общая постановка задачи планирования производства. Построение математической модели распределения ресурсов фирмы. Анализ чувствительности оптимального решения. Составление отчета по устойчивости.

презентация , добавлен 02.12.2014

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

дипломная работа , добавлен 11.02.2017

Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.

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

Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?

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

Управляемая система S в данном случае - средства или ресурсы, которые распределяются. Состояние системы S перед каждым шагом характеризуется одним числом S - наличным запасом еще не вложенных средств. В этой задаче «шаговыми управлениями» являются средства выделяемые предприятиям. Требуется найти оптимальное управление, т. е. такую совокупность чисел при которой суммарный доход максимален:

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

Начнем оптимизацию с последнего, шага. Пусть мы подошли к этому шагу с остатком средств S. Что нам делать? Очевидно, вложить всю сумму S целиком в предприятие Поэтому условное оптимальное управление на -м шаге: отдать последнему предприятию все имеющиеся средства S, т. е.

а условный оптимальный выигрыш

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

Перейдем к предпоследнему, шагу. Пусть мы подошли к нему с запасом средств S. Обозначим условный оптимальный выигрыш на двух последних шагах: (который уже оптимизирован). Если мы выделим на шаге предприятию средства то на последний шаг останется Наш выигрыш на двух последних шагах будет равен

и нужно найти такое , при котором этот выигрыш максимален:

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

и соответствующее ему условное оптимальное управление - то значение при котором этот максимум достигается.

Продолжая таким образом, дойдем, наконец, до предприятия Здесь нам не нужно будет варьировать значения S; мы точно знаем, что запас средств перед первым шагом равен К:

Итак, максимальный выигрыш (доход) от всех предприятий найден. Теперь остается только «прочесть рекомендации». То значение при котором достигается максимум (13.4), и есть оптимальное управление на 1-м шаге.

После того как мы вложим эти средства в 1-е предприятие, у нас их останется . «Читая» рекомендацию для этого значения S, выделяем второму предприятию оптимальное количество средств: и т. д. до конца.

А теперь решим численный пример. Исходный запас средств (условных единиц), и требуется его оптимальным образом распределить между пятью предприятиями Для простоты предположим, что вкладываются только целые количества средств. Функции дохода заданы в таблице 13.1.

Таблица 13.1

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

Произведем условную оптимизацию так, как это было описано выше, начиная с последнего, 5-го шага. Каждый раз, когда мы подходим к очередному шагу, имея запас средств?, мы пробуем выделить на этот шаг то или другое количество средств, берем выигрыш на данном шаге по таблице 13.1, складываем с уже оптимизированным выигрышем на всех последующих шагах до конца (учитывая, что средств у нас осталось уже меньше, как раз на такое количество средств, которое мы выделили) и находим то вложение, на котором эта сумма достигает максимума. Это вложение и есть условное оптимальное управление на данном шаге, а сам максимум - условный оптимальный выигрыш.

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

Таблица 13.2

В первом столбце каждой пары приводится значение условного оптимального управления, во втором - условного оптимального выигрыша. Таблица заполняется слева направо, сверху вниз. Решение на пятом - последнем - шаге вынужденное: выделяются все средства; на всех остальных шагах решение приходится оптимизировать. В результате последовательной оптимизации 5-го, 4-го, 3-го, 2-го и 1-го шагов мы получим полный список всех рекомендаций по оптимальному управлению и безусловный оптимальный выигрыш W за всю операцию - в данном случае он равен 5,6. В последних двух столбцах таблицы 13.2 заполнена только одна строка, так как состояние системы перед началом первого шага нам в точности известно: . Оптимальные управления на всех шагах выделены рамкой. Таким образом, мы получили окончательный вывод: надо выделить первому предприятию две единицы из десяти, второму - пять единиц, третьему - две, четвертому - ни одной, пятому - одну единицу. При этом распределении доход будет максимален и равен 5,6.