Задачи дополнительности и экономическое равновесие тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

1. О 3 1

РОССИЙСКАЯ АКАДЕМИЯ НАУК ВЫЧИСЛИТЕЛЬНЫЙ ЦЕНТР

На правах рукописи

(ШАБАЕВ БЕЙБУТ ТУЛЕУГАЗИНОВИЧ

ЗАДАЧИ ДОПОЛНИТЕЛЬНОСТИ И ЭКОНОМИЧЕСКОЕ РАВНОВЕСИЕ

Специальность 01.01.09 - "Математическая кибернетика"

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата физико-иатеыагическях наук

МОСКВА - 1992

Работа выполнена в Вычислительном Центре Российской Акадешш Наук

Научный руководитель : доктор физико-математических науз

профессор Ю.П.Иваншюв Официальные оппоненты : доктор физико-математических наз

¿.П.Афанасьев кандидат физико-математических на: А.И.Голиков

Ведущая организация : Московский Физико-ТехническиЙ

на заседании Специализированного совета К002.32.01

при Вычислительном Центре Российской Академии Наук по адресу

117333 , Москва, ул. Вавилова 40, конференцзал.

С диссертацией можно ознакомиться в библиотеке Математического института Российской Академии Наук.

Ученый секретарь Специализированного совета

доктор физико-математических тук^у^^ К.В.Рудакое

Институт

Защита состоится

Автореферат разослан

' ' -V....-.] ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Данная работа посвящена разработке численного метода нахождения всех решений линейных задач дополнительности . Проблема дополнительности имеет большое теоретическое и прикладное значения, т.к. с ней тесно связаны многие задачи математического программирования . В терминах задачи дополнительности могут быть сформулированы задачи линейной и нелинейной оптимизации, задача нахождения равновесных цен и многие другие. Линейные задачи дополнительности , являясь частным случаем общей нелинейной задачи дополнительности, тем не менее представляют из себя самостоятельный интересный объект. Линейные задачи дополнительности характеризуются неединственностью решений , в то же время, как существующие алгоритмы, например, алгоритм Лемке, находят лишь одно из возможных решений. Невозможность находить всё множество решений существенно затрудняет исследование. В силу сказанного разработка алгоритма нахождения всех решений линейной задачи дополнительности является актуальной проблемой .

Цель работы состоит в исследовании неединственности задач линейной дополнительности. При этом решаются следующие задачи :

- на основе алгоритма Лемке разработать новую его модификации, которая могла бы находить все существующие связные решения линейных задач дополнительности, исследовать свойства алгоритма и границы его применимости ;

- разработать принципиально новый алгоритм нахождения всех решений линейных задач дополнительности для случая несвязного

- г -

множества решений ;

- исследовать предлагаемый алгоритм в теоретической плане и на тестовых примерах ;

- исследовать две модели экономики в качестве приложения .

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

Научная новизна. В диссертации предлагаются два ноши алгоритма решения линейных задач дополнительности. Это модифицированный алгоритм Лемке и алгоритм рационального перебора вершин. В основу первого алгоритма положен классический алгоритм Лемке с его возможностью находить одно допустимое решение. Предложенная модификация позволяет, используя это найденное решение в качестве стартового, находить все возможные другие решения. Для успешной работы данного алгоритма требуется определённое условие, налагаемое на параметры задачи, что существенно суяает область применения. Второй из предлагаемых алгоритмов не требует никаких предварительных условий, что делает его предпочтительным. Рациональность перебора заключается в снижении трудоёмкости перебора при помощи анализа структуры задачи.

Практическая значимость. Работа выполнена в соответствии с планом научно-исследовательских работ ВЦ АН СССР по теме "Математическое моделирование экономических и природных систем" (ИГР. 0188.0026042).

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

Апробация работы. Основные результаты работы докладывались и обсуждались на 2 Республиканской конференции по автоматизации научных исследований (г.Алма-Ата,1988 г.), на семинарах отделов Прикладных проблей оптимизации и Проблем моделирования Вычислительного Центра АН СССР, на ежегодных научных конференциях МФТИ (Долгопрудный 1Э87-19Э0 г.) и других научных семинарах.

Публикации. По теме диссертации опубликовано четыре печатных работы.

Структура и объйм работы. Работа состоит из введения, трёх глав, заключения, списка использованной литературы из 69 наименований. Основной текст диссертации содержит 84 страниц машинописного текста.

СОДЕРЖАНИЕ РАБОТЫ

Во введении изложена и обоснована актуальность темы, цель работы, структура диссертации. Приводится обзор литературы по рассматриваемой теме и даётся краткое изложение содержания и результатов работы.

Глава 1 посвящена краткому введению в теорию и методы решения линейных задач дополнительности. Здесь определены основные понятия задач дополнительности, такие как : классы матриц,

используемые в теории дополнительности, вычислительная сложность проблемы, существующие алгоритмы решения.

В параграфе 1.1 приведена постановка задачи дополнительности :

Для заданной функции í(z) : Rn =» R", связанная с ней задача дополнительности (complementarity problem) , заключается в нахождении таких точек z е R" , в которых зависимая и независимая переменные составляют ортогональные пары

z $ О , í(z) 5 0 , z*f(z)eO . Неравенства для векторов понимаем как покомпонентные неравенства. Если ограничится линейным отображением вида 1(a) =Mz+q, где М есть матрица параметров размерности tn»n3 и q вектор параметров, то приходим к линейной задаче дополнительности (ЛЗД) вида : найти 2^0, чтобы

2»0,w = Hz + q¿0, «Tz = 0 . (1.1)

Задача линейной дополнительности в дальнейшем обозначается как (U,q). Условие дополняющей нежёсткости wTz=0 понимается как

»^=0 для всех 1=1.г.....п . Переменные w и zi образуют пару

взаимодополнительных переменных.

Классические направления математического программирования такие как линейное и квадратичное программирования, являются частными случаями ЛЗД , покажем это. Запишем задачу линейного программирования в прямой и двойственной формах. Прямая задача: найти вектор х , минимизирующий целевую функцию

стх *- rain при ограничении Ах ^ b ¡ х ^ О .

Звойственная задача : найти вектор у , максимизирующий функцию

утЪ max при ограничении Ату $ с ; у J О .

Геория двойственности линейного программирования при наличии допустимых решений обоих задач утверждает , что в точке решения (х,у) выполняется равенство

утЬ = стх . (1.2)

Перейдем от системы неравенств к системе линейных уравнений при помощи дополнительных неотрицательных переменных v и и .

Ax-v=b ; х > 0 ; v ^ О . (1.3)

Ату+и=с, у > О , и J О . (1.4)

Подставляя (1.3), (1.4) в (1.2) получим

хти + yTv = 0 .

Перепишем уравнения (1.3),(1.4) так, чтобы явно выделить дополнительные переменные :

СНгЖМ •

Введем обозначения :

W!=(y] q:=[-J; М!=(А "О:

- б -

Задача принимает вид :

w=Mz+q ,2)0,11)0, wTz=0 , и может рассматриваться как линейная задача дополнительности . Аналогичным образом и задача квадратичного программирования может быть сведена к ЛЗД.

Типичная форма зашей задачи квадратичного программирования :

стх + xTDx +• min (1.5

Ах > b , х > О

Выпишем условия Каруша-Куна-Твккера (ККТ) для задачи (1.5)

u = 2Dx - Ату + с , V = Ах - Ь , i,y,u,v >0 , yTv Л = О.

Если ввести обозначения :

"!=Р 5 q:eP J "'"[Г "о ] ; 21=й '

то задача (1.5) принимает вид задачи (1.1).

Линейная задача дополнительности допускает альтернативную форму записи

Iw-Mz=q , « ) 0 , z ) О , ит2-0 , где I - единичная матрица размерности [ n * п ]. Обозначим через Z(U,q) допустимое множество задачи (II,q)

Z(if,q):-{ 230:uz + q^0> . Будем говорить, что задача ЛЗД (II, q) допустимая, если множество Z(M,q) непустое .Обозначим через С матрицу дополнения

с?=4 , V > О

'толбцы С1 матрицы С формируются следующим образом :

{I, « если 1 1±

-И± , если у1=2± йсло таких возможных матриц равно 2П, где п - размерность зада-я . Обозначим через розС1 конус, генерируемый матрицей С1 :

розС1=роз(С^,С2^....С^)=^ у .....

Обозначим через К(Ы) объединение всех конусов дополнения

К(М)= и розС1 , 1=1 .2,...2П

шаче говоря, это множество всех ц е 11п для которых задача (М^)

шеет решение. Множество К(И) есть замкнутый конус , содержащий »отрицательный ортант В" , но не всегда выпуклый.

Класс матриц М € Яп"п для которых К (И) есть выпуклое шожество обозначается , как во , где }п*п - класс действительных матриц размерности 1п « п]. Сласс матриц И € В11*11 для которых К(М) эквивалентно всему пространству Ип обозначим через 0 ; о с <зо< Идентификации этих двух основных классов матриц ЛЗД посвящена основная касса литературы ю линейной дополнительности. Ясно , что задача ЛЗД имеет решение, если вектор правых частей д принадлежит хотя бы одному ко-1усу. Если объединение всех конусов покрывает все пространство, го задача имеет решение при любом ^

1^:= и ров С ( 1=1 ,г.....г

1

Данное условие вовсе не означает , что решение единственно ups данном q , так как вектор q может принадлежать одновременно нескольким конусам . Число таких конусов, которым одновременно -принадлежит вектор правых векторов q определяет число фактических решений данной задачи «которое в свою очередь не может быть больше »чем 2П. Ключевая идея определения класса Q-матриц принадлежит D.Gale . Решение является ли матрица Ii Q-матрицей (MeQ ) эквивалентно решению является ли разность R" \ К(М) пустой или нет. Если эта разность есть пустое множество, то М € Q, иначе говоря, не существует такого вектора q е Rn , который не покрывался хотя бы одним из конусов дополнения.

Класс матриц Ы е Rnxn для которых решение ЛЗД (M,q) сущей вует и единственное при любом q е Rn есть класс Р-матриц .

Определение . Квадратная матрица называется Р-матрицей, если все главные миноры положительные.

Параграф 1.2 посвящён описанию семейства задач линейной дополнительности, к которому относится помимо классической задачи (1.1) три новых подзадачи :

- вторичная задача линейной дополнительности ( second linear complementarity problem) вида :

w = q + Hz 4- Nu О = p + Rz + Su а > О , w & О , zTw=0 ,

-а> < u < -и» , 2,w € I?1 , p.u e Rm .

- минимальная задана линейной дополнительности (minlniuin linear complementarity problem) вида :

pTz + qTw + rTu => min

Pz + Qw ¥ Ru = b a i 0 , w ^ 0 , a Tw = 0 M f Rn . b e f , u i R1,

- вторичная минимальная задача линейной дополнительности (second minimum linear complementarity problem ) вида :

pT2 +- qTw + rTu =» min Pz + Qw + Ru = b

Z > 0 , -oo<W<+oo , , i=i,2,...,n

z,w e Rn , u ( R1 , b e if .

Показано,что большое число задач математического программирования могут быть сведены к одной из задач данного семейства. Такими задачами являются : линейное и квадратичное программирования (выпуклое, невыпуклое, псевдовыпуклое), линейные вариационные неравенства, билинейное программирование, теория игр, булевое целочисленное программирование, задача фиксированных пропорций, программирование абсолютного значения, сепара-бельное программирование.

Показано, что меаду задачами данного семейства существует внутренняя связь : так, например, вторичная задача линейной дополнительности при определённых условиях может быть сведена к за-

даче (1.1) . Многое из того , что развито для классической задачи (1,1) в той или иной мере пожег быть применено и для задач денного семейства.

Параграф 1.3 посвящбн подробному изложению классического алгоритма Лемке, несмотря на то, что уже имеется литература по данному вопросу (см. Г.Реклейтис и др. "Оптимизация в технике") Это связано с тем, что во второй главе предлагается некоторая модификация данного алгоритма .

Глава 2 посвящена описанию двух алгоритмов, созданных для нахождения всех возможных решений линейных задач дополнительности . Это модифицированный алгоритм Ленке и алгоритм рационального перебора вершин. Область применения первого из них ограничена условием связности множества решений, которое заключается в следующем. Число возможных решений ЛЗД равно 2П, где п-размеряость задачи. Расположим все решения в вершинах п-мер-ного гиперкуба и тогда, условие связности сводится к необходимости расположения решений в смежных вершинах. Алгоритм рационального перебора свободен от каких-либо условий, что делает его универсальным.

В параграфе 2.1 приведена схема модифицированного алгоритма Лемке. Как известно, классический алгоритм Лемке предназначен для нахождения одного из возможных решений. Разработанный в диссертации модифицированный алгоритм Лемке позволяет найти все решения линейных задач дополнительности при условии связности множества решений. Вкратце идея модификации состоит в следующем. После успешного вывода искусственной переменной алгоритм Лемке завершает работу с найденным допустимым решением. Предлагаемый

алгоритм использует данное решение в качестве стартового для анализа смежных вершин. Для этого выбирается любой внебазисный столбец в качестве ведущего, применяется правило минимального отношения с целью определения переменной, выводимой из базиса. Если правило минимального отношения невозможно применить, т.к. все элементы ведущего столбца неположительные, то выбирается любой другой из оставшихся внебазисных столбцов. Если после перебора всех II внебазисных столбцов не удалось найти столбца с положительными элементами, то считается, что данное решение изолированное , иначе говоря смежные вершины не содержат альтернативных решений. Данное условие является лишь необходимым, но не достаточным. Достаточным является условие по которому вводимая и выводимая переменные должны образовывать взаимодополнительную пару.

Параграф 2.2 посвяцён обсуждению алгоритма рационального перебора вершин. Известно, что комбинаторные задачи можно решать за счёт простого перебора вершин. Не менее очевидно, что так можно решать лишь задачи малой размерности. Не исключение составляют и задачи линейной дополнительности, т.к. они относятся к классу МР-полных задач. Принципиально новым в предлагаемом алгоритме является его способность анализировать структуру . задачи дополнительности. Анализ позволяет уменьшить трудоёмкость процедуры поиска, заведомо исключая из рассмотрения вершины без решений.

Идея подхода заключается в последовательном отделении базисных и внебазисных переменных, что и является решением задачи. Для уменьшения трудоёмкости проблемы делается первоначальный

анализ 2п столбцов патрицы ограничений. Этот анализ призван ответить на вопрос : все ли столбцы способны принять участие в формировании базиса. Если да, то задача сразу становится трудоёмкой. Условимся оценивать трудоёкость задачи числом вершин, необходимых для рассмотрения. Если найдутся такие столбцы, которые можно заведомо исключить из рассмотрения, то тем самым задача существенно упрощается. Исходная трудоёмкость составляет 2П вершин, в то время, как для задачи с исключёнными столбцами трудоёмкость снижается до 2п-а вершин, где а - число исключённых столбцов.

6 главе 3 проведено исследование двух моделей экономики : модели чистого обмена и модели экономики с производством. Основной вопрос данного исследования - условия существования равновесия по Вальрасу. Состояние экономического равновесия характеризуется тем, что ни один из экономических агентов не заинтересован в его изменении с помощью средств , которыми он располагает. Обширный и важный класс составляют модели , в которых под состоянием экономического агента понимается выбираемый им вектор затрат ( потребление ) и выпуска продуктов , под согласованностью имеется в виду выполнение материальных и финансовых балансов для системы в целом , а в качестве инструмента согласования выступают цены благ. Будем их называть моделями ценового равновесия. Для построения модели ценового равновесия необходимо задать правило формирования и распределения доходов. Согласно бюджетному ограничению расходы участника не должны превосходить его доходов, складывающихся из оплаты ресурсов , которыми он располагает. Данная глава посвящена следующей задаче : ис-

следовать модель равновесия при конкретной функции полезности, а именно функции Нобба- Дугласа . Показано, что в результате исследования получены линейные соотношения , которые легко интерпретируются. Параграф 3.1 посвящён исследование модели чистого обмена, с функцией полезности типа Кобба- Дугласа. Параграф 3.2 посвящён более общей модели, которая включает в себя производство. Для этих моделей подучены условия достаточного типа, выполнение которых гарантирует существование равновесного вектора цен. В рассмотренных моделях вопрос существования равновесного вектора цен сведён к вопросу о разложимости некоторой матрицы .

ОСНОВНЫЕ РЕЗУЛЬТАТЫ ДИССЕРТАЦИИ

1. Предложена модификация классического алгоритма Лемке, позволяющая находить все смежные решения. Описаны границы возможных применений данного алгоритма.

2. Разработан новый алгоритм, позволяющий находить все решения линейных задач дополнительности вне зависимости типов матриц, что говорит о его универсальности. Поведение алгоритма более оптимальное, чем полный перебор, так как алгоритм умеет учитывать структуру задачи.

3. Алгоритм реализован на IBM PC и проверен на многочисленных тестовых примерах.

4. Проведено исследование проблемы существования равновесного вектора цен в двух моделях экономики.

СПИСОК РАбОТ ПО таш ДИССЕРТАЦИИ

1. Оляабаев Б.Г., Мустафина Т.Е. Задачи линейной дополнительности и экономичное равновесие // Тез. 2 Респ.конфер. по автоматизации науч.исслед. , Алма-Ата, 1938 г.

2.Оляабаев Б. Т. Задачи дополнительности и экономическое равновесие // сб."Анализ развития социально-экономических систем на основе моделирования" - М.:МИНХ,1989 г. З.Олжабаев Б.Т. К вопросу о существовании равновесия в моделях экономики // сб. "Анализ развития социально-экономических систем на основе моделирования" - М.:ШНХ,1ЭЭ1 г. Д.Олявбаев В. Т.,Данильченко Т.Н. Экономическое равновесие и задачи линейной дополнительности //препринт ВЦ АН СССР ,1991 г.