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

Теоретические положения

Постановка транспортной задачи состоит в следующем. Имеется m поставщиков товара, каждый из которых обладает мощностью M (i = 1, 2, …, m), и n потребителей товара с мощностями (потребностями) N (j = 1, 2, …, т). Стоимости перевозок единицы груза от каждого i-го поставщика каждому j-му потребителю c известны и называются коэффициентами затрат. Найти объемы перевозок x для каждой пары «поставщик – потребитель» так, чтобы:

1) мощности всех поставщиков были реализованы;

2) спросы всех поставщиков удовлетворены;

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

Математически требования 1) и 2) могут быть записаны:

= M , i = 1, 2, …, m; (1)

= N , j = 1, 2, …, n.. (2)

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

F = . (3)

Математически формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (1) и (2) найти такое решение X = (x , x , …, x , …, x ), при котором значение целевой функции (3) минимально.

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

- система ограничений есть система уравнений, т.е. задача задана в канонической форме;

- коэффициенты при переменных системы ограничений равны единице или нулю;

- каждая переменная входит в систему ограничений два раза: один раз – в систему (1) и один раз - в систему (2).

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

= .

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

Являясь задачей линейного программирования, транспортная задача может быть решена симплексным методом. Модификация симплексного метода применительно к транспортной задаче называется распределительным методом.

Пример

Решить транспортную задачу распределительным методом. Исходные данные приведены в таблице 1.

Таблица 3

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

Нахождение первоначального базисного распределения поставок. Базисным называется распределение, удовлетворяющее требованиям (1) и (2), а также содержащее определенное количество заполненных клеток таблицы. Это количество равно рангу матрицы r = m + n –1. Последнее условие определено спецификой симплексного метода, в котором количество основных переменных строго определено. В распределительном методе основными переменными являются переменные в заполненных клетках таблицы.

I шаг решения

Формирование первоначального базисного распределения поставок чаще всего производится методом «северо-западного угла» или методом наименьших затрат. Найдем такое распределение методом «северо-западного угла». Дадим переменной x максимально возможное значение, т.е. максимально возможную поставку в клетку (1, 1) - «северо-западный» угол таблицы поставок: x = min(40, 20) = 20. После этого спрос первого потребителя будет удовлетворен, в результате чего первый столбец таблицы поставок выпадет из последующего рассмотрения (заполненные клетки будем перечеркивать сплошной линией, а клетки, выпавшие из рассмотрения - пунктирной). Далее в таблице поставок найдем новый северо-западный угол - клетку (1, 2) в нее максимально возможную поставку. Учитывая, что первый поставщик уже отдал 20 единиц груза, поставка будет равна x = min (20, 30) = 20. После этого мощность первого поставщика будет полностью реализована и из рассмотрения выпадает первая строка таблицы поставок. Следуя этой схеме, производим заполнение остальных клеток таблицы. В результате получим:

Таблица 4

2	3	1		5	-2
1	3 10	2 20	3	3	-2
4	3	20		2	-2
5					-2
3	4	2		1	-6
	-1

Приведенное в таблице распределение поставок является базисным. Здесь выполняются условия баланса по строкам и столбцам таблицы, а число заполненных клеток равно r = 5 + 5 – 1 = 9. Общая стоимость перевозок, т.е. значение целевой функции может быть получено как сумма по всем клеткам таблицы произведений коэффициентов ликвидности на соответствующие объемы перевозок: F = 2× 20 +3× 20 + 3× 10 + 2× 20 +2× 20 + 2× 10 + 1× 50 + 5× 10 + 1× 40 = 370.

Полученное решение может оказаться искомым оптимальным решением задачи. В симплексном методе факт оптимальности базисного решения устанавливается по выражению целевой функции через неосновные переменные. Для приведенной таблицы это выражение будет иметь вид: F = 370 + x , где индексы k и l соответствуют незаполненным клеткам таблицы. Для определения коэффициентов строится матрица оценок свободных клеток таблицы перевозок. Для этого каждой строчке и каждому столбцу таблицы назначается некоторое число, называемое потенциалом. Потенциалом строчки или столбца может быть произвольное число. Однако для каждой заполненной клетки таблицы должно выполняться условие: сумма потенциала строки, потенциала столбца для данной клетки и коэффициента затрат клетки должна быть равна нулю.

Назначение потенциала можно начинать с любой строчки или столбца таблицы. Проиллюстрируем порядок расстановки потенциалов на примере таблицы 2. Возьмем первый столбец таблицы и назначим ему потенциал равный нулю (последняя строка таблицы). В рассматриваемом столбце имеется заполненная клетка (1, 1) с коэффициентом затрат равным 2. Для выполнения сформулированного выше условия необходимо, чтобы потенциал первой строки был равен -2 (последний столбец таблицы). Обратим внимание на то, что в строке с назначенным потенциалом находится еще одна заполненная клетка (1, 2). Найдем потенциал второго столбца равный - 1 (-2 + 3 – 1 = 0). Затем по той же схеме находим потенциалы всех остальных элементов таблицы поставок.

Найдем оценки свободных клеток как сумму потенциалов строки и столбца и коэффициента затрат клетки. Например, для клетки (1, 3): 0 + 1 – 2 = - 1. Аналогично для клетки (2, 5): 5 +3 – 2 = 6 и так далее. В результате получаем матрицу оценок:

В = .

В соответствии с полученной матрицей выражение целевой функции через неосновные переменные примет вид:

F = 370 - x + 3 x + 8x - x - …- 4x .

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

В соответствии с этим на втором шаге решения переменную x переведем в основные. Это означает, что ее значение станет 0. Однако дополнительная поставка в клетку (5, 3) приведет к нарушению баланса в пятой строке и третьем столбце. Для предотвращения этого строится цикл пересчета. Циклом пересчета называют ломаную с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов таблицы поставок, удовлетворяющую условиям:

- ломаная должна быть связной, т.е. из любой ее вершины можно попасть в любую другую по звеньям ломаной;

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

- одна из вершин цикла лежит в свободной клетке, остальные - в заполненных;

- цикл пересчета называется означенным, если в его вершинах расставлены знаки «+» и «– «так, что в свободной клетке стоит знак «+», а соседние вершины имеют противоположные знаки.

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

Построим цикл пересчета для клетки (5, 3).

(4, 3) – + (4, 4)

10 50

(5, 3) + – (5, 4)

10

Далее необходимо определить максимально возможный размер поставки в свободную клетку (5, 3). Для сохранения условий баланса в сточках и столбцах таблицы поставок при назначении поставки в свободную клетку необходимо изъять такую же поставку из соседних клеток, означенных «– «. С учетом того, что поставка не может быть отрицательной (нулем поставка может быть) получим: x = min(10, 10) = 10. При изъятии 10 единиц продукции из клеток (4, 3) и (5, 4) в этих клетках остаются нулевые поставки. Любая из этих клеток может быть свободной на следующем шаге решения.

Однако общее количество заполненных и свободных клеток на каждом шаге решения должно оставаться постоянным. В соответствии с этим одна из двух обозначенных клеток считается заполненной нулевой поставкой. Пусть это будет клетка (4, 3), а клетка (5, 4) останется свободной. После этого реализуем второй шаг решения задачи.

II шаг

Проведенное исследование дает возможность сформировать новое базисное распределение поставок, показанное в таблице 2.

Таблица 5

2					-2
1	3 10				-2
	3	20			-2
					-2
		2		1	-2
	-1

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

Матрица оценок свободных клеток имеет вид:

В = .

Дадим поставку в клетку с отрицательной оценкой (1, 3). Цикл пересчета имеет вид:

(1, 2) – + (1, 3)

2 0

(2, 2) + – (2, 3)

10 20

Максимально возможная поставка x = min (20, 20) = 20. Свободной на следующем шаге будем считать клетку (1, 2).