Саати Т. Целочисленные методы оптимизации и связанные с ними экстремальные проблемы

Оглавление

Предисловие редактора русского издания.............. 5

Предисловие автора к русскому изданию.............. 7

Предисловие........................... 9

Глава 1. Основные понятия: примеры задач и методов....... 13

1.1. Введение......................... 13

1.2. Элементарные определения и полезные теоремы....... 16

1.3. Максимумы и минимумы функций, определенных на л-мерном евклидовом пространстве Еп....... 24

1.4. Классификация алгебраических задач........... 37

1.5. Примеры дискретной оптимизации функций в замкнутой форме: критерий достаточности.......... 49

1.6. Асимптотические результаты............... 58

1.7. Примеры задач...................... 59

Литература.......................... 68

Глава 2. Методы геометрической оптимизации............ 70

2.1. Введение........................ 70

2.2. Симметрия и оптимизация................. 72

2.3. Многоугольники и многогранники............. 76

2.4. Разбиения или разложения................ 80

2.5. Примеры изопериметрических задач и задач поиска кратчайшего пути................. 87

2.6. Графы и сети....................... 96

2.7. Покрытие шахматной доски [62, 72, 91]........... 121

2.8. Дискретная геометрия: упаковка, покрытие, заполнение [11,13, 41, 56, 68, 80]........... 126

2.9. Максимумы и минимумы в теории множеств......... 151

Литература......................... 154

Глава 3. Некоторые элементарные приложения............ 159

3.1. Введение......................... 159

3.2. Теория информации.................... 159

3.3. Фальшивые монеты и фальшивомонетчики [1, 4, 10, 11]... 161

3.4. Задача справедливого дележа (как справедливо разрезать пирог)[2,5]................ 164

3.5. Количество тестов, метод исчерпания............ 166

3.6. Задача о джипе [3, 11].................. 167

3.7. Задача о кокосовых орехах (гя. 1) [9]........... 170

3.8. Задача о неограниченном сверху максимуме [12]........ 172

3.9. Существование выигрывающей стратегии [14]........ 172

3.10. Игральный столик [13].................. 173

Литература........................ 174

Глава 4. Оптимизация при диофантовых ограничениях........ 175

4.1. Введение......................... 175

4.2. О разрешимости диофантовых уравнений.......... 177

4.3. Линейные диофантовы уравнения [22]............ 181

4.4. Некоторые нелинейные уравнения............. 191

4.5. Оптимизация при диофантовых ограничениях........ 195

4.6. Полезные неравенства................... 214

4.7. Теория максимина.................... 216

Литература.......................... 218

Глава 5. Целочисленное программирование.............. 220

5.1. Введение......................... 220

5.2. Задача о ранце [16]..................... 224

5.3. Общее линейное программирование............ 229

5.4. Использование симплексного процесса при решении транспортной задачи [10, 13].......... 241

5.5. Алгоритм целочисленного программирования........ 250

5.6. Алгоритм полностью целочисленного программирования с параболическими ограничениями [40].......260

5.7. Алгебраическая формулировка задач............ 265

5.8. Псевдобулевы методы в бивалентном программировании....... 275

Литература......................... 298

Об авторе

Саати Томас Л.

Математик с мировым именем, автор метода анализа иерархий, который нашел широкое применение в задачах многокритериального выбора решений, разрешения конфликтов, стратегического планирования. В настоящее время является профессором Питтсбургского университета (школа бизнеса Каца, аспирантура). Ученую степень доктора математики получил в Йельском университете; член Национальной академии техники США. Ранее работал в Университете штата Пенсильвания (школа Вартона) и в Агентстве контроля вооружений и разоружения при Государственном департаменте США в Вашингтоне. Участвовал в переговорах США и СССР по разоружению в Женеве в 1970-х годах. В настоящее время занимается методами принятия решений, стратегического планирования, разрешения конфликтов и моделированием процессов деятельности мозга.

Томас Л. Саати — консультант правительств многих стран и крупного бизнеса в области решения сложных проблем. Разработанный им метод анализа иерархий (Analytic Hierarchy Process, AHP) — одна из немногих методик многокритериального выбора, признанная в мире. Аналитические сети (Analytic Network Process, ANP) — обобщение AHP на проблемы с зависимостями и обратными связями между элементами. Международные симпозиумы по AHP/ANP (ISAHP) проводятся раз в два года и собирают ученых и практиков со всего мира. Томас Л. Саати — автор множества книг по теории принятия решений и теории графов. Лауреат многих наград и премий в области математики.