44559 (Аппроксимация), страница 2

program approx;

uses crt,gausstpu;

const nm=20;

type vect1=array[1..nm] of real;

var c:matr;

a,b:vect;

x,y,z:vect1;

n,i,j,m:integer;

f1,f2:text;

procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect);

var i,j:integer;

r:vect;

begin

for i:=1 to n do

r[i]:=1;

for j:=1 to m+1 do begin

c[1,j]:=0;

b[j]:=0;

for i:=1 to n do begin

c[1,j]:=c[1,j]+r[i];

b[j]:=b[j]+r[i]*y[i];

end;

for i:=1 to n do

r[i]:=r[i]*x[i];

end;

for i:=1 to m do begin

for j:=1 to m do

c[i+1,j]:=c[1,j+1];

c[i+1,m+1]:=0;

for j:=1 to n do

c[i+1,m+1]:=c[i+1,m+1]+r[j];

for j:=1 to n do

r[j]:=r[j]*x[j];

end;end;

begin

assign(f1,'jan.dat');reset(f1);

assign(f2,'jan.res');rewrite(f2);

readln(f1,n);writeln(f2,'Число узлов аппроксимации n=',n:3);

readln(f1,m);writeln(f2,'Степень многочлена m=',m:2);

writeln(f2,'Вектор узлов аппроксимации x[i]');

for i:=1 to n do begin

read(f1,x[i]);

write(f2,x[i]:4:2,' ');

end;

writeln(f2);

writeln(f2,'Вектор значений аппроксимируемой функции y[i]');

for i:=1 to n do begin

read(f1,y[i]);

write(f2,y[i]:4:2,' ');

end;

Create_BC(n,m,x,y,c,b);

writeln(f2);

writeln(f2,'Матрица системы линейных уравнений для аппроксимации и вектор правых частей);

for i:=1 to m+1 do begin

for j:=1 to m+1 do

write(f2,c[i,j]:8:1);writeln(f2,b[i]:8:1);end;

gauss(m+1,c,b,a);

for i:=1 to n do begin

z[i]:=0;

for j:=m+1 downto 1 do

z[i]:=z[i]*x[i]+a[j];

z[i]:=z[i]-y[i];end;

writeln(f2);

writeln(f2,'Вектор коэфициентов аппроксимирующего многочлена по возрастанию);

writeln(f2,'степени (m+1 элементов)');

for i:=1 to m+1 do

writeln(f2,'a[',i:1,']=',a[i]:6:2);

writeln(f2,'Вектор погрешности аппроксимации в узлах X);

for i:=1 to n do

writeln(f2,'z[',i:1,']=',z[i]:5:3);

close(f1);close(f2);

end.

Исходный файл jan.dat:

10

2

1 6 0 3 8 2 12 9 2 5

9 4 13 7 3 9 3 1 4 2

Файл результатов jan.res:

Число узлов аппроксимации n=10

Степень многочлена m=2

Вектор узлов аппроксимации x[i]

1.00 6.00 0.00 3.00 8.00 2.00 12.00 9.00 2.00 5.00

Вектор значений аппроксимируемой функции y[i]

9.00 4.00 13.00 7.00 3.00 9.00 3.00 1.00 4.00 2.00

Матрица системы линейных уравнений для аппроксимации и вектор правых частей

10.0 48.0 368.0 55.0

48.0 368.0 3354.0 159.0

368.0 3354.0 33428.0 1023.0

Вектор коэфициентов аппроксимирующего многочлена по возрастанию степени (m+1 элементов)

a[1]= 11.66

a[2]= -2.31

a[3]= 0.13

Вектор погрешности аппроксимации в узлах X

z[1]=0.479

z[2]=-1.381

z[3]=-1.343

z[4]=-1.070

z[5]=-1.247

z[6]=-1.430

z[7]=-0.244

z[8]=0.723

z[9]=3.570

z[10]=1.454

5.1 Список переменных основной программы.

В основной программе используются раздел констант и типов:

const nm=20;

type vect1=array[1..nm] of real;

Следующие переменные так же используются в программе, которые описываются в разделе var:

Переменная	Тип переменной	Описание переменной
С	matr	Матрица системы линейных уравнений для аппроксимации
А	vect	Вектор коэфициентов аппроксимирующего многочлена по возрастанию степени (m+1 элементов)
Х	vect1	Вектор узлов аппроксимации
B	vect	Вектор правых частей
Y	vect1	Вектор значений аппроксимирующей функции
Z	vect	Вектор погрешности аппроксимации в узлах Х
n	integer	Число узлов аппроксимации
m	integer	Степень многочлена
i	integer	Необходима для нумерации элементов массивов.
j	integer	Необходима для нумерации элементов массивов.
f1	text	Файловая переменная для файла исходных значений
f2	text	Файловая переменная резуртирующего файла

6.1 Заголовки процедур и функций. Список их переменных.

В своей программе я использовал следующие модули, которые описываются в операторе uses и процедуры:

Crt - стандартный модуль подключения экрана и клавиатуры для работы с программой.

Gauss - процедура решения системы линейных уравнений методом Гаусса. Она берется из модуля Gausstpu, где интерфейсная часть имеет вид:

Interface

Const nmax=20

Type

Поэтому при объявлении матрицы С ссылаться надо на matr, а векторов A и B на vect.

Create_BC - процедура расчета матрицы С (С - матрица системы линейных уравнений для аппроксимации). Заголовок этой процедуры выглядит так:

procedure Create_BC(n,m:integer; var x,y:vect1; var c:matr; var b:vect);

var i,j:integer;

r:vect;

А вот такие переменные используются только в этой процедуре, остальные засылаются из основной программы:

Переменная	Тип переменной	Описание переменной
i	integer	Используются в циклах для перебора численных значений
j	integer	Используются в циклах для перебора численных значений
R	vect	Рабочий вектор

7.1 Ручной счет.

Составляем матрицу системы уравнений по следующему принципу:

n	xi	xi2	yi
xi	xi2	xi3	xiyi
xi2	xi3	xi4	xi2yi

Для этого вычисляем необходимые значения:

n=10;

x_i=1+6+0+3+8+2+12+9+2+5=48;

x_i²=1²+6²+0²+3²+8²+2²+12²+9²+2²+5²=368;

y_i=9+4+13+7+3+9+3+1+4+2=55;

x_i³=1³+6³+0³+3³+8³+2³+12³+9³+2³+5³=3354;

x_iy_i=1*9+6*4+0*13+3*7+8*3+2*9+12*3+9*1+2*4+5*2=159;

x_i³=1⁴+6⁴+0⁴+3⁴+8⁴+2⁴+12⁴+9⁴+2⁴+5⁴=33428;

x_i²y_i=1²*9+6²*4+0²*13+3²*7+8²*3+2²*9+12²*3+9²*1+2²*4+5²*2=1023.

Получается следующая матрица:

10	48	368	55
48	368	3354	159
368	3354	33428	1023

Которая эквивалентна такой системе уравнений:

{

10a₁ + 48a₂ + 368a₃ = 55

48a₁ + 368a₂ + 3354a₃ = 159

368a₁ + 3354a₂ + 33428a₃ = 1023

Мы решаем эту систему уравнений методом Гаусса:

10	48	368	55
0	137,6	1587,6	-105
0	1587,6	19885,6	-1001

10	48	368	55
0	137,6	1587,6	-105
0	0	1568,203488	210.4680233

Получаем упрощенную систему уравнений:

{

1568,203488a₃ = 210,4680233

137,6a₂ + 1587,6a₃ = -105

10a₁ + 48a₂ + 368a₃ = 55

Решая которую получаем следующие окончательные значения, которые являются ответом:

{

a₃=210,4680233/1568,203488=0,134209638

a₂=(-105-1587,6 a₃)/137,6=-2,311564115

a₁=(55-48a₂-368a₃)/10=11,65659307

8.1 Обсуждение результатов с целью доказательства правильности алгоритма и программы.

Полученные результаты показывают, что алгоритм и программа составлены верно, так как значения полученные при ручном счете близки к машинным вычислением.

9.1 Выводы.

Данная программа очень эффективна, так как машина выполняет все действия гораздо быстрее, чем человек при ручном счете. Так же во время ручного счета могут произоити ошибки, что приведет к повторному перещитыванию, а у машины, при правильном алгоритме, таких сбоев не бывает (если только "зависает"). Следовательно эта программа во многом облегчает жизнь человеку.

1. Экономическая часть. Разработка модуля исключения нуль-уравнений в комплексе “Решение задачи линейного программирования”.

1.2 Постановка задачи линейного программирования и задание на разработку модуля.

Рассмотрим задачу оптимального планирования производства [1]. Пусть предприятие выпускает n изделий, для производства которых используется m ингредиентов. Ингредиенты это – детали определенного сортамента, станки, работники, электроэнергия и т.д., иначе говоря, все что требуется для осуществления производственного цикла. Запасы ингредиентов задаются вектором b=(b₁, b₂,…, b_m ), где b_i - запас i-го ингридиента (i=1,…,m). Задана матрица А, элемент которой a_ij определяет расход i-го ингридиента для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан вектор рыночных цен изделий p=(p₁, p₂,…, p_n), где p - цена j-го изделия (j=1,…,n).

Требуется составить такой план производства х=(х₁, х₂,…, х_n), чтобы при выполнение условий

a11x1 + a12x2 + … + a1nxn  b1

(1) a21x1 + a22x2 + … + a2nxn  b2

…………………………….…………………….

am1x1 + am2x2 + … + amnxn  bm

xj  0, (j=1,…,n).

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

(1')

Z= p₁x₁ + p₂x₂ + … + p_nx_n

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

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

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