В книге излагаются теория и численные методы решения важных классов экстремальных задач: общей задачи линейного программирования, транспортной задачи и задач, ей родственных, комбинаторных задач на графах, ряда дискретных задач динамического программирования.

Изложение численных методов сопровождается разбором алгоритмов, записанных на алгоритмических языках алгол-60 и алгол-68; при этом особое внимание уделено вопросам представления данных при эффективной организации вычислительного процесса.

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

Илл. 73, табл. 37, библ. 233 назв.

В этой книге излагаются в различных аспектах — от теоретического исследования до программы — методы решения экстремальных задач, главным образом дискретных.

Серьёзные экстремальные задачи решаются на вычислительных машинах, и это обстоятельство, несомненно, должно влиять на разработку, изучение и изложение методов решения экстремальных задач. Речь должна идти об эффективной организации вычислительного процесса, при разработке которой следует учитывать многие «технические» и кажущиеся несущественными детали — структуру вычислительной машины, формы представления данных, особенности используемых алгоритмических языков и соответствие их грамматических конструкций машинным возможностям.

Имеется широкий круг практически важных задач, в которых «вычислительная» в традиционном понимании часть действий оказывается очень скромной, и основные сложности лежат в логической структуре алгоритма и в вопросах представления исходной и вспомогательной информации. В таких задачах (а размеры и время счёта в них часто бывают значительными) обычно особенно существенно правильно организовать вычисления.

Цель этой книги — показать в действии некоторые способы организации вычислений, используемые в современных методах решения экстремальных задач. Однако нельзя достичь хорошего понимания этих вопросов, если формализация задачи отделена от выбора метода решения, метод решения — от возможностей алгоритмического языка, запись алгоритма — от понимания особенностей вычислительной машины и класса решаемых задач.

Очевидно, что задача влияет на метод, метод на алгоритм, алгоритм на ход вычислений. Важно отметить, что хороший алгоритм должен учитывать специфику вычислительного процесса, хороший метод вычислений — конструкции алгоритмического языка, хорошая постановка задачи — понятия, характерные для предполагаемого численного метода.

Таким образом, деление изложения на «теоретическую», «алгоритмическую» и «чисто программистскую» части представляется не только неестественным, но даже и вредным, и было сделано всё возможное, чтобы соединить эти части в единое целое и по возможности облегчить переходы. С этой целью была выбрана система обозначений, в которой такие переходы не вызывают затруднений. Для демонстрации готовых алгоритмов и отдельных конструкций используются два языка: алгол-60 и алгол-68, и такой выбор требует некоторых пояснений…

Хотя основной нашей целью являются дискретные экстремальные задачи, линейное программирование может рассматриваться как естественное начало. Поэтому в гл. 2 в лаконичной форме приведены основные факты теории линейного программирования, постановки задач, метод последовательного улучшения допустимого базисного решения и различные подходы к его вычислительной реализации.

В гл. 3 вводятся определения теории графов, которые затем интенсивно используются во всём дальнейшем изложении, после чего начинается изучение задач, связанных с транспортными потоками. Эти задачи интересны не только своими непосредственными практическими приложениями, но и неожиданными и интересными связями с различными разделами математики, в частности с комбинаторикой. Эти комбинаторные следствия из теории потоков и родственные им задачи собраны в гл. 4. Далее, в гл. 5 появляются более сложные комбинаторные задачи, для которых, как правило, нет хороших методов решения и в качестве основного вычислительного средства рассматривается метод улучшенного перебора.

Последние две главы посвящены специфическим задачам (задачам динамического программирования), которые можно решать рекуррентно, сводя задачу к такой же задаче меньших размеров. В гл. 6 рассматриваются комбинаторные задачи этого типа, а в гл. 7 — близкие по духу к материалу остальной книги вероятностные задачи, связанные с управляемыми марковскими цепями (марковские процессы решения).

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

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

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

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

ПРЕДИСЛОВИЕ
Автор

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

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