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

<0>

Міністерство загальної та професійної освіти Російської Федерації

Московський державний будівельний університет

Кафедра інформатики та прикладної математики

КУРСОВА РОБОТА ПО ІНФОРМАТИЦІ

на теми:

Апроксимація.
Розробка модуля виключення нуль-рівнянь в комплексі "Рішення задачі лінійного програмування".

Виконав студент ЕОУС - I - 2: Моносов А. Л.

Викладач: доцент Марьям А. Г.

Москва 1999.

Зміст.

I. Математична частина. Назва ... ... ... ... ... ... ... ... ... ... ... ... ... 3.

1.1 Постановка завдання ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .3.

2.1 Виклад методу ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .4.

3.1 Блок-схема алгоритму. Опис вихідних даних і результатів ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 5.

4.1 Лістинг програми, вихідних даних і результатів ... ... ... ... ... 6.

5.1 Список змінних основної програми ... ... ... ... ... ... ... ... ... 10.

6.1 Заголовки процедур і функцій. Список їх змінних ... ... ... .10.

7.1 Ручний розрахунок ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 11.

8.1 Обговорення результатів з метою доказу правильності алгоритму і програми ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 12.

9.1 Висновки ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .13.

II. Економічна частина. Назва ... ... ... ... ... ... ... ... ... ... ... ... .. 14.

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

2.2 Опис вихідних даних і результатів вирішення завдань лінійного програмування ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... 18.

3.2 Опис модуля типів ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .. 19.

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

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

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

7.2 Лістинг модуля, вихідних даних і результатів машинного розрахунку ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .23.

8.2 Ручний розрахунок задачі лінійного програмування ... ... ... ... ... 24.

9.2 Висновки ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .26.

Список використаної літератури. ... ... ... ... ... ... ... ... ... ... ... .. 27.

Математична частина. Апроксимація.

Постановка завдання.

Нехай величина y є функцією аргументу x. Це означає, що будь-якому значенню x з області визначення поставлено відповідно значення y. Разом з тим на практиці часто невідома явний зв'язок між y і x, тобто неможливо записати цей зв'язок у вигляді y = f (x). У деяких випадках навіть при відомій залежності y = f (x) вона настільки громіздка (наприклад, містить важко обчислювані вирази, складні інтеграли і т.п.), що її використання в практичних розрахунках важко.

Найбільш поширеним і практично важливим випадком, коли вид зв'язку між параметрами x і y невідомий, є завдання цієї зв'язку у вигляді деякої таблиці {x _i y _i}. Це означає, що дискретного безлічі значень аргументу {x _i} поставлено у відповідність безліч значень функції {y _i} (i = 0,1 ... n). Ці значення - або результати розрахунків, або експериментальні дані. На практиці нам можуть знадобитися значення величини y і в інших точках, відмінних від вузлів x _i. Однак отримати ці значення можна лише шляхом дуже складних розрахунків або провидінням дорогих експериментів.

Таким чином, з точки зору економії часу і коштів ми приходимо до необхідності використання наявних табличних даних для наближеного обчислення шуканого параметра y при будь-якому значенні (з деякої області) визначального параметра x, оскільки точний зв'язок y = f (x) невідома.

Цій меті і служить завдання про наближення (апроксимації) функцій: цю функцію f (x) потрібно наближено замінити (апроксимувати) деякою функцією g (x) так, щоб відхилення (в певному сенсі) g (x) від f (x) в заданій області було мінімальним. Функція g (x) при цьому називається апроксимуючої.

Для практики дуже важливий випадок апроксимації функції многочленом:

g (x) = a ₀ + a ₁ x + a ₂ x ² + ... + a ^_m x _m (2.1)

При цьому коефіцієнти a _j будуть підбиратися так, щоб досягти найменшого відхилення многочлена від даної функції.

Якщо наближення будуватися на заданій множині точок {xi}, то апроксимація називається точковою. До неї відносяться інтерполювання, середньоквадратичне наближення та ін При побудові наближення на безперервному безлічі точок (наприклад, на відрізку [a, b] апроксимація називається безперервної або інтегральної).

2.1 Виклад методу (Точкова апроксимація).

Одним з основних типів точкової апроксимації є інтерполювання. Воно полягає в наступному: для даної функції y = f (x) будуємо многочлен (2.1), що приймає в заданих точках x _i ті ж значення y _i, що і функція f (x), тобто g (x _i) = y _i, i = 0,1, ... n.

При цьому передбачається, що серед значень x _i немає однакових, тобто x _i  x _k при цьому i  k. Точки x _i називаються вузлами інтерполяції, а многочлен g (x) - інтерполяційним многочленом.

X ₀ X _1. . . X _n

Рис. 1

Таким чином, близькість інтерполяційного многочлена до заданої функції полягає в тому, що їх значення співпадають на заданою схемою точок (рис.1, суцільна лінія).

Максимальний ступінь інтерполяційного многочлена m = n; в цьому випадку говорять про глобальну інтерполяції.

При великій кількості вузлів інтерполяції виходить висока ступінь многочлена (2.1) у разі глобальної інтерполяції, тобто коли потрібно вміти один інтерполяційний многочлен для всього інтервалу зміни аргументу. Крім того, табличні дані могли бути отримані шляхом вимірів і містити помилки. Побудова аппроксіміруемого многочлена з умовою обов'язкового проходження його графіка через ці експериментальні точки означало б ретельне повторення допущених при вимірах помилок. Вихід з цього становища може бути знайдений вибором такого многочлена, графік якого проходить близько від даних точок (рис.1, штрихова лінія).

Одним з таких видів є середньоквадратичне наближення функції за допомогою многочлена (2.1). При цьому m  n; випадок m = n відповідає інтерполяції. На практиці намагаються підібрати апроксимуючої многочлен якомога меншою мірою (як правило, m = 1, 2, 3).

Мірою відхилення многочлена g (x) від заданої функції f (x) на множині точок (x _i, y _i) (i = 0,1, ..., n) при среднеквадратичном наближенні є величина S, що дорівнює сумі квадратів різниці між значеннями многочлена і функції в даних точках:

S =  [g (x _{i)-y i]} ²

^{i = 0}

Для побудови апроксимуючих многочлена потрібно підібрати коефіцієнти a _0, a _1, ..., a _m так, щоб величина S була найменшою. У цьому полягає метод найменших квадратів.

dS / da ₁ = 2  [g (x _{i)-y i]} ² * 1 = 0;

^{i = 1}

dS / da ₂ = ₂  [g (x _{i)-y i]} ² * x _i = 0;

^{i = 1}

...

dS / da _{m +1} = 2  [g (x _{i)-y i]} ² * x _i ^m = 0.

^{i = 1}

C AB

n	 x _i	...	 x _i ^m	a ₁	 y _i
=  x _i	 x _i ²	...	 x _i ^{m +1}	a ₂	 y _i x _i
...	... ...	...	... ...	...	...
 x _i ^m	 x _i ^{m +1}	...	 x _i ^2m	a _{m +1}	 y _i x _i ^m

3.1 Блок-схема алгоритму. Опис вихідних даних і результатів.

i = 1

i = n

j = 1

Розрахунок першого рядка матриці С і вектора В

i = 1

i = n

i = 1

i = n

j = m +1

i = 1

j = 1

j = m

Розрахунок інших рядків матриці С

j = 1

j = n

j = 1

j = n

i = m

i = 1

j = m +1

крок =- 1

j = 1

i = n

Вихідні дані, а саме:

m-число вузлів апроксимації.

n - ступінь апроксимує многочлена.

X - вектор вузлів апроксимації.

Y - вектор значень аппроксіміруемой функції.

Всі ці значення ми заносимо в файл jan.dat, який працює тільки на читання і файлової змінної є f1.

Результати:

Всі результати виводяться у файл jan.res, що працює на запис і має файлову змінну f2.

Спочатку в цей файл виводяться вихідні дані, які беруться з файлу jan.dat, але при цьому вже з описом, тобто не просто числа, а скоментаріем, що вони означають.

Потім виводяться результати обчислення, проведеної машиною, при цьому всі результати відформатовані:

Виводиться матриця З системи лінійних рівнянь для апроксимації разом з вектором правих частин. Потім виводиться рішення цієї системи рівнянь, що є вектором коефіцієнтів апроксимуючих многочлена за зростанням ступеня. І в кінці виводиться вектор похибки апроксимації Z.

4.1 Лістинг програми, вихідних даних і результатів.

program approx;

uses crt, gausstpu;

const nm = 20;

type vect1 = array [1 .. nm] of real;

var c: matr;

a, b: vect;

x, y, z: vect1;

n, i, j, m: integer;

f1, f2: text;

procedure Create_BC (n, m: integer; var x, y: vect1; var c: matr; var b: vect);

var i, j: integer;

r: vect;

begin

for i: = 1 to n do

r [i]: = 1;

for j: = 1 to m +1 do begin

c [1, j]: = 0;

b [j]: = 0;

for i: = 1 to n do begin

c [1, j]: = c [1, j] + r [i];

b [j]: = b [j] + r [i] * y [i];

end;

for i: = 1 to n do

r [i]: = r [i] * x [i];

end;

for i: = 1 to m do begin

for j: = 1 to m do

c [i +1, j]: = c [1, j +1];

c [i +1, m +1]: = 0;

for j: = 1 to n do

c [i +1, m +1]: = c [i +1, m +1] + r [j];

for j: = 1 to n do

r [j]: = r [j] * x [j];

end; end;

begin

assign (f1, 'jan.dat'); reset (f1);

assign (f2, 'jan.res'); rewrite (f2);

readln (f1, n); writeln (f2, 'Кількість вузлів апроксимації n =', n: 3);

readln (f1, m); writeln (f2, 'Ступінь многочлена m =', m: 2);

writeln (f2, 'Вектор вузлів апроксимації x [i]');

for i: = 1 to n do begin

read (f1, x [i]);

write (f2, x [i]: 4:2, '');

end;

writeln (f2);

writeln (f2, 'Вектор значень аппроксіміруемой функції y [i]');

for i: = 1 to n do begin

read (f1, y [i]);

write (f2, y [i]: 4:2, '');

end;

Create_BC (n, m, x, y, c, b);

writeln (f2);

writeln (f2, 'Матриця системи лінійних рівнянь для апроксимації і вектор правих частин);

for i: = 1 to m +1 do begin

for j: = 1 to m +1 do

write (f2, c [i, j]: 8:1); writeln (f2, b [i]: 8:1); end;

gauss (m +1, c, b, a);

for i: = 1 to n do begin

z [i]: = 0;

for j: = m +1 downto 1 do

z [i]: = z [i] * x [i] + a [j];

z [i]: = z [i]-y [i]; end;

writeln (f2);

writeln (f2, 'Вектор коефіцієнтів апроксимуючих многочлена за зростанням);

writeln (f2, 'ступеня (m +1 елементів)');

for i: = 1 to m +1 do

writeln (f2, 'a [', i: 1 ,']=', a [i]: 6:2);

writeln (f2, 'Вектор похибки апроксимації у вузлах X);

for i: = 1 to n do

writeln (f2, 'z [', i: 1 ,']=', z [i]: 5:3);

close (f1); close (f2);

end.

Вихідний файл jan.dat:

1 6 0 3 8 2 12 9 2 5

9 4 13 7 3 9 3 1 4 2

Файл результатів jan.res:

Число вузлів апроксимації n = 10

Ступінь многочлена m = 2

Вектор вузлів апроксимації x [i]

1.00 6.00 0.00 3.00 8.00 2.00 12.00 9.00 2.00 5.00

Вектор значень аппроксіміруемой функції y [i]

9.00 4.00 13.00 7.00 3.00 9.00 3.00 1.00 4.00 2.00

Матриця системи лінійних рівнянь для апроксимації і вектор правих частин

10.0 48.0 368.0 55.0

48.0 368.0 3354.0 159.0

368.0 3354.0 33428.0 1023.0

Вектор коефіцієнтів апроксимуючих многочлена за зростанням ступеня (m +1 елементів)

a [1] = 11.66

a [2] = -2.31

a [3] = 0.13

Вектор похибки апроксимації у вузлах X

z [1] = 0.479

z [2] =- 1.381

z [3] =- 1.343

z [4] =- 1.070

z [5] =- 1.247

z [6] =- 1.430

z [7] =- 0.244

z [8] = 0.723

z [9] = 3.570

z [10] = 1.454

5.1 Список змінних основної програми.

В основній програмі використовуються розділ констант і типів:

const nm = 20;

type vect1 = array [1 .. nm] of real;

Наступні змінні так само використовуються в програмі, які описуються в розділі var:

Мінлива	Тип змінної	Опис змінної
З	matr	Матриця системи лінійних рівнянь для апроксимації
А	vect	Вектор коефіцієнтів апроксимуючих многочлена за зростанням ступеня (m +1 елементів)
Х	vect1	Вектор вузлів апроксимації
B	vect	Вектор правих частин
Y	vect1	Вектор значень апроксимуючої функції
Z	vect	Вектор похибки апроксимації у вузлах Х
n	integer	Число вузлів апроксимації
m	integer	Ступінь многочлена
i	integer	Необхідна для нумерації елементів масивів.
j	integer	Необхідна для нумерації елементів масивів.
f1	text	Файлова змінна для файлу вихідних значень
f2	text	Файлова змінна резуртірующего файлу

6.1 Заголовки процедур і функцій. Список їх змінних.

У своїй програмі я використовував наступні модулі, які описуються в операторі uses і процедури:

Crt - стандартний модуль підключення екрану і клавіатури для роботи з програмою.

Gauss - процедура вирішення системи лінійних рівнянь методом Гауса. Вона береться з модуля Gausstpu, де інтерфейсна частина має вигляд:

Interface

Const nmax = 20

Type

Тому при оголошенні матриці С посилатися треба на matr, а векторів A і B на vect.

Create_BC - процедура розрахунку матриці С (С - матриця системи лінійних рівнянь для апроксимації). Тема цієї процедури виглядає так:

procedure Create_BC (n, m: integer; var x, y: vect1; var c: matr; var b: vect);

var i, j: integer;

r: vect;

А ось такі змінні використовуються тільки в цій процедурі, решта засилають з основної програми:

Мінлива	Тип змінної	Опис змінної
i	integer	Використовуються в циклах для перебору чисельних значень
j	integer	Використовуються в циклах для перебору чисельних значень
R	vect	Робочий вектор

7.1 Ручний рахунок.

Складаємо матрицю системи рівнянь за наступним принципом:

n	 x _i	 x _i ²	 y _i
 x _i	 x _i ²	 x _i ³	 x _i y _i
 x _i ²	 x _i ³	 x _i ⁴	 x _i ² y _i

Для цього обчислюємо необхідні значення:

n = 10;

 x _i = 1 +6 +0 +3 +8 +2 +12 +9 +2 +5 = 48;

 x _i ² = 1 ² +6 ² +0 ² +3 ² +8 ² +2 ² +12 ² +9 ² +2 ² +5 ² = 368;

 y _i = 9 +4 +13 +7 +3 +9 +3 +1 +4 +2 = 55;

 x _i ³ = 1 ³ +6 ³ +0 ³ +3 ³ +8 ³ +2 ³ +12 ³ +9 ³ +2 ³ +5 ³ = 3354;

 x _i y _i = 1 * 9 +6 * 4 +0 * 13 +3 * 7 +8 * 3 +2 * 9 +12 * 3 +9 * 1 +2 * 4 +5 * 2 = 159;

 x _i ³ = 1 ⁴ +6 ⁴ +0 ⁴ +3 ⁴ +8 ⁴ +2 ⁴ +12 ⁴ +9 ⁴ +2 ⁴ +5 ⁴ = 33428;

 x _i ² y _i = 1 ² * 9 +6 ² * 4 +0 ² * 13 +3 ² * 7 +8 ² * 3 +2 ² * 9 +12 ² * 3 +9 ² * 1 +2 ² * 4 +5 ² * 2 = 1023.

Виходить наступна матриця:

10	48	368	55
48	368	3354	159
368	3354	33428	1023

Яка еквівалентна такій системі рівнянь:

{

10a ₁ + 48a ₂ + 368a ₃ = 55

48a ₁ + 368a ₂ + 3354a ₃ = 159

368a ₁ + 3354a ₂ + 33428a ₃ = 1023

Ми вирішуємо цю систему рівнянь методом Гауса:

10	48	368	55
0	137,6	1587,6	-105
0	1587,6	19885,6	-1001

10	48	368	55
0	137,6	1587,6	-105
0	0	1568,203488	210.4680233

Отримуємо спрощену систему рівнянь:

{

1568,203488 a ₃ = +210,4680233

137,6 a ₂ + 1587,6 a ₃ = -105

10a ₁ + 48a ₂ + 368a ₃ = 55

Вирішуючи яку отримуємо наступні остаточні значення, що є відповіддю:

{

a ₃ = 210,4680233 / 1568,203488 = 0,134209638

a ₂ = (-105-1587,6 a ₃₎ / 137,6 =- 2,311564115

a ₁ = (55-48a _{2-368a 3)} / 10 = 11,65659307

8.1 Обговорення результатів з метою доказу правильності алгоритму і програми.

Отримані результати показують, що алгоритм і програма складено вірно, тому що значення отримані при ручному рахунку близькі до машинних обчисленням.

9.1 Висновки.

Дана програма дуже ефективна, тому що машина виконує всі дії набагато швидше, ніж людина при ручному рахунку. Так само під час ручного рахунку можуть проізоіті помилки, що призведе до повторного перещітиванію, а у машини, при правильному алгоритмі, таких збоїв не буває (якщо тільки "зависає"). Отже ця програма багато в чому полегшує життя людині.

Економічна частина. Розробка модуля виключення нуль-рівнянь в комплексі "Рішення задачі лінійного програмування".

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

Розглянемо задачу оптимального планування виробництва [1]. Нехай підприємство випускає n виробів, для виробництва яких використовується m інгредієнтів. Інгредієнти це - деталі певного сортаменту, верстати, працівники, електроенергія і т.д., інакше кажучи, все що потрібно для здійснення виробничого циклу. Запаси інгредієнтів задаються вектором b = (b _1, b _2, ..., b _m), де b _i - запас i-го інгрідієнта (i = 1, ..., m). Задано матриця А, елемент якої a _ij визначає витрату i-го інгрідієнта для виробництва одиниці j-го виробу (i = 1, ..., m; j = 1, ..., n). Крім того, задано вектор ринкових цін виробів p = (p _1, p _2, ..., p _n), де p - ціна j-го виробу (j = 1, ..., n).

Потрібно скласти такий план виробництва х = (х _1, х _2, ..., х _n), щоб при виконання умов

a ₁₁ x ₁ + a ₁₂ x ₂ + ... + a _1n x _n  b ₁

(1)

a ₂₁ x ₁ + a ₂₂ x ₂ + ... + a _2n x _n  b ₂

^{... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... ....}

a _m1 x ₁ + a _m2 x ₂ + ... + a _mn x _n  b _m

x _j  0, (j = 1, ..., n).

досягався максимум функції

(1 ')

Z = p ₁ x ₁ + p ₂ x ₂ + ... + p _n x _n

Функція Z називається цільовий.

i-е обмеження з (1) означає, що не можна витратити i-го інгредієнта більше, ніж є в наявності. Обмеження (1) задають безліч . Змінні, що задовольняють умові x _j  0, називаються невільними. У нашій задачі це означає, що при x _j = 0 - нічого не виробляється або при x _j> 0 виробляється певна кількість виробів.

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

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

Сформулюємо двоїсту до (1) - (1 ') завдання про придбанні інгридієнтів за мінімальною ринковою вартістю. Хай те ж саме підприємство, що і в задачі (1) - (1 '), збирається придбати на ринку m інгридієнтів для виробництва тих же n виробів. При цьому кількість придбаних інгридієнтів визначається вектором b = (b _1, b _2, ..., b _m). Задано та ж матриця А, елемент якої aij визначає витрату i-го інгрідієнта для виробництва j-го виробу. Крім того задано вектор цін p = (p _1, p _2, ..., p _n) на продукцію підприємства. Потрібно відшукати вектор цін інгридієнтів u = (u _1, u _2, ..., u _m), де u _i - ціна одиниці i-го інгрідієнта (i = 1, ..., m), щоб виконувалися умови:

a ₁₁ u ₁ + a ₂₁ u ₂ + ... + a _m1 u _m  p ₁

(2)

a ₁₂ u ₁ + a ₂₂ u ₂ + ... + a _m2 u _m  p ₂

^{... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... ....}

a _1n u ₁ + a _2n u ₂ + ... + a _mn u _m  p _n

u _i  0, (i = 1, ..., m)

при досягненні мінімуму цільової функції

(2 ')

W = b ₁ u ₁ + ... + b _m u _m

j-е умова (2) означає, що вартість усіх інгредієнтів, що йдуть на виробництво j-го виробу, не менше ринкової ціни цього виробу.

Умова невільною u _j  0 означає, що j-й інгредієнт або безкоштовний (u _j = 0), або коштує позитивний кількість рублів (u _j> 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, то область  запишеться у вигляді:

a ₁₁ x ₁ + a ₁₂ x ₂ + ... + a _1n x _n = b ₁

^{... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... ... ...}

(3)

a _k1 x ₁ + a _k2 x ₂ + ... + a _kn x _n = b _k

a _{k +1, 1} x ₁ + a _{k +1, 2} x ₂ + ... + a _{k +1, n} x _n  b _{k +1}

^{... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... ... ...}

a _m1 x ₁ + a _m2 x ₂ + ... + a _mn x _n  b _m

x _j  0, (j = 1, ..., n)

Потрібно знайти максимум функції

(3 ')

Z = p ₁ x ₁ + p ₂ x ₂ + ... + p _n x _n

У загальному випадку серед змінних x _j можуть бути вільні. Номери вільних змінних будемо зберігати в окремому масиві.

При формуванні двоїстої задачі до задачі (3) - (3 ') i-му обмеження - рівності буде відповідати вільна мінлива u _i (i = 1, ..., k), а вільної змінної x _j обмеження - рівність:

a _1j u ₁ + a _2j u ₂ + ... + a _mj u _m = p _j

Введемо допоміжні змінні y _i  0 (i = 1, ..., n) і запишемо обмеження (3) і функцію Z у вигляді:

0 = a ₁₁ (-x ₁₎ + a ₁₂ (-x ₂₎ + ... + a _1n (-x _n) + a _{1, n +1}

^{... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...}

(4)

0 = a _k1 (-x ₁₎ + a _k2 (-x ₂₎ + ... + a _kn (-x _n) + a _{k, n +1}

y _{k +1} = a _{k +1, 1} (-x ₁₎ + a _{k +1, 2} (-x ₂₎ + ... + a _{k +1, n} (-x _n) + a _{k +1, n + 1}

^{... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ... .... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...}

y _m = a _m1 (-x ₁₎ + a _m2 (-x ₂₎ + ... + a _mn (-x _n) + a _{m, n +1}

Z = A _{m +1, 1} (-x ₁₎ + a _{m +1, 2} (-x ₂₎ + ... + a _{m +1, n} (-x _n) + a _{m +1, n +1}

Умова невільною окремих або всіх змінних тут не відзначено. Позначення:

a _{i, n +1} = b _i (i = 1, ..., m),

a _{m +1, j} =-p _j (j = 1, ..., n)

a _{m +1, n +1} = 0.

Таким чином, матрицю а ми доповнили стовпцем вільних членів, а також рядок коефіцієнтів цільової функції, змінивши знаки цих коефіцієнтів на протилежні. Тоді завдання (4) можна представити у вигляді таблиці. 1:

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

	-X ₁	-X ₂		-X _n	1
0 =	a ₁₁	a ₁₂	...	a _1n	a _{1, n +1}
... ...	... ... ... ... ... ... ... ... ... ... ...				... ... ...
0 =	..				a _{k, n +1}
y _{k +1} =	a _k1	a _k2	...	a _kn	a _{k +1, n +1}
... ...	a _{k +1, 1}	a _{k +1, 2}	...	a _{k +1, n}	... ... ...
y _m =	... ... ... ... ... ... ... ... ... ... ...				... ... ...
	a _m1	a _m2	...	a _mn	a _{m, n +1}
Z =	a _{m +1, n}	a _{m +1, 2}	...	a _{m +1, n}	a _{m +1, n +1}

Номери вільних змінних запам'ятовуються окремо.

Сумісний таблицю двоїстої задачі з таблицею. 1 і отримаємо таблицю. 2.

Пряма і двоїста задачі Таблиця 2

		v ₁ =	v ₂ =		v _n =	W =
		-X ₁	-X ₂		-X _n	1
u ₁	0 =	a ₁₁	a ₁₂	...	a _1n	a _{1, n +1}
	... ...	... ... ... ... ... ... ... ... ... ... ... ...				... ... ...
u _k	0 =	a _k1	a _k2	...	a _kn	a _{k, n +1}
u _{k +1}	y _{k +1} =	a _{k +1, 1}	a _{k +1, 2}	...	a _{k +1, n}	a _{k +1, n +1}
	... ...	... ... ... ... ... ... ... ... ... ... ...				... ... ...
u _m	y _m =	a _m1	a _m2	...	a _mn	a _{m, n +1}
1	Z =	a _{m +1, n}	a _{m +1, 2}	...	a _{m +1, n}	a _{m +1, n +1}

v _j - допоміжні змінні двоїстої задачі.

Тоді j-е обмеження з таблиці має вигляд:

v _j = a _1j u ₁ + a _2j u ₂ + ... + a _mj u _m + a _{m +1, j}  0, якщо x _j  0

Якщо змінна x _j вільна, то їй відповідає обмеження-рівність двоїстої задачі:

0 = a _1j u ₁ + a _2j u ₂ + ... + a _mj u _m + a _{m +1, j}

тобто замість v _j фактично буде нуль.

Крім того перший k змінних двоїстої задачі вільні, а інші невільні.

Цільова функція двоїстої задачі

W = a _{1, n +1} u ₁ + a _{2, n +1} u ₂ + ... + a _m, n +1 u _m + a _{m +1, n +1}

Поєднання в одній таблиці прямий і двоїстої задачі невипадково. Вирішуючи пряму задачу, ми отримуємо про дновременно рішення двоїстої задачі, причому

max Z = min W = a _{m +1, n +1}

Зробимо заміну змінних в таблиці 1, перекинувши допоміжну змінну y _r на верх таблиці зі знаком мінус, а основну мінно x _s на бік таблиці (a _rs  0). Це означає рух з вершини x = (0, ..., 0) в іншу вершину багатогранника  за його ребру. Елемент а _rs називається що дозволяє, рядок r - роздільної рядком, стовпець s - дозволяючим стовпцем. Така заміна змінних носить назву модифікованих Жорданових винятків (Мжі). Елементи матриці а, не належать дозволяючим стовпцю чи дозволяє рядку, назвемо рядовими.

2.2 Опис вихідних даних і результатів рішення задачі лінійного програмування.

Обговоримо вихідні дані (текстовий файл simp.dat) та результати виконання завдання лінійного програмування (текстовий файл simp.res). На початку файлу simp.dat розташовані, так звані, представницькі дані - строкові дані, кожне з яких розташований у файлі з нового рядка:

1. Рядок з номером варіанту,

2. Рядок з російською назвою модуля,

3. Рядок з координатами студента (ПІБ, факультет, курс, група),

4. Рядок з датою виконання.

Далі йдуть рядки файлу з числовими вихідними даними:

1. Керуючий вектор kl - окремий рядок складається з трьох чисел kl _1, kl _2, kl _3:

kl ₁ = 0, якщо необхідно отримати рішення тільки прямої задачі.

kl ₁ = _1, якщо необхідно отримати рішення тільки двоїстої задачі.

kl ₁ = 2, якщо необхідно отримати рішення обох задач.

kl ₂ = 0, якщо немає вільних змінних, інакше kl ₂ дорівнює числу цих нуль-рівнянь.

2. Число обмежень і змінних (окремий рядок введення).

3. Коефіцієнти розширеної матриці a, починаючи з окремого рядка введення.

4. Вектор номерів вільних змінних, якщо вони є, починаючи з окремого рядка введення.

Результати рішення залежать від значення kl.

Якщо kl ₁ = 0, то при успішному результаті це буде вектор оптимального рішення прямої задачі і оптимальне значення цільової функції. При несприятливому результаті, це одне з повідомлень: або "Система обмежень несовместна", або "Цільова функція необмежена".

Якщо kl ₂ = 1, то ж для двоїстої задачі.

Якщо kl ₂ = _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

та

немає

p2 _r <0

p1 (| p2 _r |) =- 1

P = 0

p1 _j> 0

j = 1

немає

та

немає

| A _rj |> p

та

p = | a _rj | s = j

j = n

та

P = 0

немає

"Викл. R-е нуль-ур. Не можна"

MJI (m, n, a, r, s)

p2 _r = p1 _s p1 _s =- 1

t = q2 _r q2 _r = q1 _s q1 _s = t

Закрити файли

До

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:

Виняток нуль-рівнянь

Моносов ЕОУС-1-2 викладач Марьям А. Г.

12.05.98

2 2 0

5 Березня

-2 -1 1 -2

1 -1 0 -1

-1 -1 0 -2

0 1 0 2

2 1 0 4

4 4 0 0

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

Вектор номерів вільних змінних:

2 Січень

Вектор рішення прямої задачі:

1.00000 2.00000 3.00000

Значення цільової функції прямої задачі = 12.00000

Вектор рішення двоїстої задачі:

0.00000 4.00000 0.00000 8.00000 0.00000

Значення цільової функції двоїстої задачі = 12.00000

8.2 Ручний розрахунок задачі лінійного програмування.

Потрібно максимізувати функцію

z = 4x ₁ +5 x ₂

при обмеженнях:

-2x _{1-x 2} + x ₃ =- 2

x _{1-x 2}  -1

- X ₁ - x ₂  -2

0x ₁ + 1x ₂  2

2x ₁ + 1x ₂  4

x ₃  0

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

	-X ₁	-X ₂	-X ₃	1
0 =	-2	-1	1	-2
y ₂ =	1	-1	0	-1
y ₃ =	-1	-1	0	-2
y ₄ =	0	1	0	2
y ₅ =	2	1	0	4
z =	-4	-4	0	0

	-X ₁	-Y ₄	-X ₃	1
0 =	-2	1	1	0
y ₂ =	1	1	0	1
y ₃ =	-1	1	0	0
* X ₂ =	0	1	0	2
y ₅ =	2	-1	0	2
z =	-4	4	0	8

	-Y ₂	-Y ₄	-X ₃	1
0 =	-2	3	1	2
* X ₁ =	1	1	0	1
y ₃ =	-1	2	0	0
* X ₂ =	0	1	0	2
y ₅ =	2	-3	0	0
z =	4	8	0	12

Після цього слід виключити нуль-рівняння:

			*
	-Y ₂	-Y ₄	-Y ₁	1
x ₃ =	-2	3	1	2
* X ₁ =	1	1	0	1
y ₃ =	-1	2	0	0
* X ₂ =	0	1	0	2
y ₅ =	2	-3	0	0
z =	4	8	0	12

Ми бачимо, що вільні члени в непозначених рядках ненегативні, отже опорне рішення отримано і треба перейти до пошуку оптимального рішення. Знаходимо непозначених стовпці з негативними коефіцієнта цільової функції, крім останнього. У нас таких немає, тому оптимальне рішення отримано і переходимо до вилучення результатів. Для цього складемо ще одну таблицю, де міститися змінні прямої і двоїстої задач. Для витягання рішень потрібні лише стовпець вільних членів і рядок коефіцієнтів цільової функції. Тому внутрішня частина таблиці не узгоджено.

		u ₂ =	u ₄ =	u ₁ =	w =
		-Y ₂	-Y ₄	-Y ₁	1
v ₃ =	x ₃ =	-2	3	1	2
v ₁ =	x ₁ =	1	1	0	1
u ₃ =	y ₃ =	-1	2	0	0
v ₂ =	x ₂ =	0	1	0	2
u ₅ =	y ₅ =	2	-3	0	0
1	z =	4	8	0	12

У результаті отримуємо такі результати:

Пряма задача. Змінні прямої задачі, що знаходяться зверху таблиці рівні у вирішенні 0, а збоку - відповідним вільним членам:

x ₁ = _1; x ₂ = _2; x ₃ = 2.

Двоїста задача. Змінні двоїстої задачі, що знаходяться зверху таблиці рівні 0, а збоку - відповідним коефіцієнтом цільової функції:

u ₁ = 0; u ₂ = 4; u ₃ = 0; u ₄ = 8; u ₅ = 0.

Значення цільових функцій обох задач z _max = w _min = 12.

9.2 Висновки.

Отримані результати при ручному розрахунку збігаються з даними машинного рахунку. Це підтверджує правильність складання алгоритму і написання програми.

Список використаної літератури.

Турчак Л. І. "Основи чисельних методів".

Марьям А. Г. "Застосування модульного способу програмування в середовищі Turbo Pascal 7.0 з метою вирішення повної задачі лінійного програмування".

Додати в блог або на сайт

Цей текст може містити помилки.

Програмування, комп'ютери, інформатика і кібернетика | Реферат
91.4кб. | скачати

Схожі роботи:
Апроксимація функцій
Апроксимація функції з використанням нейронних мереж
Апроксимація характеристик нелінійних елементів і аналіз ланцюгів при гармонійних впливах
Різницевий метод розв язування звичайних диференціальних рівнянь Апроксимація Метод прогонки