- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Решение на основе лексикографического упорядочения критериев
Как и в предыдущем подходе, предпочтения ЛПР выявляются до поиска наилучшего решения. Метод применим, если для ЛПР приемлемо ранжирование критериев по важности и при этом предпочтительным является то решение, в котором лучше значение более важного критерия независимо от значения всех менее важных критериев.
Лексикографическое отношение определяется следующим образом. Для двух векторов и имеет место отношение тогда и только тогда, когда выполняется одно из условий:
>
> (10.15)
………
m) > .
В этом случае говорят, что вектор Y лексикографически больше вектора .
Множество векторов (решений), оптимальных по отношению на G (соответственно на D), называют множеством лексикографически оптимальных точек (OptlexY). Так как для любых двух векторов либо один лексикографически больше другого, либо они равны, то множество OptlexY, если оно не пустое, содержит только один элемент. Так на множестве G, изображенном на рис.10.3, лексикографически оптимальной является только точка h.
Лексикографически-оптимальное решение достигается в процессе решения следующей последовательности задач:
находим при условии ;
находим при условии ;
. . . . . . . . . . . . . . . . . . . . .
m) находим при условии .
Процесс решения прекращается, как только очередная задача из этой последовательности дает единственное решение. Нетрудно показать, что такая процедура приводит к решению многокритериальной задачи, которое принадлежит парето-оптимальному множеству. В то же время, если остановиться на задаче, имеющей не единственное решение, то нельзя гарантировать, что полученное решение является эффективным (оно может быть слабо эффективным).
В случае линейной модели решение последовательности отдельных задач можно объединить в один симплекс-процесс, что значительно снижает трудоемкость решения. Для этого применяют лексикографический вариант симплекс-метода.
В этом методе каждому критерию соответствует своя строка относительных оценок (i-индекс критерия, j-индекс переменной). Строки располагаются в порядке убывания приоритетов критериев. Сначала симплекс-преобразования выполняются по . При достижении оптимального решения по 1-му критерию ( ) выявляют нулевые оценки небазисных переменных. Если таких нет, то решение единственное и лексикографическая оптимизация завершается. Если они есть, то в строке в столбцах с выделенными нулевыми ищут отрицательные оценки. Небазисная переменная xs, для которой а <0, вводится в базисное решение, улучшая значение 2-го критерия без ухудшения значения 1-го критерия. Этот процесс продолжается, пока будут выявляться такие перспективные переменные. Если они исчерпались или их не было, то переходят к решению по 3-му критерию, т.е. к выбору перспективных переменных по строке . Введение в решение небазисной переменной хр улучшит значение 3-го критерия без изменения первых двух, если а <0. Процесс решения многокритериальной задачи завершается, когда на последующих этапах не находятся перспективные переменные.