Решение транспортной задачи

Транспортная задача – это задача о минимизации расходов на перевозку грузов. Классическая транспортная задача формулируется следующим образом.

Имеется некоторое количество (m) пунктов отправления:

A₁, A₂, …, A_m , (2.79)

в котором сосредоточены запасы какого-либо однородного товара в количествах

a₁, a₂, …, a_{m .} (2.80)

Имеется также n пунктов назначения:

B₁, B₂, …, B_n , (2.81)

подавших заявки на определенное количество товара соответственно:

b₁, b₂, …, b_n (2.82)

Предполагается, что сумма всех заявок равна сумме всех запасов

. (2.83)

Стоимость перевозки товара из пункта отправления i в пункт назначения j известна для всех вариантов перевозок и равна с_ij­. Таким образом, имеется матрица стоимостей перевозок:

. (2.84)

Требуется составить такой план перевозок, при котором все заявки были бы выполнены и при этом общая стоимость перевозок была бы минимальна.

Так как показателем эффективности является стоимость перевозок, то данную задачу можно назвать транспортной задачей по критерию стоимости.

Рассмотрим математическую формулировку задачи.

Введем некоторые обозначения:

x_ij – количество груза, отправляемого из i-го пункта отправления А_i в j-й пункт назначения B_j (i = 1, …, n; j = 1, …, m). Переменные x₁₁, x₁₂, …, x_mn должны быть неотрицательны и удовлетворять следующим условиям:

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

. (2.85)

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

. (2.86)

3. Стоимость всех перевозок должна быть минимальной.

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

В транспортной таблице записываются:

- пункты отправления (заголовки строк) и назначения (заголовки столбцов);

- запасы, имеющиеся в пунктах отправления (последний столбец таблицы);

- заявки, поданные пунктами назначения (последняя строка таблицы);

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

		Пункты назначения
		B1	B2	…..	Bn	Запасы аi
Пункты отправления	A1	C11	C12	…..	C1n	a1
A2	C21	C22	…..	C2n	a2
. . .	. . .	. . .	. . .	. . .	. . .
An	Cm1	Cm2	. . .	Cmn	am
	Заявки bi	b1	b2	. . .	bn

Для решения транспортной задачи используется надстройка «Поиск решения» (Сервис ® Надстройки ® Поиск решения). Перед использованием механизма поиска решения необходимо ввести исходные данные и расположить их на листе соответствующим образом. Рассмотрим процесс решения транспортной задачи на примере.

Пример решения.

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

Товары находятся в разных городах на разных оптовых базах. Запасы товаров на складах в различных городах представлены ниже в таблице.