Применение методов математического программирования в оценочной деятельности

Лекция 12. Применение методов математического программирования в оценочной деятельности

Вопросы лекции:

1. Сущность и содержание математического программирования.

2. Общая характеристика методов математического программирования.

3. Методы динамического и стохастического программирования

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

Имеется набор параметров x₁, ..., х_п и функция F(x). Требу­ется определить такую совокупность параметров из множест­ва X, для которой функция F(x) принимает наибольшее или наименьшее значение. Функция F(x) получила название целе­вой функции.

Методы решения задач такого типа в литературе получили наименование методов математического программирования.

Термин «программирование» не связан с составлением программ для ЭВМ, но обусловлен тем, что при решении та­кого рода задач математическими средствами составляется программа действий.

Рекомендуемые материалы

Независимо от конкретной предметной ориентации задачи, решаемые методами математического программирования, с формальной точки зрения сводятся к одной постановке.

При выполнении условий

необходимо найти совокупность параметров (план)

, при котором функция (целевая функ­ция)

принимает наибольшее или наименьшее значение.

Условия    называются   ограничениями задачи. Дополнительно к условиям может быть задано требование целостности всех или нескольких переменных х_j.

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

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

Общая характеристика методов математического программирования

Методы математического программирования относятся к численным методам поиска оптимальных решений, которые позволяют найти решение только для конкретных значений параметров. Такими методами являются методы линейного, нелинейного дискретного, стохастического и динамического программирования.

Если функции эффективности и ограничения линейны, а операция одноэтапная, то можно применить один из методов линейного программирования. Данные методы используют одну и ту же идею: задается некоторое неоптимальное реше­ние (начальный план), а затем оптимальное решение находит­ся путем изменения начального плана в направлении прибли­жения к оптимальному. Линейное программирование является в настоящее время наиболее разработанной ветвью математи­ческого программирования.

При нелинейном характере хотя бы одного компонента ма­тематической модели (целевой функции или ограничений) применяются методы нелинейного программирования. Общих методов этого типа пока не существует, за исключением слу­чая квадратичной зависимости между критерием и парамет­рами при линейных ограничениях.

Некоторые математические модели могут содержать усло­вие дискретности значений параметров (например, по своей физической сущности параметры должны быть только целыми числами). Решение таких задач осуществляется с применением методов дискретного (целочисленного) про­граммирования.

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

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

Методы решения задач линейного программирования

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

Особенности использования. Оптимальному решению все­гда соответствует одна из экстремальных точек пространства решений (это является следствием такого важного свойства задач линейного программирования, как выпуклость про­странства решений).

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

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

 Методы решения задач нелинейного программирования

Область применения. Нелинейное программирование ис­пользуется для решения однокритериальных задач оптимиза­ции с детерминированной целевой функцией при накладывае­мых ограничениях в виде равенств или неравенств. Для дан­ного класса задач снимается условие линейности функций или ограничений.

Особенности использования. Нелинейность целевой функ­ции f(х) требует исследования условий (необходимых и доста­точных) наличия экстремума. Для этого надо уметь получить аналитические выражения по меньшей мере двух производ­ных этой функции.

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

Универсальных алгоритмов решения нелинейных задач не существует из-за большого разнообразия вида нелиней­ности.

Наиболее употребительные методы. Разработанные ныне методы решения задач нелинейного программирования могут быть разделены на ряд больших групп:

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

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

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

Методы решения задач дискретного (целочисленного) программирования

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

Примерами таких задач являются: определение очередно­сти выполнения работ, назначение ресурсов по объектам ис­пользования, выбор маршрута на сети «задача о коммивояже­ре».

Особенности применения. Основной особенностью явля­ется то, что все или некоторые переменные должны прини­мать только целочисленные (дискретные) значения. Обычно это бывает при описании неделимых объектов (людей, ма­шин и т. п.) или при наложении жестких ограничений типа равенств.

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

Наиболее употребительные методы. Различают два класса методов: методы отсечения и комбинаторные методы.

Методы отсечений используются при решении ли­нейных целочисленных задач без булевых переменных. Их идея заключается в ослаблении ограничений (за счет отказа от требований целочисленности) и решения обычной задачи ли­нейного программирования. Затем, если полученное опти­мальное решение не удовлетворяет требованию целочислен­ности, вводят специальные дополнительные требования, тем самым отсекая некоторую область возможных решений, и вновь решают задачу линейного программирования с провер­кой результатов на целочисленность переменных.

Процесс повторяется до выполнения требований по цело­численности. Для решения целочисленных задач используется алгоритм Гомори и алгоритм Дальтона и Ллевелина

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

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

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

Метод особенно эффективен для задач, условия которых позволяют составить сетевой график перехода от этапа к этапу, где узлы сети будут соответствовать различным зна­чениям переменных, а дуги — допустимым вариантам реше­ния.

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

♦        этапы решений (подзадачи, на которые она декомпо­зируется);

♦        управляемые переменные (варианты решений) на каждом этапе;

♦        информацию для решения задачи на каждом этапе;

♦        рекуррентные вычислительные процедуры,  связы­вающие соседние этапы.

Ещё посмотрите лекцию "1 Содержание" по этой теме.

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

Наиболее употребительные методы. Различают прямые и обратные методы оптимизации. Они отличаются друг от друга различным представлением переменной и видом рекуррент­ных соотношений

Методы стохастического программирования

Область применения. Методы используются для задач, в которых все или отдельные параметры описываются с помо­щью случайных величин. Задачи стохастического программи­рования возникают тогда, когда каждое действие приводит к неоднозначному исходу и с каждым решением можно связать числовые параметры целевой функции f_S(X, Θ), s = 0, 1, ..., m. При этом параметры fs(X, Θ) зависят от конкретного решения X и состояния среды Θ. В стохастическом программировании Θ является элементарным событием некоторого вероятност­ного пространства.

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

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