Уважаемые дамы и господа !! Для того, чтобы без "глюков" скачать файлы электронных публикаций, нажмите на подчеркнутую ссылку с файлом ПРАВОЙ кнопкой мыши, выберите команду "Save target as ..." ("Сохранить объект как ...") и сохраните файл электронной публикации на локальный компьютер. Электронные публикации обычно представлены в форматах Adobe PDF и DJVU.
Глава 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 -близкие по духу к материалу остальной книги вероятностные задачи, связанные с управляемыми марковскими цепями (марковские процессы решения).
Читателю, знакомому с литературой, бросится в глаза отсутствие многих традиционных разделов математического программирования. Это естественно - задача предлагаемой книги в том, чтобы пополнить литературу изложением вопросов, которые слабее в ней представлены, а нуждаются в не меньшем внимании. В библиографических указаниях в конце книги приводятся ссылки на "традиционную" литературу.
К сожалению, даже в тех вопросах, которые включены в книгу, изложение может показаться односторонним, и для такого впечатления есть основания. Единство стиля как в теоретических, так и в вычислительных вопросах требовало серьезной переработки каждой используемой работы, часто существенно изменяющей первоначальные идеи ее. По возможности неполнота текста компенсируется библиографическими указаниями.
Эта книга появилась в результате моей преподавательской деятельности на математико-механическом факультете Ленинградского государственного университета. Ее можно использовать как пособие для спецкурсов по методам дискретной оптимизации, читаемых на математических факультетах университетов и технических вузов.
При работе над книгой большую помощь мне оказали заведующий кафедрой исследования операций проф. М. К. Гавурин и сотрудники кафедры и лаборатории исследования операций ЛГУ. Приношу им искреннюю благодарность.
Вы можете использовать скачанные с веб-сайта книги и другие материалы только для личного ознакомления. Авторское право авторов книг и любых электронных приложений к ним (в том числе фото, видео, рукописи, архивы и прочее) не подлежит патентованию и подобным "искусственным" дополнительным мерам защиты авторского права - не патентуют рукописи, фотографии, видеоматериалы, формулы, графики, сводные таблицы, тексты монографий, черновики и оригинальные издания вне зависимости от того, находятся ли они в частных или государственных архивах любой страны. Вне зависимости от того, есть ли у книги или рукописи и автора какие-либо коды или нет, подписаны они или нет, известен автор или нет, является он(а) гражданином Украины или иностранцем - запрещено явным образом присваивать чужое авторское право и ставить чужие ФИО в чужих работах и трудах (в случае неуказанного, неустановленного или сомнительного авторства наиболее предпочтительно использовать анонимность - это корректно, этично и непротивозаконно, так как в этом случае истинные владельцы будут поданы в розыск и объективно установленны в своих правах независимой комиссией).
Сегодня электронный вариант публикации приравнен к печатной бумажной форме распространения информации (требования аналогичны). Наиболее предпочтительными являются международные форматы публикаций PDF и DJVU (они лучше всего защищены от сторонних модификаций - изменения в них могут внести только профессионалы), допускаются и другие общепринятые и широко распространенные форматы электронного представления авторской или смежной информации. Помните, что один человек сам по себе ничего не делает и не решает - у любого автора любого издания есть коллеги, единомышленники, соратники, кураторы, преподаватели, наставники, идейные, политические и научные руководители и вдохновители, предшественники и приемники, завистники и плагиаторы, желающие незаконно "упасть на хвост и поехать", "присоседиться к работе" и "присоединиться". Чем серьезнее ученый и чем более масштабные объективные и фундаментальные работы он(а) реально ведет, тем большее количество мошенников и аферистов желает незаконно "находиться" и "быть рядом" с таким человеком, его деньгами, премиями, подарками и другими объективными поощрениями. Поэтому все подобные аферисты и мошенники, как и их голословные заявления, подлежат строгой проверке на практике как гласными, так и негласными методами государственного, общественного и политического независимого контроля (в том числе судебного и силового).
Вам разрешается использовать электронные публикации и иные материалы только для личного ознакомления. Никаких дополнительных прав и свобод (в том числе авторских и коммерческих прав, в том числе права на коммерческое распространение) получение и обладание электронной и иной публикации и материалов Вам не предоставляет. Вам не дает никаких прав, в т.ч. авторских и смежных прав, личное знакомство с автором и правообладателем, совместное проживание, учеба или работа, семейный и иной статус, совместное хобби и увлечения, посещение одних и тех же мероприятий, встречи, конфликты и даже отсутствие таковых. Вы не имеете право продавать электронные публикации и иные авторские материалы, отчуждать их от владельца и извлекать материальную выгоду от владения электронной и иной формой представления авторской информации. Отчуждение авторского научного и творческого права запрещено вне зависимости от срока давности издания, способа и места его хранения, разрекламированности, известности или неизвестности и даже анонимности автора и соавтора, гражданства, здоровья, болезни и любого другого объективного статуса реального правообладателя. Запрещены фото- и видеомонтажи, врезки и изъятия, компиляция из сторонних источников и другие формы заведомого мошенничества. Запрещено иностранцам без признанной в Украине и документально подтвержденной профессии, без легитимных виз и специальных персонифицированных межгосударственных соглашений занимать рабочие места граждан Украины на территории Украины и во всех предприятиях, которые являются собственностью Украины и ее граждан вне зависимости от места регистарции и дислокации этих предприятий. Запрещено работать без рабочих виз на территории Украины гражданам и подданым стран, с которыми у Украины установлен визовый режим.
Авторское право (особенно научное и творческое) никогда не патентуется, не отчуждается ни при каких обстоятельствах, не продается и не покупается и является неотъемлимым от его создателя при любых обстоятельствах - патентуются только уникальные инженерные и программные разработки, авторские алгоритмы, изобретения и подобные материалы, содержащие более 60% объективно признанных независимой государственной экспертной комиссией авторских инноваций. Незаконным является присвоение себе чужих архивов, черновиков, заметок, аудио, фото и видеоматериалов (даже если вы не знаете их автора или же непосредственно знакомы с создателем и правообладателем, это ничего не решает). Научное и творческое авторское право не отчуждается от автора и создателя и никогда не делегируется третьим лицам (особенно без профессии и неконтрафактных документов) - оно является наиболее строгим авторским правом, неотделимым от своего создателя, и не подлежит передаче, купле и продаже ни при каких обстоятельствах. Оно только может быть передано в возмездное или безвозмездное пользование БЕЗ ПРАВА НА ОТЧУЖДЕНИЕ. Главной особенностью научного и творческого авторского права является его обязательная частичная передача в безвозмездное пользование широким слоям заинтересованного населения - на этом сайте все научные книги бесплаты и свободны для скачивания без паролей, кодов и ограничений (я как владелец этого сайта и интернет-хостинг-провайдеры не несем ответственность за деятельность третьих лиц, возможные сбои и технические нарушения интернет-связи при пользовании сайтами по вине третьих лиц). Никаких искусственных препятствий, ограничений скорости, других "негативов" и препятствий мы не устанавливаем.
Государство Украина имеет достаточную базу для обеспечения научных работ и научных исследований по всем законным направлениям научной деятельности. C 2010 г. в Украине любая наука и научные исследования являются объектами строгой государственной монополии и требуют наличия не только документально признанной в Украине профессии, но и высшего государственного образования, официально признанного в Украине.