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

 

 

 

СОДЕРЖАНИЕ

Введение  …………………………………………………………………………………….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)

                                                                  ⁱ⁼¹   

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

5.  Определение функции  перехода в новое состояние.

                                                         F_i(s,x)=s-x               (2.8) 

Таким образом, если на i-м шаге система находилась в состоянии s, а выбрано управление x, то на i+1-м шаге система будет находиться в состоянии s-x.  Другими словами, если в наличии имеются средства в размере s у.е., и в i-е предприятие инвестируется x у.е., то для дальнейшего инвестирования остается (s-x)  у.е.

6.  Составление функционального  уравнения для i=m.                                  

                                                     W_m(s)=f_m(s)               (2.8)

                                                      x_m(s)=s                       (2.9)

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

7.  Составление основного  функционального уравнения.

                                           W_i(s)=max{f_i(x)+W_i+1(s-x)}              (2.10)        

Пусть перед i-м шагом у инвестора остались средства в размере s  у.е. Тогда х у.е. он может вложить в i-е предприятие, при этом оно принесет доход f_i(x), а оставшиеся s-x  у.е.—в остальные предприятия с i+1-го до m-го. Условный оптимальный выигрыш от такого вложения  W_i+1(s-x). Оптимальным будет то условное управление x, при котором сумма f_i(x) и W_i+1(s-x) максимальна.

 

3. Проектирование сценария диалога

Подсистема диалога реализует  основные функции по управлению программой пользователем, отображение начальных  данных задачи (матрицы вложений), результатов  оптимизации(оптимальное количество вкладываемых ресурсов(денег, и т.д.) в предприятия и максимальный доход), состояние программы. Формы ПД,  реализующие перечисленные функции изображены на рисунках  2.1 – 2.2.

Рисунок 2.1 – сценарий диалога. Первоначальная форма.

 

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

Рисунок 2.2 – сценарий диалога. Входные и выходные данные алгоритма.

 

 

 

4. Метод оптимизации реконструкции заводов отрасли

 

Данный метод  реализован с помощью одной функции  обработки кнопки. Исходные данные для реализации этого метода берутся  из матрицы (массива, который формируется  динамически в памяти компьютера) которая задается в ручную или  загружается из файла формата  dbf,db т.е. есть возможность использовать его другими программами поддерживающими данный формат. Список переменных массивов представлен в таблице 2.3

 

Таблица 2.3 Описание идентификаторов, используемых в подпрограмме Button3Click.

Идентификатор	Тип	Назначение	Обозначение в описании метода алгоритма
smax	int	Максимальная оценка при распределении  очередного ресурса на очередном  этапе	нет
mmax	int	Максимальный доход при оптимальном  распределении	нет
ok	int *	Множестово оптимальных вложений	нет
per	int *	Множество условно оптимальных оценок	нет
i,j,ii,et,ch,ii1,etap	int	Cчетчики циклов	нет

 

    Таблица 2.3 Описание идентификаторов (продолжение) 

w	int *	Множество всех оценок на всех этапах	нет
masi	int *	Множество необходимое для начальной  подготовки матрицы	нет

 

Рисунок 2.4 - Блок-схема подпрограммы вычисления оптимального вложения .

Рисунок 2.5 - Блок-схема подпрограммы вычисления оптимального вложения.

Блок 1 выполняет инициализацию  переменных и выделение в памяти места под массивы.

Блок 2 выполняет подготовку матрицы в StringGrid1 к требуему  виду, т.е. замена надписей в верхней (0-ой) строчке “Пр. n” на 0-ли.

Блок 3 производит выполнение 1-го этапа, т.е. перенос первого столбца  из начальной матрицы в W[1][] что является условно оптимальным доходом при распределении ресурсов только на первом предприятии.

Блок 4 производит вычесление всех остальных этапов.

Блок 5 выбирает наиболее оптимальный  доход который можно получить при распределении i-ресурсов между et-предприятиями.

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

Блок 7 производит вывод на экран результатов вычесления и освобождение памяти.

 

3. ЧИСЛЕННЫЕ ЭКСПЕРИМЕНТЫ
1. Ручная реализация метода динамического программирования для задачи реконструкции отрасли

 

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

 

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

Решение

Таблица 3.1

Вложение	f(1)	f(2)	f(3)	f(4)
100	70	66	85	90
200	110	120	135	148
300	180	170	150	190
400	200	215	190	210
0	0	0	0	0

 

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

Данный метод основан  на уравнении Белмана

i=1,m 

Решение сначала.

Этап 1

Вложение капитала на первом этапе не имеет альтернативы, поэтому  в качестве условно оптимальных  вариантов решений примем f₁(x) из исходной таблицы.

W1(0)=0

W1(1)=70

W1(2)=110

W1(3)=180

W1(4)=200

 

Этап 2

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

На данном этапе происходит распределение ресурсов среди 2 предприятий.

 

        

        

 

 

Этап 3

На данном этапе происходит распределение ресурсов среди 3 предприятий.

 

        

        

Этап 4

На данном этапе происходит распределение ресурсов среди 4 предприятий.

        

        

        

2. Машинные эксперименты

 

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

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

Рисунок 3.2 – результаты решения.

 

ЗАКЛЮЧЕНИЕ

 

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

Метод динамического программирования хорош для решения задач большого объема.

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

План работ поставленных на курсовой проект был выполнен полностью.

 

 

 

 

 

 

 

 

СПИСОК ЛИТЕРАТУРЫ

1. Орлов А. И. Теория принятия решений: учебник. М.: Экзамен, 2006, 573 с.
2. Хемди А. Таха. Глава 14. Теория игр и принятия решений // Введение в исследование операций = Operations Research: An Introduction. — 7-е изд. — М.: «Вильямс», 2007. — С. 549-594.
3. С# 2005 для профессионалов. Издательство: Диалектика. 2007 г.
4. Динамическое программирование в экономических задачах.  Лежнев А.В. М.: Бином. Лаборатория знаний, 2010. — 176 с.
5. Интернет – ресурсы.

 

ПРИЛОЖЕНИЕ 

Файл “main.cpp”

//--------------------------------------------------------------#include <vcl\vcl.h>

#pragma hdrstop

 

#include "Unit1.h"

#include "Main.h"

//--------------------------------------------------------------#pragma link "Grids"

#pragma resource "*.dfm"

TMainForm *MainForm;

//--------------------------------------------------------------__fastcall TMainForm::TMainForm(TComponent* Owner)

        : TForm(Owner)

{

StringGrid1->Cells[0][0]="Пред/Влож";

 

StringGrid1->Cells[0][1]=100;

StringGrid1->Cells[0][2]=200;

StringGrid1->Cells[0][3]=300;

StringGrid1->Cells[0][4]=400;

StringGrid1->Cells[0][5]=0;

j=StringGrid1->ColCount;//j1

j1=StringGrid1->RowCount;//j

 

for (i=1;i<j1;i++){

StringGrid1->Cells[i][0]=AnsiString("Пр."+IntToStr(i));}//i;0

 

StringGrid1->Cells[1][1]=70;

StringGrid1->Cells[2][1]=66;

StringGrid1->Cells[3][1]=85;

StringGrid1->Cells[4][1]=90;

StringGrid1->Cells[1][2]=110;

StringGrid1->Cells[2][2]=120;

StringGrid1->Cells[3][2]=135;

StringGrid1->Cells[4][2]=148;

StringGrid1->Cells[1][3]=180;

StringGrid1->Cells[2][3]=170;

StringGrid1->Cells[3][3]=150;

StringGrid1->Cells[4][3]=190;

StringGrid1->Cells[1][4]=200;

StringGrid1->Cells[2][4]=215;

StringGrid1->Cells[3][4]=190;

StringGrid1->Cells[4][4]=210;

}

//--------------------------------------------------------------void __fastcall TMainForm::FileNew(TObject *Sender)

{

        //--- Add code to create a new file ---

for (k=1;k<j;k++)

for (i=1;i<j1;i++){

StringGrid1->Cells[k][i]=IntToStr(0);}//i;0

 

}

//--------------------------------------------------------------void __fastcall TMainForm::FileOpen(TObject *Sender)

{

int si,sj;

        if (OpenDialog->Execute())

        {

                //---- Add code to open OpenDialog->FileName ---

 TTable *BaseTable = new TTable(this);

 BaseTable->DatabaseName=ExtractFilePath(OpenDialog->FileName);

 BaseTable->TableName=ExtractFileName(OpenDialog->FileName);

 BaseTable->TableType=ttDefault;

 BaseTable->FieldDefs->Clear();

 BaseTable->IndexDefs->Clear();

 BaseTable->Active=false;

 BaseTable->Open();//Открыте файла базы

 BaseTable->First();

 BaseTable->Active=true;

 

    StringGrid1->RowCount=BaseTable->RecordCount+1;

    StringGrid1->ColCount=BaseTable->FieldCount+1;

 

        j1=StringGrid1->RowCount;

        j=StringGrid1->ColCount;

 

for(si=1;si<j;si++)

StringGrid1->Cells[si][0]=AnsiString("Пр."+IntToStr(si));

for(si=1;si<j1;si++)

StringGrid1->Cells[0][si]=si;

 

   //Заполнение ячеек сетки

    for(si=0;si<BaseTable->RecordCount;si++)

    {

    for(sj=0;sj<BaseTable->FieldCount;sj++)

    StringGrid1->Cells[sj+1][si+1]=AnsiString

    (BaseTable->Fields[sj]->Value);

 

    BaseTable->Next();

    }

 

 BaseTable->Close();//Закрытие файла базы

 //Уничтожение объекта описывающего структуру базы

 delete BaseTable;

 

        }

}

//--------------------------------------------------------------void __fastcall TMainForm::FileSaveAs(TObject *Sender)

{

int si,sj;

        if (SaveDialog->Execute())

        {

                //--- Add code to save current file under SaveDialog->FileName ---

 //Задание стандартных параметров структуры базы

 TTable *BaseTable = new TTable(this);

 BaseTable->DatabaseName=ExtractFilePath(SaveDialog->FileName);

 BaseTable->TableName=ExtractFileName(SaveDialog->FileName);

 BaseTable->TableType=ttDefault;

 BaseTable->FieldDefs->Clear();

 BaseTable->IndexDefs->Clear();

 BaseTable->Active=false;

//======================

 

//Задание списка полей

 for(sj=0;sj<StringGrid1->ColCount-1;sj++)

 BaseTable->FieldDefs->Add(StringGrid1->Cells[sj+1][0],ftInteger, 0, True);

 //===================

 

//Непосредственно создание файла

 BaseTable->CreateTable();

 

 BaseTable->Open();//Открыте файла базы

 BaseTable->First();

 for(si=0;si<StringGrid1->RowCount-1;si++)