5.5. Решение задачи по критерию времени

Как было показано в разд. 5.1.5, такая задача исходно является нелинейной, но может быть легко преобразована к линейной. Однако получаемая линейная модель громоздка и для нахождения решения требует применения универсальных методов линейного программирования.

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

Любым из способов строится начальный план перевозок. Затем определяется текущее значение критерия Т⁽⁰⁾ как максимальное время в занятых клетках (x_ij>0). Далее рассмотрим действия в цикле.

Пусть на k-й итерации получен план со значением критерия Т^(k). Оно может быть уменьшено, если освободить клетку с t_ij= Т^(k). С этой целью на клетке строится разгрузочный цикл так, чтобы в нечетных вершинах выполнялось неравенство t_ij<Т^(k), а в четных – x_ij>0 (исходная вершина – четная). Очевидно, что такие правила позволяют в общем случае строить более одного цикла на выбранной клетки. В цикле вычисляется ₀ как минимальная перевозка в четных вершинах. Вычитая ₀ в четных вершинах и прибавляя в нечетных, получаем новый план. Если клетка с максимальным временем была единственной и перевозка в ней стала равна нулю, новый план улучшил значение критерия. Если клетка не обнулилась, то на ней строится другой разгрузочный цикл. В случае нескольких клеток со временем Т^(k) для улучшения критерия необходимо разгрузить все. Решение завершается, когда нельзя разгрузить клетку (клетки), определяющую значение критерия.

Естественно, что рассмотренный метод не гарантирует получение оптимального решения.

26. Приведение открытой транспортной задачи к закрытой

В открытой или несбалансированной задаче имеет место неравенство

.

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

Рассмотрим формальные приемы. Пусть в исходной задаче предложение превышает спрос:

Тогда условия задачи имеют вид

(5.22)

(5.23)

В каждое неравенство (5.22) введем дополнительную переменную x_i,n+1. В сумме эти переменные должны равняться величине дебаланса:

Добавляя это равенство к условиям (5.23), получаем закрытую задачу:

Потребность b_n+1 называют фиктивной. Таким образом, чтобы сбалансировать задачу, достаточно ввести фиктивного потребителя с потребностью, равной дебалансу. Практически это означает, что к исходной таблице добавляется один столбец с потребностью b_n+1 и затратами C_i,n+1=0. Ненулевые дополнительные переменные в оптимальном решении будут показывать количество груза, остающееся в соответствующих ПО.

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

.

При этом исходные условия записываются в виде:

Поступаем аналогично первому случаю. Введем в каждое неравенство дополнительную переменную x_m+1,j. Очевидно, что сумма этих переменных равна величине дебаланса:

С учетом этого равенства сбалансированная модель принимает вид:

Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью a_m+1 и нулевыми затратами C_m+1,j. Дополнительная переменная x_m+1,j имеет смысл количества груза, недопоставленного j-му ПН.

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

1. ЛПР корректирует потребности, обеспечивая баланс.

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

Если ожидается, что спрос будет длительное время превышать существующие возможности на величину a_m+1, то встает вопрос о расширении производства. Он может решаться в рамках транспортной модели следующим образом. Проектируются варианты увеличения производства, каждый на величину a_m+1. В исходную таблицу добавляется столько строк, сколько предлагается вариантов. При k вариантах это приведет к противоположному дебалансу, равному (k–1)·a_m+1. Поэтому для сбалансированности модели добавляется фиктивный потребитель с такой потребностью. А в качестве затрат во всех клетках таблицы принимаются суммарные затраты на перевозку и производство С^’_ij=C_ij+C_i, где C_i – себестоимость в i-м ПО. Исключение составляет фиктивный столбец: в первых m клетках затраты равны M, а в остальных – нулю. Те варианты, которые в оптимальном решении закрепятся за фиктивным потребителем, должны быть отброшены.

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