Информатика / Реферат: Аппроксимация

Реферат: Аппроксимация

достигался максимум функции

(1')

Z= p₁ x₁ + p₂ x₂ + … + p_n x_n

Функция Z называется целевой.

i-еограничение из (1) означает, что нельзя израсходовать i-гоингредиента больше, чем имеется вналичии. Ограничения (1) задают множество W. Переменные, удовлетворяющие условию x_j ³0, называются несвободными. В нашей задаче это означает, что при x_j =0 - ничего не производится или при x_j >0 производится некоторое количество изделий.

Переменные, на которые условия неотрицательности не накладываются, называются свободными.

Задача (1)-(1') и есть задача оптимального производственного планирования, решение которой обеспечивает достижение в конкретных условиях максимальной прибыли.

Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для производства тех же n изделий. При этом количество приобретаемых ингридиентов определяется вектором b=(b₁ , b₂ , …, b_m ). Задана та же матрица А, элемент которой aij определяет расход i-го ингридиента для производства j-го изделия. Кроме того задан вектор цен p=(p₁ , p₂ , …, p_n ) на продукцию предприятия. Требуется отыскать вектор цен ингридиентов u=(u₁ , u₂ , …, u_m ), где u_i - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись условия:

a₁₁ u₁ + a₂₁ u₂ + … + a_m1 u_m ³ p₁

(2)

a₁₂ u₁ + a₂₂ u₂ + … + a_m2 u_m ³ p₂

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

a_1n u₁ + a_2n u₂ + … + a_mn u_m ³ p_n

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

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

(2')

W=b₁ u₁ + … + b_m u_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_1n x_n = b₁

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

(3)

a_k1 x₁ + a_k2 x₂ + … + a_kn x_n = b_k

a_{k+1, 1} x₁ +a_{k+1, 2} x₂ +…+a_{k+1, n} x_n £b_k+1

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

a_m1 x₁ + a_m2 x₂ + … + a_mn x_n £ b_m

x_j ³ 0, (j=1,…,n)

Требуется найти максимум функции

(3')

Z=p₁ x₁ + p₂ x₂ + … + p_n x_n

В общем случае среди переменных x_j могут быть свободные. Номера свободных переменных будем хранить в отдельном массиве.

При формировании двойственной задачи к задаче (3)-(3') i-му ограничению - равенству будет соответствовать свободная переменная u_i (i=1,…,k), а свободной переменной x_j ограничение - равенство:

a_1j u₁ + a_2j u₂ + … + a_mj u_m =p_j

Введем вспомогательные переменные y_i ³0 (i=1,…,n) и запишем ограничения (3) и функцию Z в виде:

0 = a₁₁ (-x₁ ) + a₁₂ (-x₂ ) + … + a_1n (-x_n ) + a_{1, n+1}

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

(4)

0 = a_k1 (-x₁ ) + a_k2 (-x₂ ) + … + a_kn (-x_n ) + a_{k, n+1}

y_k+1 = a_{k+1, 1} (-x₁ ) + a_{k+1, 2} (-x₂ )+ … + a_{k+1, n} (-x_n ) + a_{k+1, n+1}

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

y_m = a_m1 (-x₁ ) + a_m2 (-x₂ ) + … + a_mn (-x_n ) + a_{m, n+1}

Z= a_{m+1, 1} (-x₁ ) + a_{m+1, 2} (-x₂ )+ … + a_{m+1, n} (-x_n ) + a_{m+1, n+1}

Условие несвободности отдельных или всех переменных здесь не отмечено. Обозначения:

a_{i, n+1} = b_i (i=1, …, m),

a_{m+1, j} = -p_j (j=1, …, n)

a_{m+1, n+1} = 0.

Таким образом, матрицу а мы дополнили столбцом свободных членов и строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:

Прямая задача Таблица 1

-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}

Номера свободных переменных запоминаются отдельно.

Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.

Прямая и двойственная задачи Таблица 2

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}

К-во Просмотров: 1139

Бесплатно скачать Реферат: Аппроксимация

>>> Скачать <<<