Главная » 2014 » Июль » 18 » Скачать Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования. Смирнова, Валентина Викторовна бесплатно
10:14 PM
Скачать Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования. Смирнова, Валентина Викторовна бесплатно
Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования
Диссертация
Автор: Смирнова, Валентина Викторовна
Название: Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования
Справка: Смирнова, Валентина Викторовна. Методы решения некоторых стохастических задач типа затраты-выпуск и линейного программирования : диссертация кандидата физико-математических наук : 01.01.09 Киев, 1984 125 c. : 61 85-1/1846
Объем: 125 стр.
Информация: Киев, 1984
Содержание:
Вв ед е н и е
Глава I Методы решения некоторых стохастических задач типа затраты-выпуск
§ I Некоторые вспомогательные формулы
§ 2 Условия существования математических ожиданий моментов компонент решений стохастических систем ЛеонтьеваСпектральный метод и метод замены переменных
§ 3 Предельные теоремы типа закона больших чисел для решений стохастических систем ЛеонтьеваМетод интегральных представлений
§ 4 Предельные теоремы общего вида для решений стохастических моделей леонтьевского типаМетод интегральных представлений
Глава 2 Методы решения некоторых задач линейного стохастического программирования
§ I Распределение отношений компонент векторов-решений некоторых систем линейных неравенств со случайными коэффициентами
§ 2 Применение метода ортогонализации в задачах линейного стохастического программирования
§ 3 Метод интегральных представлений решения задач линейного стохастического программирования
§ 4 Эмпирический метод решения задач линейного стохастического программирования
Глава 3 Методы качественного анализа некоторых оптимизационных задач типа затраты-выпуск
§ I Некоторые вспомогательные результатыУсловия оптимальности и соотношения двойственности
§ 2 Исследование зависимости эффективности межотраслевых систем от величин ошибок
3 а к люч е н и е
JI и т ер а ту р а
Введение:
Плановое руководство общественным производством требует широкого использования познанных законов общественного развития с точки зрения анализа количественных взаимосвязей в народном хозяйстве. Такое руководство невозможно без конкретного знания важнейших количественных соотношений, свойственных социалистической экономике,и народнохозяйственных пропорций социализма. Особенно актуальными вопросы управления экономикой стали в настоящее время,когда на первый план выдвинута задача повышения эффективности и качества планирования,улучшения всего хозяйственного механизма. Экономико-математические модели,используемые в качестве инструмента совершенствования планирования^ настоящий момент приобретают решающее значение.
Основные идеи математической экономики характерны именно для централизованной, плановой экономики социалистического способа производства. Стремление к нахождению и достижению оптимальных хозяйственных решений в рамках всего народного хозяйства внутренне присуще социалистическому обществу С Z, \ О ].
Широкое применение методов математического программирования в экономике и других науках выявило недостаточность имевшегося научного задела в этой области и требует дальнейшего развития численных методов для различного класса задач. Л.В.Канторович указывает,что "необходима дальнейшая разработка эффективных методов решения задач линейного программирования с большим числом переменных и ограничений,разработка более эффективных методов для решения специальных классов задач, создание новых методов для стохастического программирования" . Настоящий этап в применении экономико-математических методов знаменуется переходом ко все более сложным и масштабным задачам, связанным с созданием системы оптимального функционирования народного хозяйства. Укрупнение объекта управления является показателем успехов, с одной стороны,оптимального планирования, с другой, - таково настоятельное требование комплексного подхода к управлению экономикой с ID 3. Усложнение моделируемой системы выражается в росте размерности оптимизационных задач, что обусловливает актуальность исследований,направленных на разработку эффективных методов и алгоритмов решения задач большой размерности и, в первую очередь,задач линейного программирования большой размерности. О трудностях,которые возникают при решении линейных задач большой размерности, свойственных большинству практически важных экономических задач и прежде всего задачам оптимизации межотраслевого баланса и линейным макроэкономическим задачам, отмечал В.М.Глушков С 9].
При разработке планов для сложных экономических систем помимо необходимости решать задачи большой размерности, возникают проблемы иного рода, а именно, повышение адекватности экономико-математических моделей,учитывая неопределенность и случайность исходной информации. Исходная информация для планирования, проектирования и управления в экономике,как правило, недостаточно достоверна. Планирование производства обычно ведется в условиях неполной информации об обстановке, в которой будет выполняться план и реализоваться произведенная продукция. Научно-технический прогресс, непрерывный рост и постоянное изменение общественных потребностей,нестабильность климатических условий, стихийные бедствия,открытие новых месторождений сырья,работа автоматических устройств, сопровождаемая непредвиденными случайными помехами, статистические закономерности которых не всегда могут быть определены и учтены при вычислении управляющих воздействий и т.п. причины и обусловливают существование фактора неопределенности. Фактические значения таких экономических показателей,как коэффициенты материало-,трудо- и фондоемкости, цены на мировом рынке, параметрыхарактеризующие потребление населения в большой степени подвержены влиянию факторов,не зависящих от плановых органов,они носят в той или иной степени случайный характер.Игнорирование факторов неопределенности при составлении перспективных народнохозяйственных планов ведет к нарушению сбалансированности экономики страны не только в отдельные годы планового периода,но и в среднем за достаточно длинный период и вследствие этого к снижению конечных народнохозяйственных результатов.
Мощным инструментом планирования и экономического анализа межотраслевых пропорций народного хозяйства являются математические модели межотраслевого баланса,основы которых заложены в работах советских экономистов при разработке баланса народного хозяйства СССР за 1923/24 хозяйственный год. Огромный вклад в создание и развитие баланса (система затраты-выпуск) внес В.Леонтьев [3i3 как средство анализа взаимозависимости различных секторов экономики.
• ? = L i =
Так как каждая отрасль располагает лишь одним способом производства ,то 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 » Г,
S - (| у , а -С ,. , aj, ? - ,.,
А так как почти все модели, построенные исходя из нужд практикитобычно оказываются моделями типа Леонтьева или Неймана, то знание свойств этих моделей и их математической теории является чрезвычайно существенным. Однако большие трудности при подготовке точной исходной информации, что вообще говоря принципиально невозможно, препятствуют широкому внедрению этих систем в практику.Параметры рассматриваемой экономической системы могут быть известны плановому органу лишь с точностью до вероятностного распределения, и поэтому представляет интерес рассмотреть межотраслевые модели с учетом вероятностного характера исходной информации. Леонтьев пишет, что коэффициенты модели "представляют собой средние величины не только потому, что каждый из них касается целой группы промышленных отраслей с более или менее различной структурой издержек производства,но также потому,что эти соотношения отражают целый ряд видов техники,используемой одновременно в каждой отдельной области производства, от самых старых,еще не используемых видов, до самых новейших,только что введенных на наиболее совершенных предприятиях" [31] . Коэффициенты межотраслевого баланса по самой природе являются средними значениями, а потому для точного описания объекта необходимо заменить их более общей характеристикой - определить законы их распределения.В работе C3D] отмечается, что жизнеспособность метода в будущем зависит от того, насколько эффективными будут модели и методы, созданные для учета стохастического характера исходной информации. В ?53] подчеркивается, что "от применения теории стохастических процессов в экономической науке можно кое-чего ожидать. Эпоха детерминистических моделей скоро отойдет в прошлое". Однако,несмотря на большую важность,исследования в этом направлении носят эпизодический характер.
Впервые попытка рассмотреть системы Леонтьева со случайными коэффициентами сделана в статье Р.Куанта где было начато исследование по приближенным оценкам моментов для матрицы 2" системы (I) при а =2.В работе он утверждает, что статистические эксперименты, проделанные для.матрицы малых порядков, хорошо согласуются с логарифмически нормальным законом распределения координат вектора X при достаточно широких предположениях о законах распределения для элементов матрицы прямых затрат.Весьма интересными представляются работы Ершова Э.Б.[?4,25]7 где при малых отклонениях коэффициентов прямых затрат от известных математических ожиданий получены приближенные формулы для нахождения первых и вторых центральных моментов вектора объемов продукции и матрицы полных затрат по тем же моментам для матрицы 2 и вектора ^ предполагаемых независимыми. Приведенные результаты характеризуют модель межотраслевого баланса как весьма устойчивую относительно возмущений,вызываемых случайным поведением элементов матрицы 2 . Большая работа проведена Самознаевым М.Д. по изучению фа'кторов неопределенности и устойчивости решения народнохозяйственных межотраслевых моделей
Стохастическим межотраслевым моделям посвящены работы [ ЦтГ-^ЭЗ Ястремского А.И. Автор предлагает в качестве стохастического аналога модели Леонтьева модель вида
Л II «-2 (1?г)х-Ь\\г -nzin у приводятся критерии стохастической продуктивности стохастического, аналога, изучаются свойства моделей,как частные случаи общей стохастической модели производства.
В работе С^ЗД было проведено экспериментальное исследование с помощью метода Монте-Карло вероятностных характеристик решения полудинамической межотраслевой модели при условии, что некоторые параметры модели случайны. В работах С 5"9 7 ^кЗ рассматриваются динамические модели затраты-выпуск экономических регионов Италии со стохастическими переменными.
В С 5-?] для общих систем линейных уравнений с многомерным нормальным законом распределения для коэффициентов при неизвестных и правых частей строятся доверительные области, соответствующие выбору в качестве статистики некоторого скаляра, имеющего -распределение с Л-степенями свободы.
Когда в матрице 3 элементы k < п. столбцов содержат случайные ошибки, в С предлагается метод Монте-Карло для пересчета коэффициента матрицы полных затрат.
Статистические модели межотраслевого баланса производственных ю мощностей в вероятностной постановке приводятся в ? 3 7]р там же описаны методика и результаты экспериментов на основе реальной информации,дан сравнительный анализ детерминированных моделей и моделей в вероятностной постановке.
Нетрудно заметить,что результатов по изучению стохастических систем леонтьевского типа получено немного. Это объясняется большими вычислительными трудностями,которые возникают при решении таких задач. Однако, благодаря тому, что в последнее время появились новые методы изучения случайных матриц, систем линейных алгебраических уравнений со случайными коэффициентами,некоторые трудности удалось преодолеть при решении стохастических задач Леонтьева.
В диссертационной работе для стохастических задач типа затраты-выпуск впервые применены такие методы как спектральный, мартингальный и метод интегральных представлений.
Отметим,что во многих случаях практически невозможно получить точные коэффициенты матрицы прямых затрат - уже при сборе информации происходит влияние всякого рода "помех".Кроме того, в задачах экономики часто приходится сталкиваться с ситуациями, когда порядок рассматриваемой системы высок. Поэтому возникает интерес в изучении предельного поведения решения систем типа затраты-выпуск.
В первой главе диссертационной работы найдены условия существования математических ожиданий моментов компонент решений стохастических систем Леонтьева,приведены некоторые асимптотические методы решения задач типа затраты-выпуск со случайными коэффициентами.Основной метод доказательства предельных теорем первой главы базируется на использовании интегральных представлений для детерминантов,приведенных в § I.
Для стохастической системы Леонтьева (I) найдены условия существования математических ожиданий моментов компонент решений, т.е. М II II « где S У О - некоторое число, II 2 К s ^ если существует pllj.)- плотность вектора 4>.
J 11 Г1 Г
•??-?? - ее то ?
М II х г с **> .
• произвольное постоянное число. ^ ^
Теорема 1.4.I. Пусть случайные векторы = I А щ . — ч 1
Ду 0simL )для каждого значения a
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 ^
Таким образом, из теоремы I.4.I видно, что случайные помехи "сгущаются" на диагонали матрицы Д. , Кроме того, суммы
Л» ^ • - L=i«rt- удобны для применения предельных теорем, рч Г' LP 5 в частности, они могут сходиться по вероятности к детерминированным постоянным.
Вторая глава диссертационной работы посвящена асимптотическим методам решения задач линейного стохастического программирования, изучению предельного поведения решения задач линейного программирования при случайной матрице удельных затрат, случайных векторе ограничений и целевой функции и большом порядке системы.
Задача линейного программирования формулируется следующим образом: найти значения вектора а? удовлетворяющие условиям ,
As ^ Ь , > О, и доставляющие оптимум целевой функции
С с —> тип (тая). (2)
В обычных задачах линейного программирования предполагается; что все параметры, т.е. коэффициенты целевой функции, матрицы условий и вектора ограничений, являются известными числами -они достоверны и свободны от ошибок. Однако на практике оказывается,что на поведение системы в целом большое влияние оказывают множество случайных факторов, и экономические данные подвержены различного рода ошибкам. Л.В.Канторович указывал что для построения более полных моделей оказывается необходимым выйти за пределы линейного программирования, в частности, а таком направлении,как учет неопределенности - случайного характера исходных данных.
Термин "стохастическое программирование" появился в начале 50-х годов, когда Данциг,Чарнес,Купер ?133 стали анализировать задачи линейного программирования со случайными параметрами, о помощью которых более полно описывались реальные ситуации оптимального планирования.
В настоящее время этот раздел математического программирования интенсивно развивается. Моделям и методам стохастического программирования посвящены работы [ 20,23,5, к Z , кб б^бЗД^ДЗ^обзор прямых и непрямых методов стохастического программирования дан в литературе известны несколько постановок моделей стохастического программирования,например, жесткая постановка задачи, т.е. выпшнение ограничений модели для каждой реализации случайных величин; требование выполнения ограничений с определенной вероятностью; достижение оптимального значения в "среднем". Выбор той или иной модели существенно зависит от конкретной экономической ситуации . К задачам в жесткой постановке относятся,например, задачи в Е 299537 58, Так, в для определения распределения ?С и С предлагается аппроксимация, в которой пренебрегают членами, содержащими "ошибки"(отклонения от математических ожиданий) второго порядка. В отмечается, что аппроксимация, основанная на отбрасывании членов, содержащих "ошибки" второго порядка, является слишком грубой. Кроме того, в С Не Учитывается, что при различных реализациях случайных коэффициентов может изменяться набор базисных векторов.
В коэффициенты Q,. ? is- и ? - являются ef ' 1 J функциями одного или нескольких стохастических параметров Тг .
Дана вычислительная схема решения задачи непрерывного планирования,когда и С I - линейные функции одного стохастического параметра с известной функцией распределения.После определения областей оптимальности в пространстве случайных параметров может быть найдена функция распределения и математическое ожидание оптимального значения целевой функции.
В С рассматривается следующая задача с критерием типа квантиля: найти максимизирующий ? при условии
• Ес.хс. - Ес.))\ 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.
Б.Береану ? 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 . - случайный вектор при
Теорема 2.2.2. Пусть для любого fL = i ? . слу
Тогда для любого неслучайного такого, что gtf^ II Ujl^oo
С X, Cll} -) iCm. P j -Д- 4 г U i + i.
В § 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,
С ^ 11 M 2. Л iim. I+E
Ь--* ffC ri <5-3 t-1 el rt. где
Функция |' ограничена неслучайной константой. Тогда
В § 4 для задач линейного стохастического программирования (2) применен эмпирический метод. Учитывая, что на практике распределение элементов матрицы А. и компонент Еекторов 4 и
С неизвестны, а имеются только наблюдения этих векторов и матрицы, исходную стохастическую задачу представляем в виде эмпирического аналога, т.е. используем эмпирические наблюдения
А. <к t Ct ksiH . Доказано,что решение эмпирической за-k ' к ' к 5 ' дачи сходится по вероятности к решению первоначальной задачи при увеличении размерности ее до бесконечности.
Третья глава посвящена исследованию зависимости эффективности стохастических межотраслевых систем фиксированной размерности от величин ошибок. На эффективность моделируемой системы в некоторых случаях оказывают влияние не только средний уровень случайных удельных выпусков,но и их разбросы. При исследовании зависимости использовались условия оптимальности и соотношения двойственности.Доказано,что величина ковариации коэффициента удельных выпусков пропорциональна увеличению эффективности системы при малом увеличении интенсивности способа с меньшим разбросом соответствующего коэффициента удельных выпусков.
Для оптимизационной стохастической задачи типа затраты-Еыпуск Я rnin г- Г х - ACw)x ] —> max, i I L 5 (3) где
• случайная матрица прямых затрат, cJ
Разработанные в диссертации методы оптимизации могут использоваться при решении многих задач экономики: планировании- народного хозяйства, управлении многономенклатурным производством,задач оптимального распределения ресурсов,производственных мощностей и других, теории управления стохастическими системами, стохастической оптимизации.
Методы,разработанные в диссертационной работе для стохастической балансовой матричной модели типа затраты-выпуск используются при обосновании плановых показателей в системе планирования и управления предприятием (завод "Орбита"),что подтверждено актом внедрения.
Основные результаты диссертации докладывались на П Всесоюзной научно-технической конференции "Применение многомерного статистического анализа в экономике и оценке качества продукции" г.Тарту,1981 г.), на научном семинаре "Математические аспекты моделирования народного хозяйства" (г.Львов, ноябрь 1983 г.),на У1 Всесоюзном семинаре "Неопределенность информации в планировании и управлении народным хозяйством" (г.Таллин, ноябрь 1983 г.),на республиканской школе-семинаре "Системология и междисциплинарные исследования"(пос.Ворохта Ивано-Франковской обл., апрель 1983 г.),на семинаре "Стохастические модели и методы в экономике" кафедры экономической кибернетики КГУ в 1983 г.,на республиканском семинаре "Статис
U «9 тическки анализ и оптимизация стохастических систем" при Киевском государственном университете в 1984 году.
Основные результаты диссертационной работы опубликованы в работах С 13 -16 Л > С •