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

Смирнова, Валентина Викторовна АВТОР
кандидата физико-математических наук УЧЕНАЯ СТЕПЕНЬ
Киев МЕСТО ЗАЩИТЫ
1984 ГОД ЗАЩИТЫ
   
01.01.09 КОД ВАК РФ
Диссертация по математике на тему «Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования»
 
 
Содержание диссертации автор исследовательской работы: кандидата физико-математических наук, Смирнова, Валентина Викторовна

Вв ед е н и е

Глава I. Методы решения некоторых стохастических задач типа затраты-выпуск.

§ I. Некоторые вспомогательные формулы.

§ 2. Условия существования математических ожиданий моментов компонент решений стохастических систем Леонтьева.Спектральный метод и метод замены переменных.

§ 3. Предельные теоремы типа закона больших чисел для решений стохастических систем Леонтьева.Метод интегральных представлений.

§ 4. Предельные теоремы общего вида для решений стохастических моделей леонтьевского типа.Метод интегральных представлений.

Глава 2. Методы решения некоторых задач линейного стохастического программирования.

§ I. Распределение отношений компонент векторов-решений некоторых систем линейных неравенств со случайными коэффициентами.

§ 2. Применение метода ортогонализации в задачах линейного стохастического программирования.

§ 3. Метод интегральных представлений . решения задач линейного стохастического программирования

§ 4. Эмпирический метод решения задач линейного стохастического программирования.

Глава 3. Методы качественного анализа некоторых оптимизационных задач типа затраты-выпуск.

§ I. Некоторые вспомогательные результаты.Условия оптимальности и соотношения двойственности.

§ 2. Исследование зависимости эффективности межотраслевых систем от величин ошибок.

3 а к люч е н и е

JI и т ер а ту р а

 
Введение диссертация по математике, на тему "Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования"

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

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

Широкое применение методов математического программирования в экономике и других науках выявило недостаточность имевшегося научного задела в этой области и требует дальнейшего развития численных методов для различного класса задач. Л.В.Канторович указывает,что "необходима дальнейшая разработка эффективных методов решения задач линейного программирования с большим числом переменных и ограничений,разработка более эффективных методов для решения специальных классов задач, создание новых методов для стохастического программирования" . Настоящий этап в применении экономико-математических методов знаменуется переходом ко все более сложным и масштабным задачам, связанным с созданием системы оптимального функционирования народного хозяйства. Укрупнение объекта управления является показателем успехов, с одной стороны,оптимального планирования, с другой, - таково настоятельное требование комплексного подхода к управлению экономикой с ID 3. Усложнение моделируемой системы выражается в росте размерности оптимизационных задач, что обусловливает актуальность исследований,направленных на разработку эффективных методов и алгоритмов решения задач большой размерности и, в первую очередь,задач линейного программирования большой размерности. О трудностях,которые возникают при решении линейных задач большой размерности, свойственных большинству практически важных экономических задач и прежде всего задачам оптимизации межотраслевого баланса и линейным макроэкономическим задачам, отмечал В.М.Глушков С 9].

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

Мощным инструментом планирования и экономического анализа межотраслевых пропорций народного хозяйства являются математические модели межотраслевого баланса,основы которых заложены в работах советских экономистов при разработке баланса народного хозяйства СССР за 1923/24 хозяйственный год. Огромный вклад в создание и развитие баланса (система затраты-выпуск) внес В.Леонтьев [3i3 как средство анализа взаимозависимости различных секторов экономики.

Рассмотрим простейшую модель типа затраты-выпуск.Пусть iC. - годовой уровень общего выпуска отрасли I , Is $ X. • - количество продукции отрасли L , поглощаемое ежегодно отраслью J , j = i , П j - количество продукции 13 идущее на внешнее потребление.Тогда общий баланс выражается в виде П линейных уравнений

- £ = L i =

J-1 J

Так как каждая отрасль располагает лишь одним способом производства ,то 2. s а:. С l, j = iTa ) ? где J . • - коэффи

J , J J LJ t циенты затрат L -го продукта на единицу выпуска j -й отрасли,иначе называемые технологическими коэффициентами. Тогда a

Ж. = Z J . X. + ь. a«i,a)

1 • е ч J j-i «1 или в векторно-матричной форме Г- 2)2 » Г,

I) где

S - (| у , а -С ,. , aj, ? - ,.,

А так как почти все модели, построенные исходя из нужд практикитобычно оказываются моделями типа Леонтьева или Неймана, то знание свойств этих моделей и их математической теории является чрезвычайно существенным. Однако большие трудности при подготовке точной исходной информации, что вообще говоря принципиально невозможно, препятствуют широкому внедрению этих систем в практику.Параметры рассматриваемой экономической системы могут быть известны плановому органу лишь с точностью до вероятностного распределения, и поэтому представляет интерес рассмотреть межотраслевые модели с учетом вероятностного характера исходной информации. Леонтьев пишет, что коэффициенты модели "представляют собой средние величины не только потому, что каждый из них касается целой группы промышленных отраслей с более или менее различной структурой издержек производства,но также потому,что эти соотношения отражают целый ряд видов техники,используемой одновременно в каждой отдельной области производства, от самых старых,еще не используемых видов, до самых новейших,только что введенных на наиболее совершенных предприятиях" [31] . Коэффициенты межотраслевого баланса по самой природе являются средними значениями, а потому для точного описания объекта необходимо заменить их более общей характеристикой - определить законы их распределения.В работе C3D] отмечается, что жизнеспособность метода в будущем зависит от того, насколько эффективными будут модели и методы, созданные для учета стохастического характера исходной информации. В £53] подчеркивается, что "от применения теории стохастических процессов в экономической науке можно кое-чего ожидать. Эпоха детерминистических моделей скоро отойдет в прошлое". Однако,несмотря на большую важность,исследования в этом направлении носят эпизодический характер.

Впервые попытка рассмотреть системы Леонтьева со случайными коэффициентами сделана в статье Р.Куанта где было начато исследование по приближенным оценкам моментов для матрицы 2" системы (I) при а =2.В работе он утверждает, что статистические эксперименты, проделанные для.матрицы малых порядков, хорошо согласуются с логарифмически нормальным законом распределения координат вектора X при достаточно широких предположениях о законах распределения для элементов матрицы прямых затрат.Весьма интересными представляются работы Ершова Э.Б.[£4,25]7 где при малых отклонениях коэффициентов прямых затрат от известных математических ожиданий получены приближенные формулы для нахождения первых и вторых центральных моментов вектора объемов продукции и матрицы полных затрат по тем же моментам для матрицы 2 и вектора ^ предполагаемых независимыми. Приведенные результаты характеризуют модель межотраслевого баланса как весьма устойчивую относительно возмущений,вызываемых случайным поведением элементов матрицы 2 . Большая работа проведена Самознаевым М.Д. по изучению фа'кторов неопределенности и устойчивости решения народнохозяйственных межотраслевых моделей

С32 1.

Стохастическим межотраслевым моделям посвящены работы [ ЦтГ-^ЭЗ Ястремского А.И. Автор предлагает в качестве стохастического аналога модели Леонтьева модель вида

Л II «-2 (1£г)х-Ь\\г -nzin у приводятся критерии стохастической продуктивности стохастического, аналога, изучаются свойства моделей,как частные случаи общей стохастической модели производства.

В работе С^ЗД было проведено экспериментальное исследование с помощью метода Монте-Карло вероятностных характеристик решения полудинамической межотраслевой модели при условии, что некоторые параметры модели случайны. В работах С 5"9 7 ^кЗ рассматриваются динамические модели затраты-выпуск экономических регионов Италии со стохастическими переменными.

В С 5-?] для общих систем линейных уравнений с многомерным нормальным законом распределения для коэффициентов при неизвестных и правых частей строятся доверительные области, соответствующие выбору в качестве статистики некоторого скаляра, имеющего -распределение с Л-степенями свободы.

Когда в матрице 3 элементы k < п. столбцов содержат случайные ошибки, в С предлагается метод Монте-Карло для пересчета коэффициента матрицы полных затрат.

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

Нетрудно заметить,что результатов по изучению стохастических систем леонтьевского типа получено немного. Это объясняется большими вычислительными трудностями,которые возникают при решении таких задач. Однако, благодаря тому, что в последнее время появились новые методы изучения случайных матриц, систем линейных алгебраических уравнений со случайными коэффициентами,некоторые трудности удалось преодолеть при решении стохастических задач Леонтьева.

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

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

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

Для стохастической системы Леонтьева (I) найдены условия существования математических ожиданий моментов компонент решений, т.е. М II II « где S У О - некоторое число, II 2 К s ^ если существует pllj.)- плотность вектора 4>.

Теорема I.2.I. Если для некоторого 3 У f л, 0 Л" О и 0 4 S s f где Q< СХ ) - плотность распределения элементов матрицы 2 рп m 1 d X ~Л d Ж. и с вероятностью I £р 2 2 ^ С ^ с, fsi У

J 11 Г1 Г

-■■-■■ - ее то £

М II х г с **> .

В § 3 при некоторых условиях доказано, что распределение компонент вектора-решения системы Леонтьева (I) сближается по вероятности с:соответствующими компонентами вектора-решения системы ( I'M 2 ) X = b 9 где под матрицей J^f 2 понимаем матрицу, составленную из математических ожиданий Л . .

Представляет большой интерес задача описания общего вида ^ предельных распределений. Для этого необходимо сделать некоторые' предположения об элементах матрицы 2 ^ - Эти ограничения обусловлены самим характером экономических задач и заключаются в С £ \ том,что для всякого /г векторы ( i . £ ) ly.; i \Z£ ц

Г-Т* S^Lnf* ^ ' ' составленные из элементов матрицы 2 - С I j п. ^.j.i , независимы и предельно постоянны. Тогда при некоторых естественных предположениях распределение решения системы С 1~ 3 ) х„= п. п. s Ь сближается при П. —<эо с распределением реше fL ния системы уравнений, коэффициенты которых неслучайны,за исключением диагональных и этот результат приведен в § 4 главы I. Обозначим д У J J J ^ J 'J J

- произвольное постоянное число. ^ ^

Теорема 1.4.I. Пусть случайные векторы = I А щ . — ч 1

Ду 0simL )для каждого значения a

W5 ' 1 9 V с In* с \ и компоненты (|pi, | тингал-разностями, т.е. .М СД , L . )=0 где М, ^ - уср W р^ 5 ' Р ловное математическое ожидание при фиксированной минимальной -алгебре, относительно которой измеримы случайные величины сукаждого вектора являются мар-Спл „ см шествуют конечные дисперсии f у случайных величин а film £ ^ bp Я pi if» p + p iirrv Z a

I* ■ p

- л pt

4p ip

V -1 £

7*j 0

1 + + pi J 0 sup [{^AJ+^A^A'' a J

4 сЖ? icm k П.—^ icm F{ £*й

- I in i,;-i л ^ J

Sj ton tin P[\M С 1+ &}'!, I'D 1-й—^(ЗО n. km EC + )s o, . а —* a*o Jsi eJ ^

Тогда почти для всех значений IJ, ^ ^ - Целые числа от 1 до а ^ toa [р{- < ^,., -Р{8 0 • ,., Я - Ь J] 0 где 2(- . £; . . - 2 ; - компоненты вектора-решения слеЧ дующей стохастической системы Леонтьева п.

Таким образом, из теоремы I.4.I видно, что случайные помехи "сгущаются" на диагонали матрицы Д. , Кроме того, суммы

Л» ^ • - L=i«rt- удобны для применения предельных теорем, рч Г' LP 5 в частности, они могут сходиться по вероятности к детерминированным постоянным.

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

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

As ^ Ь , > О, и доставляющие оптимум целевой функции

С с —> тип (тая). (2)

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

Термин "стохастическое программирование" появился в начале 50-х годов, когда Данциг,Чарнес,Купер £133 стали анализировать задачи линейного программирования со случайными параметрами, о помощью которых более полно описывались реальные ситуации оптимального планирования.

В настоящее время этот раздел математического программирования интенсивно развивается. Моделям и методам стохастического программирования посвящены работы [ 20,23,5, к Z , кб б^бЗД^ДЗ^обзор прямых и непрямых методов стохастического программирования дан в литературе известны несколько постановок моделей стохастического программирования,например, жесткая постановка задачи, т.е. выпшнение ограничений модели для каждой реализации случайных величин; требование выполнения ограничений с определенной вероятностью; достижение оптимального значения в "среднем". Выбор той или иной модели существенно зависит от конкретной экономической ситуации . К задачам в жесткой постановке относятся,например, задачи в Е 299537 58, Так, в для определения распределения £С и С предлагается аппроксимация, в которой пренебрегают членами, содержащими "ошибки"(отклонения от математических ожиданий) второго порядка. В отмечается, что аппроксимация, основанная на отбрасывании членов, содержащих "ошибки" второго порядка, является слишком грубой. Кроме того, в С Не Учитывается, что при различных реализациях случайных коэффициентов может изменяться набор базисных векторов.

В коэффициенты Q,. ■ is- и £ - являются ef ' 1 J функциями одного или нескольких стохастических параметров Тг .

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

В С рассматривается следующая задача с критерием типа квантиля: найти максимизирующий £ при условии

А я £ k , л > о, Р [сх £ S} * ^ , 0 ^ где С - случайный вектор с известным математическим ожиданием £ С и дисперсионной матрицей V = С - )s СЕ ССС^

- Ес.хс. - Ес.))\ L =

L V с) « Г <г / T

Возможна постановка стохастической задачи I^jUJ со случайным вектором С где требуется максимизировать вероятность того, что значение С & будет не меньше некоторого фиксированного числа 4 mace ( J> s P £ cx > к0} ) ?

В работах П 1, 6 , «3 ё ? анализируются задачи с вероятностными ограничениями, т.е. задачи, в которых ограничения должны выполняться с заданной, достаточно высокой вероятностью.

Большое количество исследований посвящено многоэтапному стохастическому программированию^, в частности, двухэтапным задачам стохастического программирования(например, £ 2.2 j^O к 5

14,62,9i,923 ).

Исследованию различных сторон вопроса стохастической устойчивости задач математического программирования посвящены работы

Lfc-.б,«0,823.

Раздел стохастического программирования, изучающий методы определения вспомогательных характеристик задач линейного стохастического программирования,таких как распределение компонент-решения, распределение оптимального значения целевой функции,число наблюдений параметров условий, обеспечивающее заданное качество оценок,вероятность сохранения оптимального базиса при малых возмущениях параметров условий и т.д., - называется пассивным стохастическим программированием.Суть пассивной постановки применительно к задачам стохастического программирования заключается в следующем. Требуется определить закон распределения условного экстремума целевой функции и соответствующих составляющих оптимального плана по известной совместной плотности распределения параметров условий задачи.В этой области выполнен ряд работ С 55 т 56 7 б 3; &Z, 8 б , 8 7 3 7 где при использовании существенных дополнительных предпосылок о характере распределения параметров ограничений задачи удается получить закон распределения оптимального значения линейного функционала. Однако,как отмечается в 7 предложенные точные методы неконструктивны и крайне трудоемки, причем трудоемкость резко возрастает с увеличением размерности задачи. В связи с этим развитие получили приближенные методы оценки закона распределения компонент оптимального плана и соответствующего значения целевого функционала.Наиболее распространенные среди них [ 617 б 53 опираются на использование неравенства Чебышева и свойств, вытекающих из монотонности отображения (здесь введено следующее отношение порядка.Считается, что (А.-Ь с)?/ . . 1 ± . СП, сел .«> & а-> at L Ut , , С Д если О. с, * а а , 4. У, Ь , С i,m */л 1 \ d V V js£tn,9L CA,T>fc)является монотонно неубывающей функщей). Если нам известна совместная функция распределения случайных величин ( Л , , С } 9 то теоретически можем определить функцию распределения Сл} случайной величины 2 (оптимального значения целевой функции стохастической задачи (2)). Отдельные авторы либо накладывали ограничения на функции распределения

Б.Береану £ 53 , 55 7 5б 1 ),либо определяли приближенную функцию распределения 5 С2) ( Г.Тинтнер [Зй,<§8 3 М.Кауртилье Цй-П , Д.Лемайрье ££33 ),либо изучали лишь некоторые характеристики функции распределения Q С2%например, область изменения £ (Я.Талако С.Вайда С^ЭЗ ).Однако нужно заметить,что работы могут иметь применение в том случае,если случайные отклонения параметров задачи от их среднего значения не изменяют оптимального базиса детерминированной задачи,полученной из исходной путем замены всех случайных величин их математическими ожиданиями.

Некоторые задачи по выбору фиксированного плана при нормальности распределения элементов матрицы (А (к*) рассматриваются в [ 1<3].

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

Для распределений величин / ^ (где 31 ^

5 -ая компонента вектора решения х. системы линеиных алгебраических неравенств А. X. £ ь ) доказана следующая теорема 2.2.2. ^ f С \

Систему неравенств А за k где Az С J J случайная матрица, b . - случайный вектор при

1 - - п ^

Л f ^ у- — ведем к виду А х « & + и. 5 И & и 9 где ц - случайный вектор, стохастически зависящий в общем случае от элементов матрицы А и вектора ^ . Так как зависимость вектора U-от матрицы А и вектора 4 явно указать трудно, и это значительно осложняет нахождение распределения вектора х А 9 то сузим множество всех решений LL . Под решением такой системы уравнений будем понимать множество только тех случайных векторов 02. ^и.) для которых вектор детерминирован, LL, 4 О С isl,n. ) , и удовлетворяющих условию J± = 4 + Ii . LL 6 О.

Теорема 2.2.2. Пусть для любого fL = i £ . слу

Ла^ сп.) 3 ' чайные величины Д. I \-i.n е. , is in. независимы, и »i * ej ' .'с/ J ^ ' Г ^ л|. = Л Ь. =0, D£\.=T>b. для некоторого d >0 eJ е/ ' el ' еор ^ Г л У

Тогда для любого неслучайного такого, что gtf^ II Ujl^oo

С X, Cll} -) iCm. P j -Д- 4 г U i + i.

Ms,

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

Рассмотрим стохастическую задачу линейного программирования: найти injK /я Ctir»)® ^ j ,v> a v ^ о на множестве функций распределения

5 С ,v ) = Р{ xj-ur) * , J^w)^ iT,,

К x^CurVI £1, « a С ^ > & J, Q 9 где дГ - решение системы уравнений ti.

С I + Aj^Cvr) Cvr) +V,

Jl - случайная квадратная матрица П. -го порядка, £. % ^ п. и ь случайные векторы, V s ( V, . V„ ) - детермини-^ л. ft £ ? ••• * п. -#>. рованный, т.е. не зависящий от «ц^ вектор, ^ Сг&)))~ некоторая измеримая функция, выбранная таким образом, чтобы существовал интеграл М f (( Л . X . с/ <г '

Теорема 2.3.1. Пусть векторы ^ и /> не зависят от матриц J* s L £ . / > * , ; Для каждого ft. i? c ч значения ft векторы I £ ^. •. i*^ <;,J независимы, предельно постоянны, ^ ^

С ^ 11 M 2. Л iim. I+E

Ь--* ffC ri <5-3 t-1 el rt. где

О ^n.) cv cm p , f1 v У У ^ У , , I if J J d /xur

CO ^ / I у J ' Pfl vVv fyO - произвольное постоянное число, для каждого значения п. i. ' существуют обратные матрицы С J + A. ) , п» ~ йпг Р{|1|(ь1[ + иГа11>/Ь.}=0. k П —

Функция |' ограничена неслучайной константой. Тогда

W Л / (С 11с X CwW = л fee jW livrffi+oW), б «г где & - множество функций распределения, ^ Сиг) - Решение системы уравнений peT.UK; 1 t t вид множеств Т^ и К ^ указан в § 3 главы 2.

В § 4 для задач линейного стохастического программирования (2) применен эмпирический метод. Учитывая, что на практике распределение элементов матрицы А. и компонент Еекторов 4 и

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

А. <к t Ct ksiH . Доказано,что решение эмпирической за-k ' к ' к 5 ' дачи сходится по вероятности к решению первоначальной задачи при увеличении размерности ее до бесконечности.

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

Для оптимизационной стохастической задачи типа затраты-Еыпуск Я rnin г- Г х - ACw)x ] —> max, i I L 5 (3) где

- случайная матрица прямых затрат, cJ

У 0 - удельный вес I -й продукции в составе конечной продукции, В - удельные затраты труда, £ - величина трудовых ресурсов, - интенсивность технологических способов, показано, что оптимальное значение функционала задачи (3) увеличивается на величину Сй^ (иг), LL ^ С иг)) где - интенсивность применения дополнительного технологического способа, LL - решение двойственной к (3) задачи.

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

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

Основные результаты диссертации докладывались на П Всесоюзной научно-технической конференции "Применение многомерного статистического анализа в экономике и оценке качества продукции" г.Тарту,1981 г.), на научном семинаре "Математические аспекты моделирования народного хозяйства" (г.Львов, ноябрь 1983 г.),на У1 Всесоюзном семинаре "Неопределенность информации в планировании и управлении народным хозяйством" (г.Таллин, ноябрь 1983 г.),на республиканской школе-семинаре "Системология и междисциплинарные исследования"(пос.Ворохта Ивано-Франковской обл., апрель 1983 г.),на семинаре "Стохастические модели и методы в экономике" кафедры экономической кибернетики КГУ в 1983 г.,на республиканском семинаре "Статис

U «9 тическки анализ и оптимизация стохастических систем" при Киевском государственном университете в 1984 году.

Основные результаты диссертационной работы опубликованы в работах С 13 -16 Л > С •

 
Заключение диссертации по теме "Дискретная математика и математическая кибернетика"

ЗАКЛЮЧЕНИЕ

Диссертационная работа посвящена изучению свойств и методов решения некоторых стохастических задач типа затраты-выпуск и линейного программирования. Основными результатами работы являются:

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

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

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

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

5. Исследована зависимость эффективности оптимизационных стохастических задач типа затраты-выпуск от разбросов случайных коэффициентов системы. Чем меньше разброс; коэффициента удельных выпусков,тем больший прирост эффективности получает система.

6. Для систем линейных алгебраических неравенств, случайные элементы матрицы условий которых распределены по симметричному устойчивому закону,показано,что отношение компонент вектора-решения будет распределено так же^как и отношение двух независимых случайных величин,распределенных по симметричному устойчивому закону с характеристическим показателем eL ).

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

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

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

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

1. Абрамов Л.М.,Бочкарева И.И. О задаче стохастического программирования с вероятностными ограничениями. - Сб."Оптимальное планирование",Новосиб.,1970, вып.16, с.3-8.

2. Аллен К. Математическая экономия. М.ИД,1963, 469 с.

3. Аоки М. Оптимизация стохастических систем. М.:Наука, 1971,424 с.

4. Арбузова Н.И. Взаимосвязь стохастической £ -устойчивости задач линейного и дробно-линейного программирования специального вида. Экономика и мат.методы, 1968,тДУ,вып.I,с.I08-II0.

5. Арбузова Н.И. О стохастической устойчивости двойственных задач линейного программирования. Экономика и мат.методы,1966, т.Л, вып.4,с.559-562.

6. Арбузова Н.И.,Данилов В.Л. Об одной задаче стохастического линейного программирования и ее устойчивости. ДАН СССР,1965, т.162, № I.

7. Аркин В.И.,Евстигнеев И.В. Вероятностные модели управления и экономической динамики. М.:Наука,1979, 176 с.

8. Бочкарева И.И. Алгоритм решения одного класса задач стохастического программирования с вероятностными ограничениями. -Сб."Оптимальное планирование",Новосиб.,1970, вып.16,с.9-15.

9. Гпушков В.М. О диалоговом методе решения оптимизационных задач. Кибернетика,1975, № 4,с.2-6.

10. Ю.Гранберг А.Г. Математические модели социалистическойэкономики,- М.:Экономика,1978.

11. Гирко В.Л. Смирнова В.В. Метод интегральных представлений решения задач линейного стохастического программирования.-Кибернетика,1983, № 6,с.122-124.

12. Гирко В.Л.,Смирнова В.В. Предельные теоремы для стохастических систем Леонтьева. ДАН УССР, сер.А,1980, № 12,с,3-6.17. 1Ъхман И.И.,Скороход А.В., Ядренко М.И. Теория вероятностей и математическая статистика. Киев:Вища школа,1979, 408 с.

13. Гофмарк А.С. Некоторые задачи стохастического линейного программирования со случайными элементами матрицы ограничений.-Автореф.канд.дисс. ,Ташкент,1972.

14. Данциг Дж. Линейное программирование,его применения и обобщения. М.:Прогресс,1966, 600 с.

15. Ермольев Ю.М. Методы стохастического программирования.-М.:Наука,1976, 256 с.

16. Ермольев Ю.М. Стохастические модели и методы оптимизации. Кибернетика, 1975, J6 4,с.109~П9.

17. Ермольев Ю.М.,Шор Н.З. Метод случайного поиска для двухэтапной задачи стохастического программирования и его обобщение. Кибернетика, № I,с.90-91.

18. Ермольев Ю.М.,Ястремский А.И. Стохастические модели и методы в экономическом планировании. М.:Наука,1979,256 с.

19. Ершов Э.Б. Неопределенность информации и устойчивость решения статической.модели планового межотраслевого баланса.-В кн.:Проблемы народнохозяйственного оптимума. Новосиб.: Наука,1969, вып.2,с.431-467.

20. Ершов Э.Б., Цветкова М.М. Вероятностные системы ^уравнений межотраслевого баланса. Материалы к Междун.научн.конференции по вопросам разработки и использования в планировании балансов межотраслевых связей в странах-членах СЭВ, М.,1967,3 25.

21. Ибрагимов И.А.Динник Ю.В. Независимые и стационарно связанные величины. М.:Наука,1965, 524 с.

22. Канторович Л.В. Математические проблемы оптимального планирования. В сб."Математические модели и методы оптим.планирования. - Новосибирск:Наука,1966, с.116-124.

23. Канторович Л.В. Экономический расчет наилучшего использования ресурсов. М.:АН СССР,1959,344 с.

24. Колбин В.В. Стохастическое программирование. Сб. Итоги науки.Сер.Математика,Теория вероятностей,1968, М., ВИНИТИ,1970, с.5-68.

25. Коссов В.В. Межотраслевой баланс. М.:Экономика, 1966,223 с.

26. Леонтьев В.,Ченери X. и др. Исследование структуры американской экономики.Теоретический и эмпирический анализ по схеме затраты-выпуск.-М.:Госстатгиз,1958,640 с.

27. Самознаев М.Д. Фактор неопределенности и устойчивость решения народнохозяйственных межотраслевых моделей. Автореф. канд.дисс.,Москва, 1978.

28. Сатанова Э.А. Экспериментальное исследование вероятностной полудинамической модели межотраслевого баланса производственных мощностей. В сб.:Проблемы моделирований народного хозяйства,Новосиб., 1973, ч.Ш, с.199-223.

29. Смирнова В.В. Стохастические системы Леонтьева. Исследование операций и АСУ,I960, вып.16,с.56-63.

30. Смирнова В.В. Системы линейных алгебраических неравенств со случайными коэффициентами. Исследование операций и АСУ, 1982,вып.20, с.49-55.

31. СолдатоЕ В.Е. О задачах линейного программирования со случайными данными. В сб.Мат.модели и методы оптим.планирования, Новосиб.:Наука,1966, с.54-64.

32. Фактор неопределенности в межотраслевых моделях(Бере-зин С.А.,Лавровский Т.Л.,Рыбакова Т.А.,Сатанова Э.А. Новосиб.: Наука,1983,126 с.

33. Фельс Э. ,Тинтнер Г. Методы экономических исследований.-М.:Прогресс,1971,151 с.

34. Шор Н.З.Депакин М.В. Алгоритм решения двухэтапной задачи стохастического программирования.-Кибернетика,1968, № 3, с.56-58.

35. Чирба С.С. Некоторые вопросы пассивного стохастического программирования. М.,Автореф.канд.дисс.,1972.

36. Юдин Д.Б. Математические методы управления в условиях неполной информации. М.:Сов.радио, 1974,400 с.

37. Юдин Д.Б. Задачи и методы стохастического программирования. М.:Сов.радио, 1979, 392 с.

38. Юдин Д.Б. Выбор решений в сложных ситуациях. Известия АН СССР.Сер.Техн.кибернетика, 1970, № 2,с.9-24.

39. Юдин Д.Б. Новые подходы к стохастическому программированию. Экономика и мат.методы, 1969, JS 2.

40. Гупал A.M. Стохастические методы решения некоторых негладких экстремальных задач. Киев: Наук.думка, 1979, 152 с.

41. Ястремский А.И. Стохастические модели производства. I-III.- Исследование операций и АСУ, 1978-79, М-12-14.

42. Ястремский А.И. 0 простейшей оптимизационной межотраслевой модели. Кибернетика, 1973, В 5.

43. Ястремский А.И. Стохастические модели математической экономики. Киев:Вища школа, 1983, 128 с.

44. Ястремский А.И. 0 влиянии степени разброса случайных параметров на эффективность некоторых стохастических систем. -Кибернетика, 1985, JS5.

45. Ястремский А.И.,Головко В.И.Демковский А.Б.Исследование влияния точности информации на эффективность межотраслевых систем с помощью стохастических межотраслевых моделей.- Исследование операций и АСУ, 1983,вып.22,с.12-22.

46. Bereanu В. On stochastic linear programming.Distribution problems: a single random variable.- Revue de mathematiques pures et appliquees,1963,v.8,pp.683-697.

47. Bereanu B. On stochastic linear programming.The Laplace transform of the distribution of the optimum and application.-J.Math.Anal.Appl.,1966,v.15, N 2,pp.280-294.

48. Box G.E.,Hunter J.S. A confidence regione for the solution of a set of simultaneous equations with an application to experiment dessign.-Biometrica,1954,v.41,parts 1,2.

49. Bubbur M. Distribution of solutions of a set of linear equations (with an application to linear prog.). -Journal of the Amer.stst ass.Manacha,1955,p.854-869.

50. Cardini A. ModeHi econometrici e modelli input output nella polilica economica regionalle.-Statistical977,an.37, H3,pp.365-378.

51. Charnes A.,Cooper W.W. Deterministic equivalents for optimizing and satisficing under chance constraints.-Oper.res.,1963, v.11, N 1,p.18-39.

52. Courtillot M. Contribution о la theorie de la program-mation lineaire et de la programmation stochastique.Thise Paris,1963,p.96.

53. Dantzig G.,Madansky A. On the solution of two-stage linear programs under un certainty.-Proc.4-th Berkeley Simpo-sium on Math.Stat.and probab.1961,v.1,pp.165-176.

54. Faber M.M. Stochastich.es Programmieren. Wurzburg-Wien,Physica-VerL.,1970,134 p.

55. Filippucci C. Un modello quantitative per la politica economica: integrazione fra modeHi macroeconomici e modelli input-output.-Statistica,1977,an.37, N 3,pp.495-509.

56. Josifesku M.,Theodoresku R. Linear programming under uncertainty.-"Coloquium on Appl.of Matfr.to Economics",Budapest,1965,pp.133-139.

57. Geoffrion A. Stochastic proc.with aspiration of bractil'e criteria.-Manag.Sci.,1967,v.13,H 9,pp.672-679.

58. Kail P. Stochastic linear programming,Berlin,1976, 96 p.

59. Kataoko Sh. A stochastic programming model.-Economet-rica,1963,v.31, N 1-2,pp.181-196.

60. Lemarie I.M. Prevision et desision en programmation lineatre stochastique.These, Grenoble, 1967.

61. Mandelbrot B. Variables et processus stochastiquesde Pareto-Levy et a repartition des revenus. -С.ПАтаг.зсi., 1959, 249,N 5,pp.613-615.

62. Mandelbrot B. Stable paretian random function and the multiplicative variation of income.-Econometrica,1961, 29,N 4,pp.517-543.

63. Prekopa A. Programming under probabilistic constraints with a random technology matrix.-Math.Operations-forsch.und Statist.,1974,5,N 2,pp.109-116.

64. Prekopa A. On the Probability Distribution of the Optimum of a Random Linear Program.-SIAM Journal on Control,1966,v.4, U 1, pp.211-222.

65. Quandt R.E. Probabilitic errors in the Leontief system.-Naval Res.Logict.Quart,1958,5,N 2,pp.155-170.

66. Quandt R.E. On the solution of probabilistic Leontiefsystems.-Naval Res.Logict.Quart.,1959,v.6, N 4,pp.295-305.1

67. Rockafellar R.,Wets R. Non-anticipativity and L -martingales in stochastic optimization problems.-Math.Program. Study,1976,v.6,pp. 170-187.

68. Rockafellar R.,Wets R. Stochastic convex programming: relatively complete recourse and induced feasibility.-SIM

69. J.Control and Opt.,1976,v.14, N 3,pp.574-589.

70. Rockafellar R.,Wets R. The optimal recource problem1in discrete time: L -multipliers for inequality constraints. SIAM J. Control and Opt.,1978,v.16, N 1,pp.16-36.

71. Sengupta J.K. Stochastic programming .Methods and applications.Amsterdam,New-York,1972,313 p.

72. Sengupta J.K. The stability of truncaled solutions stochastic linear programming.-Econometrica,1955,v.34,N 1, pp.77-104.

73. Sengupta J.K.,Kumar Т.К. An application of sensivity analysis to a linear programming model.-Unternehmensforschung, 1965,9, heIf 1,p.18-36.

74. Sengupta J.K.,Milham C.,Tintner G. On the stability solutions under errors in stochastic linear programming.-Metrica,1965,v.9, heIf 1,pp.47-59.

75. Symonds G. Deterministic solutions for a class of Chawce-counstraining programming problems.-Oper.Res.,1967,15, N 3,PP.495-512.

76. Symonds G. Chawce 3 coustrained equivalents of some stochastic programming problems.-Oper.Res.,1968,v.16,N 6, pp.1152-1159.

77. Talacko J.V. On stochastic Linear Inequalities.-Tra-bajos de Esdadistica,1959,v.10.

78. Tintner G. A stochastic linear programming with application to agricultural economics.-Proc.of the 2-th Symposium in L.P.,v.1,national Bureau of Standarts,1955,pp.197-227.

79. Tintner G.,Milham C.,Sengupta J.K. A weak duality theorem for stochastic linear programming.- Unternehmnsforschung, 1963,v.7,И 1.

80. Tintner G. A note of stochastic linear programming.-Econometrica,1960,v.28,!T 2,pp.490-495.

81. Vajda S. Stochastic linear programming . Ch.II.-In:Mathematical programming,Addison-Wesley,Reading Mass., London,1961,pp.206-217.

82. Wagner H. On the distribution on solutions in linear programming problems.-J.of the Amer;stst.ass Manacha,1958,v.53, N 281 ,pp. 161-163.

83. Walkup D. ,Wets R. Stochastic programs with recourse. SIAM,App.math.,1967,v.15, N 5,pp.1299-1314.

84. Walkup D.,Wets R. Stochastic programs with recourse. II: on the continuity of the objective.- SIAM,App.math., 1969,v.17,H 1,pp.98-103.