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

Інформатика, програмування

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

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

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

КУРСОВА РОБОТА ПО ІНФОРМАТИЦІ на теми:

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

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

Виконав студент ЕОУС - 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.

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

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

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

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

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

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

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

g (x) = a0 + a1x + a2x2 + ... + amxm (2.1)

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

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

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

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

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

Рис. 1

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

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

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

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

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

S = ([g (xi)-yi] 2 i = 0

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

ndS/da1 = 2 ([g (xi)-yi] 2 * 1 = 0; i = 1

ndS/da2 = 2 ([g (xi)-yi] 2 * xi = 0; i = 1

...

ndS/dam +1 = 2 ([g (xi)-yi] 2 * xim = 0. i = 1

AB
| n | (xi | ... | (xim | | a1 | | (yi |
| (Xi | (xi2 | ... | (| | a2 | | (yixi |
| | | | Xim 1 | | | | |
| ... | ... ... | ... | ... ... | | ... | | ... |
| (Xim | (| ... | (xi2m | | am 1 | | (yixim |
| | Xim 1 | | | | | | |

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

Вихідні дані, а саме: 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;beginfor i: = 1 to n dor [i]: = 1;for j: = 1 to m 1 do beginc [1, j]: = 0;b [j]: = 0;for i: = 1 to n do beginc [1, j]: = c [1, j] + r [i];b [j]: = b [j] + r [i] * y [i];end;for i: = 1 to n dor [i]: = r [i] * x [i];end;for i: = 1 to m do beginfor j: = 1 to m doc [i +1, j]: = c [1, j +1];c [i +1, m +1]: = 0;for j: = 1 to n doc [i +1, m +1]: = c [i +1, m 1] + r [j];for j: = 1 to n dor [j]: = r [j] * x [j];end; end;beginassign (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 beginread (f1, x [i]);write (f2, x [i]: 4:2, '');end;writeln (f2);writeln (f2, 'Вектор значень аппроксіміруемой функції y [i]');for i: = 1 to n do beginread (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 beginfor j: = 1 to m +1 dowrite (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 beginz [i]: = 0;for j: = m +1 downto 1 doz [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 dowriteln (f2, 'a [', i: 1 ,']=', a [i]: 6:2);writeln (f2, 'Вектор похибки апроксимації у вузлах X);for i: = 1 to n dowriteln (f2, 'z [', i: 1 ,']=', z [i]: 5:3);close (f1); close (f2);end.

Файл jan.dat:

10
2
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.66a [2] = -2.31a [3] = 0.13
Вектор похибки апроксимації у вузлах Xz [1] = 0.479z [2] =- 1.381z [3] =- 1.343z [4] =- 1.070z [5] =- 1.247z [6] =- 1.430z [7] =- 0.244z [8] = 0.723z [9] = 3.570z [10] = 1.454

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

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

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

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

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 ;

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

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

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

| n | (xi | (xi2 | (yi |
| (xi | (xi2 | (xi3 | (xiyi |
| (xi2 | (xi3 | (xi4 | (xi2y |
| | | | I |

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

n = 10;
(xi = 1 +6 +0 +3 +8 +2 +12 +9 +2 +5 = 48;
(xi2 = 12 +62 +02 +32 +82 +22 +122 +92 +22 +52 = 368;
(yi = 9 +4 +13 +7 +3 +9 +3 +1 +4 +2 = 55;
(xi3 = 13 +63 +03 +33 +83 +23 +123 +93 +23 +53 = 3354;
(xiyi = 1 * 9 +6 * 4 +0 * 13 +3 * 7 +8 * 3 +2 * 9 +12 * 3 +9 * 1 +2 * 4 +5 * 2 = 159;
(xi3 = 14 +64 +04 +34 +84 +24 +124 +94 +24 +54 = 33428;
(xi2yi = 12 * 9 +62 * 4 +02 * 13 +32 * 7 +82 * 3 +22 * 9 +122 * 3 +92 * 1 +22 * 4 +52 * 2 = 1023. Виходить наступна матриця:

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

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

10a1 + 48a2 + 368a3 = 55

48a1 + 368a2 + 3354a3 = 159

368a1 + 3354a2 + 33428a3 = 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 a3 = 210,4680233

137,6 a2 + 1587, 6a3 = -105

10a1 + 48a2 + 368a3 = 55

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

a3 = 210,4680233/1568,203488 = 0,134209638 a2 = (-105-1587,6 a3)/137,6 =- 2,311564115 a1 = (55-48a2 - 368a3)/10 = 11,65659307

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

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

9.1 Висновки.

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

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), щоб привиконання умов

| 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;interfaceconst 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;implementationend.

У розділі констант задані константи 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 укрупнена блок-схема задачі лінійного програмування.

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

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

m, n, r, s: integer; (числові змінні цілого типу)

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

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

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

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

У результаті успішної роботи алгоритму всі нуль-рівняння будуть виключені, ів відслідковує векторі p1 це буде відзначено як -1, що дасть можливістьв подальшому відповідні стовпці матриці А при виборі дозволяєелемента не чіпати. Якщо ж алгоритм застосувати не можна, то буде виданоповідомлення (див. блок-схему), і робота програми закінчиться.

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

unit isnum;interfaceuses typesm, mjim;procedure isnu (var k1: k1t; m, n: integer; var a: at;var p1, q1: vec1it; var p2, q2: vec2it);implementationprocedure isnu;var p: real; k, s, r, j, t: integer;beginfor r: = 1 to k do beginif p2 [r] 0 then beginif 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 5 x2

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

-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

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

Висновок 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 = 1j = 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 =- 1t = q2r q2r = q1s q1s = t

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

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

r = 1

r = k

так

немає

j = 1

j = n

немає

так

немає