lec_opt1
.pdf
(***)
Рассмотреть отрезок, это может дать нам еще один отрезок.
Задачи линейного программирования (ЛП).
Z = CT x +C0 |
→ min |
|
|
Ax = b |
- стандартная форма задачи ЛП |
|
||
|
x ≥ 0 |
|
|
|
|
|
|
|
В общем случае, |
если Ax ≥ b , то допустимая область представляющая собой |
|
многогранник в пространстве.
В случае Ax = b, x ≥ 0 - многогранник, имеющий неполную размерность.
Допустим, имеется некоторое выпуклое множество. Тогда в любой граничной точке этого множества, всегда можно провести опорную гиперплоскость, т.е. такую гиперплоскость которая имеет с множеством только одну общую точку, и все множество находится по одну сторону от гиперплоскости.
Если –grad является нормалью к гиперплоскости и плоскость не опорная, то можно двигаться под острым углом к –grad, тем самым улучшая значение функции. Такое движение невозможно, если антиградиент определяет опорную плоскость. Следовательно в этом случае это точка локального минимума, который является и глобальным.
Геометрически, чтобы найти точку локального минимума, необходимо найти такую вершину глобального множества, что плоскость которая является нормальной к антиградиенту является опорной.
Рассмотрим Ax = b, x ≥ 0 , т – ограничений равенств, п – число переменных. n
m A
Первые m столбцов линейно независимы. rank(B)= m , det(B)≠ 0 .
31
n n-m
A = |
B |
N |
m |
Базисная матрица
Ax = A1 x1 + A2 x2 +K+ An xn , A1 , A2 ,K, An - столбцы матрицы
A = B x = xB - базисные переменные
N xN
Тогда систему ограничений равенств можно записать
B xB +b ; N xN
BxB + NxN = b BxB = −NxN +b ;
Для В существует обратная матрица B−1 xB = −B−1 NxN + B−1b ;
xB = −B−1 NxN + B−1b
Если для данного базиса зафиксируем не базисные переменные в нуле, то получим точку, которая является вершиной многогранника.
Вершины многогранника множества характеризуемые тем, что небазисные переменные равны 0.
Что делать если вершина не точка оптимума. Рассмотрим целевую функцию:
|
T |
|
|
T |
|
|
|
T |
|
T |
T |
|
−1 |
|
−1 |
T |
|
|
|
CB |
|
|
xB |
|
|
|
|||||||||
Z = C |
|
x = |
|
|
|
|
|
|
= CB xB +СN xN = CB |
(− B |
|
NxN + B |
|
b)+CN xN = |
|||
|
|
|
|
|
|||||||||||||
|
|
CN |
xN |
|
|
|
|
|
|
|
|
|
|||||
−CBT B−1 NxN + CBT B−1b + CNT xN = (CNT −CBT B −1 N )xN + CBT B −1b = |
|||||||||||||||||
|
|
|
|
|
|
|
|
|
T |
xN +bT B−T CB = B−T = (BT )−1 |
|
||||||
|
|
|
CN |
− |
N T B−T CB |
|
|
||||||||||
|
|
|
1442443 |
|
|
14243 |
|
|
|
|
|||||||
|
|
|
|
|
|
d |
|
|
|
d0 |
|
|
|
|
|
||
d – показывает суммарное влияние небазисных переменных на целевую функцию d0 – множители Лагранжа или относительные оценки небазисных переменных.
Z = C T x = d T xN + Z0
Z
X N |
X B |
Точка будет точкой оптимума, если все d ≥ 0 . Если имеется один отрицательный коэффициент.
Z = d1 (xN )1 +K+ d j (xN )j +K+ dn (xN )n + Z0
d j < 0 следовательно можно увеличить xN , тогда целевая функция начнет
улучшаться.
(xB )i ≥ 0 , если (xB )j = 0 , то дальше xN увеличивать нельзя xNj и xBj меняются местами.
32