Везде
On the Transportation Problem with Ecological Criterion
Table of contents
Annotation Estimate Publication content
References Comments
Share
QR
Metrics
On the Transportation Problem with Ecological Criterion
Annotation
PII
S042473880003951-5-1
DOI
10.31857/S042473880003951-5
Publication type
Article
Status
Published
Authors
V. Assaul 
Affiliation: Naval Polytechnic Institute
Address: St. Petersburg, Russian Federation
I. Pogodin
Affiliation: Naval Polytechnic Institute
Address: Russian Federation, St. Petersburg
Edition
Volume 55 issue 2
Pages
58-64
Abstract

Three ways of solving the transport problem are considered, in which, in addition to the transportation fee of each unit of cargo, a fixed fee for the use of a particular route by each carrier is additionally charged regardless of the amount of cargo carried on it. (1) With the help of a detailed logical analysis of a payment matrix with a decision tree construction that takes into account corrective cycles, at the same time, deliveries to all unfilled cells are considered, and those which lead to the objective function decreasing are selected. (2) With the choice of the best plan from the set of iterative variants, in each the costs of transport along the used routes (cells) are replaced by actual ones. That means it is recalculated taking into account the additions to the initial costs of transportation the “penal additives”, reduced to a unit of cargo transported along the corresponding route at the previous iteration. (3) With the approximate reduction of two-component costs to the effective continuous values of unit transportation costs, that simulates the stepwise contribution of additional payments, and the further reduction of the problem to the search of extremum to a function of several variables. Estimates are made of the conditions under which the task necessarily requires accounting for additional payments on the routes. Since the very formulation of the problem did not have a single term for it, taking into account current conditions, the term “transport problem with ecological criterion” was proposed.

Keywords
objective function, transportation cost, optimal plan, corrective cycle.
Received
18.03.2019
Date of publication
05.06.2019
Number of purchasers
93
Views
1624
Readers community rating
0.0 (0 votes)
Cite   Download pdf
1 В математическом моделировании и оптимизации актуальных экономических задач широко известна транспортная задача (проблема Монжа—Канторовича (Канторович, 1942), восходящая к 1791 г.), в которой требуется найти такой план перевозок однотипных грузов от n производителей к m потребителям, чтобы минимальными оказались суммарная стоимость материальных затрат (критерий стоимости) либо необходимое время на осуществление всех перевозок (критерий времени).
2 В настоящее время, когда все больше внимания уделяется проблемам защиты окружающей среды, актуальным становится введение экологического критерия, направленного на минимизацию ущерба от необходимых транспортных перевозок. Желательно, чтобы это учитывалось еще на этапе планирования. Например, следовало бы учесть ущерб от выхлопов и шума от транспорта на современных автомагистралях типа КАД (кольцевая автодорога) в совокупности с потерей изъятой из оборота весьма обширной территории, включая прилегающую к трассе. Или при планировании перевозок по сети платных магистралей, где взимается плата за проезд по конкретному участку дороги, в частности в автотранспортной платежной системе «Платон».
3 Впрочем, в абстрактной общей форме без формулировки возможных приложений подобная задача рассматривалась c 1960-х годов под различными названиями: неоднородная транспортная, транспортная с фиксированными доплатами (Туй, 1964; Поляк, 1964; Корбут, 1969). В то время при низком уровне электронно-вычислительной базы она решалась преимущественно приближенными методами. Так, работа (Корбут, 1969, глава 16, § 1) до сих пор используется в Интернете в качестве квалифицированного современного обзора (см. например (Сигал, Иванова, 2007)).
4 К примеру, в работе (Поляк, 1964) предложены основы весьма трудоемкого, однако логичного и точного, несмотря на техническую ошибку в тексте, метода решения задачи, учитывающего ее специфику, но дающего лишь локальный экстремум целевого функции. Позже в Центральном экономико-математическом институте (ЦЭМИ) был разработан мощный метод узловых векторов (Седова, Лебедев, 1999), который может применяться в том числе и к рассматриваемому классу задач (Седова, Лебедев, 2001). Рассмотрим эту задачу в следующей постановке. Заданы мощности производителей однотипных грузов {Ai, i=1,…, n} и емкости их потребителей {Bj, j=1,…, m}. Перевоз единицы грузов по трассе: i→j оценивается величиной cij и факт использования конкретной трассы в любом объеме (xij >0) отражается в том числе штрафом (включающим экологический ущерб) в виде фиксированной доплаты dij на одного перевозчика.  Стоимость перевозки xij единиц груза рассчитывается по формуле
5 , (1)
6 где ɛ(x) — функция Хевисайда: при при .
7 Таким образом, из-за скачкообразных включений фиксированных доплат проблема выходит из разряда классических задач линейного программирования. Задача теряет удобное свойство линейности, поскольку приобретает своеобразное дополнительное свойство дискретности по использованию тарифов dij (полуцелочисленность по булевым переменным), строго говоря, исключающее применение операций дифференцирования.
8 Как показали численные расчеты, если оценка средней дополнительной добавки к тарифу перевозок 
9

10 составляет не более 0,2—0,3 от оценки средневзвешенного основного тарифа
11

12 то оптимальный план перевозок можно получить из решения стандартной транспортной задачи с тарифами , не учитывая доплат . Пренебречь основными тарифами нельзя, даже если Mc ≈ 0,1Md. Поэтому для общего случая соотношений между Mc и Md  предлагаются несколько путей поиска оптимального плана перевозок {xij, i=1,…, n; j=1,…, m}.
13 Остановимся подробнее на трех вариантах поиска оптимального плана рассматриваемой задачи.
14 I. В качестве начального приближения к оптимальному плану используем один из базисных планов задачи, например оптимальный план задачи без доплат {dij=0}. Дальнейшее улучшение плана будем строить распределительным методом (Бирман, 1968; Фролькис, 2002).
15 Известно, что из любой незаполненной клетки базисного плана транспортной таблицы можно построить циклическую перевозку, и притом единственным образом. В (Поляк, 1964) отмечено, что число заполненных клеток в оптимальном плане не может превышать числа заполненных клеток базисного плана в начальном приближении, и предлагается последовательно строить циклы, освобождающие клетки с наибольшими значениями dij с соответствующим пересчетом потенциалов.
16 В общем случае возможно различное соотношение слагаемых тарифа, поэтому представляется более эффективной поочередная проверка всех незаполненных клеток и порождаемых ими циклических перевозок. Некоторые из них могут приводить к уменьшению транспортной работы. Любую из таких перевозок, например дающую наибольшее уменьшение целевой функции, можно выбрать в качестве следующего приближения, и так далее.
17 После некоторого шага окажется, что незаполненных клеток, позволяющих построить план с меньшей транспортной работой, больше нет. Это означает, что построен оптимальный план задачи в классе базисных решений. Чтобы убедиться в том, что это искомое решение, следует отдельно рассмотреть класс небазисных решений. Это решения с числом заполненных клеток, меньшим, чем (n+m–1). Очевидно, что в ряде случаев уменьшение числа заполненных клеток может компенсировать удорожание стоимости перевозок, пропорциональной объему перевозимого груза. В небазисном плане не во все пустые клетки можно назначить перевозку, и процедура поиска оптимального плана ускоряется. Сравнивая значения целевой функции оптимальных базисного и небазисного планов, выбираем наиболее дешевый.
18 Следует учитывать, что улучшения плана можно добиться не только назначением перевозки в одну из пустых клеток. Если в двух клетках одинаковые поставки, можно заполнить сразу 2 клетки, образующие цикл с данными, при этом две исходные клетки освобождаются.
19 Покажем на примере реализацию предложенного алгоритма. Рассмотрим транспортную задачу с экологическим критерием, или, другими словами, задачу с фиксированными доплатами. В табл. 1 приведена закрытая транспортная задача размерности 4×4. В левом столбце таблицы показаны мощности {Ai} (запасы товара), в верхней строке — емкости {Bi} (потребности), в левых верхних углах каждой клетки приведены значения {сij}, в правых верхних углах — значения {dij} в соответствии с формулой (1). По центру клеток указаны элементы оптимального плана задачи без учета дополнительных затрат.
20 В табл. 1 звездочкой помечена ячейка, позволяющая уменьшить значение целевой функции на 40 единиц путем назначения в нее новой перевозки Ɵ=5. На рисунке показан этот план перевозки (П1) без дублирования первого столбца, первой строки и тарифов, а также улучшенный на 40 единиц (план П2), в котором невозможно дальнейшее уменьшение стоимости перевозки распределительным методом, и он является оптимальным.
21 На этом рисунке приведен один из базисных планов (П3) и последующие планы, получающиеся назначением новых перевозок в одну из допустимых клеток транспортной таблицы. Так, использование клетки плана П3, помеченной звездочкой, приводит к плану П1 и удешевлению перевозки на 30 единиц, а двух клеток, помеченных здесь двумя звездочками, к плану П4 с уменьшением стоимости на 5 единиц. В плане П4 также возможно уменьшение целевой функции путем назначения новых перевозок в клетки, помеченные одной, двумя и тремя звездочками. Так возникают новые планы П5, П6, П7. Для каждого из них стрелкой указан переход к плану с меньшей стоимостью, клетки для назначения перевозки и уменьшение стоимости.
22 Таблица 1
23
Ai\Bj B1=28 B2=20 B3=12 B4=20
A1=15 9 120 15 24 20 16 50 18 40
A2=22 17 40 8 120 20 19 30 2 14 60
A3=25 15 60 5 12 80 21 20 * 13 70 20
A4=18 11 90 8 15 60 17 40 10 10 100
24 Как видно из схемы на рисунке, во всех случаях за разное количество шагов получен один и тот же план П2, являющийся оптимальным среди базисных планов рассматриваемой задачи. В табл. 2 приведен один из вырожденных планов задачи и следующий план, улучшенный на 158 ед. Дальнейшее улучшение плана невозможно, и окончательное значение целевой функции больше, чем в плане П2.
25 Таблица 2
26
15 П9
2 20
13 12
18
27
15 П10
20 2
13 12
18
28 В отличие от метода ветвей и границ в этом методе не происходит разделения множества всех маршрутов на непересекающиеся группы, в каждой из которых возможен локальный минимум. Из приведенного примера видно, что на каждом этапе выбор варианта с любым другим уменьшением стоимости перевозки приводит к тому же оптимальному решению. Если предположить, что кроме найденного оптимального решения существует другой план с меньшей стоимостью перевозок и включающий другие ячейки таблицы, то, назначая перевозки в различные ячейки этого плана, можно построить промежуточные планы с промежуточными затратами и транзитный переход от одного плана к другому распределительным методом. Впрочем, эти соображения не являются строгим доказательством, которое еще предстоит сделать.
29 II. На первом этапе классическими методами (например, методом потенциалов, в том числе с помощью любой компьютерной программы) строится оптимальный план перевозок {xij}, т.е. по критерию стоимости, предварительно увеличив исходные цены {cij} на оценки возможных минимальных добавок за счет штрафов  примерно так, как это предусмотрено в методе Балинского (Balinski, 1961).
30 На следующих повторяющихся этапах в занятых клетках {xij >0}, попавших в очередной оптимальный план перевозок, эти добавки следует заменить на более точные значения и повторить построение оптимального плана. Если в нескольких (по крайней мере, в двух) последовательных планах устойчиво появляются одни и те же клетки, занятые одними и теми же значениями (), в сумме по линии составляющими величины Piо и Qjо, строго меньшие соответствующих мощностей Aiо  или емкостей Bjо, то оценки минимальных штрафных добавок к исходным ценам cij делаются по формуле   т.е. уменьшив мощности Aiо или емкости Bjо на величины тех перевозок, которые уже претендуют на включение в истинно оптимальный план.
31 На каждом шаге итерации построение плана первоначально использует оценки эффективных тарифов (в основном заниженные), а на следующем шаге эффективные тарифы могут измениться только в тех клетках, которые вошли в план, выбранный на предыдущем шаге, а в остальных незадействованных клетках тарифы остаются нескорректированными. Это обстоятельство мешает сходимости решения и не дает общего рецепта для остановки процедуры поиска оптимального плана.
32 Таким образом, данный процесс не является упорядоченным алгоритмом, а представляет собой некоторую аналогию с вариационным или с квазислучайным поиском. На практике он позволяет лишь сократить число рассматриваемых вариантов (итераций) по сравнению с прямым перебором всех возможных планов. В качестве оптимального плана выбирается тот, на котором в серии нескольких (от 3 до 10 в зависимости от размеров задачи) попыток достигается минимальное значение целевой функции
33

34 Такой пример приведен в табл. 3, где полужирным шрифтом выделены входные параметры, курсивом — результаты расчетов для четырех итераций и суммарные расходы (столбец F). Можно заметить, что планы и значения F, полученные в итерациях 1 и 4, совпадают: на представленной последовательности итераций 1—4  F =3740 минимально в итерации 2, соответствующий план принимаем в качестве оптимального.
35 Таблица 3
Ai\Bj № итерации В1=50 В2=40 В3=60 F
cij xij dij cij xij dij cij xij dij
А1=80 14 400 19 250 10 600
1 22 20 25,25 20 60 3950
2 34 25,25 20 20 60 3740
3 34 31,5 40 20 3810
4 22 20 25,25 25 60 3950
А2=70 10 700 18 350 20 200
1 24 30 26,75 40 23,33 3950
2 33,33 50 26,75 20 23,33 3740
3 24 50 35,5 23,33 60 3810
4 24 30 26,75 40 30 3950
36 Что касается попыток исследования зависимости продолжительности этой процедуры от размеров задачи (таблицы), то в связи с отсутствием общей монотонной сходимости метода можно лишь констатировать, что, например, при сохранении общего объема перевозок от исходной таблицы 2×3 (4 шага) к таблице 3×3 потребовалось 4 шага, к таблице 2×4 — 3 шага, таблице 3×5 — 2 шага (см. табл. 3). Табл. 1, рассмотренная методом I, приводится к оптимальному результату за 4 шага, а останавливается за 7 шагов.
37 Таким образом, регулярной детерминированной связи между продолжительностью этой процедуры и размерами задачи не наблюдается. Метод II можно считать эмпирическим, так как его теория не выходит за рамки асимптотических приближений.
38 III. Для решения задачи введем переменные эффективных тарифов, нелинейным образом зависящие от выбора объемов перевозок сij по конкретным трассам, например вида где K — большой параметр (например, K ≈100÷1000). В этом случае задача формально относится уже к разделу нелинейного программирования. Традиционный путь решения таких задач с помощью уравнений Куна—Таккера здесь менее перспективен из-за большого числа уравнений и совместнонеопределенного характера соответствующей системы уравнений. Однако задача может решаться численным поиском условного экстремума функции многих переменных средствами современных математических пакетов, например в Mathcad-15 при не слишком большом числе неизвестных (n–1)(m–1), например Minimize.
39 Построив из линейных ограничений на мощности и емкости систему из n+m–1 линейно независимых (задача замкнутая) алгебраических уравнений для всех nm неизвестных {xij}, получаем (n–1)(m–1) свободных переменных {, экстремум по которым для нелинейной целевой функции вида
40

41 требуется найти при ограничениях по диапазонам изменения этих свободных переменных: . Здесь k — порядковые номера свободных неизвестных. Для задачи, заданной матрицей табл. 2, при K=100 получим основу того же (итерация 2) оптимального плана: =20, 0.
42 Можно воспользоваться более наглядными классическими методами поиска экстремума, включающими построение матрицы Гессе и использование правила Сильвестра. Поэтому сначала численно находим координаты всех подозрительных на экстремум точек из решения системы (n–1)(m–1) нелинейных уравнений для обнуления первых производных от целевой функции F по оставленным свободными переменным вида
43 (2)
44 Здесь в сумму включены свободные переменные и связанные, выраженные через свободные, что отражается соответствующим коэффициентом.
45 В решении могут получаться не соответствующие практической стороне задачи нецелочисленные значения, которые можно округлять, по крайней мере до целых, не опасаясь существенного нарушения плана, поскольку ограничения задачи содержат единичные коэффициенты при неизвестных, т.е. не дают наклонов соответствующих геометрических образов (прямых, плоскостей, гиперплоскостей), близких к 0 или к π/2.
46 Можно несколько изменить эту задачу, назначая повышение тарифов на dij удельных перевозок сij только в тех клетках, для которых перевозки превышают некоторый условный лимит xij ≥С0. Тогда откорректированные тарифы примут вид, заданный выражением (2).
47 Метод III основан на теории поиска условного экстремума и на том, что цены, пропорциональные функции Хевисайда, аппроксимируются непрерывными функциями. Постоянные цены в клетках заменяются на аппроксимирующие ступеньку функции, с помощью которых строится исследуемая на экстремум целевая функция.
48 Фактически ограничения на размерности задачи в предложенных методах определяются:
49 – в методе I — обозримостью матрицы (условно 10×10) для возможности логического анализа ситуации при ручном решении, и практически отсутствуют при использовании компьютерного алгоритма; – в методе II — чисто техническими факторами (включая обозримость в случае ручной реализации), поскольку требуется просто отобрать вариант с минимумом пробной целевой функции по группе итераций; – в методе III — возможностями процедуры поиска условного экстремума в используемом математическом пакете либо в специально созданной для этой цели программы. Практически этот путь ограничен условно размерностью 5×5 (большее потребует искусного алгоритма поиска экстремума).
50
15 5 15 * ** 10 10 * 5 40 10 5
15 7 15 7 20 2 20 2
* 5 ** 20 5 20 10 15 5 20
13 ** 5 П3 13 5 *** П4 18 ** П6 18 * П7
30 50 65 55 15
15 10 5
20 2 20 2
5 * 20 5 20
8 10 П1 18 * П5
40 15
15
20 2
5 20
13 5 П2
Рисунок. Дерево поиска оптимального базисного плана
см.

см.

см.

см.

см.

см.

см.

см.

см.

см.

см.

см.

References

1. Birman I.Ya. "Optimal programming", 1968, M. "Economics" 231p.

2. Kantorovich L.V. On the movement of masses. Reports of the USSR Academy of Scienc-es,1942,v.37,p.227-229

3. Korbut A.A., Finkelstein Yu. Yu. "Discrete programming", 1969, M. "Nauka", 368p

4. Polyak R.A. On one inhomogeneous transport problem - In Sat. Mathematical models and methods of optimal planning. Novosibirsk, "Nauka", 1966, p.109-115

5. Sedova S.V., Lebedev S.S. The decision of one task of placement with use of nodal vectors of the resolving multipliers. – Economy and mathematical methods, 1999, t.35, No. 3, p.116-121

6. Sedova S.V., Lebedev S.S. Method of nodal vectors of integer programming. 2 Problems of a special look: ÑEMI pre-print. WP/2000/094, 2001, 88p..

7. Sigal I.Kh., Ivanova A.P. Introduction to applied and discrete programming: models and com-putational algorithms. M. "Fizmatlit", 2007, p.45-49

8. Frolkis V.A. Introduction to the theory and optimization methods for economists, St.Petersburg,“Peter”,2002,320ð.

9. Hoang Tui. Concave programming with linear constraints. Reports of the Academy of Sciences of the USSR, 1964, vol.159, ¹1, p.32-35

10. Electronic resource, >, (access is free), Approximate methods for a transport problem with fixed surcharges. Russ. 02/20/2017

11. Balinski M. L. Fixed cost transportation problem. Naval Res. Log. Quart. 1961, 8 ¹1, p.41-54

Comments

No posts found

Write a review
Translate