Свойства транспортной задачи

1. Ранг матрицы из коэффициентов при неизвестных системы ограничений ТЗ равен m + n – 1, где m и n – количество поставщиков и потребителей соответственно.

2. ТЗ всегда имеет оптимальный план.

3. В ТЗ всегда существуют допустимые планы, содержащие не более

m + n – 1 положительных элементов.

4. Если в ТЗ все числа a_i , b_j целые, то она имеет оптимальный целочисленный план.

Решение (план перевозок) назовем допустимым, если оно удовлетворяет системе ограничений (8), опорным, если в нем отличны от нуля не более

m + n – 1 базисных переменных, остальные равны нулю.

Решение ТЗ разобьем на три этапа:

· определение первоначального допустимого решения;

· проверка найденного решения на оптимальность (оценка плана по критерию стоимости). Если оно оптимальное, то ТЗ решена;

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

3.3. Методы нахождения начального плана перевозок

Клетки матрицы перевозок, где , называются базисными, а остальные, где – свободными.

В матрице есть m + n – 1 базисных клеток. Их число совпадает с числом независимых уравнений – ограничений.

Значение в матрице перевозок находится по формуле:

(11)

Значение в свободной клетке не пишется явно, а вместо этого в ней ставится точка.

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

Вычисление проводим по формуле (11), начиная с элемента x₁₁, стоящего в северо-западном углу матрицы перевозок.

Пример 3. Найти начальный план перевозок в ТЗ методом северо-западного угла

Запишем матрицу перевозок (табл. 3.2).

Таблица 3.2

Bj Ai	B1	B2	В3	B4	Запасы ai
A1			*
A2	*
A3		*	*
Потребности bj

Начинаем с северо-западного угла, т. е.

.

Тогда в пункте B₁ потребности удовлетворены, и, следовательно, (в табл. 3.2 ставится точка (*)). Первый столбец выбывает из рассмотрения.

Продолжаем с северо-западного угла, т.е.

.

Запасы в пункте А₁ исчерпаны и (в табл. 3.2 ставится точка). Первая строка таблицы выбывает из рассмотрения.

Продолжаем с северо-западного угла:

.

Потребности в пункте В₂ удовлетворены, второй столбец выбывает из рассмотрения.

Продолжаем с северо-западного угла:

и .

Третий столбец выбывает из рассмотрения.

.

Запасы в пункте А₂ исчерпаны.

.

Получен начальный план перевозок:

с суммарной стоимостью

.

Число базисных клеток m + n – 1 = 3 + 4 – 1 = 6.

Примечание. При нахождении начального плана перевозок возможен случай вырождения, когда в результате вычислений значения x_ij получается, что потребности в пункте B_j удовлетворены, а запасы в пункте A_i исчерпаны. Тогда одновременно из рассмотрения выбывают строка и столбец. Рекомендуется в одну из клеток выбывающих строки и столбца (лучше в клетку с наименьшей стоимостью) ставить так называемый базисный нуль. Эта клетка считается базисной (в ней пишется 0), а общее число базисных клеток остается равным

m + n – 1.

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

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

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

Пример 4. Найти начальный план перевозок в ТЗ (пример 3) методом минимального элемента.

Запишем матрицу перевозок (табл. 3.3).

Таблица 3.3

Bj Ai	B1	B2	В3	B4	Запасы ai
A1			*
A2
A3		*	*
Потребности bj

Заполняем клетку с наименьшей стоимостью:

.

Потребности в пункте В₂ удовлетворены, запасы в пункте А₁ исчерпаны – случай вырождения. В клетке с наименьшей стоимостью среди выбывающих клеток ставим базисный нуль .

Среди оставшихся клеток ищем клетку с наименьшей стоимостью:

– случай вырождения, базисный нуль .

Из оставшихся клеток заполняем клетку с наименьшей стоимостью:

.

Потребности в пункте В₃ удовлетворены, выбывает третий столбец.

.

Получен начальный план перевозок:

с суммарной стоимостью

,

которая меньше стоимости, полученной методом северо-западного угла. Число базисных клеток m + n – 1 = 3 + 4 – 1 = 6.

Метод потенциалов

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

Циклы матрицы перевозок

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

а б в

Рис. 3. Простейшие циклы

На рис. 3 звездочкой отмечены клетки матрицы, включенные в состав цикла. На рис. 3 в кружком отмечена точка самопересечения.

Означенный цикл – цикл, в котором некоторой вершине приписан знак +, а затем при обходе цикла в каком-либо направлении знаки чередуются.

Сдвигом по циклу на величину назовем увеличение объемов перевозок во всех клетках, отмеченных знаком + и уменьшение объемов перевозок на во всех клетках цикла, отмеченных знаком –.