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

Открытая транспортная задача решается сведением ее к закрытой.

Задача. Найти оптимальное распределение поставок для транспортной задачи таблица 16

Таблица 16 таблица 17

	45	35	55	65
40	4	1	2	5
60	3	2	3	7
90	4	4	5	2

	45	35	55	65
40	4	1	2	5
60	3	2	3	7
90	4	4	5	2
10	0	0	0	0

Решение.Суммарный спрос потребителей больше суммарной мощности поставщиков (45+35+55+65=20040+60+90=190). Введем, фиктивного поставщика в таблицу поставок добавим, строку ( таблица 17), так чтобы задача стала закрытой. Мощность фиктивного поставщика равна 10=200-190. коэффициенты затрат этой добавленной строки определяются издержками ввиду не догрузки мощностей потребителем. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу (например 0). Согласно теореме о потенциалах, конкретное значение этого числа не влияет на оптимальное распределение поставок.

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

Табл. 18

	45			35			55			65
40	4						1		2			5
						35			5
60	3			2			3			7
			10						50
90	4			4			5			2 55
			35
10		0			0			0			0 10

-2

-3

0 1 0 2

Укажем последовательность заполнения таблицы поставок: x₄₄=(10,65)=10;

x₁₂=(40,35)=35;x₃₄=(90,65-10)=55;x₁₃=(45-40,55)=5;x₂₃=(60,55-5)=50;x₂₁=(60-50,45)=10;x₃₁=(90-55,45-10)=35. В результате приходим к базисному распределению поставок (табл. 18). Установим оптимально ли распределение и найдем матрицу оценок (22).

(22)

Распределение (таблица 18) неоптимальное т.к. есть отрицательные оценки. Переведем поставку в одну из клеток с наименьшей отрицательной оценкой(4,3)

+

10

-

50

-

35

+

50

+

-

10

Поставка передаваемая по циклу равна . Передвигая по циклу поставку равную 10 единиц приходим к распределению таблица 19 находим оценку свободных матриц(23)

4		1				2		5
				35			5
3		2				3		7
	20						40
4		4				5		2
-2	2 -1 5			-2			0			65
0			0		0 10				0

0

1 (23)

-2

-2

-1

2

-2 -1 -2 0

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