Прикладные задачи оптимизации. Модели, методы, алгоритмы

Серия «Библиотека профессионала»
В. И. Струченков
Прикладные задачи
оптимизации
Модели, методы, алгоритмы
Москва
СОЛОН-Пресс
Москва
СОЛОН-ПРЕСС
2016
2020

УДК 681.3
ББК 32.97
С 87
Струченков В. И.
2020.
Прикладные задачи оптимизации. Модели, методы, алгоритмы. — М.:
СОЛОН-ПРЕСС, 2016. — 314 с.: ил.
ISBN 978-5-91359-191-3
Эта книга для всех, кто, не имея специального математического образования,
хочет узнать, как применять методы оптимизации для решения практических задач. В ней рассматриваются задачи оптимизации из различных сфер деятельности:
экономика, финансы, техника, проектирование, строительство и др., излагаются
теоретические основы методов оптимизации (линейное, нелинейное и динамическое программирование). В разделе «Динамическое программирование» опровергаются некоторые устоявшиеся стереотипы и умозаключения; для широкого круга
задач предложен новый метод «динамическое программирование на множествах
Парето».
По каждому из трех разделов приводятся контрольные вопросы и задачи, на
большинство из них в приложениях даны ответы и решения. Приводятся сведения
о пяти обучающих компьютерных программах, специально разработанных для изучения методов оптимизации.
Используемый математический аппарат сведен к минимуму и поясняется в тексте, что обеспечивает понимание методов оптимизации при наличии математической подготовки в объеме программы обычного технического вуза, а для понимания основных идей динамического программирования достаточно знаний в объеме
средней школы.
В основу книги положен курс лекций автора в институте Кибернетики Московского Технологического Университета (МИРЭА) и практический опыт разработки
алгоритмов и программ для решения задач большой размерности в рамках САПР.
Программы можно заказать по электронной почте (str1942@mail.ru) или по телефону (495) 930-19-44.
Книга может быть полезна студентам и аспирантам, изучающим методы оптимизации, а также специалистам, сталкивающимся с проблемами поиска оптимальных решений в различных областях деятельности.
По вопросам приобретения обращаться: ООО «ПЛАНЕТА АЛЬЯНС»
Тел: (499) 782-38-89, www.alians-kniga.ru
Сайт издательства «СОЛОН-ПРЕСС»: www.solon-press.ru
E-mail: avtor@solon-press.ru
2020
ISBN 978-5-91359-191-3
© Струченков В. И., 2016
© Макет и обложка «СОЛОН-ПРЕСС», 2016
2020

Введение
Математические методы оптимизации, соответствующие алгоритмы и компьютерные программы можно рассматривать как эффективный элемент наукоемких технологий, разработка которых в
различных областях практики в настоящее время особенно актуальна.
Наибольший эффект в планировании производства, в проектировании различных объектов, в строительстве, в финансово-экономической деятельности и других областях может быть достигнут
при переходе к выработке и принятию оптимальных решений (оптимальных планов, проектов, конструкций, технологий и т. д.)
В настоящее время для этого имеются достаточные вычислительные мощности, так как современные персональные компьютеры, на которых могут быть реализованы алгоритмы оптимизации,
получили широкое распространение. Однако они в основном используются для других целей и область применения методов оптимизации может быть существенно расширена.
Наиболее известными и простыми являются методы линейного
программирования. Они используются в научных исследованиях и
практической деятельности значительно чаще, чем методы нелинейного программирования [15]. Но нелинейное программирование — это бурно развивающийся раздел современной теории оптимизации, который создан практически в последние 30—40 лет.
Сравнительно редкое практическое применение методов нелинейного программирования можно объяснить именно этим обстоятельством (а не отсутствием реальных практических задач), так как
необходимо значительное время для освоения новых теорий широким кругом практиков и для реализации новых методов в конкретных алгоритмах и компьютерных программах. К тому же реализация методов нелинейного программирования для решения задач большой размерности требует мощных компьютеров, которые
в нашей стране получили широкое распространение только в последние 10—15 лет.
Основным препятствием на пути широкого использования в
практической деятельности современных методов оптимизации
является необходимость разработки математических моделей конкретных задач, то есть сведение практической задачи к математической задаче поиска оптимума. Для этого необходимы знания в
3

Введение
соответствующей предметной области, понимание особенностей
практической задачи и вместе с тем нужны знания современных
методов оптимизации. Разработка сложных систем, в которых используются методы оптимизации, например, таких как системы
автоматизированного
проектирования
(САПР),
требует
усилий
различных специалистов и больших затрат времени. Поэтому в
сложных системах компьютеры часто используются для автоматизации вспомогательных операций (вариантные расчеты, визуализация данных и промежуточных результатов и т. д.), но не для выработки оптимальных решений. При решении творческих задач
принятия решений (в проектировании, конструировании, планировании и т. д.) варианты этих решений задает человек, а компьютер в лучшем случае используется как вспомогательное средство
для проверки приемлемости этих вариантов, их сравнения по тем
или иным показателям с выполнением различного рода расчетно-графических операций и оформления документации. В тех областях деятельности, где число возможных вариантов решения
конкретной практической задачи относительно невелико и человек в состоянии при желании и достаточной квалификации путем
перебора вариантов выбрать наилучший из них, нет особой надобности в применении сложных методов оптимизации, так как полный перебор — это самый универсальный и надежный метод оптимизации. Однако при этом должна быть уверенность, что рассмотрены все допустимые в конкретных условиях варианты, а не
только те, «которые видит специалист». В задачах, где число вариантов принятия решения достаточно велико и специалист не в состоянии рассмотреть их все, перебор малого числа интуитивно назначаемых вариантов может привести к пропуску оптимального
решения. В этих случаях наличие математической модели задачи и
использование компьтера для выработки оптимального варианта с
применением алгоритмов и программ оптимизации может быть
более эффективно, несмотря на то, что математическая модель задачи творческого характера, как правило, не отражает «все детали
и тонкости» и получаемое компьютерное решение только формально является оптимальным. Если эта модель отражает главное и
используется обоснованный алгоритм оптимизации, то получаемый вариант должен быть по крайней мере принят во внимание.
В худшем случае он должен рассматриваться как «дружеский совет» специалисту, принимающему решение. Чем качественнее ма4

Введение
тематическая модель, тем более ценным оказывается такой совет
(подсказка).
Еще одним осложняющим обстоятельством в деле практического применения методов оптимизации является то, что в настоящее время методы нелинейного программирования изучаются в
основном будущими математиками, причем в основном в теоретическом плане, а для их практического применения нужны знания
в предметной области. Студенты технических, экономических и
др. вузов, как правило, знакомятся только с методами линейного
программирования.
В большинстве источников методы нелинейного программирования излагаются с опорой на глубокие знания линейной алгебры
и математического анализа и доступны в основном специалистам-математикам. В то же время практическое применение современных методов оптимизации в значительной мере сдерживается именно отсутствием соответствующих знаний у действующих
инженеров, специалистов в прикладных областях.
Данная работа — это попытка преодолеть образовавшийся разрыв путем изложения основных идей, методов и алгоритмов с
привлечением ограниченного числа математических понятий, которые к тому же поясняются в тексте, так что материал должен
быть доступен при наличии математической подготовки в пределах программы технических вузов.
Наибольшую пользу может принести изучение того, как удалось построить математическую модель и применить тот или иной
метод оптимизации для решения конкретной сложной задачи.
Особенно это относится к применению метода динамического
программирования, который в «компьютерную эпоху» получил
широкое применение в самых различных областях практики. Этот
мощный метод оптимизации далеко не универсальный. Известны
безуспешные попытки его применения без должного анализа особенностей конкретной задачи оптимизации. Поэтому при изложении основных идей динамического программирования в книге
основное внимание уделяется принципу оптимальности Р. Беллмана и области применимости его метода. Рассматриваются различные виды целевых функций и систем ограничений, при наличии которых имеются особенности в применении динамического
программирования. Для некоторых известных задач, решаемых с
помощью динамического программирования, приводятся новые,
более эффективные алгоритмы. Это касается прежде всего задач, в
5

Введение
которых множество состояний не задается изначально, например
в виде регулярной сетки, а формируется в процессе поиска решения. При этом возможна не только отбраковка путей, приводящих
в рассматриваемое состояние, но и отбраковка заведомо бесперспективных состояний, что существенно повышает эффективность
метода.
Критически
оцениваются
опыт
применения
динамического
программирования в различных областях практики и некоторые
устоявшиеся суждения на этот счет.
При изложении методов нелинейного программирования вместо строгих доказательств известных в математике теорем, обосновывающих методы оптимизации, излагаются основные идеи каждого метода, соответствующие им алгоритмы и даются расчетные
и графические иллюстрации для задач малой размерности.
Автор не ставил своей целью изложение всех или хотя бы большинства математических методов оптимизации. Цель автора —
оказать помощь в освоении основных идей линейного, нелинейного и динамического программирования, на конкретных практических примерах из различных областей продемонстрировать эти
идеи, соответствующие методы и алгоритмы, а также особенности
их реализации в компьютерных программах.
Этой же цели служат и многочисленные контрольные вопросы
и задачи по каждом разделу. Ответы и решения приведены в приложениях.
Известно, что наибольшие трудности в решении практических
задач вызывает построение адекватных математических моделей,
выбор метода оптимизации и разработка соответствующих алгоритмов и программ решения конкретной задачи. В этой связи в
книге для нескольких практических задач из различных областей
приводятся математические модели, рассматриваются возможности использования различных методов оптимизации, излагаются
алгоритмы и даются сведения о программных реализациях.
Особое внимание уделяется использованию конкретных особенностей модели, что позволяет продемонстрировать на реальных практических задачах как использование этих особенностей
приводит к резкому сокращению объема вычислений и делает реальным решение задач большой размерности (сотни переменных и
тясячи ограничений).
Необходимо отметить, что для широкого круга задач оптимизации имеются стандартные программные средства. Так, задача ли6

Введение
нейного программирования с вычислительной точки зрения не
вызывает трудностей при числе переменных и ограничений в несколько сотен. Нужно просто уметь свести исходную практическую задачу к линейному программированию, то есть построить
математическую модель и далее использовать готовую программу.
Значительно сложнее решение нелинейных задач большой размерности. Использование стандартных алгоритмов и программ без
учета специфических особенностей конкретной задачи в этом случае может оказаться нецелесообразным. Этому вопросу в книге
уделяется особое внимание. На конкретных математических моделях различных прикладных задач показано, как можно использовать их особенности и существенно упростить алгоритмы оптимизации, оставаясь в рамках математически корректных методов.
Аналогично обстоит дело и с применением метода динамического программирования. В соответствующем разделе показано,
как в ряде случаев можно модифицировать математические модели, если они не позволяют применить этот метод. Кроме того,
программная реализация метода с учетом конкретных особенностей задачи позволяет резко сократить время счета. Естественно,
что в этих случаях речь идет не о применении стандартных программ, а о разработке специальных программных средств. В книге
приводятся данные о решении конкретных прикладных задач оптимизации по специально разработанным программам, которые в
дальнейшем были усовершенствованы именно с учетом особенностей задач, что привело к резкому повышению их эффективности.
На основе практического опыта решения прикладных задач оптимизации в книге последовательно проводится вывод о нецелесообразности различного рода «эвристических» поправок к математическим методам оптимизации. Лучше упростить модель задачи,
имея возможность оценить последствия этих упрощений, чем
применять какой-либо «эвристический» алгоритм поиска решения, особенно вместо математически обоснованных алгоритмов.
Принятый в книге порядок изложения материала — от простого к сложному. Вначале на простой задаче демонстрируется основная идея каждого метода, приводятся необходимые графические
иллюстрации на задачах малой размерности, затем даются обобщения и математические формулировки, после чего разбираются
конкретные практические задачи и алгоритмы, рассматриваются
возможности их практической реализации для задач большой раз7

Введение
мерности либо приводятся сведения об уже осуществленных реализациях.
Раздел «Динамическое программирование» можно читать независимо от других. В разделе «Нелинейное программирование» существенно использутся материал предшествующих разделов, в частности, при рассмотрении нелинейных задач с линейной системой
ограничений
используется
материал
раздела
«Линейное
программирование».
8

1. Этапы решения прикладных задач
оптимизации
Первый этап решения сложных задач оптимизации — это содержательная постановка задачи. На этом этапе устанавливается,
какая цель должна быть достигнута и что конкретно должно быть
определено в процессе решения задачи. Например, требуется разработать оптимальный проект некоторого сооружения, оптимальный план производства работ, оптимальное распределение финансовых ресурсов и т. п. Прежде всего должно быть установлено, что
значит «оптимальный». На этот вопрос могут быть разные ответы:
например, оптимальное сооружение — это сооружение с минимальной стоимостью или с максимальным сроком службы и т. д.
В любом случае речь идет об экстремальных значениях одного или
нескольких
количественных
показателей,
по
которым
можно
сравнивать варианты принимаемого решения. Такие показатели
называются критериями оптимальности. Если критерий оптимальности один, то задача называется однокритериальной, в противном случае — многокритериальной. Может оказаться, что достижение экстремального (например, минимального) значения одного критерия автоматически означает достижение экстремального
значения другого. В этом случае достаточно рассматривать только
один из них. Но чаще бывает так, что критерии противоречат друг
другу и оптимизация по каждому из них в отдельности приводит к
разным результатам. К примеру, минимум стоимости и максимум
срока службы, как правило, противоречат друг другу, им соответствуют различные варианты допустимых решений. Стремление достичь сразу нескольких целей, характерное при постановке многокритериальных задач, приводит к противоречию, которое может
быть разрешено или сведением многокритериальной задачи к однокритериальной (посредством достижения некоторого компромисса) или уточнением самого понятия оптимальности так, чтобы
оно было приемлемо и в данном случае.
Укажем два способа сведения многокритериальных задач к однокритериальным.
9

1. Этапы решения прикладных задач оптимизации
1. Ранжирование критериев оптимальности (метод уступок).
Все критерии рассматриваются последовательно в порядке убывания их значимости, то есть важности для лица, принимающего
решение. Получаем последовательность критериев K1, K2, ..., Kn.
Решается задача оптимизации по главному критерию K1, в результате чего определяется его оптимальное значение K1*. Затем назначается величина уступки — u1, то есть максимальное значение
отклонения от K1, которое можно допустить при оптимизации по
следующему по важности критерию K2. Оптимизация по K2 выполняется при дополнительном условии: нельзя отклоняться от K1
более чем на u1. Если по первому критерию задача решалась на минимум, то это дополнительное ограничение имеет вид K1 ≤K1* +
+ u1, а если на максимум — то K1 ≥K1* – u1. Определяется оптимальное значение второго критерия K2* при уступке по первому, назначается уступка по второму критерию u2, вводится еще одно дополнительное ограничение, теперь на отклонение K2 от K2*, и решается задача оптимизации по K3 и т. д.
В этом методе вместо многокритериальной задачи решается несколько однокритериальных задач (по числу критериев), причем
для каждого следующего критерия вводится дополнительное ограничение на величину предыдущего, которое может существенно
осложнить поиск оптимального решения.
2. Свертка критериев.
Вместо нескольких критериев вводится один новый в виде их
взвешенной суммы.
K = v1K1 + v2K2 + ... + vnKn.
Весовые множители характеризуют относительную важность
критериев. Это положительные числа, сумма которых равна единице. Фактически речь снова идет о ранжировании критериев, но с
заданием количественных характеристик важности каждого критерия. Это можно сделать следующим образом. Важность главного
критерия принимаем за единицу (w1 = 1), а для каждого из остальных устанавливаем его относительную важность по сравнению с
главным wi (i = 2, ..., n). Все полученные положительные числа должны быть меньше единицы. Затем каждое из них, в том числе и
важность главного критерия (она равна 1), делим на их сумму и получаем весовые коэффициенты vi (i = 1, 2, ..., n). Можно в качестве
весовых коэффициентов принять и величины wi (i = 2, ..., n), не до10