Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

Описание

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

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

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

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

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

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

Содержание

Введение       5

1. Этапы решения прикладных задач оптимизации        9

2. Особенности задач дискретной оптимизации 16

2.1. Отличия непрерывных и дискретных задач оптимизации  16

2.2. Классификация методов решения дискретных задач          20

3. Динамическое программирование        23

3.1. Многоэтапные процессы принятия решений           23

3.2. Принцип оптимальности и уравнение Р. Беллмана 30

3.3. Область применения динамического программирования  36

3.4. Практические задачи, решаемые с применением классического динамического программирования   40

3.4.1. Задача об инвестициях          40

3.4.2. Оптимальное планирование поставок        45

3.4.3. Планирование производства  продукции при переменном спросе        50

3.4.4. Проектирование оптимальных трасс линейных сооружений      52

3.4.5. Аппроксимация плоских кривых     59

4. Динамическое программирование с использованием множеств

Парето           76

4.1. Однокритериальная задача распределения ресурса 76

4.2. Оптимальное использование транспортных средств          81

4.3. Оптимальный выбор поставщиков     95

4.4. Оптимальное планирование реализации возобновляемых ресурсов         96

4.5. Планирование капиталовложений на несколько лет          108

4.6. Задача о защите поверхности. 114

4.7. Двухкритериальные задачи специального вида.      122

4.8. Расчёт оптимальных сроков замены оборудования 128

4.9. Двухпараметрические задачи  132

4.9.1. Задача о загрузке транспортных средств    132

4.9.2. Задача об использовании двух видов сырья           138

5. Комбинированные методы дискретной оптимизации           146

5.1. Метод ветвей и границ 147

5.2. Комбинированный метод оптимального распределения ресурса  149

5.3. Оптимальное управление запасами   166

5.4. Задача оптимального резервирования           175

5.5. Задача выбора оптимальной комплектации 177

Заключение   179

Приложение 1. Обучающая программа «Bellman»          181

Приложение 2. Обучающая компьютерная программа «Pareto»           187

Библиографический список           189