Конечные алгоритмы отыскания равновесия в линейных экономических моделях тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

АКАДЕМИЯ МУК СССР СИБИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

Специализированный сонет Д 002.23,03

На нравах руне лиси

УДИ 513,853.0 1 519,805. ''

ВМЫРЕВ ВИДИМ ИВАНОВИЧ

КОНЕЧНЫЕ АЛГОРИТМ отишш РПВИОВКСИЯ 4 В ЛИ11ЕИНИХ ЭКОНОМИЧЕСКИХ НОДШХ

01.01.09 - математическая кибернетика

Автореферат

диссертации на- соисканиеучимой степени доктора' физики математических наук

"оиосибирск 1091

Работа выполнена в Институте математики СО АН СССР

Официальные оппоненты - докт,ор физл.ко-аатематичвских наук,

ирс^аас-ор Л.И.Ёрек^н

доктор физико-математических наук, профессор В.Б.Булатов

доктор физико-математических наук, профессор ОД.Жэфяров

Ведущее научное учреждение - Вычислительный центр АН СССР

Защита состоится " %".Ц-Щ-о&Лик 1992г. в Iв часов 1 васедании Специализированного совета Д 002.23.03 при Институте математики Сибирского отделония АН СССР по адресу: г. Новосибирск-Университетский проспект, 4

С диссертацией мокно ознакомиться-в библиотеке Института математики СО АН СССР.

Автореферат разослан " 13 " ШАСО^аА. 1591г.

Учены'! секретарь Специализированного совета доктор физ.-мат.наук

^ „ А.В.Косточка

,.. I. (!, |й !

Диссертация посвящала ¿опросам разработки конечных алгоритмов о?нс:сзикл равновесных цен м отвечающих им равновесных состояш"; I? ра&лкчякх экономических моделях, 2 основу которых голодна лкнейлея модель пйвеиа.

Проблема чдслепного отксхакш состояний экономического раг-новескя традиционно занимает значительное место в исследованиях: по катеиагячеокой глоногляке. Первоначально изучение этой проблеш велось в рампах вопроса-об устойчивости процесса регулирования.цек через о^ображеше избыточного спросе, что приводило к яссяедовэкяю точек покоя скогеш обнкио-венгшх дадЛЗерсншсль^х уравнений. Яга тематика разрабатывалась Вельр сом еа;е н проектом столетии, а в последствия продолжена Хаясом, Саг/у ¡шло.чом, Зрроу, Турвицек, Удзавой л другими лзЕестижЕ учении»:.

Другое лаправледа« в о&ярсгл численного откскаюзя .рав-■ новесылс состояний связано с вопросом нахождения неподвлЕИш: точек ртобрзкеш!;; с;ет:л&кса цэн в себя я базируется пз кои-сгрукцки ошзлацкамапк •разбяедаЗ (восхедя^еЯ' к .известной лемме Ша ераера) й процедуре построения нвБОзрацающяхся траекторий, впервые предположенной празендтельно к бимагрнчвым дарам Лемке и.Хауеонш-я обобщенной впоследствии для задач ■ линзйкоЗ ко!лпле?.:ектзрности Лемке.

Первый алгоритм такого типа для отыскания.неподвижных точек бил предложен Скарфом, я впоследствии это направление интенсивно развивалось Куиок, Ивесом, Ме^рилоиДоанг-Туеи,

л

Сегалом, Шелли, Толдом, Тельманом я многими другими ясследо--вателямя, - '

Предлагаемая работа иосшцеиа яеследоЕашш конечных процедур огысканяа состояний равновесия а линейных эвонсыи-/ческих моделях.

Для случал линейной модели обмена с фиксированными бюджетами задача откокакяя равновесия была сведена Айзенбергом х. задаче математического. программирования о линейными огра~_ нлченяямя, однако конечных процедур её решения предложено не било. Конечный алгоритм этой модели с переменными были пред-.гожек Ивесоы на основе алгоритма Лег/ке применительно к специальной задаче линейной ждаядементарности 5 пространстве размерности пт + т+-п . , где т - число участников а И - число продуктов модели.

В предлагаемых процедурах все рассмотрения ведутся в симплексе цен. Организационно эти процедуры заключаются в от-слекинаняя'траектории "соседках" состояний я являются дальнейшим развитием подхода Яемке-1аусока. С другой Стороны, их условно можно назвах-ь симплексными процедух>аш, ибо они являются в определенном смысле аналогами известного сяшлекс--ыегода из теория линейного программирования. Подобно току, как в симплекс-методе на каздоы шаге процесса анализируется допустюе решеиае, поровдашое определенкой структурой базиса, в рвссматх'йнаемпх процедурах осуществляется последовательный аналяо различных предполагаемых структур равновесного реиендя. - .. '

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

(точс-чно-гочечпш,;) отображением, согласованные .с- Екй^йрлгЛ хркянгуляцие?;, продиагаега-е процедуры эсиодош

том-факте, что при .эпализг линейных медалей еотест»ен:ши образом возникает точэчно-шояеотвекяиа отображения особого гяпа, которые условно иошго .именовать куоочяо-лосгоянкими. 1Сзвдое такое огоСражелие порождается двумя яолявдральныкя комплексами,находтоитеся в отношения двойственности.

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

В работе излагаются аффективные конечные алгоритмы точного отыскания неподвикных точек рассматриваемых отображений, пе аспользующие Ьгжротоимацря точечко-точепшми отображениями, а бззяруитсся но келользевашш полиэдральной струк-турк исходного, отображения. Такой подход позволял не только подучить эффективные алгоритмы отыскания ■равновесия в линейной мод оля ойюпа к раздач пых её модификациях, но в го не вреул в значительной степени дродешл качественную сторону исследушого Еспрооа. Капри;/,ер, для кодела обмена это выражается г выявлении'определенного свойства монотонности, ко-;ч • „ - ^

тороеЧязяно сформулировать оледукэдям образом: получающиеся задача полиэдральной кошътеыектарнооги большей частью локально устроеки как задачи дяисйной ком: ;еыенгарйостя с по-яокит&'шшш гдавшлк минорами матрида ограничений. •

Осковнке.результаты диссертация кратко мотао охаракте- " | ( ризо'вать следующим образом: . ! .• ,,

1) Установлена потиидалыюсть'кусочно-постоятшх моко-гошшх отображений я-предлокеш; з$фскхи&ннс алгоритмы, откс- .... «шаг '¡еподапгаяЬс гочек.увгагё окобракеияй;-' ;

2) Предложен подход- к йязлазу лляеКкнх акояо\щ-' . ,.

ческкх кодеяеЗ, опирающийся ка рассмотрена© возникающей за-;-дата шышэдралноИ ксшашенгарности;

3) Для задач, яякейнок я полкадраяьной кокялекенгарнсс-полупены признаке разрешимости и предложены эффективнее

ал горл тии р еп;еш;я;

4) Предложены конечные глгорятмн симплексного тхпа для отыскания равновесных соегоялкй з различных вариантах лакей-ных экономических моделей (модели обмена и кооперация как с фякслровакншй, тэк у. с переданными бюджетами; модель обмена с огранячен/кми сверху на лктенсягносту., модель с ограничения:.® сверху финансового типа» вариант линейной кодеяя Эрроу-Дебре),

Объем дясеергацкн 279 страниц, библиография содержи" 79 надуенонанщ".

Изложение рсаблто на тря тлавн. В первой главе раесмаг--рдаквтея куесчяо-пестоляяне огсбраиешш в РГ . Какдое такое отображение по определению представляет собой пару ( сО ; Р ) где сО - конечный полиэдральный комплекс, об-разоЕаяннй зсезоклоЕкищ! гранкма выпуклых многогранных множеств С} , Сё] , лркммхзгацах друг к другу правильным образом я х:окрь."ва:ощчх все пространство, а V - много значков отображение, определяемое формулой "

ГО«)« С.| .-¿ёОл , ¿Л } (I)

ери каданнет точках ' , 1С I .

Кусочнонкюгоянноо отображение (<-<3>ь) дменуется мо-штокшл, если ■

а лскально-мрясгочкш, если пто сесйстхо заполняется для

о

•У к у , лринадогсяшишх соседом множествам , ¿б/ ,

т.е. имеющих общую (п-;{) - мерную грань.

Основиш результатом § I является следующее .утверждение:

Георека. Веяное хуеочно-лоетояшюе локально-монотонное отображение (со , Р" _) потенциально: существует полиэдральная гкнумая функция ■}■ такая, что многозначное отображение [- . совпадает с порождаемым.;функцией субдифферен-■ циэльиьгм отображением 1)} : а -—!> ■

Одного лишь требования монотонности отображения, как известно, недостаточно для его потенциальности (требуется более сильное требование цпгалческой монотонности я максимальности). Приведется результат означает, что для кусочно--ностоянного отображения уже локальная монотонность обеспечивает его потенциальность.' ;.

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

в;:альна. " .....*

Свойство зотенцияльяоети' позволяет- сбоснсьыЕзть тивнне ¡процедури'. отоскопия неподвякннх точек как собственно -монотонных куссчно-гоогоянныхотстранений, так и отображений, для которнх в, (I) выполняетсянеравенство противополоатого знака. Тэте отображения именуются в работе убшамцикд, в • отличие от -собственно монотонных, женуа.мх юзргсгавдйкя.

3 теораце 3 у 2 доказывается, что ддя отыскания невод-. вичю:: точка возрестЕгяцего' кусочио-лосгоянного отображения применима процедура гтетода итервцкй, ояисшшемая соотповени-' е:.; <~ Ь С2") й состоящая, в тог,., что по имеющему-

ся теку,у прблзхеют в качестве. следующего пргблк-

я18я.чя ■ принимается «табая точка лз ¡-(в*)

Показывается такке, чг-о-среди точек •Х'' , ¿(¿I , свегда существуют неподшаЛлыс то?:::! отображения Г ,м для кх отменами можно воспользоваться процедурой "соседней вершины": если для ям<зщихса на очередном шаге процесса мнояо--стеа 'а точки У.1 имеем- л'" 4 го ссущеот-

/—ч

вляется переход к "соседнему" множеству, ^¿j , такому что несущая плоскость клетки. .0.1 отделяет от!*},; .

Обоснование »ю2 процедуры основано на монотонном возрастания значения .функции ь текущей

точке . л"1 , где - функция, .созрякекная к функция

, являющейся потенциальной для отображения Для убывающих оюбракеявй доказывается теорема 2, утверждающая. что для'того, чтобы точка Л была неподвижной гонкой такого отображения Сг , необходимо я достаточно', чгсоы она являлась точкой (безусловного) минимума выпуклой

функций 4-' гле ~ потенциальная

функция возрастающего отображения \-~-Gr

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

В § 3 гл. I полученные результаты переносятся ка класс многозначных, отображений-, заданных на внутренности симплекса 6Г-—ре. | р] — 1 ^ л'.именуемых логврифми-

чесюы.зднотоЕКкмй. . '

Тгкяе'отображения естесгЕеш»м образом гозивказот при ' лесгроенки' апгор^жов' хля. лшейнадг моделей обмена с• ©дксг-ровазтт.» б:гджетзми, кс?:ор:;е ргссма:рягак<тсз 'и х-л.Ш. '.

•СогйрзОличеокя-коноююше нозрг.сггвиие оюбрег.одая по.

определении характеризуется первенством

(¿п р - ^ ^ , ЬТр; - ? ^.гб» (з)

а убнвахвде - неравенство1« протакополслаюго 'знака.

Для определения кусочно-посгояиннх логармфмячеспгй-то-нотошшх отображений на б>° вводятся операции линейного пространства по следуг.щей схеме. Каждая точка Р£ 6° рассматривается кэк представитель сс-гветогруадего ей луча р 4 х'в | .X ~ Лр , X > О } .На мноЕзетле

таких лучей определяв опеп-шлю сложения, кошшея под сугдаой Р Ф Р' дъух лучей . р\ Р"с луч Ре , порождаемый точкой р с яоордапатзмк • р. «г - » » ■

где Р/Ч/3/ - уоордаяйгн' «счек Р' , р"е Р" .

Под произведением ЬрР элемента р£ сР нз вещественно е "чиело Т понимается луч 6?£ порождаемый точкой ^ с координатами .; ...

, • • ..■ ъ -- />; .

где р. - коордиаать* какой-либо, точки' Р<=Р .'• Так .как мекду элементами мисаеств" б" . к . .;' Имеется взаимно-од-нозначйое соответствие, то введенные операции-в ^ . пере, носятся на 45° , которое таким образом установятся линей- • . нны пространством . .-В нем ряссмат^яваетея описанная

выше конструкция кусочно-достоянного отобракения, однако с тем отличиемУ что .выпуклая оболочка/Ё. (I) берется по-преж-. нему в смысле пространства : . Если'для вомикатацего тахям'образом точечго-мюкествекногс отображения вшолняэт-ся. условие (3), .то-такое отобраяенио, именуется кусочяо-по-

огояян«м логг?р/^фтллпс.ки-ь;онотоннш ■^'Б0зрастг1М;!Ш::б10йрв&ениегА . ; •I л полок::тельного ?екгора. . р^ врй1шзев!гпя' : *:■•„■

\ .. ... е^рп).

Теорема I. Логарифмически - монотонное возрастающее кусочно-посгоянное.отображение потенциально в,следующем смысле: существует выпуклая полиэдральная функция

такая, что доя любого р^б" выполняется

Эта связь имеет место и для уо'квамщх отображений с тек тем лишь отлячяем, что ^ в втом случае является вогнутой функций к по определению считается --Эс/ 0 выпуклой . -Для функции ^ определяемой формулой ] -гт ) , доказывается Теорема 3, Логарифмически монотонное убывающее кусочно--постоядное отобракеняе Р" . клест в б° в.. точности одну неподЕКкнук точку, которая является точкой максимума строго вогнутей функции у . , порождаемой отображением

Г .

На основе лотенцяадъностя доказывается также Теопема 4. Для логаркфилзчесь'и-монотонксго возрастающего куссчко-псетояншго отображения прл любом векторе рк'г!" из множества" ятюцесс заканчивается через конечное число шагов получением неподвижной точке отобраке-ния. •

Вторая глава работы состоят из трех частей. Здесь рассматриваются кусочяо-постоянние отображения более общего ткпа, поровдаеше задачей полиэдральной косплэыентарностя. Речь идет об отыскании нелодв^кной точки отображения Р* , задаваемого даумя канечшзд замкнутыми полиэдральными комплексами и £ — ЛЕИг.^геГ • нах°ДЯ]151~ шея в отношения двойственности:.

I) есля . .0 - собственная грань для ,то

соссгвек-тя грань для > £ ;

2; сЬ.т £11 ¿1т ¿НИс ~ п , '/¿с/.

э

При этом клетки не пересекаются по относительно "внут-

ренним точкам и заполняет некоторый вилуклш; мнох. гражшк

П . Но относительно;; внутренности наждо!: клетки Еияолняегся РТ-О JhZ i

Собственно твшд отображением посвящается часть П второй главы. В j I это"; части приводятся общая схема алгоритма для отыскания нелсдютных точек описанных отоСраг.сир.И в предположении, что выполняется условие- "общности подогашя": аффишне носители-клеток к2г. л алгебраически вза-

имно дополгиют друг друга и, тек саиш, всегда пересекаются в един сгвспшй точке. Эта схема состоит в следующем.

Кз к -ом sars процесса имеется пара о'лзечаюакх друг

другу клеток .slic ed , ^zli Ч и точек y-'e^ll^ , У К £ I3EZ < ^ . Эпсед&литз однйзяачно точку Zк , являющуюся г.- ресечевдем £®&якнлс носителей меток и

Г—"'.. \ рассматриваем зависящие от вещее та много пара*--

метра ■£ точки

¿¡it)-г(4)

Параметр' t меняется от О при совладении

условий: xitjcQ-U -, ^(t)S^Eli^ а при увеличении t еще и услоеия ~t i ,'Еоли при этом £ достигает некоторого значения i , к дальнейшее изменение

"£ . лжи тируется, например, условием 'Jcffle&i , то в кечесгсе яргшмется грань клетки , со-

дертаг-яя точку x(tH) . л jT^k) „ .

Слун" когдз изменение t джотар^етея условием

у (t) 6 ¡ц , пь!сл'»гйч;ц. В срсдполотгсяял кева-

розденносгя, когда |с/с—с{йп{«/направление лзме-/

нения параметра X. на ковдоы лаге однозначно определено яо-некоторому правилу предысторией процесса, а на начальном шаге - задается вместо с точками £2-1о , ^"е:.г-~Т/о .

В '3 2 выделяется югасс задач, для яогоркх описанная схема позволяет отыскивать неиодвляные точки. Пусть Н я - конические составлявшие в разложении соответственно киогограннкх мнокеств и в сумму ограниченного многогранника к полиэдрального конуса с вергканой в ну- . ле, а - конус касательных направлений к .0. в относительно внутренних точках метки

Теорема. Бела Н ~ гелесен я для "любой клетки .Г} £ , лекащей па границе многогранника л! соответствующие конусы I а ^ " удовлетворяют условию

то задача полиэдральной комплемеигарностя разрешима.

Б § 3 ч.П одксивается класс задач, характеризующихся ослабленным ^требованием монотонности.

Определение, Многозначное отображение Ь* будем называть слабо убывающая, есля для любой пары различных точек Л-' я ^ существует вектор „ Ь ф О , что

- (Ь,.ч-#)>0 > 15)'

■ Для слабо убнваювдк отображений доказывается

Теорема 2. Для порокдаемого задачей полиэдральной комп~ лемеитарностл многозначного отображения Р задача об отысканий такого X что л; <£ ) однозначно разрешила лрл любой ■ тогда я только тогда, когда отображение является слабо убивающим.

п.

Б 5 4 гл.П приводится кодификация процесса, позволяв- ] щая ослабить условно "обучаем положения".

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

I

у^ , удорлеизорякжкх условиям

и

? V (6)

> И, ...,20 {7)

■<8)

где А* ^ у - заданные лекторы, г А

( - ортн в /3" ).

Определение. Множество 15 2,..-/Лпу назнва-

' ется кокшмийкгарнжл, если из каадей. пары в него

. входит ровно один оломеяг. , . . ,

Рассмотрение задачи ведется и лрзднолокекли, что для любого •комплементарного ЗЬ а любого нетривиального набора ' неотрицательных у^ , j £ ¿Яч , выполняется

Л* X: ■■+€>' ■ О)

Подход, подокеннуй в основу рассмотрений, базируется на сведении допроса к задаче отыскания прообраза некоторой фиксированной точки при непрерывном отображении евклидовой сферы,в себя. 0-го дзет возможность подключить к анализу задачи аппарат топологии л воспользоваться некоторыми язвесг-нцмн утверждения].«! из этой области (равенство степеней у гомотопных отобрахс-ккй, теорема Порсука о ьзчегностя степени нечеткого отобраяенйя). Гаяой гчгдрд позволяет получить но-

ъые уттериде-чвя о разревшлостя задачи. Fía этом яутя естественный образоа возникает и новая верснд алгоритма дополня-тельностя, расаирявдая класс реваешпс задач по сравкенш с изкеспМ'Л алгорятмо;.; Лемке.

Построение упомянутого непрерывного отображения сферы ■ б себя описывается е § 2 ч,1 гл.П и состоят в следующем. В кнокестве ортов | qí 3 .. _ д <~п введем нуме-

рацию о? I до 2¡4 , обозначая йх о''ьt с eoto-

деаяем правила: для каздсй л яри сдан яз ортов

получает" сбозкаченне , 's другой - c¿n'r* ,

. Какдоау хгамслеяакгоршк/у гаокесгву ¿Й со-позгширютои ЯЕ0 конуса; Ц f cc/se f с- } я

./£ (<>б) - WiejA'f . Послз оюго однозначно стро-

ятся ?уосчно-лкяс!'тое отобргхснцс Ь , пессшддае' коку-ск R е соодетоздукиц* »л ко:va- íAv" . Иакоме?.

rj'ecyébOü oroSpavenpe сфери v себя определяемся как p(x)ss

~ Fí*-)/¡IR*) a

А

Отдочде os нуля втепека огобрикенкя • является дост&точдкм дте разрсзшосхь задачг, коаю:еион?ар1!ОСХ,я (6-8) при лобоа . Досг'аточаам признаком го кого рода яосвяден

5 3, Приведем кеногзрыа es док&зшаекш: уиэсрэдегиШ.

Теорека I. Ь'ам sea гдавпне шпоря-матрацы г\ нево-логм.тсльии я для некоторого шояесгва с/. С ^ i ,2 ,... ¿¡О £ выполняется

то задача лол:пле~*ептарност'я с такой матрицей А разрешима ПРИ JJÍ)6oi.i Oy .

С-дгсг - мзтргэда из столбцов .... А .

г- ^v.a -в gne-ifcHroi» CUj ^ j ¿' cL-

Теорема ?.. Если гее диагональные элексагн Ccjj иотря-;ы Д отрицательны, и при всех j'-í,Л ,_-ш:олняется

о при любом задачи комгогементарноста жест не кеиее п -i решений.

?соре.>а 3. Пусть ллч. какого c¿£-¡ ¿f-, Л î такого, го chit Act el я любого вектора ST^O выполняется

А<м ^ -ь'О . Гели супесяеуег, по кеньуе5 :<:ере, дэо тряцат'мьпьх, дкагояалгккле олекекга догршг Д , is хотя и в одно',: кз соогветс?зугх!,к:с столбцов кзтрзпн ow:/.:mc л с:'от:: неохгдцзгздхкя, то efefj Р -I

jj 5 4 лзляг^е^ся оог-ац схй/п сйсрпчесхого вэ^гпнго ai-гсгиле:¡гнтаргтостл. 'Í5BOctfl:M л весьма п'^Т'^кт'^нн" ят-ср'Л": Jí>".;i-cr= (bsj;p'/e:c;ï из шдпугеп;:.;; исходно:!' гадачл в ••лее с праго:; частно ^-ÖsS ,где&-

еи;естп<зшп:Г1 Liaprwetp, a ¿¿sidy.. », -í) ■ Для некоторых лусо-'З задач -тог алгоритм, однако, не даег решеная. ¡Триере: л у.ччого :-:ласса являются зздс.чя с отрицательной дяэго-алыо в тэрзце ограничений» о которых на речь в теореме 2. предлагаемом взрканте алгоритма ксшлеадбнторносхя расск-класса pt-naiffü« задг->ч доогягзегоя за счет иной папа-зтрльяцвч ярпг-сЗ чяот'л: <?„(i) <j -i- pcoi't .

3 заключительно« § 5 Г гл. И приводится одна из boskos-алгоритмических конкреэтгацяЛ общей схсмы сс.ерлческого тгорятка я доказывается, э чьоткоегя.

Теорема 8. Есля ' р— ->2. и вгшоетяется яредпояояеипе ггарояденноетя, то в усяорялх теореш 2 сферически? алго-îTw дает решегше задкчй чокадлле'.гсирпости.

ПредюяоЕОййе кескрсЕ^ечьости состою? в том. чтч «сд:»

.р.

m ко*ш.^*«з!!?8ркого «.•»cg-ocri!» ap¡ w >:vsojxa /л»-

с.-.- <|(£) в '¿. (&>") , то г представлении-

^ АЦ = а[€) (ю)

резвв л;;!:;ь одни из коофГицвслтоб М: , ыоь-ет <5иг-ь равен

а

В третье* чисто гл. П р8сс»двтраз8етоа специальная до-Нйхиаг. задача доиолкягелшо«?» в , порода емая чгюгяч-

кол уггорядочеимотьк яереыетакх и некоторой нерезлосадоб не-стгчида-гааы'.оГ; пзтр;п;еп. Задача такого йпа возникает при построении алгоритмов егкекпния рзвновесия в лине/ной коде-як обтт, излагаемого в гл. К!. Постаноьке задачи такова. Пусть имеется граф Г' с ыпокеетгоч вержн

кпогество:л дуг С7 =-" 'А - ^ • • ^ р.явлдацийсн

дерево;,;. Крокз тс го, зздииы полоттедькш вектор —} - ■ л квадратная матрица — ] и у] размером ЛхП - неотрицательная, перг-азота» вя л при всех

Пусть ^о!4 - строк;: пто? матрицу. Расскатркаавтся д*е скс-гемк ;.т.не1:;\к;'. однородны"/, нсренснстн:

где к^Ц означает, что цстъ дуг, сседадявуая верилнк'К к нз-содержи;: дуги ■ ■ ,'..■■

ТреСуется найти кекулеьс! вектор реР^ , решающ;;: (11-12) а удовлетворявший сясгег:е уелогиЗ ко„;ялемецтбрности

Показывается, что' такая задача при сделокних предполо-, ениях о ^ и D всегда разрешила, и приток единственны образог,: (с точностью до положительного мнокктедя). Сли-ьгняется алгоритм решения являющийся конкретизацно"; обде:"' хеш алгоритма пол•эдрклъяой комплементарности, ззлоъекяоК § I гл. П.

. 3 гл. Ill рассматриваются алгоритмы отыскания состоянил йЕНовесия в различных вариантах линейно? экономической ко-еля обмена. Наряду с классическим вариантом собственно мо-ели обмена рассматривается модель, условно именуемая "но-елыо кооперации" л отличающаяся тем, что-максимизация целе-их функций участников модели заменена их мишмизац'.-сй (с охранением требования неотрицательности коэффициентов целе-мх функций). Обе модели рассматриваются как в обще?,: случае Э§ 5-9), так и при условии постоянства бюджетов участников J 3). В s 10 рассматривается модель обмена с дополнятельны-и ограничениями сверху на переменные, а в § 4 - модель об-ена с фиксированными бюдкетами и ограничениям сверху юп-знсозого типа. За*слючигельны2 § II посвящен специальной мо-sли обмена с производством типа Эрроу-Дебре, Для этой моде-я такне приводится конечной алгоритм отыскания состояния ЗЕНовесия.

Бее рассмотрения основываются на специальных полкэдраль-jx разбиениях симллексоЕ цен, порондаеыкх моделью. Быязля-гся принципиальное качественное различие между рассматривавши вариантами моделей: модели с фиксированными бюджетами эройдаюг потенциальные дусочко-лосгояннке отображения, рас-лэтривавшиеся в § 3 гл.1, а при исследовании моделей, с пе-?ыеннкми бюджетами возникает аналог общей задача полнадралъ-м" коглплементаряоеги, о котором una речь в ч.П.гл.Л. При

эхо:.; собственно модели обмена отвечают убывающие (слабо убц "еевч/'С в случае переменных бюджетов) кусочко-постояннке ого бро&шяг, а здд<Ш| кооперации - возрастающие (слабо возрас-тагдре).

К дзлькейзж обобщениям задач;; полиэдрально? кшглег.:еп тарвости крлсодат рзсшагрлваоажй вариант подели Эрроу-Дебр Приведен сб'дую схему подхода применительно к модели об :лека, которая '"слагается в §5 1,2. Пусть в модели ш&е-ся т участников у. П товароз. Обозначим 1. • ^171 $ , | - ] ... . Пусть с\ с/'с - фиксированные векторы хгрокгерззутою учесгадва ¿6 Г: .с1 задает его функцию предпочтения (с, а с1с уке?квает даегацаеса у участника ззпасы товаров. При заданном векторе цен —

— ^ ре / ^Уучяогик <■ £ / реиает задачу

— /пезлг / (14)

Требуется отыскать такой вектор цен р - р , чтобы средг. •пгктоьаЕх рекша? задач учг-езнгков• иашгксь такае я* , что при —выполняется условие баланса

«Л^ 21Г^/£ це)

^ /б-/" .

Вектор р и набор /х^^падают состояние равновесия мо-

ДйЛК.

В предяачокадшг с'->£? у, - / ',- ^,

сятеы с расскетриваел-ой кодс-чь» сяеду;хчум транспортную задачу ' -

7 1 I _( ^ Л С — (

У , £¿¡ </1 С- , - ткх ; , с?)

JE2 s ¿el, (ic)

-'J ^ ?} . J£ J. » . (13)

кц&О 3 ¿el je], (20)

Обозначим. через ,jêr совокупность "дво.чственно-дапуст»'ш: базисных шокесгв этой зядечи.я всевозможных их поданохеств, обладающие свойством i - накриваемостя: для мно-

жество {jéJl ({>]) лри всех се/

Теперь свях.см с каждым ÛbC^êr пару множеств: JET^e^O • Множество J^C^O- &то мнокество таких ре<5 , при которых совместна сястека.(18-20) при дополнительном требовании -

Sij^O > .. (2D

Множество Я7 задается формулой

(22)

Теорема I. Дня того, чтобы вектор цен рСб° был равновесным, необходимо я достаточно, чтобы пря некотором & ей- выполнялось р £ .Q л .

В предположения, что-выполняется условие двойственной невнройденностд транспортной задачи (17-20) л показывается, что множества Q СЛ) , , образуют

разбиение симплекса С5 , г- совокупность мноаестЕ JET(oS_) ,

(Pè С - разбяенае его внутренности Sa . При это:л множества Q. 0® ) - и являются многогранными я

следует Qf^) cQfa) }

Кроме того, c/'lm i 1 -/при любом

Тек: самим многогрйшке множества

при образуют два полиэдральных комплекса, дво5-,

с те синих друг другу, s отекание равновесного вектора цен • модели сводится г. задаче полиэдральной коыплементарностд: нзП-га ЗЬсУЬ- , для которого

Эта задача является аналогом задачи, рассмотрение/ в ч.П. гл.П.

Приведенные построения имеют место и для Модели.кооперация, - нунио ли'лъ зькенигь Л'&Х на miп в (14) и (£2), Модели с фикс кроваьниш бюдгетгмк характеризуются тем, что с, 7до <?-.С£, ■ , .о Л;-><2 и ,

'Реализация описанного подхода для таких .моделей рассматривается в § 3. Показънаегся, что в втом случае, если ввести многозначное отображение , ^Р. : формулой

где К&) - относительная внутренность множества

.. до да::: модели кооперации отображение F— удовлетворяет неравенств? (ЗУ, а для модели.обмена - неравенству псотйнополоншого ЗНЭГа. сто ПОЗЬОЛКеГ НОСЛОЛЬЗОЕОТЬ-ся резульгетамл § 3 гл.1 и получить конечные процедура для отыскания неяодедашх1 точек огобр&кенпя , когорке и ' дают равновесные гв«?орь* цен.

Теорема 3. Для модели кооперации с фиксированиями йод-жетазд ясксме'/ равновесный вектор цен может быть получен за конечное ччело шагов процедуройллетода.-итераций, опи^ввее-;/о£. соотноЕе. jew " Я^'^р*) • ■'

. Дчя модели обмена с =.фи ксидевдмшкк. блд^етат.» исстадует-

:я процедура, являющаяся аналогом процедур:-: субоп?№иязи;-:ц ю § 2 гл. I. Один иаг предлагаемого процесса состоят з следующем. Пусть имеются 'Ък £ к а '~€ !вякем с множеством ЗЪл. граф с Knoxeci'Eow верит V—"[ -í) 2, ...^1-гп} ■ Я ЬЩОгкОСТВОш дуг I/ "{O'^+j ) ! С S j) £ <%>к í . Цуо?ь компонента связности этого графа занумерованы: знаяеняями индекса -д <--jC(¿8*) я V-? - кяояестдо вершин 9 -ой компоненты. Поводам

V* . J0H jej I }' . Пойдем -

р с Ь " , решая систему линейных уравнений.

с у ¿\

(¿> ч) «JBx.

« --------------- "*eQCñ«) .

Есля имеем с| с , го проверяем ?дя этого при решается система' (18-19) вместе с

(21) пря ЗЪ—ЗЪк . Если найденные неотрицательны,

го я - равновесный вектор цен.

8 лрогивногл случае, взяв пару (<■<,>]„) » отвечающую некото

** /-1 ■ '

рому 2^ -< С , перехода к следующему шагу с

В случае Cj'<фZi<' проверяем - Золи

это условие выполняется, то принимаем я

В' противном олучаз науодям максимальное' £ ,пря котором ¿¡(¿^ tz]?-^ принадлежит 1^ С^З*") .т.е. удовлетяоряет сустеме неравенств

Бэлн пару ('¿г^ ¿1) , отвечающую л»шгирукчне;«у аз згпх ус-

I

лов;;:!. при опргдедеш-ш Ъ , переход;:',; :■: следующему шагу

'Гсорг^о 5. Для {¿сколи обуепа с фиксированным бюджета-' • ' хк и,с:од субойт.:;.;;!зацы: лра 'условия двойственной невырлкден-иостп транспартко" задач/. ксделд заканчивается через конеч-' по о ч;:с;;о тагов.

Доказательство ;>-гого утверждения основано на шюгок-мо.м возрастании в течение процесса значения функции )« в» ГД-- .- сопрякснная к вогнугоЛ.функции

Ы(р) , задаче!! оптимальное значение цглево* функ-Ц2Й (I?) в трваопорйюй .ЖУ£ЗЧ«г (17-20).

3 у /, олисалкие конструкции переносятся па случай модели об:.;енэ йен наличии дополнительных сгргкпчс-н;:" зхла

р^у^^- е задачах у-'астнпков (14-16), -что' приводит к- ограничения:.! в транспортной задаче модели

(17-20), которая, ввиду ртого, разреиа;;.:а -теперь, вробке гс-верд.-ие при всех ¡>е£> . 3 предположен::;: Л^И доказывается .существование рззнонс-сяя ;; сдравздашСегь прая-кего критерия: точка !.:вкс::;.-,у;, л вогнуто?., с&иъч&Е на совпадает с ревяовеелки- т?ора* сен.-01.::шг£.в7ся

лво процедуры оть'скакпя ркхнснспн а •осссюкиаязгс« их конечность при пгэбт,е:ш;;:тс\ш;1.': пред1;оло?.екпл •: певпрокцекнос-ти системы ограагченк^- грьясвиргао? еадзч;' .модели.

В ?5 5-7 рассматривается применение сисг» ссдиздрель-ной ко.щда.гептарпссти дед отк-жкия ршювс-сня £ модели семена с_ перемегплш оакспгзетск :: зСрскэтчклвтся

эн&чний алгоритм, его связь с обдал алгоритмом г.олнпдролъ-5;": комллс:,:ентарностк. В^шлдется определенное ло:!с?во ки-угснкосгд недели обмена, зарекающееся в то;,\ что при проЕО-:нли процесса пэроксгр £ в форкулах (4) на каядо- гаге гняется в сторону увеличения.

2 § 8 обсуждаются гоз:.;с?.кые ослабления исходных требо-;ки:1 к модели, 2 частности- требования С1"^ С , Это при-•дкт к тому, что транспортная задача модели иояег'яквть не-■дную систему сзяге;1 я будет разрешимо";, вообще говоря,не >а всех . Поквзкваетсд, что известны!' критерий

Гейла для существования равновесия эквивалентен условию зреаимости транспортной задачи модели при иекогорогл Р>0.

Б отличие от модели обмена, в когорсг возникающее кучно-постоянное отображение является слабо Ълюгокнкл убывшим, в модели кооперации, алгоритм для которой пряводкг-в" § 9, аналогичной отображение является возрастающим, я менеяде параметра "С- в формулах (4) косит альтеряярую-й характер: итерации с возрастанием и убиванием параметра ~Ь чередуются. Конечность процесса показыватеся при до-лндтелызом требовании на'выбор стартового множества —

■ .

Процедура- еще более общего характера возникает прл применяя рассматриваемого подхода к кодеяи обмена с ограни-гаями сверху на переменные М"- , т.е. ограничениям

- Такая процедура ^засматривается в § 10 в прзд-юкенял с11< ё'.

В § II рассматривается следующий класс моделей обмена 1роягводотвом типа Эрроу- ,збре. Пусть в кодеяи имеются летника двух типов: истребители ¿6 Г и производители ; £ ^ . Если зафиксирован вс:<тор цен ре к" , г-- т>- .

п *

язаодгтель -к€ /< ремгеу -аздячу

- W.x ! (23)

(с", é г;К , к% 0 , (24)

где ¿j >0 , фаш-.роваш ü харзкюрлауюг

производителя. Содержзгелио это означайг, что реализуя -своп клан выпуска' товаров .цролгЕодптель ке^

затрачивает некоторь'? pe<Lypc (например,труд). 3rt¡ затраты ог.исыесюгся ллпе":ю" $ункц:;е2 ¡C«* , не долили прогноз ib и:.;е:э!;;е'гося в квлглкь количествай ¿Г„. . Среди планов врб;:раеток даш;::*: каксшадьшй доход f Р>•**") ""А* . Этот до•<сод распределяется незду' иотребятелямк 'а соответствии с толевша; Q ' * ~ f. ,

¿<z :

Ъ результате дтя потребителя Еозадко-?г задача (I4-1&)

но с й;::;еипоЕан!!Ь'м ^юдкегом ( /5 5 с/L )^-.'л; — .Тре-

¡'усгсл отискять такой вектор дек р~.р , что орсдя оятлыадь нкх планов участников нгЛду:ся jíí*S¿4' в. .xlSarSi* , удовлетворял';;.^ услов;:;:) баланса-

¿42 «tR

Для влокензя такой 'одета в о>:(.:.:у ргссмотрдеэcvoro год-хода гздаче (25-24) сояосгзгляетсл гедято (с.^, ^""-J/ — УГ.схх ! '

. - Cp.Jt")' ; » ; ;

после чего возникает пер^е^ркческпк : одсль с кьряв:етр«зя -Aie." , которая отличается от оЛг-п-'-о": \:b¿t)í:' •.'oí:.sut- т¿.к, -что часть участников - потрс'Зкт-схк,- í€ i - '.;'n:cаоз'/рук^ свод целеьке , г другая часть ~ лсопзвод'.-тгл;. к«.'^ —

такздзлруп? (прд условкогрддагслд-лоо?;'

[елевкх фулквдй у всех участков). 2адача оводигся к опре-;елеикю таких значений параметров Л к ,. чтобы с,тягальные наченяя деловых функций , к<£ Аг , в состояла;;

авновесяя полученной параметрической модели совпадали с за-.акныад значениями

При усяоздя, что все >0 з § II приводится ал-оритм стнскандк равновесия, для которого- токжа доказьгаает-я конечность в предположений невмрокденасстк- придаст я ря определенном требования к стартоьому состоянию..

Результаты дяссертецш; докладывались автором на семяка-ах штематяко-экономячеокого отдела я объединенное семяно-е прикладных подразделений Института математики СО АН, сейнере отдела математического программирования Института атематики я механики Уральского отделения АН, на Второй энференцяя по оптимальному планированию я управлению народам хозяйством (Москва, 1583 г.), на Ш Новосибирской' школе э математической экономике, на международной шксле-секкна-э по методам огшжязацяя и ях прялокедиал (Иркутск, 1989 г.).-

Содержание диссертации отражено в следующих публякаца-<. автора.

1. В.И.Шмырёв. Об отыскания нзлодзйккнх течек кусочко-зстсянных монотонных отображений в" г?* . ЛАК СССР 1981, .259, !') 2.

2. В.И.Ш.шрёв. О потенциальности кусочно-достоянных, ыо-лонных отображения в . Оптимизация 2? (44), 1981, 5-76..

3. В.й.Щлырёы. Монотонность в ляиеЗшх иоделях обмена, гтямкзация, 27 (44), 1331, 7"-95.

4. Е.И.&тирёа. О аостроеш:и алгоритмов отыскания нспод-жшх точек ху соч.'о-постолI пг х аюаитошк оюера^ск»::". к

Оптимизация 20 „'46), 1982.

5. В.К.Шыирёв. 05 одном подходе к отысканию равноЕеся.

-я

в простейспх моделях, обыгда. да СССР, т.266, Й 5, 1933,

6. В.й.Илирёи. А.чгорятьж отыскания равновесия в коде-дяд обмена с фякеярсвенкнта бвдкеммл. Оптимизация 31 (48) 1383; 137-155.

7. В.Л.Шг/дтрев. Алгоритм поиска равновесия в линейно!: коделя обмена, Саб.аат.яуряая., Т.Х2У1, ^ 2,1985,163-7Т>Ъ.

С. Коиечвнй алгоритм отыскания равновесия

в модели обмена. ОгтшЕЗиция 35(52),. 1385, 85-108.

. 9. В. И.аир«;. Топологически" педхид к • исследованию за нехной шделя догслакгсдьносгй.'Сфэ.'чгаескяй вариант' адгори; МО. Оптимизация 3,9(56), 1956, ИЗ & 143.

10. Б.й.йлгрйз. Задача полиэдральной кошшзменгаряоет» ОЛТПГ.мзегдя 44(61), .1988, £2-95.

11. В.И.&щрёв. Об отыскании Разнс-Ессяя в модели кооперации. Оптимизация 41(58)1987, 60-75. " . .

12. В.й.йшрёз. Об едкой классе линскннх однородных зя дач дополнительности в ... Оптимизация 45(62), 1959, , 54-65.

13. Б.Й.Сйгырёк. Об охисдениа равновесия з линейной модели' ойиьпо г фиксированными бюдкеттан и допа~нлтс-лькк.'у^г огр&нпченняш! финансового типа.*Оптимизация 45(62), 1289, 66-86. .

14. В.И.Згя?рёв. Об одно:: да;аеЙно£ экономической кодам г.роизводства-оСыена типа Эрроу-Дебре. Оптимизация. 46(63), 1989, 68-95. ..

Л/Н ■ ^