Маршрутизация грузовых перевозок и транспортная задача. Логистика ПЗ. Курсовой проект По дисциплине Логистика на транспорте Студент 5 курса 23. 05. 01 Климашев А. А
 Скачать 0.68 Mb.
|
|
2.Сущность транспортной задачи Транспортная задача - это специальный вид задачи линейного программирования. Для решения транспортной задачи можно использовать методы решения задач линейного программирования, однако ввиду специфического вида задачи, были построены алгоритмы специально для решения этой задачи. 2.1 Математическая постановка транспортной задачи. Общая постановка транспортной задачи заключается в определении оптимального плана перевозок некоторого однородного груза из пунктов отправления A1, A2,..., Am в пункты назначения B1, B2,..., Bn. Критерий оптимальности берется минимальная стоимость перевозки или минимальное время доставки груза. Рассмотрим транспортную задачу, где в качестве критерия оптимальности взята минимальная стоимость перевозок всего груза. Обозначим через Сij тарифы перевозки единицы груза из пункта отправления i в пункт назначения j. Обозначим через Ai запасы груза i-м пункте отправления, а через Bj потребности груза j-м пункте назначения, а через Xj количество единиц груза переводимого из пункта отправления i в пункт назначения j. Тогда математическая модель транспортной задачи состоит в определении минимального значения функции
при условиях
Поскольку удовлетворяется условия (1.2)−(1.4), то обеспечивается доставка необходимого количества груза в каждый из пунктов назначения, вывоз груза из всех пунктов отправления, а также исключаются обратные перевозки. Определение 1. Любое неотрицательное решение Xij=∥xij∥ (i=1,..,m; j=1,...,n) систем (1.2) и (1.3) называется допустимым планом транспортной задачи. Определение 2. План  при котором функция (1.1) принимает минимальное значение, называется оптимальным планом транспортной задачи.Если сумма груза у поставщиков равно общей сумме потребностей в пунктах назначения:
то модель транспортной задачи называется закрытой . Если (1.5) не удовлетворяется, то модель транспортной задачи называется открытой. Теорема 1. Для разрешимости транспортной задачи необходимо и достаточно, чтобы выполнялось условие (1.5). В случае превышения запаса над потребностью, т.е. при
вводится фиктивный (n+1)-ый пункт назначения с потребностью
Соответствующие тарифы считаются равными нулю: ci n+1=0 (i=1,...,m). После этих преобразований получим закрытую модель транспортной задачи. Аналогично, при  вводится фиктивный (m+1) пункт отправления с грузом  а тарифы полагаются равными нулю: cm+1j=0 (j=1,...,n). После этих преобразований получим закрытую модель транспортной задачи.Обычно данные транспортной задачи записывают в виде таблицы:
Число переменных Xij равно mn, где m число пунктов отправления , а n число пунктов назначения. Число уравнений в (1.2) и (1.3) равно m+n. Так как мы рассматриваем закрытую модель транспортной задачи (выполняется равенство (1.5)), то число линейно независимых уравнений равно m+n−1. Следовательно опорный план транспортной задачи может иметь не более m+n−1 отличных от нуля неизвестных. Если в опорном плане количество отличных от нуля компонентов равно в точности m+n−1, то опорный план называется невырожденным, а если меньше − то вырожденным. 2.2 Определение опорного плана. Опорный план транспортной задачи находим следующим образом. На каждом шаге в таблице условий задачи заполняем одну клетку, которая называется занятой. Обозначим через Kij клетку, где i -номер пункта отправления (строка), j-номер пункта назначения (столбец). Клетку Kij заполняем так, чтобы удовлетворялись полностью потребности пункта назначения j, либо обеспечивался полный вывоз груза из пункта отправления i. В первом случае временно исключаем из рассмотрения столбец j и изменяем запас груза пункта отправления i. Во втором случае временно исключаем из рассмотрения строку i и изменяем потребность груза пункта назначения j. Далее повторяем процедуру с таблицей условий с исключенной строкой или столбцом. В m+n−1-ом шаге получаем задачу с одним пунктом отправления и одним пунктом назначения. Остается свободной одна клетка. Запасы оставшегося пункта отправления будут равны потребностям пункта назначения. Заполнив эту клетку заканчиваем m+n−1-ый шаг и получаем опорный план. Если на некотором шаге (но не на последнем) потребности очередного пункта назначения равны запасам пункта отправления, то временно исключаем из рассмотрения либо столбец, либо строку (только одно из двух). Тогда либо запасы данного пункта отправления, либо потребности данного пункта назначения считаем равным нулю. Этот нуль при очередном шаге записываем в очередную заполняемую клетку. Данный подход обеспечивает ровно m+n−1 занятых клеток, что обеспечивает возможность проверки полученного опорного плана на оптимальность и нахождение оптимального плана. 2.3 Метод северно-западного угла При нахождении опорного плана транспортной задачи методом северно-западного угла, заполнение клеток таблицы условий начинают с верхней левой клетки K11 поэтому метод и называется "метод северно западного угла"). Рассмотрим метод на конкретном примере. Пример 1. На три базы A1, A2, A3 поступил очередной груз в количествах равных 140, 160, 120 ед. Этот груз требуется перевезти в четыре пунктов назначения B1, B2, B3, B4 в количествах 150, 90, 100, 80. Тарифы перевозок представлена матрицей
Найти план перевозок данной транспортной задачи методом северно-западного угла. Решение. Запишем все данные в таблицу условий:
Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненных клетках таблицы. Наличие груза у поставщиков равно: ∑Ai=140+160+120=420. Общая потребность в грузе в пунктах назначения равна: ∑Bj=150+90+100+80=420. ∑Ai=∑Bj. Модель транспортной задачи является закрытой. Следовательно она разрешима. Найдем опорный план задачи методом северно-западного угла. A1≤B1. Следовательно в клетку (A1, B1 ) помещаем число min(A1, B1)=140. Запасы пункта A1 полностью исчерпаны. Поэтому исключаем из рассмотрения строку A1 и будем считать потребности пункта B1 равными 150−140=10.
A2>B1. Следовательно в клетку (A2, B1) помещаем число min(A2, B1)=10. Потребности пункта B1 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B1 и будем считать запасы пункта A2 равными 160−10=150.
Таким образом, продолжая процедуру в m+n−1-ом шаге получим:
Запишем полученный опорный план:
При этом плане стоимость перевозок вычисляется так: F=2·140+8·10+4·90+ 1·60+3·40+6·80=1380. 2.4 Метод минимального элемента В отличие от метода северно-западного угла, в методе минимального элемента выбор пунктов отправления и пунктов назначения производится ориентируясь на тарифы перевозок, т.е. в каждом шаге нужно выбрать клетку с минимальным тарифом перевозок. Если таких клеток несколько, то выбираем один из них. Надо отметить, что при данном методе определения заполняемой клетки, стоимость перевозок как правило бывает меньше, чем при методе северно западного угла. Поэтому целесообразно начальный опорный план найти методом минимального элемента. Рассмотрим метод минимального элемента на примере. Пример 2. Найти опорный план транспортной задачи представленной в таблице условий ниже методом минимального элемента:
Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненных клетках таблицы. Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей.
Наличие груза у поставщиков равно:  Общая потребность в грузе в пунктах назначения равна:  Модель транспортной задачи является закрытой. Следовательно она разрешима. Минимальный тариф равный 1 находится в клетке (A1, B3). Поэтому заполняем эти клетки. A1>B3. Следовательно в клетку (A1, B3) помещаем число 70. Потребности пункта B3 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B3 и будем считать запасы пункта A1 равными 150−70=80.
Минимальный тариф равный 1 находится в клетке (A2, B4). Поэтому заполняем эту клетку. A2>B4. Следовательно в клетку (A2, B4) помещаем число 40. Потребности пункта B4 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B4 и будем считать запасы пункта A2 равными 100−40=60.
Таким образом, продолжая процедуру в m+n−1-ом шаге получим:
Запишем полученный опорный план:
При этом плане стоимость перевозок вычисляется так:
2.5 Метод аппроксимации Фогеля Суть метода аппроксимации Фогеля заключается в следующем. Для каждой строки и для каждого столбца находим разности между двумя записанными в них минимальными тарифами. Полученные разности записываем в специально отведенные для этого столбце и в строке в таблице условий задачи. Среди указанных разностей выбираем максимальную. В строке (или в столбце), которой данная разность соответствует, определяем минимальный тариф. Клетку, в которой он записан заполняем на данной итерации. Если минимальный тариф одинаков для нескольких клеток данной строки (столбца), то для заполнения выбираем ту клетку, которая соответствует наибольшей разности между двумя минимальными тарифами в данном столбце (строке). Применение метода аппроксимации Фогеля позволяет получить либо опорный план, близкий к оптимальному, либо сам оптимальный план. Рассмотрим метод аппроксимации Фогеля на примере 2, рассмотренной выше. Пример 3. Найти опорный план транспортной задачи представленной в таблице условий ниже методом аппроксимации Фогеля:
Число пунктов отправления m=3, а число пунктов назначения n=4. Следовательно опорный план задачи определяется числами, стоящими в m+n−1=3+4−1=6 заполненных клетках таблицы. Тарифы перевозок единицы груза из каждого пункта отправления во все пункты назначения задаются матрицей:
Наличие груза у поставщиков равно: Общая потребность в грузе в пунктах назначения равна: Модель транспортной задачи является закрытой. Следовательно она разрешима. Для каждой строки Ai найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце. В строке 1 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 3, разность между ними 3−3=0. Для каждого столбца Bj найдем разности между двумя минимальными тарифами, записанными в данном столбце и поместим их в соответствующей дополнительной строке. В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этом столбце минимальный тариф равен 1 и находится в пересечении строки A 1 и столбца B3. Следовательно заполняем эту клетку. A1>B3. Следовательно в клетку помещаем число 70. Потребности пункта B3 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B3 и будем считать запасы пункта A1 равными 150−70=80.
Для каждой строки Ai найдем разности между двумя минимальными тарифами, записанными в данной строке и поместим их в соответствующем дополнительном столбце. В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 3 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. В строке 1 минимальный тариф равен 2, а следующий за ним равен 2, разность между ними 2−2=0. В строке 2 минимальный тариф равен 1, а следующий за ним равен 3, разность между ними 3−1=2. В строке 3 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. Для каждого столбца Bj найдем разности между двумя минимальными тарифами, записанными в данном столбце и поместим их в соответствующей дополнительной строке. В столбце 1 минимальный тариф равен 2, а следующий за ним равен 3, разность между ними 3−2=1. В столбце 2 минимальный тариф равен 3, а следующий за ним равен 4, разность между ними 4−3=1. В столбце 4 минимальный тариф равен 1, а следующий за ним равен 2, разность между ними 2−1=1. Вычислив все разности выберем наибольшую из них. В данном случае наибольшая разница равна 2. В этой строке минимальный тариф равен 1 и находится в пересечении строки A2 и столбца B4. Следовательно заполняем эту клетку. A2>B4. Следовательно в клетку помещаем число 40. Потребности пункта B4 полностью удовлетворены. Поэтому исключаем из рассмотрения столбец B4 и будем считать запасы пункта A2 равными 100−40=60.
Таким образом, продолжая процедуру в m+n−1-ом шаге получим:
Запишем полученный опорный план:
При этом плане стоимость перевозок вычисляется так: F=2·40+3·40+1·70+ 4·60+1·40+3·100=850. |
,
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.