Транспортная задача открытого типа

Если для транспортной задачи выполняется одно из условий

или

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

Это делают так: если , то добавляют фиктивного потребителя со спросом (в распределительной таблице появится дополнительный столбец), если , то добавляют фиктивного поставщика с предложением (в распределительной таблице появится дополнительная строка). В обоих случаях тарифы полагают равными нулю. Далее задача решается по такому же порядку, как было рассмотрено ранее.

Запишем алгоритм решения транспортной задачи:

1) Проверка типа модели ТЗ.

2) Построение начального опорного плана (любым способом).

3) Проверка плана на вырожденность.

4) Проверка плана на оптимальность методом потенциалов:

а) нахождение потенциалов из системы

(для всех заполненных клеток);

б)проверка второго условия оптимальности

(для всех пустых клеток).

5) Переход к нехудшему опорному плану (если это необходимо).

Пример. На складах имеются запасы однотипного товара в количестве а (35; 40; 40; 50), который необходимо доставить потребителям. Потребности потребителей задает вектор b (31; 52; 17; 20). Матрица затрат на доставку единицы товара от i-го поставщика j-му потребителю:

с=

Составить план перевозок с минимальными транспортными затратами.

Решение. Определим тип модели транспортной задачи. Суммарная мощность поставщиков: 35+40+40+50=165 (единиц товара); Суммарный спрос потребителей: 31+52+17+20=120 (единиц товара).

Т.к. , то имеем модель открытого типа.

Введем фиктивного потребителя, спрос которого равен

165 –120 =45 (единиц товара).

Тарифы 0. Т.о. получаем модель закрытого типа, m = 4 – число поставщиков, n = 5 – число потребителей. Ранг матрицы задачи . Построим начальный опорный план методом минимального элемента (наименьшей стоимости).

	31		52		17		20		45
35		5		4		3		1		0	0
					15		20
40		2		3		5		8		0	1
	31		9
40		6		8		7		10		0	4
									40
50		5		6		7		2		0	4
			43		2				5
	1		2		3		1		– 4		Таб.1

Число заполненных клеток распределительной таблицы 8 равно рангу матрицы задачи r = 8, следовательно, опорный план является невырожденным.

Транспортные затраты, соответствующие опорному плану:

(ден. ед.).

Исследуем опорный план на оптимальность, используя метод потенциалов.

Дополним таблицу 1 столбцом и строкой потенциалов и . Систему потенциалов найдем, используя первое условие оптимальности: для заполненных поставками клеток .

;

Из записанной системы находим: , , , , , , , , .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: .

(1; 1) 0 + 1 – 5 = –4 0;

(1; 2) 0 + 2 – 4 = –2 0;

(1; 5) 0 – 4 – 0 = –4 0;

(2; 3) 1 + 3 – 5 = –1 0;

(2; 4) 1 + 1 – 8 = –6 0;

(2; 5) 1 – 4 – 0 = –4 0;

(3; 1) 4 + 1 – 6 = –1 0;

(3; 2) 4 + 2 – 8 = –2 0;

(3; 3) 4 + 3 – 7 = 0 0;

(3; 4) 4 + 1 – 10 = –5 0;

(4; 1) 4 + 1 – 5 = 0 0;

(4; 4) 4 + 1 – 2 = 3 0.

Т.к. среди свободных клеток есть такие, в которых второе условие оптимальности не выполняется, то план не оптимален.

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (4; 4), т. к. ей соответствует наибольшая положительная оценка

4 + 1 – 2 = 3.

Найдем цикл перераспределения груза для этой клетки.

Выбранной для заполнения клетке присваиваем знак «+», далее знаки чередуем. Среди вершин со знаком «–» выбираем наименьшую поставку.

– объем перепоставки.

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

–2

–1

Таб.2

Транспортные затраты, соответствующие опорному плану:

(ден. ед.).

Исследуем опорный план на оптимальность. Найдем значения потенциалов, используя первое условие оптимальности. Для заполненных поставками клеток .

, , , , , , , , .

Проверим выполнение второго условия оптимальности. Для всех пустых клеток должно выполняться неравенство: .

Выпишем клетки, в которых условие нарушено:

(1; 2) 0 + 5 – 4 = 1 0.

Осуществим переход к нехудшему опорному плану. Наиболее перспективная для заполнения клетка (1; 2), т. к. ей соответствует положительная оценка 1. Найдем цикл перераспределения груза для этой клетки.