КУРСАЧ. Способы разработки рациональных условий маршрутов транспортировки
 Скачать 71.69 Kb.
|
|
2.2.2. Способ наименьшего элемента по столбцу (строке) Несколько лучшими способами составления базисного плана являются способы наименьшего элемента по столбцу или наименьшего элемента по строке. При составлении базисного плана способом наименьшего элемента по столбцу поочередно в столбцах матрицы отмечаются клетки с минимальным значением аij и в них заносятся поставки. Если при записи поставок спрос по столбцу удовлетворен не полностью, ищется следующий по величине показатель аij, и так до полного удовлетворения спроса. Только после этого переходят на следующий столбец. Когда в столбце два или несколько одинаковых по величине минимальных показателей аij, то поставки могут быть размещены в любом из них. Результаты составления базисного плана этим способом приведены в табл. 3. При базисном плане, полученном способом наименьшего элемента по столбцу (табл. 3), транспортная работа составит F(x) = 3*70 + 0*285 + 0*310 + 2*270 + 3*180 + 2*210 + 2*290 + 3*70 + 2*270 = 3040 тыс. руб. Таблица 3 - Базисный план, составленный способом наименьшего элемента по столбцу
Базисный план является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи. 2.2.3. Способ аппроксимации У. Фогеля По мнению У. Фогеля, его способ может заменить во многих случаях методы линейного программирования. На самом деле его можно применять только для составления базисного плана, а затем для решения задачи использовать обычную процедуру линейного программирования. При составлении базисного плана поставок способом аппроксимации У. Фогеля исходные данные заносятся в таблицу, которая отличается от матрицы метода потенциалов тем, что имеет дополнительную строку и столбец разностей (табл. 5). Таблица 5 - Базисный план поставок способом аппроксимации У. Фогеля
Процесс составления базисного плана начинается с определения разностей между двумя наименьшими элементами каждой строки и каждого столбца матрицы. Так, в столбце В2 минимальный элемент равен 3 в клетке A3 B2. Затем из всех разностей столбцов и строк выбирается наибольшая. В нашем примере это цифра 2 в столбце В2. Клетка с наименьшим расстоянием (при решении задачи на минимум), расположенная в строке или столбце, имеющая наибольшую разницу, загружается максимально возможным количеством груза (с учетом потребности грузопотребляющего и возможности грузообразующего пунктов). Смысл способа У. Фогеля заключается в следующем. Найденные разности показывают, насколько больше будут расстояния, если в соответствующем столбце или строке поставка будет записана не в клетку, где находится минимальный в этом столбце или строке элемент, а в клетку, где находится элемент, следующий за ним по величине. Там, где разность оказывается наивысшей, будут наибольшие потери на единицу продукции, если поставка не попадет в клетку с наименьшим оптимизирующим элементом. В нашем примере, записав максимальную поставку в клетку A3B2 в количестве 180 т, исключаем показатели критерия оптимальности по этой строке, поскольку мощность поставщика А2 полностью исчерпана, и вновь определяем разности между наименьшими элементами по строкам и столбцам матрицы (табл. 6) Если оказывается несколько одинаковых разностей, имеющих максимальное значение, то в соответствующих им столбцах или строчках находят и загружают седловую точку. Седловой точкой называют клетку таблицы, расстояние которой имеет наименьшее значение (при решении задачи на минимум) из всех расстояний ее строки и столбца или наибольшее значение при решении задачи на максимум. При наличии независимых седловых точек, т. е. расположенных в различных строках и столбцах, загружают их одновременно. Когда седловые точки отсутствуют, находят дополнительные разницы. Загружается клетка, у строки или столбца которой дополнительная разница будет наибольшей. В нашем примере седловой точкой будет клетка А1В4, в которую записывается максимально возможная поставка, и т. д. Итоговая таблица - базисного плана поставок способом аппроксимации У. Фогеля приведена в таблице 5. Таблица 5 - Базисный план поставок способом аппроксимации У. Фогеля
При базисном плане, полученном способом аппроксимации У. Фогеля, транспортная работа составит. F(x) = 3*180 + 0*175 + 0*310 + 2*270 + 3*180 + 0*110 + 2*290 + 3*70 + 2*270 = 2950 тыс. руб. | ||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||