Файл: Конспект лекций Санкт Петербург.pdf

Системный анализ и принятие решений Макаров Л.М.
63
Непрерывная функция – функция, обладающая свойством непрерывности в каждой точке х, принадлежащей области допустимых значений.
Виды функций даны на рис. 4.5.
Функция f(x) является монотонной, если для двух произвольных точек х1 и х2 при х1 ≤ х2 вы- полняется одно из следующих неравенств: f(x1) ≤ f(x2) – монотонно возрастающая функция; f(x1) ≥ f(x2) – монотонно убывающая функция.
Функция f(x) является унимодальной на отрезке a < x < b в том случае, если она монотонная по обе стороны от единственной на интервале оптимальной точки х*.
Функция f(x), определенная на множестве S, достигает своего глобального минимума в точке х
Г
в том и только в том случае, если f(x
Г
) ≤ f(x) для всех х ???? S.
Если функция унимодальна, то локальный оптимум автоматически является глобальным. Если функция не является унимодальной, то возможно наличие нескольких оптимумов. Глобальные оптимумы можно определить путем нахождения всех локальных оптимумов и выбора наимень- шего (минимум) или наибольшего (максимум) из них (рис. 4.6).
Для оптимизации функции одной переменной используется множество алгоритмов наиболее часто применяемых методов: правило исключения интервалов, методы полиноминальной

Системный анализ и принятие решений Макаров Л.М.
64 аппроксимации и методы с использованием анализа производных. Все методы одномерной оп- тимизации основаны на предположении, что исследуемая целевая функция в допустимой обла- сти обладает свойством унимодальности, так как для унимодальной функции f(x) сравнение значений f(t) в двух различных точках интервала поиска позволяет определить, в какой из за- данных двумя указанными точками под интервалов точки оптимума отсутствуют.
Рис. 4.6. Локальные и глобальные оптимумы
95
Сущность метода полиноминальной аппроксимации заключается в том, что непрерывную функцию в некотором интервале можно аппроксимировать полиномом достаточно высокого порядка. Следовательно, если функция унимодальна и найден полином, который достаточно точно ее аппроксимирует, то координаты точки оптимума функции можно оценить путем вы- числения координаты точки оптимума полинома.
Методы с использованием анализа производных заключаются в следующем: необходимыми условиями того, что точка х* является точкой локального минимума (максимума) дважды диф- ференцируемой функции f(x) на интервале (a, b), являются следующие отношения:

Системный анализ и принятие решений Макаров Л.М.
65
Условия являются необходимыми, но недостаточными, так как они характерны не только для точек оптимума, но и для то- чек перегиба (рис. 4.7).
Несмотря на то, что безусловная оптимизация функ- ции одной переменной – это наиболее простой тип оп- тимизационных задач, она занимает центральное ме- сто в теории оптимизации как с теоретической, так и с практической точек зрения. Это связано с тем, что задачи однопараметрической оптимизации достаточно часто встречаются в инженер- ной практике и, кроме того, находят свое применение при реализации более сложных итератив- ных процедур многопараметрической оптимизации.
Безусловная многопараметрическая оптимизация Методы безусловной оптимизации функции многих переменных отличаются относительно высоким уровнем развития по сравнению с дру- гими методами нелинейного программирования. К ним относятся методы прямого поиска, ос- нованные на вычислении только значений целевой функции, методы, в которых используются значения первых и вторых производных.
Методы прямого поиска приемлемы лишь для исследования непрерывных циклоидальных функций. Применяются следующие методы прямого поиска:
− эвристические, построенные на интуитивных геометрических представлениях;
− поиск по комплексу;
− по методу Хука−Дживса;
− теоретические, основанные на математических направлениях;
− метод сопряжения направлений Пауэлля.
Особенности методов прямого поиска:
− относительная простота соответствующих вычислительных процедур, которые быстро реали- зуются и легко корректируются;
− не требуют явного выражения целевой функции в аналитическом виде;
− могут требовать более значительных затрат времени по сравнению с методами, основанными на производных.
4.4. Линейное программирование
Задачами линейного программирования называются оптимизационные задачи, в которых огра- ничения представляются в виде равенств или неравенств и целевая функция линейна. Это наиболее часто применяемый метод решения оптимизационных задач, особенно в экономике и управлении.
Имеется целый ряд различных методов линейного программирования; одни являются специали- зированными, другие носят общий характер.
В пособии рассматривается два метода общего назначения: метод графического линейного про- граммирования и симплексный метод. Метод графического линейного программирования нагляден и прост, но ограничен только задачами с двумя переменными. Симплексный метод не

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

Графический метод линейного программирования
Графический метод линейного программирования отображает ограничения в виде графиков и определяет область, которая удовлетворяет всем ограничениям. Эта область называется обла- стью возможных решений. Затем выстраивается целевая функция и определяется оптимальная точка в области возможных решений. Координаты точки могут быть определены непосред- ственно по графику. Если в задаче существует оптимальное решение, то по крайней мере одна из вершин допустимой области представляет оптимальное решение, которое можно найти пу- тем целенаправленного перебора каждого числа ее вершин.
Порядок решения оптимизационной задачи:
1) поставить задачу оптимизации, завершающейся математической моделью оптимизации;
2) построить на графике ограничения;
3) определить область возможных решений;
4) построить на графике целевую функцию;
5) найти оптимальное решение.
Графический метод решения удобен лишь для случая решения задачи оптимизации при двух переменных целевой функции и линейных ограничениях.
Симплексный метод линейного программирования
Симплексный метод линейного программирования применяется для решения оптимизационных задач, содержащих более двух переменных. Симплекс (от лат. simplex – простой) – в матема- тике простейший выпуклый многогранник данного числа измерений. Трехмерный симплекс (n
= 3) – тетраэдр, двухмерный (n = 2) – треугольник, n-мерный симплекс имеет n + 1 вершин.
Хотя симплексный метод и ориентирован на применение при оптимизации экономических, ре- сурсных и транспортных задач, он пригоден также для решения условных линейных техниче- ских задач, в частности задач технической диагностики.
Большинство задач технической диагностики сводится к поиску минимума функции издержек
F(x), связанных с эксплуатацией и ремонтом машин. В качестве переменной х могут быть пара- метры технического состояния (допустимые или предельные значения), погрешность и досто- верность измерения этого параметра, периодичность диагностирования
Приведение задач линейного программирования к стандартной форме
При решении задач линейного программирования симплекс-методом требуется, чтобы задача была представлена в стандартной форме, т.е. все неравенства должны быть представлены ра- венствами, а все отрицательные переменные преобразованы в неотрицательные. На практике задачи линейного программирования чаще не имеют стандартной формы. Часто ограничения имеют вид неравенств. В некоторых задачах не все переменные неотрицательные. Первый этап решения задачи линейного программирования состоит в приведении ее к стандартной форме.
Основные определения можно сформулировать следующим образом:
– допустимое решение представляет собой неотрицательный вектор х, для которого выполняются ограничения Ах = В;
– допустимая область S состоит из всех допустимых решений;
– оптимальным решением называется такой допустимый вектор x0, для которого целевая функ- ция сх0 больше любого другого допустимого решения, т.е. тогда, когда x0 S и cx
0
≥ c x
для вce x x
0
???? S;

Системный анализ и принятие решений Макаров Л.М.
67
– оптимальное значение задачи.
При решении задач линейного программирования число уравнений меньше числа переменных
(m n), т. е. задача имеет бесконечное множество решений. Классическим методом решения систем линейных уравнений является метод Гаусса - Жордана. Основная идея этого метода со- стоит в сведении системы m уравнений с n неизвестными к каноническому виду с помощью элементарных операций над строками:
– умножением любого уравнения системы на положительное или отрицательное число;
– прибавлением к любому уравнению другого уравнения системы, умноженного на положи- тельное или отрицательное число. В результате элементарных преобразований коэффициент при некоторой переменной в одном из уравнений системы сводят к единице, в других уравне- ниях - к нулю. Переменные x1, x2 ,..., xm, входящие с единичными коэффициентами только в одно уравнение системы и с нулевыми – в остальные, называются базисными или зависимыми.
Остальные n – m переменные (xm+1,..., xm) называются небазисными или независимыми пере- менными.
При симплекс-методе анализируется лишь часть всех допустимых базисных решений по следу- ющему алгоритму:
1) выбор начального допустимого базисного решения;
2) переход от начального решения к другому допустимому базисному решению с лучшим зна- чением целевой функции;
3) продолжение поиска допустимых базисных решений, улучшающих значение целевой функ- ции. Если некоторое допустимое базисное решение нельзя улучшить, оно является оптималь- ным. Решение завершается.
4.5. Нелинейное программирование при решении задач оптимизации
Нелинейное программирование применяется при решении задач, в которых нелинейны и (или) целевая функция, и (или) ограничения в виде равенств и неравенств и для которых методы ма- тематического анализа оказываются непригодными. Нелинейное программирование представ- ляет наиболее характерный метод оптимизации при проектировании машин и технологических процессов и служит для выбора наилучшего плана распределения ограниченных материальных, финансовых и трудовых ресурсов.
Метод множителей Лагранжа
Метод множителей Лагранжа применяется в тех случаях, когда целевая функция и ограничения представлены нелинейными функциями нескольких переменных. Одним из методов решения подобных задач является метод множителей Лагранжа, при котором задача с ограничениями преобразуется в элементарную задачу безусловной оптимизации, в которой используются неко- торые неизвестные параметры, называемые множителями Лагранжа.
Развитием метода Лагранжа при нелинейном программировании является метод квадратиче- ского программирования.
Задачи квадратического программирования характеризуются квадратной зависимостью целевой функции и линейной зависимостью ограничений:
Для решения этих задач разработаны методы, основанные на теореме Куна - Таккера, которые представляют собой обобщение метода множителей Лагранжа для определения экстремума при наличии ограничений, представляющих не только равенства, но и неравенства.
Метод последовательной частной оптимизации.