ref-19831 (Сетевое моделирование при планировании. Задача о коммивояжере...), страница 3
Описание файла
Документ из архива "Сетевое моделирование при планировании. Задача о коммивояжере...", который расположен в категории "". Всё это находится в предмете "экономико-математическое моделирование" из , которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "рефераты, доклады и презентации", в предмете "экономико-математическое моделирование" в общих файлах.
Онлайн просмотр документа "ref-19831"
Текст 3 страницы из документа "ref-19831"
x5 = 1
x7 = 1
x8 = 0
x11 = 1
Э то означает, что на графике остаются только пути, соответствующие переменным х3, х5, х7, х11 (1 4, 2 3, 3 1, 4 2). Функционал равен 12, т. е. время пути будет равно 12 единицам. График при этом выглядит следующим образом.
Задание №3
Тема: Графы
Задача о максимальном потоке
Имеется трубопроводная сеть с заданной Sij пропускной способностью каждого участка из i-го узла в j-й узел и мощностью насосной станции, расположенной в узле. Необходимо рассчитать максимальную пропускную способность сети из начального узла в конечный узел.
и сток с ток
Пропускная способность Sij , тыс. тонн
S12 = 4
S13 = 7
S14 = 8
S23 = 3
S25 = 5
S34 = 8
S35 = 9
S45 = 9
Математическая модель
Обозначим за х1, 2, …, 8 перевозки по маршрутам 12, 13, 14, 23, 25, 34, 35, 45 соответственно, а за х9 – пропускную способность конечного узла сети.
Сумма входящих в каждый узел потоков равна сумме выходящих, причем интенсивность каждого потока не может превышать пропускную способность своего участка сети. Поэтому система условий-ограничений выглядит следующим образом.
х9 - х1 – х2 – х3 = 0 (1)
х1 – х4 – х5 = 0 (2)
х2 + х4 – х6 – х7 = 0 (3)
х3 + х6 – х8 = 0 (4)
х5 + х7 + х8 – х9 = 0 (5)
х1 4 (6)
х2 7 (7)
х3 8 (8)
х4 3 (9)
х5 5 (10)
х6 8 (11)
х7 9 (12)
х8 9 (13)
Ф ункция цели: х9 max
Таблица 3.1
Исходная матрица
№ | х1 | х2 | х3 | х4 | х5 | х6 | х7 | х8 | х9 | Знак | Св.чл. |
1 | -1 | -1 | -1 | 0 | 0 | 0 | 0 | 0 | 1 | = | 0 |
2 | 1 | 0 | 0 | -1 | -1 | 0 | 0 | 0 | 0 | = | 0 |
3 | 0 | 1 | 0 | 1 | 0 | -1 | -1 | 0 | 0 | = | 0 |
4 | 0 | 0 | 1 | 0 | 0 | 1 | 0 | -1 | 0 | = | 0 |
5 | 0 | 0 | 0 | 0 | 1 | 0 | 1 | 1 | -1 | = | 0 |
6 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 4 |
7 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | | 7 |
8 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | 0 | | 8 |
9 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | 0 | | 3 |
10 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | 0 | | 5 |
11 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | 0 | | 8 |
12 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | 0 | | 9 |
13 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 0 | | 9 |
Ф. ц. | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | max |
Решение
х1 = 4
х2 = 7
х3 = 8
х5 = 4
х7 = 7
х8 = 8
х9 = 19
Функционал в данной задаче равен –481, что не имеет смысла при заданных условиях. Однако, исходя из математической модели, функционал в данной задаче равен значению х9 . Таким образом, максимальная пропускная способность сети составит 19 тыс. тонн. При этом некоторые маршруты окажутся незадействованными (х4 и х6). График будет выглядеть следующим образом.
Задание №4
Тема: Системы массового обслуживания
Задача: Рационализация функционирования системы управления аэропортом на базе анализа марковских процессов
Различные аэропорты имеют отделы системы управления, функциональная связь которых и интенсивность потоков информации представлены на рисунке и в таблице 4.1.
Требуется вычислить вероятности состояний в стационарном режиме по значениям интенсивности перехода.
Таблица 4.1
Исходные данные
Интенсивность потоков (переходов) | |||||||
12 | 13 | 21 | 32 | 34 | 45 | 53 | 54 |
3 | 2 | 1 | 3 | 2 | 2 | 3 | 1 |
Математическая модель
Примем за х1, х2, …, х5 предельные вероятности состояний в стационарном режиме пунктов S1, S2, …, S5 соответственно. Произведение вероятности состояния на интенсивность исходящих из этого пункта потоков равна произведению интенсивностей входящих потоков на вероятность состояния в стационарном режиме пунктов их отправления. Система уравнений Колмогорова для данной задачи в общем виде выглядит следующим образом:
(13 + 12 )* х1 = 21 * х2 (1)
21 * х2 = 12 * х1+ 32 * х3 (2)
(32 + 34 )* х3 = 13 * х1 + 53 * х5 (3)
45 * х4 = 34 * х3+ 54 * х5 (4)
(54 + 53 )* х5 = 45 * х4 (5)
Кроме того, сумма всех вероятностей равна 1. При подстановке данных таблицы 4.1 и добавлении переменной х6 получаем:
5 х1 - х2 + х6 = 0 (1)
х2 - 3х1 - 3х3 + х6 = 0 (2)
5 х3 - 2х1 - 3х5 + х6 = 0 (3)
2 х4 - 2х3 – х3 + х6 = 0 (4)
4 х5 - 2х4 + х6 = 0 (5)
х1 + х2 + х3 + х4 + х5 + х6 = 1 (6)
Ф ункция цели: М х6 max
Таблица 4.2.
Исходная матрица
№ | х1 | х2 | х3 | х4 | х5 | х6 | Св.чл. | Знак |
1 | 5 | -1 | 0 | 0 | 0 | 1 | 0 | = |
2 | -3 | 1 | -3 | 0 | 0 | 1 | 0 | = |
3 | -2 | 0 | 5 | 0 | -3 | 1 | 0 | = |
4 | 0 | 0 | -2 | 2 | -1 | 1 | 0 | = |
5 | 0 | 0 | 0 | -2 | 4 | 1 | 0 | = |
6 | 1 | 1 | 1 | 1 | 1 | 1 | 1 | = |
Ф.ц. | 0 | 0 | 0 | 0 | 0 | М | max |
Решение
Функционал = -500