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

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

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

 
 
 
 
 
 
 
 

Кафедра №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. Цель  работы
 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

xє{x1,x2,…,xm}

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

    xє{x1,x2,…,xm}

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

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

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

    

    

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

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

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

 
 

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

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

                                       

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

                                     

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

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

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

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

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

    P1(θ)=10-6

    P2(θ)=0,1

    P3(θ)=0,899999

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

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

P(θ)=

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

    X=1

    10-6

    		 0.1 0.899999
    0.5*106 200 100
    X=2

    107

    		 400 1

θ=3

θ=2

θ=1

 

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

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

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

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

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

      xє{1,2}

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

min

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

При минимизации  потерь по формуле а) наилучшей стратегией будет 2-ая (подготовку для осуществления  переправы не производить), т.е. xo=2  zo=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-ая (организовать подготовку для  осуществления переправы), т.е. xo=1  zo=10-6

Примечание: xo-оптимальная стратегия, zo-оптимальное значение 
 
 
 
 
 

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

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

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

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

  P1(θ)=10-6

  P2(θ)=0,1

  P3(θ)=0,899999

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

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

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

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

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

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

xo=1

zo=10-6

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

P3(θ)= P3(θ)+∆

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

P2(θ)=P2(θ)+∆;

P3(θ)= P3(θ)-∆

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

Получаем следующие  результаты: 

Сводная таблица.

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

Номер эксперимента θ 1 2 3 xo zo
1  
 
 
 
 
 
 
 
 
 
 
P(θ)		 10-6 0,05 0,949999 2 30,95
2 10-6 0,1 0,899999 2 50.9
3 10-6 0,2 0,799999 2 90,8
4 10-6 0,3 0,699999 1 130,5
5 10-6 0,4 0,599999 1 140,5
6 10-6 0,5 0,499999 1 150,5
7 10-6 0,6 0,399999 1 160,5
8 10-6 0,7 0,299999 1 170,5
9 10-6 0,8 0,199999 1 180,5
10 10-6 0,9 0,099999 1 190,5
11 0,000091 0,1 0,899909 1 155,5
12 0,100001 0,1 0,799999 1 50100,5
13 0,400001 0,1 0,499999 1 200070,5
14 0,500001 0,1 0,399999 1 250060,5
15 0,600001 0,1 0,299999 1 300050,5
16 0,700001 0,1 0,199999 1 350040,5
17 0,800001 0,1 0,099999 1 400030,5
18 0,050001 0,05 0,899999 1 25100,5
19 0,080001 0,02 0,899999 1 40094,5
20 0,090001 0,01 0,899999 1 45092,5
21 0,100001 0 0,899999 1 50090,5
 

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

Номер эксперимента θ 1 2 3 xo zo
1  
 
 
 
 
 
 
 
 
 
P(θ)		 10-6 0,05 0,949999 1 10-6
2 10-6 0,1 0,899999 1 10-6
3 10-6 0,2 0,799999 1 10-6
4 10-6 0,3 0,699999 1 10-6
5 10-6 0,4 0,599999 1 10-6
6 10-6 0,5 0,499999 1 10-6
7 10-6 0,6 0,399999 1 10-6
8 10-6 0,7 0,299999 1 10-6
9 10-6 0,8 0,199999 1 10-6
10 10-6 0,9 0,099999 1 10-6
11 0,000091 0,1 0,899909 1 0,000091
12 0,100001 0,1 0,799999 1 0,100001
13 0,400001 0,1 0,499999 1 0,400001
14 0,500001 0,1 0,399999 1 0,500001
15 0,600001 0,1 0,299999 1 0,600001
16 0,700001 0,1 0,199999 1 0,700001
17 0,800001 0,1 0,099999 1 0,800001
18 0,050001 0,05 0,899999 1 0,050001
19 0,080001 0,02 0,899999 1 0,080001
20 0,090001 0,01 0,899999 1 0,090001
21 0,100001 0 0,899999 1 0,100001
 

    Стратегия 2 говорящая о том, что оперирующая  сторона задолго до переправы  через реку должна осуществить подготовку оказалась оптимальной только в тех экспериментах, где производился поиск оптимального решения по критерию минимум средних потерь. И только до тех пор, пока вероятность неблагоприятного состояния природы была намного меньше, чем вероятность благоприятного состояния природы (P2(θ)<0,3; P3(θ)>0,7)

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

      1.   Вариация порогового значения потерь fр

Матрица затрат имеет вид:

θ 1 2 3
P(θ) 0,000001 0,1 0,899999
X1 500000 200 100
X2 10000000 400 1

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

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

пороговое значение потерь: 1

xo=1

zo= 1 

пороговое значение потерь: 2

xo=2

zo= 0,100001 

пороговое значение потерь: 60

xo=2

zo= 0,100001 

пороговое значение потерь: 90

xo=2

zo= 0,100001 

пороговое значение потерь: 100

xo=2

zo= 0,100001 

пороговое значение потерь: 101

xo=1

zo= 0,100001 
 

пороговое значение потерь: 210

xo=1

zo= 10-6 

пороговое значение потерь: 505000

xo=1

zo= 0 
 
 
 
 
 

Сводная таблица.

Номер эксперимента fp xo zo
1 1 1 1
2 2 2 0,100001
3 60 2 0,100001
4 90 2 0,100001
5 100 2 0,100001
6 101 1 0,100001
7 210 1 10-6
8 505000 1 0
 

    Пока пороговое значение потерь находилось в ограничениях 1<fp<101, оптимальной стратегией действий оперирующей стороны оставалась вторая стратегия: подготовку для осуществления переправы не производить. Т. к. вероятность крепкого состояния льда была достаточно велика, затраты при таком состоянии льда были не велики и превышали наше пороговое значение, т.е. выигрыш был достаточно велик, а потери минимальны. Как только пороговое значение потерь стало расти, нас стали интересовать более высокие затраты на осуществление переправы через реку и вероятность того, что лёд будет иметь крепкое состояние уменьшилась и для оперирующей стороны оптимальная стратегия поменялась на ту, которая обязывает проводить подготовку для переправы через реку. А когда пороговое значение потерь равнялось 1, получилось так, что абсолютно все затраты превысили его и оптимальное значение критерия стала 1, т.к. просуммировались все вероятности состояний природы. 

      1. Вариация  затрат на осуществление  переправы через  реку при различных  состояниях льда (θ=1,2,3) и реализуемых стратегиях действий (x=1,2)
P(θ) 0,000001 0,1 0,899999
X1 100 200 500000
X2 1 400 10000000

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

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

xo=1

zo= 450019,5001

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

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

xo=1

zo= 0,899999 

P(θ) 0,000001 0,1 0,899999
X1 1 400 10000000
X2 100 200 500000