Имя материала: Исследование систем управления

Автор: А. С. Малин

6.7  синтез систем управления методами математического программирования

 

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

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

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

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

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

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

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

 

Сущность и содержание математического

программирования

 

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

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

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

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

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

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

 

 

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

 

                                                               ,

 

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

 

                                                                         

 

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

 

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

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

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

 

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

программирования

 

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

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

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

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

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

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

 

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

программирования

 

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

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

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

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

Основным методом решения задач линейного программирования является симплекс-метод и его модификации, ориентированные на особенности решаемых задач (см. [6.9; 6.55; 6.57]).

 

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

программирования

 

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

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

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

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

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

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

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

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

 

Методы решения задач дискретного

(целочисленного) программирования

 

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

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

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

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

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

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

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

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

 

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

 

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

Динамическое программирование особенно эффективно для задач, условия которых позволяют составить сетевой график перехода от этапа к этапу, где узлы сети будут соответствовать различным значениям переменных, а дуги — допустимым вариантам решения (см. [6.51]).

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

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

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

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

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

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

Различают прямые и обратные методы оптимизации. Они отличаются ДРУГ от друга различным представлением переменной и видом рекуррентных соотношений (см. [6.51]).

 

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

 

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

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

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

 

Страница: | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | 46 | 47 | 48 |