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

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

	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