ref-19831 (743491), страница 3

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 3)

x₅ = 1

x₇ = 1

x₈ = 0

x₁₁ = 1

Э то означает, что на графике остаются только пути, соответствующие переменным х₃, х₅, х₇, х₁₁ (1 4, 2 3, 3 1, 4 2). Функционал равен 12, т. е. время пути будет равно 12 единицам. График при этом выглядит следующим образом.

Задание №3

Тема: Графы

Задача о максимальном потоке

Имеется трубопроводная сеть с заданной S_ij пропускной способностью каждого участка из i-го узла в j-й узел и мощностью насосной станции, расположенной в узле. Необходимо рассчитать максимальную пропускную способность сети из начального узла в конечный узел.

_{и сток} _{с ток}

Пропускная способность S_ij , тыс. тонн

S₁₂ = 4

S₁₃ = 7

S₁₄ = 8

S₂₃ = 3

S₂₅ = 5

S₃₄ = 8

S₃₅ = 9

S₄₅ = 9

Математическая модель

Обозначим за х_{1, 2, …, 8} перевозки по маршрутам 12, 13, 14, 23, 25, 34, 35, 45 соответственно, а за х₉ – пропускную способность конечного узла сети.

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

х₉ - х₁ – х₂ – х₃ = 0 ⁽¹⁾

х₁ – х₄ – х₅ = 0 ⁽²⁾

х₂ + х₄ – х₆ – х₇ = 0 ⁽³⁾

х₃ + х₆ – х₈ = 0 ⁽⁴⁾

х₅ + х₇ + х₈ – х₉ = 0 ⁽⁵⁾

х₁  4 ⁽⁶⁾

х₂  7 ⁽⁷⁾

х₃  8 ⁽⁸⁾

х₄  3 ⁽⁹⁾

х₅  5 ⁽¹⁰⁾

х₆  8 ⁽¹¹⁾

х₇  9 ⁽¹²⁾

х₈  9 ⁽¹³⁾

Ф ункция цели: х₉ max

Таблица 3.1

Исходная матрица

Решение

х₁ = 4

х₂ = 7

х₃ = 8

х₅ = 4

х₇ = 7

х₈ = 8

х₉ = 19

Функционал в данной задаче равен –481, что не имеет смысла при заданных условиях. Однако, исходя из математической модели, функционал в данной задаче равен значению х₉ . Таким образом, максимальная пропускная способность сети составит 19 тыс. тонн. При этом некоторые маршруты окажутся незадействованными (х₄ и х₆). График будет выглядеть следующим образом.

Задание №4

Тема: Системы массового обслуживания

Задача: Рационализация функционирования системы управления аэропортом на базе анализа марковских процессов

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

Требуется вычислить вероятности состояний в стационарном режиме по значениям интенсивности перехода.

Таблица 4.1

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

Математическая модель

Примем за х₁, х₂, …, х₅ предельные вероятности состояний в стационарном режиме пунктов S₁, S₂, …, S₅ соответственно. Произведение вероятности состояния на интенсивность исходящих из этого пункта потоков равна произведению интенсивностей входящих потоков на вероятность состояния в стационарном режиме пунктов их отправления. Система уравнений Колмогорова для данной задачи в общем виде выглядит следующим образом:

(₁₃ + ₁₂ )* х₁ = ₂₁ * х₂ ⁽¹⁾

₂₁ * х₂ = ₁₂ * х₁+ ₃₂ * х₃ ⁽²⁾

(₃₂ + ₃₄ )* х₃ = ₁₃ * х₁ + ₅₃ * х₅ ⁽³⁾

₄₅ * х₄ = ₃₄ * х₃+ ₅₄ * х₅ ⁽⁴⁾

(₅₄ + ₅₃ )* х₅ = ₄₅ * х₄ ⁽⁵⁾

Кроме того, сумма всех вероятностей равна 1. При подстановке данных таблицы 4.1 и добавлении переменной х₆ получаем:

5 х₁ - х₂ + х₆ = 0 ⁽¹⁾

х₂ - 3х₁ - 3х₃ + х₆ = 0 ⁽²⁾

5 х₃ - 2х₁ - 3х₅ + х₆ = 0 ⁽³⁾

2 х₄ - 2х₃ – х₃ + х₆ = 0 ⁽⁴⁾

4 х₅ - 2х₄ + х₆ = 0 ⁽⁵⁾

х₁ + х₂ + х₃ + х₄ + х₅ + х₆ = 1 ⁽⁶⁾

Ф ункция цели: М х₆ max

Таблица 4.2.

Исходная матрица

Решение

Функционал = -500

Характеристики

Список файлов реферата