Применение алгоритма симплексного метода решения транспортной задачи для определения оптимального распределения объемов поставок от производителей по пунктам потребления
Общая черта матричных способов решения транспортной задачи – необходимость составления матрицы стоимостей (кратчайших расстояний, времени, расходов и др.), а это дело довольно трудоемкое. Но, как правило, однажды составленная матрица служит для большого числа решений длительное время. Поэтому затраты на ее составление оправдываются.
Одним из перспективных направлений решения классической транспортной задачи является метод потенциалов (или симплексный метод), разработанный Л.А. Канторовичем и М.К. Гавуриным [1, 2].
Потенциалами называются условные числа ui и vj, приписанные определенным образом к каждой строке i и к каждому столбцу j матрицы. Решение сводится к отысканию таких значений потенциалов, при которых выполняется следующее условие оптимальности: для каждой клетки сумма (разность) потенциалов строки и столбца должна быть меньше или равна стоимости перевозок, причем для занятых клеток – точно равна стоимости перевозок, т. е.
ui v j cij , xij 0 . (1)
ui v j cij , xij 0
Если определены значения потенциалов, удовлетворяющие этому условию, то найден оптимальный план, обеспечивающий минимизацию целевой функции. Экономический смысл потенциалов заключается в том, что их разность для любой назначенной перевозки точно отображает реальные затраты на транспортировку. Поэтому отправителям и получателям грузов можно присвоить такие значения потенциалов, при которых любая другая перевозка (не входящая в оптимальный план) не будет более выгодной (затраты на транспортировку), чем перевозки оптимального плана.
Для максимизации целевой функции необходимо: либо изменить условие оптимальности для свободных элементов матрицы ui ± vj > cij, либо изменить знак на обратный у всех значений стоимости. Рассмотрим применение алгоритма симплексного метода решения транспортной задачи для определения оптимального распределения объемов поставок серной кислоты от производителей по филиалам потребления.
Такой алгоритм состоит из следующих этапов (рис.1):
Рис.1. Блок-схема алгоритма симплициального метода решения транспортной задачи по определению оптимального варианта распределения объемов поставок
- Построение начального плана. В данном случае используются статистические данные.
- Вычисление потенциалов. Схема расчета заключается в том, что одному из столбцов (или строк) присваивается произвольное значение потенциала, например 0. Чтобы среди потенциалов было меньше отрицательных чисел, нуль присваивают столбцу или строке с возможно меньшими значениями «стоимости» cij в занятых клетках. Используя условие оптимальности (1), вычисляются по занятым элементам все остальные потенциалы.
- Проверка по условию оптимальности. Все свободные элементы матрицы необходимо проверить по условию оптимальности (1). Если оно выполнено для каждого элемента, то план оптимален. В противном случае в соответствующем элементе проставляют величину нарушения этого условия со знаком плюс.
- Цикл пересчета. Выбираем потенциальную клетку с наибольшей величиной нарушения и назначаем в нее новую перевозку. Чтобы определить величину вводимой перевозки, строят замкнутый контур, двигаясь от выбранной клетки прямолинейными ходами с поворотами в занятых клетках.
Если в ходе оптимизации найден оптимальный вариант плана распределения потоков серной кислоты, то экономия общей «стоимости» транспортной работы будет равна
с сначал сопт , (2)
где сначал – общая «стоимость» транспортной работы при начальном плане распределения объемов перевозок (вагоно-км);
сопт – общая «стоимость» транспортной работы при оптимальном плане распределения объемов перевозок (вагоно-км).
Рассмотрим начальный (договорной) план распределения объемов поставок серной кислоты от производителей по филиалам. Отметим, что данный начальный план составлен договорными отношениями между поставщиками и потребителями (табл.1).
Таблица 1. Исходная матрица транспортной задачи
|
Потребитель 1 |
Потребитель 2 |
поставка (цистерны) |
|
|
Поставщик 1 |
987 4 714 |
1359 6 271 |
al = 10 985 |
|
Поставщик 2 |
1488 871 |
1860 0 |
а2 = 871 |
|
Поставщик 3 |
1792 1 943 |
2164 3 147 |
а3 = 5 090 |
|
Поставщик 4 |
1890 1 290 |
2262 484 |
а4 = 1 774 |
|
Поставщик 5 |
2089 980 |
1990 1 100 |
а5 = 2 080 |
|
спрос (цистерны) |
bl = 9 798 |
b2 = 11 002 |
Рассчитаем для данной матрицы общую «стоимость» транспортной работы. сначал = 987×4714
+ +1359×6271 + 1488×871 + 1860×0 + 1792×1943 + 2164×3147 + 1890×1290 + 2262×484 + 2089×980
+ +1990×1100 = 4 652718 + 8 522 289 + 1 296 048 + 0 + 3 481 856 + 6 810 108 + 2 438 100 +
1 094 808 + +2 038 400 + 2 189 000 = 32 523 327 вагоно-км.
Методика вычисления потенциалов матрицы транспортной задачи и на ее основе построение оптимальной матрицы распределения ресурсов довольно достаточно освещена в специальной литературе по исследованию операций (например, [3 – 5]).
На основе принятой методики симплексного метода на каждом этапе итерации (их всего 2) произведен расчет на оптимальность потенциалов исходной матрицы и определена оптимальная матрица распределения объемов перевозки серной кислоты для рассматриваемого примера. Результаты расчета сведены в новую (оптимальную) матрицу распределения объемов перевозки серной кислоты по филиалам (табл. 2).
Для данной матрицы также рассчитана общая «стоимость» транспортной работы. Такая работа составит: сопт = 987×8927 + 1359×2058 + 1488×871 + 1860×0 + 1792×0 + 2164×5090 +
1890×0 + 2262×1774 + 2089×0 + 1990×2080 = 8 810 949 + 2 796 822 + 1 296 048 + 0 + 0 + 11 014 760
+ 0 + 4 012 788 + 0 + 4 139 200 = 32 070 567 вагоно-км.
Таблица 2. Оптимальная матрица распределения объемов перевозки серной кислоты
|
Потребитель 1 |
Потребитель 2 |
поставка (цистерны) |
|
Поставщик 1 |
987 8 927 |
1359 2 058 |
al = 10 985 |
|
Поставщик 2 |
1488 871 |
1860 0 |
а2 = 871 |
|
Поставщик 3 |
1792 0 |
2164 5 090 |
а3 = 5 090 |
|
Поставщик 4 |
1890 0 |
2262 1 774 |
а4 = 1 774 |
|
Поставщик 5 |
2089 0 |
1990 2 080 |
а5 = 2 080 |
|
спрос (цистерны) |
bl = 9 798 |
b2 = 11 002 |
Снижение общей «стоимости» транспортной работы составляет:
с сначал сопт = 32 523 327 – 32 070 567 = 452 760 вагоно-км.
Таким образом, после применения симплексного метода решения транспортной задачи определена матрица оптимального распределения объемов поставок серной кислоты от производителей по филиалам (табл. 2).
На основе данной матрицы получена оптимальная сеть распределения перевозки серной кислоты (рис. 2).
Рис. 2. Оптимальная сеть транспортной задачи
Таким образом:
Во-первых, получено четкое перераспределение поставок серной кислоты между отечественными и экспортными производителями. Такое перераспределение также дает огромную экономию управленческих затрат.
Во-вторых, при среднем тарифном расстоянии транспортировки серной кислоты на данных
7-ми маршрутах только отечественных производителей
lср = 1 706 км ((987 + 1359 + 1488 + 1792
+ +2164 + 1890 + 2262)/7 = 1 706) и при среднем обороте цистерн ср = (17,1 + 17,1 + 19,2 + 19,2 + 13,4 + 14,9 + 18,6)/7 = 17 суток (см. п. 6.1 данного НИР), из оборота высвобождается примерно +452 760×17/1 706×365 = 13 кислотных цистерн.
При средней цене на 1 кислотную цистерну 6,87 млн. тенге ($ 46 400), это составит единовременную экономию перевозчикам в размере 89,31 млн. тенге.
В-третьих, получена экономия 452 760 вагоно-км транспортной работы, которую можно определить по тарифным ставкам. По предварительным расчетам при средней себестоимости 1 вагоно-км 85 тенге (с учетом цен АО «НК «КТЖ» за выход на МЖС, предоставление тяги, маневровую работу и т.д.) такая экономия составит около 38,5 млн. тенге в год.
ЛИТЕРАТУРА
- Канторович Л.В. Экономический расчет наилучшего использования ресурсов. - М.: Изд. АН СССР, 1959. – 564 с.
- Гавурин М.К., Малоземов В.Н. Экстремальные задачи с линейными ограничениями. - Л.: 1984. 176с.
- Математическое моделирование экономических процессов на железнодорожном транспорте /А.Б. Каплан, А.Д. Майданов, А.М. Макарочкин, Р.М. Царев. – М.: Транспорт, 1984. – 256 с.
- Вагнер Г. Основы исследования операций. Т.1 – М.: Мир, 1972. – 335 с.
- Давыдов Э. Г. Исследование операций. - М.: Наука, 1980.- 348 с.