- •Системный анализ и моделирование процессов в техносфере
- •1.1. Понятие системы. Базовые категории систем
- •1.2. Классификация систем
- •1.3. Общее представление о системном анализе
- •1.4. Принципы системного анализа
- •2.1. Этапы анализа и синтеза
- •2.2. Понятие о структурном анализе
- •2.3. Методы декомпозиции
- •2.4. Требования, предъявляемые к декомпозиции
- •2.5. Алгоритм декомпозиции
- •2.5. Программно-целевой подход к решению системных задач
- •1. Область применения и этапы программно-целевого подхода
- •2. Дерево целей
- •3.1. Агрегирование системы и эмерджентность
- •3.2. Виды связей в системе
- •Связи взаимодействия (координации):
- •Связи преобразования:
- •3.3. Виды агрегирования
- •4.1. Общие свойства процесса принятия решений
- •4.2. Участники процесса принятия решения
- •4.3. Схема ппр
- •4.4. Формулирование проблемы
- •4.5. Определение целей
- •4.6. Генерирование альтернатив
- •4.7. Формирование критериев
- •4.8. Физиология принятия решений
- •4.9. Виды и особенности задач принятия решений
- •4.10. Формализация принятия решений
- •Лекция 5. Информационное обеспечение ппр
- •5.1. Понятие информации
- •5.2. Информационная структура процесса принятия решений
- •6.1. Особенности группового выбора
- •6.2. Экспертные методы выбора
- •6.3. Методы типа мозговой атаки или коллективной генерации идей
- •6.4. Методы типа сценариев
- •6.5. Методы типа «Делфи»
- •6.6. Методы типа дерева целей
- •6.7. Морфологические методы
- •7.1 Основные положения теории управления
- •7.2 Аксиомы теории управления
- •7.3 Модели основных функций организационно-технического управления
- •7.4 Описание функций управления
- •Лекция 8. Понятие и классификация моделей
- •8.1 Понятие модели, моделирования
- •8.2 Познавательные и прагматические модели
- •8.3 Статические и динамические модели
- •8.4 Классификация моделей по способу воплощения
- •8.5 Место математического моделирования в системных исследованиях
- •8.6 Типы и виды математических моделей
- •8.7 Процесс построения математической модели
- •8.8 Структура моделирования происшествий в техносфере
- •9.1 Конфликт ‒ предмет рассмотрения теории игр
- •9.2 Понятие игры. Классификация игр. Формальное представление игр
- •9.3 Определение бескоалиционной игры
- •9.4 Приемлемые ситуации и ситуации равновесия
- •9.5 Примеры игровых задач
- •10.1 Граф и его виды
- •10.2 Задача о кратчайшем пути
- •10.3 Задача о максимальном потоке
- •11.1 Поверхность отклика
- •11.2 Этапы планирования эксперимента
- •11.3 Обработка и анализ результатов моделирования
- •12.1 Полный факторный эксперимент
- •12.2 Дробный факторный эксперимент
- •12.3 Метод наименьших квадратов
- •13.1 Основная цель кластерного анализа
- •13.2 Объединение (древовидная кластеризация)
- •13.3 Двувходовое объединение
- •13.4 Метод k средних
- •13.5 Алгоритм нечеткой кластеризации
- •14.1 Понятие когнитивного моделирования
- •14.2 Подсистема представления субъективной информации
- •14.3 Подсистема извлечения предпочтений эксперта
- •14.4 Подсистема обработки
- •14.5 Подсистема представления результатов моделирования
- •14.6 Подсистема поддержки аналитической деятельности эксперта
- •14.7 Моделирование бизнес процессов на основе bpmn-диаграмм
- •14.8 Метод анализа иерархий (маи): введение
- •14.9 Основные принципы маи
- •1. Принцип идентичности и декомпозиции
- •2. Принцип дискриминации и сравнительных суждений
- •3. Принцип синтеза
- •14.10 Общая оценка маи как метода принятия решений
- •15.1 Общий ход решения задачи на основе метода конечных элементов
- •15.2 Сети одномерных конечных элементов
- •15.3 Виды конечных элементов
- •16.1 Основные понятия
- •16.2 Приближенное решение оду при заданных начальных условиях
- •16.3 Метод Эйлера и его модификации
- •16.4 Метод Рунге-Кутта
- •16.5 Приближенное решение ду n-го порядка при заданных начальных условиях
- •16.6 Приближенное решение ду при заданных граничных условиях (краевых задач)
- •16.6.1 Метод начальных параметров
- •16.6.2 Редукция к задаче Коши для линейного ду второго порядка
- •17.1 Основные понятия
- •17.2 Типы элементов
- •17.3 Источники энергии и преобразователи. Аналоги топологических уравнений
- •17.4 Метод получения топологических уравнений
- •18.1 Свойства задач принятия решения со многими критериями
- •18.2. Формирование множества критериев
- •18.3 Методология решения многокритериальных задач
- •18.4 Технологии отыскания эффективных решений
- •18.5 Методы принятия решения при нескольких критериях
10.3 Задача о максимальном потоке
По каким маршрутам послать максимально возможное количество грузов из начального пункта в конечный, если пропускная способность путей между пунктами ограничена?
Для решения этой задачи каждой дуге ориентированного графа, соответствующего транспортной системе, должно быть сопоставлено число – пропускная способность этой дуги (рис. 11).
Рис. 11. Исходные данные
Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис.11, можно также задать таблицей (табл. 2).
Табл. 2. Исходные данные к задаче о максимальном потоке
Пункт отправления |
Пункт назначения |
Пропускная способность |
0 |
1 |
2 |
0 |
2 |
3 |
0 |
3 |
1 |
1 |
2 |
4 |
1 |
3 |
1 |
1 |
4 |
3 |
2 |
3 |
1 |
2 |
4 |
2 |
3 |
4 |
2 |
Решение задачи о максимальном потоке может быть получено из следующих соображений.
Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3.
Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу ‒ в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4.
Итак, максимальная пропускная способность рассматриваемой транспортной системы ‒ 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 ‒ по ней направлены 2 единицы груза при пропускной способности в 3 единицы.
Решение можно представить в виде таблицы (табл. 2) или графа (рис. 12).
Рис. 12. Решение задачи (числа в скобках)
Табл. 3. Решение задачи о максимальном потоке
Пункт отправления |
Пункт назначения |
Пропускная способность |
План перевозок |
0 |
1 |
2 |
2 |
0 |
2 |
3 |
3 |
0 |
3 |
1 |
1 |
1 |
2 |
4 |
0 |
1 |
3 |
1 |
0 |
1 |
4 |
3 |
2 |
2 |
3 |
1 |
1 |
2 |
4 |
2 |
2 |
3 |
4 |
2 |
2 |
Дадим формулировку задачи о максимальном потоке в терминах линейного программирования. Пусть ХKM ‒ объем перевозок из пункта К в пункт М. Согласно рис. 11 К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны лишь в пункт с большим номером. Значит, всего имеется 9 переменных ХKM , а именно, Х01 , Х02 , Х03 , Х12 , Х13 , Х14 , Х23 , Х24 , Х34 . Задача линейного программирования, нацеленная на максимизацию потока, имеет вид:
F → max ,
Х01 + Х02 + Х03 = F (0)
- Х01 + Х12 + Х13 + Х14 = 0 (1)
- Х02 ‒ Х12 + Х23 + Х24 = 0 (2)
- Х03 ‒ Х13 ‒ Х23 + Х34 = 0 (3)
- Х14 ‒ Х24 ‒ Х34 = ‒ F (4)
Х01 ≤ 2
Х02 ≤ 3
Х03 ≤ 1
Х12 ≤ 4
Х13 ≤ 1
Х14 ≤ 3
Х23 ≤ 1
Х24 ≤ 2
Х34 ≤ 2
ХКМ ≥ 0 , К, М = 0, 1, 2, 3, 4
F ≥ 0 .
Здесь F ‒ целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) ‒ (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не "рождаются" в ней. Условие (4) ‒ это условие "выхода" грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом ("вход" равен "выходу"). Следующие девять неравенств задают ограничения на пропускную способность отдельных "веток" транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию ‒ через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом "не знает").
Литература:
1. Белов В.В. Теория графов / В.В. Белов, Е.М. Воробьев, В.Е. Шаталов. ‒ М.: Высшая школа, 1976. ‒ 392 с.
2/ Электронный учебник по решению задач на графах Татарского института содействия бизнесу. URL: http://www.tisbi.ru/resource/lib/graph/cont.htm
Лекция 11. Основные положения теории планирования экспериментов