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

Работа добавлена на сайт bukvasha.net: 2015-06-29

Поможем написать учебную работу

Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.

Предоплата всего

от 25%

Подписываем

договор

Имя

Выберите тип работы:

Принимаю Политику конфиденциальности

Скидка 25% при заказе до 27.12.2024

Министерство общего и профессионального образования Российской Федерации

Московский Государственный Строительный Университет

Кафедра информатики и прикладной математики

КУРСОВАЯ РАБОТА ПО ИНФОРМАТИКЕ

на темы:

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

Выполнил студент ЭОУС – I – 2: Моносов А. Л.

Преподаватель: доцент Марьямов А. Г.

Москва 1999.

Оглавление.

I. Математическая часть. Название…………………………………3.

1.1 Постановка задачи………………………………………………….3.

2.1 Изложение метода………………………………………………….4.

3.1 Блок-схема алгоритма. Описание исходных данных и результатов………………………………………………………………5.

4.1 Листинг программы, исходных данных и результатов……………6.

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

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

7.1 Ручной расчет……………………………………………………..11.

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

9.1 Выводы…………………………………………………………….13.

II. Экономическая часть. Название………………………………..14.

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

2.2 Описание исходных данных и результатов решения задач линейного программирования………………………………………...18.

3.2 Описание модуля типов…………………………………………..19.

4.2 Укрупненная блок-схема задачи линейного программирования..20.

5.2 Параметры и заголовки процедур задачи линейного программирования……………………………………………………..21.

6.2 Блок-схема и параметры реализованной процедуры……………21.

7.2 Листинг модуля, исходных данных и результатов машинного расчета………………………………………………………………….23.

8.2 Ручной расчет задачи линейного программирования…………...24.

9.2 Выводы…………………………………………………………….26.

Список использованной литературы. ……………………………..27.

Математическая часть. Аппроксимация.

Постановка задачи.

Пусть величина y является функцией аргумента x. Это означает, что любому значению x из области определения поставлено в соответствии значение y. Вместе с тем на практике часто неизвестна явная связь между y и x, т.е. невозможно записать эту связь в виде y=f(x). В некоторых случаях даже при известной зависимости y=f(x) она настолько громоздка (например, содержит трудно вычисляемые выражения, сложные интегралы и т.п.), что ее использование в практических расчетах затруднительно.

Наиболее распространенным и практически важным случаем, когда вид связи между параметрами x и y неизвестен, является задание этой связи в виде некоторой таблицы {x_i y_i}. Это означает, что дискретному множеству значений аргумента {x_i} поставлено в соответствие множество значений функции {y_i} (i=0,1…n). Эти значения - либо результаты расчетов, либо экспериментальные данные. На практике нам могут понадобиться значение величины y и в других точках, отличных от узлов x_i. Однако получить эти значения можно лишь путем очень сложных расчетов или провидением дорогостоящих экспериментов.

Таким образом, с точки зрения экономии времени и средств мы приходим к необходимости использования имеющихся табличных данных для приближенного вычисления искомого параметра y при любом значении (из некоторой области) определяющего параметра x, поскольку точная связь y=f(x) неизвестна.

Этой цели и служит задача о приближение (аппроксимации) функций: данную функцию f(x) требуется приближенно заменить (аппроксимировать) некоторой функцией g(x) так, чтобы отклонение (в некотором смысле) g(x) от f(x) в заданной области было минимальным. Функция g(x) при этом называется аппроксимирующей.

Для практики весьма важен случай аппроксимации функции многочленом:

g(x)=a₀+a₁x+a₂x²+…+a_mx^m (2.1)

При этом коэффициенты a_j будут подбираться так, чтобы достичь наименьшего отклонения многочлена от данной функции.

Если приближение строиться на заданном множестве точек {xi}, то аппроксимация называется точечной. К ней относятся интерполирование, среднеквадратичное приближение и др. При построении приближения на непрерывном множестве точек (например, на отрезке [a,b] аппроксимация называется непрерывной или интегральной).

2.1 Изложение метода (Точечная аппроксимация).

Одним из основных типов точечной аппроксимации является интерполирование. Оно состоит в следующем: для данной функции y=f(x) строим многочлен (2.1), принимающий в заданных точках x_i те же значения y_i, что и функция f(x), т.е. g(x_i)=y_i, i=0,1,…n.

При этом предполагается, что среди значений x_i нет одинаковых, т.е. x_ix_kприэтом ik. Точки x_i называются узлами интерполяции, а многочлен g(x) - интерполяционным многочленом.

X₀X₁. . . X_n

Рис. 1

Таким образом, близость интерполяционного многочлена к заданной функции состоит в том, что их значения совпадают на заданной схеме точек (рис.1, сплошная линия).

Максимальная степень интерполяционного многочлена m=n; в этом случае говорят о глобальной интерполяции.

При большом количестве узлов интерполяции получается высокая степень многочлена (2.1) в случае глобальной интерполяции, т.е. когда нужно уметь один интерполяционный многочлен для всего интервала изменения аргумента. Кроме того, табличные данные могли быть получены путем измерений и содержать ошибки. Построение аппроксимируемого многочлена с условием обязательного прохождения его графика через эти экспериментальные точки означало бы тщательное повторение допущенных при измерениях ошибок. Выход из этого положения может быть найден выбором такого многочлена, график которого проходит близко от данных точек (рис.1, штриховая линия).

Одним из таких видов является среднеквадратичное приближение функции с помощью многочлена (2.1). При этом m  n; случай m = n соответствует интерполяции. На практике стараются подобрать аппроксимирующий многочлен как можно меньшей степени (как правило, m=1, 2, 3).

Мерой отклонения многочлена g(x) от заданной функции f(x) на множестве точек (x_i,y_i) (i=0,1,…,n) при среднеквадратичном приближении является величина S, равная сумме квадратов разности между значениями многочлена и функции в данных точках:

S = [g(x_i)-y_i]²

ⁱ⁼⁰

Для построения аппроксимирующего многочлена нужно подобрать коэффициенты a₀, a₁,…,a_m так, чтобы величина S была наименьшей. В этом состоит метод наименьших квадратов.

dS/da₁=2[ g(x_i)-y_i]²*1=0;

ⁱ⁼¹

dS/da₂=2[ g(x_i)-y_i]²*x_i=0;

ⁱ⁼¹

…

dS/da_m+1=2[ g(x_i)-y_i]²*x_i^m=0.

ⁱ⁼¹

C A B

n	 x_i	…	 x_i^m	a₁	y_i
=  x_i	 x_i²	…	 x_i^m+1	a₂	y_ix_i
…	……	…	……	…	…
 x_i^m	 x_i^m+1	…	 x_i^2m	a_m+1	y_ix_i^m

3.1 Блок-схема алгоритма. Описание исходных данных и результатов.

i=1

i=n

j=1

Расчет первой строки матрицы С и вектора В

i=1

i=n

i=1

i=n

j=m+1

i=1

j=1

j=m

Расчет остальных строк матрицы С

j=1

j=n

j=1

j=n

i=m

i=1

j=m+1

шаг=-1

j=1

i=n

Исходные данные, а именно:

m-число узлов аппроксимации.

n - степень аппроксимирующего многочлена.

X - вектор узлов аппроксимации.

Y - вектор значений аппроксимируемой функции.

Все эти значения мы заносим в файл jan.dat, который работает только на чтение и файловой переменной является f1.

Результаты:

Все результаты выводятся в файл jan.res, работающий на запись и имеющий файловую переменную f2.

Первоначально в этот файл выводятся исходные данные, которые берутся из файла jan.dat, но при этом уже с описанием, то есть не просто числа, а скоментарием, что они означают.

Затем выводятся результаты вычисления, проведенной машиной, при этом все результаты отформатированы:

Выводится матрица С системы линейных уравнений для аппроксимации вместе с вектором правых частей. Затем выводится решение этой системы уравнений, что является вектором коэффициентов аппроксимирующего многочлена по возрастанию степени. И в конце выводится вектор погрешности аппроксимации Z.

4.1 Листинг программы, исходных данных и результатов.

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:

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	x_i	x_i²	y_i
x_i	x_i²	x_i³	x_iy_i
x_i²	x_i³	x_i⁴	x_i²y_i

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

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.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), чтобы при выполнение условий

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

(1)

a₂₁x₁ + a₂₂x₂ + … + a_2nx_n  b₂

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

a_m1x₁ + a_m2x₂ + … + a_mnx_n  b_m

x_j  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 производится некоторое количество изделий.

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

Задача (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_m1u_m  p₁

(2)

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

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

a_1nu₁ + a_2nu₂ + … + a_mnu_m  p_n

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

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

(2')

W=b₁u₁ + … + b_mu_m

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

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

Опорным решением задачи (1)-(1') называется точка множества , в которой не менее чем n ограничений из (1) обращается в верное равенство. Это - так называемая, угловая точка множества. Для n=2 это - вершина плоского угла.

Опорным решением задачи (2)-(2') называется точка, в которой не менее чем m ограничений из (2) обращается в верное равенство.

В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не является.

Опорное решение, доставляющее максимум функции (1') или минимум функции (2') называется оптимальным. В работе [1] показано, что оптимальное решение можно всегда искать среди опорных решений.

Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и равенства. Тогда условимся писать эти равенства первыми. Если их количество равно k, то область  запишется в виде:

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

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

(3)

a_k1x₁ + a_k2x₂ + … + a_knx_n = b_k

a_k+1,
1x₁+a_k+1,
2x₂+…+a_k+1,
nx_nb_k+1

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

a_m1x₁ + a_m2x₂ + … + a_mnx_n  b_m

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

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

(3')

Z=p₁x₁ + p₂x₂ + … + p_nx_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}

v_j- вспомогательные переменные двойственной задачи.

Тогда j-е ограничение из таблицы имеет вид:

v_j = a_1j u₁ + a_2j u₂ + … + a_mj u_m + a_m+1,
j 0, если x_j  0

Если переменная x_jсвободна, то ей соответствует ограничение-равенство двойственной задачи:

0=a_1ju₁ + a_2ju₂+ … + a_mj u_m + a_m+1,
j

т.е. вместо v_j фактически будет нуль.

Кроме того первые k переменных двойственной задачи свободны, а остальные несвободны.

Целевая функция двойственной задачи

W= a_1,
n+1u₁ + a_2,
n+1u₂+ … + a_m,n+1 u_m + a_m+1,
n+1

Совмещение в одной таблице прямой и двойственной задачи неслучайно. Решая прямую задачу, мы получаем о дновременно решение двойственной задачи, причем

max Z = min W = a_m+1,
n+1

Сделаем замену переменных в таблице 1 , перебросив вспомогательную переменную y_r на верх таблицы со знаком минус, а основную пременную x_s на бок таблицы (a_rs0). Это означает движение из вершины x=(0, …, 0) в другую вершину многогранника  по его ребру. Элемент а_rs называется разрешающим, строка r - разрешающей строкой, столбец s - разрешающим столбцом. Такая замена переменных носит название модифицированных жордановых исключений (МЖИ). Элементы матрицы а, не принадлежащие разрешающему столбцу или разрешающей строке, назовем рядовыми.

2.2 Описание исходных данных и результатов решения задачи линейного программирования.

Обсудим исходные данные (текстовой файл simp.dat) и результаты решения задачи линейного программирования (текстовой файл simp.res). В начале файла simp.dat расположены, так называемые, представительские данные - строковые данные, каждое из которых распологается в файле с новой строки:

1. Строка с номером варианта,

2. Строка с русским названием модуля,

3. Строка с координатами студента (ФИО, факультет, курс, группа),

4. Строка с датой исполнения.

Далее следуют строки файла с числовыми исходными данными:

1. Управляющий вектор kl - отдельная строка состоящая из трёх чисел kl₁ , kl₂ , kl₃:

kl₁=0, если необходимо получить решение только прямой задачи.

kl₁=1, если необходимо получить решение только двойственной задачи.

kl₁=2, если необходимо получить решение обеих задач.

kl₂=0, если нет свободных переменных, иначе kl₂ равен числу этих нуль-уравнений.

2. Число ограничений и переменных (отдельная строка ввода).

3. Коэффициенты расширенной матрицы a, начиная с отдельной строки ввода.

4. Вектор номеров свободных переменных, если они есть, начиная с отдельной строки ввода.

Результаты решения зависят от значения kl .

Если kl₁=0, то при благоприятном исходе это будет вектор оптимального решения прямой задачи и оптимальное значение целевой функции. При неблагоприятном исходе, это одно из сообщений: либо "Система ограничений несовместна", либо "Целевая функция неограничена".

Если kl₂=1, то же для двойственной задачи.

Если kl₂=2, то сначала выдается решение прямой, а потом двойственной задачи. При не благоприятном исходе сообщения справедливы только для прямой задачи (для двойственной аналогичные сообщения не выдаются). Результаты помещаются в файл simp.res.

3.2 Описание модуля типов.

Для задания типов и файловых переменных вводного и выводного текстовых файлов используется модуль типов unit typesm, структура которого приведена ниже

unit typesm;

interface

const

mmax=20; nmax=20; e=1e-5;

type

klt =array[1..3] of integer;

at =array[1..mmax+1,1..nmax+1] of real;

vec1it =array[1..nmax] of integer;

vec2it =array[1..mmax] of integer;

vec1rt =array[1..nmax] of real;

vec2rt =array[1..mmax] of real;

var

fi, fo:text;

implementation

end.

В разделе констант заданы константы nmax и mmax, задающие максимальное число строк расширенной матрицы a без единицы, а также пороговая константа е, используемая в модуле поиска разрешающей строки. Константа е используется для обеспечения устойчивости алгоритма (модуль разрешающего элемента не должен быть слишком мал, а именно, больше е).

Ниже приведена таблица фактических и формальных параметров подпрограмм задач линейного программирования. Обозначения формальных и фактических параметров совпадают.

N/N	Назначение	Обозначение	Тип
1.	Управляющий вектор	k1	ki1t
2.	Число ограничений	m	integer
3.	Число переменных	n	integer
4.	Матрица коэффициентов	a	at
5.	Вектор номеров свободных переменных	i1	vec1it
6.	Отслеживающий вектор основных переменных прямой задачи	p1	vec1it
7.	Отслеживающий вектор вспомогательных переменных двойственной задачи	q1	vec1it
8.	Отслеживающий вектор вспомогательных переменных прямой задачи	p2	vec2it
9.	Отслеживающий вектор основных переменных двойственной задачи	q2	vec2it
10.	Разрешающая строка	r	integer
11.	Разрешающий столбец	s	integer
12.	Вектор-решение прямой задачи	x	vec1rt
13.	Вектор-решение двойственной задачи	u	vec2rt

4.2 Укрупненная блок-схема задачи линейного программирования.

5.2 Параметры и заголовки процедур задачи линейного программирования.

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

m,n,r,s:integer;{числовые переменные целого типа}

Процедуры программы:

N/N	Назначение	Заголовок
1.	Ввод и контроль исходных данных и вывод их в файл результатов	input(var k1:k1t; var m,n:integer; var a:at, var i1:vec1it; var p1,q1:vec1it; var p2,q2:vec2it)
2.	Исключение свободных переменных	issp(var k1:k1t; m,n:integer; var a:at; var i1,p1,q1:vec1it; var p2,q2: vec2it)
3.	Исключение нуль-уравнений	isnu(var k1:k1t; m,n:integer; var a:at; var p1,q1:vec1it; var p2,q2: vec2it)
4.	Поиск опорного решения	opor(m,n:integer; var a:at; var p1,q1:vec1it; var p2,q2: vec2it)
5.	Поиск оптимального решения	optim(m,n:integer; var a:at; var p1,q1:vec1it; var p2,q2: vec2it)
6.	Вывод решения прямой задачи	outp(m,n:integer; var a:at; var p2: vec2it; x:vec1rt)
7.	Вывод решения двойственной задачи	outd(m,n:integer; var a:at; var q1: vec1it; u:vec2rt)
8.	МЖИ	mji ( m,n:integer; var a:at; r,s:integer)
9.	Поиск разрешающей строки	nstro(m,n:integer; var a:at; r,s:integer var p2:vec2it)

6.2 Блок-схема и параметры реализованной процедуры.

r=1

да

нет

p2_r<0

p1(|p2_r|)=-1

P=0

p1_j>0

j=1

нет

да

нет

|a_rj|>p

да

p=|a_rj| s=j

j=n

да

P=0

нет

"Искл. r-ое нуль-ур. Нельзя"

MJI(m,n,a,r,s)

p2_r=p1_s p1_s=-1

t=q2_r q2_r=q1_s q1_s=t

Закрыть файлы

r=k

Обращащение: isnu(k1,m,n,a,p1,q1,p2,q2). Используются модули typesm, mjim.

Параметры подпрограммы isnu:

Наименование	Обозначение
Число ограничений	m
Число переменных	n
Матрица задачи	a
Отслеживающие векторы	p1, q1, p2, q2

В итоге успешной работы алгоритма все нуль-уравнения будут исключены, и в отслеживающем векторе p1 это будет отмечено как -1, что даст возможность в дальнейшем соответствующие столбцы матрицы А при выборе разрешающего элемента не трогать. Если же алгоритм применить нельзя, то будет выдано сообщение (см. блок-схему), и работа программы закончится.

7.2 Листинг модуля, исходных данных и результатов машинного расчета.

unit isnum;

interface

uses typesm,mjim;

procedure isnu(var k1:k1t;m,n:integer; var a:at;

var p1,q1:vec1it; var p2,q2:vec2it);

implementation

procedure isnu;

var p:real;k,s,r,j,t:integer;

begin

for r:=1 to k do begin

if p2[r]<0 then p1[abs(p2[r])]:=-1;end;

p:=0;

for j:=1 to n do begin

if p1[j]>0 then begin

if abs(a[r,j])>p then begin p:=abs(a[r,j]);s:=j;end;

end;end;

if p=0 then begin writeln(fo,'Исключить r',r:6,'-ое нуль-уравнение нельзя');

close(fi);close(fo);halt end;

mji(m,n,a,r,s);

p2[r]:=p1[s];p1[s]:=-1;

t:=q2[r];q2[r]:=q1[s];q1[s]:=t;

end;

end.

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

Исключение нуль-уравнений

Моносов ЭОУС-1-2 преподаватель Марьямов А. Г.

12.05.98

2 2 0

5 3

-2 -1 1 -2

1 -1 0 -1

-1 -1 0 -2

0 1 0 2

2 1 0 4

4 4 0 0

1 2

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

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ СТРОИТЕЛЬНЫЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАТИКИ И ПРИКЛАДНОЙ МАТЕМАТИКИ

Лабораторная работа по информатике

Факультет ЭОУС, 2-ой семестр обучения

Решение задачи линейного программирования

Вариант 12

модуль: Исключение нуль-уравнений

Исполнил студент Моносов ЭОУС-1-2 преподаватель Марьямов А. Г.

Дата исполнения: 12.05.98

Управляющий вектор:

2 2 0

Число ограничений: 5

Число переменных: 3

Матрица задачи

Н-р Коэффициенты Св. члены

строки

1 -2.00000 -1.00000 1.00000 -2.00000

2 1.00000 -1.00000 0.00000 -1.00000

3 -1.00000 -1.00000 0.00000 -2.00000

4 0.00000 1.00000 0.00000 2.00000

5 2.00000 1.00000 0.00000 4.00000

6 4.00000 4.00000 0.00000 0.00000

Вектор номеров свободных переменных:

1 2

Вектор решения прямой задачи:

1.00000 2.00000 3.00000

Значение целевой функции прямой задачи= 12.00000

Вектор решения двойственной задачи:

0.00000 4.00000 0.00000 8.00000 0.00000

Значение целевой функции двойственной задачи= 12.00000

8.2 Ручной расчет задачи линейного программирования.

Требуется максимизировать функцию

z=4x₁+5x₂

при ограничениях:

-2x₁-x₂+x₃=-2

x₁-x₂ -1

- x₁ - x₂  -2

0x₁+ 1x₂  2

2x₁+ 1x₂  4

x₃ 0

Коэфициенты ограничений, записанных в таком виде, переписываются со своими знаками, в последней строке таблицы записываются коэффициенты целевой функции с противоположными знаками. Сперва следует исключить свободные переменные, перекинув их на бок таблицы:

	-x₁	-x₂	-x₃	1
0=	-2	-1	1	-2
y₂=	1	-1	0	-1
y₃=	-1	-1	0	-2
y₄=	0	1	0	2
y₅=	2	1	0	4
z=	-4	-4	0	0

	-x₁	-y₄	-x₃	1
0=	-2	1	1	0
y₂=	1	1	0	1
y₃=	-1	1	0	0
*x₂=	0	1	0	2
y₅=	2	-1	0	2
z=	-4	4	0	8

	-y₂	-y₄	-x₃	1
0=	-2	3	1	2
*x₁=	1	1	0	1
y₃=	-1	2	0	0
*x₂=	0	1	0	2
y₅=	2	-3	0	0
z=	4	8	0	12

После этого следует исключить нуль-уравнение:

			*
	-y₂	-y₄	-y₁	1
x₃=	-2	3	1	2
*x₁=	1	1	0	1
y₃=	-1	2	0	0
*x₂=	0	1	0	2
y₅=	2	-3	0	0
z=	4	8	0	12

Мы видим, что свободные члены в непомеченных строках неотрицательны, следовательно опорное решение получено и надо перейти к поиску оптимального решения. Находим непомеченные столбцы с отрицательными коэфициентами целевой функции, исключая последний. У нас таких нет, поэтому оптимальное решение получено и переходим к извлечению результатов. Для этого составим еще одну таблицу, где содержаться переменные прямой и двойственной задач. Для извлечения решений нужны только столбец свободных членов и строка коэффициентов целевой функции. Поэтому внутренняя часть таблицы не преведена.

		u₂=	u₄=	u₁=	w=
		-y₂	-y₄	-y₁	1
v₃=	x₃=	-2	3	1	2
v₁=	x₁=	1	1	0	1
u₃=	y₃=	-1	2	0	0
v₂=	x₂=	0	1	0	2
u₅=	y₅=	2	-3	0	0
1	z=	4	8	0	12

В итоге получаем следующие результаты:

Прямая задача. Переменные прямой задачи, находящиеся сверху таблицы равны в решении 0, а сбоку - соответствующим свободным членам:

x₁=1; x₂=2; x₃=2.

Двойственная задача. Переменные двойственной задачи, находящиеся сверху таблицы равны 0, а сбоку - соответствующим коэфициентам целевой функции:

u₁=0; u₂=4; u₃=0; u₄=8; u₅=0.

Значение целевых функций обеих задач z_max= w_min=12.

9.2 Выводы.

Полученные результаты при ручном расчёте совпадают с данными машинного счёта. Это подтверждает правильность составления алгоритма и написания программы.

Список использованной литературы.

Турчак Л. И. "Основы численных методов".

Марьямов А. Г. "Применение модульного способа програмирования в среде Turbo Pascal 7.0 с целью решения полной задачи линейного программирования".

Bukvasha