Обсудим исходные данные (текстовой файл 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 |intege| | | | |r | |3. |Число переменных |n |intege| | | | |r | |4. |Матрица коэффициентов |a |at | |5. |Вектор номеров свободных переменных |i1 |vec1it| |6. |Отслеживающий вектор основных |p1 |vec1it| | |переменных прямой задачи | | | |7. |Отслеживающий вектор вспомогательных|q1 |vec1it| | |переменных двойственной задачи | | | |8. |Отслеживающий вектор вспомогательных|p2 |vec2it| | |переменных прямой задачи | | | |9. |Отслеживающий вектор основных |q2 |vec2it| | |переменных двойственной задачи | | | |10. |Разрешающая строка |r |intege| | | | |r | |11. |Разрешающий столбец |s |intege| | | | |r | |12. |Вектор-решение прямой задачи |x |vec1rt| |13. |Вектор-решение двойственной задачи |u |vec2rt|
4.2 Укрупненная блок-схема задачи линейного программирования.
[pic]
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 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 с целью решения полной задачи линейного программирования".
-----------------------
C1j=C1j+Ri
Bj=Bj+Ri*Yi
C1j=0, Bj=0
Ri=1
Ввод n, m, X, Y
Y0 Y1 . . . Yn
Y
X
X0 X1 . . . Xn
Ri=Ri*Xi
Ci+1, j=Ci, j+1
Ci+1, m+1=0
Ci+1, m+1=Ci+1, m+1 +Rj
Rj=Rj*Xj
Решение системы линейных уравнений Gauss(m+1,C,B,A)
Zi=0
Zi=Zi*Xi+Aj
Zi=Zi*Yi
K
Вывод A, Z
i=1
i=n
j=1
j=m+1
Расчет первой строки матрицы С и вектора В
i=m
j=m
j=n
j=1 j=n
шаг=-1
Расчет остальных строк матрицы С
(1)
(1')
(2)
(2')
(3)
(3')
(4)
{
p1(|p2r|)=-1
p2r0
|arj|>p
p=|arj| s=j
P=0
MJI(m,n,a,r,s)
p2r=p1s p1s=-1 t=q2r q2r=q1s q1s=t
B
"Искл. r-ое нуль-ур. Нельзя"
Закрыть файлы
К
r=1
r=k
да
нет
=
Страницы: 1, 2, 3
