Реферат: Аппроксимация
Номера свободных переменных запоминаются отдельно.
Совместим таблицу двойственной задачи с таблицей. 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 = a1j u1 + 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] 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 Блок-схема и параметры реализованной процедуры.
|
|
|||
Обращащение: 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=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 с целью решения полной задачи линейного программирования".