On a discrete max-plus transportation problem

В статье предоставлен явный алгоритм для решения идемпотентного аналога дискретной задачи Монжа–Канторовича об оптимальном переносе массы с заменой обычного поля вещественных чисел тропическим (макс-плюс) полукольцом, в котором сложение определяется как максимум, а произведение определяется как обычное сложение, причем $-\infty$ и $0$ играют роли, соотвественно, аддитивного и мультипликативного нейтральных элементов. Такую задачу естественно назвать тропической или “макс-плюс” оптимальной транспортной задачей. Мы показываем, что решения последней, называемые оптимальными тропическими планами, могут не соответствовать паросочетаниям, даже если данные (макс-плюс вероятностные меры) имеют все веса, равные нулю, в отличие от классической дискретной задачи оптимального переноса массы, в которой в аналогичной ситуации соответствующие паросочетаниям оптимальные планы существуют всегда. Тем не менее, в некоторой рандомизированной ситуации существование оптимальных тропических планов, соответствующих паросочетаниям, может встречаться достаточно часто. Наконец, мы доказываем, что единственность решений оптимальной тропической транспортной задачи встречается достаточно редко. Библ. – 6 назв.