Алгоритм решения транспортной задачи

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

Имеются пункты производства A₁, …, A_m, которые выпускают однородную продукцию за определённый период в количестве, соответственно, a₁, …, a_m(единиц). Эта продукция должна быть перевезена в пункты потребления B_1, …, B_n в количествах b₁, …, b_n.

Транспортные издержки, связанные с перевозкой единицы груза из A_i в B_j, образуют матрицу перевозок C_ij.

{C_ij}i = 1, m; j = 1, n

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

Математическая модель транспортной задачи

Рассмотрим случай, когда затраты по перевозке груза пропорциональны количеству перевозимого груза; тогда имеем транспортную задачу линейного программирования. Обозначим х_ij – количество единиц груза перевозимого от А_i к В_j. Тогда математическая модель транспортной задачи линейного программирования принимает следующий вид:

(1) i – номер строки

(2) j – номер столбца

(3)

(4) x_ij ³ 0

(5)

Решение { x_ij }, которое удовлетворяет условиям (2) и (3), (4) называется допустимым. Те допустимые решения, которые доставляют экстремум целевой функции (1)называются оптимальными решениями или планом транспортной задачи { x_ij^* }. Обычно решение транспортной задачи находят используя матрицу транспортной задачи с клетками: если x_ij = 0, то клетка называется свободной, если x_ij ¹ 0, то – загруженной. Если выполняется балансирующее уравнение (5), то транспортную задачу называют закрытой, если Sа_i ¹ Sb_j, то открытой. Из математики известно, что можно решить только закрытую транспортную задачу.

1. Пусть Sа_i > Sb_j, тогда вводим фиктивного потребителя В_n+1^ф с потребностью и нулевыми тарифами, т.е. С_{i, n+1} = 0

2. Пусть Sа_i < Sb_j, тогда вводим фиктивного поставщика А_m+1^ф с выпуском с нулевыми тарифами, т.е. С_{m+1, j} = 0

Алгоритм решения транспортной задачи

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

Определение начального опорного решения.

Нахождение оптимального решения, используя циклы пересчета.

Существуют различные методы получения опорного плана:

1. Метод северо-западного угла.
2. Метод минимального тарифа.
3. Метод Фогеля.

Легко показать, что из m*n клеток только d = m + n - 1 клеток является загруженными, а остальные – свободными. Если в опорном плане число загруженных клеток не равно d, то план называется вырожденным. Если в опорном плане число загруженных клеток равно d, то план называется невырожденным. Рассмотрим решение транспортной задачи на следующем примере: для строительства 4 – х объектов (В_j) используется кирпич, изготовленный на 3 – х заводах (А_i); известен дневной выпуск кирпича (а_i) и отпускная цена (р_i). Потребности в кирпиче каждой стройки (в_i), тарифы перевозок условной единицы кирпича задаются матрицей { С_ij }. Решить транспортную задачу по минимизации затрат (по закупке и доставке) необходимого количества кирпича. Исходные данные:

,

Решением проверяем задачу на условие закрытости:

Sа_i = 10 + 15+20 = 45,

Sв_j = 15 + 10 + 15 = 40.

Нужно вводить фиктивного потребителя (столбец)

В₅^ф: в₅ = 45 – 40 = 5.

	B1	B2	B3	B4ф	ai
А1
А2
А3
bj

Решение транспортной задачи удобно представить в виде таблицы.

 

Рассмотрим метод северо–западного угла.

d = 5 + 3 – 1 = 7 – число загруженных клеток. Клетка А₁В₂ – условно – загруженная.

Правило – на каждом шаге обнуляем только одну строчку или столбец. Суммарные затраты по закупке и доставке равны:

L₁^тр(x) = 6*10+10*5+8*10+4*0+9*15+0*5=325д.е.

L₁^зак(x)= 8*10+(5+10)*10+(15*12)=410 д.е.

L₁^сум(x) =735 д.е.

 

Если расположить заводы в порядке возрастания цены (р₁ = 8 <10 <12), то метод северо – западного угла реализует решение локальной задачи – минимизация затрат на основании информации только о закупочных ценах. Рассмотрим второй метод нахождения опорного плана – метод минимальной стоимости.

 

 

Метод потенциалов:

1. Для загруженных клеток составляем уравнение , где U_i – потенциал строки, V_j – потенциал столбца, т.к. их количество равно m + n, а число згруженных клеток m + n – 1, то один потенциал равен 0 (U_i). Остальные потенциалы находим из уравнения:

V_j = С_ij - U_i, если известно U_i и U_i = С_ij - V_j, если известно V_j.

Для свободных клеток определением разности по формулам D_ij = U_i + V_j - С_ij. Разности D_ij – двойственные переменные для транспортной задачи.

2. Если все D_ij £ 0, то полученный план оптимальный. Если все D_ij для свободных клеток D_ij < 0, то план оптимальный и единственный.

3. Если существует D_ij > 0,то выбираем максимальное из них и для соответствующей клетки строим циклы пересчета.

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

е = min x_ij

-

 

Строим новый план. Новое значение в вершинах цикла пересчета определяется по формулам.

х_ij^нов = x_ij ± e.

 

 

Остальные значения переписываем из старой таблицы без изменения.

Вычисляем:

 

	B1	B2	B3	B4ф	ai	U
А1		10	0
А2				0 0
А3
bj
V	-2			-4

 

L₂⁽¹⁾ =1*10+7*15+2*15=145 д.е.

 

D₁₁ = 0 -2-6 = -8 D₂₂ = -3

D₁₄ = 0 -4 -0 = -4 D₃₂ = +1

D₂₁ = 4 – 2 – 10 = -8 D₃₃ = -2

min (3; 6) = 3 º е

Новый план.

 

	B1	B2	B3	B4ф	ai	U
А1		10	0
А2				0 0
А3
bj
V	-1			-4

 

 

L₂⁽²⁾= 5+15+70+30+20=140 д.е.

L₂⁽¹⁾ - L₂⁽² = 5 =1*5 д.е.

 

L₂^зак(x)= 8*10+10*10+(15+5)*12=420 д.е.

L₂^сум(x) =560 д.е.

 

3.Рассмотрим третье задачу – минимизация суммарных затрат на закупку и транспортировку

 

	B1	B2	B3	B4ф	ai	U
А1
А2
А3
bj
V				-6

 

 

L₃^сум(x) =(1+8)*10+ (7+10)*15+2+12)*15=(10+105+30)+ (80+150+180)= 145+410=555 д.е.

 

 

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

 

Задача	Издержки	Абсолютная оценка	Относительная оценка, %
по закупке	транспортные	суммарные
	441410 *1*010	325			32,4
	420	3140 * 25			0,9
			555 *	-	-

 

Абсолютные и относительные оценки вычисляются по формулам:

Оптимизация по модели в, основанная на полной информации (об отпускных ценах и транспортных тарифах) лучше, чем локально-оптимальные планы по моделям а,б, найденные на основании неполной информации (только об отпускных ценах или только о транспортных тарифах): она позволяет получить такой план перевозок сырья, для которого суммарные издержки будут меньше как по абсолютной величине, так и в процентном отношении. Это видно из табл. 1.2. (последние 2 графы).