Инструкция . Выберите количество предприятий.
Пример №1 . Планируется работа двух предприятий на n лет. Начальные ресурсы равны s0. Средства x, вложенные в 1-е предприятие в начале года, дают в конце года прибыль f1(x), и возвращаются в размере g1(x). Средства y, вложенные в 2-е предприятие в начале года, дают в конце года прибыль f2(y) и возвращаются в размере g2(y). В конце года возвращенные средства заново перераспределяются между отраслями. Определить оптимальный план распределения средств и найти максимальную прибыль.
Задачу решим методом динамического программирования. Операцию управления производственным процессом разобьём на этапы. На каждом из них управление выберем так, чтобы оно приводило к выигрышу как на данном этапе, так и на всех последующих до конца операции. В этом состоит принцип оптимальности
, сформулированный американским математиком А. Беллманом.
Разобьём весь период на три этапа по годам и будем нумеровать их, начиная с первого.
Обозначим через x k
и y k
количество средств выделяемых каждому предприятию на k-ом этапе, а через x k
+ y k
= a k
- общее количество средств на этом этапе. Тогда первое предприятие приносит на этом этапе 3 x k
, а второе 4 y k
единиц дохода. Общий доход на k-ом этапе 3x k
+ 4y k
.
Обозначим через f
k (a
k) - максимальный доход, который получает отрасль от обоих предприятий на k-ом и всех последующих. Тогда функциональное уравнение, отражающее принцип оптимальности Беллмана, принимает вид:
f k (a k)=
max{3
x k + 4
y k +
f k +1 (a k +1)}.
(1)
Так как x k + y k = a k , то
y k = a k - x k и
3x k + 4y k = 3x k + 4(a k - x k) = - x k + 4a k . Поэтому
f k (a k) = max{-x k + 4a k + f k+1 (ak+1)}
. (2)
0 ≤ x k ≤ a k
Кроме того, ak - это средства выделяемые обои предприятиям на k-ом этапе, и они определяются остатком средств, получаемых на предыдущем (k-1)-ом этапе. Поэтому по условию задачи оптимальное управление на каждом этапе
a k = 0,5
x k -1 + 0,2
y k -1 = 0,5
x k -1 +0,2(a k -1 -
x k -1) = 0,3
x k -1 +0,2
a k -1 .
(3)
I.Условия оптимизации
Планирование начинаем с последнего третьего этапа
При k
=
3
получаем из (2)
f 3 (a 3) = max {- x 3 + 4a 3 + f 4 (a 4)}
0 ≤ x 3 ≤ a 3
Так как четвёртого этапа нет, то f 4 (a 4)=0
и
f 3 (a 3) = max {- x 3 + 4a 3 }=4a 3
0 ≤ x 3 ≤ a 3
(максимум выражения (-
x 3 + 4
a 3
) будет при x 3 =0)).
Итак, для третьего последнего этапа имеем: f 3 (a 3) = 4
a 3 ,
x 3 = 0,
y 3 =
a 3 -
x 3 =
a 3 ,
где a
3 = 0,3x 2
+ 0,2a 2 ,
что следует из формулы (3).
При k = 2
из (2) и (3) получаем:
f(a 2) = max {-x 2 + 4a 2 + f 3 (a 3)}=
0 ≤ x ≤ a 2
= max {-x 2 + 4a 2 + 4a 3 }= max {-x 2 + 4a 2 + 4(0,3x 2
+ 0,2a 2)} max{0,2x 2 + 4,8a 2 } 5a
0 ≤ x ≤ a
2
т. к. максимум выражения (0,2
x 2 + 4,8
a 2
) будет при x 2 =
a 2
.
То для второго этапа имеем: f 2 (a 2) = 5a 2 , x 2 = a 2 , y 2 = a 2 x 2 = 0 , при этом
a 2 = 0,3x 1 + 0,2a 1 с учетом (3).
При k = 1
с учетом (2) и (3) получаем:
f 1 (a 1) = max {-x 1 + 4a 1 + f 2 (a 2)}=
0 ≤ x ≤ a 1
= max {-x 1 + 4a 1 + 5a 2 }= max {-x 1 + 4a 2 + 5(0,3x 1 + 0,2a 2)}= max {0,5x 1 + 5a 1 }=5,5a 1
0 ≤ x ≤ a
1
при x 1 = a 1
.
Итак, для первого этапа f 1 (a 1) = 5,5
a 1 ,
x 1 =
a 1 ,
y 1 = 0.
Процесс закончен. На первом этапе общее количество распределяемых средств известно -a 1
= 900 ед. Тогда максимальный доход, получаемый обоими предприятиями за три года составит f 1 (a 1) = 5,5*900 = 4950 ден. ед.
II. Безусловная оптимизация
Выясним, каким должно быть оптимальное управление процессом выделения средств между первым и вторым предприятиями для получения максимального дохода в количестве 4950 ден. ед.
1-й год.
Так как x 1 =
a 1
и ,
y 1 = 0,
то все средства в количестве 900 ден. ед. отдаются первому предприятию.
2-й год.
Выделяются средства a 2 = 0,3x 1 + 0,2a 1 = 0,5 a 1
=450 ед., x 2 = a 2 , y 2 = 0.
Все они передаются первому предприятию.
3-й год
. Выделяются средства a
3 = 0,3x 2
+ 0,2a 2
= 0,5 a 2
= 225 ед., x 3 = 0,
y 3 =
a 3
. Все они передаются второму предприятию.
Результаты решения представим в виде таблицы.
| Период | Средства | Предприятие №1 | Предприятие №2 | Остаток | Доход |
| 1 | 900 | 900 | 0 | 450 | 2700 |
| 2 | 450 | 450 | 0 | 225 | 1350 |
| 3 | 225 | 0 | 225 | 45 | 900 |
| 4950 |
Пример №2 . Оптимальное поэтапное распределение средств между предприятиями в течении планового периода.
Руководство фирмы, имеющей договор о сотрудничестве с тремя малыми предприятия, на плановый годовой период выделила для них оборотные средства в объеме 100000 у.е. Для каждого предприятия известны функции поквартального дохода и поквартального остатка оборотных средств в зависимости от выделенной на квартал суммы x. В начале квартала средства распределяются полностью между тремя предприятиями (из этих вложенных средств и вычисляется доход), а по окончанию квартала остатки средств аккамулируются у руководства фирмы и снова распределяются полностью между предприятиями.
Составить план поквартального распределения средств на год (4 квартала), позволяющего достичь максимальный общий доход за год.
f 1 (x)=1,2x, f 2 (x)=1.5x, f 3 (x)=2x; g 1 (x)=0.7x, g 2 (x)=0.6x, g 3 (x)=0.1x
Метод динамического программирования позволяет с успехом решать многие экономические задачи (см., например, ). Рассмотрим одну из простейших таких задач. В нашем распоряжении имеется какой-то запас средств (ресурсов) К, который должен быть распределен между предприятиями . Каждое из предприятий при вложении в него каких-то средств приносит доход, зависящий от , т. е. представляющий собой какую-то функцию Все функции заданы (разумеется, эти функции - неубывающие).
Спрашивается, как нужно распределить средства К между предприятиями, чтобы в сумме они дали максимальный доход?
Эта задача легко решается методом динамического программирования. Хотя в своей постановке она не содержит упоминания о времени, можно все же операцию распределения средств мысленно развернуть в какой-то последовательности, считая за первый шаг вложение средств в предприятие за второй - в и т. д.
Управляемая система 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.
Имеется определенное количество ресурсов s 0 , которое необходимо распределить между n хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц, квартал, полугодие, год и т.д.) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов x i (;) в деятельность каждого хозяйствующего субъекта кратны некоторой величине h. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств x i за рассматриваемый период приносит прибыль в размере f i (x i) (не зависит от вложения ресурсов в другие хозяйствующие субъекты).
Представим процесс распределения ресурсов между хозяйствующими субъектами как n-шаговый процесс управления (номер шага совпадает с условным номером хозяйствующего субъекта). Пусть s k () - параметр состояния, т.е. количество свободных средств после k-го шага для распределения между оставшимися (n - k) хозяйствующими субъектами. Тогда уравнения состояний можно записать в следующем виде:
Введем в рассмотрение функцию - условно оптимальная совокупная прибыль, полученная от k-го, (k+1) - го, …, n-го хозяйствующих субъектов, если между ними оптимальным образом распределялись ресурсы в объеме s k-1 (). Множество возможных управленческих решений относительно размера распределяемых ресурсов на k-ом шаге можно представить следующим образом: .
Тогда рекуррентные уравнения Р.Э. Беллмана (обратная схема) будут иметь вид:
Пример. Имеется определенное количество ресурсов s 0 =100, которое необходимо распределить между n=4 хозяйствующими субъектами на текущую деятельность в течение рассматриваемого периода (месяц) с целью получения совокупной максимальной прибыли. Размеры вложений ресурсов x i (;) в деятельность каждого хозяйствующего субъекта кратны величине h=20 и заданы вектором Q. Известно, что каждый хозяйствующий субъект в зависимости от объема используемых средств x i за рассматриваемый период приносит прибыль в размере f i (x i) () (не зависит от вложения ресурсов в другие хозяйствующие субъекты):
Необходимо определить, какой объем ресурсов нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
Решение. Составим рекуррентные уравнения Беллмана (обратную схему):
Определим условные максимумы в соответствии с (13), результаты расчетов представлены в таблице 1.
Таблица 1. Расчет условных оптимумов
|
22+20=42 |
|||||||||||
|
22+33=55 |
17+42=59 |
||||||||||
|
22+46=68 |
17+55=72 |
14+59=73 |
|||||||||
|
67+20=87 |
|||||||||||
По результатам условной оптимизации определим оптимальное распределение ресурсов:
Таким образом, оптимальное распределение ресурсов:
которое обеспечит наибольшую прибыль в размере 87 усл. ден. ед.
Ответ: оптимальное распределение ресурсов: , которое обеспечивает наибольшую прибыль в 87 усл. ден. ед.
Вывод
Динамическое программирование - это область математического программирования, включающая совокупность приемов и средств для нахождения оптимального решения, а также оптимизации каждого шага в системе и выработке стратегии управления, то есть процесс управления можно представить, как многошаговый процесс. Динамическое программирование, используя поэтапное планирование, позволяет не только упростить решение задачи, но и решить те из них, которым нельзя применить методы математического анализа. Упрощение решения достигается за счет значительного уменьшения количества исследуемых вариантов, так как вместо того, чтобы один раз решать сложную многовариантную задачу, метод поэтапного планирования предполагает многократное решение относительно простых задач. Планируя поэтапный процесс, исходят из интересов всего процесса в целом, т.е. при принятии решения на отдельном этапе всегда необходимо иметь в виду конечную цель. Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения. Недостаток динамического программирования заключается также в трудоемкости решения многомерных задач. Задача динамического программирования должна удовлетворять два условия. Первое условие обычно называют условием отсутствия последействия, а второе - условием аддитивности целевой функции задачи. На практике встречаются такие задачи планирования, в которых заметную роль играют случайные факторы, влияющие как на состояние системы, так и на выигрыш. Существует разница между детерминированной и стохастической задачами динамического программирования. В детерминированной задаче оптимальное управление является единственным и указывается заранее как жесткая программа действий. В стохастической задаче оптимальное управление является случайным и выбирается в ходе самого процесса в зависимости от случайно сложившейся ситуации. В детерминированной схеме, проходя процесс по этапам от конца к началу, тоже находится на каждом этапе целый ряд условных оптимальных управлений, но из всех этих управлений, в конечном счете осуществлялось только одно. В стохастической схеме это не так. Каждое из условных оптимальных управлений может оказаться фактически осуществленным, если предшествующий ход случайного процесса приведет систему в соответствующее состояние. Принцип оптимальности является основой поэтапного решения задач динамического программирования. Типичными представителями экономических задач динамического программирования являются так называемые задачи производства и хранения, задачи распределения капиталовложений, задачи календарного производственного планирования и другие. Задачи динамического программирования применяются в планировании деятельности предприятия с учетом изменения потребности в продукции во времени. В оптимальном распределении ресурсов между предприятиями в направлении или во времени. Описание характеристик динамического программирования и типов задач, которые могут быть сформулированы в его рамках, по необходимости должно быть очень общим и несколько неопределенным, так как существует необозримое множество различных задач, укладывающихся в схему динамического программирования. Только изучение большого числа примеров дает отчетливое понимание структуры динамического программирования.
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
Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.
