Лекции.Орг


Поиск:




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

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

Имеются пункты производства 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

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

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

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

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

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

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

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

,

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

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. Для загруженных клеток составляем уравнение , где 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   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 графы).

 



<== предыдущая лекция | следующая лекция ==>
на осеннюю (установочную) сессию с 17.10.16-25.10.16 г. | Протокол судебного заседания
Поделиться с друзьями:


Дата добавления: 2016-11-20; Мы поможем в написании ваших работ!; просмотров: 391 | Нарушение авторских прав


Поиск на сайте:

Лучшие изречения:

Начинать всегда стоит с того, что сеет сомнения. © Борис Стругацкий
==> читать все изречения...

843 - | 679 -


© 2015-2024 lektsii.org - Контакты - Последнее добавление

Ген: 0.011 с.