17) Распределительный метод решения транспортной задачи.

Прежде всего заметим, что система ограничений (2), (3) состоит из n + m уравнений. Причем при условии(4) эти уравнения линейно зависимы. Действительно, сложив все уравнения вида (2) и вида (3) получим ∑∑Xij =∑Mi , (2’)

∑∑Xij=∑Ni , (3’)

Правые части уравнений (2’), (3’) равны друг другу по условию (4), а левые, являющиеся суммами всевозможных переменных Xij также совпадают. Вычитая из (2’) (3’) получим верное тождество 0=0 , следовательно, уравнения системы ограничений линейно зависимы, и ранг этой системы не больше, чем n + m-1 . Можно доказать, что ранг системы ограничений не меньше, чем n+m-1 (смотри «Исследование операций в экономике под редакцией» Н.Ш. Кремера) Итак, ранг системы ограничений транспортной задачи (2), (3) при условии (4) равен n+m-1.

Следовательно, число базисных переменных в системе ограничений также равно n + m -1, а число свободных — ( nm -n–m+1 ).

Распределение поставок, соответствующее базисному решению будем называть базисным распределением, клетку, соответствующую базисной переменной будем считать заполненной, а соответствующую свободной переменной — свободной или пустой. Заметим, что в случае вырожденного решения клетку, соответствующую нулевой базисной переменной , также считают «заполненной».

По аналогии с симплексным методом в распределительном методе, выбрав начальное базисное решение будем переходить от одного базисного распределения поставок к другому, уменьшая значение целевой функции (1) вплоть до оптимального решения. Для начала такого процесса необходимо исходное базисное распределение поставок (базисное решение) — так называемый опорный план.

18) Открытая модель транспортной задачи.

 Если суммарный спрос потребителей N= ∑Nj , не равен суммарной мощности поставщиков M=∑Mi , то транспортная задача называется открытой.

Пусть N > M , тогда, добавив еще одного «фиктивного поставщика» с мощностью

Mm+1=N-M , мы сведем задачу к закрытой. Стоимость перевозки от «фиктивного поставщика» к

потребителю можно положить, например, равной штрафу за недопоставку товара. Если информации

об убытках в связи с недопоставками неизвестна, то все коэффициенты затрат C(m+1)j в

дополнительной строке, соответствующей «фиктивному поставщику» можно взять равными одному

и тому же произвольному числу.

Если M > N , то тогда вводят «фиктивного потребителя» с мощностью N(n+1)=M-N .

Коэффициенты затрат C(m+1)j в дополнительном столбце таблицы поставок соответствуют, например,

затратам на хранение неотправленного груза или принимаются равными одному и тому же числу.

19) Вырождение в транспортных задачах.

Решение или распределение является вырожденным, если в нем имеется менее m + n - 1 заполненных клеток, поскольку из-за недостатка заполненных клеток нельзя построить циклы пересчета для части свободных клеток. Для устранения вырождения необходимо количество заполненных клеток довести до m + n - 1. Для этого среди свободных клеток выбирается ровно столько, сколько не хватает заполненных клеток до m + n - 1 и в них помещают нулевые загрузки.

Таблица 12

Грузообразую-щие точки	Потенциалы	Грузопоглощающие точки	Итого по вывозу, т
		B1	B2	B3	B4
		0	-4	6	4
A1	0	16	6	10	4 400	400
A2	6	8	2 400	12 200	14	600
A3	2	2 200	18	8 600	6 200	1000
Итого по ввозу, т	200	400	800	600	2000