Математическое программирование

Карманов В.Г.







Математическое программирование










МОСКВА ФИЗМАТЛИТ ®

УДК 519.85
ББК 22.18
     К24


    К а р м а н о в В. Г. Математическое программирование: Учеб. пособие — 6-е изд., испр. — М.: ФИЗМАТЛИТ, 2008. — 264 с. — ISBN 978-5-9221-0983-3.
    Рассматривается широкий круг вопросов, связанных с математическим программированием. Изложены теоретические основы задач линейного, выпуклого и нелинейного программирования и построения численных методов для их решения.
    По сравнению с изданием 1986 г. в книгу включены результаты, связанные с исследованиями в области численных методов оптимизации и их применением к решению экстремальных задач, в том числе задач вырожденного типа.
    Для студентов высших учебных заведений.



































ISBN 978-5-9221-0983-3


(О ФИЗМАТЛИТ, 2008
(О В. Г. Карманов, 2008

                ПРЕДИСЛОВИЕ





   Эта книга содержит основные положения теории математического программирования и численные методы решения соответствующих экстремальных задач.
   Книга написана на основе лекций, которые автор читал в течение ряда лет на механико-математическом факультете и на факультете вычислительной математики и кибернетики Московского государственного университета им. М.В. Ломоносова.
   Естественно, что в курсе, предназначенном для первого знакомства с предметом, представлены лишь основные численные методы. В связи с этим настоящая книга не может служить справочником, в котором читатель рассчитывает найти тот самый алгоритм, который ему необходим для решения возникшей перед ним реальной задачи оптимизации.
   Глава 1 посвящена предмету математического программирования, его месту в науке об исследовании операций, примерам задач технико-экономического содержания, математическими моделями которых являются задачи математического программирования.
   В главе 2 излагается математический аппарат, на который опираются последующие главы книги.
   В главе 3 основное место отводится условиям оптимальности — необходимым условиям локального минимума в задачах нелинейного программирования, необходимым и достаточным условиям разрешимости задач выпуклого программирования.
   Глава 4 — теория линейного программирования.
   Основные методы решения задач линейного программирования изложены в главе 5.
   Получивший широкое распространение метод штрафных функций рассмотрен в главе 6.
   Важному понятию устойчивости задач математического программирования посвящена глава 7. Здесь изложен метод регуляризации для решения неустойчивых экстремальных задач.
   Многократное решение задач одномерной минимизации — непременный этап большинства численных методов математического программирования, в связи с чем и появилась глава 8.

Предисловие

   На первый взгляд методы решения задач безусловной оптимизации относятся к «численному анализу», однако эти методы стали неотъемлемой частью математического программирования. Так, экстремальные задачи с ограничениями (условно-экстремальные задачи) методом штрафных функций сводятся к задачам безусловной оптимизации, то же самое относится и к методу регуляризации. Кроме того, идеи многих методов решения условно-экстремальных задач существенно базируются на методах безусловной оптимизации, которым посвящена глава 9. Весьма существенный раздел этой главы посвящен стабилизирующим свойствам методов градиентного типа, позволяющим находить нормальное решение некорректных задач, не прибегая к процедуре регуляризации. Этот раздел дополняют исследования, изложенные в главе 7.
   Глава 10 посвящена методам решения экстремальных задач с ограничениями: методам проекции градиента, условного градиента, методу возможных направлений и методам случайного спуска.
   Внимание многих специалистов привлечено к методам решения задач математического программирования, основанным на построении модифицированных функций Лагранжа. Эти вопросы рассмотрены в главе 11.
   Основное внимание при исследовании методов, излагаемых в настоящей книге, уделяется вопросам сходимости и устойчивости, а также априорным оценкам скорости сходимости — одной из существенных характеристик качества методов.
   Относительно численных методов следует сделать одно замечание: при решении реальной задачи самый неудачный, на первый взгляд, метод может оказаться весьма эффективным; в связи с этим автор воздержался от заманчивой перспективы привести некоторые сравнительные характеристики методов, выходящие за рамки оценок скорости сходимости.
   При работе над книгой большую помощь автору оказывали сотрудники ВЦ РАН В.А. Березнев, О.А. Брежнева, А.Ф. Измайлов и А.А. Третьяков, совместную многолетнюю работу с которыми автору трудно переоценить.

В. Г. Карманов

ГЛАВА 1





                ВВЕДЕНИЕ




        1.1. Предмет математического программирования

   1.1.1.   Содержание предмета. Содержание математического программирования составляют теория и методы решения задач о нахождении экстремумов функций на множествах, определяемых линейными и нелинейными ограничениями (равенствами и неравенствами). Математическое программирование является одним из разделов науки об исследовании операций.
   1.1.2.   Области применения. Задачи математического программирования находят применение в различных областях человеческой деятельности, где необходим выбор одного из возможных образов действий (программ действий), например при решении проблем управления и планирования производственных процессов, в проектировании и перспективном планировании, в военном деле и т. д.
   Значительное число задач, возникающих в обществе, связано с управляемыми явлениями, т. е. с явлениями, регулируемыми на основе сознательно принимаемых решений. При том ограниченном объеме информации, который был доступен на ранних этапах развития общества, принималось оптимальное в некотором смысле решение на основании интуиции и опыта, а затем, с возрастанием объема информации об изучаемом явлении,— с помощью ряда прямых расчетов. Так происходило, например, создание календарных планов работы промышленных предприятий.
   Совершенно иная картина возникает на современном промышленном предприятии с многосерийным и многономенклатурным производством, когда объем входной информации столь велик, что его обработка с целью принятия определенного решения невозможна без применения компьютеров. Еще большие трудности возникают в связи с задачей о принятии наилучшего решения.
   1.1.3.   Принятие решений. Проблема принятия решений в исследовании операций неразрывно связана с процессом моделирования.
   Под понятием, обозначаемом термином модель, понимают способ отражать (в том числе и изображать) основное содержание иссле

Гл. 1. Введение

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

*)Это название не вполне удачно, но оно уже вошло в обиход. Заметим, что иногда точную модель называют идеальной (в смысле идеализированной). Но мы будем придерживаться устоявшегося названия.

1.1. Предмет математического программирования

7

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

   Четвертый этап — сопоставление результатов вычислений, полученных на третьем этапе, с моделируемым объектом, т. е. экспертная проверка результатов (критерий практики). Таким образом, на этом этапе устанавливается степень адекватности модели и моделируемого объекта в пределах точности исходной информации.
   Здесь возможны два случая.
   1-й случай. Если результаты сопоставления неудовлетворительны (обычная ситуация на начальной стадии процесса моделирования), то переходят ко второму циклу процесса: уточняется входная информация о моделируемом объекте и в случае необходимости уточняется постановка задачи (первый этап), уточняется или строится заново математическая модель (второй этап), решается соот

Гл. 1. Введение

ветствующая математическая задача (третий этап) и, наконец, снова проводится сопоставление (четвертый этап).
   2-й случай. Если результаты сопоставления удовлетворительны, то модель принимается. Когда речь идет о неоднократном использовании на практике результатов вычислений, возникает задача подготовки модели к эксплуатации. Предположим, например, что целью моделирования является создание календарных планов производственной деятельности предприятия. Тогда эксплуатация модели включает в себя сбор и обработку информации, ввод обработанной информации в компьютер, расчеты на основе разработанных программ календарных планов и, наконец, выдачу результатов вычислений (в удобном для пользователей виде) для их использования в сфере производственной деятельности.
   Подготовка модели к эксплуатации предусматривает разработку специального математического обеспечения, без которого невозможно практическое использование модели: должна быть создана гибкая система программ, обеспечивающая пользователям удобный контакт с компьютером и не требующая при ее эксплуатации высокой математической квалификации пользователей.
   В то же время математическое обеспечение (впрочем, так же, как и сама модель) должно допускать модернизацию в связи с новыми требованиями, которые жизнь постоянно предъявляет к производству. Подчеркнем, что именно модернизацию, а не создание каждый раз новой системы программ. Только при этих условиях возможно регулярное использование математических моделей в процессе управления.



        1.2. Еще раз о моделях

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

1.3. Вопросы классификации и специфики

9

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



        1.3. Вопросы классификации и специфики

   1.3.1.   Направления. В математическом программировании можно выделить два направления. К первому, уже вполне сложившемуся направлению — собственно математическому программированию — относятся детерминированные задачи, когда вся исходная информация является полностью определенной.
   Ко второму направлению — так называемому стохастическому программированию — относятся задачи, в которых исходная информация содержит элементы неопределенности либо когда некоторые параметры задачи носят случайный характер с известными вероятностными характеристиками. Так, планирование производственной деятельности зачастую производится в условиях неполной информации о реальной ситуации, в которой будет выполняться план. Или, скажем, когда экстремальная задача моделирует работу автоматических устройств, которая сопровождается случайными помехами. Заметим, что одна из основных трудностей стохастического программирования состоит в самой постановке задач главным образом из-за сложности анализа исходной информации.
   1.3.2.   Основные разделы. Традиционно в математическом программировании выделяют следующие основные разделы.

Гл. 1. Введение

   Линейное программирование-, целевая функция линейна, а множество, на котором ищется экстремум целевой функции, задается системой линейных равенств и неравенств. В свою очередь в линейном программировании существуют классы задач, структура которых позволяет создать специальные методы их решения, выгодно отличающиеся от методов решения задач общего характера. Так в линейном программировании появился раздел транспортных задач.
   Нелинейное программирование: нелинейны целевая функция и ограничения. Нелинейное программирование принято подразделять следующим образом.
   Выпуклое программирование: когда выпукла целевая функция (если рассматривается задача ее минимизации) и выпукло множество, на котором решается экстремальная задача.
   Квадратичное программирование: когда целевая функция квадратична, а ограничения — линейные равенства и неравенства.
   Многоэкстремальные задачи: здесь обычно выделяют специализированные классы задач, часто встречающихся в приложениях, например, задачи о минимизации на выпуклом множестве вогнутых функций.
   Важным разделом математического программирования является целочисленное программирование — когда на переменные накладываются условия целочисленности.
   1.3.3.    Специфика. В чем состоит специфика задач математического программирования?
   Во-первых, к задачам математического программирования неприменимы, как правило, методы классического анализа для отыскания условных экстремумов, так как даже в наиболее простых задачах — линейных — экстремум достигается в угловых точках границы множества условий, т. е. в точках, где нарушается дифференцируемость. И наиболее сильный метод решения экстремальных задач в классическом анализе — метод множителей Лагранжа — разработан для случая, когда множество условий задается системой уравнений, а не системой неравенств.
   Другой специфической особенностью является то, что в практических задачах число переменных и ограничений столь велико, что если просто перебирать все точки, «подозреваемые в экстремальности», например, все угловые точки множества условий, то никакая современная вычислительная система будет не в состоянии справиться с этой задачей в мало-мальски разумные сроки.
   В связи со сказанным целью математического программирования является создание, где это возможно, аналитических методов определения решения, а при отсутствии таких методов — создание эффективных вычислительных способов получения приближенного решения.