|
Читайте также: |
Одним из методов, которые позволяют свести задачу нелинейного программирования к решению системы уравнений, является метод неопределенных множителей Лагранжа.
Если целевая функция F является линейной, а ограниченным пространством является политоп, то задача является задачей линейного программирования, которая может быть решена с помощью хорошо известных решений линейного программирования.
Если целевая функция является вогнутой (задача максимизации) или выпуклой (задача минимизации) и множеством ограничений служит выпуклая, то задачу называют выпуклой, и в большинстве случаев могут быть использованы общие методы выпуклой оптимизации.
Если целевая функция является отношением вогнутых и выпуклых функций (при максимизации) и ограничения выпуклые, то задача может быть преобразована в задачу выпуклой оптимизации использованием техник дробного программирования.
Существуют несколько методов для решения невыпуклых задач. Один подход заключается в использовании специальных формулировок задач линейного программирования. Другой метод предусматривает использование методов ветвей и границ, где задача делится на подклассы, чтобы быть решенной с выпуклыми (задача минимизации) или линейными аппроксимациями, которые образуют нижнюю границу общей стоимости в пределах раздела. При следующих разделах в определенный момент будет получено фактическое решение, стоимость которого равна лучшей нижней границе, полученной для любого из приближенных решений. Это решение является оптимальным, хотя, возможно, не единственным. Алгоритм можно прекратить на ранней стадии, с уверенностью, что оптимальное решение находится в рамках допустимого отклонения от найденной лучшей точки; такие точки называются ε-оптимальными. Завершение ε-оптимальных точек, как правило, необходимое для обеспечения конечности завершения. Это особенно полезно для больших, сложных задач и задач с неопределенными расходами или значениями, где неопределенность может быть определена из соответствующей оценки надежности.
Дифференцирование и условия регулярности, условия Каруша — Куна — Такера (ККТ) обеспечивают необходимые условия оптимальности решения. При выпуклости, эти условия являются и достаточными.
18. Метод квадратичного программирования.
Последовательное квадратичное программирование — один из наиболее распространённых и эффективных оптимизационных алгоритмов общего назначения, основной идеей которого является последовательное решение задач квадратичного программирования, аппроксимирующих данную задачу оптимизации. Для оптимизационных задач без ограничений алгоритм SQP преобразуется в метод Ньютона поиска точки, в которой градиент целевой функции обращается в ноль. Для решения исходной задачи с ограничениями-равенствами метод SQP преобразуется в специальную реализацию ньютоновских методов решения системы Лагранжа.
Основные сведения
Рассмотрим задачу нелинейного программирования следующего вида:
при ограничениях
Лагранжиан задачи примет следующий вид:
где λ и σ — множители Лагранжа.
На итерации xk основного алгоритма определяются соответствующие направления поиска dk как решение следующей подзадачи квадратичного программирования:
при ограничениях
19. Сепарабельное программирование. Метод кусочно-линейной аппроксимации.
В качестве приближения к нелинейной функции на большом отрезке используется её кусочно-линейная аппроксимация, если разбить отрезок на подинтервалы и построить линейные приближения функции на каждом из подинтервалов. Этот метод применим только к сепарабельным функциям.
Определение.
Функция 
, где 
- N-мерный вектор, называется сепарабельной, если она представляется в виде суммы функций, каждая из которых зависит только от одной из N переменных, т.е.
Кусочно-линейная аппроксимация для сепарабельной непрерывной функции f(x) строится следующим образом. Интервал значений каждой переменной xi разбивается при помощи сетки с Ki узлами. Таким образом, на интервале xi(L) Ј xi Ј xi(R) рассматривается следующая последовательность точек:
xi(L) = xi(1) < xi(1) <...< xi(Ki) = xi(R)
Введём обозначение fi(k) = fi(xi(k)). Тогда аппроксимирующая функция примет вид:
причём при всех i=1,...,N выполняется:
Последнее условие выражает тот факт, что не более двух переменных l(i) должны быть положительными.
Таким образом, нелинейная функция f(x) заменяется кусочно-линейной 
. Для построения хорошего приближения число узлов сетки должно быть большим, то есть линейность достигается за счёт роста размерности задачи, то есть решение задачи НЛП сводится к решению задачи ЛП большой размерности с переменными li(k). Полученная задача ЛП может быть решена с помощью симплекс-метода, дополненного правилом ограниченного ввода в базис, учитывающего условие (*).
Решение, полученное с помощью сепарабельного программирования, представляет собой локальный минимум. Сходимость к глобальному минимуму гарантирована только тогда, когда целевая функция и допустимая область выпуклы. Метод сепарабельного программирования подходит для решения задач, которые в основном линейный, а отклонения от линейности представляются сепарабельными функциями. Если не требуется высокой точности, то приближенное решение задачи можно получить в процессе однократного решения задачи ЛП.
Сепарабельное программирование даёт хорошие приближения во всей области определения каждого ограничения, однако он применим только к сепарабельным задачам и его точность сильно зависит от густоты узлов сетки. Поэтому, необходимо построить алгоритм, использующий довольно грубые аппроксимации внешних частей ограничений для достижения окрестности оптимальной точки и строящий более тонкие аппроксимации в этой окрестности.
20. Задачи дробно-линейного программирования (гиперболическое программирование).
Дробно-линейное программирование (ДЛП) — математическая дисциплина, посвящённая теории и методам решения задач об экстремумах отношений линейных функций на множествах n-мерного векторного пространства, задаваемых системами линейных уравнений и неравенств.
ДЛП является обобщением линейного программирования (ЛП) и, в то же время, частным случаем математического программирования. Как и в ЛП, принято разделение на общую задачу ДЛП и специальные задачи ДЛП (например, транспортная задача ДЛП, целочисленная задача ДЛП и т. д.).
Этапы для решение задачи:
1.В системе ограничений задачи заменяют знаки неравенств на знаки точных равенств и строят определяемые этими равенствами прямые.
2. Находят полуплоскости, определяемые каждым из неравенств системы ограничений задачи
3 находят многоугольник решений задачи
4.Строят прямую, уравнение которой получается, если положить значение целевой функции равным некоторому постоянному числу.
5.Определяют точку максимума или устанавливают неразрешимость задачи
6.Находят значение целевой функции в точке.
21. Дискретное программирование. Общие характеристики дискретных задач. Математические модели дискретных задач и их классификации.
Дискретное программирование (дискретная оптимизация) — раздел математического программирования.
В противоположность задачам оптимизации с непрерывными переменными, переменные в задачах дискретного программирования принимают только дискретные значения, например, целочисленные.
Задачи комбинаторной оптимизации можно решить с помощью методов дискретного программирования. Одними из основных методов решения задач дискретного программирования являются метод ветвей и границ и динамическое программирование.
Задачей дискретного программирования будем называть задачу отыскания экстремума скалярной функции, заданной на дискретном множестве, т.е. такую задачу математического программирования, у которой на все три или на часть переменных, определяющих область допустимых решений, наложено требование дискретности.
При дискретном программировании количество допустимых планов задачи конечно. Простейший алгоритм заключается в последовательном сравнении значений елевой функции для двух допустимых планов, отбрасывании плана с худшим решением и т.д. до полного перебора всех допустимых планов. Алгоритм полного перебора оказывается практически непригодным при большом числе допустимых планов, что в реальных задачах обычно имеет место.
Модели задач дискретного программирования
Существуют различные классификации математических моделей задач дискретного программирования. Обычно выделяют модели задач с неделимостями; экстремальные комбинаторные задачи; задачи, имеющие определенные особенности целевой функции или области допустимых решений; задачи, сводящиеся к задачам ДП.
Рассмотрение математической постановки некоторых конкретных прикладных задач, что включает выбор переменных, формулировку выражения для целевой функции и зависимостей, определяющих области допустимых решений.
Примеры задач:
· Задача о назначениях
· Задача о ранце
· Задача коммивояжера
· Задачи теории расписаний
· Задача маршрутизации транспорта
· Задачи о покрытиях графов
22. Перечисление специальных методов решения задач дискретного программирования.
Одними из основных методов решения задач дискретного программирования являются метод ветвей и границ и динамическое программирование.
Метод ветвей и границ (англ. branch and bound) — общий алгоритмический метод для нахождения оптимальных решений различных задач оптимизации, особенно дискретной и комбинаторной оптимизации. По существу, метод является вариацией полного перебора с отсевом подмножеств допустимых решений, заведомо не содержащих оптимальных решений.
Общая идея метода может быть описана на примере поиска минимума и максимума функции f(x) на множестве допустимых значений x. Функция f и x могут быть произвольной природы. Для метода ветвей и границ необходимы две процедуры: ветвление и нахождение оценок (границ).
Процедура ветвления состоит в разбиении области допустимых решений на подобласти меньших размеров. Процедуру можно рекурсивно применять к подобластям. Полученные подобласти образуют дерево, называемое деревом поиска или деревом ветвей и границ. Узлами этого дерева являются построенные подобласти.
Процедура нахождения оценок заключается в поиске верхних и нижних границ для оптимального значения на подобласти допустимых решений.
В основе метода ветвей и границ лежит следующая идея (для задачи минимизации): если нижняя граница для подобласти A дерева поиска больше, чем верхняя граница какой-либо ранее просмотренной подобласти B, то A может быть исключена из дальнейшего рассмотрения (правило отсева). Обычно, минимальную из полученных верхних оценок записывают в глобальную переменную m; любой узел дерева поиска, нижняя граница которого больше значения m, может быть исключен из дальнейшего рассмотрения.
Если нижняя граница для узла дерева совпадает с верхней границей, то это значение является минимумом функции и достигается на соответствующей подобласти.
23. Методы целочисленного программирования. Класс задач целочисленного программирования.
Целочисленное программирование
Целочисленное программирование - разновидность математического программирования, подразумевающая, что искомые значения должны быть целыми числами.
Раздел математического программирования, в котором изучаются методы нахождения экстремумов функций в пространстве параметров, где все или некоторые переменные являются целыми числами.
Простейший метод решения задачи целочисленного программирования — сведение её к задаче линейного программирования с проверкой результата на целочисленность.
Булевское программирование
К частному случаю задачи целочисленного линейного программирования относятся задачи, где переменные X могут принимать всего лишь два значения — 0 и 1. Соответствующие задачи часто называют задачами булевского программирования. Наиболее известные из этих задач — задача о назначениях (какого работника на какую работу поставить), задача выбора маршрута (задача коммивояжера, задача почтальона), задача о максимальном паросочетании и т. д. Целочисленное программирование применяется при решении задачи оптимизации развития компании, в которой 0 или 1 означают покупку какого-либо оборудования.
Для решения задач этого типа разрабатываются специфические алгоритмы, основанные на комбинаторике, графах и т. д.
К методам целочисленного программирования относят:
МЕТОДЫ ОТСЕЧЕНИЙ
Методы отсечений относятся к численным методам решения дискретных задач оптимизации (методам дискретного программирования). Они предназначены для решения целочисленных задач линейного программирования (ЛП).
Идея методов отсечения состоит в следующем. Первоначально решается обычная ("непрерывная") задача ЛП, полученная из исходной задачи отбрасыванием требования целочисленности. Если полученное решение является целочисленным, то оно будет также решением исходной задачи. Если нет, то к ограничениям исходной задачи добавляется новое линейное ограничение, обладающее двумя свойствами:
Такое ограничение называется правильным отсечением.
Затем решается расширенная непрерывная задача ЛП, т.е. непрерывная задача с добавленным ограничением. Если полученное решение не является целочисленным, добавляется новое правильное отсечение и т.д. Процесс повторяется до тех пор, пока решение очередной расширенной непрерывной задачи ЛП не окажется целочисленным. Таким образом, решение целочисленной задачи ЛП сводится к решению некоторой последовательности обычных задач ЛП.
Геометрически добавление каждого такого линейного ограничения означает проведение гиперплоскости, отсекающей от многогранника допустимых решений очередной непрерывной задачи ЛП оптимальную точку с нецелочисленными координатами, но не затрагивающей ни одной из целочисленных точек этого многогранника. Поэтому методы, опирающиеся на эту идею, получили название методов отсечений.
МЕТОД ВЕТВЕЙ И ГРАНИЦ
Метод ветвей и границ относится к группе комбинаторных методов дискретного программирования и является одним из наиболее распространенных методов этой группы. Центральную идею комбинаторных методов составляет замена полного перебора допустимого множества X частичным перебором. В случае метода ветвей и границ это осуществляется путем последовательного разбиения допустимого множества на подмножества (ветвления) и вычисления оценок (границ), позволяющих отбрасывать подмножества, заведомо не содержащие решения задачи. При реализации общей схемы метода ветвей и границ для различных задач дискретного программирования необходимо, исходя из специфики этих задач, конкретизировать правила ветвления и вычисления границ.
24. Метод отсечения (метод Гомери, метод отсекающих плоскостей) и метод ветвей и границ.
Общая задача линейного дискретного целочисленного программирования имеет вид:
(4.1)
(4.2)
xj ≥ 0, j = 1,..,n (4.3)
xj– целые, j = 1,..,n (4.4)
Задача (4.1) – (4.4) называется полностью целочисленной задачей линейного программирования, т.к. на все переменные положено условие целочисленности (ограничение 4.4). Когда это условие относится лишь к некоторым переменным, задача называется частично целочисленной.
Пусть дана задача полностью целочисленного линейного программирования (4.1) – (4.4). Алгоритм метода отсечений состоит из следующих этапов:
1) решается ЗЛП (4.1) – (4.3) с отброшенными условием целочисленности (4.4); если она не разрешима, то задача (4.1) –(4.4) тоже решения не имеет;
2) если условие целочисленности выполняется по всем переменным, то найденное решение есть решение задачи (4.1) –(4.4);
3) иначе строится дополнительное отсекающее ограничение, включается в систему ограничений (4.2) – (4.3) и на этап 1.
Для решения полностью целочисленной задачи ЛП Гомори предложено делать каждый раз на этапе 3 дополнительное ограничение для нецелой переменной с наибольшей дробной частью.
Предположим, что задача с отброшенным условием целочисленности решена. Рассмотрим i-ю строку оптимальной симплексной таблицы, которой соответствует нецелое решение β i базисной переменной xi Пусть R – множество индексов j, которые соответствуют небазисным переменным. Тогда переменная xi может быть выражена через небазисные переменные xj:
β i – нецелое. (4.5)
Обозначим наибольшую целую часть числа a, его не превосходящую, через [a], (a≥[a]), а дробную положительную часть – через {a} Очевидно a = [a] + {a}. Например, если a=4,7 то [a] = 4, {a} = 0,7, если a =-8,6, то [a] = -9, {a} = 0,4.
Выразим базисную переменную xi в (4.5) в виде суммы целой и дробной частей.
.(4.6)
Выражение в левых круглых скобках (4.6) целое число, и чтобы xj было целым, необходимо, чтобы выражение в правых круглых скобках (4.6) тоже было целым. Когда выражение 
будет целым? Так как 0 ≤ {βi}≤1, а 
то Li будет целым числом, если 
т.е.
(4.7)
Соотношение (4.7) определяет правильное отсечение Гомори.
Задача (4.1) – (4.4) не будет иметь полностью целочисленного решения, если встретится в симплекс-таблице уравнение такое, что βi дробное число, а αij –целые.
25. Динамическое программирование. Общая структура задач динамического программирования.
В рассмотренных задачах линейного и нелинейного программирования мы находили их решение как бы в один этам или за один шаг. В отличи от этих задач задачи динамического программирования являются многоэтапными или многошаговыми. Иными словами, нахождение решения конкретных задач методами динамического программирования включает несколько этапов или шагов, ка каждом из которых определяется решение некоторой частной задачи, обусловленной исходной. По этому термин «динамическое программирование» не столько определяет особый тип задач, сколько характеризует методы нахождения решения отдельных классов задач математического программирования, которые могут относиться к задачам как линейного, так и не линейного программирования. Несмотря на это, целесообразно дать общую характеристику задачи динамического программирования и определить единый подход к ее решению.
26. Стохастическое программирование.
Стохастическое программирование — раздел математического программирования, совокупность методов решения оптимизационных задач вероятностного характера. Это означает, что, либо параметры ограничений (условий) задачи, либо параметры целевой функции, либо и те и другие являются случайными величинами (содержат случайные компоненты).
В задачах прикладной математики можно различать детерминированные и стохастические задачи. В процессе решения последних развилась обширная в настоящее время математическая дисциплина — теория вероятностей.
Вместе с тем вероятностные методы по существу применялись до сих пор исключительно к решению задач дескриптивного типа Оптимизационные стохастические задачи начали разрабатываться только в последнее десятилетие. Сказанное относится и к стохастическим вариантам задач оптимального программирования.
Тем не менее, стохастическое оптимальное программирование является весьма важной и перспективной ветвью прикладной математики уже хотя бы потому, что «на практике принятие решений всегда происходит в условиях той или иной неопределенности. Ясно также, что задачи стохастического программирования оказываются существенно сложнее соответствующих детермированных вариантов.
В задаче линейного программирования:
1.1
заданные величины сj, аij,,bi, dj, Dj. Часто на практике величины cj, aij bj, могут быть случайными. Так, если bi — ресурс, то он зависит от ряда факторов. Аналогично, сj — цены — будут зависеть от спроса и предложения, aij — расходные коэффициенты — от уровня техники и технологии. Задачи, в которых сj, аij,,bi — случайные величины, относят к задачам стохастического программирования. Переход от чистых стратегий к смешанным расширяет область определения задачи. Достижимый максимум целевой функции может при этом только увеличиться, а достижимый минимум — только уменьшиться. Вычисление оптимальной смешанной стратегии иногда называют определением решающего распределения стохастической задачи.
Задача стохастического программирования предусматривает стохастическую постановку и целевой функции, и ограничений. В задачах стохастического программирования, отвечающих ситуациям, в которых решение следует принимать до наблюдения реализации случайных условий и нельзя корректировать решение при получении информации о реализованных значениях случайных параметров, естественно определять оптимальный план в виде детерминированного вектора. Так определяется класс стохастических задач, для которых естественные решающие правила — правила нулевого порядка. Решение задач стохастического программирования в виде случайного вектора позволяет установить связь между компонентами оптимального плана, реализациями параметров условий задачи и их априорными статистическими характеристиками. Каждой реализации условий задачи соответствует, таким образом, реализация решения. Следовательно, решение задачи стохастического программирования в виде случайного вектора целесообразно определять в ситуациях, в которых решение может быть принято после наблюдения реализации условий задачи. Решающие распределения (смешанные стратегии) целесообразно использовать в стохастических задачах, отвечающих повторяющимся ситуациям, когда ограничены суммарные ресурсы, а интерес представляет только средний эффект от выбранного решения. Решение задачи в смешанных стратегиях, не зависящих от реализации случайных параметров, естественно проводить в повторяющихся ситуациях, в которых выбор оптимального плана должен предшествовать наблюдению. Решающее распределение, зависящее от реализации случайных параметров,— условное распределение компонент оптимального плана — рациональная основа управления в повторяющихся ситуациях, в которых выбор решения производится после наблюдения реализации параметров условий задачи.
Стохастическая постановка целевой функции может быть двух видов: М-постановка и Р-постановка.
При М- постановке случайная величина заменяется ее математическим ожиданием и задача сводится к оптимизации детерминированной целевой функции:
1.2
где сj — математическое ожидание случайной величины сj.
При Р-постановке целевая функция будет иметь вид:
· при максимизации целевой функции:
1.3
обозначает максимизацию вероятности того, что случайная величина ∑cj xj будет не меньше некоторого значения r;
· 
при минимизации целевой функции:
1.4
обозначает максимизацию вероятности того, что случайная величина ∑cj xj будет не больше некоторого значения r.
Наиболее распространены СТП-постановки в вероятностных ограничениях вида:
1.5
где аi j, bi — случайные величины; ai — заданные уровни вероятности.
Так, ограничение (а) означает, что вероятность соблюдения неравенства
1.6
должна быть не меньше, чем ai. Аналогичный смысл и других ограничений.
Для случая, когда вероятностные ограничения представлены в виде типа (а), задачу СТП можно записать при М-постановке:
1.7
При Р-постановке:
· в случае максимизации целевой функции
1.8
· в случае минимизации целевой функции
1.9
где cj, ai j, bi — случайные величины.
Для остальных случаев ограничений (б, в, г) постановка задач стохастического программирования аналогична.
Задачи (1.7), (1.8), (1.9) непосредственно решены быть не могут. Одним из возможных методов их решения может быть представление их в виде детерминированного эквивалента.
Практические задания:
1. Симплекс метод табличный.
2. Решение двойственных задач.
3. Нахождение оптимального плана прямой и двойственной задачи.
4. Метод геометрической интерпретация.
5. Решение ЗЛП двойственным симплекс методом.
6. Решение т-задачи.
Литература:
1. Методические указания по самостоятельным работам, практическим занятиям, контрольной работе.
2. Дослідження операцій в інформаційних системах.
3. Ю.П. Зайченко, С.А. Шумилова. Исследование операций. Сборник задач. – К., Вища школа. 1990.
Дата добавления: 2015-12-08; просмотров: 500 | Нарушение авторских прав