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

Введение

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

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

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

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

Первый класс — это задачи планирования деятельности экономического объекта (предприятия, отрасли и т. п.) с учётом изменения потребности в производимой продукции во времени.

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

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

Рассмотрим основные теоретические аспекты решения задач методом динамического программирования.

Будем считать, что состояние рассматриваемой системы на — ом шаге

(1)

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

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

(2)

где .

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

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

(3)

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

Распределение капитальных вложений — это нелинейная задача распределения ресурсов между предприятиями одного производственного объединения или отрасли.

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

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

(4)

было бы наибольшим при ограничениях общей суммы ,

где — общая сумма капитальных вложений.

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

где — некоторое количество предприятий, для которых определяется параметр и функция состояния.

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

Если — количество единиц ресурса, тоое предприятие получит единиц ресурса, то остаток необходимо распределить между предприятиями отго дого так, чтобы был получен максимальный прирост прибыли или мощности Следовательно, прирост прибыли будет равен и нужно выбрать такое значениеое между 0 и, чтобы увеличение прибылипредприятий было максимальным.

1.Построение математической модели Общая сумма в 4 млн руб. распределяется между пятью предприятиями в количествах, кратных 1 млн руб. В результате выделение средств предприятию в размере оно дает доход =1,2,3,4,5 величина которого может быть найдена из таблицы № 1:

Таблица № 1. «Исходные данные»

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

1. Заполним таблицу первой итерации.

Таблица № 2. «Первая итерация»

Строку f₁ (-x₂) заполним данными первого субъекта f₁(x₁) из таблицы 1. Столбец f₂(x₂) заполним данными, соответствующими данным из таблицы 1. Незаполненные элементы таблицы находятся путем сложения элементов строки f₁ (-x₂) и столбца f₂(x₂), т. е. по формуле:

F_K(X_K) + F_K-1 (-X_K) (5)

гденекоторое количество субъектов, для которых определяются параметры и функция состояния;

— сумма капитальных вложений, выделяемая нескольким субъектам.

2. Затем находим максимумы среди элементов, полученных в результате предыдущего шага, по побочным диагоналям таблицы (максимальные элементы выделены в таблице № 2. Например, среди элементов диагонали 12,14,13,10 выберем 14.

3. После чего заполним новую таблицу данными, полученными в результате предыдущего шага. Строкаx₂() заполняется элементами столбца ресурсов из таблицы 2, соответствующих максимальным элементам побочных диагоналей, полученным на шаге 3.

Таблица № 3. «Максимальный прирост прибыли на первых двух предприятиях»

4. Заполняем «вторую итерацию»

Таблица № 4. «Вторая итерация»

Строку f₂ (-x₃) заполним данными строки F₂() из таблицы № 3. Столбец f₃(x₃) заполним данными, соответствующими данным из таблицы № 1. Незаполненные элементы находим аналогично шагу 2 (формула 5).

5. Далее снова находим максимумы среди элементов, полученных в результате предыдущего шага, по побочным диагоналям таблицы (максимальные элементы выделены в таблице № 4).

6. За тем снова заполним новую таблицу данными, полученными в результате предыдущего шага. Строка x₃() заполняется элементами столбца ресурсов из таблицы 4, соответствующих максимальным элементам побочных диагоналей, полученных на данном шаге.

Таблица № 5. «Максимальный прирост прибыли на первых двух предприятиях»

7. Заполним таблицу третьей итерации.

Таблица № 6. «Третья итерация»

Строку заполним данными строки () из таблицы № 3. Столбец f₃(x₃) заполним данными, соответствующими данным из таблицы № 1. Незаполненные элементы находим аналогично шагу 2 (формула 5).

8. Далее снова находим максимумы среди элементов, полученных в результате предыдущего шага, по побочным диагоналям таблицы (максимальные элементы выделены в таблице № 6).

9. За тем снова заполним новую таблицу данными, полученными в результате предыдущего шага. Строка x₃() заполняется элементами столбца ресурсов из таблицы 6, соответствующих максимальным элементам побочных диагоналей, полученных на данном шаге.

Таблица № 7. «Максимальный прирост прибыли на первых двух предприятиях»

Заполним «четвертую итерацию»

Таблица № 8. «Четвертая итерация»

Заполним последнюю диагональ таблицы путем сложения элементов (формула 5).

Находим максимальное число побочной диагонали, полученной на предыдущем шаге.

z_max=20 млн.рублей.

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

Пятому предприятию должно быть выделено (см. табл. 3.):

=₅(4)=0 млн руб.

причем четвертому предприятию должно быть выделено :

=₄(4−0)=₄(4)=1 млн руб.

Тогда третьему предприятию должно быть выделено (см. табл. 5.):

=₃(4—)=₃(4−0-1)=3(3)=1 млн руб.

второму предприятию должно быть выделено (см. табл. 7.):

млн. руб.

Hа долю первого предприятия остается:

млн. руб.

Таким образом, наилучшим является следующее распределение капитальных вложений по предприятиям:

которое обеспечивает производственному объединению наибольший возможный прирост прибыли:

млн. руб.

Описание решения с использованием инструментальных средств MicrosoftExcel

1.Используя данные из таблицы № 1, составим подобную таблицу в Excel.

Рисунок 1"Построение капиталовложений"

Пусть:

_j(x_j)-Прирост мощности или прибыли j-го предприятия, если оно получит xj денежных единиц капитальных вложений.

Xj-Сумма капитальных вложений в j-ое предприятие.

— Сумма капитальных вложений, выделяемая нескольким предприятиям (0 b)

Решение в Excel

Рассмотрим теперь подробнее четыре предприятия.

«Исходные данные»

f1(x1) -прирост прибыли 1-го предприятия, если оно получит капитальные вложения;

f2(x2) -прирост прибыли 2-го предприятия, если оно получит капитальные вложения;

f3(x3) -прирост прибыли 3-го предприятия, если оно получит капитальные вложения;

f4(x4) -прирост прибыли 4-го предприятия, если оно получит капитальные вложения.

Для заполнения Таблицы 2 «Первого предприятия» необходимо в Таблице1"Построение капиталовложений" сложить значения функции ₁(x₁) и ₂(x₂).

В ячейку С₁₁ внесем формулу =$B$ 11+C10

В ячейку D₁₁внесем формулу=$B$ 11+D10

В ячейку С₁₂внесем формулу=$B$ 12+C10

И т. д для всех клеток. Для заполнения остальных северо-восточной диагонали.

Рисунок 2 «Первое предприятие «

И на каждой северо-восточной диагонали выбрать наибольшее число (отмечено голубым цветом), указав соответствующие значение 2():

В ячейку С₂₃ внесем формулу =МАКС (C11)

В ячейку D₂₃ внесем формулу =МАКС (C12;D11)

В ячейку С₂₄внесем формулу =ЕСЛИ (C11=C23;A11)

В ячейку D₂₄ внесем формулу =ЕСЛИ (C12=D23;A12;A11)

И.т.д для всех остальных клеток.

Рисунок 3 «Первое предприятие максимальное значение»

Рисунок 4 «Подробное решение первого предприятия и максимальное значение»

Рисунок 5 «Второе предприятие и максимальное значение»

Рисунок 6 «Подробное решение второго предприятия и максимальное значение»

Рисунок 7 «Третье предприятие»

Таблица 8 «Подробное решение третьего предприятия»

Рисунок 9 «Четвертое предприятие»

Таблица 10 «Подробное решение четвертого предприятия»

Рисунок 11 «Z_max»

Чтобы найти Z_max, нам нужно в ячейку В₇₁ внести формулу =МАКС (C68;D67;E66;F65;G64)

2. Руководство пользователя к разработанному решению Программа «Максимизации капиталовложений» предназначена для вычисления максимально возможного суммарного прироста прибыли всех предприятий (субъектов), прироста прибыли каждого предприятия, а также количества ресурсов, которые необходимо выделить каждому предприятию, чтобы суммарный прирост прибыли был максимальным.

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

· ПК на базе процессора Intel, AMD;

· Оперативная память 128 МБ;

· Видео: совместимая VGA видеокарта;

· Операционная система Windows XP/Windows7;

· Клавиатура, мышь;

· Microsoft.NET Framework 3.0;

Для начала работы с программой запустите файл RZMK.exe. Далее вы должны заполнить пустые поля на форме данными.

Рисунок 17 «Главная форма приложения»

Для проведения операций над введенными данными необходимо воспользоваться кнопками (Рис.19):

— Результат — программа вычисляет и выводит результат.

— Сброс — очищает поля от введенных значений и ответа.

— Файл — Пример — автоматически заполняет поля вложения ресурсов и их распределения тестовыми значениями.

— О программе — вызывает информацию о программе и его разработчике Рисунок 19 «Кнопки»

После нажатия кнопки «Рассчитать» программа выдает результаты максимального суммарного прироста прибыли, прирост прибыли на каждом предприятии и количество необходимых ресурсов (Рис.20),

Рисунок 20 «Максимальный прирост прибыли и прирост прибыли и выделенные ресурсы на предприятиях «

Алгоритм решений унифицированной задачи Рисунок 24 «Алгоритм решения унифицировнанной задачи»

Заключение

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

1. Кузнецов А. М., Сакович В. А, Холод И. И. Высшая математика. Математическое программирование. Минск, Высшая школа, 2011.

2. Федосеев В. В. и др. Экономико-математические методы и прикладные модели: Учебное пособие для ВУЗов. — М:. Юнити, 2002.

3. Шикин Е. А., Чхартишвили А. Г. Математические методы и модели в управлении — М:. Дело 2010.

Приложение

unit Unit1;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, StdCtrls, Grids, Math, ExtCtrls, Menus, ShellAPI;

type

TForm1 = class (TForm)

StringGrid1: TStringGrid;

Button1: TButton;

Button2: TButton;

MainMenu1: TMainMenu;

N1: TMenuItem;

N2: TMenuItem;

N3: TMenuItem;

N4: TMenuItem;

N5: TMenuItem;

N6: TMenuItem;

procedure Button1Click (Sender: TObject);

procedure FormCreate (Sender: TObject);

procedure Button2Click (Sender: TObject);

procedure N2Click (Sender: TObject);

procedure N3Click (Sender: TObject);

procedure N4Click (Sender: TObject);

procedure N5Click (Sender: TObject);

procedure N6Click (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form1: TForm1;

MasSum:Array[0.5,0.5] of Integer; // Массив для хранение суммы

MasMax:Array[1.5,1.5] of Integer; // Массив для хранение максимальных чисел

Cells:Array[0.20] of TPoint; // Массив точек (записи координат максимальных чисел)

L:Integer;

implementation

uses Unit2;

{$R *.dfm}

procedure TForm1. FormCreate (Sender: TObject);

var

myRect: TGridRect;

I:Integer;

begin

// Смещаем фокус (выделение)

with myRect do

begin

Left:=-1;

Top:=-1;

Right:=-1;

Bottom:=-1;

end;

StringGrid1.Selection:=myRect;

// Заполняем заголовки таблицы

with StringGrid1 do

begin

Cells[0,0]: ='U';

for I:=1 to 5 do

begin

Cells[0,I]: ='L'+IntToStr (I)+'(U)';

Cells[I, 0]:=IntToStr (I-1);

end;

end;

end;

// Процедура для подсчета суммы

procedure Sum ();

var

I, J: Integer;

begin

For I:=1 to 5 do

For J:=1 to 5 do

MasSum[I, J]: =MasSum[I, 0] + MasSum[0,J];

end;

// Процедура для нахождние максимальных чисел (диагонали)

// и записи координат в массив

procedure Max ();

var

I, J, iMax, jMax: Integer;

C:TPoint;

begin

iMax:=0; jMax:=0;

For I:=5 downto 1 do

begin

MasMax[I, 1]: =MasSum[1,I];

For J:=I downto 1 do

If MasSum[I-J+1,J] >= MasMax[I, 1] then

begin

MasMax[I, 1]: =MasSum[I-J+1,J];

iMax:=I-J+1;

jMax:=J;

MasMax[I, 2]:=J-1; // В какой строке найдено максимальное знач.

end;

C.X:=jMax; C. Y:=iMax; // Координаты максимальных значений

Cells[L]: =C;

L:=L+1;

end;

end;

// Сбрасываем введенные нами значения

procedure TForm1. Button1Click (Sender: TObject);

var

I, J: Integer;

begin

For I:=1 to 5 do

For J:=1 to 5 do

Form1.StringGrid1.Cells[I, J]: ='';

Form2.Close;

end;

// Процедура подсчета итераций

// Вывод результата в таблицы

procedure TForm1. Button2Click (Sender: TObject);

var

I, J, K, C, P:Integer;

begin

Form2.Show;

L:=0; C:=0; P:=2;

while C<=6 do

begin

K:=1;

For I:=1 to 5-K+1 do

begin

For J:=1 to 5-K+1 do

begin

If C=0 then MasSum[I, 0]: =StrToInt (StringGrid1.Cells[I, 1])

else MasSum[I, 0]: =StrToInt ((Form2.Components[C-1] as TStringGrid).Cells[I, 1]);

MasSum[0,J]: =StrToInt (StringGrid1.Cells[J, P]);

(Form2.Components[C] as TStringGrid).Cells[I, 0]: =IntToStr (MasSum[I, 0]);

(Form2.Components[C] as TStringGrid).Cells[0,J]: =IntToStr (MasSum[0,J]);

Sum ();

(Form2.Components[C] as TStringGrid).Cells[I, J]: =IntToStr (MasSum[I, J]);

(Form2.Components[C+1] as TStringGrid).Cells[I, 0]: =IntToStr (K-1);

end;

K:=K+1;

end;

Max ();

for I:=1 to 5 do

begin

(Form2.Components[C+1] as TStringGrid).Cells[I, 1]: =IntToStr (MasMax[I, 1]);

(Form2.Components[C+1] as TStringGrid).Cells[I, 2]: =inttostr (MasMax[I, 2]);

(Form2.Components[C+1] as TStringGrid).Cells[0,0]: ='E';

(Form2.Components[C+1] as TStringGrid).Cells[0,1]: ='F'+IntToStr (P)+'(E)';

(Form2.Components[C+1] as TStringGrid).Cells[0,2]: ='X'+IntToStr (P)+'(E)';

end;

C:=C+2;

P:=P+1;

end;

Form2.StringGrid1.Invalidate;

// z (max)

Form2.LabeledEdit1.Text:=' '+Form2.StringGrid8.Cells[5,1];

// x5

Form2.LabeledEdit6.Text:=' '+Form2.StringGrid8.Cells[5,2];

// x4

Form2.LabeledEdit5.Text:=' '+Form2.StringGrid6.Cells[4;

StrToInt (Form2.LabeledEdit6.Text)+1,2];

// x3

Form2.LabeledEdit4.Text:=' '+Form2.StringGrid4.Cells[4;

StrToInt (Form2.LabeledEdit6.Text)-StrToInt (Form2.LabeledEdit5.Text)+1,2];

// x2

Form2.LabeledEdit3.Text:=' '+Form2.StringGrid2.Cells[4;

StrToInt (Form2.LabeledEdit6.Text);

StrToInt (Form2.LabeledEdit5.Text);

StrToInt (Form2.LabeledEdit4.Text)+1,2];

// x1

Form2.LabeledEdit2.Text:=' '+IntToStr (4;

StrToInt (Form2.LabeledEdit6.Text);

StrToInt (Form2.LabeledEdit5.Text);

StrToInt (Form2.LabeledEdit4.Text);

StrToInt (Form2.LabeledEdit3.Text));

end;

// Кнопка «Решить»

procedure TForm1. N2Click (Sender: TObject);

begin

Form1.Button2.Click;

end;

// Кнопка «Мой пример»

procedure TForm1. N3Click (Sender: TObject);

var

I:Integer;

begin

with StringGrid1 do

begin

for I:=1 to 5 do Cells[1,I]: =IntToStr (0);

Cells[2,1]:='5'; Cells[4,1]: ='11';

Cells[2,2]:='3'; Cells[4,2]: ='5';

Cells[2,3]:='7'; Cells[4,3]: ='10';

Cells[2,4]:='4'; Cells[4,4]: ='12';

Cells[2,5]:='3'; Cells[4,5]: ='7';

Cells[3,1]:='9'; Cells[5,1]: ='12';

Cells[3,2]:='4'; Cells[5,2]: ='10';

Cells[3,3]:='9'; Cells[5,3]: ='11';

Cells[3,4]:='8'; Cells[5,4]: ='14';

Cells[3,5]:='5'; Cells[5,5]: ='9';

end;

end;

// Кнопка «Сброс»

procedure TForm1. N4Click (Sender: TObject);

begin

Form1.Button1.Click;

end;

// Кнопка «Выход»

procedure TForm1. N5Click (Sender: TObject);

begin

Form1.Close;

Form2.Close;

end;

// О программе

procedure TForm1. N6Click (Sender: TObject);

begin

ShowMessage ('Программа предназначена для решения задачи' + chr (13) +

'максимизации капатиловложений' + chr (13) + chr (13) +

'Разработал студент группы 10п-1' + chr (13) +

'Урусов Алексей' + chr (13) + chr (13) +

'УАвиаК, 2013 г.');

end;

end.

unit Unit2;

interface

uses

Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,

Dialogs, Grids, Math, StdCtrls, ExtCtrls, jpeg, ColorGrd, Buttons,

ImgList;

type

TForm2 = class (TForm)

StringGrid1: TStringGrid;

StringGrid2: TStringGrid;

StringGrid3: TStringGrid;

StringGrid4: TStringGrid;

StringGrid5: TStringGrid;

StringGrid6: TStringGrid;

StringGrid7: TStringGrid;

StringGrid8: TStringGrid;

LabeledEdit1: TLabeledEdit;

LabeledEdit2: TLabeledEdit;

LabeledEdit3: TLabeledEdit;

LabeledEdit4: TLabeledEdit;

LabeledEdit5: TLabeledEdit;

LabeledEdit6: TLabeledEdit;

StaticText1: TStaticText;

StaticText2: TStaticText;

StaticText3: TStaticText;

StaticText4: TStaticText;

procedure SG_OnDrawCell (Sender: TObject; ACol, ARow: Integer; Rect: TRect; State: TGridDrawState);

procedure FormCreate (Sender: TObject);

private

{ Private declarations }

public

{ Public declarations }

end;

var

Form2: TForm2;

implementation

uses Unit1;

{$R *.dfm}

// Процедура для закрашивание максимальных элементов

// по найденным координатам

procedure TForm2. SG_OnDrawCell (Sender: TObject; ACol, ARow: Integer; Rect: TRect; State: TGridDrawState);

var

I, F, N:Integer;

Change:Boolean;

begin

F:=0; N:=0;

while F<=6 do

begin

Change:=False;

For I:=N to N+4 do

begin

If (ACol = Cells[i]. Y) and (ARow = Cells[i]. X) then

begin

Change:=True;

Break

end;

end;

If Change then

begin

(Components[f] as TStringGrid).Canvas.Brush.Color:=clRed;;

(Components[f] as TStringGrid).Canvas.FillRect (Rect);

(Components[f] as TStringGrid).Canvas.TextOut (Rect.Left, Rect. Top, (Components[f] as TStringGrid).Cells[ACol, ARow]);

end;

N:=N+5;

F:=F+2;

end;

end;

// Процедруа для смещений фокуса (выделения)

procedure TForm2. FormCreate (Sender: TObject);

var

myRect:TGridRect;

C:Integer;

begin

with myRect do begin

Left:=-1;

Top:=-1;

Right:=-1;

Bottom:=-1;

end;

for C:=1 to 8 do

(Form2.FindComponent ('StringGrid'+IntToStr (C)) as TStringGrid).Selection:=myRect;

end;

end.