8. Транспортная задача: понятие базисного плана перевозок.

Символом U обозначим множество клеток транспортной задачи:

Пусть - произвольное подмножество клеток транспортной таблицы. Попытаемся соединить между собой клетки из U₁ вертикальными и горизонтальными звеньями замкнутой ломаной линии. При этом в клетках из U₁ ломаная обязательно должна менять направление. Если это удалось, то будем говорить, что клетки множества U₁ образуют цикл.

Множество клеток будем называть базисом транспортной таблицы, если оно удовлетворяет следующим условиям:

1) никакие клетки из U_б не образуют между собой циклов;

2) любая клетка из (не базисная клетка) образует с базисными клетками цикл.

План транспортной задачи будем называть базисным, если заполненные клетки образуют базис.

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

9. Методы построения начального базисного плана.

а) метод северо-западного угла

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

Если поставщиков больше, то в таблицу добавляется фиктивный потребитель (цена перевозок 0).

Если поставщиков больше, чем потребителей, в таблицу добавляется фиктивный поставщик с ценой перевозок 0.

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

Поскольку на каждой итерации алгоритма после заполнения клетки вычеркивались строка или столбец (или и строка и столбец вместе), то заполненные клетки не образуют между собой циклов. Поэтому необходимое условие базисности автоматически становится достаточным: для того, чтобы заполненные клетки образовывали базис транспортной таблицы их должно быть n+m-1. Для того чтобы он стал базисным необходимо дополнить его фиктивно заполненной (нулем) клеткой.

б) метод минимального элемента

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

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

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

Простое увеличение объема поставок в одной отдельно взятой клетке невозможно – оно приведет к нарушению ограничений.

Чтобы разрешить эту проблему, используем клетки цикла. Раз объем поставки в клетке (i,j) увеличился на 1, уменьшим на эту же величину объем поставки в клетке (l,j). Благодаря этому суммарный объем поставок в j-ом столбце останется неизменным и соответствующее ему ограничение не нарушится. Зато нарушится баланс в l-ой строке – сумма поставок уменьшится на единицу. Поэтому увеличим на 1 объем поставки от l-ого поставщика к k-му потребителю. Это изменение, в свою очередь, повлечет за собой уменьшение на 1 поставки в клетке (i,k) – и цикл замкнулся, все изменения взаимно компенсировали друг друга. Такое свойство характерно для любого цикла в транспортной таблице.

Поскольку план перевозок изменился, то в общем случае изменились и транспортные затраты. Подсчитаем величину этого изменения, обозначив его через Δ_ij. Объем перевозок в клетке (i,j) увеличился на единицу, следовательно затраты, связанные с этой клеткой возросли на c_ij денежных единиц. В клетке (l,j) объем перевозок снизился на 1, а поэтому транспортные затраты уменьшились на c_lj денежных единицу. И т.д. В клетках транспортной таблицы, не вошедших в цикл, объемы поставок не изменились, а поэтому они не участвуют в формировании величины Δ_ij. Следовательно,

Δ_ij=с_ij-c_lj+c_lk-c_ik.

Обойдем клетки цикла, начиная с клетки (i,j), в определенном направлении, например, по часовой стрелке, и пометим их по очереди знаками «+» и «-» (начнем с клетки (i,j), которую пометим знаком «+»). Введем следующие обозначения: - множество клеток цикла, помеченных знаком «+», - множество клеток цикла, помеченных знаком «-». Тогда .

Величина Δ_ij играет очень важную роль в исследовании транспортных задач и имеет простую экономическую интерпретацию: она показывает, как реагирует целевая функция

задачи на единичное изменение объема поставки в небазисной клетке. Если Δ_ij>0, то с увеличением x_ij транспортные затраты увеличиваются, с уменьшением - уменьшаются; если Δ_ij<0, то при увеличении x_ij транспортные затраты снижаются, при уменьшении - уменьшаются; при Δ_ij=0, то целевая функция не чувствительна к изменению x_ij. Поэтому ее называют оценкой небазисной клетки.

По предположению X – базисный план перевозок. Так как (i,j)- небазисная клетка, то x_ij=0. Это означает, что в небазисной клетке возможно только увеличение объема поставок. Поэтому транспортные затраты можно уменьшить только в том случае, если среди оценок небазисных клеток есть хотя бы одна отрицательная. Если все оценки неотрицательны, то добиться уменьшения целевой функции невозможно. Последнее означает оптимальность базисного плана транспортной задачи. Таким образом, справедливо следующее утверждение:

Теорема (достаточное условие оптимальности базисного плана): если о базисный план перевозок оптимален.