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

АКАДЕМИЯ НВДК СССР гШ>ИРСКОЕ ОТДЕЛЕНИЕ ИНСТИТУТ МАТЕМАТИКИ

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

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

УДК 5!3.853.0 1 519.805.!

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

КОНЕЧНЫЕ АЛГОРИТМ!! ОТЖШИЯ РАВНОВЕСИЯ В ЛИНЕЙ1ШХ ЭКОНОМИЧЕСКИХ ЩЕЛЯХ

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

■ Автореферат

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

Новосибирск 1991

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

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

нрс ¿ессвр 1<1.И,Еремин

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

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

х

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

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

1992г. в

_. часов на

заседании Специализированного совета Д 002.23.03 при Институте математики Сибирского отделения АН СССР по адресу: г.Новосибирск-9С Университетский проспект, 4

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

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

1991г.

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

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

•Дассертацйя ноекящпяа ¿опросам разработки конечных алгоритмов откскз;:;*л р?ваовесшх: цен у, отвечавдих ям равновесную сосгойКбЕ .в раздютотк аконсшческих моделях,. 2. основу которых яожж«кй лкнейпая модель обмена. , •

Проблема численного отыскания состояний экономического равновесия традиционно зантейет значительное место е иссле-довэнхкх по катечвтячсской экономике. Яервоначгльио.'изучение' этой проблеск велось ъ ранах вопроса об усюйчяностя процесса регулировании .цек через'отображение избыточного сиро-' с«, что приводило к лсследовзвш точек покоя сястеш• обыкновенных Дй<ЭДерскци8лы.ах уравнений. Зга ¡тематика разрабатива-лаеъ Заль£ сом .еа;е' в прошло*! ■ столетии, з в последствия про-долкеяа Хиксои, Са^эльсопон, Эрроу, Гурвицем, Удзавой я. другими дзвестншЕ -учеида»г." '

Другое направлений в облгетя численного отнояаник.рав- -новесаых состояний связано с вопросом нахождения неподвижных. : точек отображений'симплекса.цен в сеЗя я базируется на конструкции ои^иг^алмшх-.разбабнйа; .(восходящей' к/иззестяой'. лемме йаеряера). ¿ процедуре построения невозрз'дающтгея тра-екторяй, впервые предположенной.прилеклтелвно к биматрйчннм играм Ленке я.Хаусоном-я обобщенной впоследствии для задач..-:"':'' лкнзйноЗ юыялекеягарностя Лёмке*/-'-/-

Первый алгоритм такого типа для .отыскания. ненодвжных' . точек был предаокен Скар$ом,; я впоследствии это направление интенсивно развивалось Кувок, Ивесом, Мегомом,ХоанхЧГуем, -

«í

Сегалом, Шеплн, Тоддом, 'Гальмаком и многими другими исследо-»ателяш. Г ..,.':■■". ..

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

Для. случал линейкой моделя оомена с фиксированными о'ид-•«егами задача отыскания равновесия была сведена Айзенбергом к задаче математического, программирования c¡ линейными огра-. ничекяямя, однако конечных процедур её решения предложено не было. Конечный алгоритм згой моделя с переменными бьию предложен Ивесом на основе алгохжгма Летее применительно к специальной -задаче линейной, комлдементерностя в пространстве размерности .. гцп -f- т +п ; , где fИ - число участников ■ а П - число продуктов ыодели. . ,; .

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

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

'.a-ikü^mvsl гркекгующке'Л, гфс-дагаець-е процедуры оскогапы

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

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

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

Основнке. результаты^ диссертации.кратко можно- охарактеризовать следующим образом: , -:,..'■'■- ,-'

г чеподяитяаг точек тагфг отображений;;

2) Предложен. ' подхсд ".к анализу л:

ла зу :лдк ей ннх з:«?йс«й-

ческкх ьюдеясй. опяиаюгдйся ка -рзссыотреаяс возкакввдей so-' •дата ладяэдралькоЗ когда емевтврностя;

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

4) Црсдкоясяы конечяыз алгоритмы сяшлексиого г.кпз для отыскания равновесннх состояний б различных вариантах лкней-ш экономических неделей (модели обмеяа а кооперация как с фйкскрозоннша!, гак s о переаноннами бзодаетама; модель обае— иа с огранячеяшш сверху -на янтенсдвяоста, модель с ограничении.«; сверку финансового шм,.-вариант линейной г,-одели Зрроу-Дебре).

Объем дюсергзцвя 279 страниц, библиография содержит 79 наименований. •

Кзяокедие рааблто на три главы. 13 первой- главе рассмаг-ркве»тся кусочяо-посгоаннис огобракешт в f?" . Какдое' такое отображение но определена» представляет собой пару ( сО, Р.) где сО - конетакй полкэдрадьтй • комплекс, образованный всезозаошшмя грзняик вшуквнж многогранных кно~ кеств Ol , ¿б'] ■ , вддотищях'друг к другу првшшгаи'. образом д х/окпывагощях eck яросгранегво, a F - многозначное отображение, определяемое формулой •

FC*)« oonv-fjf4' I J<€pt , iel J" (I).

при каданнкх точках , ici .

Кусочно-лссгоянное отобраяение даенуегся мо~

нотокцил, если

Vy^ePV (2)

к лскальногмонотойвим, .с'сли это мзсйогго вшкиляетса мя

о

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

т.е. имеющих общую .' . (л -1) - мерную грань.

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

.Теорега. Всякое кусочно-постоянное локальпо-монотошюе отображение (ой , р" ) потонщгаяьно: существует ислиэдраль-. пая выпуклая функция такая, что многозначное стобраке-пйс /- совпадает с порондземш Л-уницией .'••'субдкффереп-цквльнкм отображением '<)■} : X .

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

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

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

Б теореие 3 2 2 доказывается, что для отыскания недод-. в;гаю?. точки возрастающего кусочно-постоянного■ отобрзпёния' применима процедура .метода итераций'; • описываемая соотпощени-• о::. ¿<"~ ^ ¡- (а*) и состоящая; в что по . имеющему- • ел текуп;е:/у лряйшееикп в качестве, следующего прибли-

кен.чя z-K-rL -принимается любая течка из F(z *) ' . ■','.

. Показывается также, что'среди точек Jt" , ¿el , свегда существуют неподвикные .точка -отображения F ,и для Л •их - огнекайия ШЕНО воспользоваться процедурой "соседней вершив": если-для •ми'зщихоя на очередном шаге процесса шоке---Q- Ли точки у '■', имеем , то осущест-

вляется '.переход к "соседнему"'множеству.' .Qy- *, такому что несущая плоское тъ клетки

В

i Л-О/ отдаляет X4 от а:. Обоснование »roS процедуры основано.яз монотонном Еозраста-ния ' значения фушада -' } —в текущей

точке х- , где : -j- ~ функция, .сопряженная, х функции j- , являющейся лохенциальной '-для отображения

Г .

Лдя убывающих отсбрзЕвапй доказывается теорема .2, ут-'верзяведая, что .для того „ чтобы точка Ji бита неподвижной точкой такого отображения Gr > необходимо и достаточно, чтобы ons H2J.sisaot точкой (безусловного) ■ минимума выпуклой

функции (й-) , где f -потенциальная

фуикдая возрастающего • отображения

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

5 5 3 гл.- I полученные результаты переносятся на -класс многозначных отображений, заданных на внутренности симплекса ре R+. J .р^ —1 j- а 'текуыых логарифмя-

• 4ec:yj-t.;0H0'c0brnbw.. . . -" . .--.

Такие отобраз^епия естесгвежте-г образом возникают при ' построения алгордшов для линейных моделей обмэка'с 8яко*~ ровазчцмз»- <$здпкегзмв* 'керорае ргосмах-рягайтс«".'» гл.и.

'•1огйря0.м2чеок2-кояотйн;ц!е аозраогеки^.е 'оюйрексяия па

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

(¿п р - Спу, РТр) - ¡-'(ф), Ур,<: 6° о)

а убивающие'-' неравенством протиЕополокного 'знака.

Для определения ¡кусочяо-лоотояттах логаркфмяческн-мэ--нбтонннх отображений на вводятся операции линейного

пространства но следующей схеме. Каждая точка р<= б°- рассматривается как представитель сс:* тветатвувдего «3 луча 'Р | х'^Лр 3 } .'.На мнокеотве' &

таких лучей ■определяв"опеппшдо слокенал, донимая под суммой

Р'ф Р"

71ву< лучей. Р', луч Ре 9 , порож-

даемый точкой' р «' коордякатамк.. -'.р. р* ■ • , ■

где ру , р?; - координаты течек />'<£ Р , Р" .

Под произведением Р олемента

на. вещественное число понимается луч /пороудаеМыЗ точкой Ц с координата;,:;:

» ;-л

где р. - -координата какой-либо, точки р€ Р■•-.''■■'Так как , "между элегченгами мисаеств V©"5 .';:и 'имеется взаимно-од- '■'•

/ V . . . . Г^

позначное соответствие, то введенные 'операнд в ^ переносятся на , которое таким, образом становятся линеЗ- ;• нш пространством . ■, •■ ., В. нег<^рассматривается ошюакная выше конструкция кусочно-постоянного отображения, однако с . теы 'отлячяем';'- что выпуклая об6лочка: в. (I). берется. по-дреж-.-. нему в .смысле пространства; й ; . Есля для возникающего '. таким' образом точечпо-шгажествекногс отображения выполняется условие (3), то такое; отобпайеняе; даенуется кусочно-по- у ^Ьтряш%* .'-ло.гарифг.?ичо'скй-моирто 01сбройением -X) положительного вектора, р =([->„.•: принетзьетг.ч ;■ = (& р. £л р.) . ■ ' . ' •

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

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

Эта связь имеет место и ,для убывающих отображений с тем тем лишь отличием, что ^ . в этом случае яьляется вогнутой функцией я по определению считается с выпуклой . ^ . Функции. ^ . определяемой формулой ) . доказывается Теорема 3, Логарифмически монотонное убывающее кусочно--постояхиое отображение , РГ .-имеет в 6° в точности одну неподвижную точку, которая является точкой максимума строго вогнутой функции . </ , яоровдаемой отображением На основе ."потенциальности доказывается также •Теорема 4. Для логарифкичесхд-шнотонксго возрастающего куссчно-иостояякого отображения . . при любом векторе из множества' процесс заканчивается через конечное число шагов получением неподвижной точки отобраке-ния. •

Вторая глава работы состоит из трех частей. Здесь рассматриваются кусочно-постоянные отображения 'более общего типа, порождаемые задачей полиэдральной косплементарносгя«. Речь идет об отыскании неподвижной точки отображения Р~ , задаваемого двумя конечшми зашнутыми полиэдральными комплексами иЗ ¿&1 и. 5 — | ГЕ^ге/' » находящимися в отношении двойственности:.

I) если . £11 - собственная грань для

собственная грань для ¿Е!^ • »•' .

2) сит +■ с1ст >» П , V ¿е { ..

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

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

О. . . На относительной внутренности каждой клетки выполняется 1

Собственно таким отображением посвящается часть П второй главы. В § I этой части приводится общая схема алгоритма для отыскания неподвижных точек описанных отображений в предположения, чТ0 выполняется условие "общности положения": аффинные носителя клеток С2; я }~~п I алгебраически 'взаимно дополняют друг друга, и, те?,? самым, всегда пересекаются в един сгвспнок точке. Эта схема состоит в следующем.

Ко к -ом гаге-процесс» имеется пара отвечающих друг

другу клеток л2с.€сО , € X я точек ,

."Определив однозначно точку 'й"" , являющуюся г, 'ресечением аффинных носителей меток и Г^Т- , рассматриваем' зависите от вещественного параметра .•£ точки

Параметр меняется от £—0 при соблюдения

условий: х(£)6 0-1 к , у£.¿НТ«:

^ а при увеличении '6 еше и условия I ."Если при этом; достигает -некоторого значения , к дальнейшее изменение•

лимитируется, например, условием £ £ _0<:к , то в качестве Х2; ппянитлоется грань клетки. О л • .со-

С ^ - л. Ч» „» I

держащая точку * , л "м**1-?* ' , .

олучаг когда гх^йиспзе с лшятируеуся -условием '

У 6 ,' оислогич-зп,- В кредпояо*ссиял новы-

роаденностя, когда )' ¿11 л-) О.*; — [«/направление нзме-

ненкя параметра и на каждом ¿-зге однозначно определено яо •некоторому'правилу предысторией процесса, а и& начальном' шаге - задается вместе с точками .¿Ре , .-

В '5 2 выделяется масс задач, для когорыз: описанная схема позволяет отыскивать неподвижные точки. Пусть И и -- конические составляющие в разложении соответственно многогранных мнокеств и 1 в сумму ограниченного многогранника и полиэдрального конуса с вершиной в нуле, а ^ - конус касательных направлений к в относительно внутренних точках метки

Теорема. Если Н ~ теяесеи и для дабой клетки ,

■■ О

лекащеи на границе многогранника соответствующие кону-

сы к^ >* • :' •' удовлетворяют условаю

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

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

Определение. Многозначное отобрааеняе будем на-

зывать слабо убывающем, если для любой пары различных точек' X и ^ существует вектор Ь ФО , что

- 3 (5)

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

Теорема 2. Для ворондаемого задачей полиэдральной комп-лемеитарносги многозначного' отображения Ц- задача об отыскания такого X , что 6 () однозначно разрешима при любок . ср ■ тогда я только тогда, когда отображение Н является слабо убивающим.

В § 4 гл.И приводится модификация процесса, позволяю- ' щая ослабить условие "общности' голокекяя".

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

(6) (V)

(В)

J

Xj'J(nrj - О , j-^í- .-.j л ,

i < л <-j

где Д я - задатке векторы, и A: , j

( - орты в 13" ).

Определение. Маокестьо 6Ъ<~\ ..казыва-' егся коьгслецектари&л-, если из кавдо" пары . /j в него входит ровно один ¿лсмеит. ; , ..

Рассиотренк.е задачи ведется и лредполокещш, что для любого комплементарного . и, любого нетривиального набора неотрд-цагсльних' Jc'j • j 6 ¿P¿ . . выполняется

. с . АЦ -Ф О о)

' -j&jb - J

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

ше ут^ержде-шя о разрешимое га задачи. На этом пук* еетест-венный образом возникает к новая версия алгоритма доколня-телышети, расширяющая класс реяаемщ: задач по сравнений с известном, алгоритмом Демке.

Построение упомянутого непрерывного отображения сферы в себя описывается в § 2 ч.1 гл.П и состоят в следующем. I В мнояеетве ортов { ел' введем нуме-

рацию от I до 2п , обозначая их , 3>2* с совпадением правила: для каадей парк один из ортоЕ получает обозначений о£3 , а другой - ,

. Кавдшу. кошиааектарному мнокестау сопоставляется два конуса: № (ЗЪ) - ¿ас ■{-5 } я .

'¿- (ЗЬ) ~ I _ после отого однозначно стро-

ится куссчио-лянейноё отображение р • , пер'евоядщее' кону-си И № в соответствующие дм конусы . Наконец

требует,гое отобракение сферы в себя определяется как р~ 0е)—

Отличие от нуля степени отображения Р • является достаточным для разрешимости.задача'коыплеменгаркости (6-8) при любом Достаточным признаком такого рода посвящен

3 3. Приведем некоторые я» док&зываемых утверждений.

Теорема I. Воде все главные миноры матрявд А 'иеио-локкгашш и для некоторого множества , с¿С • »^П }

,выполняется

с!е1Аи,,<0 г {А1}.^ 4-0 ,

то задача коотлемеигарностя.с 'такой, ыагрицей А разрешима, при дюбом <|, .

Одесъ ~ ^трхца из столбцов А^..., А ..

еяе^бкгов пр:-: £ с)~

Теорема 2. Если нее диагональные элементы О,- :латри-•цц А отрицательны, я при всех у«-^,..., П .выполняется !

Я]]-*- а^ &0 , 1Ф) , '

то при" любом (р задачи комплементарностя имеет не менее п -¿ решений.

Теорема 3. Пусть для каждого Я/ такого,

что Ас^и и любого вектора С? выполняется

АсМ . Если существует, но меньшей мере, два

отрицательных.диагональных элемента матради А ,'и хотя

бы в одном из соответствующих столбцов матрицы остальные

л

элементы неотрицательны, "то о/е^ (-" ^ 1

В § 4 излагается общая схема сферического варианта алгоритма комплеглентарностя. Известный и. весьма эффективны?:-алгоритм Лемке базируется на погружении исходной задачи в класс задач с переменной правой частно ,гдеб>-

вещестЕеннкй параметр, а ^ • - , I) . Дга некоторых

классов задач этот алгоритм, однако, не дает решения. Примером такого класса ¡являются задачи с отрицательной диагональю в матрице ограничений, о которых шла речь в теореие 2. В предлагаемом варианте алгоритма комплементарноети расш-релие класса решеьшх задач достигается за счет иной пара-аетразодач правой частя: ^,(6) рсо-ьТ. .

В заключительном § 5 I гл. П приводится одна из возкок-ннх алгоритмических конкретизация общей схемн сферического алгоритма я доказывается, в частности,

Теорема 8. Если р— --2. а выполняется яредполокенпе невырожденности, то з условна теореш 2 сферически?, алгоритм дает решение задачи кокплементарности..

ГГрсдполокеяяе невнрогденностя состоит в ток, чт^ пел;! дот ко».а.у.«=квк?арпого арогх-сгвй яру нгкоторой <- ж-з-

е-,- • (j (b) 6 ■ (Jh") , то в представлении 1

JE1, ^ C^i) (Ю)

разве ддвь один кз. коэффициентов X; . ыокет быть равен нулю,

В третьей чист::, г.;:. И рзсскатряваегся спздаельная дв-

п"

пе£ная задача дополнительности в : .-<+ , порождаемая частично:: упорядоченностью переменных л некоторой неразлокзмлй ие-стоицателъко" патрицей. Задача такого типа возникает при построении алгоритмов егкокания 'равновесия в линейкой модель- обмена, излагаемого в гл. С!. Постановке задачи такова. Пусть имеется граф Р с множеством вераан /?/и

кпанеегаси дуг. D. — -C4S|js)l >• Я -¿J .являющийся

дорадо;..;. Кроме того, задана ;полокигехьку2 вектор и квадратная матрица Ъ-jctij} 'размером' ЛхП - неотрицательная, иерг.здокь.ая и при всех л

Пусть el1 - строк;: кто" матрицы. Рассматриваются две слета® линейных однородных неравенств:

> y-'-i-'^i, (II)

р (fUr)> <? V л (1:а>:

где означает, что цсчь дуг,: соедаддахая вер'линн к

и ¿4 з-с ссдер-:;;-.? дуг:: Ц^

\ л

1ресуется найти кекулеьс i вектор с> е к^. :, --.решающий (II—12) л удовлетворяющий сие у слог и" ког.жяеией та рнос г к-

Показывается, что такая задача при сделанных предполо-; жениях о ^ и X) всегда разрешима, и притом едяиствек-яыы образом (с точностью до палоаятельного кнонетеля). Олз-сквается алгоритм решения являющийся конкретизацией обще:» схемы алгоритма полиэдральной комплементарности, .ззяо&бвной в § I гл. II.

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

Все рассмотрения основываются на специальных полиэдральных разбиениях симллексоЕ цен, порождаемых моделью. Выявляется принципиальное качественное различие монду рассматриваемыми вариантами моделей: модели с фиксированными бюджетами поровдаюг потенциальные кусочно-постоянные отображения, рассматривавшиеся в '3 3 гл.1, а при исследовании моделей . с переменными бюджетами возникает аналог общей задачи полиэдральной компленентарности, о котором вию речь л ч.ГГ.гл.П. Поя

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

К дальнейшим обобщениям задачи полиэдральной кокплекен-таркости приводит рассматриваемый вариант модели Зррау-Дебра Приведем общую схему подхода применительно к кодевя обмена, которая "влагается в 1,2. Пусть в ?,-.одели ямье-ся т участников и п товаров. Обозначим 013 ,

••• . Пусть с\ (Ж *€ (2+ - фиксированные векторы, хершстерлзугацие учесиша 1бТ : с1 аадает его. функцию .предпочтения (с',Л") , а с1с укгрывает имеющиеся у участника запасы, товаров. При заданном векторе цен —

— ре Р^ I участник ¿С 1 'решает задачу

(с'~ та х I ■ (14)

, . (15)

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

(к)

с61 и/

Везстор р. и набор Ух^.^падают состояние равновесия модели . ''■■,:■■

В предположении с'^О и ~ { ' V ¡й [ .

<.е/ ^ у у '

срякеи-с рассматриваемой ^одг-лъ:о. следугхгдо лранспортнув задачу ■ - .. .

¿¿¡ ¿л с1. - та* / с?)

г . / - "■'..■■■

(1С)'

^ л р] > . аз).

(2 л ; ¿е/, . ; (20)

Обозначим.через ^ 'совокупность дэойственно-допустгкых базисных множеств этой задачи я всевозможных лх подлнояеств, обладающее свойством . ¿' иакриваемоотя: для ¿ЬеЗэ- мно-.

аество Ф & ПРИ ^^

Теперь свяжем с кавдьм £>€¿¿5- пару множеств: £2 (■%>) и ■ ЯТ-б^ • Множество' Х2.это'множество•таких

рев» . при которых совместна система (18-20) при дополнительном требовании- -

. »:■ . (21) задается формулой •

глнояее:

(22)

Теорема I. Для того,, чтобы вектор цен был рав-

новесным, необходимо я достаточно, чтобы при некотором .".выполнялось

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

разбиение симплекса 0 , г-совокупность мноаестг ,

разбиение его внутренности б" . При этом множества О. ) - и являются многогранными л

¿^с^следуог ,.£!(%*) =>£ХЛи,).

Кроме того, dim .¡//1/>1 Г~ '(^jj-n-hlw любом

Тек сами», многогранные множества О. (Я') при образуют два полиэдральных комплекса, двой--, '

сгбсякнх друг Другу, с отыскание равновесного вектора цен модели сводится к -задаче патеояраяшой комплементарное yja: найти ¿Ъс , 'для которого

Ora задача является аналогом задачи, рассмотрениеГ в ; ч.п. гл. п.- ■

Приведенные яоогро'еккя.'ямевт. место и дия иоделя-кооперации, - нувио'лхуь юивакть'. на mi'r» в (14) и (22).

Недели с фиксироваьщш бкдгетгш характеризуются тш, что С, где <?-.CiY*-->-0 , а Л;>0 и'. РеглизацчД онисагного-подхода для таких моделей рассматри- ' •веьтся в § 3. Показывается, что в этом• случае,--если ввести многозначное охо'брпьегние . ; '• & &" форчулой.

где АУ0&)

- относительная внутренность мгожестве . до для модели кооперации отображение удовлетворяет нерниенсгву (ЗУ, а для модели обыенз - керз-векству противоположного знзга. йо .позволяет воспользоваться результатами § 3 гл.1 и получить.конечные .процедура для. отыскания неподвижных точек :ггобрз.кенпя которые. и:

'дают равновесные вз.ггоры цен. .

Теорема 3., Ддк модели кооперации .с'фкйсаровеиьймячбкд* жетак-g ясксшй разновесный Bt-ктор цен пожег быть гоЛучен за конечное.чмело сйгов. процедурой.метода-итераций, опие-увае-г,-оП соотнося /.ev ' ^Р 'р*) •

Для модели с $якг ировзннш: и,-с годует- :

ся процедура, являющаяся аналогом процедур:-: субопгшизацгя ^ из § 2 гл. I. Один шаг предлагаемого процесса состоит в следующем. Пусть имеются. и с>.'~€ (<%>.<) Свикем с множеством граф с множеством версии •{ ¿,2, , я икомюпхш дуг и

\ $ . Пусть компоненты связноегя

о того грефа занумерованы;' зигмеякяия- индекса >> £/£(28*}- я ' множество вершин т) -ой.компонента. Положим

I С^реУ^ У. Найдем Р = ?"сб° , петая систему линейных .уравнений

с) ск -

Если имеем , то проверяем •

Для этого при р~'(£.к решается .система'(18-19) вместе с ", 421) при ^ —сАц . Если найденные неотрицательны,

то я ^ "" - равновесный' вектор цен.

В яротявпом случае, взяв пару С^у]о) .отвечающую некоторому -< <9 , переходим к следующему сагу-с

В случае 2к проверяем ^ЕЕГ.б^О.. Вели

это условие выполняется, то принимаем ^ ск и .В противно!.! случае! находим максимальное ,при кото-

ром — принадлежит ^г^С^ЗкУ ,т.е.

удовлетворяет системе неравенств

Cl VC'

, ^Л/.

cm \

Бзян пару C¿t , отв.ечавдую .Арштяруюпему йз этих ус-

ловя?., при опргдсленяя Ъ. - , пер.ехохйк 'к .следующему шагу

с .-зь'^щV^a/jjf ,'■jT^fr*)'.' : - л

Теорема 5. Для модели оймена с .фиксированными бюджета-' ' mí: метод суботнмпзацип'яри условии .дарственной, невырожденности транспортно*? задачи модели заканчивается чороа конечное число тагов. -.'''. ' _ ■ . ' ..

.Доказательство >гого.утверадекзя основано.на монотонном возрастания .'в -течей;:ei процесса значения функции V ("$)•= ' '■■¡a- гд.". т - сопрякенная к вогнуто",функцая

c¿- 0¿(p) , зэдюаасй оптимальное значение целсио.Ч. фуик- . ни;: (17)' в траяспоргло* ■ задаче- (17-20).•-;■'.'

■ Б s 4 опксаякае конструкция переносятся па случай модели обмела пра .наличия допояпхтельикх ограничен;:" вида " Pjüji&ßj. в задачах участников (14-16), что'-ириводат к ограничения:.! ■ <■ fij ' в транспортир?-задаче модели . (17-20), которая, -ввиду'этого, "разрещ;ма теперь, вообще говора,- не при всех .5 предполоиенп;: JZZ ßj ->Д;-'-доказывается существование рз.'зновесия и ç"[аведливость прак-него критерия: точка мскс::мут.:>. вогнуто':. cjyr.v-u;:.t: ^(^^-ffinfy на 6° совпадает с рсвноЕеслкм. вектором цеп. Ог.::сг:вЕ.втсд -две процедуры отыскания рквысксия й;оСссковква^гсл их конечность при пгойремгнпголъав.:: предполо&йвклх леькрокдекпос-тн система ограничен!:;: гр&лспортно"'. вад^ч:- модели. ■ • .;• .

; В Çl'5-7 рассматривается пр::меяоннб схсмц педивдрадь-ной ко^лемепгарпсстн дся'отк^каккя рш:овссня а модели обмена с переменна:«! едкекнзгтея с'-Х^твавтся

конечный аигорят»:, его связь с обжал алгоритме:.' полиядрпдь-но:: кс?.;яло:.:с':тпрностл, Заявляется определенное .-о::с?во монотонное т:; педеля сбпена, виргзжцееся в -гот.т, что лрл проведен;!!! процесса пэрокстр С в формулах (4) на кзядои ¡лаге меняется з сторону увелаченяя.-

]> 5 В обсуудаютск возьмгзше ослабления пеходчкх требо-взкпГг к «одели, в часгнсстя- требования . Зге при-

водит к тому, что транспортная задача модели похет л:,:еть неполную слоте?.;;/ связей л будет разрешшй, вообще говоря,не при всех . Показывается, что гзаесяшЗ критерий

Д.ГеЗда для существования равновесия &кшшагектеа условию рззрезятгости транспортной задачи модели пек некотором С»О.

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

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

■ . Такая процедура рассматривается в § Ю в прад-

полокенян .

В § II рассматривается следующий. класс моделей обмена с производством типа Эрроу-,";збре. Пусть в модели имеются участника двух типов: потребители <6 X и производители '<€ й? . Если зафиксирован вектор ц^к р& ,, хг о- ,

взвода телъ- ч£ 14 . решает-задач?

Ср> ~~ тах • (2S)

Сск, , , (24)

где %к>0 , -ск€3/»£й?- $:йкс{:роваиь' ¿5 характеризуют 'прокзводателя. Содержательно это означает, что реализуя • • свой :шан выпуск^" товаров '• .производитель

затрачивает яекотопу" /ресурс (например,труд).' Эти затраты олпсывЕйтся ля;':с"по." 'фущдаей С'^ х^У , s '.не .должны пре-внпать имеющегося вналичии количествас . Среди планов в'нбпрн стоя дздкЗ какспкальний доход ( р> .X*4) . Этот

доход распределяется ыезду' 'потребятелямв; а .-соответствии с .,■■ долевьет кссЗД'в^екта'л;: > ^у" ^ ■ ."•."

В результате для. потребителя В03.чикэ?т задача (14-15)

но с'йяксиповаиша» 'юд-хето;,; .( Р>'c/frj ~ „Тре-

йуется отыскать такой' -вектор кад ip-p ' »' что среди оптнмаль-нкх планов участников найду"c<i oi'^j?*" . к. '• /удов- -

лсгворлЕзгцге условии йалакса-•.

..-■■ ¿4J. ;. :, .

.• Дгя влоЕбнпл такой уодели в. сх<^:у рассматриваемого подходе задаче (25-<Ц) сопостаг.ляетсл 'гед-ччг '

(с.«\ x'-j — .^са .f .-

после чего ..возникает пгра-ейкческая : одг-:ь с пйра:/етр2:л;г ... , yVst.'. ,; ксторая. стлДчается,'дс ::0дел::'-.:оС:-7сйс'- тел,-,.-;

что-ч=сть :уч^сгаиксв - потребителиie.J; какбшззкрую^;: свои целеькеЧуикда:, а .другая' часть - яропзгоднтел;; к с -KKK3K.43iipyRT (при услов'.:;: ■ .неотрицательности :

¿а. •

' целевых функций У всех участников). Задача сеодится к определению таких значений параметров Л« , чтобы Стиральные значения целевых функции , ке , э.состоянии

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

При условии V что вез 0^0 з § II приводится алгоритм отыскания равновесия, для которого- также доказывается конечность в предположении -нёвырокденнссиг щгацеаяа, и. при определенном требовании к стартоьому состоянию.,

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

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

1. В.К.Шмырёв. Об отыскания нзлодвияшых точек хусочно-постсянных монотонных отображений в 9° . ДАК СССР 1981,

т.259, 2.

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

3. В.й.Щлкрёв. Монотонность в линейных моделях обмена. Оптимизация,. 27 (44), 1531, 77-95.

4. Е.й.Егллрёв. О построении алгоритмов отнешигя догад-никны.х точек нуссчпо-зостояшшх копотевных отображен;::' в

Опттззукя as ¿48), ХЗБ2. i

5. B.K.tepSe. Об- одной подходе к отышишю равковесяь в npocveîtox моделях обмела. ДАК СССР, г.268, Л- 5,, 1933.

6. В.Й.ПЬигрсв. А'пърмш; отысквакя равновесия в моделях обмена с ф;;кса?еваянккя ' бюдкеккш. Оаишзацця 31 (40),-1933,•I3?TI55. .' ' '

7. B.ÎI.SfcKpSB. Адгориш поиска равновесия в линейной модели обмина. Слбллаг.куриад., т.ШТ, & 2,1965,163-7^5.'

S. Б.И.11нкр;й. Конечный 'алгоритм отыскания рависвссяя в модели обкека. 35(52), 1385, 85-Ï0S.

S. В.И.Елшрок.' Топологически" подход к исследованию лй-не;;ной моделв •дополиыелыюотя. Сферический вариант' алгорат~ мо. Опх>;:л;аацля 39(56),' 1986, ИЗ 143. •'

10. Б.ИЛ'&згрйв. Задача полиэдральной комплементарноетк. Олгжпзгйш 44(61); 19£8, .82-95.'

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

12. Б'.И.&шр&э. Об едкоц классе линейных однородных за; дач дополклтелькоспГ в .'-Оптлиизацяя 45(62), 1989,'.

54-65. .

13. В.К.Шмкрёв. 03 отысканий разновес ля в ллке^ной мо-\ далк' обмена с фякеярованяыгди бюдкетамд и .допатакт&дкаш. ■ ограничениями финансового тепа. ,'01тшязацкя','45('62),1989,

14. В.И.Шиырёа. Об одной жаейной ваонокяяеекей' модели производства-обмена типа Эрроу-Дебре^; Оптику з$ция.46(63), 1989, ,68-95. ч