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

II.       Экономическая часть. Разработка модуля исключения нуль-уравнений в комплексе “Решение задачи линейного программирования”.

1.2 Постановка задачи линейного программирования и задание на разработку модуля.

   Рассмотрим задачу оптимального планирования производства [1]. Пусть предприятие выпускает n изделий, для производства которых используется m ингредиентов. Ингредиенты это – детали определенного сортамента, станки, работники, электроэнергия и т.д., иначе говоря, все что требуется для осуществления производственного цикла. Запасы ингредиентов задаются вектором b=(b1, b2,…, bm ), где bi  - запас i-го ингридиента (i=1,…,m). Задана матрица А, элемент которой aij определяет расход i-го ингридиента для производства единицы j-го изделия (i=1,…,m; j=1,…,n). Кроме того, задан вектор рыночных цен изделий p=(p1, p2,…, pn), где p  - цена j-го изделия (j=1,…,n).

   Требуется составить такой план производства х=(х1, х2,…, хn), чтобы при выполнение условий

достигался максимум функции

	(1')

Z= p1x1 + p2x2 + … + pnxn

Функция Z называется целевой.

    i-е ограничение из (1) означает, что нельзя израсходовать i-го ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество W. Переменные, удовлетворяющие условию xj³0, называются несвободными. В нашей задаче это означает, что при xj=0 - ничего не производится или при xj>0 производится некоторое количество изделий.

   Переменные, на которые условия неотрицательности не накладываются, называются свободными.

   Задача (1)-(1') и есть задача оптимального производственного планирования, решение которой обеспечивает достижение в конкретных условиях максимальной прибыли.

   Сформулируем двойственную к (1)-(1') задачу о приобритении ингридиентов по минимальной рыночной стоимости. Пусть то же самое предприятие, что и в задаче (1)-(1'), собирается приобрести на рынке m ингридиентов для производства тех же n изделий. При этом количество приобретаемых ингридиентов определяется вектором b=(b1, b2, …, bm). Задана та же матрица А, элемент которой aij определяет расход i-го ингридиента для производства j-го изделия. Кроме того задан вектор цен p=(p1, p2, …, pn) на продукцию предприятия. Требуется отыскать вектор цен ингридиентов u=(u1, u2, …, um), где ui - цена единицы i-го ингридиента (i=1, …,m), чтобы выполнялись условия:

при достижении минимума целевой функции

	(2')

W=b1u1 + … + bmum

j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на производство j-го изделия, не меньше рыночной цены этого изделия.

   Условие несвободности uj³0 означает, что j-й ингредиент либо бесплатен (uj=0), либо стоит положительное количество рублей (uj >0).

   Опорным решением задачи (1)-(1') называется точка множества W, в которой не менее чем n ограничений из (1) обращается в верное равенство. Это - так называемая, угловая точка множества. Для n=2 это - вершина плоского угла.

   Опорным решением задачи (2)-(2') называется точка, в которой не менее чем m ограничений из (2) обращается в верное равенство.

   В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не является.

   Опорное решение, доставляющее максимум функции (1') или минимум функции (2') называется оптимальным. В работе [1] показано, что оптимальное решение можно всегда искать среди опорных решений.

   Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и равенства. Тогда условимся писать эти равенства первыми. Если их количество равно k, то область W запишется в виде:

Требуется найти максимум функции

	(3')

Z=p1x1 + p2x2 + … + pnxn

   В общем случае среди переменных xj  могут быть свободные. Номера свободных переменных будем хранить в отдельном массиве.

   При формировании двойственной задачи к задаче (3)-(3') i-му ограничению - равенству будет соответствовать свободная переменная ui (i=1,…,k), а свободной переменной xj ограничение - равенство:

a1j u1 + a2j u2 + … + amj um =pj

   Введем вспомогательные переменные yi³0 (i=1,…,n) и запишем ограничения (3) и функцию Z в виде:

   Условие несвободности отдельных или всех переменных здесь не отмечено. Обозначения:

ai, n+1 = bi (i=1, …, m),

am+1, j = -pj (j=1, …, n)

am+1, n+1 = 0.

   Таким образом, матрицу а мы дополнили столбцом свободных членов и строкой коэффициентов целевой функции, изменив знаки этих коэффициентов на противоположные. Тогда задачу (4) можно представить в виде таблицы. 1:

Прямая задача                                   Таблица 1

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

Совместим таблицу двойственной задачи с таблицей. 1 и получим таблицу. 2.

Прямая и двойственная задачи                        Таблица 2

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 без единицы, а также пороговая константа е, используемая в модуле поиска разрешающей строки. Константа е используется для обеспечения устойчивости алгоритма (модуль разрешающего элемента не должен быть слишком мал, а именно, больше е).

   Ниже приведена таблица фактических и формальных параметров подпрограмм задач линейного программирования. Обозначения формальных и фактических параметров совпадают.

4.2 Укрупненная блок-схема задачи линейного программирования.

5.2 Параметры и заголовки процедур задачи линейного программирования.

   В основной программе используются следующие переменные, которые описаны в разделе var:

          m,n,r,s:integer;{числовые переменные целого типа}

Процедуры программы:

6.2 Блок-схема и параметры реализованной процедуры.

r=1

			r=k

   Обращащение: isnu(k1,m,n,a,p1,q1,p2,q2). Используются модули typesm, mjim.

   Параметры подпрограммы isnu:

   В итоге успешной работы алгоритма все нуль-уравнения будут исключены, и в отслеживающем векторе 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

   Коэфициенты ограничений, записанных в таком виде, переписываются со своими знаками, в последней строке таблицы записываются коэффициенты целевой функции с противоположными знаками. Сперва следует исключить свободные переменные, перекинув их на бок таблицы:

   После этого следует исключить нуль-уравнение:

   Мы видим, что свободные члены в непомеченных строках неотрицательны, следовательно опорное решение получено и надо перейти к поиску оптимального решения. Находим непомеченные столбцы с отрицательными коэфициентами целевой функции, исключая последний. У нас таких нет, поэтому оптимальное решение получено и переходим к извлечению результатов. Для этого составим еще одну таблицу, где содержаться переменные прямой и двойственной задач. Для извлечения решений нужны только столбец свободных членов и строка коэффициентов целевой функции. Поэтому внутренняя часть таблицы не преведена.

В итоге получаем следующие результаты:

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