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

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

 

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

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

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

на темы:

1.  Аппроксимация.

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

Выполнил студент ЭОУС – 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.

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

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

  

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

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

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

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

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

g(x)=a0+a1x+a2x2+…+amxm(2.1)

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

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

 

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

  

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

   При этомпредполагается, что среди значений xi нет одинаковых, т.е. xi¹xk при<sub/>этом i¹k. Точки xiназываютсяузлами интерполяции, а многочлен g(x) — интерполяционныммногочленом.

  

/> /> /> /> /> /> /> /> /> /> /> /> <td/> <td/>

X

  /> />

Рис. 1

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

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

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

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

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

                                                      n

S = å[g(xi)-yi]2

                                                      i=0

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

               

                        n

dS/da1=2å[ g(xi)-yi]2*1=0;

               i=1

                

                         n

dS/da2=2å[ g(xi)-yi]2*xi=0;

                       i=1

               

              …

               

                   n

dS/dam+1=2å[ g(xi)-yi]2*xim=0.

                            i=1

 

                                                             C                              A               B

n

å xi

å xim

a1

åyi

=

  å xi

å xi2

å xim+1

a2

åyixi

… …… … …… … …

å xim

å xim+1

å xi2m

am+1

åyixim

 

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


/>  

  

/> /> /> /> /> />

i=1

  /> /> />

i=n

  />  

/>


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

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

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

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

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

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

  Результаты:

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

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

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

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

 

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

 

programapprox;

usescrt,gausstpu;

constnm=20;

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

varc:matr;

      a,b:vect;

      x,y,z:vect1;

      n,i,j,m:integer;

      f1,f2:text;

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

vari,j:integer;

     r:vect;

begin

fori:=1 to n do

r[i]:=1;

forj:=1 to m+1 do begin

c[1,j]:=0;

b[j]:=0;

fori:=1 to n do begin

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

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

end;

fori:=1 to n do

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

end;

fori:=1 to m do begin

forj:=1 to m do

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

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

forj:=1 to n do

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

forj:=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]');

fori:=1 to n do begin

read(f1,x[i]);

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

end;

writeln(f2);

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

fori:=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,'Матрицасистемы линейных уравнений для аппроксимации и вектор правых частей);

fori:=1 to m+1 do begin

forj:=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);

fori:=1 to n do begin

z[i]:=0;

forj:=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 элементов)');

fori:=1 to m+1 do

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

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

fori:=1 to n do

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

close(f1);close(f2);

end.

          

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

 

10

2

16 0 3 8 2 12 9 2 5

94 13 7 3 9 3 1 4 2

 

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

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

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

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

1.00 6.00 0.00 3.008.00 2.00 12.00 9.00 2.00 5.00

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

9.00 4.00 13.00 7.003.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 Список переменныхосновной программы.

 

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

constnm=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; varx,y:vect1; var c:matr; var b:vect);

    var i,j:integer;

          r:vect;

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

Переменная

Тип переменной

Описание переменной

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

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

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

n

Sxi

Sxi2

Syi

Sxi

Sxi2

Sxi3

Sxiyi

Sxi2

Sxi3

Sxi4

Sxi2yi

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

n=10;

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

Sxi2=12+62+02+32+82+22+122+92+22+52=368;

Syi=9+4+13+7+3+9+3+1+4+2=55;

Sxi3=13+63+03+33+83+23+123+93+23+53=3354;

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

Sxi3=14+64+04+34+84+24+124+94+24+54=33428;

Sxi2yi=12*9+62*4+02*13+32*7+82*3+22*9+122*3+92*1+22*4+52*2=1023.

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

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

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

 {

 

10a1 +48a2 + 368a3 = 55

48a1 +368a2 + 3354a3 = 159

368a1 +3354a2 + 33428a3 = 1023

 

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

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

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

/> <td/>

{

 

1568,203488a3= 210,4680233

137,6a2+ 1587,6a3 = -105

10a1 +48a2 + 368a3 = 55

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

/> <td/>

{

 

a3=210,4680233/1568,203488=0,134209638

a2=(-105-1587,6a3)/137,6=-2,311564115

a1=(55-48a2-368a3)/10=11,65659307

 

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

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

 

9.1 Выводы.

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

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

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

  

   Рассмотрим задачуоптимального планирования производства [1]. Пусть предприятие выпускает n изделий, дляпроизводства которых используется m ингредиентов. Ингредиенты это – деталиопределенного сортамента, станки, работники, электроэнергия и т.д., иначеговоря, все что требуется дляосуществления производственного цикла. Запасы ингредиентов задаются вектором b=(b1,b2,…, bm ), где bi  - запас i-го ингридиента (i=1,…,m). Задана матрица А,элемент которой aij определяет расход i-го ингридиента дляпроизводства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, заданвектор рыночных цен изделий p=(p1, p2,…, pn), где p  — цена j-го изделия (j=1,…,n).

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

a11x1 + a12x2 + … + a1nxn £ b1

(1)

  a21x1 + a22x2 + … + a2nxn £ b2

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

am1x1 + am2x2 + … + amnxn £ bm

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

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

/> <td/>

(1')

 

Z= p1x1+ p2x2 + … + pnxn

 

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

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

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

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

   Сформулируем двойственную к (1)-(1') задачу о приобритенииингридиентов по минимальной рыночной стоимости. Пусть то же самое предприятие,что и в задаче (1)-(1'), собирается приобрести на рынке m ингридиентов дляпроизводства тех же n изделий.При этом количество приобретаемых ингридиентов определяется вектором b=(b1,b2, …, bm). Задана та же матрица А, элемент которой aij определяет расход i-го ингридиента дляпроизводства j-го изделия. Кроме тогозадан вектор цен p=(p1, p2, …, pn) на продукциюпредприятия. Требуется отыскать вектор цен ингридиентов u=(u1,u2, …, um), где ui — цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялисьусловия:

a11u1 + a21u2 + … + am1um ³ p1

(2)

  a12u1 + a22u2 + … + am2um ³ p2

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

a1nu1 + a2nu2 + … + amnum ³ pn

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

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

/> <td/>

(2')

 

W=b1u1+ … + bmum

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

   Условие несвободности uj³0 означает, что j-йингредиент либо бесплатен (uj=0), либо стоит положительноеколичество рублей (uj >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 запишется в виде:

a11x1 + a12x2 + … + a1nxn = b1

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

(3)

  ak1x1 + ak2x2 + … + aknxn = bk

ak+1, 1x1+ak+1, 2x2+…+ak+1, n xn£bk+1

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

am1x1 + am2x2 + … + amnxn  £ bm

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

 

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

/> <td/>

(3')

 

Z=p1x1+ p2x2 + … + pnxn

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

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

a1ju1 + a2j u2 + … + amj um=pj

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

 

0 =  a11  (-x1)   +   a12  (-x2)  +  …  +   a1n  (-xn)   +   a1, n+1

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

(4)

  0 =  ak1   (-x1)   +   ak2  (-x2)  +  …  +   akn  (-xn)  +  ak, 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<sub/>= 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 = a1ju1 + a2j u2 + … + amj um+ am+1, j ³ 0, если xj ³ 0

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

0=a1j u1+ a2j u2 + … + amj um + am+1,j

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

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

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

W= a1, n+1 u1+ a2, n+1 u2 + … + am, n+1 um + am+1,n+1

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

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

   Сделаем заменупеременных в таблице 1, перебросив вспомогательную переменную yr  наверх таблицы со знаком минус, а основную пременную xs на бок таблицы (ars¹0). Этоозначает движение из вершины x=(0, …, 0) в другую вершину многогранника W по егоребру. Элемент аrs называется разрешающим, строка r — разрешающейстрокой, столбец s — разрешающим столбцом. Такая замена переменных носитназвание модифицированных жордановых исключений (МЖИ). Элементы матрицы а, непринадлежащие разрешающему столбцу или разрешающей строке, назовем рядовыми.

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

 

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

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

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

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

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

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

1. Управляющий вектор kl — отдельная строкасостоящая из трёх чисел kl1, kl2, kl3:

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

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

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

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

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

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

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

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

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

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

   Если kl2=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] ofreal;

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

    /> /> /> /> /> /> /> <td/>

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(vark1:k1t;m,n:integer; var a:at;

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

implementation

procedure isnu;

varp:real;k,s,r,j,t:integer;

begin

for r:=1 to k do begin

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

p:=0;

for j:=1 to n do begin

if p1[j]>0 thenbegin

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

end;end;

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

close(fi);close(fo);haltend;

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:

12

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

Моносов ЭОУС-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=4x1+5x2

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

-2x1-x2+x3=-2

x1-x2£ -1

— x1 — x2 £ -2

0x1+1x2 £ 2

2x1 +1x2 £ 4

x3 ³ 0

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

-x1

-x2

-x3

1 0= -2 -1 1 -2

y2=

1 -1 -1

y3=

-1 -1 -2

y4=

1 2

y5=

2 1 4 z= -4 -4

-x1

-y4

-x3

1 0= -2 1 1

y2=

1 1 1

y3=

-1 1

*x2=

1 2

y5=

2 -1 2 z= -4 4 8

 

-y2

-y4

-x3

1 0= -2 3 1 2

*x1=

1 1 1

y3=

-1 2

*x2=

1 2

y5=

2 -3 z= 4 8 12

 

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

*

-y2

-y4

-y1

1

x3=

-2 3 1 2

*x1=

1 1 1

y3=

-1 2

*x2=

1 2

y5=

2 -3 z= 4 8 12

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

u2=

u4=

u1=

w=

-y2

-y4

-y1

1

v3=

x3=

-2 3 1 2

v1=

x1=

1 1 1

u3=

y3=

-1 2

v2=

x2=

1 2

u5=

y5=

2 -3 1 z= 4 8 12

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

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

x1=1; x2=2; x3=2.

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

u1=0; u2=4; u3=0; u4=8;  u5=0.

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

 

9.2 Выводы.

 

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

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

 

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

·    МарьямовА. Г. «Применение модульного способа програмирования в среде Turbo Pascal7.0 сцелью решения полной задачи линейного программирования».


еще рефераты
Еще работы по информатике, программированию