On the Transportation Problem with Ecological Criterion

 
PIIS042473880003951-5-1
DOI10.31857/S042473880003951-5
Publication type Article
Status Published
Authors
Affiliation: Naval Polytechnic Institute
Address: St. Petersburg, Russian Federation
Affiliation: Naval Polytechnic Institute
Address: Russian Federation, St. Petersburg
Journal nameEkonomika i matematicheskie metody
EditionVolume 55 Issue 2
Pages58-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.

Keywordsobjective function, transportation cost, optimal plan, corrective cycle.
Received25.05.2019
Publication date25.05.2019
Number of characters17885
Cite   Download pdf To download PDF you should sign in
1 В математическом моделировании и оптимизации актуальных экономических задач широко известна транспортная задача (проблема Монжа—Канторовича (Канторович, 1942), восходящая к 1791 г.), в которой требуется найти такой план перевозок однотипных грузов от n производителей к m потребителям, чтобы минимальными оказались суммарная стоимость материальных затрат (критерий стоимости) либо необходимое время на осуществление всех перевозок (критерий времени).
2 В настоящее время, когда все больше внимания уделяется проблемам защиты окружающей среды, актуальным становится введение экологического критерия, направленного на минимизацию ущерба от необходимых транспортных перевозок. Желательно, чтобы это учитывалось еще на этапе планирования. Например, следовало бы учесть ущерб от выхлопов и шума от транспорта на современных автомагистралях типа КАД (кольцевая автодорога) в совокупности с потерей изъятой из оборота весьма обширной территории, включая прилегающую к трассе. Или при планировании перевозок по сети платных магистралей, где взимается плата за проезд по конкретному участку дороги, в частности в автотранспортной платежной системе «Платон».
3 Впрочем, в абстрактной общей форме без формулировки возможных приложений подобная задача рассматривалась c 1960-х годов под различными названиями: неоднородная транспортная, транспортная с фиксированными доплатами (Туй, 1964; Поляк, 1964; Корбут, 1969). В то время при низком уровне электронно-вычислительной базы она решалась преимущественно приближенными методами. Так, работа (Корбут, 1969, глава 16, § 1) до сих пор используется в Интернете в качестве квалифицированного современного обзора (см. например (Сигал, Иванова, 2007)).
4 К примеру, в работе (Поляк, 1964) предложены основы весьма трудоемкого, однако логичного и точного, несмотря на техническую ошибку в тексте, метода решения задачи, учитывающего ее специфику, но дающего лишь локальный экстремум целевого функции. Позже в Центральном экономико-математическом институте (ЦЭМИ) был разработан мощный метод узловых векторов (Седова, Лебедев, 1999), который может применяться в том числе и к рассматриваемому классу задач (Седова, Лебедев, 2001). Рассмотрим эту задачу в следующей постановке. Заданы мощности производителей однотипных грузов {Aii=1,…, n} и емкости их потребителей {Bj, j=1,…, m}. Перевоз единицы грузов по трассе: i→j оценивается величиной cij и факт использования конкретной трассы в любом объеме (xij >0) отражается в том числе штрафом (включающим экологический ущерб) в виде фиксированной доплаты dij на одного перевозчика.  Стоимость перевозки xij единиц груза рассчитывается по формуле
5 , (1)
6 где ɛ(x) — функция Хевисайда: при при .
7 Таким образом, из-за скачкообразных включений фиксированных доплат проблема выходит из разряда классических задач линейного программирования. Задача теряет удобное свойство линейности, поскольку приобретает своеобразное дополнительное свойство дискретности по использованию тарифов dij (полуцелочисленность по булевым переменным), строго говоря, исключающее применение операций дифференцирования.

Price publication: 0

Number of purchasers: 2, views: 1474

Readers community rating: votes 0

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

Система Orphus

Loading...
Up