Оптимизация реконструкции заводов отрасли

 

 

 

СОДЕРЖАНИЕ

Введение  …………………………………………………………………………………….4

1 Постановка  задачи……………………………………………………………………….5

1. Качественное описание исследуемой операции…………………………………5
2. Математическая постановка задачи………………………………………………..6

2  Алгоритмизация решения задачи……………………………………………….…….8

1. Анализ методов решения…………………………………………………………….8
2. Задача о распределении капиталовложений……………………………………12
3. Проектирование сценария диалога………………………………………………..14
4. Метод оптимизации реконструкции заводов отрасли…………………………..16
3. Численные эксперименты……………………………………………………………21
1. Ручная реализация метода динамического программирования для задачи реконструкции отрасли……………………………………………………………….21
2. Машинные эксперименты……………………………………………………………24

Заключение………………………………………………………………………………….25

Список  литературы…………………………………………………………………………26

Приложение  – листинг программы……………………………………………………27

 

ВВЕДЕНИЕ

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

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

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

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

 

1 ПОСТАНОВКА ЗАДАЧИ

 

1. Качественное описание исследуемой операции

 

Руководство корпорации решило провести реконструкцию n заводов. Общий объем капиталовложений c₀, выделенный для целей реконструкции, необходимо  распределить между заводами так, чтобы добиться максимального дохода при условии, что для каждого j-го завода  задана функция прибыли q_j(х_i) в зависимости от величины  х_i вложения в его реконструкцию.

	Исходные данные
Номер	Количество		Функция доходов заводов
Варианта	заводов	Вложение	1-го	2-го	3-го	4-го
7.3	4	100 200 300 400	70 110 180 200	66 120 170 215	85 135 150 190	90 148 190 210

 

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

 

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

Следовательно, если имеется  оптимальная траектория, то и любой  ее участок представляет собой оптимальную  траекторию.

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

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

  (1.1) 

  (1.2) 

при   

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

 

2. АЛГОРИТМИЗАЦИЯ РЕШЕНИЯ ЗАДАЧИ

 

1. Анализ методов решения задачи

 

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

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

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

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

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

(2.1) 

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

Будем предполагать, что  состояние   в которое перешла система   зависит от данного состояния   и выбранного управления   и не зависит от того, каким образом система   перешла в состояние 

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

(2.2) 

где 

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

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

 

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

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

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

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

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

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

(2.3) 

(2.4) 

при   

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

 

2. Задача о распределении капиталовложений

 

Инвестор выделяет средства в размере D условных единиц, которые должны быть распределены между m-предприятиями. Каждое i-е предприятие при инвестировании в него средств x приносит прибыль f_i(x) условных единиц, i=1..m. Нужно выбрать оптимальное распределение инвестиций между предприятиями, обеспечивающее максимальную прибыль.

          Выигрышем W в данной задаче является прибыль, приносимая  m-предприятиями.

1.  Определение числа  шагов.  Число шагов m равно числу предприятий, в которые осуществляется инвестирование.

2.  Определение состояний  системы. Состояние системы на  каждом шаге характеризуется   количеством средств s_i, имеющихся в наличии перед данным шагом, 

s≤D.                  (2.5)

3   Выбор шаговых  управлений. Управлением на i-м шаге x_i, x=1..m   является количество средств, инвестируемых в i-е предприятие.

4.  Функция выигрыша  на i-м шаге

                                                       f_i(x_i)                   (2.6)                        

- это прибыль, которую  приносит i-е предприятие при инвестировании в него средств

                                                                  _m   

                                                         W=∑f_ix_i,                           (2.7)

                                                                  ⁱ⁼¹