Возможные варианты построения цикла перераспределения

 

 

В нашем случае форма цепи простая. Однако цепь может иметь любую форму, в том числе и причудливую (см. табл. 2.7). Её нужно научиться отыскивать, используя эвристические подходы. При этом необходимо учитывать, что каждая небазисная клетка транспортной матрицы обязательно имеет одну цепь перераспределения поставок.

Операция 3.2. Перераспределение поставок.

Перераспределение поставок (см. табл. 2.6) производится по цепи. Вначале определим объем перераспределения поставок. Для этого присвоим клеткам – вершинам цепи – знаки. В небазисную клетку А₂В₄ ставим «+», поскольку в нее будет вводиться поставка. Далее, чередуя «+» с «–», расставляем знаки по остальным вершинам контура. Величина объема перераспределения поставок принимается равной минимальной поставке в отрицательной клетке. Для нашего случая это 50 единиц груза. Перераспределение заключается в том, что к поставкам в положительных клетках найденный объем прибавляется, а для отрицательных клеток отнимается. Результат представлен в табл. 2.6.

Функционал F' нового плана, представленного в табл. 2.6 (выделенные поставки), составляет 1950 ткм, что на 200 ткм меньше значения функционала F предыдущего плана.

Полученный улучшенный план, представленный в табл. 2.6, в свою очередь, требует проверки на оптимальность, поэтому необходимо вернуться к операции 2.

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

Таблица 2.8

Повторение операций 2, 3

 

 

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

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

Проверка плана на оптимальность свидетельствует о том, что для двух клеток условия оптимальности не выполняются. После перераспределения поставок по клетке А₄В₃, получаем новый план (табл. 2.9).

 

Таблица 2.9

Оптимальный план поставок

 

Проверка плана перевозок на оптимальность по условию (2.8) показала, что для всех небазисных клеток матрицы условия оптимальности выполняются. Функционал F'' оптимального плана равен 1920 ткм. Таким образом, получен план перевозок, обеспечивающий минимальный объем перевозочной работы для транспортировки всего груза между станциями погрузки и выгрузки.

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

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

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

Пусть, например, процесс управления некоторой системой состоит из m шагов (этапов), на i-м шагу управление y_i переводит систему из состояния x_i-1 в новое состояние x_i, которое зависит от x_i-1 и y_i:

x_i = x_i(y_i, x_i-1).

Т. о., управление у₁, у₂, ..., у_m переводит систему из начального состояния x₀ в конечное х_m. Требуется выбрать x₀ и у₁, ..., у_mтаким образом, чтобы целевая функция F = å^m_i=1 j_i (x_i-1, y_i) достигла максимального значения F*. Основным методом Д. п. является сведение общей задачи к ряду более простых экстремальных задач. Пользуясь так называемым принципом оптимальности, сформулированным американским математиком Р. Беллманом, легко получить основное функциональное уравнение:

и                                                              (k = 2, ..., m - 1)

f₁(x₀) = F*,

где

(k = 1, ..., m).

Т. о., метод Д. п. приводит к необходимости решения этой рекуррентной системы функциональных уравнений. В процессе решения последовательность этапов проходится дважды: в приведённом варианте рекуррентной системы в первый раз от конца к началу (находятся оптимальные значения F* и х*₀), второй раз — от начала к концу (находятся оптимальные управления y*₁, ..., у*_m).

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

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