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

A text on operations research statistics designed for junior and senior graduate courses in multiple criteria decision making, multiple criteria optimization, and multiple objective programming. Shows how to implement the techniques of multiple criteria optimization for solving large-scale multiple objective problems on a computer. Contains full details on such recent breakthrough developments as the Tchebycheff method, a method that enables one to solve large-scale multiple objective linear, integer and nonlinear programming problems. Includes numerous exercises for solving problems manually and by using a computer. Обложка ......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