Задачи, связянные с определением оптимальных потоков в сети
Стр 1 из 4Следующая ⇒ ЗАНЯТИЕ 5 СЕТЕВЫЕ ЗАДАЧИ ЗАДАЧИ, СВЯЗЯННЫЕ С ОПРЕДЕЛЕНИЕМ КРАТЧАЙШЕГО И КРИТИЧЕСКОГО ПУТЕЙ Словесная формулировка. Необходимо найти кратчайший или самый протяженный (критический) путь между заданными исходной и конечной вершинами (узлами, пунктами) сети Формальная постановка. Пусть задана сеть с графом Тогда задача о кратчайшем (критическом) пути предстает в виде задачи линейного дискретного программирования:
Ограничения (1.1.2) являются необходимыми условиями, при которых набор дуг, соответствующих ненулевым значениям ЗАДАЧИ, СВЯЗЯННЫЕ С ОПРЕДЕЛЕНИЕМ ОПТИМАЛЬНЫХ ПОТОКОВ В СЕТИ Задача о максимальном потоке. Словесная формулировка. Необходимо рассчитать величины потоков по дугам графа сети, которые бы обеспечивали максимальный приток в узел-приемник Формальная постановка. Рассмотрим сеть с графом
Здесь Задача о потоке минимальной стоимости. Словесная формулировка. Нужно рассчитать величины потоков минимальной суммарной стоимости по дугам сети, которые бы обеспечивали заданный суммарный приток в узел-приемник Формальная постановка. Пусть задана сеть с графом
Задача 1.1. Дорожная сеть состоит из транспортных узлов, соединенных между собой дорогами. Передвижение между узлами возможно лишь в одном направлении, разрешенные направления движения обозначены стрелками. Рядом с каждой стрелкой проставлены два числа: первое означает расстояние между узлами; второе (заключенное в скобки) – максимально возможную пропускную способность дороги (тыс.автомобилей в час). Требуется:
Решение. Ответы на первый и второй вопросы находим, следуя (1.1.1)-(1.1.2). Реализуем следующие действия:
1) Из рисунка на рабочий лист вводим информацию по всем дугам сети (ячейки A35:D48 на шаблоне, рис.1.1 ниже); 2) перечисляем номера всех узлов сети (ячейки E34:M34); 3) вычисляем элементы матрицы инцидентности (ячейки E35:M48); 4) отводим столбец N35:N48 («выбор пути») под ячейки, которые будут определять искомый путь; 5) вычисляем итоги взаимодействия входящих в путь дуг со всеми узлами сети (ячейки E49:M49); 6) вычисляем суммарную длину всех дуг, образующих искомый путь (ячейка C49); 7) заносим в ячейки E50:M50 значения, определяющих сценарий пути (для начального узла пути заносим –1, для конечного узла заносим 1, для всех остальных заносим 0); 8) ставим задачу в «Поиске решения», отмечая при этом линейную модель, и решаем ее (рис.1.1):
Рис.1.1. Шаблон с решением задачи 1.1 для ответа на первый вопрос
Для получения ответа на второй вопрос делаем копию листа рис. 1.1; вызываем «Поиск решения», целевую ячейку устанавливаем на максимальное значение; даем команду «выполнить» и получаем ответ на второй вопрос.
Для получения ответа на третий вопрос необходимо решить задачу по определению максимальной пропускной способности. Следуя (1.2.2)-(1.2.3), делаем следующие шаги: 1) копируем лист (рис. 1.1), где решалась задача определения пути минимальной длины; 2) на скопированном листе удаляем строку со сценарием пути и ячейку с длиной пути (рис. 1.2); 3) заголовок «выбор пути» над столбцом N35:N28 изменяем на заголовок «потоки» (рис. 1.2); 4) ставим задачу в «Поиске решения» и решаем ее (рис. 1.2):
Рис. 1.2. Шаблон с решением задачи 1.1 для ответа на третий вопрос
2. ПРИНЯТИЕ РЕШЕНИЙ В УСЛОВИЯХ НЕОПРЕДЕЛЕННОСТИ (ИГРЫ ПРОТИВ ПРИРОДЫ)
Игрой против природы называется модель конфликта двух лиц, одно из которых не имеет цели, но своими действиями существенно влияет на качество принимаемых другим лицом решений. Такое лицо называется «природой». Другое лицо, имеющее цель и своими действиями стремящееся достичь ее, называется лицом, принимающим решения (ЛПР). Конечную игру против природы в нормальной форме задают с помощью платежной матрицы (матрицы исходов)
В зависимости от того, какая информация доступна ЛПР, а также от его субъективных характеристик (особенностей), при поиске оптимальных решений применяются различные критерии оптимальности.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|