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

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

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

 

 

Здесь Р, p_t – символы вероятности. Под допустимым планом в данной задаче подразумевается такой набор значений неизвестных, который обеспечивает выполнение i-гo условия с вероятностью Р, не меньшей заданной вероятности p_t. Для условий, выполнение которых очень важно, величина p_t выбирается близкой к единице; для менее существенных условий она берется ближе к нулю.

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

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

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

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

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

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

Задача  добычи электроэнергии.

Пусть имеются два  месторождения A и B электроэнергии, энергия  которых соответственно равны x и y ед. Для добычи энергии используется одна машина, которая либо с определенной вероятностью добывает часть энергии, либо выходит из строя и в дальнейшем не используется. Если машина работает на месторождении A, то с вероятностью p₁ она добывает часть r₁ имеющейся энергии и с вероятностью 1 – p₁ выходит из строя. Если машина работает на месторождении B, то с вероятностью p₂ она добывает часть r₂ имеющейся энергии и с вероятностью 1 – p₂ выходит из строя.

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

Решение.

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

Исходя из критерия задачи, определим функцию ƒ_N (x,y) как ожидаемое количество электроэнергии, добытой до выхода машины из строя.

В одноэтапном процессе в случае первоначального выбора для разработки месторождения A среднее количество добытой энергии составляет p₁r₁x и p₂r₂y при выборе месторождения B, следовательно, ƒ₁ (x, y) = max [p₁r₁x, p₂r₂y]

Рассмотрим (N + 1)-этапный процесс. Каким бы ни был первоначальный выбор, его продолжение на оставшихся N этапах должно быть оптимально. Ожидаемое количество добытой электроэнергии в (N + 1)-этапном процессе при первоначальном выборе месторождения А

(1) ƒ_А (x, y) = p₁ [r₁x + ƒ_N ((1 – r₁) x, y)],

 

а при выборе месторождения  В

 

(2) ƒ_В (x, y) = p₂ [r₂y + ƒ_N (x, (1 – r₂) y)]

 

По условию необходимо максимизировать общее количество добытой электроэнергии, поэтому, объединяя (1) и (2), получаем основное уравнение  для (N + 1)- этапного процесса:

(3)                                                                     p₁ [r₁x + ƒ_N ((1 – r₁) x, y)]

ƒ_N+1 (x, y) = max [ƒ_А (x, y), ƒ_В (x, y)] = max

                                                                          p₂ [r₂y + ƒ_N (x, (1 – r₂) y)]

 

Используя функциональные уравнения (1) и (3), определим оптимальное поведение в трехэтапном процессе, если x = 500, y = 300, p₁ = 0,6, r₁ = 0,5, p₂ = 0,7, r₂ = 0,7.

Рассмотрим одноэтапный  процесс [при этом используем уравнение (1)]. На 1-этапе работу можно начать либо на месторождении А, либо на месторождении В. В случае выбора месторождения А добыча электроэнергии составит в среднем ƒ₁ (x, y) = p₁r₁x = 0,6*0,5*500 = 150 (ед.)

Если в течение 1-ого  этапа машина не вышла из строя, то в начале 2-ого этапа необходимо сделать выбор: продолжить работу на месторождении А или начать работу на месторождении В на месторождении А добыто r₁x ед. электроэнергии и её остаток составляет x- r₁x (1- r₁)x ед.; на месторождении В энергия осталась прежней.

Решая функциональное уравнение, получаем

 

 

                                        p₁r₁ (1- r₁)x               0,6*0,5*0,5*500

ƒ₁ [(1 – r₁) x, y)] = max                        = max                                =

                                           p₂ r₂y                       0,7*0,7*300

            75

= max             = 147 (ед.)

            147

 

Следовательно, на 2-м  этапе машина должна работать на месторождении  В.

В начале 3-его этапа  следует сделать выбор: продолжать работу на месторождении В или  на месторождении А на месторождении  В добыто r₂y ед. электроэнергии, её остаток составляет y- r₂y = (1- r₂)y ед. Имеем

                                               p₁r₁ (1- r₁)x              0,6*0,5*0,5*500

ƒ₁ [(1 – r₁) x, (1- r₂)y] = max                      = max                                =

                                               p₂ r₂(1- r₂)y             0,7*0,7*0,3*300

             75

= max            = 75 (ед.)

             44,1

 

Следовательно, на 3-м  этапе машина должна работать на месторождении  А.

Таким образом, если на 1-м  этапе работа начата на месторождении А, то оптимальное поведение состоит в том, что на 2-м этапе надо начать работу на месторождении В, а на третьем этапе – продолжать работу на месторождении А.

Пусть работа начата на месторождении  В; тогда на 1-м этапе добыча электроэнергии составляет в среднем

 

ƒ₁ (x, y) = p₂r₂x = 0,7*0,7*300 = 147 (ед.)

 

В начале 2-ого этапа производим выбор:

 

                                    p₁r₁x                         150

ƒ₁ [ x, (1- r₂)y] = max                       = max           = 150 (ед.)

                                     p₂ r₂(1- r₂)y               44,1

 

т.е. работу следует начинать на месторождении А.

В начале 3-его этапа  также производим выбор:

                                               75

ƒ₁ [(1 – r₁) x, (1- r₂)y] = max           = 75 (ед.)

                                               44,1

 

т.е следует продолжать работу на месторождении А. Таким образом, если на 1-м этапе работа начата на месторождении В, то оптимальное поведение состоит в том, что на 2-м и 3-м этапах добыча ведется на месторождении А.

Рассмотрим двухэтапный  и трехэтапный процессы. Полагая  последовательно N = 1,2, из уравнения (3) определяем вид функций, необходимых для решения задачи.

При N = 1

(4)                       p₁ [r₁x + ƒ₁ ((1 – r₁) x, y)]

ƒ₂ (x, y) = max

                           p₂ [r₂y + ƒ₁ (x, (1 – r₂) y)]

 

При N = 2

 

 

(5)                       p₁ [r₁x + ƒ₂ ((1 – r₁) x, y)]

ƒ₃ (x, y) = max

                           p₂ [r₂y + ƒ₂ (x, (1 – r₂) y)]

 

(6)                                   p₁ [r₁(1 – r₁) x + ƒ₁ ((1 – r₁)² x, y)]

ƒ₂ ((1 – r₁) x, y) = max

                                        p₂ [r₂y + ƒ₁ ((1 – r₁) x, (1 – r₂)y)]

 

(7)                                  p₁ [r₁x + ƒ₁ ((1 – r₁) x, (1 – r₂)y)]

ƒ₂ (x, (1 – r₂) y) = max

                                      p₂ [r₂ + (1 – r₂) y + ƒ₁ (x, (1 – r₂)² y)]

 

Таким образом, кроме  значений ƒ₁ ((1 – r₁) x, y), ƒ₁ (x, (1 – r₂) y) и ƒ₁ ((1 – r₁) x, (1 – r₂)y), необходимо вычислить количество добытой электроэнергии в одноэтапном процессе для следующих случаев:

 

                                           p₁r₁(1 – r₁)² x                0,6*0,5*0,25*500

а) ƒ₁ (x, (1 – r₂)² y) = max                           = max                                =

                                             p₂ r₂y                          0,7*0,7*300

             37,5

= max               = 147 (ед.)

             147

 

если на 1-м и 2-м этапах машина работала на месторождении А, а на 3-м на месторождении В;

 

 

                                            p₁r₁x                               0,6*0,5*500

б) ƒ₁ (x, (1 – r₂)² y) = max                             = max                               =

                                            p₂ r₂ (1 – r₂)² y)               0,7*0,7*0,09*300

              150

= max               = 150 (ед.)

             13.23

 

если на 1-м и 2-м этапах машина работала на месторождении В, а на 3-м – на месторождении  А подставляя найденные значения функций в уравнения (4) – (7), окончательно получаем:

для двухэтапного процесса:

                           0,6*(0,5*500+147)               208,2

ƒ₂ (x, y) = max                                    = max              = 252 (ед.)

                           0,7*(0,7*300+150)                252

                                      0,6*(0,5*0,5*500+147)                163,2

ƒ₂ ((1 – r₁) x, y) = max                                        = max                =252

                                      0,7*(0,7*300+150)                        252

                                     0,6*(0,5*500+75)                       195