Введение к работе
ГД1;...-,
Актуальность темы. Данная работа посвящена разработке численного метода нахождения всех решений линейных задач дополнительности . Проблема дополнительности имеет большое теоретическое и прикладное значения, т.к. с ней тесно связаны многие задачи математического программирования . В терминах задачи дополнительности могут быть сформулированы задачи линейной и нелинейной оптимизации, задача нахождения равновесных цен и многие другие. Линейные задачи дополнительности , являясь частным случаем общей нелинейной задачи дополнительности, тем не менее представляют из себя самостоятельный интересный объект. Линейные задачи дополнительности характеризуются неединственностью решений , в то же время, как существующие алгоритмы, например, алгоритм Лемке, находят лишь одно из возможных решений. Невозможность находить всё множество решений существенно затрудняет исследование. В силу сказанного разработка алгоритма нахождения всех решений линейной задачи дополнительности является актуальной проблемой .
Цель работы состоит в исследовании неединственности задач линейной дополнительности. При этом решаются следующие задачи :
- на основе алгоритма Лемке разработать новую его модификацию,
которая могла бы находить все существующие связные решения ли
нейных задач дополнительности, исследовать свойства алгоритма и
границы его применимости ,
- разработать принципиально новый алгоритм нахождения всех
решений линейных задач дополнительности для случая несвязного
множества решений ;
исследовать предлагаемый алгоритм в теоретической плане и на тестовых примерах ;
исследовать две ыодели экономики в качестве приложения .
Общая методика исследования . При решении вышеуказанных задач использован аппарат вычислительной математики, теории матриц, теории графов и элементы теории математической экономики. Предложенные методы прошли проверку путём проведения вычислительных экспериментов и решения тестовых примеров.
Научная новизна. В диссертации предлагаются два новых алгоритма решения линейных задач дополнительности. Это модифицированный алгоритм Лейке и алгоритм рационального перебора вершин. В основу первого алгоритма положен классический алгоритм Леыке с его возможностью находить одно допустимое решение. Предложенная модификация позволяет, используя это найденное решение в качестве стартового, находить все возможные другие решения. Для успешной работы данного алгоритма требуется определённое условие, налагаемое на параметры задачи, что существенно сужает область применения. Второй из предлагаемых алгоритмов не требует никаких предварительных условий, что делает его предпочтительным. Рациональность перебора заключается в снижении трудоёмкости перебора при помощи анализа структуры задачи.
Практическая значимость. Работа выполнена в соответствии с планом научно-исследовательских работ ВЦ АН СССР по теме "Математическое моделирование экономических и природных систем" (ИГР.0188.0026042).
Алгоритмы, предложенные Е диссертации, применимы для решения некоторых важных классов оптимизационных задач, например, для решения задач линейного и квадратичного программирования. Результаты могут быть использованы при решении задач управления и планирования, экономических и инженерных задач.
Апробация работы. Основные результаты работы докладывались и обсуждались на 2 Республиканской конференции по автоматизации научных исследований (г.Алма-Ата,1988 г.), на семинарах отделов Прикладных проблей оптимизации и Проблем иоделирования Вычислительного Центра АН СССР, на еяегодных научных конференциях МФТИ (Долгопрудный 1Э87-1Э90 г.) и других научных семинарах.
Публикации. По теме диссертации опубликовано четыре печатных работы.
Структура и объйм работы. Работа состоит из введения, трёх глав, заключения, списка использованной литературы из 69 наименований. Основной текст диссертации содеряит 84 страниц машинописного текста.
Во введении излогена и обоснована актуальность темы, цель работы, структура диссертации. Приводится обзор литературы по рассматриваемой теме и даётся краткое изложение содержания и результатов работы.
Глава 1 посвящена краткому введению в теорию и методы решения линейных задач дополнительности. Здесь определены основные понятия задач дополнительности, такие как : классы матриц,
используемые в теории дополнительности, вычислительная сложность проблемы, существующие алгоритмы решения.
В параграфе 1.1 приведена постановка задачи дополнительности :
Для заданной функции I(z) : Rn =* If1, связанная с ней задача дополнительности (complementarity problem) , заключается в нахождении таких точек z е R" , в которых зависимая и независимая переменные составляют ортогональные пары
2^0 , 1(Z) 5 О , 2^1(2)=0 .
Неравенства для векторов понимаем как покомпонентные неравенства. Если ограничится линейныи отображением вида і(a) =Mz+q, где М есть матрица параметров размерности ln*nl и q вектор параметров, то приходим к линейной задаче дополнительности (ЛЗД) вида : найти а 5 О , чтобы
2»0,w = Hz + q?0, «Tz = 0 . (1.1)
Задача линейной дополнительности в дальнейшем обозначается как (U,q). Условие дополняющей нехесткости wTz=0 понимается как
№^=0 для всех 1=1.г n . Переменные w и z± образуют пару
взаимодополнительных переменных.
Классические направления математического программирования такие как линейное и квадратичное программирования, являются частными случаями ЛЗД , покажем ато. Запишем задачу линейного программирования в прямой и двойственной формах. Прямая задача: найти вектор х , минимизирующий целевую функцию
стх *- rain при ограничении Ах ^ b ; х ^ О .
Двойственная задача : найти вектор у , максимизирующий функцию
у b +- max при ограничении Ату $ с ; у Ь О
Геория двойственности линейного програшгарования при наличии цопустишх решений обоих задач утверждает , что в точке решения (х,у) выполняется равенство
yTb = стх . (1.2)
Перейден от системы неравенств к системе линейных уравнений при помощи дополнительных неотрицательных переменных V И U .
Ax-v=b і ї И і т^О ATy+u=c, y>0 ,uJO
(1.3) (1.4)
Подставляя (1.3),(1.4) в (1.2) получим
xTu + yTv = 0 . Перепишем уравнения (1.3),(1.4) так, чтобы явно выделить дополнительные переменные :
ж-к:\ш
Введем обозначения
""Р ' q:=[-J ! ""(а "о ] ! ""(і
- б -
Задача принимает вид :
w=Mz+q , zHt «Hi wTz=0 , и может рассматриваться как линейная задача дополнительности . Аналогичный образом и задача квадратичного программирования может быть сведена к ЛЗД. Типичная форма записи задачи квадратичного программирования :
стх + xTDz * min (1.5
Ах > b , і > О Выпишем условия Карута-Куна-Таккера (ККТ) для задачи (1.5)
u = 2Dx - Ату + с , v ш Ах - о , x»y»u,v >0 , yTv + И** = О.
Если ввести обозначения :
W!=P 5 q:eP J М!=Г "о ] ; 2!=й '
то задача (1.5) принимает вид задачи (1.1).
Линейная задача дополнительности допускает альтернативную форму записи
Iw-Mz=q ,«>0 , z)0, ит2=0 , где I - единичная матрица размерности I п * п. 1. Обозначим через Z(H,q) допустимое множество задачи (M,q)
Z(if,q):-{ ОО ! Us + qSO } . Будем говорить, что задача ЛЗД (li,q>) допустимая, если множество Z(U,q) непустое .Обозначим через С матрицу дополнения
Gv=q , v > О толбцы С матрицы С формируются следупцим образом :
*-:
если vi=»1 если v1=z±
йсло таких возможных матриц равно 2П, где п - размерность задэ-я . Обозначим через розС4 конус, генерируемый матрицей С1 :
posC±=po3(C^.C2^....C^)=f 2aJCJ У ^ '^=1-2 »}
Обозначим через К(М) объединение всех конусов дополнения
К(М)= U posC1 ,
1=1 ,2,...2П
шаче говоря, это множество всех q є Rn для которых задача (M,q)
шеет решение. Множество К(Н) есть замкнутый конус , содержащий іеотрипательннй ортант В" , но не всегда выпуклый.
Класс матриц М R""" для которых К (И) есть выпуклое шожество обозначается , как Q , где Р**1 - класс действительных матриц размерности In * n]. Сласс матриц U Rn*n для которых К(М) эквивалентно всему пространству Rn обозначим через Q ; QeQQ. Идентификации этих двух основных классов матриц ЛЗЛ посвящена основная масса литературы ю линейной дополнительности. Ясно , что задача ЛЗД имеет решение, если вектор правых частей q принадлежит хотя бы одному ко-іусу. Если объединение всех конусов покрывает все пространство, го задача имеет решение при любом q
їРі= U ров С (±=1,2 г" ) .
Данное условие вовсе не означает , что решение единственно прг данном q , так как вектор q иохет принадлежать одновременно нескольким конусам . Число таких конусов, которым одновременно -принадлежит вектор правых векторов q определяет число фактических решений данной задачи «которое в свою очередь не может быть больше ,чем 2П. Ключевая идея определения класса Q-матриц принадлежит D.Gale . Решение является ли матрица М Q-матрицей (MeQ ) эквивалентно решению является ли разность R" \ К(М) пустой или нет. Если эта разность есть пустое множество, то М t Q, иначе говоря, не существует такого вектора q е Rn , который не покрывался хотя бы одним из конусов дополнения.
Класс матриц Ы е К12"" для которых решение ЛЗД (14,) сущей вует и единственное при любом q є Rn есть класс Р-матриц .
Определение . Квадратная матрица называется Р-матрицей, если все главные миноры положительные.
Параграф 1.2 посвящен описанию семейства задач линейной дополнительности, к которому относится помимо классической задачи (1.1) три новых подзадачи :
- вторичная задача линейной дополнительности ( second linear complementarity problem) вида :
w = q + lis + Hu 0 = p + Rz + Su a > 0 , w & 0 , zTw=0 , -a> < u < -и» , 2,w R11 , p,u e Rm .
- минимальная задача линейной дополнительности (minimum linear
complementarity problem) вида :
pTz + qTw + rTu =» mln
Vz + Qw + Ru = b
z > 0 , w > 0 , aTw = 0
z,w Rn , b є R , u e R1.
- вторичная минимальная задача линейной дополнительности
(second minimum linear complementarity problem ) вида :
pT2 f qTw + rTu =» mln
Pz + Qw + Ru = b
z > 0 , -»<»<+« , ZjW^O , i=i,2,...,n
z,h R" , u ( R1 , li e f .
Показано,что большое число задач математического программирования могут быть сведены к одной из задач данного семейства. Такими задачами являются : линейное и квадратичное программирования (выпуклое, невыпуклое, псевдовыпуклое}, линейные вариационные неравенства, билинейное программирование, теория игр, булевое целочисленное программирование, задача фиксированных пропорций, программирование абсолютного значения, сепара-бельвое программирование.
Показано, что между задачами данного семейства существует внутренняя связь : так, например, вторичная задача линейной дополнительности при определённых условиях может быть сведена к за-
даче (1.1) . Многое из того , что развито для классической задачи (1.1) в той или иной мере может быть применено и для задач денного семейства.
Параграф 1.3 посвящен подробному изложению классического алгоритма Лемке, несмотря на то, что уже имеется литература по данному вопросу (см. Г.Реклейтис и др. "Оптимизация в технике") Это связано с тем, что во второй главе предлагается некоторая модификация данного алгоритма .
Глава 2 посвящена описанию двух алгоритмов, созданных для нахождения всех возможных решений линейных задач дополнительности . Это модифицированный алгоритм Ленке и алгоритм рационального перебора вершин. Область применения первого из них ограничена условием связности множества решений, которое заключается в следующем. Число возможных решений ЛЗД равно 2п, где п-размерность задачи. Расположим все решения в вершинах п-мер-ного гиперкуба и тогда, условие связности сводится к необходимости расположения решений в смежных вершинах. Алгоритм рационального перебора свободен от каких-либо условий, что делает его универсальным.
В параграфе 2.1 приведена схема модифицированного алгоритма Лемке. Как известно, классический алгоритм Ленке предназначен для нахождения одного из возможных решений. Разработанный в диссертации модифицированный алгоритм Лемке позволяет найти все решения линейных задач дополнительности при условии связности множества решений. Вкратце идея модификации состоит в следующем. После успешного вывода искусственной переменной алгоритм Лемке завершает работу с найденным допустимым решением. Предлагаемый
алгоритм использует данное решение в качестве стартового для анализа смежных вершин. Для этого выбирается любой внебазисный столбец в качестве ведущего, применяется правило минимального отношения с целью определения переменной, выводимой из базиса. Если правило минимального отношения невозможно применить, т.к. все элементы ведущего столбца неположительные, то выбирается любой другой из оставшихся внебазисных столбцов. Если после перебора всех п внебазисных столбцов не удалось найти столбца с положительными элементами, то считается, что данное решение изолированное , иначе говоря смежные вершина не содержат альтернативных решений. Данное условие является лишь необходимым, но не достаточным. Достаточным является условие по которому вводимая и выводимая переменные должны образовывать взаиыодополнительную пару.
Параграф 2.2 посвящен обсуждению алгоритма рационального перебора вершин. Известно, что комбинаторные задачи можно решать за счёт простого перебора вершин. Не менее очевидно, что так можно решать лишь задачи малой размерности. Не исключение составляют и задачи линейной дополнительности, т.к. они относятся к классу MF-полных задач. Принципиально новым в предлагаемом алгоритме является его способность анализировать структуру . задачи дополнительности. Анализ позволяет уменьшить трудоёмкость процедуры поиска, заведомо исключая из рассмотрения вершины без решений.
Идея подхода заключается в последовательном отделении базисных и внебазисных переменных, что и является решением задачи. Для уменьшения трудоёмкости проблемы делается первоначальный
анализ 2п столбцов матрицы ограничений. Этот анализ призван ответить на вопрос : все ли столбцы способны принять участие в формировании базиса. Если да, то задача сразу становится трудоёмкой. Условимся оценивать трудоёкость задачи числом вершин, необходимых для рассмотрения. Если найдутся такие столбцы, которые можно заведомо исключить из рассмотрения, то тем самым задача существенно упрощается. Исходная трудоёмкость составляет 2П вершин, в то время, как для задачи с исключёнными столбцами трудоёмкость снижается до 2п_а вершин, где а - число исключённых столбцов.
6 главе 3 проведено исследование двух моделей экономики : модели чистого обмена и модели экономики с производством. Основной вопрос данного исследования - условия существования равновесия по Вальрасу. Состояние экономического равновесия характеризуется тем, что ни один из экономических агентов не заинтересован в его изменении с помощью средств , которыми он располагает. Обширный и важный класс составляют модели , в которых под состоянием экономического агента понимается выбираемый им вектор затрат ( потребление ) и выпуска продуктов , под согласованностью имеется в виду выполнение материальных и финансовых балансов для системы в целом , а в качестве инструмента согласования выступают цены благ. Будем их называть моделями ценового равновесия. Для построения модели ценового равновесия необходимо задать правило формирования и распределения доходов. Согласно бюджетному ограничению расходы участника не должны превосходить его доходов, складывающихся из оплаты ресурсов , которыми он располагает. Данная глава посвящена следующей задаче : ис-
следовать иодель равновесия при конкретной функции полезности, а именно функции Кобба- Дугласа . Показано, что в результате исследования получены линейные соотношения , которые легко интерпретируются. Параграф 3.1 посвящен исследовании модели чистого обмена, с функцией полезности типа Кобба- Дугласа. Параграф 3.2 посвящен более общей иодели, которая вклвчает в себя производство. Для этих моделей получены условия достаточного типа, выполнение которых гарантирует существование равновесного вектора цен. В рассмотренных моделях вопрос существования равновесного вектора цен сведён к вопросу о разложимости некоторой матрицы .