Теория оптимального планирования и управления

Московский  Авиационный Институт

(государственный  технический университет) 
 
 

 
 
 
 
 
 
 
 

Кафедра №302

"Автоматизированные  системы обработки информации  
и управления" 
 
 
 

Теория  оптимального планирования и управления 

Курсовая  работа

«Решение задачи стохастического программирования «Об игре с природой»» 

Вариант №153 
 
 
 
 
 

Выполнила студентка 

группы 03-322:

          Ильина Е. А. 
 
 

Проверил  профессор кафедры 302:

    Хахулин Г. Ф. 
 
 
 
 
 

Москва, 2011 

Содержание 

1. Цель работы           3
2. Содержательная постановка задачи       3
3. Формализованное описание задачи и метод её решения    3
4. Алгоритм программной реализации       4
5. Результаты ручного счёта         6
6. Результаты машинного счёта        7
7. Влияние вариации параметров на оптимальное решение и управление  8
8. Описание программной реализации                                                                              15
9. Вывод                    21
10. Приложение                    22

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
---
 
 
 
 
 
 
 
 
 
 
    

1. Цель  работы

 

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

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

    Провести  анализ на оптимальное решение вариаций параметров задачи. 

    

2. Содержательная  постановка задачи

 

    Задача  стохастического  программирования об «игре с природой».

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

    Оперирующая сторона должна выбрать одну из m стратегий своего поведения x_i (i = 1, т). Природа, определяя условия, в которых действует оперирующая сторона, может реализовать одно из п своих состояний θ_j (j = 1, п) с вероятностями P_j (полная группа несовместных событий).

    Реализации  каждой пары x_i и θ_j соответствуют определенные потери оперирующей стороны, заданные матрицей f_j(x_i,θ_j). 

    

3. Формализованное описание задачи и метод её решения.

 

    x_i - кол-во стратегий, которые должна принять оперирующая сторона (i=1,2,…,m)

    θ_j - кол-во состояний, которые может реализовать природа (j=1,2,…,n)

    f_j(x_i,θ_j) - потери оперирующей стороны, заданные матрицей (i=1,2,…,m), (j=1,2,…,n)

    P_j - вероятности происхождения состояний природы θ_j (j=1,2,…,n)

    В сумме вероятности происхождения  состояний природы P_j должны давать 1.

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

    а)   min          M[f(x,θ)] - минимум средних потерь

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

xє{x₁,x₂,…,x_m}

    б)  min           P(f(x,θ)≥f_p) -

    xє{x₁,x₂,…,x_m}

    f_p— заданное пороговое значение потерь.

    Каждую i-ю строку матрицы потерь f_j(x_i,θ_j) (j = 1, п) с соответствующими вероятностями Р_j (j = 1, n) можно рассматривать как

    ряд распределения дискретной случайной  величины "потери оперирующей стороны" при фиксированной стратегии x_j. С учетом этого

    

    

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

    Класс:  задача стохастического программирования

Метод решения: эта задача стохастического программирования решается косвенными методами на основе применения аппарата теории вероятностей. 2

 
 

а) алгоритм поиска оптимального решения  по критерию минимум  средних потерь:

4. Алгоритм программной реализации.

 

                                       

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

                                     

5. Результаты ручного счёта

 

Задача  об игре с природой на примере организации  зимней переправы  через реку.

Лёд на реке зимой может иметь 3 альтернативных состояния (θ_j):

1. Толщина и крепость льда исключает возможность его использования для организации переправы
2. Толщина и крепость льда недостаточна без организации предварительной подготовки
3. Толщина и крепость льда достаточна без предварительной подготовки

Вероятности состояний льда:

P₁(θ)=10^-6

P₂(θ)=0,1

P₃(θ)=0,899999

Оперирующая сторона должна задолго до переправы  принять действия (стратегии) (x_i):

1. организовать подготовку для осуществления переправы
2. такую подготовку не производить

P(θ)=

Матрица потерь будет иметь следующий  вид:

θ=3

θ=2

θ=1

 

где 0.5*10⁶, 200, 100, 10⁷, 400, 1 - затраты на осуществление переправы при различных состояниях льда (θ=1,2,3) и реализующих стратегиях действий (x=1,2),

а 10^-6, 0.1, 0.899999-вероятности состояний льда

Пороговое значение потерь f_p=250

1. Если  решаем задачу стохастического  программирования «Об игре с  природой» по критерию: минимум  средних потерь, то для минимизации  потерь воспользуемся формулой:

а)   min          M[f(x,θ)]

xє{1,2}

                M[x=1]=0.5*10⁶*10^-6+200*0.1+100*0.899999=110.5   

min

                M[x=2]=10⁷*10^-6+400*0.1+1*0.899999=50.9 

При минимизации  потерь по формуле а) наилучшей стратегией будет 2-ая (подготовку для осуществления  переправы не производить), т.е. x^o=2  z^o=50.9

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

 б)  min           P(f(x,θ)≥250)

     xє{1,2}

                 P(x=1)=10^-6

min

                 P(x=2)=0.1+10^-6=0.1

При минимизации  потерь по формуле б) наилучшей стратегией будет 1-ая (организовать подготовку для  осуществления переправы), т.е. x^o=1  z^o=10^-6

Примечание: x^o-оптимальная стратегия, z^o-оптимальное значение 
 
 
 
 
 

6. Результаты  машинного счёта

 

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

7. Влияние вариации параметров на оптимальное решение  и управление.

 

1.   Вариация вероятностей состояний природы P(θ)

Исходные  данные:

  P₁(θ)=10^-6

  P₂(θ)=0,1

  P₃(θ)=0,899999

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

а) по критерию: минимум средних потерь, то

x^o=2 - оптимальная стратегия

z^o=50.9 - оптимальное значение целевой функции

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

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

x^o=1

z^o=10^-6

Не меняя данные о затратах на осуществление переправы при различных состояниях льда (θ=1,2,3) и реализуемых стратегиях действий (x=1,2)-f(x,θ) и фиксируя одну из вероятностей состояния природы (льда) и меняя остальные две согласно соотношениям: P₂(θ)=P₂(θ)-∆;

P₃(θ)= P₃(θ)+∆

или наоборот:

P₂(θ)=P₂(θ)+∆;

P₃(θ)= P₃(θ)-∆

где ∆-малое число (∆<1)