Модели сетевого планирования

     Под термином «природа» будем понимать комплекс внешних обстоятельств, при которых приходится принимать решения. Игры с «природой», т.е. когда одним из участников является человек (игрок С), а другим - «природа» (игрок П), называют также статистическими играми.  

Вопросы для письменных ответов. 

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

     Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:

     

     

, , .

     

     При этом система линейных уравнений (1) и неравенств (2), (3), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f{X) называется целевой функцией, или критерием оптимальности.

     Если  математическая модель задачи линейного  программирования имеет вид: то говорят, что задача представлена в канонической форме.189

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

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

     1) если в исходной задаче требуется  определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

     2) если в ограничениях правая  часть отрицательна, то следует умножить это ограничение на —1;

     3) если среди ограничений имеются  неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

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

     2. На чем основан графический  метод решения задач линейного  программирования (ЛП)

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

     Запишем задачу линейного программирования с двумя переменными: целевая функция: ограничения:

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

     Областью  допустимых решений системы неравенств может быть:

     • выпуклый многоугольник;

     • выпуклая многоугольная неограниченная область;

     • пустая область;

     • луч;

     • отрезок;

     • единственная точка.

     Целевая функция определяет на плоскости  семейство параллельных прямых, каждой из которых соответствует определенное значение Z.

     Вектор  С = ( ) с координатами C1 и С2, перпендикулярный этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор - направление убывания Z. Если в одной и той же системе координат изобразить область допустимых решений системы неравенств и семейство параллельных прямых, то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение.

     Для определения данной вершины построим линию уровня Z = CiXi + С2Х2 = О, проходящую через начало координат и перпендикулярную вектору С = (C1;С2), и будем передвигать ее в направлении вектора С = (c1;c2) до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты

указанной точки и определяют оптимальный  план данной задачи. 

Задачи  теории массового массового обслуживания 

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

Решение. n = 3, m = 6, l = 1, = 6 мин = 0,1 ч., n = = 10,

a = = 0,1.

В любой момент времени система находится в  одном из своих возможных состояний:

k = 0 – все  станки работают, очереди нет;

k = 1 – один  станок обслуживается, очереди  нет;

k = 2 – два  станка обслуживаются, очереди нет;

k = 3 – два  станка обслуживаются, один в  очереди, остальные работают;

………………………..………………………..………………………………

k = 6 – два  станка обслуживаются, четыре  в очереди на обслуживание, т.е.  ни один станок не работает.

Этим состояниям системы соответствуют вероятности:

Р₀, Р₁, Р₂, Р₃, …, Р₉. 

Определим значения для случая, когда очереди нет (0 £ k £ 2): 

b₀ = × 0,1° = 1;  b₁ = × 0,1¹ = 0,6;  b₂ = × 0,1² = 0,15.

Определим значения для случая, когда очередь есть (3 £ k £ 6): 

b₃ = × 0,1³ = 0,03; … b₆ = × 0,1⁶ = 0,00000225.

Результаты расчетов представлены в таблице:

 

Вероятность того, что в системе не будет ни одного требования:  

Р₀ = (1,7849725)^-1 = 0,560.

Среднее число  станков, стоящих в очереди: 

М₁ =

× Р_k = 0,0058.

Это означает, что  в среднем из 6 станков 0,0058 простаивают  в очереди на обслуживание.

Коэффициент простоя  станка в очереди

К₁ =

= 0,01.

Это означает, что  в среднем каждый станок 1 % времени  простаивает в очереди.

Среднее число  простаивающих станков (в очереди  и обслуживании) 

М₂ =

× Р_k = 0,57.

Это означает, что  в среднем 57 % рабочего времени 1 станок из 6 не будет работать.

Коэффициент простоя  станка в системе обслуживания 

К₂ =

= 0,095.

Это означает, что 9,5 % времени в среднем будет  простаивает каждый станок из 6.

Среднее число  свободных обслуживающих аппаратов (рабочих) 

М₃ =

× Р_k =0,896. 

Это означает, что  из двух человек в среднем один всегда свободен, а другой свободен в течение 89,6 % времени.

Коэффициент простоя  рабочего 

К₃ =

= 0,29. 

Это означает, что  в среднем каждый рабочий 29 % рабочего времени простаивает без работы. 

Теория  игр и статистических решений 

     Определить  наилучшую стратегию поведения  на рынке товаров и услуг с  помощью критериев: Байеса, Лапласа, Вальда, Сэвиджа, Гурвица и максимакса. Сi (I = 1 - m) – стратегии лица, принимающего решения, Пj (j = 1 - n) – вероятные состояния рыночной среды, q_j – вероятности проявления каждой из n вожможных ситуаций во внешней среде.