- •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. Диалоговые методы решения задач по многим критериям
- •Метод уступок
- •Интерактивное компромиссное программирование
- •Построить таблицу
Построить таблицу
|
X1 |
X2 |
… |
Xm |
f1 |
|
|
… |
|
f2 |
|
|
… |
|
… |
… |
… |
… |
… |
fm |
|
|
… |
|
где - степень близости j-ro решения к максимальному значению i-й целевой функции.
Шаг 2. Решить следующую игровую задачу одним из методов линейного программирования.
при условиях
. . .
Шаг 3. Образовать новую функции свертки, используя оптимальные веса, найденные на шаге 2, и решить следующую задачу максимизации этой функции для получения нового альтернативного компромиссного решения .
при условии X D.
Шаг 4. Вычислить значения степеней близости нового решения к максимально возможным значениям целевых функций, . Добавить колонку с этими значениями к таблице, построенной на шаге 1.
Шаг 5. Представить ЛПР новую таблицу и спросить, предпочитает ли он строго одно решение всем другим m-решениям. Если да, то идти на шаг 6. Иначе просить ЛПР отметить наименее предпочитаемое решение. Заменить его новым решением, найденным на шаге 4, и вернуться на шаг 2.
Шаг 6. Останов.
Пример 10.7. Применим этот алгоритм к задаче из примера 10.5.
Шаг 0. a)
при условии X D,
где D определяется системой
x1+x2 8,
-x1+x2 2,
0 x1 6, 0 x2 4.
Решение: =(0,2), =2.
f2(X)=4x1-x2
при условии X D.
Решение: =(6,0), =24.
б) f1(X)=-2x1+x2
при условии X D.
Решение: =(6,0), =-12.
= 4x1- x2 min
при условии X D.
Решение: =(0.2). =-2.
Шаг 1. Решения и принимаем за первоначальные эффективные решения X1 и X2. Составляем таблицу степеней близости
|
X1 |
X2 |
|
f1 |
1 |
0 |
2 |
f2 |
0 |
1 |
24 |
Шаг 2. Решаем задачу линейного программирования:
при условиях
,
,
.
Решение: =0.5, =0.5.
Шаг 3. Составляем новую функцию свертки
Решаем следующую задачу линейного программирования для нахождения нового компромиссного решения:
при условии X D.
Решение: Х3=(4,4), f1(Х3)=-4, f2(X3)=l2. На рис.10.17 это точка С.
Шаг 4. Вычисляем степени близости полученного решения
,
и показываем ЛПР три эффективных решения:
-
X1
X2
X3
f1
1
0
0.571
2
f2
0
1
0.538
24
Шаг 5. Предположим, что ЛПР не устраивает ни одно из этих решений, а наименее предпочтительным он считает решение X1. Тогда это решение заменяем решением X3 и возвращаемся на шаг 2.
Вторая итерация
Шаг 2. Решаем следующую задачу для определения новых весов:
d4(X)=> max
при условиях
0.571 + 0.538 d4,
2 d4,
Оптимальные значения: =0.447, =0.553.
Шаг 3. Решаем задачу с этими весами:
d4(X)=0.447 d1(X) + 0.553 d2(Х)=
= (2х1+ x2+40)=> max
при условии X D.
Решение: Х4=(6.2), f1(X4)=-10, f2(X4)=22. На рис.10.17 это вершина E множества достижимости.
Шаг 4. Вычисляем степени близости нового решения
=0.143, =0.923
и предъявляем его ЛПР вместе с оставшимися:
-
X3
X2
X4
f1
0.571
0
0.143
2
f2
0.538
1
0.923
24
Шаг 5. Предположим, что ЛПР предпочитает новое решение всем другим. Идем на шаг 6.
Шаг 6. Останов. Наилучшее компромиссное решение нашей задачи:
Х =(6.2), f = (-10,22), d = (0.143,0.923).
Отметим некоторые особенности рассмотренного метода.
При его применении необходимо иметь в виду, что в соответствии с теоремой 5 максимизация линейной свертки (10.25) гарантирует получение эффективного решения только в случае положительности всех . Наличие нулевых значений весов может приводить к слабо эффективным решениям.
Из анализа процедуры поиска компромиссного решения следует, что область принятия решений сужается после каждой итерации алгоритма. При этом можно ожидать хорошей сходимости, так как каждое новое решение, предъявляемое ЛПР, является наиболее вероятным среди уже имеющихся, что обусловлено максиминным выбором весов.
Очевидным достоинством метода является использование естественного для ЛПР способа выражения своих предпочтений. Здесь отсутствуют какие-либо эвристические параметры (к ним относят параметры, значения которых должен назначать ЛПР).
Если модель исходной многокритериальной задачи линейна, то вся вычислительная часть интерактивного метода может быть реализована с помощью стандартных пакетов линейного программирования, что означает возможность решения задач большой размерности. Подзадача определения оптимальных весов (шаг 2) остается линейной при любом виде исходной модели.
Наконец, заметим, что для получения очередного нового решения можно применить вместо линейной максиминную свертку. Такая замена может оказаться существенной для линейных задач, так как линейная свертка позволяет находить решения только в вершинах, в то время как максиминная – и на ребре или грани. И тем самым можно избежать возможных повторений решений.
1