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

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

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++)