Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Методы стохастического программирования

Методы стохастического программирования

4. Стохастическое программирование

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

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

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

* (Математическим ожиданием или средним значением случайной величины x, принимающей значения x1, x2, . xn с вероятностями, равными, соответственно p1, p2, . pn, называется величина , обозначающаяся обычно .)

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

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

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

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

Найти вектор x (детерминированный!), доставляющий максимум математическому ожиданию линейной целевой функции

Здесь величины aij(θ), bi(θ) и Cj(θ) принимают случайные значения в зависимости от значения, принимаемого случайным параметром θ. Каждая реализация θ определяет многогранник допустимых планов соответствующей задачи линейного программирования (реализация параметра θ носит название состояния природы или элементарного события, а множество возможных значений этого параметра R называется множеством возможных состояний природы или пространством элементарных событий). При любом состоянии природы должны удовлетворяться все поставленные ограничения, поэтому допустимым, естественно, считать план, который принадлежит всем возможным многогранникам допустимых планов. Если пересечение этих многогранников пусто, то допустимого плана задачи не существует.

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

Несколько слов о методах решения. Если множество состояний природы конечно, то, очевидно, стохастическая задача может быть сведена к такой детерминированной задаче.

Здесь через Cj‾(θ) обозначено среднее значение случайной величины Cj(θ), взятое относительно всех возможных состояний природы, K — число возможных состояний природы, а a k ij и b k i — коэффициенты, соответствующие реализации k-го состояния природы. Если число K велико, то трудность определяется большой размерностью задачи. В случае бесконечного числа состояний природы приходится устраивать подходящую конечномерную аппроксимацию.

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

Пусть имеется поле площадью S гектаров, которое предполагается засеять двумя культурами с урожайностями, равными соответственно a1 ц/га и a2 ц/га. Известны цены на эти культуры — C1 руб./ц и C2 руб./ц. Предусмотрена и возможность орошения поля, причем цена воды составляет α руб./м 3 . Первая культура для нормального созревания обязательно должна получать b1 м 3 /га воды, а вторая — b2 м 3 /га. Эта вода попадает в почву частично в результате дождей, частично благодаря системе орошения. Для простоты предположим, что возможен один из двух исходов: либо лето влажное, когда выпадает d1 м 3 /га воды, либо лето сухое — d2 м 3 /га воды, причем вероятность влажного лета р, а сухого — 1-р. При таких условиях требуется составить план посева (определить площади под каждую культуру) и орошения, который обеспечивает максимум суммарного среднего дохода (математического ожидания дохода).

Введем ряд обозначений. Если x — площадь, которая отводится под первую культуру, то под вторую культуру остается площадь S — x. Стратегия орошения — количество кубометров воды, требующееся дополнительно на гектар поля, определяется величинами:

В результате решения должны быть найдены величины x, y 1 1, y 1 2, y 2 1 и y 2 2. Приступим к построению модели. Так как мы предположили, что потребности каждой культуры в воде обязательно должны удовлетворяться, то должны выполняться такие равенства:

(1)

Величина x должна удовлетворять разумному физическому ограничению

(2)

Целевая функция, математическое ожидание чистого дохода, складывается из дохода от реализации обеих культур по известным ценам минус средние затраты на орошение, исчисленные в предположении, что влажное лето случается с вероятностью p, а сухое — с вероятностью 1-p, т. е. она может быть записана так:

Оптимизационная задача состоит в том, чтобы найти максимум целевой функции при условиях (1) и (2). Нетрудно показать, что если из условий (1) определить величины y 1 1, y 1 2, y 2 1, y 2 2 и подставить их в целевую функцию, то в данном случае получится обычная задача на максимум линейной функции от x.

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

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

Методы стохастического программирования

Методы используются для задач, в которых все или отдельные параметры описываются с помощью случайных величин. Задачи стохастического программирования возникают тогда, когда каждое действие приводит к неоднозначному исходу и с каждым решением можно связать числовые параметры целевой функции fs(X, Q), s = 0, 1, . т. При этом параметры fs(X, Q) зависят от конкретного решения X и состояния среды Q. В стохастическом программировании Q является элементарным событием некоторого вероятностного пространства.

Читать еще:  Восстановление системы из безопасного режима

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

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

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

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

Общая постановка задачи оптимизации заключается в следующем:

1. Выбирается критерий

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

3. Накладывается система ограничения

4. Решение

модель — линейная или нелинейная

Ограничения

В зависимости от структуры модели применяются различные методы оптимизации. К ним относятся:

1. Аналитические методы оптимизации (аналитический поиск экстремума, метод множителей Лагранжа, Вариационные методы)

2. Математическое программирование (линейное программирование, динамическое программирование)

3. Градиентные методы.

4. Статистические методы (Регрессионный анализ).

Линейное программирование. В задачах линейного программирования критерий оптимальности представляется в виде:

где — заданные постоянные коэффициенты

— переменные задачи

Уравнения модели представляют собой линейные уравнения (полиномы) вида на которые накладывается ограничения в виде равенства или неравенства, т.е. (6.2)

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

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

, которая удовлетворяет условия (6.2) и обеспечивает в зависимости от постановки задачи max или min значение критерия.

Геометрическая интерпретация (рис.6.7) имеет вид: — критерий при наличии ограничении на переменных Х1 и Х2 типа равенств и неравенств

R имеет постоянное значение вдоль линии l. Оптимальное решение будет в точке S, т.к. в этой точке критерий будет max.Одним из методов решения задачи оптимизации линейного программирования является симплекс-метод.

Нелинейное программирование.Математическая постановка задачи нелинейного программирования заключается в следующем: Найти экстремум целевой функции , которая имеет вид нелинейности.

На независимые переменные налагаются различные ограничения типа равенств или неравенств

в настоящее время для решения задач нелинейного программирования применяются довольно большое число методов.

К ним относится: 1) Градиентные методы (метод градиента, метод наискорейшего спуска, метод образов, метод Розенброка и т.д.)

2) Безградиентные методы (метод Гауса-Зейделя, метод сканирования).

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

Рассмотрим метод градиента. В этом методе используется градиент целевой функции. В методе градиента шаги совершаются в направлении наибыстрейшего уменьшения целевой функции. (Рис. 6.8)

Рис. 6.8 Поиск минимума методом градиента

Поиск оптимума производится в два этапа:

1-этап: — находят значения частных производных по всем независимым переменным, которые определяют направление градиента в рассматриваемой точке.

2-этап: — осуществляется шаг в направлении обратном направлению градиента, т.е. в направлении наибыстрейшего убывания целевой функции.

Алгоритм градиентного метода может быть записан следующим образом:

(6.3)

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

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

К безградиентным методам поиска экстремума относится:

1. метод золотого сечения

2. метод с использованием чисел Фибония

3. метод Гауса-Зейделя (метод получения изменения переменной)

Методы стохастического программирования;

Методы динамического программирования

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

Динамическое программирование особенно эффективно для задач, условия которых позволяют составить сетевой график перехода от этапа к этапу, где узлы сети будут соответствовать различным значениям переменных, а дуги — допустимым вариантам решения (см. [6.51]).

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

¨ этапы решений (подзадачи, на которые она декомпозируется);

¨ управляемые переменные (варианты решений) на каждом этапе;

¨ информацию для решения задачи на каждом этапе;

¨ рекуррентные вычислительные процедуры, связывающие соседние этапы.

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

Различают прямые и обратные методы оптимизации. Они отличаются ДРУГ от друга различным представлением переменной и видом рекуррентных соотношений (см. [6.51]).

Методы используются для задач, в которых все или отдельные параметры описываются с помощью случайных величин. Задачи стохастического программирования возникают тогда, когда каждое действие приводит к неоднозначному исходу и с каждым решением можно связать числовые параметры целевой функции fs(X, Q), s = 0, 1, . т. При этом параметры fs(X, Q) зависят от конкретного решения X и состояния среды Q. В стохастическом программировании Q является элементарным событием некоторого вероятностного пространства.

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

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

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

Стохастическое программирование

Понятие о стохастическом программировании

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

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

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

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

Стохастическое программирование используется для решения задач двух типов.

1. В задачах первого типа прогнозируются статистические характеристики множества одинаковых экстремальных систем. Это задачи пассивного СП.

2. В задачах второго типа строятся алгоритмы планирования и управления в условиях неполной информации. Это задачи активного СП.

Читать еще:  Не включается безопасный режим

В зависимости от постановки задачи стохастического программирования её решения или планы могут вычисляться в двух видах:

1) в чистых стратегиях, когда результатом будет вектор оптимального плана или решения задачи. Решения в чистых стратегиях называются решающими правилами;

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

При построении моделей управления в условиях неполной информации существует два подхода к использованию информации:

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

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

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

Постановка задач СП

Большое число военных, экономических, технических задач записывается в виде задачи ЛП:

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

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

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

Задачи СП могут формулироваться в трех видах

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

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

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

Если в конкретной задаче требуется только чтобы вероятность попадания решения в допустимую область превышала некоторое заранее заданное число a >0 (обычно a >1/2), то такая постановка задач СП называется моделью с вероятностными ограничениями.

Если коэффициент cj детерминирован, то целевая функция задачи с вероятностными ограничениями не изменяется. Если сj случайно, то в качестве целевой функции задачи с вероятностными ограничениями берут математическое ожидание целевой функции

(10.1)

или вероятность превышения целевой функции некоторого фиксированного порога F :

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

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

(10.4)

такая постановка задач СП называется моделью со статистическими условиями.

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

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

Модели задач СП

Задачи СП различаются по трем признакам.

1. По характеру решений (детерминированный или случайный вектор, чистые или смешанные стратегии).

2. По выбору показателя качества, т. е. целевой функции. Еслинаходится:

а) математическое ожидание от целевой функции, т.е.

, то такие задачи называются М-моделями;

б) если минимизируется дисперсия целевой функции

то такие задачи называются V-моделями;

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

3. По способу расчленения ограничений задачи могут быть:

а) С построчными вероятностными ограничениями, когда учитываются стохастические связи только в одной строке:

где ai вероятность соблюдения условий,

ai =1 – ai ¾ вероятность несоблюдения условий. (от 0 до 1)

б) С общими вероятностными ограничениями Р[АХ ≥ В] ≥ a , когда могут быть коррелированы параметры не только строки, но и между строками. В такой модели не учитывается сравнительная важность отдельных ограничений.

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

Задача планирования добычи угля в априорных решающих правилах

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

— мощность и угол падения пластов,

— склонность к выбрасыванию газов,

— физико-механические свойства угля и пород,

— надежность оборудования, эксплуатационные расходы.

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

Для простоты допускается:

— показатель плана определяется средним значением суммарных затрат,

— область определения плана задается спросом на добываемый уголь (требуемый объем добычи) и фондом заработной платы.

Задача планирования угледобычи следующая.

Для i шахты заранее разрабатывается несколько вариантов развития. Требуется установить наиболее рациональный, с точки зрения объединения шахт, вариант развития каждой шахты.

Пусть , если для i -й шахты принят j-й вариант, иначе По каждой шахте реализуется только один вариант, т. е. .

— годовые затраты на добычу угля в i-й шахте по j-му варианту при реализации w случайных параметров, зависящих от природных факторов.

годовой объем добычи угля в i-й шахте по j-му варианту при реализации w случайных природных факторов.

— годовой фонд зарплаты i -й шахты по j-му варианту развития при реализации w случайных природных факторов.

d — требуемая в соответствии с планом более высокого уровня годовая добыча угля по объединению в целом.

k — общий фонд зарплаты по объединению.

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

. (10.5)

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

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

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

Автор работы: Пользователь скрыл имя, 23 Июня 2011 в 01:36, курсовая работа

Описание

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

Содержание

Введение 3
1.Задачи математического моделирования 4
1.1.Виды программирования 4
1.2.Специфика стохастического программирования 6
1.3.Разновидности задач моделирования и подходов к их решению 7
2.Задачи стохастического программирования 12
2.1.Подходы к моделированию задач 12
2.2.Методы решения задач стохастического программирования 13
2.3.Пути решения задач 15
2.4.Формальная постановка стохастической задачи 17
Заключение 18
Список литературы 19

Работа состоит из 1 файл

Стохастические методы.doc

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

Или другой пример:

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

Прежде всего нужно выбрать показатель эффективности F. Разумеется, желательно, чтобы время ожидания врача было минимальным. Но время величина случайная и если применить «оптимизацию в среднем», то надо выбрать тот алгоритм, при котором время ожидания минимально.

Но дело в том, что время ожидания врача отдельными больными не суммируется: слишком долгое ожидание одного из них не компенсируется почти мгновенным обслуживанием другого. Чтобы избежать таких неприятностей, можно дополнить показатель эффективности добавочными требованиями, чтобы фактическое время ожидания врача было не больше какого предельного значения f. Поскольку время ожидания величина случайная, нельзя просто потребовать, чтобы выполнялось условие F≤ f, но можно потребовать, чтобы это условие выполнялось с большой вероятностью, настолько большой, чтобы событие F≤ f было практически достоверным. Пусть k=0,995 и потребуем, чтобы вероятность P(F≤ f ) ≥ k.

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

Читать еще:  Безопасное восстановление системы

Особенно осторожными надо быть с «оптимизацией в среднем», когда речь идет об единичной операции.

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

  • распределение вероятностей для параметров в принципе существует, но к моменту принятия решения не может быть получено;
  • распределение вероятностей для параметров вообще не существует.

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

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

Оптимальное решение (от лат. оptimum – «наилучшее») – наилучший среди возможных вариант решения поставленной задачи. Следует помнить, однако, что оптимальность любого решения носит относительный характер: данное решение будет наилучшим, но с точки зрения того набора ограничений, который лежит в основе формулировки рассматриваемой задачи. Оптимальность, при этом, означает экстремальное (минимальное или максимальное) значение критериального показателя (суммы показателей), относительно которого оценивается полученный вариант решения.

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

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

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

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

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

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

Для решения задач стохастического программирования обычно надо знать статистические характеристики исследуемой системы – ее математическое ожидание, дисперсию, среднее квадратическое отклонение, коэффициент вариации, закон ее распределения, представляемый в двух формах: плотность данного распределения (f(x)) и функцию распределения (F(x)). Плотность распределения случайной величины f(x) показывает вероятность появления каждого конкретного значения случайной величины, а интегральная функция F(x) – дает возможность определить вероятность появления случайной величины х≤а, скажем валовой региональный продукт меньше или равный конкретному значению.

Нелинейные стохастические задачи обычно решаются в М-постановке или в Р-постановке.

М-постановка – максимизация (минимизация) среднего значения целевой функции, а Р-постановка – максимизация вероятности получения максимального (минимального) значения целевой функции.

Роль стохастических моделей и методов в исследовании закономерностей поведения экономических систем и в разработке количественных методов планирования экономики и управления производством имеет два аспекта — методологический и вычислительный. И тот и другой связаны с одной из важнейших категорий современной математической логики — с понятием сложности, точнее, с понятиями «сложность алгоритма», «сложность вычислений» и «сложность развития».
Роль вычислительного аспекта проблемы определяется тем, что планирование, управление и проектирование происходят, как правило, в условиях неполной информации. Рыночная конъюнктура, спрос на продукцию, изменения в состоянии оборудования не могут быть точно предсказаны. В условиях конкурентной экономики дополнительно возникает направленная дезинформация.

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

2. Задачи стохастического программирования

2.1. Подходы к моделированию задач

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

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

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

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

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

Как и в любой задаче, основным её этапом является постановка задачи. На этапе постановки задачи необходимо:

  • описать задачу,
  • определить цели моделирования,
  • проанализировать объект или процесс.

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

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

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

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

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

Ссылка на основную публикацию
Adblock
detector