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


Струченков В. И.







                ДИСКРЕТНАЯ ОПТИМИЗАЦИЯ




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











Москва СОЛОН-Пресс 2020

УДК 681.3
ББК 32.97 С 87


Струченков В. И.
Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач. — М.: СОЛОН-Пресс, 2020. — 192 с.: ил.

    Эта книга для всех, кто, не имея специального математического образования, хочет узнать, как применять методы оптимизации для решения практических задач. В ней рассматриваются прикладные задачи из различных сфер деятельности, их математические модели и методы решения на основе современной теории оптимизации. Особое внимание к дискретным задачам обусловлено их практической важностью и меньшей изученностью по сравнению с непрерывными задачами.
    Приводятся новые алгоритмы, основанные на комплексном применении динамического программирования и метода ветвей и границ, доведённые до практических реализаций. Их эффективность подтверждается результатами решения задач большой размерности.
    Используемый в книге математический аппарат сведён к минимуму и поясняется в тексте, что обеспечивает понимание методов оптимизации лицами, не имеющими специальной математической подготовки, для которых математика не является профессией.
    В основу книги положен курс лекций, которые автор читал в Институте кибернетики Московского государственного университета информационных технологий, радиотехники и электроники ( МИРЭА), и практический опыт разработки алгоритмов и программных средств для решения задач большой размерности.
    Книга может быть полезна студентам и аспирантам, изучающим методы оптимизации, а также специалистам, сталкивающимся с проблемами поиска оптимальных решений в различных областях деятельности.
    В приложении приводятся сведения об обучающих компьютерных программах, которые могут быть полезны при изучении методов оптимизации. Программы можно заказать по электронной почте str1942@mail.ru..


ISBN 978-5-91359-181-4

© «СОЛОН-Пресс», 2020
© Струченков В.И., 2020

        Содержание

Введение.........................................................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

3

Содержание


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

4

        Введение


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

5

Введение

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

6

Введение

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

7

Введение

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

8

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


  Первый этап решения сложных задач оптимизации - это содержательная постановка задачи. На этом этапе устанавливается какая цель должна быть достигнута и что конкретно должно быть вычислено. Например, требуется разработать оптимальный проект некоторого сооружения, оптимальный план производства работ, оптимальное распределение финансовых ресурсов и т.п. Прежде всего должно быть установлено, что значит оптимальный? На этот вопрос могут быть разные ответы: например, оптимальное сооружение - это сооружение с минимальной стоимостью или с максимальным сроком службы и т.д. В любом случае речь идёт об экстремальных значениях одного или нескольких количественных показателей, по которым можно сравнивать варианты принимаемого решения. Такие показатели называются критериями оптимальности. Если критерий оптимальности один, то задача называется однокритериальной, в противном случае - многокритериальной. Может оказаться, что достижение экстремального значения одного критерия автоматически означает достижение экстремального значения другого. В этом случае достаточно рассматривать только один из них. Но чаще оптимизация по каждому критерию в отдельности приводит к разным результатам. К примеру, минимум стоимости и максимум срока службы, как правило, противоречат друг другу. Стремление достичь сразу нескольких целей, приводит к противоречию, которое может быть разрешено или сведением многокритериальной задачи к однокритериальной или уточнением самого понятия оптимальности.
  Укажем два способа сведения многокритериальных задач к однокритериальным.
1. Ранжирование критериев оптимальности (метод уступок).
  Все критерии рассматриваются последовательно в порядке убывания их значимости, то есть важности для лица принимающего решение. Получаем последовательность критериев Ki,K2,.. .,Kn.
  Далее решается задача оптимизации по главному критерию Ki, в результате чего определяется его оптимальное значение K1*. Затем назначается величина уступки ui>0, то есть максимальное значение отклонения от Ki, которое можно допустить при оптимизации по следующему по важности критерию K2. Оптимизация по K2 выполняется при дополнительном условии: нельзя отклоняться от Ki более, чем на ui. Если по первому критерию задача решалась на минимум, то это дополнительное ограничение имеет вид Ki< K1* +u1, а если на максимум

9

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

- то Ki>Ki* - ui. Определяется оптимальное значение второго критерия K2* при уступке по первому, назначается уступка по второму критерию U2>0, вводится ещё одно дополнительное ограничение, теперь на отклонение K2 от K2*, и решается задача оптимизации по K3 и т.д.
   В этом методе вместо многокритериальной задачи решается несколько однокритериальных задач (по числу критериев), причём для каждого следующего критерия вводится дополнительное ограничение на величину предыдущего, которое может существенно осложнить поиск оптимального решения.
       2. Свёртка критериев.
   Вместо нескольких критериев вводится один в виде их взвешенной суммы. K= V1K1+ V2K2+...+ VnKn.
   Весовые множители vi,V2,..., Vn характеризуют относительную важность критериев. Это положительные числа, сумма которых равна единице. Фактически речь снова идёт о ранжировании критериев, но с заданием количественных характеристик важности каждого из них. Это можно сделать следующим образом. Важность главного критерия принимаем за единицу (wi=1), а для каждого из остальных устанавливаем его относительную важность по сравнению с главным wi (i=2,...,n). Все полученные положительные числа должны быть меньше единицы. Затем каждое из них, в том числе и важность главного критерия (она равна i), делим на их сумму и получаем весовые коэффициенты Vi (i=i,2,...,n). Можно в качестве весовых коэффициентов принять и величины wi (i=2,...,n), не добиваясь равенства единице суммы весов, так как умножение критерия на положительное число не меняет оптимального решения.
   Отметим, что в некоторых задачах можно просто выбрать главный критерий, а по всем остальным задать дополнительные ограничения на соответствующие величины. Например, требуется создать конструкцию с минимальной стоимостью и максимальным сроком службы. Вместо этого решается задача на минимум стоимости при условии, что срок службы не менее заданного.
   Если в конкретной многокритериальной задаче не удаётся использовать ни один из способов её сведения к однокритериальной, то приходится изменить подход к оптимизации, само понятие оптимальности. Один из таких приёмов состоит в оптимизации по Парето [7,9,i8 ].
   Вместо оптимальных предлагается искать так называемые эффективные решения, то есть такие решения, каждое из которых нельзя улучшить ни по одному критерию, не ухудшая ни по одному из остальных критериев. Множество таких решений называется множеством Парето. Как правило, в него входят ре

i0

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

шения, оптимальные по отдельным критериям. Но если при оптимизации по одному критерию получаем не одну, а несколько точек с равными значениями этого частного критерия, то может оказаться, что не все они входят в множество Парето. Такая ситуация возникает, если при переходе от одной такой точки к другой, имеет место улучшение хотя бы по одному критерию без ухудшения по остальным. В множество Парето могут входить точки, не соответствующие оптимуму ни по одному из частных критериев.
  Если численные значения каждого критерия для всех допустимых решений, отложить по соответствующей координатной оси, то получим множество точек так называемого критериального пространства. Если в задаче минимизации по критериям Ki, K;,..., Kn для двух точек этого множества A(Kr,K2³,..., Кпа) и B(Kib,K2b,..., Knb) выполнены неравенства Ка <Kib (i=1,2,...,n) и хотя бы для одного значения i соответствующее неравенство выполнено строго (иначе это совпадающие точки), то точка А (и соответствующее ей решение задачи) называется доминирующей над точкой B, а точка B называется доминируемой. Заметим, что было бы ошибочным определить множество Парето как множество доминирующих точек, как это иногда делается [13 ]. Дело в том, что в множество Парето очевидно не входят доминируемые точки, но из двух точек не обязательно одна доминирующая. Вообще в исходном множестве допустимых решений (соответственно множестве точек критериального пространства) может и не быть доминирующих точек. Поэтому множество Парето- это подмножество недоминируемых (т.е. эффективных) точек исходного множества критериального пространства, то есть недоминируемых допустимых решений. Если два решения по некоторым критериям могут быть равноценны, то нельзя утверждать, что множество Парето - это множество решений, каждое из которых нельзя улучшить сразу по всем критериям. Например, для задачи минимизации по двум критериям для двух решений A и B выполнено Ki³< Kib и K;³= K;b и других допустимых решений нет. Переходя к решению А от решения В, его нельзя улучшить по всем (двум) критериям, но можно улучшить по одному (первому), не ухудшая по остальным (второму), поэтому оно не входит в множество Парето.
  Для графической иллюстрации рассмотрим задачу минимизации по двум критериям Ki и K;. Предположим, что нам известны все допустимые решения, из которых нам предстоит сделать выбор по этим двум критериям и для каждого решения вычислены величины каждого критерия. Геометрически на координатной плоскости с осями Ki и K; все допустимые решения будут представле


ii

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

ны точками (рис.1.1). Как определить какие точки входят в множество Парето? Другими словами, по какому правилу мы можем исключить заведомо не эффективные решения? Очевидно, в это множество из всех допустимых точек попадут только точки A,B,C,D, причём только точки A и D соответствуют мини-мимизации по отдельным критериям. Заметим, что в задаче на минимум точка входит в множество Парето, в том и только в том случае, если в третьем квадранте системы координат, построенной с центром в этой точке, нет других точек.


          К2    *







  Рис. 1.1 Пример построения множества Парето
  При максимизации по двум критериям вместо третьего анализируется первый квадрант. Это правило позволяет из всех допустимых решений после вычисления значений каждого критерия сформировать множество Парето для двухкритериальной задачи. Аналогично можно поступить и при наличии трёх и более критериев. Но реально встречаются прикладные задачи, где такой путь крайне не эффективен, так как требует большого объёма вычислений. B разделе 4.7 рассматриваются двухкритериальные задачи, относящиеся к задачам распределения ресурсов, для которых с использованием их особенностей приводится алгоритм построения множества Парето с помощью динамического программирования.
  На рассматриваемом нами первом этапе построения математической модели, кроме выбора критериев оптимизации, необходимо выявить каким условиям (ограничениям) должно удовлетворять искомое решение. Так, в задачах оптимального планирования, проектирования и др., как правило, необходимо учитывать ограниченность различного вида ресурсов. Задачи без ограничений вообще встречаются довольно редко.
  Второй этап решения задачи состоит в формализации, то есть в её постановке как задачи математической. При этом необходимо прежде всего форма

12