Отправить другу/подруге по почте ссылку на эту страницуВариант этой страницы для печатиНапишите нам!Карта сайта!Помощь. Как совершить покупку…
московское время19.03.24 11:48:06
На обложку
Норна у источника Судьбы: Сборник статей в честь Елены Александровны…Норна у источника Судьбы: Сборник статей в честь Елены Александровны…
Тайна капитана Немоавторы — Клугер Д.
Информационные измерения языкаавторы — Пиотровский Р. Г.
б у к и н и с т и ч е с к и й   с а й т
Новинки«Лучшие»Доставка и ОплатаМой КнигоПроводО сайте
Книжная Труба   поиск по словам из названия
Авторский каталог
Каталог издательств
Каталог серий
Моя Корзина
Только цены
Рыбалка
Наука и Техника
Математика
Физика
Радиоэлектроника. Электротехника
Инженерное дело
Химия
Геология
Экология
Биология
Зоология
Ботаника
Медицина
Промышленность
Металлургия
Горное дело
Сельское хозяйство
Транспорт
Архитектура. Строительство
Военная мысль
История
Персоны
Археология
Археография
Восток
Политика
Геополитика
Экономика
Реклама. Маркетинг
Философия
Религия
Социология
Психология. Педагогика
Законодательство. Право
Филология. Словари
Этнология
ИТ-книги
O'REILLY
Дизайнеру
Дом, семья, быт
Детям!
Здоровье
Искусство. Культурология
Синематограф
Альбомы
Литературоведение
Театр
Музыка
КнигоВедение
Литературные памятники
Современные тексты
Худ. литература
NoN Fiction
Природа
Путешествия
Эзотерика
Пурга
Спорт

/Наука и Техника/Математика

Алгоритмы решения экстремальных задач — Романовский И. В.
Алгоритмы решения экстремальных задач
Романовский И. В.
год издания — 1977, кол-во страниц — 352, тираж — 16000, язык — русский, тип обложки — твёрд. 7Б тканев., масса книги — 380 гр., издательство — Физматлит
цена: 600.00 рубПоложить эту книгу в корзину
Сохранность книги — хорошая

Формат 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

Книги на ту же тему

  1. Динамические задачи дискретной оптимизации, Рихтер К., 1985
  2. Геометрическое программирование, Даффин Р., Питерсон Э., Зенер К., 1972
  3. Оптимальные решения в экономике, Канторович Л. В., Горстко А. Б., 1972
  4. Оптимальные решения, Ланге О., 1967
  5. Линейное программирование: Пособие для экономистов, Габр Я., 1960
  6. Линейное программирование, Ашманов С. А., 1981
  7. Введение в теорию линейного и выпуклого программирования, Еремин И. И., Астафьев Н. Н., 1976
  8. Элементы динамического программирования, Вентцель Е. С., 1964
  9. Комбинаторные методы дискретной математики, Сачков В. Н., 1977
  10. Комбинаторные задачи и (0, 1)-матрицы, Тараканов В. Е., 1985
  11. Транспортные узлы, Скалов К. Ю., ред., 1966
  12. Управление запасами, Рыжиков Ю. И., 1969
  13. Графы, сети и алгоритмы, Свами М., Тхуласираман К., 1984
  14. Эйлеровы графы и смежные вопросы, Фляйшнер Г., 2002
  15. Графы и их применение, Оре О., 1965
  16. Дискретная математика для программистов, Хаггарти Р., 2004

Напишите нам!© 1913—2013
КнигоПровод.Ru
Рейтинг@Mail.ru работаем на движке KINETIX :)
elapsed time 0.022 secработаем на движке KINETIX :)