Динамическое программирование (ДП) – это метод нахождения оптимальных решений в задачах с многошаговой (многоэтапной) структурой.
Приведем
общую постановку задачи ДП. Рассматривается
управляемый процесс (распределение
средств между предприятиями, использование
ресурсов в течение ряда лет и т.п.). В
результате управления система (объект
управления) переводится из начального
состояния
в состояние
.
Предположим, что управление можно
разбить на
шагов. На каждом шаге выбирается одно
из множества допустимых управлений
,
переводящее систему в одно из состояний
множества
.
Элементы множества
и
определяются из условий конкретной
задачи. Последовательность состояний
системы можно изобразить в виде графа
состояний, представленного на рис. 3.1.
На
каждом шаге n
достигается эффект
.
Предположим, что общий эффект является
суммой эффектов, достигнутых на каждом
шаге. Тогда задача ДП формулируется
так: определить такое допустимое
управление
,
переводящее систему из состояния
в состояние
,
при котором функция цели
принимает наибольшее (наименьшее)
значение, т.е.
Решение задач методом ДП осуществляется на основе принципа оптимальности, который был сформулирован американским ученым Р.Беллманом: каково бы ни было состояние системы в результате какого-либо числа шагов, на ближайшем шаге нужно выбирать управление так, чтобы оно в совокупности с оптимальным управлением на всех последующих шагах приводило к оптимальному выигрышу на всех оставшихся шагах, включая данный.
Обозначим
через
условно-оптимальное значение целевой
функции на интервале от шагаn
до последнего
-го
шага включительно, при условии, что
передn
-ым
шагом система находилась в одном из
состояний множества
,
а наn
-ом
шаге было выбрано такое управление из
множества
,
которое обеспечило целевой функции
условно-оптимальное значение, тогда
условно-оптимальное значение целевой
функции в интервале от (n
+1
)-го
до
-го
шага включительно.
В принятых обозначениях принцип оптимальности Беллмана можно записать в математической форме следующим образом
Равенство (3.1) называется основным функциональным уравнением динамического программирования. Для каждой конкретной задачи уравнение имеет особый вид.
Вычислительная процедура метода ДП распадается на два этапа: условную и безусловную оптимизацию.
На этапе условной оптимизации в соответствии с функциональным уравнением определяются оптимальные управления для всех возможных состояний на каждом шаге, начиная с последнего.
На
этапе безусловной
оптимизации
шаги рассматриваются, начиная с первого.
Поскольку исходное состояние
известно, выбирается оптимальное
управление из множества
.
Выбранное оптимальное управление
приводит систему во вполне определенное
состояние
.
Благодаря тому, что исходное состояние
в начале второго шага известно, становится
возможным выбрать оптимальное управление
на втором шаге
и т.д. Таким образом, строится цепь
взаимосвязанных решений безусловной
оптимизации.
Пусть
на реконструкцию и модернизацию основного
производства объединению выделяется
некоторый объем материальных ресурсов
Х
.
Имеется N
предприятий, между которыми нужно
распределить данный ресурс. Обозначим
через
прибыль, которому приносит народному
хозяйству выделениеj
-му
предприятию
единиц ресурса. Предполагается, что
размер прибыли зависит как от выделенного
количества ресурса, так и от предприятия.
Причем прибыль, получаемая предприятиями
измеряется в одних и тех же единицах и
общая прибыль объединения состоит из
прибылей отдельных предприятий.
Необходимо найти оптимальный план
распределения ресурсов между предприятиями,
при котором общая прибыль объединения
будет максимальной.
Поставленную задачу нужно рассмотреть как многошаговую.
На
этапе условной оптимизации будем
рассматривать эффективность вложения
средств на одном (например, на первом
предприятии), на двух предприятиях
вместе (на первом и втором), на трех
предприятиях вместе (на первом, втором
и третьем) и т.д., и наконец, на всех N
предприятиях вместе. Задача состоит в
определении наибольшего значения
функции
при условии, что
.
Воспользуемся
рекуррентным соотношением Беллмана
(3.1), которое для данной задачи приводит
к следующим функциональным уравнениям
при
:
Здесь
функция
определяет максимальную прибыль первого
предприятия при выделении емуx
единиц ресурса, функция
определяет максимальную прибыль первого
и второго предприятий вместе при
выделении имx
единиц ресурса, функция
определяет максимальную прибыль первого,
второго и третьего предприятий вместе
при выделении имx
единиц ресурса и т.д., и наконец, функция
определяет максимальную прибыль всех
предприятий вместе при выделении имx
единиц ресурса.
На этапе безусловной оптимизации определяется оптимальный план распределения ресурсов между предприятиями.
Пример 3.1.
Для
увеличения объемов выпуска пользующейся
повышенным спросом продукции четырем
предприятиям производственного
объединения выделены средства в размере
50 млн. руб. Каждому из предприятий может
быть выделено: 0, 10, 20, 30, 40 или 50 млн. руб.
При этом ежегодный прирост выпуска
продукции каждым из предприятий
в зависимости от капиталовложений
известен и приведен в табл. 3.1.
Таблица 3.1
|
Объем выделенных средств x (млн. руб.) |
Ежегодный прирост выпуска продукции (млн. руб.), в зависимости от объема выделенных средств |
|||
|
|
|
|
|
|
Найти оптимальный план распределения средств между предприятиями, обеспечивающий максимальный ежегодный прирост выпуска продукции производственным объединением.
Имеется определенное количество ресурсов 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 усл. ден. ед.
Вывод
Динамическое программирование - это область математического программирования, включающая совокупность приемов и средств для нахождения оптимального решения, а также оптимизации каждого шага в системе и выработке стратегии управления, то есть процесс управления можно представить, как многошаговый процесс. Динамическое программирование, используя поэтапное планирование, позволяет не только упростить решение задачи, но и решить те из них, которым нельзя применить методы математического анализа. Упрощение решения достигается за счет значительного уменьшения количества исследуемых вариантов, так как вместо того, чтобы один раз решать сложную многовариантную задачу, метод поэтапного планирования предполагает многократное решение относительно простых задач. Планируя поэтапный процесс, исходят из интересов всего процесса в целом, т.е. при принятии решения на отдельном этапе всегда необходимо иметь в виду конечную цель. Однако динамическое программирование имеет и свои недостатки. В отличие от линейного программирования, в котором симплексный метод является универсальным, в динамическом программировании такого метода не существует. Каждая задача имеет свои трудности, и в каждом случае необходимо найти наиболее подходящую методику решения. Недостаток динамического программирования заключается также в трудоемкости решения многомерных задач. Задача динамического программирования должна удовлетворять два условия. Первое условие обычно называют условием отсутствия последействия, а второе - условием аддитивности целевой функции задачи. На практике встречаются такие задачи планирования, в которых заметную роль играют случайные факторы, влияющие как на состояние системы, так и на выигрыш. Существует разница между детерминированной и стохастической задачами динамического программирования. В детерминированной задаче оптимальное управление является единственным и указывается заранее как жесткая программа действий. В стохастической задаче оптимальное управление является случайным и выбирается в ходе самого процесса в зависимости от случайно сложившейся ситуации. В детерминированной схеме, проходя процесс по этапам от конца к началу, тоже находится на каждом этапе целый ряд условных оптимальных управлений, но из всех этих управлений, в конечном счете осуществлялось только одно. В стохастической схеме это не так. Каждое из условных оптимальных управлений может оказаться фактически осуществленным, если предшествующий ход случайного процесса приведет систему в соответствующее состояние. Принцип оптимальности является основой поэтапного решения задач динамического программирования. Типичными представителями экономических задач динамического программирования являются так называемые задачи производства и хранения, задачи распределения капиталовложений, задачи календарного производственного планирования и другие. Задачи динамического программирования применяются в планировании деятельности предприятия с учетом изменения потребности в продукции во времени. В оптимальном распределении ресурсов между предприятиями в направлении или во времени. Описание характеристик динамического программирования и типов задач, которые могут быть сформулированы в его рамках, по необходимости должно быть очень общим и несколько неопределенным, так как существует необозримое множество различных задач, укладывающихся в схему динамического программирования. Только изучение большого числа примеров дает отчетливое понимание структуры динамического программирования.
Назначение сервиса . Онлайн-калькулятор предназначен для решения задачи оптимального распределения ресурсов заданных в виде функций f(x) . Результаты вычислений оформляются в отчете формата Word (см. ).Инструкция . Выберите количество предприятий.
Пример №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 |
Информатика, кибернетика и программирование
Средства X выделенные kому предприятию приносит в конце года прибыль. Функции заданы таблично: X f1X f2X f3X f4X 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ому предприятию. Уравнения на м шаге удовлетворяют условию: либо kому предприятию ничего не выделяем: либо не больше того что...
Лабораторная работа 4_2. Решение задачи о распределении ресурсов методом динамического программирования.
Цель работы изучить возможности табличного процессора MS Excel для решения задачи распределения ограниченных ресурсов методом динамического программирования.
Краткие теоретические сведения
Построение модели динамического программирования (ДП) и применение метода ДП для решения задачи сводится к следующему:
а) и
б) по цепочке оптимальное управление (решение) .
Постановка задачи динамического программирования в общем виде.
Условие задачи . Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства: у.е. Размеры вложения в каждое предприятие кратны 1 условной единице. Средства X , выделенные k
|
f 1 (X) |
f 2 (X) |
f 3 (X) |
f 4 (X) |
|
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль (равная сумме прибылей, полученных от каждого предприятия), была наибольшей.
Решение. Пусть - количество средств, выделенных k -ому предприятию. Суммарная прибыль равна. Переменные X удовлетворяют ограничениям: . Требуется найти переменные, удовлетворяющие данным ограничениям и обращающие в максимум функцию Z .
Схема решения задачи методом ДП имеет следующий вид: процесс решения распределения средств можно рассматривать как 4-шаговый, номер шага совпадает с номером предприятия; выбор переменных уравнения на 1, 2, 3, 4 шагах соответственно; - конечное состояние процесса распределения равно нулю, т.к. все средства должны быть вложены в производство, =0 .
Уравнения состояний и схему распределения можно представить в виде:
Здесь - параметр состояния количество средств, оставшихся после k -ого шага, т.е. средства, которые остается распределить между оставшимися (4- k ) предприятиями.
Введем в рассмотрение функцию - условно оптимальную прибыль, полученную от -го, (k +1 )-го, …, 4-го предприятий, если между ними распределялись оптимальным образом средства). Уравнения на -м шаге удовлетворяют условию: (либо k -ому предприятию ничего не выделяем: , либо не больше того, что имеем к k -ому шагу:).
Уравнения Беллмана имеют вид:
Решение уравнений осуществляется путем последовательной оптимизации каждого шага.
4 шаг. Все средства, оставшиеся к 4-ому шагу, следует вложить в 4-е предприятие, поскольку согласно таблице прибыли монотонно возрастают. При этом для возможных значений получим:
3 шаг . Делаем предположения относительно остатка средств к 3-ему шагу: может принимать значения 0,1,2,3,4,5 (=0, если все средства отданы 1-ому и 2-ому предприятиям и т.д.). В зависимости от этого выбираем и сравниваем для разных при фиксированных значениях значения суммы. Для каждого максимальное из этих значений есть - условная оптимальная прибыль, полученная при оптимальном распределении средств между 3-м и 4-м предприятиями. Полученные значения для приведены в таблице в графах 5 и 6 соответственно.
|
S k-1 |
k =3 |
k =2 |
k =1 |
||||||||
|
f 3 (X 3 )+ |
f 2 (X 2 )+ |
f 1 (X 1 )+ |
|||||||||
|
0+4=4 3+0=3 |
0+4=4 6+0=6 |
0+6=6 8+0=8 |
|||||||||
|
0+6=6 3+4=7 4+0=4 |
0+7=7 6+4=10 9+0=9 |
0+10=10 8+6=14 10+0=10 |
|||||||||
|
0+8=8 3+6=9 4+4=8 7+0=7 |
0+9=9 6+7=13 9+4=13 11+0=11 |
0+13=13 8+10=18 10+6=16 11+0=11 |
|||||||||
|
0+13=13 3+8=11 4+6=10 7+4=11 11+0=11 |
0+13=13 6+9=15 9+7=16 11+4=15 13+0=13 |
0+16=16 8+13=21 10+10=20 11+6=17 12+0=12 |
|||||||||
|
0+16=16 3+13=16 4+8=12 7+6=13 11+4=15 18+0=18 |
0+18=18 6+13=19 9+9=18 11+7=18 13+4=17 15+0=15 |
0+19=19 8+16=24 10+13=23 11+10=21 12+6=18 18+0=18 |
|||||||||
2 шаг k =2. Для всех возможных значений значения и находятся в столбцах 8 и 9 соответственно; первые слагаемые в столбце 7 значения взяты из условия, вторые слагаемые взяты из столбца 5 при.
1 шаг . Условная оптимизация проведена в таблице при k =1 для.
Если, то=5; прибыль, полученная от четырех предприятий при условии, что =5 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.
Если, то=4; суммарная прибыль при условии, что =4 средств между оставшимися тремя предприятиями будут распределены оптимально, равна.
Аналогично, при, и;
При, и;
При, и;
Сравнивая полученные значения, получим при.
Вычисляя, получим, а по таблице в столбце 9 находим. Далее находим, а в столбце 6 . Наконец, и. Оптимальное решение.
Ответ. Максимум суммарной прибыли равен 24 у.е. при условии, что 1-ому предприятию выделена 1 у.е.; 2-ому предприятию выделено 2 у.е.; 3-ому предприятию - 1 у.е.; 4-ому предприятию - 1 у.е.
Реализация задачи в MS Excel
Рис.1. Ввод исходных данных в ячейки рабочего листа MS Excel
2. Порядок заполнения ячеек таблицы:
1). В ячейку E 15 введем формулу ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($C15;$B$3:$B$8);G$12+1) и скопируем формулу в диапазоне ячеек с E 15 до E 35.
2). В ячейку F 15 введем формулу
ИНДЕКС($B$3:$F$8;ПОИСКПОЗ($D15;$B$3:$B$8);5) и скопируем формулу в диапазон ячеек с F 15 до F 35.
3). В ячейку G 15 введем формулу E 15+ F 15 и скопируем формулу в диапазон: G 15 - G 35.
4). Находим максимальное значение для каждого состояния от 0 до 5, для этого в ячейку H 15 введем формулу МАКС(G15); после ввода формулы в ячейку H 16 необходимо изменить диапазон с G 16 на G 16: G 17 и т.д. по всему столбику до ячейки H 30 (Рис.2а).
3. Находим значение управления, которому соответствует максимальное значение функции, для этого в ячейку I 15 введем формулу ИНДЕКС($ C 15: G 15;ПОИСКПОЗ(H 15; G 15;0);1), скопируем формулу в ячейку I 16 и увеличим диапазон, в результате в ячейке I 16 получим: ИНДЕКС($ C 16: G 17;ПОИСКПОЗ(H 16; G 16: G 17;0);1). Далее скопируем формулу в ячейки I 18, I 21, I 25, I 30 , постепенно увеличивая диапазон (Рис.2б)
Рис.2а. Вид рабочего листа с формулами, k =3.
Рис.2б (правая часть рабочего листа с формулами, k =3
В результате получим:
Рис. 3 . Результат выполнения первого шага (k =3).
4. Выделяем диапазон E 15: I 35, выполняем команду Копировать J 15 и выполняем команду Вставить .
5. Изменим формулу функции. В ячейки K 15, K 16, K 18, K 21, K 25, K 30 введем соответственно максимальные значения предыдущего шага, находящиеся в ячейках H 15, H 16, H 18, H 21, H 25, H 30. В остальные ячейки поместим значения, стоящие в этом же столбце и соответствующие предыдущим S k . :
В ячейку K 17 копируем значения ячейки К15;
в ячейки К19 и К20 значения К16 и К17;
в К22:К24 значения К18:К20;
в К26:К29 значения К21:К24;
в К31:К35 значения К25:К29;
В результате получим:
Рис.4. Результат выполнения второго шага (k =2).
6. Выделяем диапазон ячеек J 15: N 35, выполняем команду Копировать , устанавливаем курсор в ячейку O 15, выполняем команду Вставить . В результате получаем заполненную таблицу с решением для k =1 (Рис.5)
7. Объясним полученные результаты: при. Вычисляя, получим, а по таблице в столбце 12 находим. Далее определяем, а из столбца 6 . Наконец, и. Таким образом, оптимальное значение, а значение функции 24 у.е., что согласуется с данными, полученными вручную.
Рис.6. Результат выполнения третьего шага (k =1).
Контрольные упражнения. Варианты.
1. Планируется деятельность четырех промышленных предприятий на очередной год. Начальные средства у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средства X , выделенные k -ому предприятию (), приносит в конце года прибыль. Функции заданы таблично:
|
f 1 (X) |
f 2 (X) |
f 3 (X) |
f 4 (X) |
|
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль была наибольшей.
2. Планируется деятельность трех промышленных предприятий на очередной год. Начальные средства: у.е. Размеры вложения в каждое предприятие кратны 1 у.е. Средства X , выделенные k -ому предприятию (), приносит в конце года прибыль. Функции заданы таблично:
|
f 1 (X) |
f 2 (X) |
f 3 (X) |
|
Определить, какое количество средств нужно выделить каждому предприятию, чтобы суммарная прибыль, была наибольшей.
А также другие работы, которые могут Вас заинтересовать |
|||
| 58796. | Geographical Outlook | 977.5 KB | |
| By the end of the lesson you should be able to recognize and understand new words and word combinations in the text, to read and understand the gist and details despite the natural difficulties. | |||
| 58797. | Інформація та інформаційні процеси. Обчислювальна система | 128 KB | |
| Загальна характеристика теми. Правила техніки безпеки в кабінеті ПЕОМ. Інформатика. Поняття інформації. Інформація і шум. Інформаційні процеси. Інформація й повідомлення. | |||
| 58798. | Операційні системи | 126 KB | |
| Робочий стіл. Основні об’єкти Windows. Виділення об’єкта. Операції, властивості та основні команди для роботи з об’єктами. Контекстне меню об’єкта. Ярлики та їх призначення. | |||
| 58799. | Основи роботи з дисками | 144.5 KB | |
| Загальна характеристика теми. Форматування диска. Діагностика та дефрагментація дисків. Відновлення інформації на диску. Правила записування та зчитування інформації з дискет. | |||
| 58800. | Текстовий редактор | 190 KB | |
| Системи опрацювання текстiв i їх основнi функцiї. Завантаження текстового редактора. Iнтерфейс редактора. Інформаційний рядок. Режими екрана, використання вікон. | |||
| 58801. | Графічний редактор | 708 KB | |
| Загальна характеристика теми. Машинна графiка. Графiчний екран. Система опрацювання графiчної інформації. Вказiвки малювання графiчних примiтивiв при роботi з редактором. Типи графічних файлів. | |||
| 58802. | Електронні таблиці | 280.5 KB | |
| Навчальна. Охарактеризувати нову тему, висвітлити її роль в курсі інформатики. Ввести поняття електронна таблиця. Ознайомити учнів з програмами опрацювання ЕТ, правилами введення та редагування інформації в ЕТ, способами форматування ЕТ. | |||
| 58803. | Системи управління базами даних (СУБД) | 156.5 KB | |
| Бази даних. Фактографічні й документальні БД. Iєрархiчна, мережева, реляцiйна модель бази даних. Основнi елементи та об’єкти бази даних: поле, запис, файл. СУБД. | |||
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на 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
Модель динамического программирования. Принцип оптимальности и уравнение Беллмана. Описание процесса моделирования и построения вычислительной схемы динамического программирования. Задача о минимизации затрат на строительство и эксплуатацию предприятий.
