- •Глава 5. Транспортные задачи
- •5.1. Основные модели транспортных задач
- •5.1.1. Простейшая транспортная задача (т-задача)
- •5.1.2. Транспортная задача с ограниченными пропускными способностями (Td- задача)
- •5.1.3. Задачи с неоднородным грузом
- •5.1.4. Многоиндексные задачи
- •5.1.5. Транспортные задачи по критерию времени
- •5.2. Метод потенциалов
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •5.2.2. Переход от одного плана перевозок к другому
- •5.2.3. Признак оптимальности
- •5.2.4. Алгоритм метода потенциалов
- •5.2.5. Двойственная пара транспортных задач
- •5.3. Приведение открытой транспортной задачи к закрытой
- •5.4. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •5.6. Транспортные задачи в сетевой постановке (транспортные сети)
- •5.7. Задания для самостоятельной работы
5.2.5. Двойственная пара транспортных задач
Построим двойственную задачу простейшей транспортной задачи (Т-задачи). Предварительно изменим знаки в выражении критерия и в условиях по пунктам назначения. Тогда модель прямой задачи примет вид:
Здесь слева от равенств записаны сопоставленные им двойственные переменные. Модель двойственной задачи запишем по правилам, приведенным в разд. 4.11.3:
;
Если Cij перенести в левую часть, то согласно (5.19) условия двойственной задачи приобретают смысл признака оптимальностиΔij0.
Итак, если выполняются условия прямой и двойственной задач, решение оптимально. Теперь понятно, что потенциалы представляют собой переменные двойственной задачи.
Из теорем двойственности известно, что в оптимальном решении критерии прямой и двойственной задач равны. Для рассматриваемой двойственной пары это означает, что
(5.21)
Отсюда находим:
Учитывая линейность (5.21), полный дифференциал запишем в виде
Изменения ai и bj могут быть только равными, иначе нарушится сбалансированность задачи. Если положить ai= bj =1, то получим
Следовательно, разность потенциалов показывает, как изменится оптимальное значение критерия при одновременном изменении соответствующих потребностей и возможностей на единицу.
5.3. Приведение открытой транспортной задачи к закрытой
В открытой или несбалансированной задаче имеет место неравенство
.
Прежде чем решать такую задачу, необходимо привести ее к сбалансированному виду. В зависимости от ситуации сбалансировать задачу можно формальным способом без обращения к ЛПР или с привлечением дополнительной информации от ЛПР.
Рассмотрим формальные приемы. Пусть в исходной задаче предложение превышает спрос:
Тогда условия задачи имеют вид
(5.22)
(5.23)
В каждое неравенство (5.22) введем дополнительную переменную xi,n+1. В сумме эти переменные должны равняться величине дебаланса:
Добавляя это равенство к условиям (5.23), получаем закрытую задачу:
Потребность bn+1 называют фиктивной. Таким образом, чтобы сбалансировать задачу, достаточно ввести фиктивного потребителя с потребностью, равной дебалансу. Практически это означает, что к исходной таблице добавляется один столбец с потребностьюbn+1 и затратами Ci,n+1=0. Ненулевые дополнительные переменные в оптимальном решении будут показывать количество груза, остающееся в соответствующих ПО.
Второй случай несбалансированности задачи имеет место, когда спрос превышает предложение:
.
При этом исходные условия записываются в виде:
Поступаем аналогично первому случаю. Введем в каждое неравенство дополнительную переменную xm+1,j. Очевидно, что сумма этих переменных равна величине дебаланса:
С учетом этого равенства сбалансированная модель принимает вид:
Такое преобразование соответствует введению фиктивного поставщика (дополнительной строки) с возможностью am+1 и нулевыми затратамиCm+1,j. Дополнительная переменнаяxm+1,j имеет смысл количества груза, недопоставленногоj-му ПН.
Рассмотренный формальный способ будет неприемлем, если потребители по-разному реагируют на недопоставки. Тогда возможны два варианта решения задачи:
ЛПР корректирует потребности, обеспечивая баланс.
Выявляется и учитывается влияние недопоставок для каждого потребителя. Если зависимость потерь от величины недопоставки линейная, то задача остается в классе линейных. В этом случае задача балансируется как при формальном подходе, но в дополнительной строке в качестве затрат берутся удельные потери от недопоставки.
Если ожидается, что спрос будет длительное время превышать существующие возможности на величину am+1, то встает вопрос о расширении производства. Он может решаться в рамках транспортной модели следующим образом. Проектируются варианты увеличения производства, каждый на величину am+1. В исходную таблицу добавляется столько строк, сколько предлагается вариантов. При kвариантах это приведет к противоположному дебалансу, равному (k–1)·am+1. Поэтому для сбалансированности модели добавляется фиктивный потребитель с такой потребностью. А в качестве затрат во всех клетках таблицы принимаются суммарные затраты на перевозку и производство С’ij=Cij+Ci, гдеCi – себестоимость в i-м ПО. Исключение составляетфиктивный столбец:в первыхm клетках затраты равны M, а в остальных – нулю. Те варианты, которые в оптимальном решении закрепятся за фиктивным потребителем, должны быть отброшены.
При прогнозировании длительного превышения возможностей над спросом может возникнуть вопрос о сокращении производства. Он также может быть представлен в виде транспортной задачи. Достаточно в затраты включить себестоимость, как в предыдущем случае, и добавить фиктивного потребителя с потребностью bn+1 и нулевыми затратами. Оптимальные значения дополнительных переменных в фиктивном столбце дадут величину сокращения производства в соответствующих ПО с учетом полных затрат.