ЖУРНАЛ ВЫЧИСЛИТЕЛЬНОЙ МАТЕМАТИКИ И МАТЕМАТИЧЕСКОЙ ФИЗИКИ, 2008, том 48, < 7, с. 1167-1180
УДК 519.612
КОНСТРУКТИВНЫЙ АЛГОРИТМ СВЕРТЫВАНИЯ СИСТЕМ ЛИНЕЙНЫХ НЕРАВЕНСТВ ВЫСОКОЙ РАЗМЕРНОСТИ
© 2008 г. А. М. Лукацкий, Д. В. Шапот
(117186 Москва, ул. Нагорная, 31-2, ИНЭИ РАН) e-mail: macrolab@eriras.ru Поступила в редакцию 30.11.2007 г. Переработанный вариант 01.02.2008 г.
Традиционная процедура свертывания системы линейных неравенств, основанная на алгоритме Фурье-Черникова, дополняется методами исключения зависимых неравенств, позволяющими существенно ослабить разрастание системы. Предлагаются как точные, так и приближенные методы, доведенные до алгоритмов и программной реализации. Обсуждаются результаты машинных экспериментов. Библ. 10. Табл. 5
Ключевые слова: выпуклые многогранники, линейные неравенства, метод ортогональных проекций; алгоритм Фурье-Черникова, согласование диапазонов, зависимые неравенства, точная чистка зависимых, симплекс-алгоритм, чистка зависимых с загрублением, вычислительные эксперименты.
ВВЕДЕНИЕ
При исследовании линейных моделей весьма полезной может оказаться процедура свертывания системы линейных неравенств. Геометрически эта процедура эквивалентна ортогональному проектированию многогранника на подпространства, получающиеся путем последовательного исключения независимых переменных, т.е. удаления элементов из базисного набора векторов. В дальнейшем будем ее называть процедурой ортогонального проектирования (ПОП). В результате ее использования формируется решение системы неравенств в явном виде, когда выбор значения любой переменной может быть сделан в пределах определяемого числового интервала. При этом для одной из переменных этот интервал является соответствующей проекцией, а для всех остальных переменных он определяется линейными функциями от выбранных значений ранее рассмотренных переменных. Подобный подход может эффективно использоваться во многих исследованиях. Здесь уместно отметить следующие направления.
Во-первых, при моделировании объектов разной природы нередко возникает ситуация, когда приходится учитывать факторы, которые сами по себе не представляют интереса для исследователя. В частности, в экономико-математических моделях подобными факторами являются замыкающие статьи различных балансов. Обычно в моделях они задаются как параметры, т.е. численно. Степень их влияния на результаты исследования модели легко определить, варьируя соответствующие числовые оценки. Однако когда модель содержит несколько таких параметров, подобный вариантный анализ перестает быть целесообразным. Если они фиксируются в модели в виде свободных членов, то в такой ситуации удобно в качестве объекта исследования использовать проекцию исходной модели на подпространство, не содержащее рассматриваемых параметров.
Во-вторых, с помощью ПОП можно получить полное решение задачи параметрического программирования, т.е. найти в явном виде кусочно-линейную зависимость оптимального решения задачи линейного программирования (ЛП) от таких параметров линейной модели, как свободные члены ограничений и (или) граничные значения независимых переменных. Правда, учитывая, что в современных условиях решение стандартных задач ЛП даже высокой размерности требует незначительных затрат времени, актуальность привлечения дополнительного инструментария может вызывать сомнения.
В-третьих, явная запись системы линейных неравенств может быть весьма полезной при выборе технологически допустимых отклонений от номинальных значений параметров любых изделий, если область их работоспособности (Р) задается линейной моделью. Это позволит гораздо полней использовать Р при переходе от общепринятых взаимонезависимых допусков к системе за-
висимых допусков, поскольку приводит к замене вписанного в Р прямоугольного параллелепипеда на вписанный многогранник. Тем самым можно заметно уменьшить долю бракуемых изделий.
Кроме того, существуют проблемы, для решения которых использование ПОП вряд ли имеет альтернативу. К числу таких проблем следует отнести построение инструментальных средств для резкого повышения эффективности процедур согласования решений нескольких партнеров, имеющих несовпадающие интересы, о какой бы области человеческой деятельности ни шла речь. Здесь можно говорить, например, о согласовании параметров любых объектов (проектов, процедур, изделий и т.д.) в рамках технологического, коммерческого, финансового или управленческого аспектов.
В настоящей работе рассматриваются следующие вопросы:
а) в порядке иллюстрации обсуждается конкретная методика использования ПОП в одном из перспективных направлений - в процедурах согласования.
б) излагаются и обосновываются известные правила построения ортогональных проекций многогранников и анализируются причины нерациональности их практического использования в задачах со многими переменными;
в) предлагаются и экспериментально исследуются конкретные алгоритмы, устраняющие препятствия к практическому использованию ПОП, они связаны с выявлением зависимых неравенств и "загрублением" многогранников.
1. МЕТОДИКА ИСПОЛЬЗОВАНИЯ ПОП В ПРОЦЕДУРАХ СОГЛАСОВАНИЯ
Рассмотрим в общем виде соответствующую постановку задачи. Пусть имеются несколько партнеров с несовпадающими интересами, которые должны сформировать компромиссное решение по поводу численных значений ряда параметров некоторого объекта. Предположим, что для ]-го партнера количественную оценку у ] степени реализации его интересов можно получить с помощью решения соответствующей задачи ЛП со специфической совокупностью независимых переменных Х], но с общим набором согласуемых параметров С. Эта задача предполагает запись линейной целевой функции у = Н](Х], С) и области допустимых решений в виде системы линейных равенств и неравенств
{(Х] , С )> 0 }, I = 1, 2,..., г.. (1.1)
Здесь функции Н] и ] предполагаются линейными как по переменным Х], так и по компонентам вектора параметров С.
Целесообразно использовать двухэтапную процедуру согласования. На первом этапе следует договориться, во-первых, о возможных (допустимых) диапазонах АС варьирования параметров С, а во-вторых, об одинаковом для всех партнеров предельно допустимом относительном снижении
q максимально достижимого индивидуального эффекта у0 при заданных диапазонах АС. На втором этапе производится выбор конкретных значений согласуемых параметров. Для резкого повышения эффективности переговоров на втором этапе предлагается предварительно выполнить следующую совокупность вычислительных операций.
1. Каждый партнер определяет значение у0, решая соответствующую задачу ЛП], в которой параметры С рассматриваются как независимые переменные, варьируемые в согласованных диапазонах.
Если хотя бы для одного партнера ограничения соответствующей задачи ЛП] окажутся несовместными, то процедура выбора компромиссных значений параметров С не имеет смысла. В этом случае придется либо расширить допустимые диапазоны АС, либо отказаться от поиска совместного решения. Будем считать, что для всех партнеров существуют и найдены предельные
о
значения у..
2. Каждый партнер строит проекцию на подпространство параметров С многогранника, задаваемого системой (1.1) и дополнительным неравенством qy0 < Н](Х],С) < у0, где С е АС. Эта проекция будет представлена следующим набором линейных неравенств:
Р]( С) = {Р] (С )> 0}, I = 1, 2,..., sJ. (1.2)
Полученные результаты позволяют построить область совместных решений всех партнеров в пространстве согласуемых параметров С в виде Р(С) = О Р;(С). Для этого достаточно "объединить" (1.2) по всем у, построив единую систему линейных неравенств [ру(С) > 0}.
3. Построение проекции многогранника Р(С) на ось любого (лучше наиболее "дискуссионного") из согласуемых параметров. В результате окажется возможным выяснить, является ли Р(С) пустым множеством. В подобном случае придется либо уменьшить общий нижний предел индивидуальных эффектов ц, либо отказаться от поиска совместного решения. Если Р(С) не пусто, то можно реализовать второй этап процедуры поиска компромисса.
На втором этапе производится последовательный выбор численных значений согласуемых параметров в обратном порядке, относительно того, в котором проводилось их исключение при построении проекции Р(С). На каждом шаге этой последовательной процедуры ее участникам предъявляется сформированный с помощью результатов проведенных вычислений числовой диапазон допустимых для всех партнеров значений очередного рассматриваемого параметра. Этот диапазон зависит, в частности, и от выбранных значений ранее согласованных параметров. После согласования всех компонент вектора С партнеры могут оценить с помощью соответствующей задачи ЛП достигнутый для каждого из них уровень у. Очевидно, что при желании партнеров процедура выбора конкретных значений согласуемых параметров может быть многократно повторена. Важно подчеркнуть, что при каждой подобной попытке, реализуемой в рамках непосредственного переговорного процесса, всем партнерам гарантирован положительный результат в ранее согласованных пределах. А в случае объективной невозможности достижения подобного результата этот факт выявляется до начала основных переговоров.
2. ОРТОГОНАЛЬНОЕ ПРОЕКТИРОВАНИЕ. АЛГОРИТМ ФУРЬЕ Пусть К" - действительное я-мерное пространство. Проекцией множества Qn с К" на подпро-
странство
т,п - к
называется множество
PkQn = Q
п - к'
Ух' е Qn - к ЗМ е К : (х', М )е Qn
^у е Qn - кЗ V' е Кк : (у', V' )е Qn)
Общий алгоритм построения проекций, к сожалению, возможен лишь для выпуклых множеств, задаваемых линейными неравенствами, хотя в некоторых частных случаях эту задачу удается решать и для нелинейных выпуклых множеств (см., например, [1]).
Рассмотрим непустое ограниченное множество Qn, задаваемое системой линейных неравенств
Qn = 1 X+ ЬУ > (У = 1' 2' •••'т) = 3 |
ч = 1 1
Пусть необходимо построить Qn _ 1 с к" 1, где к" 1 не зависит от некоторой переменной хг. Согласно алгоритму свободного свертывания систем линейных неравенств, предложенного Фурье, разобьем множество индексов 3 на три группы: Q(1) = (V = 1, 2, ..., s), Q(2) = („ = 5 + 1, ..
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.