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

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

Имеются пункты производства A1, … , Am, которые выпускают однородную продукцию за определённый период в количестве, соответственно, a1, … , am(единиц). Эта продукция должна быть перевезена в пункты потребления B1, … , Bn в количествах b1, … , bn.

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

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

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

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

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

(1) Алгоритм решения транспортной задачи - student2.ru i – номер строки

(2) Алгоритм решения транспортной задачи - student2.ru j – номер столбца

(3) Алгоритм решения транспортной задачи - student2.ru

(4) xij ³ 0

(5) Алгоритм решения транспортной задачи - student2.ru

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

1. Пусть Sаi > Sbj, тогда вводим фиктивного потребителя Вn+1ф с потребностью Алгоритм решения транспортной задачи - student2.ru и нулевыми тарифами, т.е. Сi, n+1 = 0

2. Пусть Sаi < Sbj, тогда вводим фиктивного поставщика Аm+1ф с выпуском Алгоритм решения транспортной задачи - student2.ru с нулевыми тарифами, т.е. Сm+1, j = 0

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

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

Алгоритм решения транспортной задачи - student2.ru Определение начального опорного решения.

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

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

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

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

Алгоритм решения транспортной задачи - student2.ru , Алгоритм решения транспортной задачи - student2.ru Алгоритм решения транспортной задачи - student2.ru Алгоритм решения транспортной задачи - student2.ru

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

i = 10 + 15+20 = 45,

j = 15 + 10 + 15 = 40.

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

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

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

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

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

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

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

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

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

L1сум(x) =735 д.е.

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

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

1. Для загруженных клеток составляем уравнение Алгоритм решения транспортной задачи - student2.ru , где Ui – потенциал строки, Vj – потенциал столбца, т.к. их количество равно m + n, а число згруженных клеток m + n – 1, то один потенциал равен 0 (Ui). Остальные потенциалы находим из уравнения:

Vj = Сij - Ui , если известно Ui и Ui = Сij - Vj, если известно Vj.

Для свободных клеток определением разности по формулам Dij = Ui + Vj - Сij. Разности Dij – двойственные переменные для транспортной задачи.

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

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

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

е = min xij

-

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

хijнов = xij ± e.

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

Вычисляем:

  B1 B2 B3 B4ф ai U
А1   Алгоритм решения транспортной задачи - student2.ru 10 Алгоритм решения транспортной задачи - student2.ru 0  
А2     Алгоритм решения транспортной задачи - student2.ru 0 Алгоритм решения транспортной задачи - student2.ru 0
А3 Алгоритм решения транспортной задачи - student2.ru  
bj  
V -2 -4  

L2(1) =1*10+7*15+2*15=145 д.е.

D11 = 0 -2-6 = -8 D22 = -3

D14 = 0 -4 -0 = -4 D32 = +1

Алгоритм решения транспортной задачи - student2.ru D21 = 4 – 2 – 10 = -8 D33 = -2

min (3; 6) = 3 º е

Новый план.

  B1 B2 B3 B4ф ai U
А1   Алгоритм решения транспортной задачи - student2.ru 10 Алгоритм решения транспортной задачи - student2.ru 0  
А2     Алгоритм решения транспортной задачи - student2.ru 0 Алгоритм решения транспортной задачи - student2.ru 0
А3 Алгоритм решения транспортной задачи - student2.ru  
bj  
V -1 -4  

L2(2)= 5+15+70+30+20=140 д.е.

L2(1) - L2(2 = 5 =1*5 д.е.

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

L2сум(x) =560 д.е.

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

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

L3сум(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 * - -

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

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

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

Наши рекомендации