"Записки научных семинаров ПОМИ"
Том 536, стр. 54-78
О дискретной идемпотентной (макс-плюс) версии задачи переноса массы
П. Барриос, С. Майорга, Е. Степанов
Universidad de Antioquia,
Medell\'{\i}n, Colombia
pdrlsbrrs@gmail.com
Innopolis University,
Innopolis, Russia
me@mayorga.ru
St.Petersburg Department
of the Steklov Mathematical Institute
of the Russian Academy of Sciences,
St.Petersburg, Russia;
Dipartimento di Matematica,
Universit\`a di Pisa,
Pisa, Italy;
HSE University, Moscow, Russian Federation
stepanov.eugene@gmail.com
- Аннотация:
В статье предоставлен явный алгоритм для решения
идемпотентного аналога дискретной задачи
Монжа--Канторовича об оптимальном переносе массы
с заменой обычного поля вещественных чисел
тропическим (макс-плюс) полукольцом,
в котором сложение определяется как максимум, а
произведение определяется как обычное сложение, причем
$-\infty$ и $0$ играют роли, соотвественно,
аддитивного и мультипликативного нейтральных элементов.
Такую задачу естественно назвать тропической
или ``макс-плюс'' оптимальной транспортной задачей.
Мы показываем, что решения последней,
называемые оптимальными тропическими планами, могут не соответствовать
паросочетаниям, даже если данные (макс-плюс вероятностные меры)
имеют все веса, равные нулю,
в отличие от классической дискретной задачи оптимального переноса массы,
в которой в аналогичной ситуации соответствующие паросочетаниям
оптимальные планы существуют всегда.
Тем не менее, в некоторой рандомизированной ситуации
существование
оптимальных тропических планов, соответствующих паросочетаниям,
может встречаться достаточно часто.
Наконец, мы доказываем, что единственность решений оптимальной
тропической транспортной задачи встречается достаточно редко.
Библ. -- 6 назв.
- Ключевые слова: оптимальный перенос массы, тропическое полукольцо, идемпотентный анализ
[optimal transportation, tropical semiring, idempotent analysis]
Полный текст(.pdf)