Везде
О транспортной задаче с экологическим критерием
Оглавление
Аннотация Оценить Содержание публикации
Библиография Комментарии
Поделиться
QR
Метрика
О транспортной задаче с экологическим критерием
Аннотация
Код статьи
S042473880003951-5-1
DOI
10.31857/S042473880003951-5
Тип публикации
Статья
Статус публикации
Опубликовано
Авторы
Ассаул В. Николаевич 
Аффилиация: ВМПИ ВУНЦ ВМФ ВМА
Адрес: Российская Федерация, Санкт-Петербург
Погодин И. Е.
Аффилиация: ВМПИ ВУНЦ ВМФ ВМА
Адрес: Российская Федерация, Санкт-Петербург
Выпуск
Том 55 Номер 2
Страницы
58-64
Аннотация

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

Ключевые слова
целевая функция, стоимость перевозки, оптимальный план, корректирующий цикл.
Классификатор
Получено
18.03.2019
Дата публикации
05.06.2019
Всего подписок
93
Всего просмотров
1625
Оценка читателей
0.0 (0 голосов)
Цитировать Скачать pdf
Доступ к дополнительным сервисам
Дополнительные сервисы только на эту статью
Преимущества сервисов
100 руб. / 1.0 SU
Дополнительные сервисы на весь выпуск”
Преимущества сервисов
720 руб. / 15.0 SU
Дополнительные сервисы на все выпуски за 2019 год
Преимущества сервисов
2534 руб. / 30.0 SU
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
Рисунок. Дерево поиска оптимального базисного плана
см.

см.

см.

см.

см.

см.

см.

см.

см.

см.

см.

см.

Библиография

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

Комментарии

Сообщения не найдены

Написать отзыв
Перевести