Валерий Струченков: Методы оптимизации. Курс лекций

Предлагаемый читателю текст - это изложение лекций по дисциплине "Методы оптимизации" в Московском институте радиотехники, электроники и автоматики (ныне Российский технологический университет). Основное внимание уделяется методу динамического программирования (ДП), как наиболее простому и доступному для восприятия большинством студентов. Этот метод разработал Р. Беллман в начале 50-ых годов 20 века. Его книга "Динамическое программирование" была издана на русском языке в 1960 году и вызвала эйфорию у многих исследователей. Метод позволял решать задачи, которые в то время казались неразрешимыми. К сожалению, расширительное толкование возможностей метода, как следствие этой эйфории, попало и в учебную литературу. С тех пор и до настоящего времени в вузах для изучения ДП используется написанное в 60-х годах учебное пособие Е.С. Вентцель "Исследование операций: задачи, принципы, методология", в котором ошибочно трактуются возможности применения метода Р. Беллмана как в части свойств целевой функции, так и системы ограничений. Более того, приведенный в этом пособии конкретный алгоритм решения задачи об оптимальной загрузке машины (это известная задача о "рюкзаке") и соответствующий численный пример крайне неудачны, так как требуют больше вычислений, чем при полном переборе вариантов. Это было установлено и опубликовано в журналах РФ и Германии, но упомянутое пособие переиздаётся и в наше время (Кнорус, Юстиция 2018 г.). без всяких комментариев на этот счёт. Поэтому вопрос об области применимости метода Р. Беллмана в лекциях рассматривается подробно.