Многокритериальные модели и методы для задач оптимизации на графах : При P*NP имеем три случая: два как в однокритериальной задаче, а у третьего экспоненциальные трудоемкость и память

U odnokriterial'nykh zadach kolichestvo al'ternativ ravno 1. V mnogokriterial'nom sluchae snachala nakhodim polnoe mnozhestvo al'ternativ (PMA), a zatem spetsialist vydelyaet v nem nailuchshee reshenie, chto trebuet ot cheloveka nepod"emnykh usiliy pri perebore PMA. Osnova mnogokriterial'noy optimizatsii: opredelenie PMA i algoritmy nakhozhdeniya ego, razreshimost' s pomoshch'yu algoritmov lineynoy svertki kriteriev, statisticheski effektivnye i asimptoticheski tochnye algoritmy, polnye zadachi i nakhozhdenie otnositel'nogo ili absolyutnogo ukloneniya ot optimuma i eshche ryad voprosov. Glava 4 kasaetsya v osnovnom aktual'nykh zadach - riska upushchennoy vygody. Glava 5 posvyashchena modelirovaniyu sevooborota, a glava 6 - obshchemu sluchayu, kogda popadaem v usloviya neopredelennosti: znacheniya parametrov zadachi predstavlyayutsya ne chislami, a intervalami. Dlya spetsialistov v oblasti modelirovaniya i upravleniya slozhnymi sistemami, a takzhe dlya prepodavateley, studentov i aspirantov spetsial'nostey ekonomiki i prikladnoy matematiki Многокритериальные модели и методы для задач дискретной оптимизации на графах. Перепелица В.А. LAP, 2013. 330 с. ISBN 978-3-659-49814-5 Содержание Список условных обозначений Введение Глава 1. Алгоритмы с оценками для однокритериалных дискретных задач 1.1. Алгоритмы с оценками для дискретных задач оптимизации 1.2. Асимптотический подход к решению экстремальных задач на графах 1.3. Асимптотически оптимальный алгоритм для задачи коммивояжера 1.4. К задаче нахождения оптимального севооборота 1.5. К задаче о назначении Глава 2. Нахождение множества альтернатив для многокритериальных задач на графах и оценки сложности 2.1. Основные понятия и результаты 2.2. Описание исследуемых модельных задач 2.3. Полные задачи и NP-трудные проблемы 2.4. Нижние оценки мощности множеств альтернатив для задач на графах 2.5. Полнота задач с критериями удельного веса 2.6. Квазиполные задачи Глава 3. Исследование эффективности алгоритмов линейной свертки критериев 3.1. Формулировка проблемы и полиномиальные многокритериальные алгоритмы 3.2. О неразрешимости использования линейной свертки критериев для нахождения паретовского множества и полного множества альтернатив 3.3. Двукритериальные и трехкритериальные дискретные задачи, разрешимые с помощью полиномиальных алгоритмов линейной свертки 3.4. О сводимости проблемы нахождения полного множества альтернатив к NP -полным задачам 3.5. Статистически эффективные алгоритмы Глава 4. Оценки для дискретных многокритериальных задач 4.1. Введение 4.2. К оценке сложности многокритериальных транспортных задач 4.2.1. Многокритериальная транспортная задача 4.2.2. Оценки мощности ПМА 4.2.3. Неразрешимость 4.3. Статистически эффективные алгоритмы 4.4. Исследование одного класса двукритериальных задач об остовных деревях 4.5. Риск выбора нецелесообразного решения в процессе моделирования 4.5.1. Риски упущенной выгоды 4.5.2. Предпосылки существования риска упущенной выгоды для двукритериальной задачи инвестора 4.5.3. Математический аппарат учета инфляции, вычисления потока реальных денег, дисконтирования затрат и результатов 4.5.4. Сравнительный анализ оптимальных решений с учетом и без учета дисконтирования Глава 5. Исследование одного класса многокритериальных задач о севообороте 5.1. Формулировка многокритериальных задач землепользования 5.2. Оценка вычислительной сложности задачи (5.8)-(5.12) 5.3. Приближенный алгоритм для 1-критериальной задачи 5.4. Алгоритм с оценками эффективности 5.5. Алгоритмы линейной свертки 5.6. О свойствах задачи (5.1)-(5.7) 5.7. О построении метода решения задачи (5.1)-(5.7) Глава 6. Задачи оптимизации на графах с интервальными параметрами 6.1. Что является задачей дискретной оптимизации с интервальными параметрами? 6.2. Задачи оптимизации на графах с интервальными параметрами 6.3. Сведение интервальной задачи дискретной оптимизации к дискретной многокритериальной задаче 6.4. Оценки вычислительной сложности 6.5. Полиномиально разрешимые подклассы интервальных задач на графах 6.6. Статистически эффективные алгоритмы Литература