Решение транспортной задачи методом МОДИ

 

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

 

 

 

 

Нет

Потенциальные

 

клетки есть

 

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

 

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

 

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

5.3. Решим задачу закрепления потребителей за поставщиками для четырех грузоотправителей и пяти грузополучателей. Пусть имеется три грузообразующих точки А1, А2, А3, из которых следует вывезти однородный груз четырем потребителям (В1, В2, В3, В4): соответственно 400, 600, 1000т. При этом потребителю В1 необходимо доставить 200 т груза, В2 - 400, В3 -800 и В4 - 600.

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

Таблица 5.1

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

Грузополу-	Грузоотправитель
чатель	А1	А2	А3
В1
В2
В3
В4

 

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

Матрица исходных данных имеет следующий вид (табл. 5.2).

Таблица 5.2

Матрица исходных данных

 

Грузопо-	Грузоотправитель	Потребность
лучатель	А1	А2	А3	в грузе, т
В1
В2
В3
В4
Наличие груза, т

 

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

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

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

- отыскивают клетку с минимальным расстоянием C_ij в первой строке и в ней записывают возможную загрузку;

- если наличие груза по первой строке не исчерпано (b_j < a_i), то в этой же строке отыскивают следующую клетку с минимальным расстоянием и заносят в нее возможную загрузку;

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

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

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

 

Таблица 5.3

Построение опорного плана методом минимума по строке

 

Грузопо-	Грузоотправитель	Потребность
лучатель	А1	А2	А3	в грузе, т
В1
В2
В3
В4
Наличие груза, т

 

В строке В1 минимальное расстояние имеет клетка А3В1. Потребность в грузе у В1 (200 т) полностью удовлетворяется наличием в А3 (1000 т), после этого у грузоотправителя осталось 800 т.

В строке В2 минимальное расстояние имеет клетка А2В2. Потребность в грузе у В2 (400 т) полностью удовлетворяется наличием в А2 (600 т), после этого у грузоотправителя осталось 200 т.

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

В строке В4 потребность в грузе удовлетворяется наличием груза в пункте А1 (400 т) и остатком груза в пункте А2 (200 т).

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

- вначале выбирают и отмечают знаком х наименьшее расстояние в каждой строке;

- затем это же делают по столбцам;

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

- затем загружают клетки, отмеченные один раз;

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

Количество груза, помещаемое в каждую клетку, определяется наименьшей величиной груза у соответствующего поставщика или потребностью в грузе у соответствующего потребителя. Так, в табл. 5.4 в клетку А3В1, отмеченную дважды, следует поместить 200 т груза, хотя наличие груза у грузоотправителя А3 составляет 1000 т. В клетку А2В2 вписываем 400 т груза по максимальной потребности, хотя наличие груза в пункте А2 600 т. Следующая клетка, отмеченная дважды, - А1В4, в нее помещаем 400 т, что соответствует максимальному наличию груза у грузоотправителя. Все дважды отмеченные клетки загружены. Следующей загружается клетка с одним значком А3В3 - 800 т, что соответствует максимальной потребности в грузе и остатку груза у грузоотправителя. Все отмеченные значками клетки загружены, но осталась неудовлетворенной потребность грузополучателя В4, а у грузоотправителя А2 остался нераспределенный груз. На пересечении строки В4 и столбца А2 загружаем клетку - 200 т.

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

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

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

Таблица 5.4

Построение опорного плана методом двойного предпочтения

 

Грузопо-	Грузоотправитель	Потребность
лучатель	А1	А2	А3	в грузе, т
В1			хх 2
В2		хх 2
В3			х 8
В4	хх 4
Наличие груза, т

 

 

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

 

a_i + b_j = C_ij^*, (5.1)

 

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

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

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

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

 

m + n - 1, (5.2)

 

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

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

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

В соответствии с правилом в клетке вспомогательного столбца b₁ записываем ноль, затем находим индекс a₃ для столбца А3:

 

a₃ + b₁ = С _ij; b₁ = 0; a₃ + 0 = 2, следовательно, a₃ = 2.

 

В столбце А3 имеем загруженную клетку А3В3, по ней можем определить индекс строки В3: a₃ + b₃ = 8, 2 + b₃ = 8, следовательно b₃ =6.

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

 

Таблица 5.5

Построение оптимального плана

 

Грузопо-лучатель	Вспомога-тельные	Грузоотправитель	Потреб-ность
	строка	А1	А2	А3	в грузе, т
	столбец
В1			+2 8	0 2
В2	-8
В3			+4 12 -	+ 8
В4			+	-
Наличие груза, т

 

Среди незагруженных клеток находим клетку с минимальным расстоянием и одним известным индексом (А3В4) и в ней записываем ноль, в дальнейших расчетах эта клетка рассматривается как загруженная. Теперь можем найти недостающие индексы.

Аналогично вышеприведенным расчетам определяем индексы столбца А1 (a₁ = 0), строки В4 (b₄ = 4), столбца А2 (a₂ = 10), строки В2 (b₂ = -8).

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

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

 

a_i + b_j > C_{ij .} (5.3)

 

Рассматриваем последовательно незагруженные клетки матрицы (см. табл. 5.5). Находим две потенциальные клетки: А2В1 и А2В3. Для клетки А2В1 сумма индексов a₂ + b₁ = 10+0=10, а расстояние - 8, величина потенциала равна 2 (10-8=2). Для клетки А2В3 потенциал равен 4 (10+6-12 = 4). Величины потенциала записывают в левых верхних углах потенциальных клеток в кружочке. Величина потенциала показывает, что если перераспределить загрузку в потенциальные клетки, то на каждую тонну перемещенного груза может быть получена экономия в расстоянии перевозок по 2 км для клетки А2В1 и 4 км для клетки А2В3.

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

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

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

Вершины контура обозначаются попеременно знаками “+” и”-”, начиная с потенциальной (А2В3), которой присваивается знак “-”. Потом из всех клеток, обозначенных знаком “+”, выбирается наименьшая цифра загрузки (в А2В4). Это количество груза (200 т) вычитается из загрузки, указанной в клетках со знаком “+”, и прибавляется к загрузке в клетках со знаком “-”. Полученные цифры записывают в новую матрицу (табл. 5.6), куда без изменений переносят загрузки тех клеток, которые не являются вершинами контура.

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

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

 

 

Таблица 5.6

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

 

Грузопо-лучатель	Вспомога-тельные	Грузоотправитель	Потреб-ность
	строка	А1	А2	А3	в грузе, т
	столбец
В1
В2	-4
В3
В4
Наличие груза, т