Реферат: Аппроксимация
Опорным решением задачи (1)-(1') называется точка множества W, в которой не менее чем n ограничений из (1) обращается в верное равенство. Это - так называемая, угловая точка множества. Для n=2 это - вершина плоского угла.
Опорным решением задачи (2)-(2') называется точка, в которой не менее чем m ограничений из (2) обращается в верное равенство.
В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не является.
Опорное решение, доставляющее максимум функции (1') или минимум функции (2') называется оптимальным. В работе [1] показано, что оптимальное решение можно всегда искать среди опорных решений.
Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и равенства. Тогда условимся писать эти равенства первыми. Если их количество равно k, то область W запишется в виде:
|
a11x1 + a12x2 + … + a1nxn = b1 |
||
|
…………………………….……………………… |
||
|
|
||
|
ak+1, 1x1+ak+1, 2x2+…+ak+1, n xn£bk+1 |
||
|
…………………………….……………………… |
||
|
am1x1 + am2x2 + … + amnxn £ bm |
||
|
xj ³ 0, (j=1,…,n) |
Требуется найти максимум функции
|
Z=p1x1 + p2x2 + … + pnxn
В общем случае среди переменных xj могут быть свободные. Номера свободных переменных будем хранить в отдельном массиве.
При формировании двойственной задачи к задаче (3)-(3') i-му ограничению - равенству будет соответствовать свободная переменная ui (i=1,…,k), а свободной переменной xj ограничение - равенство:
a1j u1 + a2j u2 + … + amj um =pj
Введем вспомогательные переменные yi³0 (i=1,…,n) и запишем ограничения (3) и функцию Z в виде:
|
0 = a11 (-x1) + a12 (-x2) + … + a1n (-xn) + a1, n+1 |
||
|
…………………………………………………….……………………………………… |
||
|
|
||
|
yk+1 = ak+1, 1 (-x1) + ak+1, 2(-x2)+ … + ak+1, n(-xn) + ak+1, n+1 |
||
|
…………………………………………………….……………………………………… |
||
|
ym = am1 (-x1) + am2 (-x2) + … + amn(-xn) + am, n+1 |
||
|
Z = am+1, 1 (-x1) + am+1, 2(-x2)+ … + am+1, n(-xn) + am+1, n+1 |
Условие несвободности отдельных или всех переменных здесь не отмечено. Обозначения:
ai, n+1 = bi (i=1, …, m),
am+1, j = -pj (j=1, …, n)
am+1, n+1 = 0.
Таким образом, матрицу а мы дополнили столбцом свободных членов и строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:
Прямая задача Таблица 1
|
-x1 |
-x2 |
-xn |
1 | ||
| 0 = |
a11 |
a12 |
… |
a1n |
a1, n+1 |
| …… | …………………………… | ……… | |||
| 0 = | .. |
ak, n+1 |
|||
|
yk+1 = |
ak1 |
ak2 |
… |
akn |
ak+1, n+1 |
| …… |
ak+1, 1 |
ak+1, 2 |
… |
ak+1, n |
……… |
|
ym = |
…………………………… | ……… | |||
|
am1 |
am2 |
… |
amn |
am, n+1 |
|
| Z = |
am+1, n |
am+1, 2 |
… |
am+1, n |
am+1, n+1 |
Номера свободных переменных запоминаются отдельно.
Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.
Прямая и двойственная задачи Таблица 2
|
v1 = |
v2 = |
vn = |
W = | |||
|
-x1 |
-x2 |
-xn |
1 | |||
|
u1 |
0 = |
a11 |
a12 |
… |
a1n |
a1, n+1 |
| …… | ……………...……………… | ……… | ||||
|
uk |
0 = |
ak1 |
ak2 |
… |
akn |
ak, n+1 |
|
uk+1 |
yk+1 = |
ak+1, 1 |
ak+1, 2 |
… |
ak+1, n |
ak+1, n+1 |
| …… | …………………………… | ……… | ||||
|
um |
ym = |
am1 |
am2 |
… |
amn |
am, n+1 |
| 1 | Z = |
am+1, n |
am+1, 2 |
… |
am+1, n |
am+1, n+1 |
vj - вспомогательные переменные двойственной задачи.
Тогда j-е ограничение из таблицы имеет вид:
vj = a1j u1 + a2j u2 + … + amj um + am+1, j ³ 0, если xj ³ 0
Если переменная xj свободна, то ей соответствует ограничение-равенство двойственной задачи:
0=a1j u1 + a2j u2 + … + amj um + am+1, j
т.е. вместо vj фактически будет нуль.
