Задача транспорта

 

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

 

10. Способ наименьшего элемента в матрице

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

Функционал полученного решения:

L(x) = 6 • 25 + 12 • 75 +5 • 75+16 • 25+ 18 • 75 + 14 • 50 + 12 • 150 +22 • 25 = 7625 т•км.

Обычно  способ наименьшего элемента в матрице  дает допустимое решение, более близкое к оптимальному, чем способ северо-западного угла. В условии нашего примера суммарный объем транспортной работы меньше на 2050 т•км (96•75 - 7625 = 2050). Способ наименьшего элемента в матрице целесообразно использовать при решении небольших матриц, поскольку с увеличением размера матрицы его применение затрудняется. В данном случае хорошие результаты позволяет получить способ двойного предпочтения.

Таблица 4

 

11.Способ двойного предпочтения

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

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

 

12. Способ аппроксимации Фогеля

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

Таблица 5

 

При этом способе исходная матрица дополняется  столбцом и строкой разностей. Затем  в каждой строке и каждом столбце  матрицы отыскивают два наименьших элемента и определяют абсолютную разность между ними, которую заносят соответственно разности по строке в столбец разностей, разности по столбцам - в строку разностей. Если две клетки в одной и той же строке или столбце имеют одинаковые значения элементов, то разность для этой строки или столбца принимается равной нулю и также проставляется в соответствующую строку или столбец. Затем выбирают наибольшую величину разности независимо от того, стоит ли она в столбце или строке разностей. В клетку с минимальным элементом в данной строке или столбце заносят максимально возможную загрузку, учитывая при этом соотношение ресурса поставщика и спрос потребителя. Наибольшая разность зачеркивается. Если окажется, что спрос потребителя полностью удовлетворен или ресурс поставщика полностью исчерпан, в соответствующей строке или столбце разностей проставляется буква К (конец) и данная строка или столбец матрицы из дальнейшего рассмотрения исключается. После заполнения клетки матрицы разности пересчитывают и операции повторяются вновь до тех пор, пока не будет составлена допустимая программа распределения. При наличии двух одинаковых наибольших разностей загрузку записывают в клетку, которая имеет меньший элемент по строке и столбцу. Такая клетка называется Седловой. Последние распределения можно сделать без вычисления разностей, поскольку остается несколько незагруженных клеток, поставки в которые очевидны.

 

13. Решение транспортных задач, имеющих некоторые дополнительные условия

13.1 Задача с распределением резерва (спрос не равен предложению)

 

Если  в задаче спрос потребителей меньше предложения поставщиков, то задача решается следующим образом. Составляется таблица по форме табл. 6, в которую вводится фиктивный (несуществующий) потребитель. Его спрос равен разности между суммами фактических величин предложения и спроса (2000 -1400 = 600), т.е. 600 т. Для фиктивного потребителя отводится дополнительный, четвертый столбец в таблице, куда и проставляют потребность в 600 т груза. Поскольку груз никуда не вывозится, то в углах клеток столбца B4 ставят нули (можно и любые другие цифры, но одинаковые величины). Дальше задача решается обычным путем по алгоритму метода потенциалов (распределительного метода), рассматривая столбец B4 как четвертый потребитель груза. В данном случае задача решена с помощью модифицированного распределительного метола. Полученное решение, кроме оптимального закрепления потребителей за грузоотправителями, доказывает, что наиболее рационально, с точки зрения транспортных затрат, иметь 400 т резервного запаса груза у поставщика А₁ и 200 т - у поставщика А₂.

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

 

13.2 Запрещение корреспонденции

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

Например, наложим запрет на перевозки груза  от поставщика А₂ потребителю В₂ (см. табл. 6). Чтобы решить задачу, достаточно вместо реального элемента целевой матрицы, стоящего в клетке А₂В₂, равного 2, поставить букву М, под которой подразумевается очень большое число, больше любого наперед заданного числа, или поставить какое-либо число, например 100, которое больше любого элемента целевой матрицы, имеющегося в данной задаче. В этом случае экономически невыгодно осуществлять поставку в эту клетку. Такой приём называется «блокированием клетки».

 

Таблица 6

 

 

 

 

 

13.3 Обязательная (директивная) корреспонденция

 

Директивная корреспонденция означает обязательность поставки из точки А_i; в точку В_j части или всего объема груза, имеющегося в точке А_i, В этом случае величина обязательной поставки вычитается из суммы спроса В_j и суммы ограничения А_i и при решении задачи не учитывается.

Например, из точки А₂ нужно обязательно поставить 400 т груза в В₃ (см. табл. 6). Следовательно, при решении задачи ограничения столбца В₃ и строки А₂ должны быть уменьшены на 400 т, т.е. будут равны для В₃ - 400 т (800 - 400 = 400) и для А₂ - 200 т (600 - 400 = 200).

При подсчете окончательного грузооборота обязательный объем (400•8 = 3200 т•км) прибавляют к полученному оптимальному объему грузооборота.

 

13.4. Открытая модель распределительного метода

 

Открытая  модель распределительного метода возникает  в тех случаях, когда отсутствует  какая-либо из групп ограничений — спрос b_j или предложение a_i. Это означает, что любой потребитель может взять всю сумму имеющихся у поставщиков материалов или, наоборот, любой из поставщиков может удовлетворить спрос всех потребителей данного материала.

Задача  решается просто. Если отсутствуют  ограничения по предложению, то ограничения  по спросу в каждом столбце таблицы  переносятся в клетки с оптимальным  элементом целевой матрицы данного  столбца, а при отсутствии ограничений  по спросу - в клетки каждой строки. Полученное решение всегда будет  оптимальным.

Рассмотрим  пример. Чтобы удовлетворить потребности  в строительном песке пяти потребителей В₁, В₂, В₃, В₄, В₅, его можно добывать в неограниченном количестве в любой из трёх точек А₁, А₂, А₃. Потребность в сутки: В₁ - 300 т, В₂ - 200 т, В₃ - 400 т, В₄ – 250 т, В₅ - 400 т.