Аппроксимация (стр. 4 из 4)
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 Блок-схема и параметры реализованной процедуры.
 |
| Наименование | Обозначение |
| Число ограничений | 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=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 | 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, а сбоку - соответствующим свободным членам:
x1=1; x2=2; x3=2.
2. Двойственная задача. Переменные двойственной задачи, находящиеся сверху таблицы равны 0, а сбоку - соответствующим коэфициентам целевой функции:
u1=0; u2=4; u3=0; u4=8; u5=0.
Значение целевых функций обеих задач zmax= wmin=12.
9.2 Выводы.
Полученные результаты при ручном расчёте совпадают с данными машинного счёта. Это подтверждает правильность составления алгоритма и написания программы.
Список использованной литературы.
· Турчак Л. И. "Основы численных методов".
· Марьямов А. Г. "Применение модульного способа програмирования в среде Turbo Pascal 7.0 с целью решения полной задачи линейного программирования".