Решение транспортной задачи методом МОДИ - Оперативное планирование перевозок грузов

Последовательность решения транспортной задачи линейного программирования методом МОДИ можно представить схематически (рис. 3).

Процедуру решения транспортной задачи методом МОДИ рассмотрим на примере решения задачи закрепления потребителей за поставщиками груза.

Задача закрепления потребителей за поставщиками груза формулируется следующим образом: имеется несколько поставщиков и получателей транспортно-однородного груза. Известны объемы наличия груза у каждого поставщика и потребности в нем у каждого получателя, а также расстояния между грузоотправителями и грузополучателями. Необходимо закрепить потребителей за поставщиками так, чтобы объем транспортной работы (в тонно-километрах) был минимальным.

Решим задачу закрепления потребителей за поставщиками для трех грузоотправителей и четырех грузополучателей. Пусть имеется четыре грузообразующих точки А1, А2, А3, А4 из которых следует вывезти однородный груз пятерым потребителям (Б1, Б2, Б3, Б4, Б5) в объеме соответственно 385, 315, 520 890 т. При этом потребителю Б1 необходимо доставить 385 т груза, Б2 - 315, Б3 - 520, Б4 - 440 и Б5 - 450.

Расстояние между грузоотправителями и потребителями указаны в табл. 2 (матрица кратчайших расстояний).

Таблица 2 - Расстояние между грузоотправителями и потребителями

Грузополу-

Грузоотправитель

Чатель

А1

А2

А3

А4

Б1

25

14

18

16

Б2

19

28

25

26

Б3

17,5

23,5

15,5

27,5

Б4

23

18

26

16

Б5

14

2

6

4

Рис. 3 Схема выполнения расчета

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

В представленном примере наличие груза равно потребности в грузе (2110 т), т. е. имеем закрытый тип транспортной задачи.

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

При построении допустимого плана методом минимума по строке порядок распределения груза по клеткам матрицы следующий:

    - отыскивают клетку с минимальным расстоянием CIj в первой строке и в ней записывают возможную загрузку; - если наличие груза по первой строке не исчерпано ( bJ aI ) , то в этой же строке отыскивают следующую клетку с минимальным расстоянием и заносят в нее возможную загрузку; - после распределения всего груза по первой строке переходят к распределению груза по следующей строке, причем только в клетках тех строк, которые еще полностью не загружены, и такие действия производят до полного распределения всего груза по клеткам матрицы; - в последней строке записывают загрузку в клетки тех потребителей, которые остались еще неудовлетворенными, независимо от величины CIj .

Рассмотрим построение опорного плана методом минимума по строке на примере вышеприведенных данных.

Таблица 3 - Построение опорного плана методом минимума по строке

Грузопо-

Грузоотправитель

Потребность

Лучатель

А1

А2

А3

А4

В грузе, т

Б1

25
    14 315

18
    16 70

385

Б2
    19 315

28

25

26

315

Б3

17,5

23,5
    15,5 520

27,5

520

Б4

23

18

26
    16 440

440

Б5
    14 70

2

6
    4 380

450

Наличие

Груза, т

385

315

520

890

2110

В строке Б1 минимальное расстояние имеет клетка А2Б1. Потребность в грузе у Б1 (385 т), но наличие у А2 только 315 т, поэтому удовлетворить полностью потребность мы не можем, в клетке А2Б1 записываем 315 т, далее выбираем вновь клетку с минимальным расстоянием на строке Б1. В данном случае это клетка А4Б1, наличие груза А4 (890 т) нам позволяет закрыть потребность Б1( 70 т), в клетке А4Б1 пишем 70 т, у грузоотправителя А4 остается 820 т.

В строке Б2 минимальное расстояние имеет клетка А1Б2. Потребность в грузе у Б2 (315 т), полностью удовлетворяется наличием в А1 (385 т), после этого у грузоотправителя А1 осталось 70 т.

В строке Б3 минимальное расстояние имеет клетка А3Б3. Потребность в грузе у Б3 (520 т) полностью удовлетворяется наличием в А3 (520 т), пишем 520 т в клетке А3Б3.

В строке Б4 минимальное расстояние имеет клетка А4Б4. Потребность в грузе у Б4 (440 т), что полностью удовлетворяется наличием в А4 (820 т), остаток в А4 - 380 т.

В строке Б5 потребность в грузе удовлетворяется частично наличием груза в пунктах А4 (380 т), в клетке А4Б4 записываем 380 т, оставшуюся потребность в размере 70 т может удовлетворить грузоотправитель А1, в наличие у которого 70 т.

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

P = 315*14+70*16+315*19+520*15,5+440*16+70*14+380*4 = 29115 ткм

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

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

Количество груза, помещаемое в каждую клетку, определяется наименьшей величиной груза у соответствующего поставщика или потребностью в грузе у соответствующего потребителя. Так, в табл. 4 в клетку А2Б5, отмеченную дважды, следует поместить 315 т груза, наличие груза у грузоотправителя А2 как раз составляет 315 т, потребность Б5 теперь составляет 135т. Все дважды отмеченные клетки загружены.

Следующей загружается клетка с наименьшим расстоянием с одним значком А4Б5 - вписываем 135т груза, наличие груза у грузоотправителя А4 (890 т.) позволяет закрыть потребность грузополучателя Б5, наличие груза у А4 теперь составляет 755т.

Далее из оставшихся клеток загружается клетка с наименьшим расстоянием с одним значком А3Б3. Потребность в грузе у Б3 (520 т.) полностью удовлетворяется наличием в А3 (520 т.).

Затем из оставшихся клеток загружается клетка с наименьшим расстоянием с одним значком А4Б4. Потребность в грузе у Б4 (440 т), что полностью удовлетворяется наличием в А4 (755 т), остаток в А4 - 315 т.

Из оставшихся клеток загружается клетка с наименьшим расстоянием с одним значком А1Б2. Потребность в грузе у Б2 (315 т.), полностью удовлетворяется наличием в А1 (385 т.), после этого у грузоотправителя А1 осталось 70 т.

Теперь из оставшихся клеток загружается клетка с наименьшим расстоянием А4Б1. Потребность в грузе удовлетворяется частично наличием груза в пунктах А4 (315 т), в клетке А4Б1 записываем 315 т., оставшуюся потребность в размере 70 т может удовлетворить грузоотправитель А1, в наличие у которого 70 т.

После того, как указанными способами груз будет распределен по клеткам матрицы, можно рассчитать объем транспортной работы в тонно-километрах для каждого из полученных опорных планов. Для дальнейших операций выбирается опорный план, которому соответствует минимальная транспортная работа.

После получения допустимого плана перевозок производится промежуточная проверка: необходимо, чтобы количество груза, записанное по клеткам каждого столбца матрицы, равнялось объему производства в данном столбце, а количество груза, записанное по клеткам каждой строки матрицы, равнялось объему потребления в этой строке.

Пока остается неясным, является ли полученное в табл. 4 распределение перевозок оптимальным. Для проверки оптимальности полученного распределения находят цифровые индексы, проставляемые в клетках вспомогательных строки и столбца (табл. 4).

Таблица 4 - Построение опорного плана методом двойного предпочтения

Грузопо-

Грузоотправитель

Потребность

Лучатель

А1

А2

А3

А4

В грузе, т

Б1
    25 70

14

18
    16 315

385

Б2
    19 315

28

25

26

315

Б3

17,5

23,5
    15,5 520

27,5

520

Б4

23

18

26
    16 440

440

Б5

14
    2 315

6
    4 135

450

Наличие

Груза, т

385

315

520

890

2110

P = 70*25+315*16+315*19+520*15,5+440*16+315*2+135*4 = 29045 ткм

Для дальнейшего рассмотрения выбираем опорный план методом минимума по строке, так как его грузооборот меньше (29045 т < 29115 т).

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

I + J = CIj , (4.1)

Где I - индекс в клетке вспомогательной строки ;

J - индекс в клетке вспомогательного столбца ;

CIj - расстояние в загруженной клетке.

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

M + n - 1 , (4.2)

Где m - число столбцов в матрице ;

N - число строк в матрице.

Если количество загруженных клеток в матрице будет меньше числа ( m + n - 1), то необходимо искусственно догрузить недостающее количество клеток, для этого в них записывают ноль. Ноль следует ставить в такую незагруженную клетку матрицы, в которой имеется минимальное расстояние (из числа незагруженных клеток) и один индекс для нее известен. (А3Б5)

В соответствии с правилом в клетке вспомогательного столбца 1 записываем ноль, затем находим индекс 2 для столбца А2:

1 + 1 = С Ij ; 1 = 0 ; 1 + 0 = 25 , следовательно, 1 = 25.

В столбце А4 имеем загруженную клетку А4Б2, по ней можем определить индекс столбца А4 : 4 + 1 = 16, 16 + 0 = 16, следовательно 4=16. Далее по аналогии проставляем дальнейшие индексы, результаты которых записаны в табл. 5.

Автомобильный транспорт перевозка маршрутизация

Таблица 5 - Построение оптимального плана

Грузопо-лучатель

Вспомога-тельные

Грузоотправитель

Потреб-ность

В грузе, т

Строка

А1

А2

А3

А4

Столбец

25

14

12

16

Б1

0
    25 70

14

18
    16 315

385

Б2

-6
    19 315

28

25

26

315

Б3

3,5

17,5

23,5
    15,5 520

27,5

520

Б4

0

23

18

26
    16 440

440

Б5

-12

14
    2 315
    6 0
    4 135

450

Наличие груза, т

385

315

520

890

2110

После определения вспомогательных индексов находим в матрице потенциальные клетки.

Потенциальной называется незагруженная клетка, у которой сумма цифровых индексов вспомогательных строки и столбца больше проставленного в ней расстояния, т. е.

I + J CIj . (4.3)

Рассматриваем последовательно незагруженные клетки матрицы (см. табл. 5). Находим одну потенциальную клетку: А1Б3. Для клетки А1Б3 сумма индексов 1 + 3 = 25+3,5=28,5, а расстояние - 17,5, величина потенциала равна 11 (28,5-17,5=11). Величины потенциала записывают в левых верхних углах потенциальных клеток в кружочке или со знаком "+". Величина потенциала показывает, что если перераспределить загрузку в потенциальные клетки, то на каждую тонну перемещенного груза может быть получена экономия в расстоянии перевозок по 11 км для клетки А1Б3.Так же и для клетки А1Б4. Для клетки А1Б4 сумма индексов 1 + 4 = 25+0=25, а расстояние - 23, величина потенциала равна 2 (25-23=2)

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

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

Контур строится следующим образом. От клетки с наибольшим по величине потенциалом ведется прямая линия по строке или столбцу до загруженной клетки, которой, в свою очередь, должна соответствовать еще одна загруженная клетка под прямым углом, и так до тех пор, пока линия не замкнется в исходной клетке. Движение при построении контура совершается строго под прямым углом. В табл. 4 получили шестиугольный контур с вершинами в клетках А1Б1, А4Б1,А4Б5,А3Б5,А3Б3,А1Б3.

Вершины контура обозначаются попеременно знаками "+" и "-", начиная с потенциальной (А1Б3), которой присваивается знак "-" . Потом из всех клеток, обозначенных знаком "+", выбирается наименьшая цифра загрузки (в А1Б1). Это количество груза (70 т) вычитается из загрузки, указанной в клетках со знаком "+", и прибавляется к загрузке в клетках со знаком "-". Полученные цифры записывают в новую матрицу (табл. 6), куда без изменений переносят загрузки тех клеток, которые не являются вершинами контура.

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

Таблица 6 - Оптимальный план закрепления потребителей за поставщиками

Грузопо-лучатель

Вспомога-тельные

Грузоотправитель

Потреб-ность

В грузе, т

Строка

А1

А2

А3

А4

Столбец

20

14

18

16

Б1

0

25

14

18
    16 385

385

Б2

-1
    19 315

28

25

26

315

Б3

-2,5
    17,5 70

23,5
    15,5 450

27,5

520

Б4

0

23

18

26
    16 440

440

Б5

-12

14
    2 315
    6 70
    4 65

450

Наличие груза, т

385

315

520

890

2110

Похожие статьи




Решение транспортной задачи методом МОДИ - Оперативное планирование перевозок грузов

Предыдущая | Следующая