О транспортной задаче с экологическим критерием

Рассматривается решение транспортной задачи, в которой, помимо платы за провоз каждой единицы груза, с перевозчика дополнительно взимается фиксированная плата за использование трассы вне зависимости от количества перевозимого по ней груза. Приведены три решения этой задачи: 1) детальный логический анализ матрицы платежей с построением дерева, учитывающего корректирующие циклы; при этом рассматриваются поставки во все незаполненные клетки и отбираются приводящие к уменьшению целевой функции; 2) выбор наилучшего плана из совокупности итерационных вариантов, в каждом из которых стоимости перевозок по используемым трассам (клеткам) заменяются фактическими, т.е. пересчитанными с учетом добавок к исходным стоимостям перевозок дополнительных штрафных добавок, приведенных к единице груза, перевозимого по соответствующей трассе на предыдущей итерации; 3) приближенное сведение двухкомпонентных стоимостей к эффективным непрерывным величинам удельных стоимостей перевозок, которые моделируют скачкообразный вклад дополнительных доплат, и дальнейшим сведением задачи к поиску экстремума целевой функции как функции нескольких переменных. Делаются оценки условий, при которых задача с необходимостью требует учета дополнительных платежей по трассам. Поскольку такая постановка задачи не имела единого термина, то с учетом современных условий авторы предложили назвать ее «транспортной задачей с экологическим критерием».

Ключевые слова

целевая функция, стоимость перевозки, оптимальный план, корректирующий цикл.

Получено

25.05.2019

Дата публикации

25.05.2019

Кол-во символов

17885

Цитировать Скачать pdf Для скачивания PDF необходимо авторизоваться

ГОСТ	Ассаул В. , Погодин И. Е. О транспортной задаче с экологическим критерием // Экономика и математические методы – 2019. – Tом 55. – Номер 2 C. 58-64 [Электронный ресурс]. URL: https://emm.jes.su/S042473880003951-5-1 (дата обращения: 28.04.2024). DOI: 10.31857/S042473880003951-5
MLA	Assaul, V., Pogodin, I. "On the Transportation Problem with Ecological Criterion." Ekonomika i matematicheskie metody 55.2 (2019):58-64. DOI: 10.31857/S042473880003951-5
APA	Assaul V., Pogodin I. (2019). On the Transportation Problem with Ecological Criterion. Ekonomika i matematicheskie metody 55(2), pp.58-64 DOI: 10.31857/S042473880003951-5


1	В математическом моделировании и оптимизации актуальных экономических задач широко известна транспортная задача (проблема Монжа—Канторовича (Канторович, 1942), восходящая к 1791 г.), в которой требуется найти такой план перевозок однотипных грузов от n производителей к m потребителям, чтобы минимальными оказались суммарная стоимость материальных затрат (критерий стоимости) либо необходимое время на осуществление всех перевозок (критерий времени).
2	В настоящее время, когда все больше внимания уделяется проблемам защиты окружающей среды, актуальным становится введение экологического критерия, направленного на минимизацию ущерба от необходимых транспортных перевозок. Желательно, чтобы это учитывалось еще на этапе планирования. Например, следовало бы учесть ущерб от выхлопов и шума от транспорта на современных автомагистралях типа КАД (кольцевая автодорога) в совокупности с потерей изъятой из оборота весьма обширной территории, включая прилегающую к трассе. Или при планировании перевозок по сети платных магистралей, где взимается плата за проезд по конкретному участку дороги, в частности в автотранспортной платежной системе «Платон».
3	Впрочем, в абстрактной общей форме без формулировки возможных приложений подобная задача рассматривалась c 1960-х годов под различными названиями: неоднородная транспортная, транспортная с фиксированными доплатами (Туй, 1964; Поляк, 1964; Корбут, 1969). В то время при низком уровне электронно-вычислительной базы она решалась преимущественно приближенными методами. Так, работа (Корбут, 1969, глава 16, § 1) до сих пор используется в Интернете в качестве квалифицированного современного обзора (см. например (Сигал, Иванова, 2007)).
4	К примеру, в работе (Поляк, 1964) предложены основы весьма трудоемкого, однако логичного и точного, несмотря на техническую ошибку в тексте, метода решения задачи, учитывающего ее специфику, но дающего лишь локальный экстремум целевого функции. Позже в Центральном экономико-математическом институте (ЦЭМИ) был разработан мощный метод узловых векторов (Седова, Лебедев, 1999), который может применяться в том числе и к рассматриваемому классу задач (Седова, Лебедев, 2001). Рассмотрим эту задачу в следующей постановке. Заданы мощности производителей однотипных грузов {A_i, i=1,…, n} и емкости их потребителей {B_j, j=1,…, m}. Перевоз единицы грузов по трассе: i→j оценивается величиной c_ij и факт использования конкретной трассы в любом объеме (x_ij >0) отражается в том числе штрафом (включающим экологический ущерб) в виде фиксированной доплаты d_ijна одного перевозчика. Стоимость перевозки x_ijединиц груза рассчитывается по формуле
5	, (1)
6	где ɛ(x) — функция Хевисайда: при при .
7	Таким образом, из-за скачкообразных включений фиксированных доплат проблема выходит из разряда классических задач линейного программирования. Задача теряет удобное свойство линейности, поскольку приобретает своеобразное дополнительное свойство дискретности по использованию тарифов d_ij(полуцелочисленность по булевым переменным), строго говоря, исключающее применение операций дифференцирования.

Цена публикации: 0

Всего подписок: 2, всего просмотров: 1495

Оценка читателей: голосов 0

1. Бирман И.Я. «Оптимальное программирование», 1968, М. «Экономика» 231с.

2. Канторович Л.В. О перемещении масс. Доклады Академии наук СССР, 1942, т.37, с.227-229

3. Корбут А. А., Финкельштейн Ю. Ю. «Дискретное программирование»,1969, М. «Наука», 368с.

4. Поляк Р.А. Об одной неоднородной транспортной задаче - В Сб. Математические модели и методы оптимального планирования. Новосибирск, «Наука», 1966, с.109-115

5. Седова С.В., Лебедев С.С. Решение одной задачи размещения с использованием узловых векторов разрешающих множителей. – Экономика и математические методы, 1999, т.35, № 3, с.116-121

6. Седова С.В., Лебедев С.С. Метод узловых векторов целочисленного программирования. 2. Задачи специального вида: препринт ЦЭМИ. WP/2000/094, 2001, 88с.

7. Сигал И.Х., Иванова А.П. Введение в прикладное и дискретное программирование: модели и вычислительные алгоритмы. М. «Физматлит», 2007, с.45-49

8. Фролькис В.А. Введение в теорию и методы оптимизации для экономистов. СПб: «Пи-тер», 2002.-320с.

9. Хоанг Туй. Вогнутое программирование при линейных ограничениях. Доклады Академии наук СССР, 1964, т.159, №1, с.32-35

10. Электронный ресурс, >, (доступ свободный), При-ближенные методы для транспортной задачи с фиксированными доплатами. Яз. Рус.20.12.2017

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