2.2.13 Открытая транспортная задача

Постановка транспортной задачи рассмотрена в разделе 2.2.12, модель транспортной задачи имеет вид

, (2.13.1)

где – стоимость перевозок продукта от -го поставщика -му потребителю;

– неизвестный объем поставок продукта.

Ограничение по наличию продукта у поставщика

, , (2.13.2)

где – запас продукта у -го поставщика.

Ограничение на потребность продукта

, , (2.13.3)

где – потребность в продукте -го потребителя.

Условием разрешимости задачи является равенство общих ресурсов поставщиков общей потребности потребителей.

. (2.13.4)

Если это равенство удовлетворяется, то задача называется закрытой, в противном случае задача открытая и для ее разрешимости необходимо вводить «фиктивного поставщика» или «фиктивного потребителя» с объемом продукта равным разности правой и левой части (2.13.4) получившей знак неравенства и нулевой стоимостью перевозок.

Задача 2.2.13.1. Три овощеводческих хозяйства имеют запасы картофеля в объемах 300 т, 1200 т, 720 т и заключили договора на поставку картофеля в г. Барнаул на склад 1100 т, на спиртзавод 420 т и на товарную станцию ж-д 800 т. стоимости перевозок 1 т в денежных единицах приведены в матрице

.

Здесь – стоимость перевозки от -го поставщика -му потребителю 1 т картофеля.

Определить объемы поставок от каждого поставщика каждому потребителю.

Решение.

Задача является открытой, поэтому, необходимо введение «фиктивного поставщика» №1 с объемом поставки 2320–2220=100 т.

Транспортная таблица имеет вид

Таблица 13.1

Хозяйства		Барнаул 1100	Спиртзавод 420	Ж-д станция 800
№1	3 00	80 300	20	40	0
№2	1200	100 700	50	20 500	–20
№3	720	70	10 420	30 300	–30
Ф.П.	100	0 100	0	0	80
		80	–20	0

Методом наименьших элементов находим опорный план. Определяем потенциалы из равенств, положив , составленных по базисным клеткам

; . ; .

; . ; .

; . ; .

Проверка оптимальности плана по небазисным клеткам имеет результата

нет оптимума.

;

;

;

;

.

План не оптимален, в клетку (1, 3) необходимо ввести базисный объем перевозок в 300 единиц. Строится цикл перемещения этого объема. Новая транспортная таблица имеет вид.

Таблица 13.2

		Барнаул 1100	Спиртзавод 420	Ж–д станция 800
№1	300	80 300	20	40	–40
№2	1200	100 400	50	20 800	–60
№3	720	70 300	10 420	30	–30
Ф.П.	100	0 100	0	0	40
		40	–20	–40

Новая система потенциалов начинается с клетки (2,3), поскольку она не перетерпела изменений.

; . ; .

; .

; .

; .

Проверка оптимальности оценками небазисных клеток

;

;

;

;

.

Получаем оптимальный план, оценки клеток отрицательны.

Решение в виде матрицы

.

Потребитель «Барнаул» не получит 100 т.