Развитие математических моделей и методов теории гидравлических сетей и их применение для моделирования рассредоточенного рынка Коваленко Алексей Гаврилович

Содержание к диссертации

Введение

1. Математические методы теории гидравлических сетей для моделирования однопродуктового рассредоточенного рынка 52

1.1. Основные определения и обозначения 52

1.2. Математическая модель однопродуктового рассредоточенного рынка, как задача потокораспределения теории гидравлических сетей 53

1.3. Некоторые вопросы анализа функций спроса и предложения 57

1.3.1. Некоторые вопросы анализа функций предложений и спроса на факторы производства, построенных на основе задачи производителя 51

1.3.2. Некоторые вопросы анализа функций спроса, построенных на основе задачи потребителя 68

1.3.3. Кривая предложения-спроса пункта, экспортно-импортная кривая, торгово-транспортная кривая 77

1.4. Анализ устойчивости, существования состояния равновесия и равновесных цен. Алгоритмы поузловой увязки для отыскания равновесного состояния однопродуктового рассредоточенного рынка 78

1.5. Некоторые вопросы анализа функционирования систем, описываемых моделью однопродуктового рассредоточенного рынка 94

1.5.1. О распространении неравновесных состояний 94

1.5,2 Роль субъектов рынков в процессе перехода к состоянию равновесия95 1.5.3. Численный анализ в случаях невыполнения достаточных условий .96

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

1.7. Модификация алгоритма поконтурной увязки для отыскания параметров моделей субъектов однопродуктового рассредоточенного рынка 100

2. Экстремальные модели многопродуктового рассредоточенного рынка, некоторые их свойства, применимость методов расчета потокораспределений ТГС для отыскания их равновесных состояний 107

2.1. Математическая модель однопродуктового рассредоточенного рынка, как система экстремальных задач 107

2.2. О применимости методов поузловой и поконтурной увязки 109

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

2.4. Статическая модель многопродуктового рассредоточенного рынка 114

2.5. Взаимосвязь статической модели многопродуктового рассредоточенного рынка и модели межотраслевого баланса 121

2.6. Вопросы применимости алгоритмов поузловой и поконтурной увязки теории гидравлических сетей для отыскания равновесного состояния модели многопродуктового рассредоточенного рынка 123

2.7. Финансовые потоки в сети, расчет валового внутреннего продукта 127

2.8. О взаимосвязи равновесных состояний математических моделей многопродуктового рассредоточенного рынка и задачи централизованного управления 129

2.8.1. Математическая модель многопродуктового рассредоточенного рынка и задача централизованного управления 129

2.8.2. Теоремы сравнения функционирования экономических систем, описываемых моделью многопродуктового рассредоточенного рынка и задачи централизованного управления 132

2.8.3. Рекомендации по синтезу оптимальных структур управления больших экономических систем 138

2.9. Динамические модели рассредоточенного рынка 139

3. Модификации метода возможных направлений для отыскания равновесных состояний модели конкурентного равновесия рассредоточенного рынка 143

3.1. Модель конкурентного равновесия рассредоточенного рынка с распределяемыми ресурсами 143

3.2. Основная задача выпуклого векторного программирования 146

3.3. Некоторые вопросы разрешимости систем выпуклых неравенств 151

3.4. Критерии эффективности в задачах векторного выпуклого программирования 160

3.5. Функция Лагранжа 166

3.6. Алгоритмы поиска слабо эффективных точек 171

3.6.1. Алгоритм поиска слабо эффективной точки безусловной векторной оптимизации 171

3.6.2. Алгоритм поиска слабо эффективной точки условной векторной оптимизации 174

3.6.3. Алгоритм возвращающих направлений для поиска слабо эффективной точки в задаче условной векторной оптимизации 179

3.6.4. Некоторые вопросы численной реализации алгоритма возвращавших направлений 183

3.7. Конкурентное равновесие и Парето-эффективность 188

3.8. Алгоритм метода возможных направлений для поиска точек равновесия в моделях многопродуктового рассредоточенного рынка 193

4. Динамическое программирование и аппроксимационно-комбинаторный метод в задачах размещения предприятий рассредоточенных экономических систем 198

4.1. Постановки задач оптимизации многошаговых процессов, заданных на ориентированном дереве 198

4.1.1. Основные обозначения, понятия и определения 198

4.1.2. Постановки задач оптимизации многошаговых процессов, заданных на ориентированном дереве 200

4.2. Алгоритмы решения задач оптимизации многошаговых процессов 202

4.2.1. Алгоритмы динамического программирования для решения задачи 1 202

4.2.2. Модификации алгоритмов динамического программирования и аппроксимационно-комбинаторного метода для отыскания оптимальных и R-близких решений, для решения многокритериальной задачи 208

4.2.3. Аппроксимационно-комбинаторный метод решения задачи 4 216

4.3. Развитие задач и методов оптимизации многошаговых процессов, заданных на ориентированном дереве 220

4.3.1. Задача размещения предприятий на сетях в виде ориентированного дерева 220

4.3.2 Алгоритмы отыскания оптимальных решений задачи размещения предприятий на сетях в виде ориентированного дерева 221

4.3.3. Примеры балансовых соотношений. Алгоритмы построения функций cj(z) 225

4.3.4. Алгоритмы отыскания оптимальных и всех R-близких решений ЗЦУ в сетевой постановке для сети типа ориентированного дерева 228

4.4. Задача размещения предприятий на сетях произвольной структуры 233

4.4.1. Определения, постановка задач 233

4.4.2. Построение аппроксимирующей задачи 236

4.4.3. Алгоритмы решения задачи размещения предприятий в сетевой постановке 239

Заключение 247

Список литературы 253

Приложения 278

• Некоторые вопросы анализа функций спроса и предложения
• О взаимосвязи модели однопродуктового рассредоточенного рынка и сетевой транспортной задачи
• Некоторые вопросы разрешимости систем выпуклых неравенств
• Постановки задач оптимизации многошаговых процессов, заданных на ориентированном дереве

Введение к работе

Известно, что поведение однопродуктового конкурентного рынка описывается кривыми спроса и предложений, его равновесное состояние [168], [259] достигается в точке пересечения этих кривых. Однопродуктовый рынок будем называть сосредоточенным, если поведение всех его субъектов (покупателей и продавцов) можно описать одной кривой спроса и одной кривой предложений (смотри рис. 01).

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

Возможно, что такое описание и адекватно для процесса обмена для отдельного изолированного пункта или простейшей экономической системы. Неравномерность геофизических свойств территорий, разбросанность размещения природных ресурсов, разбросанность и ограниченность мест, приспособленных для комфортного проживания людей, их большое количество (гораздо большее, чем количество мест проживания), склонность индивидуумов к производству только отдельных видов товаров, их склонность к потреблению товаров, произведенных не только на месте проживания, приводит к тому, что происходит обмен товарами также и между различными пунктами. Необходимость моделирования такой ситуации приводит к возникновению понятия однопродуктового рассредоточенного рынка (ОРР), т.е. рынка, в котором товар может производиться в одних местах, а потребляться в других [95] - [99]. При этом возникает необходимость описания не только процессов его (товара) производства и потребления, но и доставки от производителя к потребителю. Конечно, функции доставки товаров часто выполняют сами потребители и производители, однако на этой стадии развития рыночных отношений возникает еще один субъект рынка арбитражер, выполняющий посреднические функции. Арбитражер приобретает товар в пункте с меньшей ценой и продает его в пункте с большей ценой [109]. Различие в условиях производства и потребления и пространственная разобщенность приводят к различию цен обмена в разных пунктах [25], что в свою очередь приводит к обмену между отдельными пунктами. Различие цен в различных пунктах рассредоточенного рынка Поволжья во второй половине XIX - начале XI вв. демонстрирует карта изоцен на большой территории, выполненная в работе [155]. Исследования по разбросу цен на территории современной России приводятся в [37].

История развития человечества показывает, что арбитражеры являются одной из основных движущих сил познания и освоения новых территорий. Они осуществляют поиск рынков сбыта производимых товаров и дешевых рынков потребляемых товаров. История развития морского флота (да и речного тоже) теснейшим образом связана с развитием, прежде всего торгового флота. Истории крупнейших географических открытий, Великий шелковый путь, реформаторские преобразования Петра І в России, Северный морской путь -примеры расширения торговых отношений различных удаленных территорий. Роль арбитражеров выполняют различные торговцы, в России - купцы. Этот вид субъектов экономики оказался не менее значимым, чем первые два (производители и потребители). Так, например, согласно современной экономической географии [150], необходимость обмена между различными пунктами и уменьшения затрат на транспорт продуктов приводит к размещению мест поселений в основном по трассам коммуникаций (первоначально вдоль берегов морей, рек, озер, позже вдоль железных, автомобильных дорог). В модели однопродуктового рынка параметром, который определяет объем выпуска товара (поведение производителя), является цена, этот же параметр определяет и объем потребления (поведение потребителя). Объем товара, который куплен в одном пункте и продан в другом, определяет разность цен на товар между этими пунктами. В результате этих взаимодействий цены на сосредоточенных рынках приходят в иное равновесное состояние.

Модель ОРР состоит из конечного числа сосредоточенных рынков (смотри рис. 02). Их субъектами являются производители, потребители и арбитражеры, осуществляющие обмен товаром между пунктам. Арбитражеры каждого пункта могут выполнять роли как покупателя, так и продавца, в зависимости от соотношения цен со смежными пунктами. Отметим также, что в каждом пункте могут присутствовать субъекты, осуществляющие экспортно-импортные операции во внешние экономические системы. Под равновесным состоянием модели ОРР будем понимать такие цены продукта, при которых каждый пункт находится в равновесном состоянии, т.е. в каждом пункте выполняются условия материального баланса: количества товара, поступающего в пункт, плюс количество производимого равно количеству потребляемого и выходящего из пункта. А это и есть задача потокораспределения теории гидравлических сетей с нефиксированными отборами [120], в которой цены на товары следует интерпретировать как потенциалы с противоположным знаком.

Отметим, что подобная взаимосвязь этих переменных отмечена еще Ермольевым Ю.М. [58] для транспортной задачи в сетевой постановке. Развитию математических моделей и методов теории гидравлических сетей [8], [125], [157] с целью применения для моделирования рассредоточенных рынков (как однопродуктовых, так и многопродуктовых) посвящена данная работа.

Опишем кратко суть моделей и задач теории гидравлических сетей, которые развиваются в данной работе. За основу описания возьмем монографию основоположников этой дисциплины А. П. Меренкова и В. Я. Хасилева [120] и монографии Б. М. Кагановича А.П. Меренкова, О.А. Балышева [65], А. П. Меренкова, Е. В. Сенновой, С. В. Сумарокова и др.[119]. Под гидравлической цепью (в дальнейшем мы применяем термин гидравлическая сеть (ГС), который, по мнению автора, ближе к используемым в употребляемой экономической литературе терминам в аналогичных моделях) понимается математическая модель, включающая две составные части: расчетную схему в виде ориентированного графа и алгебраические соотношения, описывающие движение некоторого потока по его дугам. В [65] приводятся примеры применения ГС при расчетах химических реакций и анализе превращений и распространения вредных веществ в атмосфере. Предмет теории гидравлических сетей (ТГС) составляют: - прямые задачи потокораспределения в ГС; - обратные задачи потокораспределения в ГС; - задачи оптимального синтеза (выбора схем и параметров) сетей. Последние обычно связаны с технико-экономической оптимизацией трубопроводных гидравлических систем (водо-, тепло-, нефте- и газоснабжение и др.). При изучении реальных объектов в ТГС до настоящего времени исследовались три основных типа моделей:

- сети с сосредоточенными параметрами;

- сети с переменными (регулируемыми) параметрами;

- сети с распределенными параметрами.

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

Гидравлические сети могут быть открытые и закрытые, гомогенные и гетерогенные. Открытые сети имеют притоки и стоки, т.е. обмениваются веществом с окружающей средой. В закрытых сетях притоки и стоки отсутствуют. Под делением гидравлических сетей на гомогенные (однородные) и гетерогенные (разнородные) понимается два подхода. В термодинамике к гетерогенным относятся системы, вещество в которых находится в различных фазах.

Для простейших сетей, т.е. сетей с сосредоточенными параметрами, задачи расчета стационарного потокораспределения в [120] описаны тремя способами:

а) на основе контурной системы уравнений;

б) с использованием потенциалов в вершинах;

в) в экстремальной постановке на основе тепловой теоремы Кирхгофа - Максвелла.

Контурная система уравнений имеет вид:

Ay=Q, (0.1)

ВАР ВН, (0.2)

ЛР,=/Ы, (о.з)

где

- У и yv - вектор потоков на участках сети и его v-й компонент соответственно;

- =[a,v] - матрица инциденций соединений вершин и дуг размерности (-l)xF [148], в ней а,у=1, если дуга v ориентирована в вершину /; аы \, если дуга v ориентирована от вершины /; и aiv 0, когда вершина / и дуга v не связаны между собой;

- Q- вектор внешних притоков и стоков в вершинах, Е{) :1 =1 2 3,..м1}=0;

- Е - множество вершин;

- V- множество дуг;

- АР и APV - вектор потерь напора и его v-й компонент;

- Я- вектор действующих напоров;

- В=[Ьь] - схи-матрица совпадений контуров и участков; у-1, если первоначально задаваемое направление потока на участке совпадает с направлением обхода контура; 6 =-1, когда эти направления противоположны; 6 . = 0, когда участок v не входит в контур к.

Уравнение (0.1) описывает первый закон Кирхгофа, который применительно к гидравлическим сетям выражает требование сохранения массы. С помощью (0.2) формулируется второй закон Кирхгофа, который можно интерпретировать как распространение общего принципа сохранения энергии на отдельные контуры сети. Выражение (0.3) является замыкающим соотношением, связывающим потерю напора с расходом на ветви. Отметим, что соотношения (0.1) - (0.3) присутствуют и в модели ОРР, однако в ней замыкающее соотношение (0.3) имеет совершенно иную природу.

При использовании потенциалов в вершинах в системе (0.1)-(0.2) уравнение (0.2) заменяется уравнением

АР-Н=АТ Р, где

- Ат- транспонированная полная шхп матрица соединений узлов и ветвей;

- Р - вектор давлений в вершинах.

Если в при этом считать, что в (0.1) вектор Q является известной функцией от вектора Р давлений в вершинах, т.е. Q=Q(P), то получаем задачу потокораспределения с нефиксированными отборами. Несложными преобразованиями графа, задача с нефиксированными отборами может быть преобразована в задачу с фиксированными отборами. Такой переход описан и используется в работе [32].

Основанный на работах Кирхгофа и Максвелла экстремальный принцип потокораспределения в сетях сформулирован в [120] как тепловая теорема, смысл которой заключается в следующем: потоки в открытой пассивной сети распределяются так, что ими производится наименьшее количество теплоты. Соответствующая математическая задача приобрела вид:

найти

H{APvyv: ve V} - min

при ограничениях

Ay=Q,

APv=fv(yv)

В [120] рассматривались возможности распространения теоремы о наименьшем тепловом действии на активные сети, в том числе с различными показателями степени в замыкающих соотношениях (см. ниже), путем такого изменения вида целевой функции, чтобы решение экстремальной задачи совпало с решением системы уравнений (0.1) - (0.3). В зависимости от того, в каком виде представлена задача потокораспределения, применяются соответствующие методы решения: поконтурная увязка, поузловая увязка, применение различных экстремальных методов.

Замыкающие соотношения fv(yv) для несжимаемых жидкостей применительно к описанию задач ТГС в [120] представлены в двух формах:

APv=fv(yv)=zvA (0.4)

APv=fv(yv)= zvi yv +zv2 y\, (0.5)

где z - сопротивление дуги. Показана возможность использования зависимостей (0.4) и (0.5) для моделирования характеристик источников действующих напоров с помощью уравнения

H=ff-zeH/eH (0.6)

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

С вычислительной точки зрения исследовались формулы для определения z на основе уравнения Дарси-Вейсбаха:

AP=A{w2p)/(2d) и экспериментальных зависимостей для коэффициента трения Л.

Влияние вида замыкающих соотношений на математические особенности задач технико-экономической оптимизации сетей исследовалось В.Я. Хасилевым [159] - [162] и затем Б.М. Кагановичем [64]. Как отмечалось выше, замыкающие соотношения ОРР имеют совершенно иную природу и изучаются в этой работе.

Развитые в ТГС методы оптимизации сетей и решения обратных задач потокораспределения (идентификации) подробно изложены в [119], [120]. Развитие методов оценивания параметров рассмотрено в монографии [126]. В ней описаны задачи статистического оценивания параметров, имеющие общее значение для трубопроводных и гидравлических систем различного типа и назначения и возникающие при их идентификации, оценивании и прогнозировании состояний, системной диагностике, управлении режимами. Представлены основные положения методики гибкого статистического оценивания, инвариантной к составу и свойствам привлекаемой информации; принципы построения и основные формы стохастических линеаризованных моделей гидравлических цепей с сосредоточенными, переменными и распределенными параметрами; методы численного оценивания при разнохарактерной информации, многократных измерениях, неизвестных параметрах распределения ошибок.

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

В монографии [65] развиваются основные положения теории гидравлических сетей применительно к миогоконтурным гетерогенным системам со сложным фазовым и химическим составом потоков. На языке математического программирования излагаются экстремальные термодинамические модели таких систем.

Так же, как и в теории гидравлических сетей, в моделях ОРР потокораспределение существенно зависит от замыкающих соотношений. В связи с этим представляется необходимым анализ этих соотношений, полученных на основе задач производителя и потребителя микроэкономики.

Подобный анализ известен в литературе, в основном он проводится на основе графического анализа, (см. например [259], [168]), но известен и более глубокий математический анализ [21], [22], [50]. В данной работе эти исследования дополняются и показывается, что получаемые замыкающие соотношения могут быть возрастающими, кусочно-непрерывными, кусочно-дифференцируемыми функциями. Все это, в свою очередь, накладывает ограничения на применяемые методы. Так методы ньютоновского типа, развиваемые в [120], будут иметь ограниченное применение для анализа моделей ОРР. Замыкающие соотношения могут быть и разрывными, из этого могут возникать новые задачи анализа и несколько иные методы решения.

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

Первое развитие модели ОРР, которое мы получаем от задач потокораспределения, - замена замыкающих соотношений fjyv) экстремальными задачами арбитражера, представление нефиксированных отборов Q=Q(P) через разность между потреблением и производством в вершине и замены их так же соответствующими экстремальными задачами потребителя и производителя, которые используют соответствующие функции полезности [211] и производственные функции [72], нашедшие широкое применение в микроэкономических исследованиях [174]. Эта замена требует уточнения характера взаимодействия субъектов. Мы рассматриваем случаи, когда все субъекты являются совершенными конкурентами, т.е. для них цены в вершинах являются параметрами.

Однако модель ОРР не охватывает экономических взаимодействий с рынками других продуктов (многопродуктовый рынок), необходимых как для описания производства, так и потребления [113]. В настоящее время основной многопродуктовой моделью, описывающей выпуск - потребление в различных отраслях, является модель межотраслевого баланса (МОБ) [114]. Однако в ней существует ряд ограничений, сужающий ее применение [62]:

1) каждый продукт выпускается только одной отраслью;

2) в каждой отрасли имеется единственная технология производства выпускаемой ею продукции;

3) нормы производственных затрат не зависят от объема выпускаемой продукции;

4) не допускается замещения одного сырья другими.

В ней также не отражены рыночные взаимодействия отраслей. Методы достижения состояния, являющегося одновременно состоянием рыночного равновесия и состоянием эквивалентного межотраслевого обмена, изучаются в работе [11].

Модель межотраслевого баланса можно назвать сосредоточенной, подчеркивая тем самым концентрацию модели межотраслевого взаимодействия. Ее «рассредоточением» является модель межрегионального межотраслевого баланса (ММОБ), описывающая не только балансовые, но и экономические взаимодействие регионов [42], [149].

Представление задач субъектов рынков в виде экстремальных задач позволило объединить модели ОРР (отраслей) межотраслевыми связями в одной сетевой статической модели в равновесном состоянии. Каждое предприятие может получать факторы производства с других рынков. Получившаяся модель является развитием МОБ и названа моделью многопродуктового рассредоточенного рынка (МРР) [100], [102].

Из ограничений МОБ в ней останется следующее. Каждое предприятие выпускает только один вид продукта, но каждое предприятие, выпускающее этот же вид продукта, имеет право на собственную технологию. В модели МРР в явном виде регионы не выделяются, однако не составляет большого труда ввести принадлежность субъектов каким-либо образованиям (административно-территориальным, кооперативным и т.д.) и осуществлять моделирование с учетом их влияния (налоги, субсидии, и т.д.) [168]. В отличие от модели ММОБ, где регион следует считать единым производственно-хозяйственным комплексом, субъекты данной модели позиционируются как самостоятельные и принимают решения на основе критерия максимизации прибыли.

По своей структуре модели рассредоточенного можно отнести к классу моделей функционирования конкурентной экономики по Вальрасу [124], [172] концепция экономического равновесия которой в современной экономической теории занимает центральное место. Среди создателей этих концепций Л. Вальрас, Дж. Хикс, П. Самуэльсон, А. Вальд. Основополагающими работами в этом направлении следует считать работы Кеннет Эрроу и Джерард Дебре [179], Л. Мак-Кензи [222], которые заложили основы современных математических моделей замкнутой децентрализованной экономической системы. Эти модели и их обобщения настолько общие по постановке, что, видимо, могут включить в себя и модели МРР, но при этом теряется наглядность, возможность применения многих численных методов, используемых в ТГС, а также методов, разрабатываемых в данной работе.

Идеи равновесия является ключевой в современных экономико- математических исследованиях [1], [13], [14], [23], [45], [48], [130], [135], [139], [140], [146], [228], [241], - [244], [261]. Работа [146] посвящена взаимосвязи ряда физических моделей и методов теории равновесия с моделями экономики. Последние 40 лет были отмечены обширным потоком работ, обобщающих результаты Эрроу - Дебре в самых различных направлениях. Одним из таких направлений являлось ослабление предположений, при которых гарантировалось существование состояния конкурентного равновесия. Работы таких авторов, как Мас-Колелл [221], Ауманн [177], Хильденбранд, Гейл и ряд других. Интересные результаты в последние годы в этом направлении получены В.М. Маракулиным, М. Флорензано, П. Гурделем, А.В. Коноваловым [204], [225].

С начала 70-х годов в экономико-математической литературе появились исследования моделей экономики с бесконечным числом продуктов. В этих моделях в качестве параметров, характеризующих продукт, можно принять пространственную (аналог рассредоточенного рынка) и временную его характеристику. Одной из первых работ этого направления можно считать работы Пелеги и Ярри [238]. В своей работе Бьюли [188] установил существование состояний равновесия в модели типа Эрроу - Дебре с конечным числом экономических агентов, в которой в качестве пространства продуктов было избрано пространство существенно ограниченных измеримых функций (см. также [194]). Перспективным направлением являются исследования [192], [193], изучающие состояния равновесия с неделимыми товарами.

Большую теоретическую значимость в этом направлении исследований имеют порядковые структуры пространства продуктов, впервые рассмотренные Крепсом [226] линейные решётки введены в теорию конкурентного равновесия Алипрантисом и Брауном (см. [3], [175]). В последствии решеточная структура пространства продуктов использована Мас-Колеллом [219], (обзор литературы в [220]). Основные достижения 80-х годов в равновесном анализе моделей с бесконечным числом продуктов изложены в монографии Алипраптиса, Брауна и Беркеншо [176]. Из более поздних работ следует отметить работу Мас-Колелла и Ричарда [220], которые установили существование равновесия в моделях с пространством продуктов, описываемым как линейная векторная решетка. В последующих работах [195], [203], [239], [257], вопросы существования равновесия установлены при нетранзитивных и неполных предпочтениях экономических агентов.

Важным направлением общего бесконечномерного равновесного анализа являются динамические равновесные модели с перекрывающимися поколениями экономических агентов. Обзор этих работ смотри в [207]. В этом классе моделей множество временных периодов жизни экономики счетное, число экономических агентов также счетное, в каждом временном периоде их число конечное, В работе [264] Вильсон установил существование последовательности равновесных цен, соответствующих периодам жизни экономики при условии, что, либо каждый агент обладает только конечно живущими ресурсами, либо имеется конечная группа агентов, обладающая положительной долей всех ресурсов экономики во всех периодах ее жизни. В работе [48] В.И. Данилов получил ряд обобщений в этом направлении, которые позволили дать лучшую, чем у Вильсона экономическую интерпретацию равновесных цен. В последнее время в этом направлении работали и получили ряд результатов другие авторы [195], [ 203], [247]. Другим направлением, началом которого была попытка обобщить модели Эрроу - Дебре и более адекватно отразить в моделях функционирование финансового сектора реальных экономик, являются неполные рынки, учитывающие как неполноту информации, так и неопределенность будущего. В экономике совместно с рынками обычных продуктов сложились рынки финансовых инструментов. Целью этих рынков является решение задач, связанных с неопределенностью будущих событий (см. обзор [246]). Развитие модели Эрроу - Дебре в этом направлении дало теорию неполных рынков (см. [206], [218]).

Концепции теории равновесия использовались и для анализа плановой экономики [10], [26], [29], [33], [49], [141]. Известен ряд монографий, содержащих элементы теории равновесия и ее приложения [9], [69], [116], [124], [149].

Классическая теория равновесия основывается на предположение о возможности установить цены в равновесном значении. Развитием равновесного подхода являются ряд теорий функционирования экономики при неравновесных ценах [140]. Наибольшее развитие получили идеи Хикса [167] Барро и Гроссмана [180], достаточно общие постановки приведены в [17], [265], [185], [198] Полное изложение этих идей и их развитие приведены в монографиях [18], [139], [185].

Наибольшее полное развитие идей рассредоточения получили в геоэкономических исследованиях [142], международной экономике [109], а также в межрегиональной экономике. О взаимосвязи межрегиональной и международной связей можно найти в работе [215]. Межрегиональная и международная торговля уменьшает замкнутость экономик и использует преимущества разделения труда [107], [216]. Так в работе [130] приведены исследование влияния международной торговли и валютных обменов на экономический рост. В условиях глобализации экономики все большее развитие получают транснациональные компании, территориально расположенные в целом ряде стран [107]. Пространственная рассредоточенность и взаимосвязь субъектов мирового хозяйства отражена в научных изданиях [33], [34].

Математические методы уже давно используются для изучения международной торговли. Большое количество различных моделей, предназначенных для исследования международной торговли, территориального планирования и т.д. [118], [208], [209] основано на идеях равновесия. Наиболее близким разделом математической экономики, который могут описать модели рассредоточенного рынка, является раздел, описывающий международную торговлю и экономическое взаимодействие крупных экономических регионов [43]. В западной литературе эти вопросы исследуются в теориях международной торговли, основные идеи которых заложены в трудах Тюнена, Вебера, Леша, Айзарда. Следует отметить работы Кавеса, Франкеля, Джонса [190], Кругмана [214], Обсфельда [215], [109], в которых разбираются вопросы, связанные с зонами свободной торговли, общих рынков, таможенных, монетарных, экономических союзов. Однако наиболее строгие положения, утверждения и результаты получены в малоразмерных моделях (1-2 продуктовые и 2-3 региональные). В этой области следует отметить работы Баласса [181], Робсона [249], Трумэна [258], Викермана[262].

Для моделирования товарных потоков между парами стран сконструированы специальные эконометрические модели, получившие в литературе наименование гравитационных [46], которые по своей идее близки к моделям потокораспределения в гидравлических сетях, В общем случае гравитационная модель представляет собой эконометрическую функцию, связывающую товарный поток из страны или региона / в страну или регион/ с факторами экономического и социального характера, а также с издержками по продвижению потока из / ву:

где Efjj-- экспорт из страны (региона) і в страну (регион)у ; Z"i, Z!j - факторы, определяющие потенциальное положение стран; R ij факторы, относящиеся к продвижению товарного потока из і в у. (переменные, отображающие наличие барьеров на пути из і в у, типа расстояния между ними и т. п.). Для данного типа моделей широко известны модель Тинбергена [256], П. Поихонена [245], X. Линнемана [227], П. Васархелги [260]. Следует также отметить работы Брада, Мендеса [189], Бергстренда [185], [186]. Все эти модели основаны на мультипликативных эконометрических функциях и отличаются количеством и качественным составом параметров, входящих в Z ,, 2?j, R jj. Модель Эли Хекшера и Бертиля Олина связывает международную торговлю с распределением ресурсов, ее математическое описание приведено в [212].

По нашему мнению, математические модели рассредоточенного рынка, как совокупность взаимосвязанных локальных рынков, являются удобным аппаратом для описания этих проблем. Как отмечалось выше, в этих моделях в явном виде страны и регионы не выделяются. Но в условиях рыночной экономики любая территория представляет собой совокупность самостоятельных индивидуумов, ведущих на этой территории производственную деятельность, связанных между собой как на самой территории, так и за ее пределами [106]. Задачи исследований, связанные с изучением взаимодействия локальных рынков, поставлены достаточно давно [250], [251], [252] и остаются актуальными до настоящего времени как в теоретическом, так и в прикладном аспектах. Среди зарубежных исследований взаимодействия локальных рынков в России известны следующие работы: в [205], [223] изучается межрегиональный разброс цен и тенденции его изменения в России, предметом исследования в [183] являются ценовые взаимосвязи между локальными рынками. Из отечественных работ приведем [147], [59]. Первая посвящена типологии российских регионов по характеру поведения цен, вторая - выявлению причин различий цен в разных регионах. В работе [37] на данных о динамике уровней цен продовольственных и промышленных товаров по регионам Западной Сибири за 1994 - 1998 гг. изучается, имеет ли место сходимость к единой цене.

Среди работ, изучающих пространственный разброс цен в странах с развитой рыночной экономикой, приведем [199] и [236]. В статье [237] приведены результаты исследования разброса цен между городами США. Следует отметить, что исследования, проведенные в работах [38], [59], [147], [183], [199], [205], [223], [236], [237] основаны в большинстве на построении и анализе эконометрических моделей.

Теории международной торговли и таможенных союзов давно вошли в учебники по моделированию [46], написаны специализированные учебники [109], [253]. Современный уровень регионалистики и межрегиональных взаимодействий отражен в учебной литературе [41].

Как отмечалось выше, большое количество различных моделей, предназначенных для исследования международной торговли, территориального планирования и т.д., основаны на теории равновесия. Различают два типа моделей: модели частичного и общего равновесия. В моделях первого типа речь идет только о равновесии между предложением и спросом по конкретным видам товаров. Модели второго типа рассматривают все рынки продукции, а также рынки рабочей силы и капитала. Такие модели, как правило, сильно агрегированы (включают всего несколько отраслей и прочую экономику), модели частичного равновесия, сильно дезагрегированы. Хотя литература по данному вопросу и достаточно обширна, однако в большинстве случаев она касается конкретных исследований и мало затрагивает математические методы, используемых в них. Исследования, в которых использовались модели частичного и общего равновесия, проводились в США, Нидерландах, Австралии, ФРГ, во Франции, ряде международных организаций, например, ОЭСР, Международном институте анализа прикладных систем (Австрия) и т.д. Значительное число исследований посвящено изучению влияния внешнеторговой политики на развитие АПК (более подробно см. [70]). Модели общего равновесия использовались Службой экономических исследований Министерства сельского хозяйства США, была разработана 10-секторная модель общего равновесия страны [248], а так же 30-секторная модель аграрной политики США [224]. Модель общего равновесия ORANI разработана в университете города Мельбурн [197]. Эта модель включала 113 производственных отраслей, 115 категорий товаров, производимых национальной экономикой, и такое же количество импортных товаров, 9 категорий трудовых ресурсов, 7 типов обрабатываемых земель. Модель была создана во времена, когда еще не было эффективных программных средств для решения задач такого класса. Опыт, который был получен в ходе разработки данной модели, использован в постоянно развивающемся проекте в области внешней торговли GTAP (Global Trade Analysis Project) [254].

Практическое использование такого рода моделей связано с разработкой программного обеспечения «GAMS» (General Algebraitic Modeling System -общая алгебраическая система моделирования), представляющую собой систему, реализующую язык заданий в удобной для пользователя форме математического программирования. Одной из первых моделей общего равновесия, реализованной с помощью данной системы, была модель Камеруна [217].

В качестве системы примера модели частичного равновесия можно привести систему моделирования FAPRI (FAPRI Modeling System) [255]. С ее помощью в институте изучения продовольствия и сельскохозяйственной политики (FOOD and Agricultural Policy Research Institute, FAPRI) при Центре изучения развития сельского хозяйства и сельской местности Университета штата Айова (Center for Agricultural and Rural Development, CARD) проводились исследования по анализу влияния на функционирование сельского хозяйства торговой политики США, а также ряда других стран.

Для анализа политики в области международной торговли Службой Экономических исследований Министерства сельского хозяйства США разработана система моделей, получившая название SWOPSIM (A Static Word Policy Simulation Modeling Framework). Система включает мощную базу данных, содержащую информацию в области производства, потребления и торговли продовольствием для большинства стран мира [263]. В настоящее время SWOPSIM непрерывно совершенствуется и широко используется на практике. Ее продолжением явилось создание DWOPSIM (A Dynamic World Policy Simulation Model Building Framework), позволяющая проводить моделирование экономических систем в динамике.

Существует также множество моделей, которые разрабатывались в рамках диссертационных исследований для целого ряда развивающихся стран мира. Подробный анализ этих моделей проведен в [70].

Одной из основных моделей по анализу экономической политики в области сельского хозяйства для стран СНГ является модель EPACIS. В ней внешнеторговые связи разделяются на две составляющие: торговлю между странами СНГ и торговлю со странами дальнего зарубежья. Модель подробно анализирует двусторонние торговые потоки. Это позволяет наблюдать не только за изменением сальдо сельскохозяйственной торговли, но и детально анализировать ситуацию по каждому продукту или продуктовым группам, используемым в модели [203]. Описанию современной Российской экономики с применением теории экономического равновесия посвящена работа [44].

Математические модели экономического равновесия породили ряд работ, связывающих динамику с равновесием [117], [178]. Равновесие и асимптотический рост изучались в работах, [130], [135] - [138]. В работе [130] изложены общие положения, модели и методы системного анализа развивающейся экономики. Модели описывают ряд качественных особенностей эволюции плановой и рыночной экономики, экономики СССР и России в переходной период 1991-1995 гг. [1], [128], [131]. В работе [196] описывается значение фактора времени в теоретическом анализе отдельных отраслей индустрии, и всей экономики в целом. Реальное развитие экономики показывает, что есть территории развивающиеся, есть деградирующие, и это порой мало связано с наличием и отсутствием ресурсов, причем возможен переход из одной крайности в другую. Теоретический анализ межтерриториальных аспектов динамики при большом количестве территорий, основанные реальных данных, вряд ли выполним. Основная проблема здесь заключается в сложности этих задач. Одним из подходов в решении этой проблемы является применение имитационного моделирование и имитация динамики, заложенная в работе Дж. Форрестера «Мировая динамика» [158].

Исследования на основе численного эксперимента межрегиональной динамики развиваются в работах [42], [41], [191]. В данной диссертационной работе, следуя принципам моделирования динамических систем [63], [108], [158] строятся динамические модели многопродуктового рассредоточенного рынка, представляющие собой последовательность взаимосвязанных равновесных состояний. Динамическая модель позволяет, учитывая потребление восполнимых и невосполнимых ресурсов, прогнозировать развитие как системы в целом, оценивая ее значением внутреннего валового продукта (ВВП), так и отдельных ее субъектов, оценивая их, например, величиной добавленной стоимости выпускаемой ими продукции. Становится возможной также имитация управляющих воздействий на систему для регулирования рыночных отношений.

Одним из направлений, бурно развивающимся в настоящее время и связанным с развитием модели Эрроу-Дебре, является «Равновесное программирование» [5]. За сравнительно небольшой период времени в этой области знаний произошел значительный прогресс в теории и методах нахождения решения равновесных задач различных типов (включающих, например, вариационные неравенства, задачи дополнительности, задачи о седловой точке и об игровом равновесии). Различные постановки задач ценового равновесия и их свойства приведены в [9], [16], [139], [152], [210], [19]. Методы решения и библиографический обзор приведен в работе Коннова И. В. [105].

Внутри этого направления выделяется направление - «сетевая экономика», развиваемое школой А. Нагурней [231] - [235]. Основные модели, рассматриваемые в этих работах, основаны на свойствах состояний равновесия в экономических системах, для поиска применяются методы решения вариационных неравенств. Модели и методы, развиваемые автором, также можно отнести к этому направлению, однако в отличии от последних, рассматриваются и развиваются модели и методы, получившие широкое применение в теории гидравлических сетей, эффективность которых подтверждена многолетним использованием. Стохастические модели равновесия на графах рассматривались так же в работах [134], [202].

В силу исторического развития, экономическая наука в СССР имела направленность оптимального планирования. Основоположниками этого направления являлись Л.В. Канторович [67], [68], В.В. Новожилов [127], А.Л. Лурье [115]. Дальнейшее развитие эти идеи получили в трудах [2], [10], [11], [40], [169]. Работы этого направления стимулировало развитие методов оптимизации и исследование операций [39], [54], [173], [200], [201], исследование операций и системного анализа [35], [36], [123], [132]. А также их развитие и применение в системах энергетики [61]. Задачи линейного программирования получили большое развитие в направлении решения задач большой размерности и соответственно получили развитие идеи децентрализации планирования [24]. Появилось направление «региональное программирование» [165], [166].

В соответствии с современной экономической теорией, агенты экономических систем описываются экстремальными задачами. Один из методов анализа этих систем основывается на построении по экстремальным задачам функций спроса и предложения с последующей увязкой их. Задачи построения функций спроса и предложения входят в состав задач параметрического программирования, наиболее изученным классом которого являются линейные задачи оптимизации [173]. Результаты работ [22], [116] связанные с экстремальными свойствами равновесных состояний (например, теорема о благосостоянии) дают основание предполагать, что более перспективным является направление, использующее численные методы решения многокритериальных задач, которые активно развиваются в [27] [38], [53], [55], [56], [73], [133], [151], [165], [171]. Отмеченная в диссертации взаимосвязь моделей МРР, в которых конечные потребители минимизируют затраты при ограничениях уровня полезности, с задачами централизованного управления, дает основание предполагать, что для анализа моделей МРР будут применяться численные методы решения экстремальных задач.

Задачи прогнозирования социально-экономического развития различных экономических систем являются важными и характеризуются сложностью расчетов, неопределенностью исходных данных [170]. Оценка принимаемых решений, как правило, осуществляется по многим показателям, при этом могут быть использованы неформализованные правила оценки. Для принятия решения в таких ситуациях обычно рассматривают несколько сценариев развития и, используя формальные и неформальные методы анализа, выбирают один из них, который рекомендуют для внедрения. Аналогичный подход применяется при проектировании сложных производственно-технологических систем (многовариантное проектирование). Многовариантный анализ (проектирование) в настоящее время является основным способом, помогающим принимать решение, Основной задачей при этом является уменьшение числа вариантов проектов, которые должны быть подвергнуты окончательному анализу, так как общее число вариантов, как правило, чрезмерно велико. Традиционные способы применения методов оптимизации позволяют определять оптимальные решения по какому-либо одному критерию оценки качества проекта. Однако по вышеперечисленным причинам такие оптимальные решения могут оказаться не приемлемыми для внедрения. Очень часто решения, близкие к оптимальному, то есть незначительно (на некоторую заранее заданную величину R 0) отличающиеся по значению критерия от оптимального, более подходят для внедрения.

В моделях МРР поведение субъектов рынков описываются экстремальными задачами, однако в действительности, в силу многих причин, редко кто из субъектов решает эти задачи. Для описания конечного потребителя используется функция полезности, которая является «правдоподобной» абстракцией. Трудно однозначно определить, действительно ли он максимизирует полезность при бюджетном ограничении, или минимизирует затраты на достижение определенного уровня полезности, да и вообще, решает ли моделируемый субъект эти задачи. В связи с этим возникает потребность в отыскании не только оптимальных решений, но и близких к ним. Подход к решению экстремальных задач, основанный на отыскании близких решений аппроксимирующей задачи, предложенный В.Р. Хачатуровым в аппроксимационно-комбинаторном методе, позволил ему найти ряд модификаций известных методов оптимизации и расширить их применение для решения новых классов задач [164], [165]. Эти методы получили широкое развитие, применение [7], [20], [75] - [79], [80], [91], [92] и описаны в [81] [86], [166].

Заметим, что методы отыскания решений, близких к оптимальным, в задачах дискретного программирования известны достаточно давно. Сюда можно отнести работы Р. Беллмана, С. Дрейфуса [15], Р. Калабы [66], [182], К. Мурти [230], М. Поллака [240], В. А. Емеличева, В. И. Комлика [57], С. С. Лебедева [112]. Эти методы направлены на получение решений, близких к оптимальному, в порядке неубывания (для задач минимизации) значений их функционалов.

Методы динамического программирования Р. Беллмана имеют широчайшую известность и широчайшее применение [15]. Большое развитие получили эти методы и в теории гидравлических сетей. Они являются основой математических методов оптимизации выбора параметров трубопроводных, электроэнергетических и других физико-технических систем, имеет большую историю, отраженную в весьма обширной литературе (обзор см. в монографии [120]). Развитие вычислительной техники и методов математического программирования (в частности дискретного) стимулировали разработку новых подходов и методов теории гидравлических сетей [121]. Для решения задач проектирования трубопроводных систем стали применяться различные схемы последовательного анализа вариантов. Пионерскими в этом направлении были работы B.C. Михалевича, Н.З. Шора и других сотрудников Института кибернетики АН УССР [28], [58], [122]. Получили развитие методы динамического программирования. В этом направлении следует отметить также работы сотрудников Сибирского энергетического института [120], [121], [129], [163], М.Г. Сухарева и Е.Р. Ставровского [153], [154] и др. Динамическое программирование, применяемое ранее для оптимизации линейно-упорядоченных процессов, стало использоваться для оптимизации процессов, заданных на ориентированном дереве [6], [187], [229]. В работе [74] приведен вывод функционального соотношения Беллмана для такого вида задач, которое получило дальнейшие развитие и модификации в [86], [87], [89]. В работах [90], [120], [213] описано программное обеспечение решения задач оптимизации гидравлических систем различного назначения, где основным методом является динамическое программирование.

Диссертация состоит из введения, 4 глав, заключения, списка литературы и приложений.

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

- конечные потребители этого продукта;

- предприятия, производящие его;

-агенты, осуществляющие экспортно-импортные операции за пределы моделируемой системы;

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

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

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

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

Для того чтобы оценить применимость методов теории гидравлических сетей в задачах отыскания равновесных состояний модели ОРР, необходимо знание характеристик функциональных зависимостей, описывающих замыкающие соотношения. В теории гидравлических цепей эти зависимости, как правило, описываются зависимостями (0.4) - (0.6), где для практических целей достаточно, чтобы /3=2, В одной из первых работ по ОРР [99] для этих целей предлагалось использовать степенные функции, что соответствует производственным функциям и функциям полезности Кобба-Дугласса. Согласно современному микроэкономическому анализу, агенты рынков описываются экстремальными задачами, поэтому замыкающие соотношения могут быть получены как функции их спроса и предложения. Доказано, что если в задаче производителя используемая производственная функция удовлетворяет основным своим свойствам [72], а так же характеризуется убывающей отдачей от масштаба производства, то функции предложения у{Рх,Ру) и спроса на факторы производства xt(Px,Py), где Рх - вектор цен факторов производства, Ру - цена выпускаемой продукции, - непрерывные, дифференцируемые и возрастающие по Ру 0, - при неограниченном росте Ру функции х Рх,Ру), ieN, у(Рх,Ру) возрастают неограниченно.

- функции х, (Рх,Ру) непрерывные и дифференцируемые и убывающие по переменным РХІ - у(Рх,Ру) -» 0, х(Рх,Ру) - 0„ при Ру- 0.

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

Проведенный на основе численного эксперимента анализ задачи производителя с производственными функциями Кобба-Дугласа, CES (Constant Elasticity of Substitution), которые были с постоянной и возрастающей отдачей от масштаба производства, показал, что поведение функций предложения имеет следующий характер. Интервал изменения цены Ру [О, со) разбивается на полуинтервалы [0,Ру\), [РуиРуг), [Руг,Руг),..., [Ру„ х ), внутри каждого из полуинтервалов функция у(Рх,Ру) описывается функцией, поведение которой близко к степенной, причем на интервале [0, Ру\) у(Рх,Ру) = 0, в точке Рух разрыв, во всех остальных точках Ру\, Ру2, Руъ--- функцияу(Рх,Ру) непрерывна. Графический анализ, проведенный в различной учебно-методической литературе по микроэкономике [30] с целью построения функций предложения предприятия в коротком периоде, показывает, что эти функции имеет аналогичный характер поведения.

Также проведен анализ функций x=x(Px,BD) спроса, построенных на основе задачи потребителя, где Рх - вектор цен на потребляемые продукты, BD величина бюджета. В экономической теории эта функция, называемая функцией маршаллианского спроса, достаточно хорошо изучена. Согласно работе [21], эти функции непрерывные по переменным Рх, BD. Для обычного товара і (большинство товаров являются обычными товарами) объем потребления xi=xi(PxhPxi.,BD) (здесь и в дальнейшем такая запись означает, что в векторе Рх зафиксированы все переменные, кроме переменной Рх,) как функция от PXJ возрастающая [168]. В работе показано, что гладкость функций Xj (Pxh РХІ-, BD) может быть нарушена в конечном числе точек, а также приведен ряд интересных соотношений, не являющихся широко известными в работах по микроэкономике.

В том случае, когда в пункте несколько (конечное число) конечных потребителей, каждый из них обладает своей функцией полезности и своим бюджетом (фактор расстояния в пределах одного пункта не существенен), коллективный спрос пункта можно описать кривой коллективного спроса х(Рх). Эта функция непрерывна по переменной Рх, но функции dx,(Pxj, Px /dPxj терпят разрыв конечное число раз.

Пусть в некотором пункте / расположено несколько потребителей и несколько производителей продукции. Кривой предложения-спроса будет функция WSi(Pi), где Pt установившаяся в пункте цена на продукт. Если производственные функции строго выпуклые, их эффект масштаба убывающий, то WSi(Pi) будут непрерывными, возрастающими, кусочно-дифференцируемые. В противном случае WSi(Pi) может быть возрастающей, кусочно-непрерывной, кусочно-дифференцируемой.

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

Проблема равновесия, устойчивости, существования устойчивого равновесия является ключевой при анализе различного вида систем и, в частности, самоорганизующихся систем. В этой главе проводятся исследования функционирования ОРР [101] [103] в целом при предположениях, которые часто используются в экономико-математическом моделировании, вытекают из анализа функций спроса и предложения, а также в предположении, что поведение субъектов каждого пункта приводит к его равновесию [168]. Эти исследования проводятся на модели распространения неравновесных состояний по сети. Для этого вводятся функции NBi (функции избыточного предложения вершины і (-NBi функция избыточного спроса)), зависящие от цены в соответствующей вершине, которые являются мерой нарушения равновесия локальных рынков, и ASNB= Z{JVB,-: ієЕ2}, MNB= max{\NBj\: ієЕ2}, которые являются мерой нарушения состояния равновесия системы в целом. Доказываются ряд утверждений, отражающих сетевые свойства рассредоточенного рынка, анализируется процесс распространения и затухания неравновесных состояний по сети. Для доказательства существования состояния равновесия и равновесных цен разработан алгоритм вытеснения избыточных предложений, являющийся одной из модификацией алгоритма поузловой увязки сети. Доказательство приведено для случая, когда замыкающие соотношения zJv(APv) = фУ(Р/і2(у) Р/іі&)) удовлетворяют следующим свойствам:

1)непрерывны;

2) строго возрастающие по APV;

3) при изменении APV в пределах области определения ф v изменяются от -оо до +оо;

4) для всех ve V существуют числа /v, Lv (Lv /v 0) такие, что при любых ДРГ и ДР у выполняются неравенства / v - AP Y - APV \ [ф v (Д/\) - v (Д Ж 1у-ДР у-ДРу.

Доказанные теоремы позволяют провести некоторые выводы из анализа функционирования систем, описываемых моделью ОРР:

- распространение неравновесных состояний представляет собой аналог волновых процессов;

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

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

- для управления экономической системой важным является вопрос об ускорении процесса перехода системы с состояние равновесия. Становится ясным, что введение фиксированного отбора и свободной цены в одном или нескольких пунктах (вершине сети) не приводит к ускорению стабилизации состояния равновесия. Ускорению процесса стабилизации способствует введение фиксированной цены и свободного отбора в них, а также стимулирование производства и потребления. Однако следует заметить, что в этом случае субъекты вершины должны обладать такими мощностями по производству (либо потреблению), чтобы компенсировать возможное возникновение избыточного предложения (или спроса) вершины. Приведенный в работе алгоритм может быть реализован на ЭВМ и использован для анализа конкретных систем в режиме имитации, как в случае выполнения достаточных условий, так и в противном случае. Приведенные теоремы являются доказательством его сходимости и выполнены при весьма существенных предположениях относительно функции ф]/(АРу), которые могут быть нарушены. В самом общем случае функции фу(АР) могут быть кусочно-непрерывными, поэтому для поиска состояния равновесия приходится использовать специальные приемы, сводящиеся к непрерывной аппроксимации. Следует также отметить, в этих случаях состояние равновесия может быть не единственным. Аналогичные ситуации возникают при анализе, например, водопроводных систем в условиях избыточного водопотребления. При включении всех водопотребителей задача потокораспределения решения не имеет решения, при отключении по крайней мере одного из них, эта задача разрешима.

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

Широко применяемым и эффективным методом для расчета потокораспределений в гидравлической сети является метод поконтурной увязки. Наиболее полное его изложение можно найти в [120], исследование сходимости изложено в [153], смотри также работы [144], [145]. Для применимости метода поконтурной увязки требуется, чтобы задача была приведена к циклической схеме, т.е. к постановке с фиксированными отборами. Теоретическими предпосылками метода поконтурной увязки являются:

1) второй закон Кирхгофа. В терминах МРР оно формулируется так. По любому циклу сети сумма изменений цен при его обходе равна нулю;

2) возможность отыскания начального потокораспределения, допустимых Первому закону Кирхгофа;

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

4) утверждение, что из выполнения Первого закона Кирхгофа по системе фундаментальных циклов, следует его выполнение для любого цикла.

Эти предпосылки позволяют сформулировать алгоритм поконтурной увязки, который применим для отыскания равновесного состояния модели ОРР.

При анализе реальных экономических систем из статистической отчетности величины потоков и цены на рынках известны, и часто они не удовлетворяют соотношениям модели ОРР. Как правило, неизвестными являются параметры кривых фу, и именно эти кривые часто представляют практический интерес. Одной из наиболее распространенных производственных функций, применяемых в микроэкономических исследованиях, является функция Кобба-Дугласа. Функции спроса и предложений, построенные с применением этих производственных функций (см. Приложение 1), представляют собой кусочно-степенные функции (степенная на конечном числе интервалов области определения). Это справедливо и для функций спроса, построенных на основе функций полезности Кобба-Дугласа в задаче конечного потребителя. Для случая, когда f v(yy)=Av-yv-\yv\ccv, где AV .Q, 0 1+«V 1, рассматривается задача отыскания значений переменных Av, потоков yv, veV, отборов в вершинах и цен, удовлетворяющих модели ОРР и минимизирующих функционал - взвешенную сумму квадратов отклонения этих значений от замеренных (заданных) значений. Критерий оптимальности этой задачи, построенный на основе функции Лагранжа, дает систему уравнений, представляющую собой суперпозицию двух моделей ОРР:

1) модель относительно продуктовых потоков и продуктовых цен;

2) модель относительно лагранжевых потоков и лагранжевых цен (множителей Лагранжа).

Для отыскания решения этой системы предлагается применить алгоритм, представляющий собой суперпозицию двух алгоритмов поконтурной увязки [93], [94], [96].

Во второй главе модель ОРР представляется как система экстремальных задач. Согласно современным экономическим теориям, описание поведения субъектов через функции предложения производителей г},(Р,), функции спроса конечных потребителей (Р/) функции (кривые) экспортно-импортного сальдо z P,) можно вывести из соответствующих экстремальных задач [168]. Поэтому в исходной модели ОРР эти функции заменены соответствующими экстремальными задачами. Как и выше, структура рынка описывается графом G=(E,V,H), для задания граничных условий множество вершин Е разбито на подмножества Е[, Е2 и Е3, где Е[ множество вершин с фиксированными ценами Р І и свободным отбором Bh Е - множество вершин с фиксированным отбором и свободной ценой, в вершинах из Я3 объем внешнеторгового сальдо связан с ценой функциональной зависимостью. Каждый из субъектов описывается своей экстремальной задачей. Конечное потребление в вершинах ієЕ описывается задачей максимизации полезности при бюджетных ограничениях. Производство в вершинах ієЕ опивается задачей максимизации прибыли при ограничениях, задаваемых производственными функциями и объемами располагаемых факторов производства. Для каждой дуги veK, которые интерпретированы как торгово-транспортные коммуникации (системы) и по которым арбитражер осуществляет транспорт потока, рассматривается следующая задача. Максимизировать прибыль, зависящую от разности цен между граничными вершинами, объема транспорта, затрат на факторы производства (транспорт). Объем транспорта определяется производственной функцией и объемами факторов производства, задаваемых на дугах. В условиях равновесия объемы внешнеторгового сальдо, производства, потребления, ввоза-вывоза арбитражерами сбалансированы, поэтому выполняются условия продуктового баланса. Все локальные рынки считаются рынками совершенной конкуренции, поэтому субъекты являются ценополучателями. В их экстремальных задачах переменные, интерпретируемые ценами, являются параметрами.

Методы поузловой и покоитурной увязки являются основными при отыскании потокораспределений в теории гидравлических сетей. Для отыскания равновесных состояний в 1 главе рассмотрена применимость этих методов при условии, что функции спроса и предложения, торгово-транспортные кривые и обратные к ним были выражены в явном виде. Однако явный вид этих функций удается получить в достаточно редких случаях. Так, для случая производственных функций Кобба-Дугласа их вывести просто (см. Приложение 1), однако для производственных функций CES функции спроса и предложения не выражались в элементарных функциях. Применить метод поузловой для ОРР в экстремальной постановке не составляет труда. Несколько сложнее с применением поконтурной увязки. Выполнить переход к циклической схеме не сложно. В соответствии с выполняемыми преобразованиями дуги сети принимают следующие соответствия: дуги, соответствующие производителям; дуги, соответствующие арбитражерам; дуги, соответствующие конечным потребителям; дуги, соответствующие агентам, выполняющим экспортно-импортные операции. Для применения поконтурной увязки необходимо для каждой дуги уметь решать задачу: по известному значению yv потока по дуге v определить значение разности цен в граничных вершинах и объемы факторов производства (для дуг, соответствующих конечным потребителям объемов потребления прочих продуктов) таким образом, чтобы получившаяся совокупность давала оптимальное решений экстремальной задачи, соответствующей дуге. Эти задачи относятся к классу обратных задач оптимизации [4], в рассматриваемых постановках их можно решать без явного представления прямых функций спроса и предложения в аналитическом виде. Решение этих задач основано на применении теоремы Куна-Таккера. Для моделей дуг, соответствующих агентам, которые выполняют экспортно-импортные операции, считается, что они заданы аналитически и имею т обратную функцию, поэтому решение рассматриваемой задачи элементарно. Если эти модели представлены экстремальными задачами, то их можно отнести либо к дугам, соответствующим конечным потребитям, либо к предприятиям.

О взаимосвязи задачи потокораспределения и нелинейной сетевой транспортной задаче известно давно [58], и в [120] в связи с этим рассмотрены экстремальные методы ее решения. Наиболее эффективные экстремальные методы связаны с вычислением градиента. Представление ОРР в экстремальной постановке дает новый способ его вычисления, использующего необходимые и достаточные условия экстремальности в форме теоремы Куна-Таккера.

Описание субъектов модели ОРР экстремальными замыкающими соотношениями позволило сформулировать статическую модель МРР. В ней функционирует несколько (т) однопродуктовых рассредоточенных рынков. Так же как и в [114], между отраслями и выпускаемыми ими продуктами установлено взаимно однозначное соответствие. Каждой отрасли s=l,2,3,...,m поставлено в соответствие конечный ориентированный граф GS=(ES, Vs, Hs), описывающий структуру рассредоточенного рынка s-ro продукта, G=(E, V, Н) -их объединение.

Вершины из Es интерпретируются как пункты - локальные рынки, в которых, в соответствии с установившейся ценой, осуществляется обмен продукцией отрасли s между различными ее субъектами. В некоторых пунктах также располагаются предприятия, которые потребляют продукцию других отраслей и производят продукцию данной отрасли. Для этого в граф G введены дополнительные дуги, конкретизирующие потребление факторов производства предприятия из других локальных рынков. Для моделирования конечного потребления выделены специальные (дополнительные) вершины, связанные с локальными различных отраслей.

Так же, как и в модели ОРР, в модели МРР задаются граничные условия на продукт этой отрасли, определяющие их взаимосвязь с внешними системами, В состоянии равновесия цены в вершинах сети должны быть таковы, чтобы выполнялись условия продуктового баланса, которое означает следующее. Объем производства предприятием вершины плюс объем ввоза в вершину из других локальных рынков отрасли минус объем вывоза в другие локальные рынки отрасли минус объем потребления различными предприятиями и конечными потребителями равно граничному условию вершины (т.е. потреблению внешними системами). Это условие является можно назвать первым обобщенным законом Кирхгофа. Обобщение заключается во включение в балансовые соотношения с помощью производственной функции разнородных продуктов.

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

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

Расчет продуктовых потоков модели МРР определяет и движение денежных потоков в ней, направление которого противоположно направлению продуктовых потоков. В результате выводятся формулы для вычисления внутреннего валового продукта (ВВП) системы через добавленные стоимости, произведенные субъектами системы, и через затраты на конечное потребление.

Используя основные принципы построения динамических моделей, заложенные Дж. Форрестером в [158] строится динамическая модель МРР, как последовательность взаимно связанных статических равновесных состояний МРР. Динамическая модель рассредоточенного рынка строится в дискретном времени /=0,1,2,..., Тс постоянным шагом At, величина которого соответствует одному периоду планирования, Т горизонт планирования. Предполагается, что переходные процессы в системе достаточно быстротечны и успевают пройти значительно быстрее, чем длительность одного периода At. Для представления динамических процессов описывается динамика изменения основных элементов моделируемой экономической системы. Процесс моделирования заключается в следующем. Задав значения фондов для начального момента времени t = 0, находим равновесие статической модели МРР. Рассчитав прибыли предприятий, а также объем затраченных невосполнимых ресурсов, пересчитываем значения фондов предприятий и заново ищем равновесное состояние для t=\. Этот процесс повторяем до тех пор, пока не будет найдено равновесие для t=T.

Важнейшим вопросом экономической теории является вопрос сравнения различных структур (совершенную конкуренцию, монополии, монопсонии, олигополии) управления экономической системой [30]. Математические модели МРР включают в себя описание производственно-технологической части экономической системы, а также структуру конечного потребления. Система управления производственно-технологической частью может быть децентрализованной (рассредоточенной), а также централизованной (задача централизованного управления (ЗЦУ)). В ЗЦУ критерием оптимальности всей системы является прибыль, получаемая от ее функционирования. Прибыль включает доход от взаимодействия с внешними системами минус затраты используемые ресурсы транспорте между пунктами системы и минус затраты на используемые ресурсы при производстве продуктов.

Доказывается следующая теорема. Теорема 2.1. Какова бы ни была структура управления экономической системой, прибыль всей системы состоит из прибыли предприятий и арбитражеров за вычетом стоимости конечного потребления.

Сравнение максимального значение прибыли в ЗЦУ со значением прибыли системы, которое может быть получено в равновесных состояниях при различных стратегиях поведения субъектов локальных рынков, определяется следующей теоремой.

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

В работах по микроэкономике, в частности в [30], приведены доказательства того, что среди рыночных структур наиболее эффективной является рынок совершенной конкуренции.

Теорема 2.3. Если в рассредоточенной структуре управления все локальные рынки являются рынками совершенной конкуренции, то оптимальное решение ЗЦУ совпадает с равновесным состоянием многопродуктового рассредоточенного рынка.

Эти теоремы, называемые далее теоремами сравнения, позволяют сделать вывод об эффективности функционирования экономических систем, описываемых этими моделями. Из теорем сравнения вытекают и следующие выводы. Централизованная система управления, целью которой является получение максимальной прибыли при выполнении всех технологических и потребительских ограничений, эквивалентна децентрализованной системе управления экономической системой, в которой каждый субъект является совершенным конкурентом. Если хотя бы один из субъектов при принятии решения не ведет себя как конкурентный, то его поведение может привести всю систему по критерию максимума ее прибыли в неоптимальное состояние. С помощью имитационного эксперимента с простейшей динамической моделью рассредоточенного рынка получено, что если на рынке несколько производителей, максимизирующих прибыль, для принятия решения занимаются изучением рынка, то производитель с наименьшими издержками приобретает монопольную власть. Т.е., является вполне закономерным стремление к выходу любой конкурентной системы из конкурентного равновесия. Определенной гарантией устойчивости конкурентного равновесия является наличие в каждом локальном рынке очень большого числа покупателей и продавцов, что в силу естественных причин не всегда возможно. Как сказано выше, аналогичной эффективностью обладает централизованная система управления экономической системой, и вполне понятно, что это решение не меняется при неизменных внешних факторах. Однако централизованные системы эффективны при ее небольшой размерности. Согласно теореме 2.3, условия оптимальности ЗЦУ и совокупность условий оптимальности агентов МРР в состоянии равновесия совпадают с точностью до обозначений, причем множители Лагранжа в ЗЦУ являются важнейшим параметром описания состояния рынка - ценой товара. Эти факты позволяют заключить, что для синтеза оптимальной системы управления необходимо совмещение централизованного управления с конкурентным децентрализованным. Пункты, в которых очень большое количество продавцов и покупателей, отдаются на откуп «невидимой руке рынка», остальные находятся под централизованным управлением.

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

Модель МРРРК рассматривается как задача выпуклого векторного программирования [73], [88]. Под оптимальностью понимается эффективность по Парето и слабая эффективность (эффективность по Слейтеру) допустимых в ней решений. Согласно первой теореме экономики благосостояния, каждому конкурентному равновесию экономической системы соответствует эффективное по Парето состояние. И наоборот, если функции полезности вогнутые, а множество производственных возможностей фирм является выпуклым, то для любого равновесного состояния по Парето существуют цены, при которых это состояние будет конкурентно равновесным. Таким образом, есть основания для поиска состояний равновесия МРРРК среди Парето-эффективных решений. Содержание этой главы посвящено анализу взаимосвязи равновесного состояния МРРРК и Парето-эффективных решений, а также теоретическому обоснованию и модификациям алгоритмов метода возможных направлений, предназначенных для отыскания слабоэффективных точек задач выпуклого векторного программирования и точек равновесия в модели МРР.

Задача выпуклого векторного программирования рассматривается в достаточно общей постановке (х) - тіп, хєХ, іе М, где Х= {х: xeRn, q t{x) О, /є/}, р,{х) - выпуклые функции, ieluM . Для этой задачи на множестве X вводятся понятия отношения нестрогого предпочтения и строгого предпочтения • . На основе этого даются определения локально и глобально эффективной точки для обоих видов предпочтения. Далее оптимальные точки для предпочтения - называются эффективными по Парето (или просто эффективными), для предпочтения - называются эффективными по Слейтеру (или слабо эффективными). Используется аппарат метода возможных направлений [60], [266] получены необходимые и достаточных условия непустоты множества допустимых значений X, условия принадлежности точек из X множеству эффективных или слабо эффективных точек. Разработаны модификации методов возможных направлений для решения систем выпуклых неравенств, отыскания точек, принадлежащих множеству слабо эффективных точек. Приведенные построения являются развитием методов работ [71], [143] для однокритериальных задач.

Задача отыскания эффективных точек тесно связана с разрешимостью систем выпуклых неравенств, более того, так как рассматриваемые далее алгоритмы предполагают, что в качестве начального приближения может быть взята любая точка пространства R", то в работе разбираются некоторые вопросы разрешимости систем выпуклых неравенств. Вводится понятие возвращающего направления s в точке уХ, незначительное перемещение из точки у в направлении s не нарушает ненарушенных ограничений, значения функций нарушенных ограничений убывает. Множество всех возвращающих направлений в точке у образуют конус. В этом определении точки (y+As) и у находятся в отношении строгого предпочтения относительно функций нарушенных ограничений. Доказывается теорема, которая является ключевой в формировании условий, являющихся признаком пустоты множества X. Далее рассматривается случай, когда функции (р,(х), xeR", ієі, выпуклые дифференцируемые. По аналогии с [50], вводится задача ZR(y) выбора возвращающегося направления. Ее оптимальное решение либо дает вектор возвращающего направления, либо показывает, что их множество пусто и, в соответствии с доказанными критериями, множество решений задачи пусто. Используя задачу ZR(y) выводится еще один критерий пустоты множества X, который является аналогом теоремы Куна-Таккера.

Для произвольных точек у пространства R", совмещая понятия возвращающих направлений с направлениями, в которых одновременно убывают все критериальные функции, вводится понятие возвращающего подходящего направления для строгого предпочтения и нестрогого предпочтения. Эти множества подходящих направлений образуют конуса. Если ни по одному из возвращающих направлений ни одна из функций q ,(x), ie М, не является постоянной, то оба вида предпочтения совпадают, а, следовательно, и конуса тоже. Если уеХ, то определение возвращающих направлений преобразуется в определение возможных направлений. Но тогда возвращающие подходящие направления становятся подходящими. Для выбора возвращающих подходящих направления для строгого предпочтения строится задача ZS(y). На основании решения этой задачи и ZR(y) удается распознать одну из следующих ситуаций:

1) множество Х= 0;

2) точкам является слабо эффективной точкой;

3) в точке у конус возвращающих подходящих направлений не пуст;

4) в точке у конус возвращающих подходящих направлений пуст, но конус возвращающих направлений не пустой.

Причем в ситуациях 3 и 4 вырабатываются направления, по которым надо перемещаться для получения ответа на поставленную задачу. Используя эти задачи, строятся критерии распознавания ситуаций 1 и 2, которые являются развитием теорем Куна-Таккера на многокритериальный случай в виде систем линейных уравнений и неравенств, а также седловой точки скалярной функции Лагранжа [69]. Делается вывод о связи линейной свертки критериев со слабой эффективностью в задачах многокритериальной оптимизации.

На основе изложенных методов, рассматриваются алгоритмы, которые являются развитием градиентных методов и метода возможных направлений Зойтендейка, основой предложенных алгоритмов являются алгоритмы работы [143]. Приводятся алгоритмы безусловной оптимизации, которые в качестве начального приближения берут допустимую точку. Доказываются теоремы их сходимости к слабоэффективным точкам. Приводится алгоритм метода возвращающих направлений, который в качестве начального приближения берет произвольную точку пространства R". Этот алгоритм не являются релаксационным. Для него доказывается сходимость либо к слабоэффективным точкам, либо к точкам, в которых множество возвращающих направлений пусто, т.е. в задаче нет решений. Для реализации этих алгоритмов описана более эффективная модификация, использующая специфику решаемой задачи, а также специализированный двойственный симплекс-метод, который позволяет получать решения в специальном порядке.

Необходимые и достаточные условия слабой эффективности в задаче выпуклого векторного программирования применяются для анализа модели МРРРК. Доказывается, что если точка =(?,-, ieElKjE2; rjh rhRh ieE2;yv, veV jVD; rv,Rv,veV) является точкой равновесия модели МРРРК, тогда для каждого конечного потребителя, максимизирующего свою полезность, среди семейства эквивалентных функций полезности, определяющих его предпочтение, существуют такие функции полезности, что точка х является слабо эффективной для задачи выпуклого векторного программирования модели МРРРК.

Описанная теорема дает основание для поиска точки конкурентного равновесия модели МРРРК применять модификации алгоритмов метода возможных направлений. Непосредственное применение этих алгоритмов невозможно, так как они сходятся к некоторым слабо эффективным точкам, среди которых и находятся точки конкурентного равновесия. Модификация заключается в том, чтобы направить спуск метода возможных направлений к точкам конкурентного равновесия. Для этого используется процедура временной уступки, аналогичная приему выхода алгоритма метода возможных направлений из тупиковых точек. Вычислительный эксперимент, проведенный на ряде тестовых примеров, показал сходимость алгоритма к точке равновесия. Глава 4 посвящена применению динамического программирования и аппроксимационно-комбинаторного метода в задачах оптимального синтеза экономических систем, функционирование которых можно описать математическими моделями рассредоточенного рынка. Основой синтеза является умение решать следующие задачи дискретной оптимизации многошаговых процессов, заданных на ориентированном дереве:

1) отыскание оптимальных решений задачи оптимизации многошаговых процессов, заданных на ориентированном дереве;

2) отыскание всех Д-близких решений к оптимальному решению задачи оптимизации многошаговых процессов, заданных на ориентированном дереве; В частности, пункты 1 и 2 позволяют решать задачи:

3) отыскание всех решений, являющихся / -близкими одновременно по т (/= 1,2,3,... jri) критериям (многокритериальная задача оптимизации многошаговых процессов, заданных на ориентированном дереве);

4) отыскание оптимальных решений задачи оптимизации многошаговых процессов, заданных на ориентированном дереве с непрерывными фазовыми состояниями и дискретными управлениями.

Для первой задачи доказывается модификация функционального соотношения Беллмана и применяется алгоритм динамического программирования. Для решения второй задачи доказывается функциональное неравенство, которое применяется в модификации алгоритма динамического программирования. Этот алгоритм модифицируется и для решения задачи 3.

Задача 4 решается аппроксимационно-комбинаторным методом, использующим алгоритм решения задачи 2.

Рассмотренные задачи имеют широкое применение при оптимизации трубопроводных сетей. Включение в модели оптимизации трубопроводных сетей вместо соотношений, описывающих гидравлическое слияние потоков, различных производственных функций, позволяет интерпретировать их как многопродуктовые задачи размещения предприятий на древовидных сетях. Для их решения возможно применение алгоритмов динамического программирования, более того, для них возможно отыскание всех Я-близких решений по заданному критерию, решение многокритериальной задачи, т.е. отыскание всех решений, являющихся -близкими одновременно по т (/=1,2,3,...,/и) критериям.

В конце четвертой главы дана задача размещения предприятий в сетевой постановке для сетей произвольной структуры. Для решения этой задачи применяется аппроксимационно-комбинаторныЙ метод. Граф «разворачивается» в дерево, в результате этого получаем задачу размещения для древовидных сетей, на оптимальных и близких решениях которой ищется решение исходной.

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

Пользуясь случаем, автор хочет выразить особую благодарность заведующему отделом Методов проектирования развивающихся систем Вычислительного центра РАН (МПРС ВЦ РАН) - доктору физико-математических наук, профессору Владимиру Рубеновичу Хачатурову, без постоянной помощи которого, обсуждения основных идей и результатов, этой работе было бы не суждено появиться на свет; сотрудникам отдела МПРС ВЦ РАН А. В. Злотову, [Н-Д- Астахову!, В, Е. Веселовскому, И. А. Крылову, Ю. В. Ливанову, И. X. Сигалу, С. В. Туеву, Г. С. Булгаковой, дружеская поддержка которых и совместная работа также оказала влияние на выполнение этой работы.

Очень большое влияние на научное направление автора оказал бывший директор Сибирского энергетического института СО РАН, член-корреспондент АН СССР, доктор физико-математических наук, профессор Анатолий Петрович Меренков . Автор признателен сотрудникам лаборатории, которую возглавлял Анатолий Петрович, Сенновой Е. В., Новицкому Н. Н, Сидлеру В. Г., Ощепковой Т. Б., [С. В. Сумарокову), за активное сотрудничество и поддержку.

Хотелось бы выразить свою благодарность главному научному сотруднику ВНИИпромгаза, д.т.н., профессору Ставровскому Евгению Романовичу за оценку, поддержку, интерес к этому направлению, обсуждение основных результатов, формирование дальнейших направлений исследования, а также зав. кафедрой ПМиКМ Московского университета нефти и газа, д.т.н., Сухареву Михаилу Григорьевичу. Выражаю признательность заведующему кафедрой ТОТиГ Самарского государственного технического университета, д.ф.-м.н., профессору Кудинову В. А., благодаря усилиям которого стало возможным внедрение моделей, методов и программ на объектах СамараЭнерго [51], [52], [ПО].

Некоторые вопросы анализа функций спроса и предложения

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

Производственные функции в общем виде будем записывать как x=(Xj:ieN)T, JV={l,2,3,...,n}. Все переменные неотрицательные, этот факт будем записывать как xeR"+. Согласно [72], эти функции обладают следующими свойствами, ЯР/./(Оя) = 0. ПРФ2./(х) неубывающие по каждой переменной, для дифференцируемой функции df{x)/дхі $. ПРФЗ./(х) вогнутые по каждой переменной, для дважды дифференцируемой функции d2f{x)/dxf 0. Производственные функции характеризуются определенной отдачей от масштаба производства. Для любого xeRn+ и любого А 0 можно записать /(Я-х) = Хт-/(х).Всли: 0 5(х) 1, то убывающая отдача от масштаба производства; д(х) = 1, то постоянная отдача от масштаба производства; S(x) 1, то возрастающая отдача от масштаба. Обычно для описания производственных процессов используются однородные функции. Для них для любого xeR"+ и Л 0 5(х)= =const. ПРФ4. Производственная функция f(x) однородная с убывающей отдачей от масштаба производства. Важным свойством производственных функций является свойство вогнутости и строгой вогнутости.

ПРФ5. В дальнейшем будем считать, что функции f(x) дважды дифференцируемые, вогнутые функции. Одной из основных задач, описывающих поведение производителя в долгосрочном периоде, является следующая задача: F=Pyy-(Px,x)- max, (1.3.1) при ограничениях У А ), (1.3.2) XER"\ (1.3.3) где Ру - цена выпускаемого продукта, Рх- вектор цен на потребляемые факторы производства [30]. Максимум берется по переменным у, х, переменные Ру,Рх являются параметрами, определяемые внешними условиями, Ру 0 и Рх0п. Множество ее допустимых решений обозначим через X. Решение х(Рх,Ру) является функцией спроса на потребляемые факторы производства, у=у(Рх,Ру) =f(x(PxJ}y)) - функция предложения выпускаемой продукции.

Временно рассмотрим задачу (1.3.1)-(1.3.3) без ограничения (1.3.3), если решение х(Рх,Ру) задачи (1.3.1), (1.3.2) удовлетворяет этому ограничению, то оно является и решением первой.

Несложно доказать следующую лемму.

Лемма 1.1. Пусть функция/(х) удовлетворяет свойствам ПРФ1-ПРФ5, тогда решение задачи (1.3.1), (1.3.2) совпадает с решением задачи F = Py-y (Px,x)- -max, при ограничении =/(л:), т.е. с решением задачи F = Py -f(x) -(Рх,х) - max. (1.3.4) Лемма 1.2. Пусть функция/(х) удовлетворяет свойствам ПРФ1-ПРФ5, тогда для любых Ру 0, Рх 0„ задача (1.3.4) имеет решениеу{Рх,Ру) х{Рх,Ру\ причем эти функции строго больше нуля по Ру 0, возрастающие, непрерывные и непрерывно дифференцируемы по переменной Ру 0.

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

В пунктах 1.4 и 1.6 была показана возможность применения основных методов расчета потокораспределеиий теории гидравлических сетей (методов поузловой и поконтурной увязки) для отыскания равновесного состояния рассредоточенного рынка. Применимость этих методов рассматривалась при условии, что функции спроса и предложения, торгово-транспортные кривые и обратные к ним были выражены в явном виде. Однако явный вид этих функций удается получить в редких случаях. Как отмечалось в предыдущей главе, для случая производственных функций Кобба-Дугласа их вывод не составил труда (см. Приложение 1), однако для производственных функций CES функции спроса и предложения не выражались в элементарных функциях.

Поузловая увязка. Зададим значения цен 73,- во всех вершинах ієЕ. Тогда, решая задачи (2.1.4)-(2.1.5), (2.1.6)-(2.1.8), (2.1.9)-(2.1.11), а также используя (2.1.2) - (2.1.3) легко вычислить NBi = Z{yv:veV\i)} I1{yv\ver{i)}+ цг z;, ієЕ2иЕ\

Последовательное варьирование ценами Pt в вершинах ієЕ2 таким образом, чтобы получать NBj=0, и есть алгоритм поузловой увязки. Следует отметить, что время работы алгоритма в этом случае значительно возрастает, так как по каждое вычисление значения JVB,- сопряжено с решением ряда экстремальных задач.

Поконтурная увязка. Для описания применимости поконтурной увязки проведем в системе (2.1.1) - (2.1.12) переход к циклической схеме. Введем в граф G дополнительную вершину ik, будем считать, что эта вершина с фиксированной ценой Pik=P /4=0.

1. Пусть ієЕ , соединим вершину ik с вершиной /дугой v, h\(y) ik h2(v)-i. Для этой дуги положим фу 1 (yv)=p\, тогдаРьцУу =Лцу) + Ф 1 (yv)-Вершину / делаем вершиной со свободной ценой и заданным отбором В\ = 0.

2. Пусть /єІ

2а. Для потребителя этой вершины введем дугу v, направленную оті Kit, т.е. h2(v) = ik, hl(v) = і. Задачу (2.1.4), (2.1.5) будем записывать в виде uviyv,Sv)- mca,{Phl{V)-Ph\(v)) -yv+itv- Sy Mv,yv Q, Sv 0. (2.2.1) 2b. Для производителя вершины введем дугу v, направленную от ik к і, т.е. h2(v)=i, h\{v) = ik. Задачу (2.1.6) - (2.1.8) будем записывать в виде Fv=yv-{Phl{v) Ph4v))-(Yv,PYv)-(rViPrv) max,yv fv{(Yv,rv), 0v=rv= r (2.2.2) 2с. Вершину і делаем вершиной со свободной ценой и заданным отбором В j.

3. Пусть іє3. За, ЗЬ выполняются так же, как 2а и 2Ь, описанные выше. Зс. Агенту, выполняющему экспортно-импортные операции вершины і, поставим в соответствие дугу v, направленную от ik к /, т.е. hl(v) = ik, A2(v) = i. Для этой дуги yv =zl{Pi)=zi(PrPik) =zv(Ph2(V)-Ph]{v)) 3d. Вершину і делаем вершиной со свободной ценой и заданным отбором 5,= 0.

В соответствии с выполненными преобразованиями, в дальнейшем будем применять следующую терминологию: - дуга, соответствующая производителю; - дуга, соответствующая арбитражеру; - дуга, соответствующая конечному потребителю; Ill - дуга, соответствующая агенту, выполняющему экспортно-импортные операции.

Выполненные преобразования показывают, что задача может быть представлена в виде циклической схемы. Покажем, что с помощью замыкающих соотношений, представленных экстремальными задачами, могут быть вычислены значения ДЛ =ЛІ2(У)-ЛІІ )ПО любому заданному значению jv Это соответствует вычислению фу 1 {yv\ V&V.

Дуги, соответствующие конечному потребителю, представлены системой (2.2.1), и для них необходимо уметь решать следующую задачу: при заданном объеме потребления yv первого продукта и цене жч второго продукта, определить &Pv=(Ph2(v)-Phi(v)) первого продукта и объем потребления второго v, при котором пара (yv, Еч) является оптимальным решением системы (2.2.1). Эта задача относится к классу обратных задач оптимизации [4] и ее можно решать без представления функций фу, фу 1 в аналитическом виде.

Пусть пара (уиД) является оптимальным решением задачи (2.2.1), выпишем для этой задачи условия теоремы Куна-Таккера 8uv(yv,Ev)/dyv =а,- APV+ ha2+0-a3, (2.2.3) duv(yv,Sy)/dEv = ai-7Ty+0-a2+ 1 аз» (2.2.4) где (Х) 0, а2 0, ссз 0. При заданных v жч из уравнения (2.2.4) находим Sv, подставляя получившееся значение в (2.2.3) получаем требуемое. Естественно, что эти операции выполнимы при разрешимости (2.2.4) относительно Sv, и сс\ 0.

Дуги, соответствующие производителям и арбитражсрам, представлены соответственно системами (2.1.9) - (2.1.11) и (2.2.2). Из свойств производственных функций следует, что в системе (2.2.2) yv 0, {Ph2(y)-Ph\(v)) 0,поэтому постановка (2.1.9) - (2.1.11) описывает и постановку (2.2.2).

Пусть /„ - решение задачи (2.1.9)- (2.1.11) при фиксированному. Для этой задачи выполняется условие регулярности по Слейтеру, заметим также, что разность(/,А2(у)-Ді(і )) не влияет на значение rv, и что sign(Pk2(v)-Phi(v)) sign{yv) Воспользовавшись теоремой Куна-Таккера, запишем для этого решения необходимые и достаточные условия оптимальности

Некоторые вопросы разрешимости систем выпуклых неравенств

Основной целью исследования данного параграфа является вывод условий, при которых Х=0. Прежде чем проводить эти исследования заметим, что они могут быть сведены к решению проблемы безусловной оптимизации [143]. Пусть yeR". Введем следующие обозначения: - І(у)={і: ієі, р,(у) 0} - множество индексов существенных ограничений в точке у; - І(у)={і: /є/, р,(у) 0} - множество индексов строго ненарушенных ограничений в точке у; - J(y)={i: іеіу рі(у) Щ- множество индексов нарушенных ограничений в точке у. Обозначим также через Х{у) {х\ xeRn,),( )-0) iel(y)u 1(у)}. Доопределим понятие возможного направления для случая, когда у -произвольная точка из 7?", т.е. и на случай, когдау Х.

ОПРЕДЕЛЕНИЕ 3.9. Направление s назовем возможным в точке у для ограничения ієі, 9 ,(у) 0, если для достаточно малого Л 0 р (у + Xs) 0. Направление s назовем возможным в точке yeRn, если оно возможное для всех ограничений iel(y)ul(y).

Из определения 3.9 следует, что незначительное перемещение из точки у в сторону возможного направления s не нарушает ограничений, ненарушенных в этой точке.

ОПРЕДЕЛЕНИЕ 3.10. Направление s назовем возвращающим в точке у, если оно возможное в этой точке и для достаточно малого Я 0 # ,(у + As) (ptiy), izJ(y). Заметим, что в этом определении точки (y+/Ls) и у находятся в отношении строгого предпочтения относительно функций щ(х\ iej{y). Из определения 3.10 вытекает, что возвращающие направления в точке у дают направление убывания одновременно всех функций, соответствующие ограничения которых нарушены. Нетрудно показать, что множество возвращающих направлений в точке у образуют конус, который будем обозначать через Кц(у), если J(y) = 0, тоКк(у) = КР(у).

Следующая теорема является ключевой в формировании условий, являющихся признаком пустоты множества Теорема 3.5. Пусть непрерывные функции tp,{x), iel, таковы, что множество {х: xeRn,(pl(x) di, iel} ограниченное, где d( произвольные числа, іеі. Для того, чтобыХ=0, необходимо существование точкиyeRn, в которой J{y) 0 и конус KR(y) = 0.

ДОКАЗАТЕЛЬСТВО. Рассмотрим функцию (р{х) = тах{(р,{х): iel}, которая в силу непрерывности р,(х\ iel, также будет непрерывной. Возьмем произвольную точку xQeRn, положим do=(p(xa) и рассмотрим множество Y={x: (p(x) do}.

І.Так как х0є7, то множество JV0. Пусть хеY, тогда (p{x) du, отсюда следует (р,(х) (р(х) dQ, т.е. хе{х: Pi(x) d0}. По условию теоремы это множество ограниченное, поэтому множество Y также ограниченное. В силу непрерывности р{х), множество К также замкнутое.

2. Из теоремы Вейерштрасса следует существование точки y=argmin {(p(x):xeY}, очевидно, что y=argmin {(p{x):xeY} = =argmin { р(х):хє л }.

З.ТаккакЛГ=0, то р{у) 0, поэтому J(y) j 0. Покажем, что в точке конус Кц(у) = 0. Возьмем произвольное направление s и положим x=y+Xs. Пусть j = argmax{ pt(x): iel}. Так как (pj{y) 0, то при достаточно малом Я- ;(х) 0, поэтому jeJiy). Так как р (у) (р (х), то р (y) pj(x). С другой стороны, по построению q j(y)u р(у), поэтому Pj(y) (pj(x), т.е. направление s не является возвращающим.

В дальнейшем будем считать, что функции щ(х), iel, обладают свойством, приведенным в условии теоремы 3.5. Заметим, что это свойство можно как-то ослабить, но полностью освободиться от него нельзя. Например, X={XER1 .e S O, 1- О}=0, тем не менее, в любой точке xeR существует возвращающее направление.

Теорема 3.6. Пусть (pfe), хе Rn, /є/, -выпуклые функции. Для того чтобы X = 0, достаточно, чтобы существовала точка у, в которой Лу)Ф0 nKR(y) = 0. ДОКАЗАТЕЛЬСТВО. Предположим противное, т.е. ХФ0. Возьмем хеХ и y zR" положим s=x y. Легко показать, что s - возвращающее направление. Действительно, для iel(y) любое направление возможное, для ієІ(у) и Яє[0,1]

Ф+Цх-у))= 0((1-Л)у+Л )) (1-А) Ш+Ящіх)) О, т.е. s возможное направление в точке у для множества Х(у), Если J {у) - 0, то s также и возвращающее направление. Пусть 3{у)Ф0 и ieJ(y) возьмем Яє(0,1), тогда ф,(у+Л$) &(у+А(х-у)) р,(у) + Х[щ{х) - щіу)]. Выражение в квадратных скобках строго отрицательное, поэтому щіу+Xs) (р,(у). Таким образом, KR(y) Ф 0. Отсюда непосредственно следует справедливость теоремы.

Из теорем 3.5 и 3.6 вытекает следующее Следствие 3.3. Пусть щ(х), iel, xeRn, такие выпуклые функции, что для произвольных чисел di, ie I, множество {х: xeRn (pl{x) di, iel} ограниченное множество. Для того, чтобы Х=0, необходимо и достаточно существование точки у є#", для которой J(y) Ф0м KR(y) = 0.

Постановки задач оптимизации многошаговых процессов, заданных на ориентированном дереве

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

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

Теорема 4.2. Пусть ЙГ=[И (І), ієЕ\{р}] - -близкое управление (решение задачи 4), П о.О, [х (ї), іеЩ - соответствующая траектория, тогда для всех ієЕ\{р] справедливо неравенство Л,(д: (0 (я(0),и (0) + (0) (л(/)))+/г. (4.2.5) ДОКАЗАТЕЛЬСТВО. ДЛЯ Л-близкого управления (о =[и{к\ кеЕ\{р}] выполняется следующее неравенство {Dk(x {k),x (n(k)lи (к)):кеЩр)} й Z {D \ (х (к),х (я( )), «( )) кеЕ\{р}} +R=Fonm+R. Возьмем некоторое произвольное ieE\{p}. Перепишем это неравенство в виде {D\{x\k\x\ k)),u{k)y.keEi\{i]}uFonm R. Воспользовавшись определением функции Gi{x (j)), получаем X {О0к(х (к),х (я(к)),и (к)):кеЕл{{р}иЕд} + +D0i(x i),x ( ii)),u i))+aix-(i)) Fonm+R. (4.2.6)

Так как значению 2{ (х""(&), /(я(Щ«я (А)):ієЯ/\{/} }+»Я{ (0) соответствует некоторое допустимое решение задачи, то справедливо неравенство ар(хр) 1 {D (xJk)X{ {k)Wk)):keEMi}}+S& (i)).

Складывая это неравенство с неравенством (4,2.6) и уничтожая слева и справа одинаковые члены, получаем требуемое.

Заметим, что если в неравенстве (4.2.5) положить Д=0, то получим равенство (4.2.4).

Рассмотрим связный граф G ={E\V\H), являющийся частичным по отношению к графу G, такой, что реЕ\ На множестве \ выделим множество к минимальных элементов в смысле древесного порядка "«", определенного на множестве Е.

Теорема 4.3. Пусть [и (і), /є \{/?}]-допустимое управление на графе G\ [х (і), ієЕ ] - соответствующая ему траектория. Если 2 {D\( -(і), х {тіі)1 и Щ: ієЕ Цр}} +1 {$( ( ( )): кеК) Fonm +R, (4.2.7) то каковы бы ни были значения u"(i)eUi, x (i)eXh Д{л: (/),л: (я(і))ім 0))=0 Ддя всех ієЕ\Е , управление [ и"(і), іеЕ\{р}] не может быть Й-близким. ДОКАЗАТЕЛЬСТВО. Предположим противное, т.е. нашлось й-близкое управление [іГ(і),ієЕ\{р}] и соответствующая ему траектория [х (ї),ієЕ], для которых выполнено неравенство (4.2.7). Тогда для него справедливо {De,(x"(i)f х (я(і)),и (0):ieE\{p}} Fonm+R. Левую часть этого неравенства можно представить 2 {Dfr (i), х\ж{І)\ и {і)):ієЕ \{р}}+ +1{Б {Di(x (i), х (х(і)),и(і)):ієЕк}:кєК\. Воспользовавшись определением Sk(x (?r (к))), получаем Б {D((x (i)Xm\и (І)) izE \{p}}+Z{Sk(x (x(k)YkeK} Fotim+R, что противоречит неравенству (4.2.7). Теорема доказана. Для формулировки алгоритма нам понадобится еще одно утверждение. Теорема 4.4. Пусть koe[0..N]. Рассмотрим множества Е = {ієЕ: і К), V ={itV:i k0}. 1. рєЕ , 2. граф Gf={E ,V ,H) - связный.

ДОКАЗАТЕЛЬСТВО. Корневая вершина рєЕ , так как она имеет номер 0.

Возьмем произвольное і0єЕ и положим і=і0. По построению, дуга с номером z содержится в V. Из свойств нумерации вершин и дуг графа следует, что вершина, в которую входит эта дуга, имеет номер j i, T.e.jeE . Если _/=() (корневая вершина р), то получаем, что из вершины \0 существует путь в вершину р, в противном случае полагаем i=j и процедуру повторяем до тех, пока значение j не станет равным 0, т.е. мы не достигнем корневой вершины р. Эта операция конечна, в силу конечности множества Е. Таким образом, получаем путь из вершины i0 в корневую вершину р. В силу произвольности /0, получаем связность графа G . Теорема доказана.

На основании теоремы 4.4, каждому [0.. ставится в соответствие частичный граф G (/0), которому в соответствие ставится множество K(i0) минимальных элементов из E\E {i0), поэтому теорему 4.3 можно переформулировать с учетом нумерации вершин и дуг дерева G.

Теорема 4.5. Пусть і0 - некоторое целое число, 0 io N; [и (і),Іе[\..і0] -допустимое управление графе G , определяемом /0; [х (і),/є{0,1,2,...,/о}] -соответствующая ему траектория. Если O\(io)+O(Q F0nm+R, (4.2.8) где 0(/0)={u( W)): ЫЦ, (4.2.9) Ol(4)=S{D (0,x «0), « (і)): іф.Ло}}, то каковы бы ни были значения гГ(/)єІУ„ x (i)eXh Д(лГ(і), jf (я(/)), w (/))=0, для всех /є {/в+1,...,#}, управление [ и {ї), ієЩр}] не может быть Л-близким.

Выражение в левой части неравенства (4.2.8) представляет собой нижнюю оценку значения функционала задачи на множестве всех управления, для которых «"(/ )), іє[0../о], зафиксированы. Величина 0(/ о), определяемая по формуле (4.2.9), представляет собой нижнюю оценку на незафиксированных переменных и (0) i[i0+\..N]. Для 0(Q легко получить формулу пересчета, если /о=0, то O(i0)=ao(x"(0)). Пусть і0 \, н (/ 0+1)є//№ц, такое, что D to+\{x (/о+1),х ( (4+l)) M (/о+1))-0,ж (/0+1)єА)0 + і,тогда 0(/,+1)=0(/,) + 1 (ж"(я(і0+1))) + о}0+! (JC (I0+1)).