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

Глава 1 носит вводный характер. Здесь дан сжатый очерк моделей и методов дискретной оптимизации, описаны те классы задач (марковские и немарковские задачи), которые рассматриваются в книге. Следует отметить, что в дальнейшем основное внимание уделяется марковским задачам. Приведено краткое изложение содержания книги, даются рекомендации по изучению материала для разных категорий читателей. Глава 2 посвящена постановкам и классификации динамических задач дискретной оптимизации. Приводится ряд примеров экономического содержания. Автор выделяет такие классы задач, как одномерные, горизонтально сепарабельные и вертикально сепарабельные, рассматривает связи между динамическими и статическими задачами. В гл. 3 рассматриваются важнейшие подходы к решению исследуемых задач. Изучается отношение эквивалентности между оптимизационными задачами. На основе этого общего подхода описываются метод динамической оптимизации, метод неявного перебора и метод кратчайших путей. Глава 4 посвящена решению одномерных задач, которые представляют интерес как сами по себе, так и в связи с решением задач более общего вида. В гл. 5 исследуется решение горизонтально и вертикально сепарабельных задач при помощи неявного перебора, декомпозиции и перехода к двойственной задаче. Глава 6 — единственная глава книги, посвящённая немарковским задачам. Для них описывается метод неявного перебора, который затем уточняется применительно к задаче долгосрочного планирования. В гл. 7 суммированы некоторые выводы, важные при моделировании и численном решении динамических задач. В гл. 8 даны краткие библиографические указания по отдельным главам. Книга содержит список литературы (дополненный при переводе).

Табл. 15. Ил. 6. Библиогр. 76 назв.

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

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

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

Предметом книги тем не менее является не дискретная динамическая оптимизация как таковая. Наша тема более широка: мы описываем целый ряд подходов к решению динамических задач, среди которых динамическая оптимизация занимает вполне определённое место. Здесь невозможно подробно остановиться на всех имеющихся методах решения динамических задач. Например, приближённые методы очерчиваются лишь весьма бегло, хотя в последнее время и привлекают к себе особое внимание.

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

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

Карл-Маркс-Штадт, сентябрь 1982 г.
Кнут Рихтер

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

1. Компьютер и задачи выбора, Журавлёв Ю. И., сост., 1989
2. Алгоритмы решения экстремальных задач, Романовский И. В., 1977
3. Введение в теорию расписаний, Танаев В. С., Шкурба В. В., 1975
4. Оптимальные решения в экономике, Канторович Л. В., Горстко А. Б., 1972
5. Линейное программирование: Пособие для экономистов, Габр Я., 1960