Serguey Zefirov (thesz) wrote,
Serguey Zefirov
thesz

Categories:

Решение систем линейных ограничений в целых числах.

zelych сподвигнул. ;)

Я не думаю, что это то, что он хотел, тем не менее, я напишу. Потому, что надо. ;)

Проще всего решать системы линейных уравнений, вида ∩Σaijxij+cj=0 (aij и cj - целые числа). Основная загвоздка в том, что у нас, в общем, нет операции деления (деления без остатка, что возможно только у рациональных и вещественных чисел). Поэтому матричные методы применить тяжело, лучше применять какие-нибудь удаления (Гаусса, например).

Вместо деления мы умножаем целевую строку и удаляемую строку на коэффициенты при удаляемой переменной, с учетом общего делителя. Звучит страшнее, чем выполняется.

Допустим, мы хотим удалить строку A:6x+5y-3=0 из строки B:-4x+2z=0. Мы должны умножить A на 2, а B на три, и сложить. Получим C:(2A+3B):12x+10y-6-12x+6z=0. C:10y+6z-6=0. Если бы при x в B стояло положительное число, то строку A надо было бы умножать на -2.

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

В процессе удаления строк мы можем наткнуться на противоречие, оно будет иметь вид A=0, где A - какая-то ненулевая константа. В этом случае система не имеет решений.

Если же мы получили строку 0=0, то ее можно отбросить, как тривиальную.

К системам уравнений мы можем добавить системы неравенств. Они будут иметь вид 0≤Σaixi+c или Σaixi+c≤0. Надо заметить, что выберем ли мы < или ≤ в качестве отношения, роли не играет. В отличии от рациональных и вещественных вариантов мы всегда можем выразить одно через другое: x+1≤0 ⇔ x<0.

В процессе удаления переменных из системы равенств мы также должны удалять переменные и из системы неравенств. Здесь отличий нет.

После удаления всех переменных методом, допустим, Гаусса, надо переходить к использованию удалению переменных методом Фурье-Моцкина.

Оный метод очень прост: надо найти любую переменную, которая имеет и нижнюю, и верхнюю границу, пусть эти границы и представляют собой выражения. Затем мы исключаем эту переменную из системы, удаляя все неравенства, в которые она входит и добавляя новые, сконструированные неравенства.

Сперва про переменные с нижней и верхней границей. Вот пример:

x-y+3≤0
x+y-4≤0

Для переменной x перенос оставшихся членов вправо даст такую систему:

x≤y-3
x≤4-y

То есть, для x не существует нижней границы. А вот для y она имеется:
-y≤-x-3 или y≥x+3 (умножение на -1 приводит к смене знака отношения) и
y≤4-x

Таким образом, y находится между x+3 и 4-x (включительно для обеих границ).

Мы можем удалить эти два неравенства с y, и добавить туда новое отношение:
x+3≤4-x или 2x-1≤0

Больше в этом маленьком примере работы нет. Для всех x≤(1/2) система будет выполняться.

В общем же случае мы получим несколько верхних (y≤Hi) и несколько нижних (y≥Lj) границ. Наша переменная y будет лежать в диапазоне (MAX Lj≤y≤MIN Hi). Выглядит сурово, однако легко сводится к системе неравенств: мы просто должны добавить неравенства Lj≤Hi для всех i и j.

Количество неравенств вырастает, однако количество переменных падает. И мы можем упростить неравенства, убрав из них наиболее слабые.

Например, если мы обнаружим два неравенства A:Σaixi+c≤0 и B:Σbixi+d≤0 и при этом есть некие множители m и n, такие, что mai=nbi и xi совпадают, то задача сводится к более простой:
X≤mc
X≤nd, где X=mΣaixi=nΣbixi.

Из двух чисел mc и nd надо выбрать максимальное и нашу пару надо заменить на неравенство X≤MAX(mc,nd).

В процессе упрощения задачи мы можем обнаружить и тривиальные неравенства вида -5≤0, и противоречия вида 5≤0. Первые просто обрасываются, вторые сигнализируют о неразрешимости исходной задачи.

В процессе решения хорошо бы вести учет производимым действиям. Во-первых, надо хранить определения для убираемых переменных. Во-вторых, при удалении Фурье-Моцкина надо бы хранить диапазоны удаляемой переменной (все нижние и все верхние границы), чтобы потом подставить результирующие диапазоны.

Теперь совсем немного про реализацию (http://thesz.mskhug.ru/browser/fort/IConstr.hs - она не очень полна, тем не менее все описанные выше пункты в ней есть).

При реализации на Хаскеле напрашивается монада состояния, чтобы производить операции над таблицами равенств и неравенств. Однако, решение у системы может отсутствовать, значит, монада должна еще и обладать свойствами монады Error, которая может отказать в процессе вычисления. Плюс, ограничения вида a≠b приводят к созданию двух систем: в одной a≤b-1, в другой a≥b+1. Получается еще и недетерминизм. В результате, как мне удачно посоветовал lomeo получается StateT (состояние решателя) [] a. Монада преобразования состояния над списком (который есть монада с недетерминированным выполнением).

Чего у меня не хватает.

У меня не хватает собирания результатов обратно во что-то более читабельное. Что-то наподобие "все проходит успешно, если n≥1, и i=j+2". Этого у меня нет, поскольку до существенной части моего "компилятора" я все никак не могу дойти. Однако, если потребуется, то я добавлю. Я просто не могу сообразить, что же может потребоваться, какой результат нужен. ;)
Subscribe
  • Post a new comment

    Error

    Anonymous comments are disabled in this journal

    default userpic

    Your reply will be screened

    Your IP address will be recorded 

  • 13 comments