3.6 Транспортная задача

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

Некоторый однородный продукт сосредоточен у m поставщиков в количестве ,i =единиц соответственно. Необходимо доставитьn потребителям в количестве , j =единиц этот продукт. Известно, что_j- стоимость перевозки единицы груза от i -го поставщика к j-му потребителю.

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

Составим математическую модель.

Обозначим:

–количество единиц груза, запланированного к перевозке от i-го поставщика к j-му потребителю.

-? , причем

, i =- все грузы должны быть вывезены

, j =- все потребители должны быть удовлетворены

0 , i =, j =

Пусть -такая модель называется закрытой.

Можно показать, что любая закрытая транспортная задача ( ТЗ ) имеет решение. Транспортная задача – ЗЛП, но специфичная формой своих ограничений.

Матрица ограничений имеет n+m строк:

(*) 1-я группа ограничений:

(**) 2-я группа ограничений:

Остальные элементы матрицы равны нулю.

ЗЛП:

Ax = b (обычно)

Пример:

n = 2

m = 3

В этом случае матрица ограничений:

A =

Матрица A сильно разрежена (в реальности число ограничений может достигать 1000).

Симплекс метод при решении этой задачи будет работать очень медленно, поэтому нужны другие методы. Заметим, что в A^Tв любой строке два ненулевых элемента.

3.5.1. Построение первоначального опорного плана.

В транспортной задаче mn неизвестных и m+n уравнений. Если сложить почленно уравнения системы (*) , а потом системы (**) и учесть, что задача закрытая, то получим два одинаковых уравнения, т.е. система ограничений линейно-зависима.

Отбросим одно из уравнений системы. В общем случае система ограничений должна содержать m+n-1 линейно-независимых уравнений, следовательно, невырожденный опорный план транспортной задачи содержит m+n-1 положительных компонент или перевозок (остальные равны 0).

Транспортная задача решается с помощью матрицы (планирования).

Заполнение матрицы:

ПОСТАВЩИКИ	ПОТРЕБИТЕЛИ				ЗАПАСЫ
	В1	В2	В3	В4
А1	-5 c11=5	5 c12=1	+4 c13=4	-4 c14=7	a1=5
ЦИКЛ А2	3 c21=2	-3 c22=6	 2 c23=10	+2 c24=3	a2=7
А3	-3 c31=4	3 c32=2	+6 + c33=3	1 c34=2	a3=4
ПОТРЕБНОСТИ	b1=3	b2=8	B3=2	b4=3	ai = bj

В таблице должно быть m+n-1 (6) занятых клеток (>0). Занятые клетки соответствуют базисным неизвестным. Опорность (допустимость) плана при записи условий транспортной задачи в виде таблицы заключается в его ацикличности, т.е. в таблице нельзя построить замкнутый цикл, все вершины, которые лежат в занятых клетках.

Определение:

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

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

Если такой возврат возможен, то получен цикл , и план не является опорным. Клетки, в которых происходит поворот под прямым углом, определяют вершины цикла.

В противоположном случае план является опорным ( если цикл не найден)

Всякий план ТЗ , содержащий более m+n-1 занятых клеток не является опорным, так как ему соответствует линейно зависимая система векторов. При таком плане в таблице всегда можно построить замкнутый цикл, с помощью которого уменьшают число замкнутых клеток до m+n-1.

Существует несколько простых схем построения первоначального опорного плана транспортной задачи (метод северо-западного угла, минимальной стоимости и другие).

Метод минимальной стоимости:

Из всей таблицы стоимостей выбираем наименьшую, и в клетку, которая ей соответствует помещаем меньшее из чисел или. Затем из рассмотрения исключаем либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены(либо и строку, и столбец).

Из оставшейся части таблицы стоимостей снова выбираем наименьшую стоимость и процесс распределения запаса продолжается, пока все запасы не будут распределены, а все потребности удовлетворены.

Значение целевой функции для ранее указанного примера f = 45.