1.3 Решение тропической системы линейных уравнений

Тропическая система из n уравнений по m переменных задается матрицей размера , состоящая из коэффициентов при соответствующих переменных.

Пользуясь определением корня, которое было дано в разделе 1.2, сформулируем определение её решения.

Тропическая система имеет решение, если , где число строк в её матрице, . Иначе говоря, решение ТСЛУ – это строка из элементов, добавление которой (под добавлением здесь подразумевается классическое сложение) к каждой из строк матрицы превратит ее в матрицу без строгих минимумов по строкам. Соответственно, система имеет решение, если такую строку подобрать можно.

Теперь разберём, откуда оно появляется. Если корень многочлена – это точка, в которой минимум достигается на двух и более мономах, то решение системы – это набор переменных, являющихся решениями для всех уравнений. А так как линейная функция (формула 1.1) – это минимум из сумм переменных и их коэффициентов, для проверки строку-решение нужно именно добавлять ко всем строкам.

Теперь рассмотрим пример, приведённый в [4].

Система задана матрицей

(1.4)

Её решение – строка .

В качестве проверки прибавим (в классическом смысле) это строку ко всем строкам матрицы, получим

Видим, что ни в одной её строке нет строгих минимумов.

Примером матрицы, не имеющей решений, служит

Отметим, что добавление константы к строке или столбцу матрицы, которой задана ТСЛУ, не влияет на существование решения. Более того, решения таких систем связаны. Например, если добавить к первому столбцу матрицы (1.2) константу 5, получим

(1.5)

Её решение – , ведь его добавление ко всем строкам убирает все строгие минимумы:

Получить из решения (1.4) решение ТСЛУ (1.5) можно следующим образом: решение складываем первую строку (1.4), решение системы (1.5) и вычитаем первую строку 1.5). Для рассматриваемых матриц это соотношение выглядит так:

Иначе говоря, если одна система получена из другой путём добавления константы к строке или столбцу, то решение первой определено через решение второй как сумма решения второй ТСЛУ и разности первых строк двух систем.

Пользуясь этим свойством, будем считать все коэффициенты в рассматриваемых матрицах неотрицательными.

1.4 Описание алгоритма Григорьева

Идея алгоритма Григорьева [2] заключается в том, что если в какой-либо строке матрицы ТСЛУ наблюдается строгий минимум, то нужно провести операцию, названную автором алгоритма спуском (рисунок 1.2).

Р исунок 1.2 – Схема операции спуска алгоритма Григорьева

Отметим, что порядок добавления столбцов может быть разным, но в конечном итоге максимальное J определено единственным образом.

Приведём алгоритм вычисления константы, которая используется для преобразования матрицы после спуска (рисунок 1.3). Так как локальный минимум не может превышать глобальный, константа будет неотрицательной. За то, что она не равна нулю, отвечает перестановка строк, описанная на рис. 1.2, а также тот факт, что для расчёта используется столько строк, сколько столбцов лежит в J. Для них справедливо, что все их минимумы лежат в нижнем треугольнике матрицы системы.

Рисунок 1.3 – Схема вычисления константы

Таким образом, для поиска константы нужно рассмотреть столько строк, сколько столбцов лежит во множестве J, для каждой из них найти 2 числа: минимум по лежащим в J столбцам и минимум по не принадлежащим ему. Далее найти минимум по разностям для всех строк второго и первого чисел. Перейдём к схеме алгоритма Григорьева (рисунок 1.4).

Р исунок 1.4 – Схема алгоритма Григорьева

На выходе алгоритма получаем строку, если алгоритм не установил отсутствие решений.