Общая постановка транспортной задачи

Таблица 5.1

Задача о перевозках.

ТРАНСПОРТНАЯ ЗАДАЧА.

Симплекс-методом можно решить любую ЗЛП. Но есть такие ЗЛП, которые можно решить более простыми методами. К таким задачам относится транспортная задача. Примером транспортной задачи является задача о перевозках, задача о назначениях, задача развития и размещения одно- и многопродуктовых отраслей.

Имеется m пунктов отправления А₁, А₂,..., А_m, в которых сосредоточен некоторый груз в количествах а₁,а₂,...,а_m и n пунктов назначения В₁, В₂,..., В_n, в которые требуется завезти этот груз в количествах b₁,b₂,...,b_n, причем

. Известны стоимости c_ij перевозки единицы

груза из пунктов А_i в пункты В_j (; ). Предполагается, что

а) товар является однородным и делимым, т.е. потребителю безразличен источник получаемого товара, а перевозки могут осуществляться партиями любого размера;

б) стоимость перевозки груза из одного пункта в другой пропорциональна количеству перевозимого груза.

Требуется составить такой план перевозок из пунктов А_i в пункты В_j, при котором затраты на перевозки были бы наименьшими.

Исходные данные задачи обычно представляются в виде транспортной таблицы (табл. 5.1).

Пн По	В1	В2	...	В3	Запасы
А1	С11	С12	...	С1n	а1
А2	С21	С22	...	С2n	а2
...	...	...	...	...	...
Аm	Сm1	Сm2	...	Сmn	аm
Потребности	в1	в2	...	вn

Стоимости c_ij проставляются в правых верхних углах соответствующих клеток.

Составим математическую модель задачи. Пусть x_ij – количество груза, перевозимого из пункта А_i в пункт В_j. Целевая функция задачи (общая стоимость перевозок) записывается следующим образом:

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

а) запасы пунктов отправления должны быть исчерпаны;

б) потребности пунктов назначения должны быть удовлетворены;

в) перевозки могут быть только неотрицательными.

Таким образом, ограничения задачи имеют вид:

Мы видим, что задача о перевозках является ЗЛП.

Транспортной задачей называется ЗЛП следующего вида:

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

Уравнения (5.2) называются горизонтальными, уравнения (5.3) -вертикальными.

Любой набор значений переменных x_ij называется планом перевозок. План перевозок называется допустимым, оптимальным или опорным, если он является допустимым, оптимальным или опорным планом ЗЛП (5.1 - 5.4).

Транспортная задача, как и любая задача линейного программирования, может быть решена симплекс-методом. Однако
благодаря указанной выше особенности транспортной задачи, для неё
существуют более простые методы решения, один из которых – метод
потенциалов - мы изучим.