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

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

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.

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

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

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

 

9.2 Выводы.

 

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

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

 

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

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