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

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

Рассмотрим оптимизацию грузовых перевозок методом решения транспортной задачи – это однокритериальная оптимизация перевозок. Транспортная задача формулируется следующим образом:

Имеется m отправителей и n получателей одинакового вида продукции. Известны объемы производства каждого поставщика и объемы потребления каждого получателя. Необходимо составить план доставки продукции, при котором транспортная работа будет стремиться к минимуму. Эта задача решается методом потенциалов, суть которого заключается в оптимальном закреплении потребителей грузов за поставщиками. Пример базисного плана:

В правом верхнем углу матрицы проставлены значения расстояний между соответствующими поставщиками и потребителями. Число загруженных клеток матрицы должно быть равно m + n – 1, т.е. в данном случае 3 + 4 – 1 = 6. Если число загруженных клеток меньше, то дополнительно вводится нулевая загрузка.

После составления базисного плана методом наименьшего элемента по строке или столбцу он проверяется на оптимальность методом потенциалов. Для этого в задачу вводятся потенциалы строк и столбцов матрицы. Потенциалы – это вспомогательные величины, обладающие тем свойством, что их разность равняется значениям коэффициентов при переменных целевой функции (l_ij): V – U = l, где U – потенциалы строк; V – потенциалы столбцов.

Для столбца, где находится загруженная клетка с наибольшим расстоянием, потенциал принимается равным 0. Потенциалы строк вычисляются по уравнению: V = U + l. Для столбцов – по уравнению: U = V – l. Потенциалы считаются только для загруженных клеток. В теории метода доказано, что решение оптимально, если для всех незагруженных клеток выполняется условие: V – U £ l. В данном случае этому условию не удовлетворяет клетка А2Б1. Для этой клетки строится контур – замкнутая линия состоящая из прямых вертикальных и горизонтальных отрезков, все вершины которых лежат в загруженных клетках. Выбранной клетке (А2Б1) присваивается знак "–", а остальным вершинам контура – попеременно знаки "+" и "–". Из всех клеток со знаком "+" выбирают наименьшую загрузку. Эту наименьшую загрузку вычитают из загрузки, указанной в клетках со знаком "+" и прибавляют в клетки со знаком "–".Теперь надо снова определить потенциалы и проверить решение на оптимальность.

Теперь все клетки удовлетворяют условию оптимальности.

Способ аппроксимации Фогеля позволяет сократить число этапов при составлении базисного плана.

Процесс составления базисного плана по Фогелю начинается с определения разностей между двумя наименьшими элементами каждой строки и каждого столбца. Выбирается наибольшее значение разностей. В данном случае 12. Клетку с наименьшим расстоянием в этом столбце (строке) загружают по максимуму. Из пункта А3 в Б3 все возможные ездки были сделаны, следовательно матрица перерисовывается снова без соответствующей строки (столбца). При этом суммарные запасы ресурсов поставщиков должны по прежнему равняться суммарной потребности потребителей.

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

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

Итоговый план выглядит следующим образом:

Как видно, план идентичен матрице, полученной в результате решения транспортной задачи методом потенциалов.

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

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