Решение задачи в надстройке MS Excel «Поиск решения»

Запишем условия задачи в таблице MS Excel, в виде пригодном для использования надстройки «Поиск решения».

В первый столбец таблицы выпишем индексы вершин, которые являются началом дуг графа. Во второй – индексы вершин-концов дуг графа. В столбец «С» выпишем пропускные способности ребер графа. Столбец «D» будет содержать значения переменных задачи (потоков по ребру), которые определятся в результате поиска решения средствами MS Excel, заполним его нулями. В столбец «Е» запишем ограничения задачи в виде соответствующих формул MS Excel. Под таблицей заведем ячейку с формулой для расчета значения целевой функции.

Для решения задачи запустим надстройку «Поиск решения» и заполним соответствующие параметры рис.2.

 

Рис.2

Нажмем кнопу «Найти решение». При отсутствии ошибок при записи условий задачи будет получено следующее значение переменных и целевой функции (рис.3).

Таким образом с помощью автоматизированного решения задачи о максимальном потоке сети с помощью надстройки надстройки MS Excel «Поиск решения» было получено следующее решение:

Максимальный поток в сети графа (рис. 1) из истока – вершины 1 в сток – вершину 10 равен 12. Потоки по ребрам графа равны:

Рис.3

Моделирование по схеме дискретных марковских процессов. Расчет вероятностей состояний однородной марковской цепи за некоторое количество шагов.

Цель работы:

1. Отработать и закрепить умения строить размеченный граф состояний по

матрице переходных вероятностей для однородной марковской цепи.

2. Отработать и закрепить умения находить (рассчитывать) вероятности

состояний однородной марковской цепи за k шагов.

Задача 1.

Система может находиться в одном из пяти состояний (1, 2, 3, 4, 5).

Дана матрица Р вероятностей перехода системы из состояния в состояние за один шаг.

Постройте размеченный граф состояний системы, соответствующий матрице Р.

 

Задача 2.

 

Система может находиться в одном из четырех состояний (1, 2, 3, 4)

Переходы между состояниями за один цикл осуществляются с вероятностями заданными

матрицей P.

1) Определите матрицу вероятностей переходов за N циклов

2) Распределение вероятностей состояний за N циклов, если начальное

распределение задается вектором С

3) Вероятность того, что через N циклов система будет в состоянии k, если в

начальный момент времени она находилась в состоянии 1.