Многокритериальная оптимизация. Теория, вычисления и приложения

Штойер Р. (Steuer)0-471-88846-X

Table of contents :
Обложка ……Page 1
Титульный лист оригинала ……Page 2
Титульный лист ……Page 3
Аннотация ……Page 4
Предисловие редактора ……Page 5
Предисловие ……Page 9
1.1. Задача многокритериального программирования ……Page 14
1.2. Примеры многокритериальности ……Page 15
1.3. Многокритериальная оптимизация ……Page 16
1.4. Оптимальные и окончательные решения ……Page 17
1.5. Многокритериальная оптимизация и анализ решений по набору показателей ……Page 18
1.6. Обозначения и сокращения ……Page 19
2.1.1. Определение множеств и операции принадлежности ……Page 21
2.1.2. Подмножества и равенство множества ……Page 22
2.1.4. Операции над множествами ……Page 23
2.1.5. Действительная прямая и интервалы ……Page 24
2.1.6. Обобщенные операции, множества индексов и кардинальное число ……Page 25
2.1.8. Отображения и функции ……Page 26
2.1.9. Упорядоченные наборы из $п$ чисел и декартовы произведения ……Page 27
2.1.11. Отношения ……Page 28
2.2.1. Матрицы ……Page 30
2.2.2. Операции над матрицами ……Page 31
2.2.4. Определители ……Page 33
2.2.6. Вычисление обратной матрицы ……Page 35
2.2.8. Векторы и точки в я-мерном пространстве ……Page 37
2.2.9. Линейные и выпуклые комбинации векторов ……Page 38
2.2.10. Линейная независимость ……Page 39
2.2.11. Ранг матрицы ……Page 40
2.2.12. Базисы ……Page 41
2.2.14. Некоторые функции ……Page 42
2.3.1. Открытые и замкнутые множества ……Page 43
2.3.2. Выпуклые множества и крайние точки ……Page 44
2.3.4. Размерность и суммирование множеств ……Page 46
2.3.6. Связные и дискретные множества ……Page 48
2.4. Конусы ……Page 49
2.4.2. Размерность конуса ……Page 50
2.4.3. Крайние лучи и многогранные конусы ……Page 51
2.4.4. Поляры конусов ……Page 52
2.5.1. Семейство $L_p$-норм ……Page 54
2.5.2. Семейство $L_p$-метрик ……Page 55
2.5.3. Семейство взвешенных $L_p$-метрик ……Page 56
Глава 3. Линейное программирование в случае одного критерия ……Page 58
3.1. Градиенты и линии уровня ……Page 60
3.2. Пример задачи линейного программирования ……Page 62
3.3. Графические примеры ……Page 64
3.4. Симплекс-метод ……Page 67
3.4.1. Задача линейного программирования в канонической форме ……Page 68
3.4.2. Исходная таблица ……Page 70
3.4.3. Процедура замещения ……Page 72
3.4.4. Метод прямоугольников ……Page 76
3.4.6. Вырожденность и альтернативные оптимумы. ……Page 77
3.5. Теория двойственности ……Page 78
3.6. Неположительные и неограниченные переменные ……Page 81
3.7. Входной формат MPSX ……Page 82
3.8. Структура симплекс-таблицы ……Page 84
3.9. Двухэтапный метод линейного программирования ……Page 87
3.10. Двойственный симплекс-алгоритм ……Page 89
3.11.1 Различаются только целевые функции ……Page 91
3.11.3. Изменяется столбец матрицы ограничений ……Page 92
Глава 4. Определение всех альтернативных оптимумов ……Page 93
4.1. Классификация задач ЛП с одним критерием ……Page 94
4.2. Замечания о процедуре замещения и кодирования базисов ……Page 96
4.3. Ускоренный алгоритм ……Page 101
4.4. Основные списки ……Page 104
4.5. Пример, иллюстрирующий этап III ……Page 105
Глава 5. Замечания о параметрическом программировании (случай параметризации целевой функции) ……Page 109
5.1. Обычное параметрическое программирование ……Page 110
5.2. Параметрическое программирование на основе выпуклой комбинации векторов ……Page 112
5.3. Параметрическое программирование на основе критериального конуса ……Page 116
5.4. Подход на основе многокритериального линейного програм мирования ……Page 121
Глава 6. Функции полезности, недоминируемые критериальные векторы и эффективные точки ……Page 123
6.1. Виды функций полезости ……Page 124
6.2. Монотонность ……Page 126
6.3. Достижимое множество в пространстве критериев ……Page 129
6.4. Подход, связанный с функцией полезности ……Page 130
6.5. Доминирование ……Page 131
6.6. Недоминируемые критериальные векторы ……Page 132
6.7. Эффективность ……Page 133
6.8. Установление эффективности с использованием множеств доминируемости ……Page 134
6.10. Специфика оптимальности в случае нескольких критериев ……Page 138
6.12. Влияние нелинейности ……Page 140
Упражнения ……Page 141
Глава 7. Метод взвешенных сумм с точечным оцениванием весов ……Page 146
7.2. Математическое обоснование ……Page 147
7.3. Какой смысл имеют веса? ……Page 148
7.4. Определение весов ……Page 149
7.5. Критериальный конус ……Page 151
7.5.1. Нуль-векторное условие не выполняется ……Page 152
7.5.2. Нуль-векторное условие выполняется ……Page 153
7.6. Относительная внутренность критериального конуса ……Page 154
7.7. Нахождение эффективных точек с использованием составных градиентов ……Page 155
7.8. Связь критериального конуса с множеством доминируемости ……Page 159
7.9. Эффективные грани допустимой области ……Page 161
7.10. Определение подмножеств из множества весовых векторов ……Page 163
Упражнения ……Page 167
8.1. Трудности оценки оптимальных весовых векторов ……Page 171
8.1.1. Зависимость от предпочтений лица, принимающего решения ……Page 172
8.1.2. Зависимость от относительных длин градиентов целевой функции ……Page 173
8.1.3. Зависимость от допустимой области ……Page 174
8.2. Трудности, вызванные корреляцией критериев ……Page 176
8.3. Дополнительные трудности, связанные с оптимальными весовыми векторами ……Page 177
8.4.1. Использование числа 10 в соответствующей степени ……Page 178
8.4.2. Применение множителей, выравнивающих диапазоны изменения критериев ……Page 179
8.5. Метод $е$-ограничений для сжатия области допустимых решений ……Page 180
8.5.2. Возможные исходы ……Page 182
8.6. Анализ почти-оптимальности ……Page 184
Упражнения ……Page 187
Глава 9. Алгоритмы векторной максимизации ……Page 190
9.1. Математические основы ……Page 191
9.2. Теория векторной максимизации ……Page 193
9.3. Один алгоритм векторной максимизации ……Page 198
9.4. Слабая эффективность ……Page 200
9.5. Классификация задач МКЛП ……Page 202
9.6.1. Подзадача для проверки эффективности крайней точки ……Page 203
9.6.2. Методы нахождения эффективной крайней точки ……Page 204
9.7.1. Тест Эванса-Штойера ……Page 211
9.7.2. Тест Изермана ……Page 212
9.7.3. Метод Экера ……Page 214
9.7.4. Процедура Зайонца-Валлениуса ……Page 215
9.8. Определение всех максимальных эффективных граней ……Page 222
9.9. Подход на основе векторной максимизации к решению задач МКЛП ……Page 224
9.10. Сжатие критериального конуса ……Page 225
9.10.1. Интервально-весовой критериальный конус ……Page 226
9.10.2. Оболочка сжатого критериального конуса ……Page 229
9.11. Программа ADBASE ……Page 231
9.11.1. Входной формат ADBASE ……Page 233
9.11.2. Гибкость программы ADBASE ……Page 236
9.11.4. Пример расчета с помощью программы ADBASE ……Page 238
9.12. Опыт вычислений ……Page 239
9.13.1. Таблицы выигрышей ……Page 245
9.13.2. Основные свойства задачи поиска минимальных значений критериев ……Page 247
9.13.3. Алгоритм, основанный на симплекс-методе ……Page 248
Упражнения ……Page 249
Глава 10. Целевое программирование ……Page 258
10.1. Цели и утопические множества ……Page 259
10.2. Архимедова задача ЦП ……Page 261
10.2.1. Линии уровня архимедовых целевых функций ……Page 263
10.2.2. Решение архимедовых задач ЦП ……Page 264
10.3. Модели ОСММ ……Page 266
10.4. Задачи ЦП с приоритетами ……Page 267
10.5. Лексикографический симплекс-метод ……Page 270
10.6. Эффективность в ЦП ……Page 272
10.7. Проблемы чувствительности ……Page 273
10.8. Интерактивное ЦП ……Page 274
10.9. Минимизация максимального отклонения ……Page 275
10.10. Многокритериальная формулировка задачи ЦП ……Page 276
10.11. Математическое обеспечение ЦП ……Page 277
Упражнения ……Page 279
Глава 11. Фильтрация и дискретизация множеств ……Page 282
11.1. Прямая и обратная фильтрации ……Page 283
11.3. Веса для выравнивания диапазона ……Page 284
11.4. Механизм прямой фильтрации ……Page 285
11.4.1. Метод первой точки вне окрестностей ……Page 286
11.4.2. Стратегия удвоения и деления пополам ……Page 287
11.4.3. Начальные значения $d$ и $delta d$ ……Page 289
11.4.4. Метод ближайшей точки вне окрестностей ……Page 290
11.4.6. Максимально дисперсные множества ……Page 292
11.5. Обратная фильтрация ……Page 293
11.6. Программа FILTER ……Page 294
11.7. Интерактивные процедуры прямой в обратной фильтрации ……Page 296
11.8.1. Предопределенные выпуклые комбинации ……Page 299
11.8.3. Выпуклые комбинации, полученные из распределения Вейбулла ……Page 301
11.9. Программа LAMBDA ……Page 302
Упражнения ……Page 305
Глава 12. Многокритериальное дробно-линейное программирование ……Page 308
12.1. Дробно-линейное программирование с одним критерием ……Page 309
12.1.1. Метод преобразования переменных ……Page 313
12.1.2. Метод обновления целевой функции ……Page 314
12.2. Случай обращения в нуль знаменателя ……Page 316
12.4. Пример задачи МКДЛП и терминология ……Page 319
12.5. Графическое определение эффективности ……Page 321
12.6. Другие примеры задач МКДЛП ……Page 322
12.7. Пример задачи МКДЛП с нелинейной границей множества $Е_w$ ……Page 325
Упражнения ……Page 327
Глава 13. Интерактивные процедуры ……Page 330
13.1. STEM ……Page 332
13.1.1. Алгоритм STEM ……Page 333
13.1.2. Фрагмент результатов вычислений программы STEM ……Page 335
13.1.3. Комментарии к программе STEM ……Page 337
13.2. Процедура Джоффриона — Дайера — Фейнберга (GDF) ……Page 338
13.2.1. Метод наискорейшего подъема ……Page 339
13.2.2. Алгоритм Фрэнка-Вулфа ……Page 340
13.2.3. Программа для определения локально подходящих весов ……Page 342
13.2.4. Алгоритм GDF ……Page 344
13.2.6. Числовой пример, иллюстрирующий метод GDF ……Page 347
13.2.7. Комментарии к алгоритму GDF ……Page 349
13.3.1. Z—W-алгоритм ……Page 350
13.3.2. Числовой пример использования метода Z—W ……Page 354
13.3.3. Определение небазисных переменных, эффективных по отношению к $Lambda^{h}$ ……Page 358
13.4. Интерактивный метод со взвешенными суммами критериев и фильтрацией ……Page 361
13.4.1. Настройка (определение параметров метода) ……Page 362
13.4.2. Интерактивный алгоритм со взвешенными суммами критериев ……Page 363
13.4.3. Комментарии к интерактивной процедуре со взвешенными суммами критериев ……Page 365
13.5.1. Свертки критериев (скаляризующие функции) ……Page 367
13.5.2. «Проектирование» полупрямой на множестве $N$ ……Page 369
13.5.3. Визуальный интерактивный алгоритм ……Page 372
13.5.4. Комментарии к визуальному интерактивному методу ……Page 375
Упражнения ……Page 376
Глава 14. Интерактивный метод со взвешенными метриками Чебышева ……Page 383
14.1. Идеальный критериальный вектор $z$ ……Page 384
14.2. Выбор значений $varepsilon_i$ ……Page 386
14.3.1. Линии (поверхности) уровня ……Page 387
14.3.3. Определяющие точки, вершины и диагонали ……Page 389
14.3.4. Точки пересечения с $Z$ ……Page 392
14.4. Выбор значений $rho$ ……Page 393
14.5. Диагональное направление чебышевской метрики ……Page 395
14.6. Неопорные недоминируемые критериальные векторы ……Page 396
14.6.1. Метод взвешенных сумм и неопорность ……Page 397
14.6.2. Метод взвешенных сумм и опорные критериальные векторы ……Page 398
14.6.3. Подзадача-тест на неопорность ……Page 399
14.6.4. Множества доминируемости и неопорность ……Page 400
14.7. Несобственно недоминируемые критериальные векторы ……Page 403
14.8.1. Теория для случая конечного дискретного множества $S$ ……Page 405
14.8.2. Теория для случая многогранного множества $S$ ……Page 409
14.8.3. Теория для нелинейного и дискретного случаев с бесконечным числом точек ……Page 410
14.9. Алгоритм взвешенных метрик Чебышева ……Page 412
Упражнения ……Page 415
Глава 15. Реализация алгоритмов метрик Чебышева и взвешенных сумм ……Page 420
15.1. Формулировка задач ……Page 421
15.2. Матрица формата MPSX ……Page 422
15.3. Последовательность команд SAVE/REVISE/RESTORE ……Page 423
15.5. Организация повторяющихся процедур оптимизации ……Page 424
15.6. Иллюстративный пример задачи МКЛП ……Page 425
15.7. Некоторые решения, полученные с помощью алгоритмов на основе метрик Чебышева, в иллюстративных примерах ……Page 427
15.8. Некоторые заключительные замечания по поводу реализации метода метрик Чебышева ……Page 429
15.8.2. Диапазоны изменения критериев на множестве эффективных точек ……Page 430
15.8.4. Наиболее предпочтительный вектор как начальная точка фильтрации ……Page 431
15.8.6. Выбор значений $varepsilon_i$ в случае целочисленных и нелинейных задач ……Page 432
Упражнения ……Page 433
Глава 16 Приложения ……Page 436
16.1. Изготовление колбасной смеси ……Page 437
16.1.1. Задача о смеси для сосисок ……Page 438
16.1.2. Процедура векторной максимизации с фильтрацией для решения задачи ……Page 439
16.1.3. Формулировка задачи о смеси для сосисок ……Page 440
16.1.4. Результаты расчетов ……Page 443
16.2.1. Состояние вопроса ……Page 447
16.2.3. Формулировка задачи управления жалованием служащих ……Page 449
16.2.4. Результаты вычислений ……Page 453
16.3. Еще два приложения ……Page 457
16.3.1. Планирование качества воды в бассейне реки ……Page 458
16.3.2. Управление попусками из водохранилищ ……Page 460
17.1. Интерфейс компьютера с пользователем ……Page 461
17.2. Различные фирмы выдачи результатов на экран ……Page 462
17.3. Траекторная оптимизация ……Page 465
17.4. Другие области исследований в многокритериальной оптимизации ……Page 468
Список литературы ……Page 469
Список работ, переведенных на русский язык ……Page 498
Дополнительный список литературы ……Page 499