Москвин Б.В. Теория принятия решений
Подождите немного. Документ загружается.
71
на p-ой позиции базиса содержится дополнительная переменная
из вспомогательной задачи. Тогда рассчитываются оценки
æ
pj
=
∑
=
m
1i
ijpi
as
,
где s
pi
- элементы p-ой строки обратной матрицы базиса S
-1
;
a
ij
- элементы j-го вектора условий матрицы А; j ∈ J
q
.
2). Если æ
pj
≠ 0, при некотором j = k, то вектор базиса p
меняется на вектор условий k и происходит преобразование S
-1
.
Если æ
pj
= 0, для ∀j∈J
q
, то, следовательно, имеет место
ситуация б), т.е. rang A < m, и p-е ограничение можно исключить
из матрицы условий.
И так далее подобная процедура выполняется для всех до-
полнительных переменных, находящихся в оптимальном базисе
вспомогательной задачи. В дальнейшем целесообразно решать
основную задачу с матрицей условий А размерности r×n, где r =
rang A < m.
М-метод построения исходного опорного решения
Способ одновременного решения задачи построения ис-
ходного опорного решения и основной задачи известен как М-
метод решения задачи линейного программирования [87]. В этом
случае исходная задача погружается в специальную задачу (М-
задачу) вида
c
т
x - M
т
x
d
→ max,
A x + E x
d
= b,
x ≥ 0, x
d
≥ 0.
Здесь М - достаточно большие положительные числа, кото-
рые имеют смысл "штрафов" на введенные дополнительные пе-
ременные x
d
. Данная задача имеет очевидное исходное опорное
решение x
d
= b.
В процессе решения М-задачи симплекс-методом может
быть установлена ее неразрешимость - целевая функция неогра-
ниченно возрастает на множестве допустимых решений, либо
найдено оптимальное решение. Если в оптимальное решение
входят положительные дополнительные переменные, то исход-
ная задача неразрешима, т.е. нет допустимых решений, в про-
тивном случае (x
d
= 0) оптимальное решение М-задачи является
оптимальным решением исходной задачи.
72
Отметим, что для решения М-задачи линейного программи-
рования нет необходимости задавать величину М заранее. В
процессе решения при вычислении оценок δ
j
= π
т
a
j
- c
j
, j = 1,...,n,
следует полагать М больше любого сравниваемого с ним числа.
Такая модификация симплекс-метода часто называется М-ме-
тодом решения задач линейного программирования.
3.7. Вырожденность в задачах линейного программирования
Опорное решение, в котором одна или несколько базисных
компонент равны 0, называется в ы р о ж д е н н ы м.
Если задача вырожденная, то нарушается взаимно одно-
значное соответствие между опорными решениями и базисами, а,
следовательно, и вершинами многогранника решений. Одному и
тому же вырожденному опорному решению может соответство
-
вать несколько различных базисов. Например, если опорное ре-
шение (x) имеет (p < m) отличных от 0 составляющих и, соответ-
ственно (m-p) равных 0 составляющих, то его базис состоит из
(p) векторов условий, отвечающих ненулевым компонентам (x) и
(m-p) векторов, соответствующих нулевым компонентам. Тогда
вектор условий, соответствующий нулевой компоненте, можно
заменить на любой небазисный вектор, и единственным требова-
нием
при этом будет линейная независимость векторов вновь
образованного базиса.
Таким образом, одному и тому же вырожденному решению
может соответствовать множество базисов (или несколько вер-
шин многогранника). Данная ситуация может привести к зацикли-
ванию алгоритма поиска оптимального решения (периодическому
возвращению через несколько итераций к одному и тому же бази-
су). Переход от
одного вырожденного решения к другому проис-
ходит без изменения значения целевой функции, т.к. θ
r
= 0. Хотя,
как отмечается в литературе, явление зацикливания достаточно
редко, существует возможность модификации алгоритма с тем,
чтобы гарантированно избежать такого зацикливания. При этом
выбор вектора исключаемого из базиса (а именно на этом шаге и
возникает неоднозначность) производится особым образом.
Рассмотрим один из способов выбора вектора, выводимого
из базиса [87].
73
1. t = 0. Определяется множество Е
t
= Е
o
индексов r, на ко-
торых достигается θ
o
r
, где θ
o
r
определяется в соответствии с
(3.15)
x
si
θ
o
r
= m i n ⎯ , i = 1,..,m.
æ
ki
>0 æ
ki
2. Если Е
t
состоит из одного элемента r, то вектор a
k
вво-
дится на r-ю позицию базиса. Производится преобразование ос-
новной части таблицы 1.
В противном случае, если │Е
t
│ > 1, то t = t+1; составляется
множество Е
t
индексов r, на которых достигается θ
t
r
, где θ
t
r
вы-
числяется как
s
it
θ
t
r
= m i n ⎯
i∈E
t -1
æ
ki
здесь s
it
- элементы t-го столбца матрицы S
-1
из основной табли-
цы 1.
3. Производится переход на шаг 2.
Процесс повторяется до тех пор, пока не будет построено
множество Е
t
, для которого θ
t
r
достигается на единственной по-
зиции.
Контрольные вопросы
1. Каким образом формализовано решение в задаче линейно-
го программирования ?
2. В чем связь прямой и двойственной задач линейного про-
граммирования ? В чем смысл двойственных переменных ?
3. В чем отличие стандартной и канонической форм записи за-
дач линейного программирования. В чем отличия двойственных к
ним задач ?
4. Каким образом свести произвольную задачу линейного
про-
граммирования к канонической форме (неравенства различных
видов к равенствам; минимум к максимуму) ?
5. Как решить задачу линейного программирования, если пе-
ременные по условиям задачи могут принимать отрицательные
значения ?
74
6. Что представляет множество допустимых решений задачи
линейного программирования в n-мерном евклидовом простран-
стве? Почему ?
7. Где находится оптимальное решение задачи линейного про-
граммирования ? Почему ?
8. Как называется решение, соответствующее вершине много-
гранника решений? Чем оно отличается от других?
9. Что такое базис? Почему небазисные переменные равны 0?
10. Какие ситуации могут складываться в
процессе решения
задач линейного программирования ?
11. Каким образом в алгоритме симплекс-метода учитывается
особенность представления опорного решения ?
12. Из каких шагов состоит отдельная итерация симплекс-
метода ?
13. Что является признаком оптимальности опорного реше-
ния? Почему ?
14. Какой вектор условий целесообразно ввести в базис для
улучшения текущего решения ?
15. Какой вектор целесообразно вывести из
базиса для улуч-
шения текущего решения ? Почему ? Как изменится значение це-
левой функции ?
16. Каким образом построить исходное опорное решение в
различных задачах линейного программирования?
17. Каким образом при решении задач линейного программи-
рования убедиться, что допустимых решений не существует. По-
чему такие ситуации могут быть ?
18. Каким образом выявить факт неограниченного
возрастания
целевой функции на множестве допустимых решений. В каких
ситуациях это может быть ?
19. Что такое вырожденность в задачах линейного программи-
рования ? К чему она может привести, почему ?
75
4. НЕЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
4.1. Особенности задач нелинейного программирования
Задачу математического программирования (2.3) предста-
вим в следующем виде
f(x) → max, (4.1)
ϕ
i
(x) ≤ b
i
, i = 1,..., m, (4.2)
x = (x
1
,x
2
,...,x
n
)
т
≥ 0. (4.3)
Здесь выражение (4.1) задает целевую функцию, сопостав-
ляющую каждому решению x число, характеризующее некоторое
качество этого решения, а функциональные ограничения (4.2),
(4.3) задают множество допустимых решений ∆. В отличие от за-
дач линейного программирования, в которых целевая функция и
функции, описывающие множество допустимых решений, имеют
линейный вид, в задачах нелинейного программирования одна
или
несколько указанных функций нелинейные. В связи с этим
возникает ряд особенностей задач нелинейного программирова-
ния по сравнению с линейными задачами.
1. По сравнению с рассмотренными ранее задачами линей-
ного программирования, в которых оптимальное решение соот-
ветствует некоторым крайним точкам (вершинам) выпуклого мно-
гогранника, в задачах нелинейного программирования оптималь-
ное решение может
соответствовать произвольной точке области
Δ. В этих задачах решение может находиться как в точке, распо-
ложенной на границе допустимой области, так и в точке, распо-
ложенной внутри области, что определяется свойствами целевой
и ограничивающих функций.
76
2. Многосвязность допустимой области и многоэкстремаль-
ность задачи. В задачах нелинейного программирования при про-
извольных ограничениях (4.2) множество допустимых решений Δ
может быть многосвязным, т.е. представлять собой объединение
непересекающихся подмножеств. Решение в каждой такой облас-
ти следует искать независимо от других, и выбирать из них наи-
лучшее, однако установление факта многосвязности
Δ, как пра-
вило, достаточно трудоемко.
Нахождение оптимума произвольной функции (4.1) в допус-
тимой области Δ, даже если она задается линейными ограниче-
ниями, равно как и нахождение оптимума даже линейной функции
на невыпуклом множестве Δ, может привести к тому, что в исход-
ной оптимизационной задаче будет существовать несколько ло-
кальных экстремумов, т
.е. другими словами такая задача будет
многоэкстремальна (см.2.1). Существуют значительные трудно-
сти в определении локальных экстремумов, число которых в об-
щем случае может быть достаточно велико.
3. Так как целевая функция и множество допустимых аль-
тернатив в задачах нелинейного программирования описываются
произвольными нелинейными функциями, в ряде приложений эти
функции могут быть
разрывными или недифференцируемыми.
Это создает дополнительные трудности в решении таких задач и
требует разработки специфических методов нахождения опти-
мальных решений.
В соответствии с рассмотренными особенностями задач
нелинейного программирования, принято считать, что модель
(задача) принятия решения является теоретически разработан-
ной, если сформулированы необходимые и достаточные условия
существования оптимального решения, и построены
алгоритмы
поиска решения, обладающие доказательствами сходимости. В
этом смысле наиболее изученными и алгоритмически разрабо-
танными являются модели (задачи) выпуклого программирова-
ния, то есть задачи, в которых множество допустимых решений
выпукло, а целевая функция вогнута (выпукла вверх). В этих ус-
ловиях, как это было показано ранее (см. 2.3), оптимизационная
задача является одноэкстремальной.
Далее, рассматривая алго-
ритмы решения задач нелинейного программирования, в первую
очередь будем иметь в виду именно задачи выпуклого програм-
мирования.
77
4.2. Алгоритмы решения задач нелинейного
программирования
Эффективное решение различных задач нелинейного про-
граммирования может быть осуществлено на основе учета кон-
кретных особенностей этих задач. При этом под эффективностью
того или иного алгоритма, как правило, понимается объем вычис-
лений, необходимый для получения приемлемого решения, кото-
рый складывается из трудоемкости отдельной итерации и общего
количества итераций вычислительного процесса. В
настоящее
время для решения различных задач нелинейного программиро-
вания разработано большое количество алгоритмов, построен-
ных на использовании тех или иных методов, обладающих раз-
личными характеристиками и областью эффективной примени-
мости. Общей особенностью указанных алгоритмов является то,
что все они, как правило, для поиска оптимального решения в той
или иной степени
используют следующую итерационную схему:
x
k+1
= x
k
+ h
k
r(x
k
), k = 0,1,.... (4.4)
Здесь
k - номер итерации;
x
k
- решение на k-ой итерации;
r(x
k
) - направление, в котором изменяется значение x
k
;
h
k
- переменная, показывающая величину изменения (длину
шага) вектора x
k
в направлении r(x
k
); h
k
≥ 0.
В алгоритмах подобного типа [13] необходимо анализиро-
вать (доказывать) сходимость (и скорость сходимости) последо-
вательности {x
k
, k=0,1,...} к оптимальному решению x*. Критерием
окончания итерационного процесса служит выполнение неравен-
ства
║ x
k
- x*║ ≤ ε,
Поскольку значение x
*
, как правило, заранее не известно, то
часто используется критерий
║ x
k+1
- x
k
║ ≤ ε, или ║ r(x
k
)║ ≤ ε, или h
k
≤ ε,
Таким образом, для реализации итерационного процесса
(4.4) необходимо:
а) - задавать начальное значение x
o
;
б) - на каждом k-ом шаге уметь вычислять направление r(x
k
), и
величину шага h
k
;
78
в) - задавать критерий окончания итерационного процесса ε.
С точки зрения области применимости алгоритмов разли-
чают универсальные (широкоспециализированные) и специали-
зированные (узкоспециализированные) алгоритмы.
У н и в е р с а л ь н ы е алгоритмы предназначены для ре-
шения широкого класса задач нелинейного программирования.
При построении этих алгоритмов используются самые
общие
свойства задач; выпуклость функций, дифференцируемость
функций, замкнутость множества допустимых альтернатив и т. п.
С п е ц и а л и з и р о в а н н ы е алгоритмы в той или иной
степени учитывают специфику функций, описывающих множество
допустимых альтернатив и целевой функции. Прежде всего,
такая
специфика выражается в линейности этих функций. Так, напри-
мер, если ограничения задают выпуклый многогранник (описыва-
ются линейными уравнениями), т.е. имеют вид: A x ≤ b, x ≥ 0, то в
зависимости от вида целевой функции различают задачи:
- к в а д р а т и ч н о г о программирования; целевая функция
имеет вид: f(x) = c
т
x + x
т
Dx , где D - неположительно определен-
ная квадратная матрица;
- б и л и н е й н о г о программирования; целевая функция
имеет вид: f(x) = c
т
x + d
т
y + x
т
G y;
- д р о б н о - л и н е й н о г о программирования; целевая
функция имеет вид:
bxd
axс
f(x)
+
+
=
Τ
Τ
Учет отмеченных особенностей решаемых задач позволяет
существенно повысить эффективность специализированных ал-
горитмов.
С точки зрения особенностей математических методов оп-
тимизации, используемых при построении алгоритмов, можно
различать [42]:
1) алгоритмы, использующие методы приведения исходной
задачи нелинейного программирования с ограничениями к задаче
оптимизации некоторой другой, отличной от целевой, функции в
условиях отсутствия ограничений;
2)
алгоритмы прямого решения исходной задачи;
3) специальные алгоритмы, использующие методы преобразо-
вания функций, процедуры случайного поиска и другие.
В дальнейшем рассмотрим некоторые методы и алгоритмы
первых двух групп.
79
4.3. Методы приведенной безусловной оптимизации
Методы данной группы строятся на основе использования
концепции "погружения", когда исходная задача нелинейного про-
граммирования (4.1)-(4.3) с ограничениями приводится к задаче
оптимизации некоторой функции F(x) в условиях отсутствия огра-
ничений, и далее используются методы безусловной оптимиза-
ции. В качестве таких функций F(x) наиболее часто используются
функции Лагранжа и штрафные функции.
4.3.1. Методы безусловной оптимизации
Представим задачу безусловной оптимизации в виде
x* = arg max F(x) . (4.5)
x∈R
n
В основе алгоритмов решения задачи (4.5) лежит итеративный
процесс (4.4):
x
k+1
= x
k
+ h
k
r(x
k
), k = 0,1,....
Здесь k - номер итерации; x
k
- решение на k-ой итерации; r(x
k
) -
направление, в котором изменяется значение x
k
; h
k
- величина
изменения (шаг) вектора x
k
в направлении r(x
k
); h
k
≥0.
В зависимости от способа вычисления направления r(x
k
),
способа вычисления шага h
k
строятся различные алгоритмы ре-
шения задачи безусловной оптимизации.
Градиентный метод
В качестве r(x
k
) используется направление, в котором наи-
более сильно возрастает целевая функция. Это направление за-
дается градиентом функции ∇F(x
k
). Суть метода состоит в после-
довательном приближении к оптимальному решению x
*
на основе
проведения ряда итераций вида
x
k+1
= x
k
+ h
k
∇F(x
k
), k = 0,1,.... (4.6)
Алгоритмы, построенные на основе градиентного метода,
носят итерационный характер; итерация состоит в выполнении
ряда шагов.
0. Исходное состояние. Задается начальная точка x
o
∈ R
n
, не-
которое малое ε ≥ 0; k = 0.
1. Рассчитывается градиент в точке x
k
; ∇F(x
k
).
80
2. Задается шаг h
k
.
3. Находится x
k+1
= x
k
+ h
k
∇F(x
k
).
4. Проверяется условие ║x
k+1
- x
k
║ ≤ ε, или ║∇F(x
k
)║ ≤ ε.
Если данное условие выполняется, то счет окончен; если нет, то
k = k+1 и производится переход на шаг 2.
В пункте 2 задается шаг, обеспечивающий смещение ре-
шения в направлении градиента (возрастания целевой функции).
Шаг h
k
следует выбирать таким, чтобы обеспечивалось прираще-
ние целевой функции в направлении ∇F(x
k
), т.е. должно выпол-
няться условие F(x
k+1
) > F(x
k
). Вместе с тем, если h
k
очень велик,
то возможны ситуации, когда F(x
k+1
) < F(x
k
); если h
k
очень мал, то
процесс, описываемый (4.7), сходится достаточно долго (см.
рис.4.1).
Рис. 4.1.
В зависимости от способа выбора h
k
на каждой итерации
выделяют различные модификации алгоритма.
1. Постоянный шаг.
Задается h
k
= h = const, при этом должно выполняться ус-
ловие
F(x
k+1
) = F(x
k
+ h
k
∇F(x
k
)) > F(x
k
).
Пусть F(x) дифференцируема в окрестности точки x
k
(см. 2.2).
Тогда
F(x) = F(x
k
) + (∇F(x
k
),(x - x
k
)) + o(||x - x
k
|| ),
откуда
F(x
k+1
) - F(x
k
) ≥ ∇
т
F(x
k
)
(x
k+1
- x
k
),