|
Алгоритмы решения экстремальных задач |
Романовский И. В. |
год издания — 1977, кол-во страниц — 352, тираж — 16000, язык — русский, тип обложки — твёрд. 7Б тканев., масса книги — 380 гр., издательство — Физматлит |
|
цена: 600.00 руб | ![Положить эту книгу в корзину](/images/addToBasket.gif) | | | |
|
Сохранность книги — хорошая
Формат 84x108 1/32. Бумага типографская №3 |
ключевые слова — экстремальн, линейн, программирован, транспортн, комбинатор, граф, дискрет, динамическ |
В книге излагаются теория и численные методы решения важных классов экстремальных задач: общей задачи линейного программирования, транспортной задачи и задач, ей родственных, комбинаторных задач на графах, ряда дискретных задач динамического программирования.
Изложение численных методов сопровождается разбором алгоритмов, записанных на алгоритмических языках алгол-60 и алгол-68; при этом особое внимание уделено вопросам представления данных при эффективной организации вычислительного процесса.
Книга рассчитана на студентов-старшекурсников и аспирантов математических факультетов, специализирующихся в приложениях, а также на сотрудников научно-исследовательских учреждений и вычислительных центров, связанных с разработкой численных методов решения экстремальных задач.
Илл. 73, табл. 37, библ. 233 назв.
В этой книге излагаются в различных аспектах — от теоретического исследования до программы — методы решения экстремальных задач, главным образом дискретных.
Серьёзные экстремальные задачи решаются на вычислительных машинах, и это обстоятельство, несомненно, должно влиять на разработку, изучение и изложение методов решения экстремальных задач. Речь должна идти об эффективной организации вычислительного процесса, при разработке которой следует учитывать многие «технические» и кажущиеся несущественными детали — структуру вычислительной машины, формы представления данных, особенности используемых алгоритмических языков и соответствие их грамматических конструкций машинным возможностям.
Имеется широкий круг практически важных задач, в которых «вычислительная» в традиционном понимании часть действий оказывается очень скромной, и основные сложности лежат в логической структуре алгоритма и в вопросах представления исходной и вспомогательной информации. В таких задачах (а размеры и время счёта в них часто бывают значительными) обычно особенно существенно правильно организовать вычисления.
Цель этой книги — показать в действии некоторые способы организации вычислений, используемые в современных методах решения экстремальных задач. Однако нельзя достичь хорошего понимания этих вопросов, если формализация задачи отделена от выбора метода решения, метод решения — от возможностей алгоритмического языка, запись алгоритма — от понимания особенностей вычислительной машины и класса решаемых задач.
Очевидно, что задача влияет на метод, метод на алгоритм, алгоритм на ход вычислений. Важно отметить, что хороший алгоритм должен учитывать специфику вычислительного процесса, хороший метод вычислений — конструкции алгоритмического языка, хорошая постановка задачи — понятия, характерные для предполагаемого численного метода.
Таким образом, деление изложения на «теоретическую», «алгоритмическую» и «чисто программистскую» части представляется не только неестественным, но даже и вредным, и было сделано всё возможное, чтобы соединить эти части в единое целое и по возможности облегчить переходы. С этой целью была выбрана система обозначений, в которой такие переходы не вызывают затруднений. Для демонстрации готовых алгоритмов и отдельных конструкций используются два языка: алгол-60 и алгол-68, и такой выбор требует некоторых пояснений…
Хотя основной нашей целью являются дискретные экстремальные задачи, линейное программирование может рассматриваться как естественное начало. Поэтому в гл. 2 в лаконичной форме приведены основные факты теории линейного программирования, постановки задач, метод последовательного улучшения допустимого базисного решения и различные подходы к его вычислительной реализации.
В гл. 3 вводятся определения теории графов, которые затем интенсивно используются во всём дальнейшем изложении, после чего начинается изучение задач, связанных с транспортными потоками. Эти задачи интересны не только своими непосредственными практическими приложениями, но и неожиданными и интересными связями с различными разделами математики, в частности с комбинаторикой. Эти комбинаторные следствия из теории потоков и родственные им задачи собраны в гл. 4. Далее, в гл. 5 появляются более сложные комбинаторные задачи, для которых, как правило, нет хороших методов решения и в качестве основного вычислительного средства рассматривается метод улучшенного перебора.
Последние две главы посвящены специфическим задачам (задачам динамического программирования), которые можно решать рекуррентно, сводя задачу к такой же задаче меньших размеров. В гл. 6 рассматриваются комбинаторные задачи этого типа, а в гл. 7 — близкие по духу к материалу остальной книги вероятностные задачи, связанные с управляемыми марковскими цепями (марковские процессы решения).
Читателю, знакомому с литературой, бросится в глаза отсутствие многих традиционных разделов математического программирования. Это естественно — задача предлагаемой книги в том, чтобы пополнить литературу изложением вопросов, которые слабее в ней представлены, а нуждаются в не меньшем внимании. В библиографических указаниях в конце книги приводятся ссылки на «традиционную» литературу.
К сожалению, даже в тех вопросах, которые включены в книгу, изложение может показаться односторонним, и для такого впечатления есть основания. Единство стиля как в теоретических, так и в вычислительных вопросах требовало серьёзной переработки каждой используемой работы, часто существенно изменяющей первоначальные идеи её. По возможности неполнота текста компенсируется библиографическими указаниями.
Эта книга появилась в результате моей преподавательской деятельности на математико-механическом факультете Ленинградского государственного университета. Её можно использовать как пособие для спецкурсов по методам дискретной оптимизации, читаемых на математических факультетах университетов и технических вузов.
При работе над книгой большую помощь мне оказали заведующий кафедрой исследования операций проф. М. К. Гавурин и сотрудники кафедры и лаборатории исследования операций ЛГУ. Приношу им искреннюю благодарность.
ПРЕДИСЛОВИЕ Автор
|
ОГЛАВЛЕНИЕПредисловие | 5 | | Г л а в а 1. Подготовительные сведения | 9 | | § 1. Принятые обозначения | 9 | § 2. Описания алгоритмов | 14 | § 3. Представление данных в вычислительной машине | 22 | § 4. Списки | 35 | | Г л а в а 2. Некоторые общие сведения о линейном программировании | 46 | | § 1. Введение | 46 | § 2. Постановка задачи линейного программирования | 47 | § 3. Теория двойственности | 52 | § 4. Базисные решения. Метод последовательных улучшений | 59 | § 5. Устранение зацикливания и сходимость метода последовательных | улучшений | 70 | § 6. Некоторые реализации метода последовательных улучшений | 72 | | Г л а в а 3. Транспортная задача | 95 | | § 1. Основные определения теории графов | 95 | § 2. Способы задания графа | 97 | § 3. Связность | 100 | § 4. Деревья | 106 | § 5. Постановка транспортной задачи | 109 | § 6. Решение систем с матрицей инциденций | 112 | § 7. Метод потенциалов | 115 | § 8. Алгоритмическая реализация метода потенциалов | 124 | § 9. Варианты транспортной задачи | 137 | | Г л а в а 4. Задачи, родственные транспортной | 148 | | § 1. Упорядочения | 148 | § 2. Матрица кратчайших расстояний | 151 | § 3. Дерево кратчайших путей | 155 | § 4. Критический путь | 163 | § 5. Кратчайшее дерево | 173 | § 6. Максимальный поток через сеть | 180 | § 7. Распределение ресурсов в сетевом графике | 185 | § 8. Покрытие графа путями | 189 | § 9. Паросочетания в простых графах | 192 | § 10. Венгерский метод для задачи о назначениях | 195 | § 11. Матрицы из нулей и единиц | 202 | | Г л а в а 5. Многоэкстремальные задачи на графах | 206 | | § 1. Характеристические числа графа | 206 | § 2. Эйлеровы и гамильтоновы пути и циклы | 208 | § 3. Метод ветвей и границ | 211 | § 4. Размыкание контуров в графе | 224 | § 5. Кратчайшее частичное дерево | 227 | § 6. Задача об оптимальном раскрое | 228 | § 7. Задачи с бивалентными переменными | 231 | § 8. Задача размещения производства | 243 | § 9. Выбор наилучшего разбиения | 247 | | Г л а в а 6. Рекуррентные методы (модели динамического | программирования) | 252 | | § 1. Линейная задача раскроя | 252 | § 2. Детерминированная задача управления запасами | 259 | § 3. Общая схема динамического программирования. Детерминированный | случай | 263 | § 4. Достаточные условия разрешимости уравнения Беллмана | 268 | § 5. Асимптотическое поведение последовательных приближений | 272 | § 6. Задача замены оборудования | 276 | § 7. Задачи оптимального резервирования и надёжности | 278 | § 8. Поиск неисправности | 282 | § 9. Плоская задача раскроя | 287 | § 10. Связь динамического программирования и улучшенного перебора | 293 | § 11. Схема исключения Бертеле-Бриоши | 295 | | Г л а в а 7. Марковские процессы решения | 299 | | § 1. Некоторые сведения о марковских цепях | 299 | § 2. Марковские цепи и потенциалы | 308 | § 3. Пример управляемого случайного процесса: стохастическая задача | управления запасами | 312 | § 4. Марковские и полумарковские процессы решения | 315 | § 5. Функциональные уравнения и рекуррентные соотношения Беллмана | для марковских процессов решения | 319 | § 6. Асимптотика рекуррентных соотношений | 325 | § 7. Методы нахождения оптимальной стационарной политики | 330 | | Библиографические указания | 334 | Литература | 340 | Предметный указатель | 350 |
|
Книги на ту же тему- Динамические задачи дискретной оптимизации, Рихтер К., 1985
- Геометрическое программирование, Даффин Р., Питерсон Э., Зенер К., 1972
- Оптимальные решения в экономике, Канторович Л. В., Горстко А. Б., 1972
- Оптимальные решения, Ланге О., 1967
- Линейное программирование: Пособие для экономистов, Габр Я., 1960
- Линейное программирование, Ашманов С. А., 1981
- Введение в теорию линейного и выпуклого программирования, Еремин И. И., Астафьев Н. Н., 1976
- Элементы динамического программирования, Вентцель Е. С., 1964
- Комбинаторные методы дискретной математики, Сачков В. Н., 1977
- Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
- Транспортные узлы, Скалов К. Ю., ред., 1966
- Управление запасами, Рыжиков Ю. И., 1969
- Графы, сети и алгоритмы, Свами М., Тхуласираман К., 1984
- Эйлеровы графы и смежные вопросы, Фляйшнер Г., 2002
- Графы и их применение, Оре О., 1965
- Дискретная математика для программистов, Хаггарти Р., 2004
|
|
|