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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

РГЗ 0,1

_ Ч И*'ПП 1007 на пРавах РУК0ПИСИ

ШИНКЕВИЧ Сергей Владимирович

ИССЛЕДОВАНИЕ ОДНОЭТАПНЫХ ЗАДАЧ СТОХАСТИЧЕСКОГО ПРОГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ АППАРАТА БЕСКОНЕЧНОМЕРНОГО ПРОГРАММИРОВАНИЯ

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

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

Санкт-Петербург 1997

Работа выполнена на кафедре Математической теории экономических решений факультета прикладной математики -процессов управления Санкт-Петербургского Государственного университета.

Научный руководитель: доктор физико-математических

наук, профессор В.В. Колбин

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

наук, профессор В.Д. Ногин кандидат физико-математических наук, доцент В.М. Буре

Ведущая организация: Санкт-Петербургский Государственный технический университет.

Защита состоится 1997 г. в /¿часов на заседании

диссертационного совета К-063.57.16 по защите диссертации на соискание ученой степени кандидата физико-математических наук в Санкт-Петербургском Государственном университете по адресу: 190004, Санкт-Петербург, 10-я линия В.О., д. 33, ауд. 41.

С диссертацией можно ознакомиться в библиотеке СПбГУ им. A.M. Горького по адресу: С. Петербург, Университетская наб., 7/9.

Автореферат разослан "if" ^ * 1997 года.

Ученый секретарь Диссертационного

совета, д.ф.-м.н. В.Ф. Горьковой

Общая характеристика работы

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

Предметом исследования диссертационной работы являются задачи стохастического программирования с вероятностными условиями. Рассматриваются постановки задач в условиях неполной информации — предполагается, что функции ограничений задачи и функционал задачи зависят некоторым образом от случайных величин. Распределение этих случайных величин считается известным.

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

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

Актуальность тематики диссертационной работы объясняется необходимостью исследования задач стохастического

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

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

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

Апробация работы и публикации. Материалы диссертации опубликованы в работах [1]-[5]. Результаты исследований, представленные в работе, прошли апробацию на международной конференции: Second Int. Workshop "Beam Dynamics & Optimization-BDO '95", St. Peterburg. Кроме того, основные результаты работы докладывались на семинарах кафедры математической теории экономических решений факультета прикладной математики - процессов упраления Санкт-Петербургского Государственного университета.

Структура. Диссертация состоит из введения, трех глав, приложения, списка литературы из 40 наименований и имеет общий объем 103 страницы.

Основное содержание работы

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

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

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

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

<ро{х) = Мф0(х, £ (а;)) -> тах Р{#г,£М) <<>}>«,

где х € X С Я1, П — пространство элементарных событий, (€1,Р,Р) — вероятностное пространство с заданной мерой Р, £(и;) = • • • — ^-мерный случайный вектор, фо(х,£(и)) : X х Кк —> В. — скалярная функция, : X X 11к —» /?'" — т-мерная вектор-функция, а £ (0,1]. Через ¿Цу) = Р{ф1(х,£(и)) < у1;...;фт{х,^(и)) < ут} обозначаем совместную функцию распределения составляющих вектора ф(х, В условиях непрерывности функции Рх(у) по у возможно построение конечномерного детерминированного эквивалента задачи (1.4). Аналогично может быть построен детерминированный эквивалент для задачи с построчными вероятностными ограничениями.

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

1нумерация соотношений и утверждений соответствует нумерации в диссертационной работе

ния случайной величины

В п. 1.2. рассматриваются задачи, порожденные задачами линейного программирования. Приводятся условия, при которых возможно построение детерминированного эквивалента в классах задач выпуклого или линейного программирования. Отдельно рассмотрены задачи с детерминированной матрицой ограничений (п. 1.2.1). Для задачи с построчными вероятностными ограничениями

г

Aí(c(ш)x) —► тах

п

< аИх1 < &<Н} > а," « = 1,...,т а,- € (0,1] (1.10)

при детерминированной матрице А ограничений и случайных векторах Ь(и) и с(ш) задачи возможно построение детерминированного эквивалента задачи (1.10) в классе задач линейного программирования. Для задачи с совместными вероятностными ограничениями при детерминированной матрице ограничений А

М(с(и})х) —*тах < Р{Ах < Ь(и)} >а, 0 < а < 1 (1-13)

X] >0, з = 1,... п. детерминированный эквивалент является задачей выпуклого программирования лишь при некоторых предположениях о распределении компонент вектора Ь(и).

Для нескольких типов задания функционала линейной стохастической задачи в предположении нормального распределения компонент матрицы А и вектора Ь (п. 1.2.2.) детерминированный эквивалент принадлежит классу задач выпуклого программирования как в случае независимости случайных величин в задаче, так и в случае их коррелированное™,

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

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

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

данной мерой Р; = (^(и»),... — ^-мерный случай-

ный вектор; <ро(х) : X Я — скалярная функция; д(х,£(и})) : X хВ.к —► Пт — ш-мерная вектор-функция; {ш : д(х, ^ 0} £

^ для Ух; а 6 (0,1]. Строится семейство задач полубесконечномерного программирования

Здесь Т — некоторое подмножество Як: {ш : 6 Г} 6 ^ , 4 — ^-мерный вектор.

Обозначим через 2Г(/3) (/3 £ (0,1)) множество подмножеств Я* следующего вида: Т € ■£(/?) означает Р{ш : £ Т} = /3. Обозначим решение задачи 5ГО! — %гоь а 5ГР1(Г) —

Для задачи 5Г01 с фиксированным а построим задачу

хз!Р1(Т).

тах (ро(х31Р1(Т))

ГбЯ(а)

(2.1)

максимизации оптимумов полубесконечномерных задач на некотором множестве задач 5/Р1(Т).

Доказана следующая теорема о существовании детерминированного эквивалента

Теорема 2.1.

а) если Т — решение ("2.1), тогда х$1Р1(Т) — решение БТО1, и

Ы^т(?)) ~ ^оО^тоО-

б) если существует х.ь"го1 — решение задачи БТО!, то выполняется ; (ро{хзто1) > при УТ 6 £(«) и существует Т — решение (2.1), причем <ро(*5ТО!) = <Ро(хмР1{Т))-

Таким образом, семейство задач 57Р1(Т) на множестве I1 6 £(<*) дает множество оценок снизу оптимума задачи 5Т01 при фиксированном а, причем максимум по этому множеству дает точную оценку оптимума и среди задач этого семейства существует детерминированный (полубесконечномерный) эквивалент стохастической задачи.

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

где х Е X С В,1; (0,Р,Р) — вероятностное пространство с заданной мерой Р; £(и) = (^(си),... ,£*(ы)) — ^-мерный случайный вектор; : X Е — скалярная функция; д,(х,£(и)) : X х И* —► К — скалярные функции; {и : <7,(3:, £(ц>)) < 0} е ^ для

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

Ух.

^ . I —+ тах,

где 2} — некоторое подмножество {ш : £(ш) £ Г} 6 — ¿-мерный вектор, и задача

Существование полубесконечномерного эквивалента для этого класса задач утверждает Теорема 2.2.

а) если Т\,...,Тт — решение (2.2), тогда хз1Р2{Т\-,...,Тт) — решение (5Г02) и уъ{х51Р2{Т\,.. .,Гт)) = ^о(^тог)-

б^ ест существует хзтсп, го ^(¿згаг) > <ро(£у;я2(7ь ... ,Тт)) при Гх € Z(a^),..., Тт € £(«„,) и существует (Т!,..., Тт) — решение (2) такое, что ^(¿етог) = 'М*31Р2{Ти..., Г,„)).

Далее рассматривается постановка задачи оптимизации вероятностного функционала

[ < 0} -» тах,

(5ТОЗ) { т ^ " ~ 1 ( хех.

Здесь д, (О, Р,Р), имеют тот же смысл, что и в задаче 5Г01.

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

тах (ра(х) = Р{ы : Е Т),

X

о №ет, хех

5/РЗ(Т)

Здесь Т С Д*: {а;: £ (ь>) € Т] € 1- — ¿-мерный вектор.

Обозначим через 2 множество подмножеств Я.к: Т 6 Z означает {и> : £(<*>) £ Т} £ Г. Обозначим решение задачи 5ТОЗ — ¿б'тоз- задачи 5/РЗ(Т) — здрзСП-

Для задачи БТОЗ определим задачу

галх<р0{х51Рз{Т)) (2.3)

1СУ-

максимизации оптимумов полубесконечномерных задач на некотором множестве задач 5/РЗ(Г).

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

Теорема 2.3.

а) если Т — решение (2.3), тогда хзт(Т) — решение 5ТОЗ.

б) если ¿5хоз — решение задачи БТОЪ, то Т —

: 5(£ягоз,£М) < 0} — решение (2.3).

В п. 2.2. исследуется вопрос единственности представления полубесконечномерного эквивалента в семействе. Для задачи 5Т01 утвержает единственность представления в классе задач полубесконечномерного программирования с точностью до множества меры нуль

Теорема 2.4. Пусть

1) Существует решение задачи БТ01 — ¿ято!,'

2) — непрерывные случайные величины, г — 1,..., к;

3) д(х, ¿) строго выпукла по I, непрерывна по всем аргументам, ограничена на своей области определения;

4) точка ¿5Г01 не является точкой локального максимума функции <ро.

Тогда в классе задач 31Р1(Т) существует единственный детерминированный эквивалент задачи БТ01 с точностью до множества меры 0, иначе говоря, если 57Р1 (1\) и 31Р1(Т<2) — эквиваленты 5Г01, то б Тх \ Т2} = 0 и Р{£(«) € Т2 \ Г1} = 0.

В п. 2.3. доказываются утверждения об устойчивости решений задачи STO1 по вероятностному параметру а и вероятностному распределению случайной величины. Условия устойчивости по параметру а выражает

Теорема 2.5. Пусть для задачи STO 1

1) функция g(x,t) строго выпукла по t, непрерывна по всем переменным;

2) — непрерывные случайные величины, i = 1,..., к;

' 3) функция ipo непрерывна по х.

4) для каждого а € [а1,«0], (0 < а1 < а0 < 1) существует единственное решение задачи STO 1. Обозначим его х*(а);

5) для а = а1 множество допустимых планов задачи ST01 ограничено;

Тогда существует последовательность { Да„} —► +0: lim x*(a°—

П—+00

Дап) = х*(а°).

Условия устойчивости решений задачи (STO 1) по вероятностному распределению случайной величины рассматриваются в

Теореме 2.6. Пусть

1) для задачи STO 1: — непрерывный случайный вектор, ("(ijj) — последовательность непрерывных случайных векторов, множество реализаций случайных векторов £"(uj) — Т С Rk. Существуют F(x) и F„(x) — совместные функции распределения случайных векторов я соответственно и некоторая последовательность чисел {еп}: е„ > 0,Vn, lim £„ = О такие, что

П-++00

2) Множество реализаций случайных векторов ... ограничено: Vk(T) = С < +оо, где Vk обозначает объем в к-мерном пространстве.

3) Множество допустимых планов задачи (ST01) ограничено

при некотором 0 < а1 < 1.

4) Существуют решения задачи (БТО1) при некоторома0 > а1 (обозначим его х) и решения задачи

{max

(ST02(a)U max^°(x)

v v /М „ г , <0}>a

(обозначим x(a)) для а 6 [а1,«0].

Тогда существует последовательность {<$„}: 6„ > 0, lim 6П — О

П—»+00

такая, что {ж(а - 6„)} сходится к рсшетпо задачи (ST01) при а = а0.

В п. 2.4. предлагается метод оценки оптимума задачи STO1.

Рассматривается случай, когда — одномерная случайная величина, g выпукла. Зафиксируем N > 0, построим последовательности = JF—1(т»(1 - a)/N) тЩ = F~l(a + n(l - a)/Ar), n = 0,..., N, где F~l — функция, обратная функции распределения случайной величины

Рассмотрим семейство задач

SIP(n) I т^°{хУ'

U(M)<o, vte[tj,ig].

Пусть x(SIP(n)) — решение задачи SIP(n). Обозначим через (ppj — ipo(x(SIP(n))) оптимум задачи SIP(n). Определим еще Фц = maxv?«, (п = О,...,N). Пусть х* — решение STO 1. Тогда при выпуклой функции g множество {/ : g(x*,t) <0} — замкнутый интервал вида [fi;*2]: € [<15*2]} = Вве-

дем обозначения: ai = dg/dx(x*,ti), аi = dg/dx(x*,t2), bi = dg/dt(x*,ti), = dg/dt(x*,ti). Следующая теорема определяет условия, при которых может являться оценкой оптимума задачи ST01.

Теорема 2.7. Пусть

A) <ро, д строго выпуклы по всем своим переменным;

Б) для <ро ид существуют и непрерывны первые производные;

B) существует константа А'о > 0: \dyfdt] < Ко, Vx, t;

Г) существует константа Кi > 0: \\dg/dx\\ > Ki, Vx, t;

Д) для случайной величины существует дифференпииру-емая функпия распределения F(x);

Е) существует константа Л'г > 0: F'(x) > К2» Vx;

Ж) существует решение х* задачи ST01, щптчем —Ь\||а2|| ф />2|Ы|.

тогда, lim<i>;v = (ро(х*).

N

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

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

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

На защиту выносятся следующие результаты диссертационной работы:

— доказательство существования полубесконечномерного эквивалента одноэтапных стохастических задач с совместными вероятностными условиями, построчными вероятностными условиями, вероятностным функционалом;

— доказательство единственности представления полубесконечномерного эквивалента одноэтапных стохастических задач с совместными вероятностными условиями;

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

— метод оценки оптимума задачи стохастического программирования с совместными вероятностными условиями;

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

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

[1] Кохов И.А., Шинкевич С.В., Соболев С.Н. / Моделирование и оптимизация технологических процессов (численные методы).// СПГУТД. - СПб., 1996., 89 с.

[2] Шинкевич С.В., Захаров Г.В. / Полубссконечномерный детерминированный эквивалент одноэтапной задачи стохастического программирования с вероятностными условиями. // Деп. в ВИНИТИ №1042-В96 от 29.03.96., 5 с.

[3] Шинкевич С.В., Захаров Г.В. / Применение методов полубесконечномерного программирования к решению некоторых задач стохастического программирования. // Деп. в ВИНИТИ N° 1041-В96 от 29.03.96., 5 с.

[4] Kolbin V.V., Zakliarov G.V, Shinkevich S.V. / Semi-Infinite Deterministic Equivalents to Stochastic Programming Problems.// Abstracts of the Second Int. Workshop "Beam Dynamics & Opti-mization-BDO '95", 3-7 July 1995, St. Peterburg., St. Peterburg,

1995, p. 23.

[5] Kolbin V.V., Zakharov G.V, Shinkevich S.V. / Semi-Infinite Deterministic Equivalents to Stochastic Programming Problems.// Proceedings of the Second Int. Workshop "Beam Dynamics Op-timization-BDO '95", 3-7 July 1995. St. Peterburg., St. Peterburg,

1996, p. 85-92.