Электронная библиотека
Программисту веб-дизайнеру
Другие материалы
Бесплатная электронная библиотека. Скачать книги DJVU, PDF бесплатно
И.В. Романовский, Алгоритмы решения экстремальных задач
• Бесплатно скачать книгу, объем 3.99 Мб, формат .djvu (Москва, 1977)
Глава 1. Подготовительные сведения
§ 1. Принятые обозначения
§ 2. Описания алгоритмов
§ 3. Представление данных в вычислительной машине
§ 4. Списки
Глава 2. Некоторые общие сведения о линейном программировании
§ 1. Введение
§ 2 Постановка задачи линейного программирования
§ 3. Теория двойственности
§ 4. Базисные решения Метод последовательных улучшений
§ 5. Устранение зацикливания и сходимость метода последовательных улучшений
§ 6. Некоторые реализации метода последовательных улучшений
Глава 3. Транспортная задача
§ 1. Основные определения теории графов
§ 2. Способы задания графа
§ 3. Связность
§ 4. Деревья
§ 5. Постановка транспортной задачи
§ 6. Решение систем с матрицей инциденций
§ 7. Метод потенциалов
§ 8. Алгоритмическая реализация метода потенциалов ...
§ 9. Варианты транспортной задачи
Глава 4. Задачи, родственные транспортной
§ 1. Упорядочения
§ 2. Матрица кратчайших расстояний
§ 3. Дерево кратчайших путей
§ 4. Критический путь
§ 5. Кратчайшее дерево
§ 6. Максимальный поток через сеть
§ 7. Распределение ресурсов в сетевом графике
§ 8. Покрытие графа путями
§ 9. Паросочетания в простых графах
§ 10. Венгерский метод для задачи о назначениях
§ 11. Матрицы из нулей и единиц
Глава 5. Многоэкстремальные задачи на графах
§ 1. Характеристические числа графа
§ 2. Эйлеровы и гамильтоновы пути и циклы
§ 3. Метод петвей и границ
§ 4. Размыкание контуров в графе
§ 5. Кратчайшее частичное дерево
§ 6. Задача об оптимальном раскрое
§ 7. Задачи с бивалентными переменными
§ 8. Задача размещения производства
§ 9. Выбор наилучшего разбиения
Глава 6. Рекуррентные методы (модели динамического программирования)
§ 1. Линейная задача раскроя
§ 2. Детерминированная задача управления запасами
§ 3. Общая схема динамического программирования. Детерминированный случай
§ 4. Достаточные условия разрешимости уравнения Беллмана
§ 5. Асимптотическое поведение последовательных приближений
§ 6. Задача замены оборудования
§ 7. Задачи оптимального резервирования и надежности
§ 8. Поиск неисправности
§ 9. Плоская задача раскроя
§ 10. Связь динамического программирования и улучшенного перебора
§ 11. Схема исключения Вертеле - Бриоши
Глава 7. Марковские процессы решения
§ 1. Некоторые сведения о марковских цепях
§ 2. Марковские цепи и потенциалы
§ 3. Пример управляемого случайного процесса стохастическая задача управления запасами
§ 4. Марковские и полумарковские процессы решения
§ 5. Функциональные уравнения и рекуррентные соотношения Беллмана для марковских процессов решения
§ 6. Асимптотика рекуррентных соотношений
§ 7. Методы нахождения оптимальной стационарной политики
Краткая аннотация книги
В этой книге излагаются в различных аспектах - от теоретического исследования до программы - методы решения экстремальных задач, главным образом дискретных.
Серьезные экстремальные задачи решаются на вычислительных машинах, и это обстоятельство, несомненно, должно влиять на разработку, изучение и изложение методов решения экстремальных задач. Речь должна идти об эффективной организации вычислительного процесса, при разработке которой следует учитывать многие "технические" и кажущиеся несущественными детали - структуру вычислительной машины, формы представления данных, особенности используемых алгоритмических языков и соответствие нх грамматических конструкций машинным возможностям.
Имеется широкий круг практически важных задач, в которых "вычислительная" в традиционном понимании часть действий оказывается очень скромной, и основные сложности лежат в логической структуре алгоритма и в вопросах представления исходной и вспомогательной информации. В таких задачах (а размеры и время счета в них часто бывают значительными) обычно особенно существенно правильно организовать вычисления.
Цель этой книги - показать в действии некоторые способы организации вычислений, используемые в современных методах решения экстремальных задач. Однако нельзя достичь хорошего понимания этих вопросов, если формализация задачи отделена от выбора метода решения, метод решения - от возможностей алгоритмического языка, запись алгоритма - от понимания особенностей вычислительной машины и класса решаемых задач.
Очевидно, что задача влияет на метод, метод на алгоритм, алгоритм на ход вычислений. Важно отметить, что хороший алгоритм должен учитывать специфику вычислительного процесса, хороший метод вычислений - конструкции алгоритмического языка, хорошая постановка задачи - понятия, характерные для предполагаемого численного метода.
Таким образом, деление изложения на "теоретическую", "алгоритмическую" и "чисто программистскую" части представляется не только неестественным, но даже и вредным, и было сделано все возможное, чтобы соединить эти части в единое целое и по возможности облегчить переходы. С этой целью была выбрана система обозначений, в которой такие переходы не вызывают затруднений. Для демонстрации готовых алгоритмов и отдельных конструкций используются два языка: алгол-60 и алгол-68, и такой выбор требует некоторых пояснений.
Языка алгол-60 для поставленных целей недостаточно. Тем не менее записи на языке в книге оставлены с учетом его широкой известности, наличием трансляторов на большинстве вычислительных машин, а также для сопоставления различных форм описания алгоритмов и представления информации.
Некоторые вводные сведения о характерных приемах представления данных и описания алгоритмов излагаются в гл. 1. Здесь же вводится упомянутая система обозначений и, поскольку алгол-68 распространен еще не очень широко, разъясняются некоторые характерные его конструкции.
Хотя основной нашей целью являются дискретные экстремальные задачи, линейное программирование может рассматриваться как естественное начало. Поэтому в гл. 2 в лаконичной форме приведены основные факты теории линейного программирования, постановки задач, метод последовательного улучшения допустимого базисного решения и различные подходы к его вычислительной реализации.
В гл. 3 вводятся определения теории графов, которые затем интенсивно используются во всем дальнейшем изложении, после чего начинается изучение задач, связанных с транспортными потоками. Эти задачи интересны не только своими непосредственными практическими приложениями, но и неожиданными и интересными связями с различными разделами математики, в частности с комбинаторикой. Эти комбинаторные следствия из теории потоков и родственные им задачи собраны в гл. 4. Далее, в гл. 5 появляются более сложные комбинаторные задачи, для которых, как правило, нет хороших методов решения и в качестве основного вычислительного средства рассматривается метод улучшенного перебора.
Последние две главы посвящены специфическим задачам (задачам динамического программирования), которые можно решать рекуррентно, сводя задачу к такой же задаче меньших размеров. В гл. 6 рассматриваются комбинаторные задачи этого тина, а в гл. 7 -близкие по духу к материалу остальной книги вероятностные задачи, связанные с управляемыми марковскими цепями (марковские процессы решения).
Читателю, знакомому с литературой, бросится в глаза отсутствие многих традиционных разделов математического программирования. Это естественно - задача предлагаемой книги в том, чтобы пополнить литературу изложением вопросов, которые слабее в ней представлены, а нуждаются в не меньшем внимании. В библиографических указаниях в конце книги приводятся ссылки на "традиционную" литературу.
К сожалению, даже в тех вопросах, которые включены в книгу, изложение может показаться односторонним, и для такого впечатления есть основания. Единство стиля как в теоретических, так и в вычислительных вопросах требовало серьезной переработки каждой используемой работы, часто существенно изменяющей первоначальные идеи ее. По возможности неполнота текста компенсируется библиографическими указаниями.
Эта книга появилась в результате моей преподавательской деятельности на математико-механическом факультете Ленинградского государственного университета. Ее можно использовать как пособие для спецкурсов по методам дискретной оптимизации, читаемых на математических факультетах университетов и технических вузов.
При работе над книгой большую помощь мне оказали заведующий кафедрой исследования операций проф. М. К. Гавурин и сотрудники кафедры и лаборатории исследования операций ЛГУ. Приношу им искреннюю благодарность.
Примечание. Сохраняйте книги на мобильный телефон и скачивайте их с Вашего телефона на компьютер. Удобное скачивание книг через мобильный телефон (в память телефона) и на Ваш компьютер через мобильный интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.