Разрешимость систем интервальных линейных уравнений и неравенств (И. <...> Линейное программирование при задании коэффициентов в виде множеств (Й. <...> Линейное программирование при задании коэффициентов в виде множеств . <...> Здесь вводятся различные типы разрешимости интервальных уравнений и неравенств, ряд множеств решений и некоторые другие важные понятия, систематически используемые также в других частях книги. <...> Рассматриваемаяв ней так называемаямакс-алгебра (или алгебра «макс-плюс», которую часто называют также «тропической алгеброй») является типичным примером идемпотентного полукольца, т.е. полукольца с идемпотентным сложением, таким что x+x = x длялюбого элемента x. <...> В Главе 2 исследуетсяразрешимость систем интервальных линейных уравнений и допустимость их решений. <...> Длялинейных систем Ax = b и Ax 0,где A ∈ A и b ∈ b, отдельно исследуютсяслабаяи сильнаяразрешимость, слабо и сильно допустимые решения. <...> На этом пути, комбинируя слабую и сильную разрешимость или слабо и сильно допустимые решенияуказанных систем, мы приходим к решению восьми задач. <...> Последняя часть Главы 2 посвящена специальным типам решений (допусковые решения, управляемые и формальные решения). <...> При допущениях общего характера выводится обычная форма теоремы о слабой двойственности. <...> Объединяющей концепцией этого подхода является понятие нечеткого отношения, в частности, нечеткое расширение 20 ПРЕДИСЛОВИЕ обычных отношений равенства или неравенства. <...> Мы показываем также, что допустимые и компромиссные решения являются выпуклыми при некоторых весьма слабых допущениях, и что max–компромиссное решение может быть найдено как обычное оптимальное решение некоторой классической многокритериальной задачи линейного программирования. <...> Квадратнаяматрица размера n называется диагональной,если ее элементы aik =0 длявсех i = k. <...> Матрица называется нижней треугольной,если ее элементы aik =0 длявсех i< k и верхней треугольной,еслиее элементы aik =0 длявсех <...>
Задачи_линейной_оптимизации_с_неточными_данными.pdf
УДК 518+519.4
Издание осуществлено при финансовой поддержке Российского
фонда фундаментальных исследований по проекту
№07-01-07102.
Фидлер М., Недома Й., Рамик Я., Рон И., Циммерманн К.
Задачи линейной оптимизации с неточными данными. — М.–Ижевск: НИЦ
«Регулярнаяи хаотическаядинамика», Институт компьютерных исследований,
2008. — 288 с.
Книга посвящена теории, численным методам и алгоритмам решения задач
линейной оптимизации с неточными входными данными. Она является одним из
первых изданий, где классические задачи линейного программированиярассматриваютсяприменительно
к интервальному заданию матрицы системы и вектора ее
правой части. Привлечение методов интервального анализа обеспечивает строгую
теоретическую базу дляразработки соответствующих алгоритмов. Это позволяет
в рамках единой теории и вычислительных методов решать задачи линейной оптимизации
как в классических постановках, так и в новых условиях. Разработанные
подходы и алгоритмы тесно увязываются с вопросами их практической реализации.
Изложение иллюстрируетсярядом примеров.
Книга рассчитана на широкий круг читателей, студентов, аспирантов, инженеров,
вычислителей, программистов и математиков, работающих в области решенияпрактических
задач линейной оптимизации с неточными исходными данными,
в условиях их неопределенности и неоднозначности.
ISBN 978-5-93972-688-7
Translation from the English language edition:
Linear Optimization Problems with Inexact Data
by M. Fiedler, J.Nedoma, J.Ram´ık, J.Rohn, and K.Zimmermann.
Springer Science+Business Media, Inc., New York, 2006
All Rights Reserved
Перевод на русский язык:
НИЦ «Регулярная и хаотическая динамика», 2008
c
c
http://shop.rcd.ru
http://ics.org.ru
Стр.6
Оглавление
Предисловие к русскому изданию . ... .. ... .. .. ... .. 12
Предисловие . ... .. ... .. .. ... .. ... .. .. ... .. 15
ГЛАВА 1. Матрицы (М.Фидлер) .. ... .. ... .. .. ... .. 22
1.1. Основные понятия из теории матриц и определителей .... 22
1.2. Нормы и основы вычислительной линейной алгебры . .... 38
1.3. Симметричные матрицы .. .... .... .... ... .... 45
1.4. Обобщенные обратные матрицы .. .... .... ... .... 51
1.5. Неотрицательные матрицы, M–матрицы и P–матрицы .... 54
1.6. Примеры других специальных классов матриц . . . . . .... 61
ГЛАВА 2. Разрешимость систем интервальных линейных
уравнений и неравенств (И.Рон) ... .. ... .. .. ... .. 64
2.1. Введение и обозначения.. .... .... .... ... .... 64
2.2. Алгоритм порожденияматриц Ym . .... .... ... .... 66
2.3. Вспомогательный результат по сложности вычислений .... 67
2.4. Разрешимость и допустимость ... .... .... ... .... 70
2.5. Интервальные матрицы и векторы . .... .... ... .... 74
2.6. Слабаяи сильнаяразрешимость/допустимость . . ... .... 77
2.7. Слабаяразрешимость уравнений . .... .... ... .... 78
2.8. Слабаядопустимость уравнений .. .... .... ... .... 81
2.9. Сильнаяразрешимость уравнений . .... .... ... .... 82
2.10. Сильнаядопустимость уравнений . .... .... ... .... 89
2.11. Слабаяразрешимость неравенств . .... .... ... .... 92
2.12. Слабаядопустимость неравенств . .... .... ... .... 93
2.13. Сильнаяразрешимость неравенств .... .... ... .... 94
2.14. Сильнаядопустимость неравенств . .... .... ... .... 96
2.15. Резюме I: Вычислительнаясложность задач ... ... .... 97
2.16. Допусковые решения. ... .... .... .... ... .... 98
2.17. Управляемые решения . ... .... .... .... ... .... 100
2.18. Формальные решения. ... .... .... .... ... .... 102
2.19. Случай квадратной системы .... .... .... ... .... 103
Стр.9
10
ОГЛАВЛЕНИЕ
2.20. Резюме II: Типы решений .. .... .... .... ... .... 113
2.21. Замечанияи библиографический комментарий .. ... .... 113
ГЛАВА 3. Интервальное линейное программирование
(И. Рон) .. ... .. ... .. .. ... .. ... .. .. ... .. 118
3.1. Линейное программирование, двойственность . . ... .... 118
3.2. Задача интервального линейного программирования. .... 123
3.3. Область значений оптимума .... .... .... ... .... 123
3.4. Нижняя граница .... ... .... .... .... ... .... 127
3.5. Верхняя граница .... ... .... .... .... ... .... 134
3.6. Конечнаяобласть значений оптимума ... .... ... .... 140
3.7. Алгоритм вычисленияобласти значений оптимума .. .... 142
3.8. Замечанияи библиографический комментарий .. ... .... 142
ГЛАВА 4. Линейное программирование
при задании коэффициентов в виде множеств
(Й.Недома, Я.Рамик) .. .. .. ... .. ... .. .. ... .. 145
4.1. Введение .... .... ... .... .... .... ... .... 145
4.2. Линейное программирование при задании
коэффициентов в виде множеств . . .... .... ... .... 145
4.2.1. Строгая, слабаяи сильнаядопустимости . ... .... 147
4.2.2. Целеваяфункция ... .... .... .... ... .... 149
4.3. Двойственность .... ... .... .... .... ... .... 150
4.3.1. Слабаядвойственность ... .... .... ... .... 152
4.3.2. Сильнаядвойственность . . .... .... ... .... 153
4.4. Обобщенный симплекс-метод ... .... .... ... .... 158
4.4.1. Алгоритм нахождениядвойственного оптимального
решения. .... ... .... .... .... ... .... 158
4.4.2. Случай прямоугольной матрицы .. .... ... .... 160
4.4.3. Алгоритм нахождениянаилучшего базиса ... .... 161
4.5. Заключение ... .... ... .... .... .... ... .... 162
ГЛАВА 5. Нечеткая линейная оптимизация (Я.Рамик) . ... .. 163
5.1. Введение .... .... ... .... .... .... ... .... 163
5.2. Нечеткие множества, нечеткие величины . .... ... .... 165
5.3. Нечеткие отношения. ... .... .... .... ... .... 169
5.4. Задачи нечеткой линейной оптимизации . .... ... .... 176
5.5. Допустимое решение . ... .... .... .... ... .... 180
5.6. «Оптимальное» решение .. .... .... .... ... .... 185
5.6.1. Удовлетворяющее решение . .... .... ... .... 185
Стр.10
ОГЛАВЛЕНИЕ
11
5.6.2. α–эффективное решение .. .... .... ... .... 190
5.7. Двойственность .... ... .... .... .... ... .... 193
5.8. Расширенное сложение ... .... .... .... ... .... 200
5.9. Специальные модели нечеткого
линейного программирования... .... .... ... .... 204
5.9.1. Гибкое линейное программирование ... ... .... 205
5.9.2. Интервальное линейное программирование .. .... 207
5.9.3. Задачи нечеткого линейного программирования
с центрированными параметрами . .... ... .... 211
5.10. Многокритериальнаязадача нечеткого
линейного программирования... .... .... ... .... 214
5.11. Численный пример . . ... .... .... .... ... .... 219
5.12. Заключение ... .... ... .... .... .... ... .... 224
ГЛАВА 6. Интервальные линейные системы и задачи
оптимизации на max-алгебрах (К.Циммерманн) . . . ... .. 225
6.1. Введение .... .... ... .... .... .... ... .... 225
6.2. max–сепарабельные функции и max–сепарабельные
задачи оптимизации .. ... .... .... .... ... .... 226
6.3. Обозначенияв экстремальной алгебре . . .... ... .... 237
6.4. Точечные системы (⊕,⊗)–линейных
уравнений и неравенств ... .... .... .... ... .... 240
6.6. (⊕,⊗)–линейные системы равенств и неравенств
с интервальными коэффициентами .... .... ... .... 249
6.7. Задачи оптимизации с (⊕,⊗)–линейными
интервальными ограничениями .. .... .... ... .... 254
6.8. Заключение ... .... ... .... .... .... ... .... 258
Литература .. ... .. ... .. .. ... .. ... .. .. ... .. 259
Дополнительная литература к русскому изданию .. .. ... .. 273
Список принятых сокращений и обозначений .. .. .. ... .. 279
Предметный указатель ... .. .. ... .. ... .. .. ... .. 282
6.5. Точечные max–сепарабельные задачи
оптимизации с (⊕,⊗)–линейными ограничениями .. .... 244
Стр.11