Оптимальное распределение ресурсов методом динамического программирования

Дадим математическую формулировку принципа оптимальности. Для простоты будем считать, что  начальное x₀ и конечное x_T состояния системы заданы. Обозначим через z₁(х₀, u₁) значение функции цели на первом этапе при начальном состоянии системы x₀ и при управлении u₁, через z₂(х₁,u₂) – соответствующее значение функции цели только на втором этапе, ..., через 
z_i(х_i-1,u_i) – на i-м этапе, ..., через z_N(х_N-1, u_N) —на N-м этапе. Очевидно, что

Z = =  (1)

Надо найти  оптимальное управление u*= ( ; ;...; ), такое, что доставляет экстремум целевой функции (1) при ограничениях .

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

 

 

 

определения для подобных задач на последнем этапе, двух последних  и т. д.; 
– область определения исходной задачи. Обозначим через F₁(x_N-1), F₂(x_N-2), …, F_k(x_N-k), …, F_N(x₀) соответственно условно-оптимальные значения функции цели на последнем этапе, двух последних и т. д., на k последних и т. д., на всех N этапах.

Начинаем  с последнего этапа. Пусть х_N-1 – возможные состояния системы на начало N-го этапа. Находим:

F₁(x_N-1) = z_N(x_N-1, u_N). (2)

Для двух последних  этапов получаем

F₂(x_N-2) = (Z_N-1(x_N-2, u_N-1) + F₁(x_N-1)). (3)

Аналогично:

F₃(x_N-3) = (Z_N-2(x_N-3, u_N-2) + F₂(x_N-2)). (4)

………………………………………………….

F_k(x_N-k) = (z_N-k+1(x_N-k, u_N-k+1) + F_k-1(x_N-k+1)). (5)

…………………………………………………..

F_N(x₀) = (z₁(x₀, u₁) + F_N-1(x₁)). (6)

Выражение (6) представляет собой математическую запись принципа оптимальности. Выражение (5) – общая форма записи условно-оптимального значения функции цели для k оставшихся этапов. Выражения (2) – (6) называются функциональными уравнениями Беллмана. Отчетливо просматривается их рекуррентный (возвратный) характер, т. е. для нахождения оптимального управления на N шагах нужно знать условно-оптимальное управление на предшествующих N – 1 этапах и т. д. Поэтому функциональные уравнения часто называют рекуррентными (возвратными) соотношениями Беллмана.

1. Особенности задач динамического программирования

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

• Рассматривается система, состояние которой на каждом шаге определяется вектором x_t. Дальнейшее изменение ее состояния зависит только от данного состояния x_t и не зависит от того, каким путем система пришла в это состояние. Такие процессы называются процессами без последействия.
• На каждом шаге выбирается одно решение u_t, под действием которого система переходит из предыдущего состояния x_t-1 в новое х_t. Это новое состояние является функцией состояния на начало интервала x_t-1 и принятого в начале интервала решения u_t, т. е. x_t = x_t(x_t-1,u_t).
• Действие на каждом шаге связано с определенным выигрышем (доходом, прибылью) или потерей (издержками), которые зависят от состояния на начало шага (этапа) и принятого решения.
• На векторы состояния и управления могут быть наложены ограничения, объединение которых составляет область допустимых решений .
• Требуется найти такое допустимое управление u_t для каждого шага t, чтобы получить экстремальное значение функции цели за все Т шагов.

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

Геометрическая  интерпретация задачи динамического  программирования состоит в следующем. Пусть n – размерность пространства состояний. В каждый момент времени координаты системы имеют вполне определенное значение. С изменением времени t могут изменяться значения координат вектора состояния. Назовем переход системы из одного состояния в другое траекторией ее движения в пространстве состояний. Такой переход осуществляется воздействием на координаты состояния. Пространство, в котором координатами служат состояния системы, называется фазовым. Особенно наглядно задачу динамического программирования можно интерпретировать в случае, если пространство состояний двухмерно. Область возможных состояний в этом случае изобразится некоторой фигурой , начальное и конечное состояния системы – точками х₀, , (рис. 1). Управление – это воздействие, переводящее систему из начального состояния в конечное. Для многих экономических задач не известно начальное либо конечное состояние, а известна область X₀ или X_T, которой эти точки принадлежат.

Рисунок 1

Тогда допустимые управления переводят точки  из области Х₀ в X_T. Задача динамического программирования геометрически может быть сформулирована следующим образом: найти такую фазовую траекторию, начинающуюся в области Х₀ и оканчивающуюся в области Х_T, для которой функция цели достигает экстремального значения. Если в задаче динамического программирования известны начальное и конечное состояния, то говорят о задаче с закрепленными концами. Если известны начальные и конечные области, то говорят о задаче со свободными концами.

2. ЗАДАЧА РАСПРЕДЕЛЕНИЯ РЕСУРСОВ

2.1 Общая постановка задачи

  Рассмотрим применение метода динамического программирования на примере распределения средств между шестью объектами реконструкции предприятия горводоканала:

1. Центральная насосно-фильтровальная  станция;

2. Восточная насосно-фильтровальная  станция;

3. Водопроводная насосная станции  перекачки;

4. Центральная станция аэрации;

5. Восточная станция аэрации;

6. Загородная станция аэрации.

Общая сумма средств, предоставленная  на развитие составляет не более 195 тысяч  гривен. На основе технико-экономических  расчетов установлено, что в результате реконструкции в зависимости  от количества потраченных средств  объекты будут иметь производительность, приведенную в таблице 1.1. Необходимо определить оптимальное распределение средств между объектами реконструкции, которая обеспечит максимальное увеличение производительности этих объектов. Таким образом, в этой задаче используется критерий оптимизации - суммарная производительность предприятий объектов реконструкции.

 

 

 

 

 

 

 

Таблица 1.1 Входные данные продуктивности объектов реконструкции

Порядковый номер объекта	Объем ресурсов, выданных на развитие объектов (тыс. грн.)
	0	15	30	45	60	75	90	105	120	135	150	165	180	195
	Продуктивность объектов  результате развития (тыс. м3)
1	2250	3300	3320	3330	3340	3350	3360	4400	4430	4440	4450	4460	4470	4490
2	1100	2200	3300	3350	4400	5500	7700	9900	11100	11440	11450	11500	11600	11610
3	3330	4450	4460	4470	5520	5530	5540	5550	5560	5570	5580	6600	6620	6630
4	1160	2260	3310	3360	3370	4410	4430	4440	4460	4480	5500	5510	5570	6610
5	8850	11230	22010	22090	33170	33750	44000	44010	55000	55050	55100	55200	55300	55400
6	445	547	669	881	993	1105	1117	1129	1141	1153	1165	1177	1189	2201

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

2. Блок схема программы

Рисунок 1. Основная программа

          QtObj – количество объектов

          QtRes – количество ресурсов

effMatrix  - матрица                                        производительности объектов,

distVector – вектор выделенных              ресурсов

нет  да

 

 Шаг 1. Условная оптимизация

 

 

 

 Шаг 2. Безусловная оптимизация

 I = QtObj-1,0 формируем вектор результат

 

 

да нет

 

 

 

 

 

Рисунок 2. Ввод данных

                                                           distVector – вектор дистанций,               effMatrix = матрица производительности

 

      

 

да нет

 если все элементы матрицы введены

да  нет

если  вектор   производительности- не

отрицательный

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 3. Условная оптимизация,

формируем мартицу выхода (максимум функции  цели)

                                                               outMatrix – матрица максимума цели

                                            QtObj – количество объектов

                                           QtRes – количество ресурсов

                                                        Matrix – матрица производительности

                                                  distVect – вектор дистанций (вектор  ресурсов)

 нет да Если первое предприятие

 

 

 

 нет

 

 

 

Поиск максимума

 нет

 

 да maxItem = temp; outMatrix[i][j] = maxItem

3. Структура алгоритма программы

1. Ввод данных – класс DataDlg.

Переменные члены класса.

          //вектор для хранения объема  ресурсов

         std::vector<int> distVector;

 

   //матрица производительности объектов 

               int**  effMatrix;

 

          //функция  перевода строки в число

           int  StringToInt(CString);

 

          //функция  проверки корректности введенных  данных

            BOOL FillMatrix();

 

           //функция  очистки ресурсов, после закрытия  окна

            virtual BOOL DestroyWindow();

     

           //функция  инициализации диалога

              virtual BOOL OnInitDialog();

 

 

2. Вычисление результатов – основной класс программы courseWorkDlg

Переменные члены  класса

struct Item

{

 int Value;  //значение производительности

   int MaxIndex;// максимальный индекс в векторе ресурсов

 

};

struct Result

{

int Facility;//предприятие

int  Recource;//выделенный ресурс

};

 

           Item ** outMatrix; //матрица максимума цели

             std::vector<Result> resVector; //вектор результатов

 

             void BuildOutMatrix(int **,std::vector<int>);//функция формирования матрицы цели     (условная оптимизация)

 

               afx_msg void OnBnClickedButton1();//обработчик нажатия на кнопку «Вычислить»,   который запускает процесс вычислений.

 

                virtual BOOL DestroyWindow();//очистка ресурсов программы

 

3. Вывод результатов класс Report

Назначение данного класса – это вывод вектора результата в табличной форме.

 

2.4 Результаты работы программы

Начальный ввод данных

 

 

 

 

 

 

 

 

 

3. Ввод данных о продуктивности объектов реконструкции

1. Если не все поля заполнены

2. Если введен неправильный символ

 

 

Корректный ввод данных

Показ результата

 

 

 

Пример 2.

1. Ввод данных

Результат работы программы

 

 

 

 

Пример 3.

Начальный ввод данных

Ввод продуктивности объектов

 

 

 

Отчет

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Приложение.

Листинг программы

DataDlg.cpp

int DataDlg::StringToInt(CString str)

{

const wchar_t* s = T2CW(str);

int val = _wtoi(s);

return val;

}

 

// все поля заполнены ?

BOOL DataDlg::FillMatrix()

{

bool flag = true;

for (int i = 0; i < Cells.GetSize(); i ++){

for (int j = 0 ; j < Cells.GetAt(i)->Edits.GetSize(); j ++){

CString str;

CEdit * temp = Cells.GetAt(i)->Edits.GetAt(j);

 if (temp->m_hWnd != NULL){

temp->GetWindowText(str);

 if (str.IsEmpty()){

MessageBox(L"Нужно заполнить все поля", L"Ошибка", MB_ICONERROR | MB_OK);