Аппроксимация (стр. 3 из 4)

a₁₁u₁ + a₂₁u₂ + … + a_m1u_m³ p₁

a₁₂u₁ + a₂₂u₂ + … + a_m2u_m³ p₂

^{…………………………….…………………….}

a_1nu₁ + a_2nu₂ + … + a_mnu_m³ p_n

u_i³ 0, (i=1,…,m)

при достижении минимума целевой функции

W=b₁u₁ + … + b_mu_m

j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на производство j-го изделия, не меньше рыночной цены этого изделия.

Условие несвободности u_j³0 означает, что j-й ингредиент либо бесплатен (u_j=0), либо стоит положительное количество рублей (u_j >0).

Опорным решением задачи (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 запишется в виде:

a₁₁x₁ + a₁₂x₂ + … + a_1nx_n = b₁

^{…………………………….………………………}

-x₁	-x₂	-x_n	1
0 =	a₁₁	a₁₂	…	a_1n	a_{1, n+1}
……	……………………………				………
0 =	..				a_{k, n+1}
y_k+1=	a_k1	a_k2	…	a_kn	a_{k+1, n+1}
……	a_{k+1, 1}	a_{k+1, 2}	…	a_{k+1, n}	………
y_m=	……………………………				………
a_m1	a_m2	…	a_mn	a_{m, n+1}
Z =	a_{m+1, n}	a_{m+1, 2}	…	a_{m+1, n}	a_{m+1, n+1}

v₁ =	v₂ =	v_n =	W =
-x₁	-x₂	-x_n	1
u₁	0 =	a₁₁	a₁₂	…	a_1n	a_{1, n+1}
……	……………...………………				………
u_k	0 =	a_k1	a_k2	…	a_kn	a_{k, n+1}
u_k+1	y_k+1=	a_{k+1, 1}	a_{k+1, 2}	…	a_{k+1, n}	a_{k+1, n+1}
……	……………………………				………
u_m	y_m=	a_m1	a_m2	…	a_mn	a_{m, n+1}
1	Z =	a_{m+1, n}	a_{m+1, 2}	…	a_{m+1, n}	a_{m+1, n+1}