44559 (663416), страница 4

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 4)

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 без единицы, а также пороговая константа е, используемая в модуле поиска разрешающей строки. Константа е используется для обеспечения устойчивости алгоритма (модуль разрешающего элемента не должен быть слишком мал, а именно, больше е).

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

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

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

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

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

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

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

B

Обращащение: 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:

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=4x₁+5x₂

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

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

x₁-x₂ -1

- x₁ - x₂  -2

0x₁+ 1x₂  2

2x₁ + 1x₂  4

x₃  0

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

	-x1	-x2	-x3	1
0=	-2	-1	1	-2
y2=	1	-1	0	-1
y3=	-1	-1	0	-2
y4=	0	1	0	2
y5=	2	1	0	4
z=	-4	-4	0	0

	-x1	-y4	-x3	1
0=	-2	1	1	0
y2=	1	1	0	1
y3=	-1	1	0	0
*x2=	0	1	0	2
y5=	2	-1	0	2
z=	-4	4	0	8

	-y2	-y4	-x3	1
0=	-2	3	1	2
*x1=	1	1	0	1
y3=	-1	2	0	0
*x2=	0	1	0	2
y5=	2	-3	0	0
z=	4	8	0	12

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

			*
	-y2	-y4	-y1	1
x3=	-2	3	1	2
*x1=	1	1	0	1
y3=	-1	2	0	0
*x2=	0	1	0	2
y5=	2	-3	0	0
z=	4	8	0	12

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

		u2=	u4=	u1=	w=
		-y2	-y4	-y1	1
v3=	x3=	-2	3	1	2
v1=	x1=	1	1	0	1
u3=	y3=	-1	2	0	0
v2=	x2=	0	1	0	2
u5=	y5=	2	-3	0	0
1	z=	4	8	0	12

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

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

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

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

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

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

9.2 Выводы.

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

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

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

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

Характеристики

Список файлов реферата