Алгоритм решения транспортной задачи
Транспортная задача в матричной постановке.
Имеются пункты производства A1, … , Am, которые выпускают однородную продукцию за определённый период в количестве, соответственно, a1, … , am(единиц). Эта продукция должна быть перевезена в пункты потребления B1, … , Bn в количествах b1, … , bn.
Транспортные издержки, связанные с перевозкой единицы груза из Ai в Bj, образуют матрицу перевозок Cij.
{Cij}i = 1, m; j = 1, n
Транспортная задача в матричной постановке заключается в определении плана перевозок, удовлетворяющего спрос всех пунктов потребления, обеспечивающий вывоз всей продукции из пунктов производства с минимальными затратами (дискриптивная модель).
Математическая модель транспортной задачи
Рассмотрим случай, когда затраты по перевозке груза пропорциональны количеству перевозимого груза; тогда имеем транспортную задачу линейного программирования. Обозначим хij – количество единиц груза перевозимого от Аi к Вj. Тогда математическая модель транспортной задачи линейного программирования принимает следующий вид:
(1) i – номер строки
(2) j – номер столбца
(3)
(4) xij ³ 0
(5)
Решение { xij }, которое удовлетворяет условиям (2) и (3), (4) называется допустимым. Те допустимые решения, которые доставляют экстремум целевой функции (1)называются оптимальными решениями или планом транспортной задачи { xij* }. Обычно решение транспортной задачи находят используя матрицу транспортной задачи с клетками: если xij = 0, то клетка называется свободной, если xij ¹ 0, то – загруженной. Если выполняется балансирующее уравнение (5), то транспортную задачу называют закрытой, если Sаi ¹ Sbj, то открытой. Из математики известно, что можно решить только закрытую транспортную задачу.
1. Пусть Sаi > Sbj, тогда вводим фиктивного потребителя Вn+1ф с потребностью и нулевыми тарифами, т.е. Сi, n+1 = 0
2. Пусть Sаi < Sbj, тогда вводим фиктивного поставщика Аm+1ф с выпуском с нулевыми тарифами, т.е. Сm+1, j = 0
Алгоритм решения транспортной задачи
Транспортная задача может быть решена использованием симплекс – метода, но существует более простой распределительный метод. Решение задачи состоит из двух этапов:
Определение начального опорного решения.
Нахождение оптимального решения, используя циклы пересчета.
Существуют различные методы получения опорного плана:
- Метод северо-западного угла.
- Метод минимального тарифа.
- Метод Фогеля.
Легко показать, что из 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.
Нужно вводить фиктивного потребителя (столбец)
В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. Для загруженных клеток составляем уравнение , где 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,то выбираем максимальное из них и для соответствующей клетки строим циклы пересчета.
- Цикл пересчета – замкнутая ломанная линия с взаимоперпендекулярными звеньями, направленная вдоль строк или столбцов, вершины которой все находятся в загруженных клетках, кроме той, для которой строили цикл. К вершинам цикла, начиная с ключевой, ставим знаки поочередно «+» и «-». Находим минимальный среди всех.
е = min xij
-
Строим новый план. Новое значение в вершинах цикла пересчета определяется по формулам.
хijнов = xij ± e.
Остальные значения переписываем из старой таблицы без изменения.
Вычисляем:
B1 | B2 | B3 | B4ф | ai | U | |
А1 | 10 | 0 | ||||
А2 | 0 0 | |||||
А3 | ||||||
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
D21 = 4 – 2 – 10 = -8 D33 = -2
min (3; 6) = 3 º е
Новый план.
B1 | B2 | B3 | B4ф | ai | U | |
А1 | 10 | 0 | ||||
А2 | 0 0 | |||||
А3 | ||||||
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 * | - | - |
Абсолютные и относительные оценки вычисляются по формулам:
Оптимизация по модели в, основанная на полной информации (об отпускных ценах и транспортных тарифах) лучше, чем локально-оптимальные планы по моделям а,б, найденные на основании неполной информации (только об отпускных ценах или только о транспортных тарифах): она позволяет получить такой план перевозок сырья, для которого суммарные издержки будут меньше как по абсолютной величине, так и в процентном отношении. Это видно из табл. 1.2. (последние 2 графы).