Книга посвящена новым направлениям в целочисленном программировании и теории потоков в сетях. Ее автор - известный специалист в области математического программирования.

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

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

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

Сборник содержит большой фактический материал, отражающий как современные результаты в комбинаторной математике, так и многочисленные ее применения. Рассматриваются задачи систем управления, многие задачи из биологии, физики и техники. Для решения этих проблем применяются новые методы комбинаторного анализа. Сборник отличается высоким научным уровнем, о чем свидетельствует состав авторов: в их числе такие известные ученые, как Р. Калаба, М. Холл и др. Книга представляет большой интерес для широкого круга читателей. Она будет полезна как математикам, так и экономистам, биологам, инженерам и т. д. Ее также можно рекомендовать аспирантам и студентам соответствующих специальностей.

В книге изложены основные положения теории дискретной оптимизации (разрешимость, агрегация и приведение к каноническому виду систем уравнений в целых числах, групповой подход к задачам целочисленной оптимизации, условия целочисленности многогранных множеств). Описаны методы последовательного анализа вариантов, динамического программирования, ветвей и границ, приближённые. Рассмотрены модели задач покрытия, стандартизации, размещения производства, о рюкзаке и др. Отдельная глава посвящена задачам выпуклого симметрического программирования. Предназначена для преподавателей, аспирантов и студентов университетов, технических и экономических вузов. Может быть использована также разработчиками АСУ.

  Текст у форматі PDF 3.50 Мб

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