- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Интерактивное компромиссное программирование
Так называется метод, использующий для поиска удовлетворящего ЛПР компромиссного решения линейную свертку. При этом от ЛПР не требуется назначать веса, ему лишь нужно на каждой итерации выбрать одно решение из (m+1 )-го предлагаемых, после чего веса вычисляются программно.
Сравнивать альтернативные решения легче, если критерии измеряются в одной шкале. С этой целью в данном методе критерии заменяются функциями степени близости, которые определяются по формуле
, (10.24)
где - максимальное и минимальное значения -го критерия на допустимом множестве D. Как следует из (10.24), может изменяться от 0 до 1. Очевидно, что если - линейная функция, то и тоже линейная.
Теперь паретовские (эффективные) решения можно находить, максимизируя свертку
(10.25)
при условии Х D.
Одним из существенных недостатков ряда интерактивных методов является использование параметров, численные значения которых должен указывать ЛПР. В рассматриваемом методе эта проблема исключается, так как веса в (10.25) определяются не ЛПР, а специальной процедурой, обеспечивающей вычисление на каждой итерации значений весов, оптимальных в максиминном смысле. Процедура основана на игровом подходе, а именно, на формализации и решении игры двух лиц с нулевой суммой. В качестве стратегий первого игрока рассматриваются целевые функции, второго - решения многокритериальной задачи, полученные к данному шагу и не забракованные ЛПР. Платежом на каждой паре стратегий является степень близости -й целевой функции на -м решении к своему максимальному значению . Тогда вероятности применения стратегий первым игроком и будут иметь смысл весов целевых функций, входящих в свертку (10.25).
В целом процесс поиска компромиссного решения рассматриваемым методом можно представить следующим образом. Процедура начинается с решения 2m обычных задач математического программирования для нахождения максимальных и минимальных значений m целевых функций. По ним вычисляют степень близости каждого решения к максимально возможному значению каждой целевой функции. Приняв их за платежи игры 2-х лиц размерности m* m и решив игровую задачу, получают текущие веса целевых функций. Последние используют для нахождения (m+1)-го решения. Для полученного решения также вычисляются степени близости по всем критериям. Теперь вместе с предыдущими m решениями новое решение предъявляют ЛПР. Его спрашивают, предпочитает ли он одно из этих решений всем другим. Если да, то это решение принимается за окончательное и процесс заканчивается. В противном случае ЛПР просят выделить из предъявленных ему решений наименее предпочитаемое. Это решение исключается, а из оставшихся m решений формируется и решается очередная игровая задача. Далее таким же способом, как описано выше, находят новое альтернативное компромиссное решение и предъявляют его вместе с m уже имеющимися. Итеративный процесс продолжается до тех пор, пока ЛПР не выявит предпочитаемое им решение.
Рассмотренная процедура реализуется следующим алгоритмом.
Шаг 0. Определить и , для чего решить задачи
а)
при условии Х D. Очевидно, что получаемые решения ( ) не что иное, как идеальные решения.
б)
при условии X D. В противоположность предыдущим решения ( ) называют антиидеальными.
Шаг 1. Взять решения в качестве первоначальных решений и вычислить степени близости по формуле (10.24).