golunova_l_v_matematicheskie_modeli_v_transportnyh_raschetah

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

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

Для разрешающей строки выбираем наименьшее из полученных значений, то есть выбираем строку i* для х4. Разрешающим эле-

ментом будет аij* = а41* = 2.

Для удобства вычислений разрешающий элемент должен быть равен а41* = 1, поэтому все элементы разрешающей строки разделим на 2. Тогда таблица 5.3 примет вид таблицы 5.4.

Переходим к новой симплекс-таблице. Для этого меняем местами x1 и х4. Все элементы разрешающей строки умножаем на разрешающий элемент а41* = 1. Все элементы разрешающего столбца умножаем на –а41* = –1, кроме самого разрешающего элемента, который остается неизменным (таблица 5.5).

151

Так как все коэффициенты pj в таблице 5.5 положительны, решение считается найденным. Значение Z* из последней строки с противоположным знаком будет решением целевой функции, то есть

Zmin = –7 12.

Точка минимума находится в вершине с координатами (базисное решение): х1 =52 , x2 = 0, х3 = 0, х4 = 0, х5 = 6 12 , x6 = 5 12 .

Проверка: Zmin = –3x1 + х2 + 3x3 = –352 = –7 12 .

152

5.3. ПРИМЕРЫ ЗАДАЧ

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

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

На первый взгляд кажется целесообразным полностью загрузить фронт 2, так как выгрузка на нем обеспечивает станции максимальный доход. Однако из-за ограниченности ресурсов локомотиво-часов маневровой работы она не успеет выгрузить остальные вагоны. Нельзя ли распределить выгрузку по фронтам так, чтобы увеличить количество выгружаемых вагонов и при этом не снизить, а по возможности увеличить получаемый станцией доход? При этом необходима гарантия, что избранный вариант действительно оптимален. Ответ на этот вопрос дает строгое математическое решение. Сформулируем математически поставленную задачу. Обозначим число вагонов, предназначенных для выгрузки на грузовом фронте 1, – x1, на грузовом фронте 2 – x2 и на грузовом фронте 3 – x3. Тогда целевую функцию, выражающую общий доход станции от выгрузки вагонов, можно записать так:

153

Z = 3x1 + 5x2 + 4x3.

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

x1 + x2 + x3 ≤ 80.

Общее время на обработку грузовых фронтов не должно превышать ресурсов локомотиво-часов:

0,2x1 + 0,4x2 + 0,3x3 ≤ 23.

Вместимость грузовых фронтов:

x1 ≤ 35; x2 ≤ 40; x3 ≤ 25.

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

Z = 3x1 + 5x2 + 4x3 → max.

Неравенства можно привести к уравнениям, введя дополнительные неизвестные. Например, y1 – число не поданных под выгрузку вагонов, y2 – количество неиспользованных локомо- тиво-часов, y3, y4, y5 – недоиспользование вместимости грузовых фронтов. Таким образом, мы сможем привести систему линейных ограничений к каноническому виду, которую можно решить, используя вычислительный алгоритм симплексметода.

Согласно полученному решению [1, С.105–113] первый грузовой фронт надо загрузить полностью по вместимости (x1 = 35); на второй фронт подать лишь 25 вагонов (x2 = 25), недоиспользуя его вместимость на 15 вагонов (y4 = 15); а на третий фронт – 20 вагонов (x3 = 20), недогрузив на 5 вагонов (y5 = 5). Таким образом, вместимость грузового фронта 1 использована полностью (y3 = 0); неподанных вагонов нет (y1 = 0); все ресурсы локомотиво-часов также использованы (y2 = 0); обеспечен максимальный доход 310 тыс. руб.

5.4. ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

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

154

155

156

6. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

6.1. ОБЩИЕ СВЕДЕНИЯ

Динамическое программирование представляет собой ма-

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

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

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

-общий критерий – сумма частных критериев на этапах (аддитивность решения);

157

- неоднозначность результатов (многовариантность решения); Решение задач методами динамического программирования проводится на основе сформулированного Р. Э. Беллманом принципа оптимальности: оптимальное поведение обладает тем свойством, что каким бы ни было первоначальное состояние системы и первоначальное решение, последующее решение должно определять оптимальное поведение относительно состояния, полученного в результате первоначального

решения.

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

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

-поиск кратчайших расстояний на транспортной сети;

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

-разработка правил управления спросом или запасами;

-разработка принципов календарного планирования производства и выравнивания занятости в условиях колеблющегося спроса на продукцию;

-составления календарных планов текущего и капитального

ремонтов оборудования и его замены и т. д.

Сформулируем задачу динамического программирования. Пусть процесс оптимизации разбит на n шагов. На каждом шаге необходимо определить две переменные – переменную состояния S и переменную управления X. Переменная S определяет, в каких состояниях может оказаться система на данном k- м шаге. В зависимости от S на этом шаге можно применить некоторые управления, которые характеризуются переменной X. Применение управления Х на k-м шаге приносит некоторый результат Wk(S, Xk), в результате система переходит в некоторое

158

новое состояние S'(S, Хk). Для каждого возможного состояния на k-м шаге среди всех возможных управлений выбирается оптимальное управление Х*k такое, чтобы результат, который достигается за шаги с k-го по n-й, оказался оптимальным. Числовая характеристика этого результата называется функцией Беллмана Fk(S) и зависит от номера шага k и состояния системы S.

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

ется безусловной оптимизацией.

В общем виде задача динамического программирования формулируется так: требуется определить такое управление X *, переводящее систему из начального состояния S0 в конечное состояние Sn, при котором целевая функция F(S0, X *) принимает наибольшее (наименьшее) значение.

Особенности математической модели динамического программирования заключаются в следующем:

1)задача оптимизации формулируется как конечный многошаговый процесс управления;

2)целевая функция (выигрыш) является аддитивной и равна

сумме целевых функций каждого шага:

n

F = ∑ Fk(Sk–1, Xk);

k=1

3)выбор управления Хk на каждом шаге зависит только от состояния системы к этому шагу Sk–1 и не влияет на предшествующие шаги (нет обратной связи);

4)состояние системы Sk после каждого шага управления зависит только от предшествующего состояния системы Sk–1 и этого управляющего воздействия Хk (отсутствие последействия) и может быть записано в виде уравнения состояния:

Sk = fk(Sk–1, Xk), k = 1,n;

5)на каждом шаге управление Хk зависит от конечного числа управляющих переменных, а состояние системы Sk зависит от конечного числа параметров;

159

6)оптимальное управление представляет собой вектор X *, оп-

ределяемый последовательностью оптимальных пошаговых управлений: X = (X1*, X2*, …, Xk*, …, Xn*), число которых и определяет количество шагов задачи.

Условная оптимизация

На данном этапе в соответствии с алгоритмом обратной прогонки для всех возможных состояний каждого шага, начиная с последнего, находят функцию Беллмана и оптимальные управления. На последнем n-м шаге надо найти оптимальное управление Xn* и значение функции Беллмана Fn(S) = max{Wn(S, Xn)}, где максимум ищется по всем возможным зна-

чениям Xn.

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

Этот максимум (или минимум) определяется по всем возможным для k и S значениям переменной управления X.

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

После того как функция Беллмана и соответствующие оптимальные управления найдены для всех шагов с n-го по первый (на первом шаге k = 1 состояние системы равно ее начальному состоянию S0), осуществляется второй этап решения задачи. Находится оптимальное управление на первом шаге X1, применение которого переведет систему в состояние S1(S, x1*). Зная это состояние можно, пользуясь результатами условной оптимизации, найти оптимальное управление на втором шаге, и так далее до последнего n-го шага.

6.2. ВЫБОР ОПТИМАЛЬНОГО ПУТИ В ТРАНСПОРТНОЙ СЕТИ

В задаче о кратчайшем пути на сети дорог, состоящей из n узлов, некоторые из которых соединены магистралями, требуется найти оптимальный маршрут из 1-го пункта в n-й. Стоимость проезда (стоимость перевозки груза, расстояние между пунктами) известна.

Рассмотрим решение данной задачи на конкретном приме-

160