КнигоПровод.Ru29.03.2024

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

Динамические задачи дискретной оптимизации — Рихтер К.
Динамические задачи дискретной оптимизации
Рихтер К.
год издания — 1985, кол-во страниц — 136, тираж — 8000, язык — русский, тип обложки — бумажн., масса книги — 110 гр., издательство — Радио и связь
КНИГА СНЯТА С ПРОДАЖИ
Сохранность книги — хорошая

Dynamische
Aufgaben
der diskreten
Optimierung
von
Knut RICHTER


AKADEMIE-VERLAG BERLIN
1982

Пер. с нем. С. Л. Печерского

Формат 84x108 1/32. Бумага книжно-журнальная №2. Печать высокая
ключевые слова — дискрет, оптимизац, планирован, марковск, сепарабельн, перебор, кратчайш, двойственн, долгосрочн, запасов, управлен, комбинатор, np-сложн, транспортн, расписан, очеред, целочисленн, np-труд, многопродуктов, градиентн, фортран

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

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

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


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

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

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

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

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

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

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

ОГЛАВЛЕНИЕ

Предисловие редактора перевода5
Предисловие автора к русскому изданию6
Предисловие6
 
1. Введение9
1.1. Модели и методы дискретной оптимизации9
Целочисленные задачи оптимизации. Комбинаторные задачи. Выработка принципов решения. Развитие методов решения. Алгоритмическая реализация. Трудоёмкость и сложность задач. NP-трудные задачи
1.2. Марковские и немарковские динамические задачи15
Описание задач, рассматриваемых в книге. Марковские и немарковские динамические задачи дискретной оптимизации. Основные темы, рассматриваемые в книге
 
2. Динамические задачи дискретной оптимизации19
2.1. Примеры динамических задач20
Модель управления запасами с вогнутыми функциями затрат. Многопродуктовая модель производственного планирования. Модель планирования производства с фиксированными затратами двух видов. Модель долгосрочного планирования. Блочно-угловая структура и структура связи
2.2. Классификация динамических задач26
Марковские и немарковские задачи дискретной оптимизации. Одномерные и многомерные задачи. Горизонтально и вертикально сепарабельные задачи. Леонтьевские задачи. Статические и динамические задачи
 
3. Некоторые принципы решения задач дискретной оптимизации35
3.1. Отношения эквивалентности35
Точечно-множественное отображение. Определение понятия эквивалентности задач. Вспомогательные задачи. Соотношение между (A,B)-эквивалентностью и полиномальной эквивалентностью
3.2. Построение эквивалентных задач39
Обратное отображение. Принцип построения эквивалентной задачи. Некоторые реализации принципа построения. Базисные решения. Не базисные индексы. Задача сепарабельной оптимизации
3.3. Некоторые комбинаторные принципы решения45
Метод дискретной динамической оптимизации. Метод неявного перебора. Метод кратчайшего пути
3.4. Двойственные задачи дискретной оптимизации58
Первый и второй принципы построения двойственчой задачи. Решение двойственных задач. Модель алгоритма генерирования столбцов. Модель алгоритма субградиентного метода
 
4. Решение одномерных задач69
4.1. Дискретизация детерминированных задач управления запасами69
Сведение конкретных задач типа модели управления запасами с вогнутыми функциями затрат к задачам дискретной оптимизации
4.2. Решение некоторых детерминированных задач управления запасами76
Алгоритм динамической оптимизации для решения задач (4.14). Алгоритм решения эквивалентной задачи о кратчайшем пути для задачи (4.14). Алгоритм решения эквивалентной задачи о кратчайшем пути для задач (4.14), (4.15) с положительным спросом. Использование эквивалентной задачи о кратчайшем пути для решения других задач. Программа на языке Фортран
4.3. Более общие одномерные задачи85
Одномерные задачи без определённой структуры. Модифицированная задача (4.14). Задача о ранце
 
5. Решение сепарабельных динамических задач88
5.1. Переход к двойственной задаче и приближённое решение горизонтально сепарабельных задач88
Задача невыпуклой оптимизации. Функция Лагранжа. Формулировка двойственной задачи. Пример решения двойственной задачи. Приближённые методы. Алгоритм субградиентного метода для приближённого решения задачи (2.2). Алгоритм генерирования столбцов для приближённого решения задачи (2.2)
5.2. Неявный перебор для горизонтально сепарабельных задач98
Стратегии перебора. Вычисление границ. Алгоритм неявного перебора для решения задач (2.2), (2.12). Примеры работы алгоритма
5.3. Декомпозиция вертикально сепарабельных задач107
Эквивалентные задачи для вертикально сепарабельных задач. Алгоритм построения упорядоченной последовательности вершин куба W. Алгоритм неявного перебора для решения эквивалентной задачи (5.21). Пример работы алгоритма
 
6. Решение немарковских динамических задач114
6.1. Неявный перебор для немарковских задач115
Модель алгоритма неявного перебора для решения задачи (NM)
6.2. Решение задач долгосрочного планирования118
Рассмотрение задачи долгосрочного планирования развития мощностей предприятия (2.4). Вычисление границ. Вариант выбора управлений Xjt. Алгоритм неявного перебора для решения задачи (2.4)
 
7. Заключительные замечания123
 
8. Путеводитель по литературе124
 
Список литературы127
Дополнительный список литературы129
Предметный указатель130

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

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

© 1913—2013 КнигоПровод.Ruhttp://knigoprovod.ru