Аппроксимация

предприятие выпускает 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), чтобы при

выполнение условий

|a11x1 + a12x2 + … + a1nxn (|

|b1 |

|a21x1 + a22x2 + … + a2nxn (|

|b2 |

|…………………………….……………………. |

|am1x1 + am2x2 + … + amnxn (|

|bm |

|xj ( 0, (j=1,…,n). |

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

Z= p1x1 + p2x2 + … + pnxn

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

i-е ограничение из (1) означает, что нельзя израсходовать i-го

ингредиента больше, чем имеется в наличии. Ограничения (1) задают множество

(. Переменные, удовлетворяющие условию 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), чтобы выполнялись

условия:

|a11u1 + a21u2 + … + am1um (|

|p1 |

|a12u1 + a22u2 + … + am2um (|

|p2 |

|…………………………….……………………. |

|a1nu1 + a2nu2 + … + amnum (|

|pn |

|ui ( 0, (i=1,…,m) |

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

W=b1u1 + … + bmum

j-ое условие (2) означает, что стоимость всех ингридиентов, идущ на

производство j-го изделия, не меньше рыночной цены этого изделия.

Условие несвободности uj(0 означает, что j-й ингредиент либо бесплатен

(uj=0), либо стоит положительное количество рублей (uj >0).

Опорным решением задачи (1)-(1') называется точка множества (, в которой

не менее чем n ограничений из (1) обращается в верное равенство. Это - так

называемая, угловая точка множества. Для n=2 это - вершина плоского угла.

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

чем m ограничений из (2) обращается в верное равенство.

В задаче (1)-(1') опорное решение - точка х=(0,…,0), начало координат. В

задаче (2)-(2') начало координат - точка u=(0,…,0), опорным решением не

является.

Опорное решение, доставляющее максимум функции (1') или минимум функции

(2') называется оптимальным. В работе [1] показано, что оптимальное решение

можно всегда искать среди опорных решений.

Среди линейных ограничений задачи (1)-(1') кроме неравенств могут быть и

равенства. Тогда условимся писать эти равенства первыми. Если их количество

равно k, то область ( запишется в виде:

|a11x1 + a12x2 + … + a1nxn = |

|b1 |

|…………………………….……………………… |

|ak1x1 + ak2x2 + … + aknxn = |

|bk |

|ak+1, 1x1+ak+1, 2x2+…+ak+1, n|

|xn(bk+1 |

|…………………………….……………………… |

|am1x1 + am2x2 + … + amnxn ( |

|bm |

|xj ( 0, (j=1,…,n) |

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

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 в виде:

|0 = a11 (-x1) + a12 (-x2) + … + a1n |

|(-xn) + a1, n+1 |

|…………………………………………………….……………………………………… |

|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,|am+1, |

| | | | |n |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,|ak+1, |

| | | | | |n |n+1 |

| |…… |…………………………… |……… |

|um |ym = |am1 |am2 |… |amn |am, n+1 |

|1 |Z = |am+1, n|am+1, 2|… |am+1,|am+1, |

| | | | | |n |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) в другую

вершину многогранника ( по его ребру. Элемент а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 |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=1

i=n

i=1

i=n

i=1

i=m

j=1

j=m

j=1

j=n

j=1

j=n

i=1

i=n

j=m+1

j=1

шаг=-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

да

нет

j=1

j=n

нет

нет

да

да

да

нет

=

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