Статья: Применение метода динамического программирования для решения задачи управления процессом забора оросительной воды

УДК 626.82.004:519.71

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

В. В. Васильев (ФГБОУ ВПО «КубГАУ»)

Ю. Е. Домашенко, С. М. Васильев (ФГБНУ «РосНИИПМ»)

Аннотация

мобильный лимит забор оросительный

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

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

Annotation

The paper deals with mathematical apparatus based on the method of dynamic programming. This method allows using the volume of unspent limit for irrigation withdrawal at specific weather conditions. The method of dynamic programming is based on the Bellman's principle of optimality, which formulated as following: control at every step should be chosen so that the sum of advantages was the optimal at all remaining until the end of the process steps including the advantage at the given step. According to the stated principle the dynamic programming is a directed linear search of possibilities which obligatory leads to a global maximum. The method of dynamic programming enables to create a mobile mechanism controlling irrigation withdrawal limits for variant planning and correcting water use plans at irrigation systems.

Keywords: dynamic programming, water use, irrigation withdrawal limit, volume of irrigation withdrawal limit, Bellman's functional equation.

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

Как раздел математического программирования динамическое программирование начало развиваться в 50-х годах XX века благодаря работам Р. Беллмана и его сотрудников [1]. Как практический метод оптимизации метод динамического программирования стал возможен лишь при использовании современной вычислительной техники.

В настоящее время разработан ряд методик планирования водопользования с использованием современной компьютерной техники и программного обеспечения. Существующая методика САНИИРИ адаптирована для аридной зоны орошения, но, к сожалению, выбор критериев оптимальности для указанной зоны не позволяет перенести полученные результаты для зоны Северного Кавказа [2]. Особый интерес вызывает методика УкрНИИГиМ по созданию информационно-советующей системы планирования водопользования [3].

На сегодняшний день метод динамического программирования позволяет решать задачи планирования внутрихозяйственного водопользования без учета климатических факторов. Достаточно совершенную, но сложную в реализации методику планирования водораспределения предлагают А. И. Голованов и И. П. Айдаров [4]. Она предполагает введение функциональных связей фактора урожай-вода и прочих факторов, влияющих на урожайность сельскохозяйственных культур, что будет являться основой для решения многоуровневой оптимизационной задачи.

Рассмотрим функционирование оросительной системы в течение календарных этапов водохозяйственного планирования. Каждый -й этап () характеризуется следующими параметрами:

- (величина лимита на забор оросительной воды, оставшаяся в распоряжении учреждения после окончания -го этапа);

- (объем производства сельскохозяйственной продукции агропредприятия на -м этапе);

- (величина спроса на сельскохозяйственную продукцию агропредприятия на -м этапе).

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

Данный критерий запишем в виде уравнения:

.

Имеющиеся ограничения представим в следующем виде:

- установление объема лимитов на забор оросительной воды в конце -го периода:

,

,

,

;

- удовлетворение спроса водопотребителей в -м периоде:

, .

Для решения этой задачи методом динамического программирования необходимо определить основные компоненты:

- этапы - календарные периоды деятельности сельхозпредприятия ;

- состояние - объем лимитов на забор оросительной воды в конце -го периода;

- управление - планируемый объем производства сельскохозяйственной продукции в -м периоде;

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

;

- оператор подхода, который устанавливает связь между объемом лимитов на забор оросительной воды в конце-1-го и -го этапов:

.

Для этих целей введем функцию:

.

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

Тогда функциональное уравнение Беллмана примет следующий вид:

. (1)

Решение функционального уравнения Беллмана производится, начиная с первого этапа, т. е. переменная последовательно полагается 1, 2, 3, …, .

Решение уравнения Беллмана для данного случая будет осуществляться следующим образом:

,

где - величина лимита на забор оросительной воды на -ом этапе в объемах ;

- величина лимита после окончания n-го этапа;

- коэффициент;

- начальная величина лимитов оросительной воды;

- резервная величина лимитов на начальном этапе в объеме .

На первом этапе функциональное уравнение (1) при примет вид:

.

В полученном уравнении все величины являются известными. Для решения этого уравнения согласно Г. А. Черноморову и С. П. Воробьеву [5] формируется исходная информация.

Алгоритм заполнения таблицы результатов динамического программирования предполагает, что столбцы таблицы соответствуют начальной величине лимитов на забор оросительной воды, строки - объему производства овощной продукции на первом этапе . Каждая ячейка таблицы делится на две части: в нижней записывается значение состояния, т. е. значение для переменной : . В этом случае, если принимает отрицательное значение, то такие состояния являются недопустимыми и исключаются от рассмотрения путем вычеркивания. В частности, для положительного спроса > 0 клетка для = 0 и = 0 является отрицательной и недопустимой. Таким образом, первым допустимым состоянием является значение = 0. В верхней части каждой из ячеек записывается значение функции:

.

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

На втором этапе принятия решений () функциональное уравнение Беллмана имеет следующий вид:

,

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

, - исходные данные.

Данные записей оформляются в виде таблицы 1.

Таблица 1 - Пример оформления результатов динамического программирования

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

.

Затем находятся одинаковые состояния и для них вычисляется условно оптимальное значение функции величины лимитов . Таким образом, после окончания второго этапа для каждого из допустимых состояний должна быть определена функция величины лимитов , а также значение объема производства и лимитов . Аналогичные действия выполняются для всех этапов, пока = .

В качестве примера реализации метода динамического планирования определим оптимальный план величины лимитов оросительной воды для производства картофеля в ООО «Ольгинское». Установим, что количество интервалов планирования = 5 [6], величина спроса на продукцию постоянна для всех этапов планирования:

, и ,

лимиты на начальном этапе , ограничения на производственные мощности = 5 (2500 м³/га - максимальная оросительная норма для картофеля в засушливые годы, 5 - число поливов в засушливые годы), ограничение на предельный уровень величины лимитов на конец рассматриваемого периода = 3 (1100 м³/га - минимальная оросительная норма для картофеля в засушливые годы, 500 м³/га - поливная норма картофеля).

Решение уравнения Беллмана будет основываться на алгоритме прямой прогонки:

, , , , .

Для выполнения первого этапа формируется промежуточная таблица 2. Для примера произведем вычисление функции :

,

Таблица 2 - Результаты расчетов неизрасходованных лимитов

На основе промежуточной таблицы 2 формируется окончательная таблица 3.

Таблица 3 - Окончательный вариант расчета лимитов оросительной воды в течение поливного сезона

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

Для нахождения оптимальных объемов производства и оптимальных уровней лимитов на забор оросительной воды h_n производится решение задачи в обратном порядке. На последнем этапе ( = ) выбираются и h_n , соответствующие оптимальной (минимальной) функции затрат f_n(h_n). На этапах < выбираются строки, для которых и h_n такие, чтобы |b_n - y_n+1| = h_n. Обратное решение задачи производится до этапа .