научная статья по теме БЫСТРЫЙ СПОСОБ ПРОВЕРКИ ПРАВИЛА ЧЕРНИКОВА В МЕТОДЕ ИСКЛЮЧЕНИЯ ФУРЬЕ–МОЦКИНА Математика

Текст научной статьи на тему «БЫСТРЫЙ СПОСОБ ПРОВЕРКИ ПРАВИЛА ЧЕРНИКОВА В МЕТОДЕ ИСКЛЮЧЕНИЯ ФУРЬЕ–МОЦКИНА»

ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2015, том 55, № 1, с. 165-172

УДК 519.7

БЫСТРЫЙ СПОСОБ ПРОВЕРКИ ПРАВИЛА ЧЕРНИКОВА В МЕТОДЕ ИСКЛЮЧЕНИЯ ФУРЬЕ-МОЦКИНА1)

© 2015 г. С. И. Бастраков, Н. Ю. Золотых

(603950Нижний Новгород, пр. Гагарина, 23, Нижегородский гос. ун-т) e-mail: sergey.bastrakov@gmail.com; nikolai.zolotykh@gmail.com Поступила в редакцию 14.03.2014 г.

Рассматривается задача исключения неизвестных из систем линейных неравенств. Предлагается новый быстрый способ проверки правил Черникова в методе Фурье—Моцкина, являющийся адаптацией "графового" теста для проверки смежности в методе двойного описания. Приводятся результаты вычислительных экспериментов, подтверждающие эффективность данного способа. Библ. 9. Фиг. 6.

Ключевые слова: система линейных неравенств, полиэдр, исключение переменных, метод Фурье—Моцкина, правила Черникова.

DOI: 10.7868/S0044466915010044

1. ВВЕДЕНИЕ

Одной из базовых операций теории систем линейных неравенств является исключение переменных (см. [1], [2]). Для системы линейных неравенств вида

Ax < b, (1)

где A e Rm х d, x e Rd, b e Rm, исключение переменной xk, где k e {1, 2,..., d}, состоит в построении системы линейных неравенств

A(k)x < b(k), (2)

A(k) e Rm'x d, b(k) e Rm, обладающей следующими свойствами:

♦ система (2) является следствием исходной системы (1);

♦ в систему (2) не входит исключаемая переменная xk (все соответствующие коэффициенты равны нулю);

♦ для любого решения системы (2) существует решение системы (1), совпадающее с ним по всем компонентам, кроме, возможно, k-й.

Обозначим полиэдры решений систем (1) и (2) соответственно через

P = P(A, b) = {x: Ax < b}; (3)

P(A(k), b(k)) = {x : A(k)x < b(k)}. (4)

Следуя [2], введем операции над полиэдром P с Rd:

projkP = {x — xkek : x e P} = {x e Rd : xk = 0, 3y e R : x + yek e P},

elimkP = {x - tek : x e P, t e R} = {x e Rd : 3y e R : x + yek e P},

где ek есть k-й вектор стандартного базиса в Rd. Тогда для полиэдров (3) и (4) справедливо соотношение

P(A(k), b(k)) = elimkP(A, b).

1) Работа выполнена при финансовой поддержке ФЦП "Научные и научно-педагогические кадры инновационной России" (госконтракт № 14.В37.21.0393) и РФФИ (код проекта 14-07-31318).

Геометрически ргсцкР является проекцией полиэдра Р на координатную плоскость хк = 0, а еНткР — множеством всех точек с проекцией ргс^Р.

Классическим алгоритмом решения задачи исключения переменных является метод Фурье— Моцкина (см., например, [1], [2]), основная идея которого — комбинирование пар неравенств исходной системы, т.е. взятие их линейных комбинаций с такими множителями, в результате которых получается неравенство-следствие с исключенной неизвестной. В процессе работы этот метод порождает огромное количество избыточных неравенств, поэтому в оригинальном виде он практически не применим к системам с большим числом неизвестных. С.Н. Черников (см. [3], [4]) предложил два дополнительных правила, позволяющих уменьшить порождение значительной части избыточных неравенств. Метод исключения Фурье—Моцкина с двумя правилами Черникова иногда называется методом Фурье—Черникова. Заметим, что для однородных систем алгоритм Фурье—Черникова является оптимальным по числу комбинирований для исключения одного неизвестного (см. [4]).

Известно (см., например, [1], [2]), что метод исключения может быть применен для построения двойственного описания полиэдра, т.е. для нахождения по описанию полиэдра в виде (1) его описания в виде суммы выпуклой и конической оболочек конечных систем векторов

Р = есиу{у1, у2, ..., ур} + еспе{^1, w2, ..., wq}, (5)

где v¡ е И*, I = 1, 2,.,р, е И*,] = 1, 2, ..., q, и, следовательно, ввиду двойственности, наоборот. Действительно, пусть имеется описание (5). Чтобы получить описание (3), запишем условие х е Р:

Р 9 Р

х = ^аV + ^^а = 1, а > о, / = 1,2,...,р, р;> о, у = 1,2,..., 9,

I = 1 у = 1 I = 1

и из полученной системы исключим параметры а, i = 1, 2,., р, ру-, ] = 1, 2,., q. Как отмечено, например, в [1], [2], метод исключения, примененный к этой системе, эквивалентен методу двойного описания (см. [5]). С другой стороны, эти два метода существенно различны: метод исключения Фурье—Моцкина в отличие от метода двойного описания не использует важную информацию о двойственном описании полиэдра по [6]. Тем не менее связь между двумя методами подталкивает попробовать применить различные усовершенствования одного из них (метода двойного описания) к другому (методу исключения).

В настоящей работе предлагается быстрый способ проверки второго правила Черникова, являющийся адаптацией "графового" теста для проверки смежности экстремальных лучей из [7]. Вычислительный эксперимент показывает, что использование предлагаемого способа значительно снижает общее время работы.

Другие методы ускорения процедуры исключения рассматривались в [8].

Заметим, что задача исключения переменных из неоднородных систем линейных неравенств с d неизвестными может быть легко сведена к случаю однородных систем с d + 1 неизвестными. Для системы вида (1) введем новую неизвестную х0 и построим систему Ах — Ьх0 < 0, х0 > 0, для которой решим задачу исключения. После получения решения переход к исходным переменным осуществляется подстановкой х0 = 1. Указанный переход к однородной системе ("гомогенизация") не меняет вычислительной сути задачи, однако упрощает запись алгоритмов, поэтому в дальнейшем будет рассматриваться задача исключения переменных из однородной системы линейных неравенств вида

Ах < 0. (6)

Работа имеет следующую структуру. Разд. 2 посвящен методу исключения Фурье—Моцкина. Описание метода Фурье—Черникова содержится в разд. 3. Предлагаемый быстрый способ проверки правил Черникова излагается в разд. 4. В разд. 5 приводятся результаты вычислительных экспериментов.

2. МЕТОД ИСКЛЮЧЕНИЯ ФУРЬЕ-МОЦКИНА

Метод исключения Фурье—Моцкина из [1], [2] выполняет последовательное исключение заданных переменных из системы линейных неравенств. На каждой итерации очередная переменная исключается из системы, полученной в результате исключения предыдущей переменной. Порядок исключения переменных может существенно влиять на количество производимых операций, но не влияет на итоговый результат и в данном разделе не обсуждается.

pro ced^a ^^ tzkin_ Е1 imination' Iteration (A, k)

Фиг. 1. Метод исключения Фурье—Моцкина: вход — матрица системы A, множество индексов исключаемых переменных K, выход — матрица системы после исключения.

Исключение переменной из системы (6) производится следующим образом. В зависимости от знака коэффициента перед исключаемой переменной все неравенства системы разбиваются на три множества 1+, 1_ и 10 (соответственно с положительным, отрицательным и нулевым коэффициентом). Производится построение новых неравенств, которые являются линейными комбинациями всевозможных пар неравенств из 1+ х 1_ с положительными коэффициентами, выбранными таким образом, чтобы коэффициент перед исключаемой переменной в результирующем неравенстве был равен 0. В дальнейшем построение такой линейной комбинации неравенств будем называть комбинированием. Результирующая система составляется из новых неравенств, полученных путем комбинирования, и неравенств исходной системы из множества 10. Легко видеть, что построенная таким образом система является следствием исходной (часть неравенств сохраняются, остальные являются суммами неравенств исходной системы с положительными коэффициентами), коэффициенты перед исключаемой переменной равны нулю по построению. Таким образом, построенная система является результатом исключения заданной переменной из исходной системы. Псевдокод метода исключения Фурье—Моцкина приведен на фиг. 1.

А1 обозначает 1-ю строку матрицы А; А1, где I является множеством натуральных чисел, обозначает множество строк (подматрицу) матрицы с номерами из I; Ау — элемент 1-й строки у-го столбца матрицы А. Для упрощения записи будем подразумевать соответствие между матрицей системы вида (6) и множеством ее строк и выражать добавление нового неравенства в терминах добавления вектора-строки в множество строк.

При исключении одной переменной порождается |1+| • |1_| новых неравенств, общее количество неравенств результирующей системы составляет |1+| • |1_| + |10|. В худшем случае каждое из множеств 1+, 1_ содержит половину всех неравенств, и количество неравенств системы, полученной исключением одной переменной, квадратично зависит от количества неравенств исходной системы. При последовательном исключении ж переменных из системы т неравенств возможность квадратичного роста количества неравенств на каждой итерации дает достижимую верх-

а

нюю оценку трудоемкости 0((т/4) ), что делает метод мало применимым на практике. При

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

3. ПРАВИЛА ЧЕРНИКОВА

С.Н. Черников (см. [3], [4]) предложил алгоритм сокращенного фундаментального свертывания, являющийся модификацией алгоритма Фурье—Моцкина с добавлением двух правил, позволяющих избежать порождения некоторых избыточных неравенств. Данные правила обычно называются правилами Черникова, а метод исключения Фурье—Моцкина с модификацией Черникова иногда называют алгоритмом Фурье—Черникова.

С каждым неравенством ассоциируется индекс, являющийся множеством целых чисел. Индексы неравенств исходной системы состоят из их номеров в матрице системы, при комбинировании пары неравенств их индексы объединяются. Неформально говоря, первое правило Черникова состоит в комбинировании лишь тех пар, объединение индексов которых имеет "малую" мощность. Второе правило состоит в отбрасывании неравенств, индексы которых содержат индекс другого неравенства. Комбинации пар неравенств из 1+ х I—, не удовлетворяющие правилам Черникова, всегда являются неравенствами-следствиями и поэтому не порождаются.

Псевдокод итерации метода исключения Фурье—Моцкина с использованием правил Черникова приведен на фиг

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком