- •1.Основные понятия и этапы са
- •2. Операция и ее составляющие. Этапы исо
- •Этапы операционного проекта
- •Виды математических моделей ио, примеры.
- •4. Состязательные задачи. Решение игры 2-х лиц
- •7. Примеры задач лп: игра 2-х лиц как задача лп, транспортная задача
- •В общем случае модель задачи лп имеет вид
- •Сбалансированная транспортная задача
- •8 Формы представления задач лп и способы приведения к ним
- •1. Каноническая форма задач лп
- •2. Стандартная форма задачи лп
- •9. Основные понятия лп. Свойства задач лп
- •10. Геометрия задач лп, базисные решения, вырожденность.
- •4.7. Выделение вершин допустимого множества
- •11. Понятие базиса. Переход от одного базисного решения к другому
- •12. Признак оптимальности. Определение начального базисного решения.
- •13. Алгоритм симплекс-метода
- •14. Двойственность задач лп
- •4.11.1. Запись двойственной задачи в симметричном случае
- •4.11.3. Запись двойственной задачи в общем случае
- •15.Экономическая интерпретация двойственной задачи
- •16. Теоремы двойственности
- •17. Двойственный и модифицированный симплекс-метод Модифицированный алгоритм
- •18. Параметрический анализ. Параметрирование вектора ограничениий
- •Параметрирование вектора ограничениий
- •19. Параметрирование коэффициентов линейной формы
- •20. Модели транспортных задач и их характеристика, условия разрешимости.
- •Простейшая транспортная задача (т-задача)
- •Транспортная задача с ограниченными пропускными способностями (Td - задача)
- •Транспортные задачи по критерию времени
- •21. Построение начального плана перевозок т-задачи
- •5.2.1. Построение начального плана перевозок
- •Правило северо-западного угла
- •Правило минимального элемента.
- •22.Обоснование метода потенциалов
- •5.2.3. Признак оптимальности
- •23. Алгоритм метода потенциалов.
- •24. Двойственная пара транспортных задач
- •25. Метод потенциалов для Td-задачи
- •5.5. Решение задачи по критерию времени
- •26. Приведение открытой транспортной задачи к закрытой
- •27. Транспортные задачи в сетевой постановке (транспортные сети)
- •28. Задача о максимальном потоке
- •29. Метод декомпозиции Данцига - Вулфа
- •30. Решение транспортной задачи методом Данцига-Вулфа (метод декомпозиции тз)
- •32. Целочисленное программирование
- •7.1. Проблема целочисленности
- •33. Метод отсечений
- •Пример 7.1. Выведем условие отсечения для задачи
- •34. Метод ветвей и границ
- •35. Аддитивный алгоритм
- •36. Нелинейное программирование
- •Теорема
- •37. Квадратичное программирование
- •38. Сепарабельное программирование (сп) и дробно-линейное программирование
- •8.5. Задачи дробно-линейного программирования
- •39. Метод покоординатного спуска и Хука-Дживса Метод первого порядка
- •8.8. Многомерный поиск безусловного минимума
- •8.8.1. Метод Гаусса-Зейделя (покоординатного спуска)
- •Метод Хука-Дживса (метод конфигураций) Метод первого порядка
- •Метод Хука-Дживса (метод конфигураций)
- •40. Симплексный метод поиска
- •41. Градиентные методы
- •Методы сопряженных направлений
- •43. Методы случайного поиска
- •Алгоритм с возвратом при неудачном шаге
- •Алгоритм с обратным шагом
- •Алгоритм наилучшей пробы
- •Алгоритм статистического градиента
- •44. Метод проектирования градиента
- •Метод проектирования градиента
- •45. Генетические алгоритмы
- •46. Метод штрафных функций и барьерных функций
- •Метод барьерных функций
- •47. Динамическое программирование
- •48. Распределение одного вида ресурса
- •49. Дп: задачи о кратчайшем пути и с мультипликативным критерием
- •Задача с мультипликативным критерием.
- •52. Многомерные задачи динамического программирования
- •53. Снижение размерности с помощью множителей Лагранжа
- •56. Многокритериальные задачи: постановка, проблемы, осн. Понятия, методы
- •Многокритериальная задача математического программирования
- •Где искать оптимальное решение
- •Определения
- •Условия оптимальности
- •57. Многокритериальные задачи: функция полезности, лексикографический анализ
- •Методы первой группы
- •Функция полезности
- •Решение на основе лексикографического упорядочения критериев
- •58. Методы главного критерия, свертки, идеальной точки, целевого прогр. Метод главного критерия
- •Линейная свертка
- •Максиминная свертка
- •Метод идеальной точки
- •Целевое программирование (цп)
- •59. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
1.Основные понятия и этапы са
Системный анализ – это комплексная методология решения и исследования сложных проблем, базирующихся на системных методах (это методология и практика, улучшающая вмешательства в проблемные ситуации)
Система-совокупность объектов, св-ва которой определяются отношениями м/д объектами. Если объект не делим, то это элемент системы.
Конструктивное определение:
Пробл.сит. цель ф-ии сист. структура сист.
-конечное множество функциональных элементов и отношений м/д ними, выделяемое из среды в соответствии с определенной целью и в рамках нек-го временного интервала.
Св-ва системы:
Целевая предназначенность
Целостность
Обособленность от среды
Эмерджентность-рез-т синергетического эффекта в системе
Синергетический эффект – согласованное действие частей системы приводит к новому св-ву, к-го нет у отдельных ее частей.
Среда-это все, кроме системы.
Структура системы-относительно устойчивый порядок внутренних пространственно-временных связей м/д ее элементами и их взаимодействие с внешней средой.
Связи:
-направленные и ненаправленные; -односторонние и двусторонние; -внутренние и внешние;-равноправные и неравноправные; -постоянные и временные; -слабые и сильные; -непрерывные и дискретные
-стохастические и детерминированные
Иерархические структуры систем: многоуровневость и подчиненность
Идеальная иерархия: нижележащие подчиняются только одному вышележащему. Нарушение: подчинение нескольким вышележащим или подчинение через уровень.
Иерархические структуры:
Иерархия страт. Страта – уровень абстрагирования.
Иерархия слоев. Слои – уровни принятия решения.
Иерархия эшелонов. Эшелоны – уровень представляет собой ряд независимых подсистем.
Принципы поведения систем:
Принцип вещественно-энергетического баланса (з-н сохранения)
Принцип гоместазиса (принцип открытых систем)
Принцип выбора решений
Принцип перспективной активности (система способна обрабатывать информацию и реагировать)
На основе рефлексии (эл-ты искусственного интеллекта)
Цель - желаемый результат.
Модель – объект, заменяющий оригинал, в той части, к-ая интересует исследования, но он более удобен для работы с ним.
Критерий – показатель, к-ый служит для оценки.
Этапы системного анализа:
Формулировка проблемы .
Расширение проблемы до проблематики, т.е. определение всех проблем, связанных с исходной.
Определение цели (целеполагание)
- это центральный этап, основа поведения исследования анализа. Необходимо включать максимальное число целей.
Определение критериев ( и качественного и количественного типа)
Генерирование альтернатив (вариантов решения)
В СА существуют методы:
1. Мозговой штурм 2. Синектика (поиск аналогий) 3. Разработка сценариев
4. Морфологический анализ (выделяются части или признаки и рассматриваются все варианты реализации и получаем морф. ящик из к-го можно составить различные варианты системы)
5. Деловые игры и др.
6.Экспертное решение
Построение модели (моделей) – чаще всего используются имитационные модели.
Исследование на моделях и определение наилучшего варианта.
Анализ решений и рекомендации по внедрению.
Внедрение – реализация тех рекомендаций, которые получены в результате системного анализа.
Отличие:
В СА цели не задаются, а определяются в процессе СА, а в ИСО цели уже поставлены.
Генерирование альтернатив.
Подходы к проблеме:
Absolution – с возникновением проблемы ничего делать не нужно, она сама пройдет
Resolution – что нибудь предпринять для решения проблемы
Solution – решение проблемы
Dissolution – не только решить проблему, но и сделать все, чтоб в будущем подобные проблемы не возникали.
Критерий оптимальности
Термин "критерий" широко используется как во всех областях знаний, так и в обыденной жизни в интуитивно понятном смысле. Ввиду особой важности этого термина для исследования операций дадим краткие пояснения. Греческое слово kriterion означает мерило, оценку, средство для суждения. Именно в этом смысле используется понятие критерия в ИСО. Поставленная в операции цель может быть достигнута по-разному и в разной степени в зависимости от принимаемых решений. Критерий есть тот показатель, который характеризует (оценивает) эффективность решений с точки зрения достижения цели, а следовательно, позволяет выбрать среди них наилучшее. В ИСО применяют равнозначные термины: критерий оптимальности, критерий эффективности, целевая функция. Последний термин подчеркивает неразрывную связь критерия с целью. Таким образом, решение может быть оптимальным только в смысле конкретного критерия в пределах адекватности используемой модели.
В исследовании операций к критерию предъявляются определенные требования. Наиболее важные из них следующие.
1. Критерий должен быть количественной и неслучайной величиной.
2. Критерий должен правильно и полно отражать поставленную цель. Его можно рассматривать как количественную модель качественной цели.
3. Критерий должен иметь простой и понятный ЛПР физический смысл.
4. Критерий должен быть чувствителен к управляемым (искомым) переменным.
При исследовании действующих систем к критерию могут предъявляться дополнительные требования, такие как измеримость, статистическая однозначность, статистическая эффективность и др.
Многочисленные примеры из практики показывают огромную важность правильного выбора критерия оптимальности.
Задачи, в которых приходится определять наилучшее решение по нескольким критериям, называются многокритериальными или задачами векторной оптимизации. Они составляют особый и более сложный класс задач исследования операций, который рассмотрен в последней главе настоящего пособия.