URSS.ru Магазин научной книги
Обложка Ковалев М.М. Дискретная оптимизация: Целочисленное программирование Обложка Ковалев М.М. Дискретная оптимизация: Целочисленное программирование
Id: 294168
629 р.

Дискретная оптимизация:
Целочисленное программирование. Изд. стереотип.

2023. 192 с.
Типографская бумага
  • Мягкая обложка

Аннотация

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


Оглавление
top
Предисловие
Введение
 § 1.Предмет дискретной оптимизации
 § 2.Примеры задач дискретной оптимизации
 Комментарии
 Литература
Глава первая. Диофантово программирование
 § 1.Разрешимость линейных диофантовых уравнений
 § 2.Алгоритм Эрмита решения систем диофантовых уравнений
 Комментарии
 Упражнения
 Литература
Глава вторая. Задача о рюкзаке и ее обобщения
 § 1.Сведение задач дискретной оптимизации к задаче о рюкзаке
 § 2.Методы решения линейной задачи о рюкзаке
 § 3.Задача о рюкзаке на абелевой группе
 § 4.Теоретико-групповой (асимптотический) подход
 § 5.Методы решения нелинейной задачи о рюкзаке
 Комментарии
 Упражнения
 Литература
Глава третья. Целочисленные многогранные множества
 § 1.Условия целочнсленности
 § 2.Почти целочисленные многогранники
 § 3.О числе вершин у целочисленных многогранников
 Комментарии
 Упражнения
 Литература
Глава четвертая. Методы последовательного анализа вариантов
 § 1.Общая схема методов
 § 2.Примеры применения метода последовательного анализа решений
 § 3.Метод последовательного анализа допустимых решений
 Комментарии
 Упражнения
 Литература
Глава пятая.Методы построения последовательности решений
 § 1.Общая схема методов
 § 2.Метод ветвлений-элиминаций и его приложения
 § 3.Метод упорядочения множеств уровня
 § 4.Задачи дискретной оптимизации на крайних точках
 Комментарии
 Упражнения
 Литература
Глава шестая. Методы ветвей и границ
 § 1.Общая схема методов
 § 2.Алгоритм ветвей и границ для линейных задач ЦП
 § 3.Алгоритм ветвей и границ для нелинейных задач ЦП
 Комментарии
 Упражнения
 Литература
Глава седьмая. Приближенные методы
 § 1.Методы локальной оптимизации
 § 2.Методы случайного поиска
 Комментарии
 Упражнения
 Литература
Глава восьмая. Выпуклое симметрическое программирование
 § 1.Постановка и примеры задач
 § 2.Неравенство Шура–Мирского
 § 3.Многоэкстремальная транспортная задача ВСП
 § 4.Целочисленная транспортная задача ВСП
 Комментарии
 Упражнения
 Литература

Предисловие
top
...Существуют области, в которых математика добилась таких существенных результатов, что нельзя ждать тысячи лет, пока ими заинтересуются. Такой областью является целочисленная оптимизация, которая в настоящее время служит основным математическим аппаратом исследования операций.
Т.Саати

Данная книга составлена на основе курса лекций, которые автор читал в 1972–1975 гг. студентам IV курса факультета прикладной математики Белорусского государственного университета им.В.И.Ленина. Материал рассчитан на один семестр при условии, что некоторые вопросы будут вынесены на практические занятия.

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

Широкое применение экономико-математических методов в целях совершенствования управления и планирования экономики стимулировало исследования в области математического (оптимального) программирования. Среди оптимизационных задач, возникающих в различных областях науки, техники и производства, дискретные задачи занимают все более заметное место. Это обусловило стремительный рост числа работ, посвященных теории и методам дискретной оптимизации. Собственно как научная дисциплина дискретная оптимизация (дискретное программирование) сформировалась в последние 5–10 лет, а со времени появления первых публикаций прошло 20 лет. К настоящему времени библиография по дискретной оптимизации и смежным вопросам насчитывает около 2000 наименований. Вполне понятно, что данная книга не претендует на изложение всех результатов. Многие вопросы, не раскрытые в основном тексте, рассмотрены в упражнениях. Примечания в конце каждой главы содержат краткий комментарий по истории вопроса и ссылки на литературу, знакомство с которой поможет глубже изучить предмет (из иностранных работ указаны только доступные советскому читателю).

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

Несколько технических замечаний. Для простоты записи не делаются различия между вектором-столбцом и вектором-строкой: если вектор умножается справа на матрицу, он считается столбцом, если слева – строкой. Равенства и неравенства между векторами понимаются в покоординатном смысле. Векторы и матрицы выделены полужирным шрифтом.

Все замечания и пожелания автор просит направлять по адресу: 220080, Минск-80, Белгосуниверситет, факультет прикладной математики, Ковалеву М.М.


Об авторе
top
photoКовалев Михаил Михайлович
Доктор физико-математических наук (1993), профессор (1994). В 1969 г. окончил Белорусский государственный университет (БГУ), в 1973 г. — аспирантуру этого вуза и уже 50 лет работает в БГУ, из них 20 лет — деканом экономического факультета. Заслуженный деятель науки Республики Беларусь (2001).

Автор более 600 научных работ в области математической экономики, дискретной оптимизации, системного анализа, среди которых 25 монографий, в том числе изданных в Кембридже, Берлине и Москве. С 1993 по 1994 гг. — советник Председателя Верховного Совета.