Формулировка транспортной задачи

Оптимальное закрепление поставщиков однородного груза за потребителями, т.е. нахождение оптимальных грузопотоков, является классическим примером транспортной задачи. Эта задача возникает, когда несколько поставщиков имеют однородный груз, который в определенных объемах должен быть доставлен потребителям.

Суть транспортной задачи линейного программирования состоит в следующем. В пунктах отправления А₁, А₂,..., А_п имеется однородный груз в количестве а₁, а₂,..., а_п. Этот груз необходимо доставить в пункты потребления В₁, В₂,..., В_т в количестве b₁, b₂,..., b_т. Известны кратчайшие расстояния с_ij, между всеми пунктами отправления и получения груза. Необходимо построить план перевозок таким образом, чтобы была удовлетворена потребность в грузе всех пунктов потребления, был вывезен весь груз из пунктов производства и при минимуме транспортной работы в тонна-километрах.

Экономико-математическая модель транспортной задачи выглядит следующим образом. Система ограничений по количеству груза, доставляемого в пункты потребления:

Система ограничений по количеству груза, вывозимого из каждого пункта производства:

где x_ij – объем перевозок между i-и и j-й точками транспортной сети;
i – количество поставщиков; j – количество потребителей; а_i – ограничения по предложению; b_j – ограничения по спросу.

Причем предполагается, что , так как это необходимо для совместимости системы уравнений. Общий объем транспортной работы (стоимости перевозок) должен быть минимальным. Поэтому целевая функция выглядит следующим образом: , где x_ij ³ 0.

Математическая постановка задачи показывает, что задача закрепления поставщиков за потребителями относится к классу задач линейного программирования, называемой транспортной задачей линейного программирования. Условия транспортной задачи обычно представляются в виде матрицы, образец которой приведен в табл. 3.1.

Т а б л и ц а 3.1

Матрица условий транспортной задачи