Методические указания к решению задач контрольной работы
Задача 1
Задача коммивояжера является классическим примером применения метода ветвей и границ. Метод ветвей и границ – это метод направленного перебора множества вариантов решений задачи. Графически перебор можно представить в виде дерева, т.е. связного графа, не содержащего циклов. Корень этого дерева – все множество вариантов, а вершины дерева – подмножества частично упорядоченных вариантов решения. Метод ветвей и границ не гарантирует того, что в ходе решения задачи не будет произведен полный перебор.
Решение:
Путь состоит из пяти звеньев. Построим вершины и для каждой подсчитаем оценку границ (рисунок 3).
Наименьшую длину 320 км имеют маршруты А – В – С – Д – А и А – С – Д – В – А. Вершины А – В – С; А – С – В; А – Д – В – С и А – Д – С – В не подвергались ветвлению, так как не существует маршрута соединяющего пункты В и С.
Вывод:как мы видим два маршрута имеют один и тот же результат, следовательно коммивояжер может воспользоваться маршрутами А – В – С – Д – А и А – С – Д – В – А и при этом проедет всего 320 км.
|
рисунок 3
Задача 2
На основе сетевого графика (рисунок 4) определить: критический путь, резервы событий, а также полные и свободные резервы операций.
рисунок 4
|
Решение
Нанесем на исходный рисунок сроки свершения событий, по которым можно рассчитать поздние и ранние сроки свершения событий.
Для определения резервов времени необходимо вычислить ранние сроки свершения событий. Ранний срок свершения событий это ранний срок необходимый для выполнения всех работ, предшествующих данному событию. Он вычисляется по формуле:
, отсюда 
Поздний срок свершения события – называется самый поздний момент времени, после которого остается столько времени, сколько необходимо для завершения всех работ следующих за этим событием, он рассчитывается по формуле 
, и следовательно:
После определения ранних и поздних сроков свершения событий переходят к расчету резервов времени событий
Разность между поздним и ранним свершением срока события составляет резерв времени этого события. Резерв времени показывает, на сколько времени может задержаться совершение события без изменения срока наступления завершающегося события. Резерв времени вычисляется по формуле:
, и следовательно:
На основе полученных данных, так как у работ, лежащих на критическом пути резерв времени равен нулю (т.к. ранние и поздние сроки свершения события совпадают), то можно утверждать, что критический путь пройдет через события 1-2-5-6-8-9.
рисунок 5
|
Обозначим на рисунке 5 критический путь жирной чертой:
Полный резерв времени работы – это максимальное количество времени, на которое можно задержать начало работы или увеличить ее продолжительность, не изменяя длительность критического срока. Формула полного резерва времени:
, и следовательно:
|
|
Свободный резерв времени – это максимальное количество времени, на которое можно увеличить продолжительность данной работы, не изменяя при этом ранних сроков начала последующих работ, при условии, что непосредственно предшествующее событие наступило в свой ранний срок. Свободный резерв считается независимым резервом. Его использование на какой-либо работе не меняет величин свободных резервов остальных работ сети. Рассчитывается по формуле:
, и следовательно:
| 
|
Проведенные расчеты показывают, что можно сократить сроки решения проблемы путем перераспределения времени между ненапряженными и критическими путями, то есть часть ресурсов безболезненно можно снять с ненасыщенного пути ((1,4); (1,9); (2,6); (3,5); (3,8); (4,6); (7,8)) и перевести их на критический путь ((1,2); (2,5); (5,6); (6,8); (8,9)).
Вывод:критический путь пройдет через события 1 – 2 – 5 – 6 – 8 – 9 и при этом критический срок свершения операций составит 36 дней.
Задача 3
Упростить игру «n x m» (приложение № 3) до игры «2х2» и решите ее графическим методом и методом опций.
| В1 | В2 | В3 | В4 | В5 | |
| А1 | |||||
| А2 | |||||
| А3 | |||||
| А4 |
Решение:
Рассчитаем минимаксные стратегии игроков А и В и проверим будут ли они устойчивыми, применив «принцип минимакса» (поступай так, чтобы при наихудшем для тебя поведении противника получить максимальный выигрыш), то есть определим верхнюю (точка «минимакса» 
– минимальное значение из максимальных значений по стратегии) и нижнюю (точка «максимина» 
– максимальное значение из минимальный значений по стратегии) цену игры.
| В1 | В2 | В3 | В4 | В5 | α | |
| А1 | ||||||
| А2 | ||||||
| А3 | ||||||
| А4 | ||||||
| β |
Так как α = 5 и β = 6 → α ≠ β, то стратегии являются неустойчивыми и следовательно для определения оптимальных стратегий игры, мы можем упростить исходную матричную форму «m x n», используя принцип дублирующих и доминирующих стратегий:
Стратегия Аi игрока А называется «доминирующей» над стратегией Аk, если в строке Аi стоят выигрыши не меньшие, чем в соответствующих клетках строки Аk, и из них по крайней мере - один - действительно больше, чем в соответствующей клетке строки Аk. Стратегия Bj игрока B называется «доминирующей» над стратегией Вk, если в столбце Вj стоят выигрыши не большие, чем в соответствующих клетках столбца Вk, и из них по крайней мере один действительно меньше, чем в соответствующей клетке строки Вk. Если все выигрыши стратегий игрока А или игрока В соответственно равны между собой, то такие стратегии называются «дублирующими».
| В1 | В2 | В3 | В4 | В5 | |
| А2 | |||||
| А3 | |||||
| А4 |
Проверяем по игроку А: А1 < A3 – следовательно удаляем стратегию А1.
| В3 | В4 | В5 | |
| А2 | |||
| А3 | |||
| А4 |
Проверяем по игроку В: В3 < В2 – следовательно удаляем стратегию В2; В4 < В1 – следовательно удаляем стратегию В1.
| В3 | В4 | В5 | |
| А3 | |||
| А4 |
Проверяем по игроку А: А2 < A3 – следовательно удаляем стратегию А2.
| В3 | В5 | |
| А3 | ||
| А4 |
Проверяем по игроку В: В3 < В4 – следовательно удаляем стратегию В4.
При помощи принципа дублирующих и доминирующих стратегий игру «4 х 5» мы упростили до игры «2 х 2».
Решим данную игру при помощи графического метода:
рисунок 6 а, б.
На основе графиков для игрока А (рисунок 6а) и для игрока В (рисунок 6б) можно сделать вывод: вероятности выбора стратегий игрока А (0; 0,83; 0,17; 0); игрока В (0; 0; 0,5; 0; 0,5), следовательно игрок А предпочтет стратегию А2, а игрок В может выбрать любую из двух стратегий В3 или В5, при этом средняя цена игры составит 5,5.
Для матриц «2 х 2» можно использовать метод определения точек оптимума функции двух переменных. Обозначим вероятность выбора стратегии А2 через р, тогда вероятность выбора стратегии А3 через 1-р; вероятность выбора стратегии В3 через q, а вероятность выбора стратегии B5 через 1-q, так как сумма вероятностей выбора строк равна 1.
Подсчитаем математическое ожидание величины выигрыша игрока А.
Найдем значения р и q приравнивая к нулю частные производные функции 
.
В среднем за игру игрок А выигрывает, а игрок В проигрывает:
Вывод: вероятности выбора стратегий игрока А 
; игрока В (0; 0; 0,5; 0; 0,5), следовательно игрок А предпочтет стратегию А2, а игрок В может выбрать любую из двух стратегий В3 или В5, при этом средняя цена игры составит 5,5.
Задача 4
А) Рассмотрим игру, заданную платёжной матрицей «2 х n»: 
Решение
На плоскости х0y (рисунок 7) введём систему координат и на оси 0х отложим отрезок единичной длины А1, А2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока 1.
рисунок 7
|
В точках А1 и А2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока А при стратегии А1, а на втором – при стратегии А2.
Если игрок А применит стратегию А1, то выиграет при стратегии В1 игрока 2 – 2, при стратегии В2 – 3, а при стратегии В3 – 11. Числам 2, 3, 11 на оси 0х соответствуют точки В1, В2 и В3.
Если же игрок А применит стратегию А2, то его выигрыш при стратегии В1 равен 7, при В2 – 5, а при В3 – 2. Эти числа определяют точки В¢1, В2¢, В3¢ на перпендикуляре, восстановленном в точке А2. Соединяя между собой точки В1 и В¢1, В2 и В¢2, В3 и В¢3 получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий.
На основе рисунка 7 определяем точку максимина α (максимальную точку из минимальных значений). Это точка пересечения прямых В2 B¢2 и В3 B¢3. Таким образом мы можем найти вероятности выбора оптимальной стратегии игрока А (р1; р2) при помощи матрицы 
. Следовательно получим систему уравнений:
.
Отсюда 
, при цене игры 
.
Оптимальные стратегии для игрока 2, определяем по этой же матрице и вероятности выбора стратегий игрока В (q1; q2; q3) соответственно найти из системы
и, следовательно, 
. (Из рисунка видно, что стратегия B1 не войдёт в оптимальную стратегию).
Вывод: вероятности выбора стратегий игрока А 
; игрока В 
, следовательно игрок А предпочтет стратегию А2, а игрок В – стратегию В2, при этом средняя цена игры составит 
.
Б) Рассмотрим игру, заданную платёжной матрицей «n х 2»: 
Решение
рисунок 8
|
На плоскости х0y (рисунок 8) введём систему координат и на оси 0х отложим отрезок единичной длины В1, В2, каждой точке которого поставим в соответствие некоторую смешанную стратегию игрока В.
В точках В1 и В2 восстановим перпендикуляр и на полученных прямых будем откладывать выигрыш игроков. На первом перпендикуляре (в данном случае он совпадает с осью 0y) отложим выигрыш игрока В при стратегии В1, а на втором – при стратегии В2.
Если игрок В применит стратегию В1, то выиграет при стратегии А1 игрока А – 6, при стратегии А2 – 4, при стратегии А2 – 2, а при стратегии А4 – 1. Числам 5, 6, 7, 8 на оси 0х соответствуют точки А1, А2, А3 и А4.
Если же игрок В применит стратегию В2, то его выигрыш при стратегии А1 равен 5, при А2 – 6, при А2 – 7, а при А3 – 8. Эти числа определяют точки А¢1, А2¢, А3¢, А3¢ на перпендикуляре, восстановленном в точке В2. Соединяя между собой точки А1 и А¢1, А2 и А¢2, А3 и А¢3, А4 и А¢4 получим три прямые, расстояние до которых от оси 0х определяет средний выигрыш при любом сочетании соответствующих стратегий.
На основе рисунка 8 определяем точку минимакса β (минимальную точку из максимальных значений). Это точка пересечения прямых А1 А¢1 и А4 А¢4. Таким образом мы можем найти вероятности выбора оптимальной стратегии игрока В (q1; q2) при помощи матрицы 
. Следовательно получим систему уравнений:
.
Отсюда 
, при цене игры 
.
Оптимальные стратегии для игрока 2, определяем по этой же матрице и вероятности выбора стратегий игрока А (р1; р2 ;р3; р4) соответственно найти из системы 
и, следовательно, 
. (Из рисунка видно, что стратегии А2 и А3 не войдут в оптимальные стратегии).
Вывод: вероятности выбора стратегий игрока А 
; игрока В 
, следовательно игрок А предпочтет стратегию А1, а игрок В – стратегию В2, при этом средняя цена игры составит 
.
Задача 5
Рассчитать финальные вероятности (р0, р1, р2, р3) состояния системы по схеме, представленной на рисунке 2, если: λ1=1, λ2=2, μ1=2, μ2=3.
Решение
Имея в своем расположении размеченный граф состояний (рисунок 2), можно найти все финальные вероятности состояний (р0, р1, р2, р3) как функции времени. Для этого составляются и решаются так называемые уравнения Колмогорова - особого вида дифференциальные уравнения, в которых неизвестными функциями являются вероятности состояний.
Сформулируем общее правило составления уравнений Колмогорова. В левой части каждого из них стоит производная вероятности какого-то (i-го) состояния. В правой части – сумма произведений вероятностей всех состояний, из которых идут стрелки в данное состояние, на интенсивности соответствующих потоков событий, минус суммарная интенсивность всех потоков, выводящих данную систему из данного состояния, умноженная на вероятность данного (i-го) состояния.
Пользуясь этим правилом, запишем уравнения Колмогорова для системы, представленной на рисунке 2.
Пожертвуем четвертым уравнением, добавив вместо него нормировочное условие: 
. Уравнение примет вид:
Решая их, получим:
Вывод: В предельном, стационарном режиме системы S в среднем 40% времени будет проводить в состоянии S0 (оба узла исправны), 20% - в состоянии S1 (первый узел ремонтируется, второй работает), 27% - в состоянии S2 (второй узел ремонтируется, первый работает) и 13% - в состоянии S3 полной негодности (оба узла ремонтируются).
Задача 6
В справочном бюро работает п = 5 телефонисток, найдите финальные вероятности и характеристики эффективности, если интенсивность потока заявок λ = 2,3 телефонных звонка в минуту, а среднее время обслуживания одной заявки 
= 2 минуты (все потоки событий простейшие):
Решение
1. Найдем финальные вероятности и характеристики эффективности для СМО с отказом. Состояния системы S(СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно будет совпадать с числом занятых каналов):
S0 - в СМО нет ни одной заявки;
S1– в СМО находится одна заявка (один канал занят, остальные свободны);
S2– в СМО находится две заявки (два канала заняты, остальные свободны);
S3– в СМО находится три заявки (три канала заняты, остальные свободны);
S4– в СМО находится четыре заявки (четыре канала заняты, остальные свободны);
S5 - в СМО находится пятьзаявок (все пятьканалов заняты, заявка поступившая в данный момент получает отказ).
Построим граф состояний данной СМО, соответствующий схеме гибели и размножения (рисунок 9).
рисунок 9
Рассчитаем интенсивность потока обслуживания через μ из соотношения:
заявки обрабатывается за минуту.
Обозначим приведенную интенсивность потока заявок через ρ- среднее число заявок, приходящее за среднее время обслуживания одной заявки.
Получим формулы Эрланга для финальных вероятностей состояний.
то есть вероятность того, что канал свободен, составляет 0,01466 * 100% ≈ 1,5%
, то есть вероятность того, что один канал занят, а остальные свободны, составляет 0,06744 * 100% ≈ 6,7%
, то есть вероятность того, что два канала заняты, а остальные свободны, составляет 0,1551 * 100% ≈ 15,5%
, то есть вероятность того, что три канала заняты, а остальные свободны, составляет 0,23782 * 100% ≈ 23,8%
, то есть вероятность того, что четыре канала заняты, а остальные свободны, составляет 0,2735 * 100% ≈ 27,4%
, то есть вероятность того, что все каналы заняты составляет 0,25162 * 100% ≈ 25,2%
проверка: 0,01466 + 0,06744 + 0,1551 + 0,23782 + 0,2735 + 0,25162 ≈ 1,00014
Таким образом, финальные вероятности системы найдены. По ним вычислим характеристики эффективности СМО.
Сначала найдем вероятность отказа Ротк - вероятность того, что пришедшая заявка получит отказ (не будет обслужена, для этого необходимо, чтобы все каналы были заняты.)
, то есть вероятность того, что пришедшая заявка получит отказ (не будет обслужена) составляет 0,25162 * 100% ≈ 25,2%
Отсюда найдем относительную пропускную способность (среднюю долю пришедших заявок, обслуживаемых системой) – вероятность того, что заявка будет обслужена:
, то есть вероятность того, что пришедшая заявка будет обслужена составляет 0,74838 * 100% ≈ 74,8%
Абсолютная пропускная способность (среднее число заявок, обслуживаемых в единицу времени) вычисляется по формуле:
, то есть около 1,7 заявок, обслуживается в минуту.
А среднее число занятых каналов найдем по формуле:
то почти всегда в данной СМО занято в среднем 3 канала.
Среднее время пребывания заявки в СМО найдем по формуле:
то есть в данной СМО заявка пребывает в системе в среднем 1,5 минуты или 90 секунд
Вывод:данная СМО работает стабильно и к обслуживанию принимает 74,8% всех заявок, то есть всего 25,2% всех заявок получает отказ.
2. Найдем финальные вероятности и характеристики эффективности для СМО с неограниченной очередью (рассчитав финальные вероятности с точностью до 5 звонков в очереди). Состояния системы S(СМО) будем нумеровать по числу заявок, находящихся в системе (в данном случае оно будет совпадать с числом занятых каналов):
S0 - в СМО нет ни одной заявки;
S1– в СМО находится одна заявка (один канал занят, остальные свободны);
S2– в СМО находится две заявки (два канала заняты, остальные свободны);
S3– в СМО находится три заявки (три канала заняты, остальные свободны);
S4– в СМО находится четыре заявки (четыре канала заняты, остальные свободны);
S5 - в СМО находится пятьзаявок (все пятьканалов заняты, заявка поступившая в данный момент становится в очередь);
S6 - в СМО находится шестьзаявок (все каналы заняты, одна заявка в очереди);
S7 - в СМО находится семьзаявок (все каналы заняты, две заявки в очереди);
S8 - в СМО находится восемьзаявок (все каналы заняты, три заявки в очереди);
S9 - в СМО находится девятьзаявок (все каналы заняты, четыре заявки в очереди);
S10 - в СМО находится десятьзаявок (все каналы заняты, пять заявок в очереди) и так далее …
Построим граф состояний данной СМО, соответствующий схеме гибели и размножения (рисунок 10).
рисунок 10
Обозначим показатель нагрузки приходящийся на один канал через φ ,так как интенсивность потока обслуживанияμ= 0,5 и приведенная интенсивность потока заявок ρ =4,6то : 
следовательно можно найти все показатели - характеристики функционирования СМО с ожиданием (с неограниченной очередью)
Рассчитаем финальные вероятности состояний.
то есть вероятность того, что канал свободен, составляет 0,004025 * 100% ≈ 0,4%
, то есть вероятность того, что один канал занят, а остальные свободны, составляет 0,018515 * 100% ≈ 1,9%
, то есть вероятность того, что два канала заняты, а остальные свободны, составляет 0,04258 * 100% ≈ 4,3%
, то есть вероятность того, что три канала заняты, а остальные свободны, составляет 0,065296 * 100% ≈ 6,5%
, то есть вероятность того, что четыре канала заняты, а остальные свободны, составляет 0,07509 * 100% ≈ 7,5%
, то есть вероятность того, что все каналы заняты составляет 0,06908 * 100% ≈ 6,9%
, то есть вероятность того, что все каналы заняты и одна заявка в очереди составляет 0,06356 * 100% ≈ 6,4%
, то есть вероятность того, что все каналы заняты и две заявки в очереди составляет 0,05847 * 100% ≈ 5,8%
, то есть вероятность того, что все каналы заняты и три заявки в очереди составляет 0,05379 * 100% ≈ 5,4%
, то есть вероятность того, что все каналы заняты и четыре заявки в очереди составляет 0,04949 * 100% ≈ 4,9%
, то есть вероятность того, что все каналы заняты и пять заявок в очереди составляет 0,04553 * 100% ≈ 4,5% и так далее ….
Таким образом, финальные вероятности системы найдены. По ним вычислим характеристики эффективности СМО.
Среднее число занятых каналов и среднее число заявок, находящихся под обслуживанием найдем по формуле:
то есть почти всегда в данной СМО заняты все каналы.
Среднее число заявок, находящихся в очереди найдем по формуле:
то есть почти всегда в очереди находится в среднем 10 заявок.
Среднее время ожидания заявки в очереди найдем по формуле:
то есть в данной СМО заявка пребывает в системе в среднем 4,3 минуты или более точно 259 секунд
Среднее заявок, находящихся в СМО найдем по формуле:
то есть почти всегда в данной СМО находится в среднем 15 заявок.
Среднее время пребывания заявки в системе найдем по формуле:
то есть в данной СМО заявка пребывает в системе в среднем 6,3 минуты или 379 секунд.
Вывод:данная СМО сильно перегружена, так как почти всегда заняты все каналы.
Задача 7
Ориентируясь на матрицу прямых затрат 
определить:
1. Валовую продукцию каждой отрасли х1, х2, х3 при условии, что каждый платежеспособный спрос на продукцию отраслей в прогнозном периоде в сопоставимых ценах составит соответственно ỹ1=160 млн. руб., ỹ2=110 млн. руб., ỹ3=60 млн. руб.
2. Конечное использование продукцию каждой из отраслей у1, у2, у3, у4 при условии, что валовой выпуск отраслей в прогнозном периоде в сопоставимых ценах составит соответственно х1=80 млн. руб., х2=70 млн. руб., х3=60 млн. руб.
Решение
1. Составим матричную модель 
которая имеет решение. После простых преобразований получаем: 
или 
Решим данную задачу методом Гаусса
Отсюда 
Вывод: Таким образом, для того чтобы обеспечить конечное использование продукцию 
млн.руб. необходимо, чтобы столбец валовой выпуск отраслей в прогнозном периоде в сопоставимых ценах был равен 
млн.руб.
2. Составим матричную модель 
которая имеет решение. После простых преобразований получаем: 
или 
Отсюда 
Вывод: Таким образом, для того чтобы обеспечить валовой выпуск отраслей в прогнозном периоде в сопоставимых ценах 
млн.руб. необходимо, чтобы столбец конечного использования продукции был равен 
млн.руб.
Приложение №1
| Задача 1
| Задача 2
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 3
|
Задача 4
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 5
|
Задача 6
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 7
|
Задача 8
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 9
|
Задача 10
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 11
|
Задача 12
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 13
|
Задача 14
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 15
|
Задача 16
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 17
|
Задача 18
| |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
|
Задача 19
|
Задача 20
|