![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
![]() |
|
![]() |
![]() |
||||||
![]() |
Eng | Rus | Ukr | ![]() |
![]() |
||||
![]() |
|||||||
![]() |
![]() |
||||||
![]() |
![]() |
![]() |
|||||
![]() |
Исследование операций
|
04.10.2008
|
![]() |
![]() |
|||
8.2. ДВухэтапные ЗАДАЧИ СТОХАСТИЧескОГО ПРОГРАММИРОВАНИЯПостановка двухэтапной задачи При исследовании многих задач планирования и управления в условиях действия случайных возмущений возможно и целесообразно процесс принятия решений представить разделенным на два этапа. На первом этапе выбирается предварительный план, позволяющий провести подготовительные работы. На втором этапе производится компенсация невязок, выявленных после наблюдения реализованных значений случайных параметров условий задачи. Естественно, что предварительный план и план-компенсация должны быть согласованы таким образом, чтобы обеспечить минимум среднего значения суммарных затрат, возникающих на обоих этапах решения задачи. В разрешимой задаче выбор предварительного плана должен гарантировать существование плана-компенсации. Рассмотрим следующую задачу: минимизировать при условиях
где Допустим, что элементы матрицы Представим себе процесс решения задачи (8.2.1)-(8.2.4) следующим образом. Выберем сначала (на первом этапе) вектор
где За нарушение условий задачи устанавливается штраф, зависящий от величины составляющих вектора у, компенсирующего невязку. Будем характеризовать штраф величиной Вектор у может быть выбран многими способами. Обычно, его выбирают таким образом, чтобы обеспечить минимальный ожидаемый штраф за компенсацию условий задачи, определяемых предварительным планом х. Иными словами, на втором этапе решается задача минимизировать при условиях
Оба этапа могут быть сведены в один. Тогда приходим к постановке двухэтапной задачи стохастического программирования
при условиях
Таким образом, решение двухэтапной стохастической задачи состоит из двух векторов: детерминированного Затраты на план-компенсацию должны быть наименьшими. Поэтому целесообразно для перспективного планирования (двухэтапной схемы) использовать малочувствительные к вариации параметров условия задачи. Область определения планов первого этапа. Рассмотрим множество предварительных планов x двухэтапной задачи. Пусть x - вектор, удовлетворяющий ограничениям задачи (8.2.8)-(8.2.10). В общем случае, когда матрица компенсации B задана произвольным образом, нет гарантии, что не существует такой реализации
не будет иметь решения. В этом случае невозможно ликвидировать возникшую невязку с помощью вектора компенсации y. Для того, чтобы вектор x был допустимым планом двухэтапной задачи, необходимо, чтобы для всех
Такие неявно заданные ограничения на выбор вектора Обозначим множество векторов
Тогда область определения вектора X задается множеством Теорема 8.1. Для того, чтобы матрица компенсации существует неотрицательное решение системы Проверка условия (8.2.12) достаточно затруднительна. Однако в некоторых случаях эти условия могут быть конструктивными. Пусть, например,
По условию 1) теоремы первые
Если все Условия разрешимости задачи второго этапа. Запишем задачу (8.2.8)-(8.2.11) в виде минимизировать при условиях
где
Условия разрешимости задачи второго этапа (8.2.17)-(8.2.19) формулируются следующим образом [57]. Теорема 8.2. Для разрешимости задачи второго этапа при любых реализациях
была разрешимой. Доказательство. По условию множество планов задачи (8.2.17)-(8.2.19) непусто. Согласно теореме двойственности функции ЛП снизу тогда и только тогда, когда область определения планов двойственной задачи для каждого x, A и B
при условии
непуста. Поскольку область определения задачи (8.2.21), (8.2.22) не зависит от Эквивалентная детерминированная задача. Построим детерминированный эквивалент двухэтапной задачи стохастического программирования. Ее решением является предварительный план X. По составляющим оптимального предварительного плана X и реализации параметров условий задачи Эквивалентная детерминированная задача имеет вид:
Исследуем функционал Рассмотрим задачу второго этапа (8.2.17) - (8.2.19) и двойственную к ней задачу (8.2.21), (8.2.22) для каждого Предположим, что задача второго этапа и двойственная к ней разрешимы. По теореме 2.5 двойственности для задач ЛП имеем
где Учитывая эти обозначения, двухэтапную задачу можно переписать так:
или
Детерминированная задача (8.2.23), эквивалентная двухэтапной задаче (8.2.14)-(8.2.19), является задачей выпуклого программирования. Некоторые частные постановки двухэтапной задачиВ общем случае отыскание точного решения детерминированного эквивалента двухэтапной задачи представляет значительные трудности, поэтому решение ищут приближенно. Однако в ряде частных случаев эта задача существенно упрощается и может быть решена классическими методами линейного и выпуклого программирования. Рассмотрим некоторые случаи. Рассмотрим двухэтапную задачу, в которой случайным является только вектор ограничений Аналогичным образом разобьем векторы
при условиях
где
при условиях
Здесь Необходимое и достаточное условие существования конечного решения задачи второго этапа в данном случае приобретает следующий простой вид. Как известно, в общем случае это условие записывается в форме
В рассматриваемом случае Задача, двойственная к (8.2.27)-(8.2.29), записывается так:
при условии
Задача (8.2.30) легко решается и ее решение имеет вид
где
Поэтому эквивалентная выпуклая задача для двухэтапной стохастической задачи (8.2.27)-(8.2.29) записывается следующим образом:
при условиях
где Приведем еще одну форму записи этой же задачи. Введем обозначения
Заметим, что функции
при условиях
Исследуем функции Если Вычислим значения Отсюда Рассмотрим три случая. 1. Пусть
2. Пусть
3. Следовательно, функция
Как видим, функция При некоторых частных распределениях составляющих вектора Пример 8.2. Пусть сотавляющие
Допустим, что
Тогда
Учитывая, что
получаем
Тогда двухэтапная задача стохастического программирования (8.2.40)-(8.2.43) приводится к следующей задаче квадратичного программирования [18]:
при условиях
или
Пример 8.3. Пусть все компоненты
и
В таком случае, в соответствии с формулой (8.2.50), получим Интегрируя выражение (8.2.51) по частям, после несложных преобразований получим
Подставляя (8.2.52) в (8.2.44) и учитывая, что Следовательно, двухэтапная задача стохастического программирования сводится к следующей задаче выпуклого программирования: при условиях (8.2.41), (8.2.42). В случае, когда можно предполагать, что
Итак, эта задача сводится к задаче квадратичного программирования. Пример 8.4. Рассмотрим случай конечного числа реализаций случайного вектора Обозначим
Введем переменные
В этом случае Итак, задача стохастического программирования (8.2.40)-(8.2.43) сводится к задаче ЛП вида
при условиях
где
Пример 8.5. Двухэтапную задачу, в которой все случайные компоненты вектора
Соответствующая детерминированная задача тогда запишется следующим образом: при условиях
Пример 8.6. Рассмотрим задачу, приводящую к двухэтапной модели стохастического программирования. Пусть существует несколько предприятий, производящих некоторый однородный продукт. Предприятия расположены в пунктах Объемы производства продукта обозначим соответсвенно Обозначим производственные затраты по производству единицы продукта в пункте Обозначим через Допустим, что величины Решение. Составим математическую модель задачи. На первом этапе необходимо найти такой план перевозок
при условиях
Обозначим объем производства продукта, ввезенного в пункт
Введем вектор компенсации где Используя соотношения (8.2.40)-(8.2.43), запишем детерминированный эквивалент для данной задачи в следующем виде:
при условиях
Используя выражение (8.2.46), приведем эту задачу к виду
при ограничениях
где
Задача (8.2.74)-(8.2.77) является задачей квадратичного программирования с ограничениями-равенствами и ограничениями-неравенствами. Для ее решения , применим теорему Куна-Таккера. Составим функцию Лагранжа для данной задачи Запишем необходимые и достаточные условия оптимальности:
Для дальнейшего решения этой задачи применим стандартные методы ЛП или метод перебора вариантов. |
![]() |
||||||
![]() |
|||||||
Copyright © 2002-2004 | ![]() |
||||||
![]() |
![]() |