2.2.12 Транспортная задача. Закрытая транспортная задача

Транспортной задачей называется разновидность задач линейного программирования.

Имеется пунктов производства однородного продукта с объемами производства и пунктов потребления с объемами потребления . Известна стоимость перевозки единицы продукции от -го пункта производства до -го пункта потребления . Требуется составить план перевозок так, чтобы запасы продукта у поставщиков были вывезены и удовлетворены потребности потребителей, при этом стоимость перевозки должна быть минимальной.

Модель имеет вид

, (2.12.1)

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

Удовлетворение вывоза продукта:

, . (2.12.2)

Удовлетворение потребности получателей продукта

, , (2.12.3)

. (2.12.4)

Условие разрешимости такой задачи:

, (2.12.5)

т. е. суммарные запасы продукта равны суммарным объемам потребления. Такая задача называется закрытого типа. В противном случае задача открытого типа.

Для решения задачи при условии

(2.12.6)

вводится фиктивный поставщик с запасом продукта

. (2.12.7)

Если общий спрос продукта меньше суммарного запаса продукта

, (2.12.8)

то вводится фиктивный потребитель в пункт потребления со спросом

. (2.12.9)

Тарифы на доставку продукта фиктивным поставщикам и потребителям назначаются нулевые.

Исходные данные и решение помещается в специальной транспортной таблице.

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

Опорный план возможно построить методом «северо-западного угла» и методом «минимального элемента».

При методе «минимального элемента» первой загружается клетка с наименьшим тарифом. Далее загружается клетка той же строки (столбца) со следующим по величине тарифом и т.д.

Метод «наименьшего элемента» дает план, более близкий к оптимальному, по сравнению с методом «северо-западного угла».

Задача 2.2.12.1. В резерве железнодорожных станций , и находятся 100, 150 и 50 порожних вагонов, пригодных для перевозки сырья. Зерно находится в 4 пунктах с потребностью вагонов 75, 80, 60 и 85 для перевозки зерна. Стоимость перегона одного вагона от станции до пунктов отражены в таблице.

Составить экономическую модель транспортной задачи из условия минимизации стоимости перегона вагонов. Найти решение методом потенциалов.

Таблица 12.1

	75	80	60	85
100	6	7 5	3 60	5 35	0
150	1 75	2 75	5	6	5
50	3	10	20	1 50	6
	6	7	3	5

Решение.

Задача является закрытой, т.к. выполняется

.

Для построения опорного плана применен метод «минимального элемента».

Вычисление потенциалов по базисным клеткам

;

; ; ; ;

; ; ; ;

; ; ; .

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

Оценки оптимальности удовлетворяют, план оптимален, перераспределения базиса не требуется.

План отражен в матрице

.

Общая стоимость перевозок

денежных единиц.