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

ЧАСТНОЕ УЧРЕЖДЕНИЕ ОБРАЗОВАНИЯ

«МИНСКИЙ ИНСТИТУТ УПРАВЛЕНИЯ»

Кафедра информационных технологий и высшей математики

Контролируемая самостоятельная работа

по дисциплине «Теория вероятностей»

на тему: «Параметрическое и стохастическое программирование»

Выполнила студентка 2го курса,

факультета экономики, специальности маркетинг

группы 100601с

Бычковская К.В.

Минск, 2012

Содержание:

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

2)      Графическое и аналитическое решение, задачи параметрического программирования  

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

Параметрическое линейное программирование

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

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

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

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

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

Отыскать максимум (или минимум) функции:

L(X, λ) =

при условиях

,   Xj ≥ 0,    

Если обратиться к геометрической интерпретации задачи, то можно заметить, что вектор-градиент линейной формы определяется её параметром. Например, для целевой функции L(X, λ) = λX1 + (1-λ)X2 при различных значениях параметра λ градиент определяет различные направления роста функции.

Нетрудно видеть, что, если при некотором значении параметра максимум достигается в вершине A, то небольшая вариация этого значения несколько изменит направление градиента, но не изменит положение точки максимума. Отсюда напрашивается вывод, что некоторый план, оптимальный при λ = λ0 оптимален и в окрестности λ0, т.е. при α ≤ λ ≤ β где λ0  ∈ [α, β].

Можно заметить, что при градиенте, ставшем перпендикулярным некоторой стороне многоугольника планов, имеем два разных оптимальных опорных плана с одним и тем же значением линейной формы, откуда можно утверждать непрерывность экстремума линейной формы по λ

В случае неограниченности множества планов можно утверждать, что если линейная форма не ограничена при λ = λ0, то она не ограничена при всех λ, больших или меньших λ0.

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

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

L(X) =

при условиях

,   Xj ≥0,   j = 1 ... n;   

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

Пример 1. Рассмотрим задачу минимизации

L(X, λ) = λX1 - λX2 - λX3 + λX4

при условиях

3X1 - 3X2 - X3 + X4 ≥ 5;

2X1 - 2X2 + X3 - X4 ≤ 3;

Xk ≥ 0,   k = 1 ... 4;    -∞ < λ < ∞.

Решение. Как обычно, приводим задачу к канонической форме и с использованием метода искусственного базиса отыскиваем начальный опорный план X0 = (0, 0, 0, 0, 0, 3, 5) c L(X0, λ) = 5M.

Так как определяющую роль на этом шаге решения играет величина M, превышающая все величины задачи, то не обращаем внимания на λ и, обнаружив невыполнение критерия оптимальности для X0, вводим в базис A4 вместо A7 (переходим к следующему опорному плану):

Полученный опорный план X1 = (0, 0, 0, 5, 0, 8) c L(X1, λ) = 5 будет оптимальным, если все значения Δk неположительны, т. е.

Решаем систему двух линейных неравенств и обнаруживаем, что найденный план X1 оптимален при λ = 3.

Исследуем оставшиеся из заданного диапазона значения λ.

Пусть λ > 3. Тогда Δ2 > 0 и вектор A2 подлежит вводу в базис, но в силу неположительности его компонент приходим к выводу, что при λ > 3 линейная форма задачи не ограничена снизу.

Пусть λ < 3. Тогда Δ1 > 0 и в базис вводится вектор A1:

Полученный опорный план является оптимальным, если все значения Δk неположительны, т. е.

Решая эту систему линейных неравенств, обнаруживаем, что найденный план X=(8/5, 0, 0, 1/5) c L(X, λ) = (8λ + 1)/5 оптимален при -2 ≤ λ ≤ 3.

Пусть λ < -2. Тогда Δ5 > 0 и вектор A5 подлежит вводу в базис; в силу неположительности его компонент приходим к выводу, что при λ < -2 линейная форма задачи не ограничена снизу.

Таким образом, мы получили решение задачи:

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

Алгоритм решения задачи в общей форме состоит из двух

частей.

1. Фиксируем значение t из заданного промежутка, допустим

самое меньшее t = а. Тогда в целевой функции все коэффициенты

станут постоянными. Решаем полученную задачу 

симплекс-методом и находим вершину, в которой Za достигает максимума.

2. Определяем все значения параметра t, для которых максимум

достигается в той же вершине. Найденный интервал исключаем из

заданного отрезка [а, Р]. Для оставшегося интервала снова решаем

задачу, т. е. переходим к п.1 алгоритма. Так продолжаем до тех пор,

пока не будет разделен на частичные интервалы весь отрезок[а, р*].

Проанализируем пункты алгоритма более подробно.

1.        Полагая t = а, целевая функция принимает вид:

Составляем первую симплекс-таблицу, добавляя две строки: для коэффициентов сj и dj (табл. 12.1):

Форма симплекс-таблицы для решения задачи

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

В строке Za табл. 12.1 в каждом столбце фактически будет  стоять одно число, равное cj + dja. В последних двух строках  записаны индексы линейной формы Z, для произвольного параметра t.

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

Необходимо отметить, что в табл. 12.2 столбцы,  соответствующие базисным переменным, являются нулевыми (т. е. содержат 1 на пересечении 5-столбца и 5-строки, а остальные нули).

Поскольку план, полученный в табл. 12.2, оптимален, все  коэффициенты Za строки неотрицательны:

(Pj + qja) > 0.

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

которых план, полученный в табл. 12.2, будет оставаться 

оптимальным. План оптимален, если все коэффициенты функции Z, будут

неотрицательны:

.

Столбцы, соответствующие базисным переменным, можно не

рассматривать. Из решения полученной системы неравенств 

можно найти интересующий нас интервал.

В интервале (12.4) целевая функция достигает максимума в той же вершине.

в) Пусть среди элементов qj- имеются как положительные, так и

отрицательные числа.

Разделив неравенства системы (12.3) на две группы  соответственно знакам qj, получаем два интервала (12.4) и (12.5), объединяя эти интервалы, получим

г) Если qj = 0, то соответствующий коэффициент функции 

будет неотрицательным при любом t, поэтому на такой столбец 

можно не обращать внимания.

Сравниваем полученный интервал (a1; а2) с заданным [a, B].

Независимо от значения а1; левой границей первого интервала 

будет а, так как щ больше а быть не может. Если а2 > B, то весь 

отрезок попадает внутрь интервала [a1, а2], и задача решена. Для 

любого значения параметра t € [a, B] максимум Zt достигается в 

одной и той же вершине

Если a2 < B, то найденный интервал исключаем из  рассмотрения и решаем задачу для оставшегося интервала (а2, B). Для этого

полагаем t = a2 и заменяем строку Za строкой Za2. За 

разрешающий столбец в новой таблице выбираем тот, по которому 

определено значение t= a2 (в этом столбце на пересечении с Za2-строкой

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

Для найденного решения снова определяем интервал  изменения параметра t и т. д. Если в разрешающем столбце не окажется

положительных элементов, задача на оставшемся интервале не 

имеет решения.

Пример 12.2. Решить задачу параметрического  программирования

Решение:

Приведем задачу к виду, допускающему применение алгоритма, и найдем выражение целевой функции при t=l (левый конец  заданного промежутка):

Составим первую симплекс-таблицу с дополнительными  строчками для функции Zt и выполним преобразование  симплекс-таблицы для решения задачи (табл. 12.3—12.4).

В табл. 12.4 получено оптимальное решение, так как все  коэффициенты

Zx-строки неотрицательны - х = (0; 0; 1; 0; 5; 3). 

Определим интервал для t, в котором оптимальное решение будет в той

же вершине. Так как все qj < 0 (табл. 12.4), то согласно (12.5)

a1= —оо, а2 = 12,5.

Для нашего случая a1 = 1 (левый конец заданного отрезка).  Таким образом, на отрезке [1; 12/5] решение будет в точке х = (0; 0,1; 0; 5; 3). Исключаем найденный отрезок из рассмотрения и решаем задачу для оставшегося отрезка [12/5; 8]. Для этого, полагая t = 12/5, вычисляем для него строку Z12/5- В первом столбце  получим нуль; остальные коэффициенты Z12/5 строки положительны, а другие элементы остаются прежними (табл. 12.5). За разрешающий столбец в табл. 12.5 выбираем тот, по которому определено  значение t = a2. Если нули находятся в нескольких столбцах, то за  разрешающий можно брать любой из них. Новый план х = (1/2; 0; 0; 0; 3/12; 0) оптимален, так как в строке Z12/5 нет отрицательных элементов (практически элементы строки 212/^ остались без  изменения).

В последней строке табл. 12.6 все <т, > 0, поэтому согласно (табл. 12.6) a1 = 12/5, а2 = +°°; t e [12/5; о]. Таким образом, заданный промежуток разбился на два; при t = 12/5 оптимальное значение достигается в обеих вершинах и в любой точке, являющейся их  выпуклой линейной комбинацией

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

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

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

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

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

В задаче линейного программирования:

1.1

заданные величины сj, аij,,bi, dj, Dj. Часто на практике величины cj, aij bj, могут быть случайными. Так, если bi — ресурс, то он зависит от ряда факторов. Аналогично, сj — цены — будут зависеть от спроса и предложения, aij — расходные коэффициенты — от уровня техники и технологии. Задачи, в которых сj, аij,,bi — случайные величины, относят к задачам стохастического программирования. Переход от чистых стратегий к смешанным расширяет область определения задачи. Достижимый максимум целевой функции может при этом только увеличиться, а достижимый минимум — только уменьшиться. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи.

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

Стохастическая постановка целевой функции может быть двух видов: М-постановка и Р-постановка.

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

Для решения задачи стохастического программирования в Р-постановке и с вероятностными ограничениями переходят к детерминированному эквиваленту.

Для целевой функции детерминированный эквивалент имеет вид:

при минимизации целевой функции

2.1

при максимизации целевой функции

2.2

где σ2j — дисперсия случайной величины сj Решение таких задач затруднительно, поэтому далее рассматриваем целевая функция только в М- постановке.