Марковские процессы. Основные понятия и задачи, решаемые с помощью Марковских процессов

>       В частности, из рис. 3.2. видно, что реализовавшаяся цепь выглядит так: S₀—S₁—S₀—… Переходы произошли в следующие моменты времени: T₀—T₁—T₂—T₃—…, где T₀ = 0, T₁ = τ₀₁, T₂ = τ₀₁ + τ₁₀.

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

Практические  задания 

Задание 1

Три предприятия данного экономического района могут производить однородную продукцию в количествах, соответственно равных 180, 350, 20 единиц. Эта продукция должна быть поставлена пяти потребителям в количествах, соответственно равных 110, 90 120, 80, 150 единиц. Затраты, связанные с доставкой продукции задаются матрицей

       | 2 4 1 6 7|

С = | 3 3 5 4 2|

       | 8 9 6 3 4|.

    Составить такой план прикрепления  покупателей продукции ее поставщикам,  при котором общая стоимость  перевозок является минимальной.

Решение:

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

     Пусть х _ij – количество сырья, перевозимого от I –ого поставщика j- тому потребителю.

     Параметры задачи:

а₁ =180 а₂ = 350 а₃ = 20 – предложение продукции

в₁=110 в₂=90 в₃=120 в₄=80 в₅=150 – спрос на продукцию

       | 2 4 1 6 7|

С=  | 3 3 5 4 2|

       |8 9 6 3 4 |

    Проверяем условие сбалансированности задачи:

180+350+20=550

110+90+120+80+150=550

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

     Математическая модель задачи  выглядит так:

F(x) = 2х₁₁ +4х₁₂ +х₁₃ +

+6х₁₄+7х₁₅+3х₂₁+3х₂₂+5х₂₃+4х₂₄+2х25+8х₃₁+9х₃₂+6х₃₃+7х₃₄+4х₃₅→min

 х₁₁+х₁₂+х₁₃+х₁₄+х₁₅=180

 х₂₁+х₂₂+х₂₃+х₂₄+х₂₅ =350

 х₃₁+х₃₂+х₃₃+х₃₄+х₃₅ =20

 х₁₁+х₂₁+х₃₁ =110

х₁₂+х₂₂+х₃₂=90

х₁₃+х₂₃+х₃₃=120

х₁₄+х₂₄+х₃₄=80

х₁₅+х₂₅+х₃₅=150

     Далее для нахождения оптимального плана задачи воспользуемся методом Фогеля. Записываем транспортную таблицу с указанием предложения и спроса сырья и тарифов на перевозку.

Полученный  по методу Фогеля план перевозок имеет  вид:

               х₁₁=60   х₁₂=0    х₁₃=120  х₁₄=0   х₁₅=0

Х₁ =        х₂₁=50   х₂₁=90  х₂₃=0     х₂₄=80   х₂₅=130

               х₃₁=0     х₃₂=0   х₃₃=0     х₃₄=0    х₃₅=20 
 

Х₁ =60*2+1*120+3*50+3*90+4*80+2*130+4*20=1320 (лин. ед.) 

  Задание 2

Для изготовления трех видов изделий А, В, С используется токарное, фрезерное, сварочное и шлифовальное оборудование. Затраты времени на обработку одного изделия для каждого из типов оборудования, общий фонд рабочего времени каждого из типов используемого оборудования, а также прибыль от реализации одного изделия каждого вида учтены в таблице

Составить модель производства, обеспечивающую предприятию максимальную прибыль.

Решение:

Данная  задача относится к задаче планирования производства.

Пусть а_ij – количество рабочего времени, необходимое для производства одного изделия j-того вида

          2 4 5

а_ij =   1 8 6

          7 4 5

          4 6 7

в_i – фонд рабочего времени на предприятии, в_i ≥ 0

в₁ =120

в₂ = 280

в₃ = 240

в₄ = 360

с_i –прибыль от реализации одной единицы продукции j – того вида

с₁ =10

с₂= 14

с₃ =12

х_j – объем производства изделия j-ого вида.

Тогда математическая модель плана имеет  вид

F(x) = 10х₁ +14х₂+12х₃→ max

2х₁+4х₂+5х₃ ≤ 120

Х₁+8х₂+6х₃ ≤ 280

7х₁+4х₂+5х₃ ≤ 240

4х₁+6х₂+7х₃ ≤ 360 
 
 
 
 
 

Задание 3

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

F(X) = 2х₁-5х₂ → min

3х₁+4х₂ ≤ 6

2х₁+3х₂ ≤ 4

х₁ ≥0, х₂ ≥0 

Решение:

      На координатной плоскости Х₁ОХ₂ строим допустимую многоугольную область и вектор-градиент линейной функции F (x). Затем строим график целевой функции, и передвигаем его в направлении противоположном вектору – градиенту. График функции покидает многоугольную область в точке А, координаты которой находим из системы уравнений.

      Таким образом, оптимальный план задачи равен {2, 0}, на котором достигается минимум функции F(x) = 4 .

  Х₂ 
 
 
 

                                                                                         

3/2                                                                              f (x) = 2х₁-5х₂

4/3

 
 

   _{0                                                             2                                                                                                                               Х}

                                     А

Задача 4

Интенсивность равномерного спроса холодильников  «Ока» в магазине составляет 200 шт. в год. Организационные издержки для одной партии составляют 40 тыс. руб. Цена одного холодильника равна 10 тыс. руб., а издержки содержания холодильников на складе составляют 0,2 тыс. руб. за один холодильник в год. Найти оптимальный размер партии, число поставок и продолжительность цикла.

Решение:

Данная  задача относится к основной модели управления запасами.

Оптимальный размер партии определим следующим образом

g=√2·d·s ∕ h, где

d – годовая интенсивность спроса

s – организационные издержки за партию

h – издержки на хранение запаса

g=√2·40·200/0,2 = 282 шт.

Определим число партий

n= d/g = 200/282 = 0,7, т.е. в год производится одна поставка.

Рассчитаем  продолжительность цикла

T=365/ n =365/ 0,7 = 521 день. 

Задание 5

Найти кратчайший путь на графе от вершины 1 до вершины 8. Построить коммуникативную  сеть минимальной длины.

                              1

          1           9                             1

              6                      1

            5            1             1                 8                      

                                                                  8