- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Где искать оптимальное решение
Как отмечалось выше, без установления принципа оптимальности, отражающего предпочтения ЛПР, невозможно формально распознать оптимальное решение (как в сказке: "ищи то, не знаю, что"). Однако учитывая стремление ЛПР к увеличению значений всех частных критериев, можно формальными методами исключить из множества G (и D) заведомо не перспективные точки и тем самым облегчить решение задачи.
Для наглядности рассуждений рассмотрим пример с двумя критериями (рис10.1). Независимо от предпочтений ЛПР, вектор критериев, соответствующий точке 2, лучше, чем в точке 1. Аналогично, точка 3 лучше точки 2, а 4 лучше 3. Но точки 4 и 5 оказываются не сравнимыми, так как по первому критерию лучше точка 5, а по второму – точка 4. Как для точки 5, так и для 4 на множестве G можно найти лучшую точку, например 6. Нетрудно убедиться в том, что для любой точки Y внутри G найдется точка, которая ее доминирует, т.е. лучше хотя бы по одному частному критерию и не хуже по всем другим. В то же время для точек 6 или 7 этого сделать нельзя. Более того, не найдется вектора из G, который доминировал бы точку, принадлежащую северо-восточной границе AB множества G. Таким образом, векторы на АВ являются недоминируемыми (неулучшаемыми). Одновременно они являются несравнимыми между собой (например, в точках 6 и 7), поэтому отдать предпочтение одному из них без ЛПР невозможно. Такие точки (векторы критериев и соответствующие решения) называют эффективными или оптимальными по Парето. Их совокупность образует множество Парето (паретовское множество).
Это наименование произошло от фамилии итальянского экономиста и социолога В.Парето (1848-1923), который проводил математические исследования процесса рыночного обмена товаров. Рассматривалась модель чистого обмена, в которой каждый участник стремится составить себе набор товаров наибольшей ценности. Эффективным является такое состояние, которое не может быть улучшено путем перераспределения товаров ни для одного из участников без ущемления интересов некоторых других участников. Значит, эффективное состояние соответствует экономическому равновесию, а неэффективное состояние побуждает проводить перераспределение (торговать), которое ведет к установлению равновесия.
Теперь очевидно, что оптимальное решение следует искать только среди эффективных точек. При групповом принятии решений множество эффективных точек называют также переговрным, подчеркивая тем самым, что только их и нужно рассматривать в качестве претендентов на компромиссное решение. Если эффективная точка одна (А на рис.10.2), что возможно в тривиальном случае непротиворечивости критериев, то она и является искомым оптимумом. В задачах с конечным числом точек G (дискретные задачи) выделение эффективного множества часто настолько уменьшает число вариантов, что выбор из них наилучшего не вызывает затруднений у ЛПР.
Однако при непрерывном и тем более невыпуклом множестве G паретовское множество имеет сложную структуру и его исследование требует специальных методов
Ввиду особой важности парето-оптимальности для решения многокритериальных задач приведем более строгие определения, связанные с этим понятием.