В любой сфере деятельности человек неизбежно сталкивается с задачами оптимизации. Экономическое планирование, управление, распределение ограниченных ресурсов, анализ производственных процессов, проектирование сложных объектов всегда должно быть направлено на поиск наилучшего варианта с точки зрения намеченной цели.
Одной из распространенных задач оптимизации является транспортная задача.
Определим термины задачи таким образом: требуется развезти товар, находящийся на складах, по магазинам. При этом А – массив наличия товара на складах (в условных единицах: кг, шт., ящики и т.п.), В – массив потребностей магазинов, С – матрица тарифов (стоимости, расстояний и т.п.) для перевозки товаров со складов в магазины, D – матрица перевозок, показывающая, сколько товаров перевозится со складов в магазины, i – индекс (счетчик) складов, j – индекс магазинов.
Для решения транспортной задачи разработано несколько методов задания базового плана перевозок, являющегося первым приближением для оптимизации. Рассмотрим наиболее распространенные из них:
1) Метод северо-западного угла. Просматривается матрица перевозок D, начиная с левого верхнего угла (клетки). Находится незанятая клетка, в нее записывается величина Dij=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для левой верхней клетки оставшейся матрицы до тех пор, пока весь запас товаров не будет исчерпан.
2) Метод Двойного Предпочтения. Просматривается вся матрица тарифов перевозок и из нее выбирается клетка с наименьшим значением тарифа Cij. И в строке и в столбце значение должно быть минимальным. Затем в данную клетку записывается величина D=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. При наличии нескольких клеток с одинаковыми значениями выбирается произвольная. Обнулившаяся строка и столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.
3) Метод минимального элемента. Просматривается вся матрица тарифов перевозок, и из нее выбирается клетка с наименьшим значением тарифа Cij, При наличии нескольких клеток с одинаковыми значениями выбирается произвольная. Затем в данную клетку записывается величина D=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.
4) Метод Фогеля. Просматриваются все строки и столбцы матрицы тарифов, вычисляется разность между двумя наименьшими элементами в строке или в столбце. Затем из всех этих разностей максимальная. По индексу наименьшего элемента, соответствующего этой разности выбираются строка и столбец. Затем в данную клетку записывается величина D=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.
Различие этих методов заключается как в простоте или сложности реализации так и в “качестве” начального решения, т.е. насколько начальное решение ближе к оптимальному. В общем случае метод Фогеля дает наилучшее решение, а метод северо-западного угла – наихудшее. Однако метод северо-западного угла проще реализуется и требует меньшего объема вычислений.
Но ни в одном из этих методов не рассматриваются такие параметры задачи, как величины запасов товаров на складах и потребности магазинов. А они подчас очень сильно влияют на оценку как оптимального так и базового планов перевозок. В данной статье предлагается расширение методов задания базового плана перевозок, учитывающее величины значений наличия и потребностей товаров на складах и в магазинах.
1) Метод Приоритета Больших перевозок. Основой для него является метод Минимального Элемента. Просматривается вся матрица тарифов перевозок, и из нее выбирается клетка с наименьшим значением тарифа Cij, При наличии нескольких клеток с одинаковыми значениями выбирается та, в которой Dij=MIN(Ai, Bj) максимально (этот этап определяет различие методов). При наличии нескольких клеток с одинаковыми значениями выбирается произвольная.. Затем в данную клетку записывается величина Dij=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.
2) Метод Размена Больших значений. Он заключается в том, что просматриваются значения параметров складов и магазинов. Из этих параметров выбирается наибольшее значение. При наличии нескольких одинаковых значений в соответствующих строках или столбцах выбирается минимальное значение тарифа в этих строках (столбцах). Если опять получилось несколько одинаковых значений, то выбирается максимальное Dij=MIN(Ai,Bj). При наличии нескольких одинаковых на этом этапе выбирается первое из имеющихся с приоритетом складов. Затем в выбранную клетку записывается величина Dij=MIN(Ai, Bj). Она вычитается из запасов и потребностей соответствующего склада и магазина. Обнулившаяся строка или столбец исключаются из рассмотрения, затем процесс повторяется для оставшейся части матрицы до тех пор, пока весь запас товаров не будет исчерпан.
Сравнительное исследование известных методов и разработанных нами показало, что метод Приоритета Больших Перевозок практически равноценен методу минимальных значений, а метод Размена больших Значений не уступает методу Фогеля, а в ряде случаев превосходит его. В сравнительной таблице приводятся результаты решения задач, взятых из произвольных источников. Задачи с номерами от 15 до 35 приведены из книги Лунгу К. Н. Линейное программирование. Руководство к решению задач. М. Физматлит, 2005, глава 2.
|
Из таблицы видно, что метод Приоритета Больших Перевозок в 7‑и задачах уступает методу Минимальных Значений, в 24-х дает одинаковую с ним оценку (отмечено жирным шрифтом) и в 6-и – превосходит этот метод (жирный наклонный шрифт).
Метод Размена Больших Значений определенно лучше метода Минимальных Значений, он в 18-х задачах дает лучшую оценку и в 7-и одинаковую. По сравнению с методом Фогеля в 12-и задачах оценка равна или лучше (жирный шрифт). Более того, В 7-и задачах метод дает сразу оптимальный план перевозок (шрифт жирный наклонный).
Выводы
Из рассмотренного видно, что метод Приоритета Больших Перевозок не дает больших преимуществ по сравнению с общепринятыми методами, в частности, методом Минимальных Значений.
Но, в свою очередь, метод Размена Больших Значений заслуживает внимания по нескольким причинам:
1) Оценка метода почти не уступает общепринятому методу Фогеля при более простой реализации;
2) Понятный физический смысл метода (перевозка больших объемов при прочих равных условиях предпочтительнее) делает его более привлекательным для реализации по сравнению с тем же методом Фогеля;
3) Реализация метода сама по себе не представляет больших сложностей.
Количество просмотров публикации: Please wait