AMP версия сайта

Электронная библиотека

  • Современные работы
  • Бесплатно скачать книги
  • Высшая алгебра, геометрия
  • Математический анализ, ТФ
  • Дифференциальные уравнения
  • Численные методы алгоритмы
  • Математическая физика
  • Теория чисел и множеств
  • Специальные темы, книги
  • Общая высшая физика
  • Другие популярные издания
  • Программисту веб-дизайнеру

  • Документация - HTML, XML
  • Статьи пресс-релизы обзоры
  • Веб-дизайнеру - JavaScript
  • Другие материалы

  • Авторское право - помощь
  • Полиграфия, печать цвет
  • Библиография, статьи
  • Бесплатная электронная библиотека. Скачать книги 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 -близкие по духу к материалу остальной книги вероятностные задачи, связанные с управляемыми марковскими цепями (марковские процессы решения).

    Читателю, знакомому с литературой, бросится в глаза отсутствие многих традиционных разделов математического программирования. Это естественно - задача предлагаемой книги в том, чтобы пополнить литературу изложением вопросов, которые слабее в ней представлены, а нуждаются в не меньшем внимании. В библиографических указаниях в конце книги приводятся ссылки на "традиционную" литературу.

    К сожалению, даже в тех вопросах, которые включены в книгу, изложение может показаться односторонним, и для такого впечатления есть основания. Единство стиля как в теоретических, так и в вычислительных вопросах требовало серьезной переработки каждой используемой работы, часто существенно изменяющей первоначальные идеи ее. По возможности неполнота текста компенсируется библиографическими указаниями.

    Эта книга появилась в результате моей преподавательской деятельности на математико-механическом факультете Ленинградского государственного университета. Ее можно использовать как пособие для спецкурсов по методам дискретной оптимизации, читаемых на математических факультетах университетов и технических вузов.

    При работе над книгой большую помощь мне оказали заведующий кафедрой исследования операций проф. М. К. Гавурин и сотрудники кафедры и лаборатории исследования операций ЛГУ. Приношу им искреннюю благодарность.

    Примечание. Сохраняйте книги на планшет или смартфон и скачивайте их с Вашего AMP планшета или смартфона на компьютер. Удобное скачивание книг через мобильный планшет или смартфон (в память устройства) и на Ваш компьютер через AMP интерфейс. Быстрый Интернет без излишних тэгов. Материал носит неофициальный характер и приведен для ознакомления. Прямые ссылки на файлы книг запрещены.

    AMP версия сайта
    Мобильная версия

    Сайт для компьютера
    http://www.mat.net.ua