скачать рефераты
  RSS    

Меню

Быстрый поиск

скачать рефераты

скачать рефератыРеферат: Аппроксимация

Номера свободных переменных запоминаются отдельно.

Совместим таблицу двойственной задачи с таблицей. 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 Блок-схема и параметры реализованной процедуры.

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=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 с целью решения полной задачи линейного программирования".



Страницы: 1, 2, 3


Новости

Быстрый поиск

Группа вКонтакте: новости

Пока нет

Новости в Twitter и Facebook

  скачать рефераты              скачать рефераты

Новости

скачать рефераты

Обратная связь

Поиск
Обратная связь
Реклама и размещение статей на сайте
© 2010.