Глава 4. Транспортная задача

При планировании объемов перевозок, определении загрузки оборудования, распределении трудовых ресурсов, построении сетей вскрывающих и подготовительных выработок и при решении других задач горного производства возникает одна из типичных задач линейного программирования, которую относят к классу транспортных задач. В одних случаях это означает определение такого плана перевозок, при котором стоимость последних была бы минимальна, а в дру­гих более важным является выигрыш во времени. Первая задача получила на­звание транспортной задачи по критерию стоимости, а вторая - транспортной задачи по критерию времени.

Транспортная задача является частным случаем задачи линейного программирова­ния и может быть решена симплексным методом. Однако в силу особенностей переменных этой задачи для ее решения разработаны специальные методы. Наиболее применяемым является метод потенциалов.

Пусть в р пунктах отправления находятся соответственно a₁, а₂,..., а_р единиц однородного груза, который должен быть доставлен q потребителям в ко­личествах b₁, b₂,... b_q единиц. Заданы стоимости с_ik перевозок единицы груза из i -го пункта отправления k -му пункту потребления. Обозначим через х_ik (i = l, 2,..., р; k = 1, 2,..., q) количество единиц груза, перевозимого из i -го склада k -му потребителю. Переменные х_ik  должны удовлетворять следующим ограничениям:

а)		(4.1)
б)		(4.2)
в)		(4.3)

Суммарные затраты на перевозки равны

Следовательно, требуется найти pq переменных , удов­летворяющих указанным условиям и минимизирующих целевую функцию L.

Решение такой задачи разбивается на два этапа:

1) определение допустимого исходного базисного решения;

2) построение последовательных итераций,

т.е. приближение к оптимальному решению.    

В рассматриваемой задаче предполагается, что сумма запасов равна сумме потребностей:

Такая задача называется закрытой. Если это условие не выполняется, то задача называется открытой. Для сведения открытой задачи к закрытой вводится или фиктивный пункт отправления или фиктивный пункт потребления.