Аппроксимация
Опорным решением задачи (2)-(2') называется точка, в которой не менее чем m ограничений из (2) обращается в верное равенство.
В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не является.
Опорное решение, доставляющее максимум функции (1') или минимум функции (2') называется оптимальным. В работе [1] показано, что оптимальное решение можно всегда искать среди опорных решений.
Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и равенства. Тогда условимся писать эти равенства первыми. Если их количество равно k, то область запишется в виде:
|
a11x1 + a12x2 + … + a1nxn = b1 |
|
…………………………….……………………… |
|
(3) ak1x1 + ak2x2 + … + aknxn = bk |
|
ak+1, 1x1+ak+1, 2x2+…+ak+1, n xnbk+1 |
|
…………………………….……………………… |
|
am1x1 + am2x2 + … + amnxn bm |
|
xj 0, (j=1,…,n) |
Требуется найти максимум функции
(3')
Z=p1x1 + p2x2 + … + pnxn
В общем случае среди переменных xj могут быть свободные. Номера свободных переменных будем хранить в отдельном массиве.
При формировании двойственной задачи к задаче (3)-(3') i-му ограничению - равенству будет соответствовать свободная переменная ui (i=1,…,k), а свободной переменной xj ограничение - равенство:
a1j u1 + a2j u2 + … + amj um =pj
Введем вспомогательные переменные yi0 (i=1,…,n) и запишем ограничения (3) и функцию Z в виде:
|
0 = a11 (-x1) + a12 (-x2) + … + a1n (-xn) + a1, n+1 |
|
…………………………………………………….……………………………………… |
|
(4) 0 = ak1 (-x1) + ak2 (-x2) + … + akn (-xn) + ak, n+1 |
|
yk+1 = ak+1, 1 (-x1) + ak+1, 2(-x2)+ … + ak+1, n(-xn) + ak+1, n+1 |
|
…………………………………………………….……………………………………… |
|
ym = am1 (-x1) + am2 (-x2) + … + amn(-xn) + am, n+1 |
|
Z = am+1, 1 (-x1) + am+1, 2(-x2)+ … + am+1, n(-xn) + am+1, n+1 |
Условие несвободности отдельных или всех переменных здесь не отмечено. Обозначения:
ai, n+1 = bi (i=1, …, m),
am+1, j = -pj (j=1, …, n)
am+1, n+1 = 0.
Таким образом, матрицу а мы дополнили столбцом свободных членов и строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:
Прямая задача Таблица 1
|
-x1 |
-x2 |
-xn |
1 |
||
|
0 = |
a11 |
a12 |
… |
a1n |
a1, n+1 |
| …… | …………………………… | ……… | |||
|
0 = |
.. |
ak, n+1 |
|||
|
yk+1 = |
ak1 |
ak2 |
… |
akn |
ak+1, n+1 |
| …… |
ak+1, 1 |
ak+1, 2 |
… |
ak+1, n |
……… |
|
ym = |
…………………………… | ……… | |||
|
am1 |
am2 |
… |
amn |
am, n+1 |
|
|
Z = |
am+1, n |
am+1, 2 |
… |
am+1, n |
am+1, n+1 |
Номера свободных переменных запоминаются отдельно.
Совместим таблицу двойственной задачи с таблицей. 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 на бок таблицы (ars0). Это означает движение из вершины x=(0, …, 0) в другую вершину многогранника по его ребру. Элемент а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 Блок-схема и параметры реализованной процедуры.
r=1

![]()
да
нет
p2r<0
p1(|p2r|)=-1

![]()
P=0
![]()
![]()
![]()
![]()

![]()

![]()
p1j>0
j=1
нет
да
![]()
нет
|arj|>p
![]()
![]()
да
![]()
p=|arj| s=j
j=n
да
P=0
![]()
![]()
нет
"Искл. r-ое нуль-ур. Нельзя"
MJI(m,n,a,r,s)
![]()
p2r=p1s p1s=-1
t=q2r q2r=q1s q1s=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=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 |
В итоге получаем следующие результаты:
Прямая задача. Переменные прямой задачи, находящиеся сверху таблицы равны в решении 0, а сбоку - соответствующим свободным членам:
x1=1; x2=2; x3=2.
Двойственная задача. Переменные двойственной задачи, находящиеся сверху таблицы равны 0, а сбоку - соответствующим коэфициентам целевой функции:
u1=0; u2=4; u3=0; u4=8; u5=0.
Значение целевых функций обеих задач zmax= wmin=12.
9.2 Выводы.
Полученные результаты при ручном расчёте совпадают с данными машинного счёта. Это подтверждает правильность составления алгоритма и написания программы.
Список использованной литературы.
Турчак Л. И. "Основы численных методов".
Марьямов А. Г. "Применение модульного способа програмирования в среде Turbo Pascal 7.0 с целью решения полной задачи линейного программирования".