Зміст.
I. Математична частина. Назва
1.1 Постановка задачі
2.1 Виклад методу
3.1 Блок-схема алгоритму. Опис вихідних даних і результатів
4.1 Лістинг програми, вихідних даних і результатів
5.1 Список змінних основної програми
6.1 Заголовки процедур і функцій. Список їх змінних
7.1 Ручний розрахунок
8.1 Обговорення результатів з метою докази правильності алгоритму і програми
9.1 Висновки
II. Економічна частина. Назва
1.2 Постановка задачі лінійного програмування та завдання на розробку модуля
2.2 Опис вихідних даних і результатів розв'язання задач лінійного програмування
3.2 Опис модуля типів
4.2 укрупнена блок-схема задачі лінійного програмування
5.2 Параметри та заголовки процедур задачі лінійного програмування
6.2 Блок-схема і параметри реалізованої процедури
7.2 Лістинг модуля, вихідних даних і результатів машинного розрахунку
8.2 Ручний розрахунок задачі лінійного програмування
9.2 Висновки
Список використаної літератури.
I. Математична частина. Апроксимація.
1.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 була найменшою. У цьому полягає метод найменших квадратів.
n
dS/da1 = 2? [g (xi)-yi] 2 * 1 = 0;
i = 1
n
dS/da2 = 2? [g (xi)-yi] 2 * xi = 0;
i = 1
...
n
dS/dam +1 = 2? [g (xi)-yi] 2 * xim = 0.
i = 1
C A B
n? xi ...? xim a1? yi
? xi? xi2 ...? xim 1 a2? yixi
... ... ... ... ... ... ... ...
? xim? xim +1 ...? xi2m am 1? yixim
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;
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 ]');< br />
for i: = 1 to n do begin
read (f1, x [i]);
write (f2, x [i]: 4:2, '');
end;
writeln (f2);
writeln (f2, 'Вектор значень аппроксіміруемой функції y [i ]');< br />
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 елементів )');< br />
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:
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.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? xi? xi2? yi
? xi? xi2? xi3? xiyi
? xi2? xi3? xi4? xi2yi
Для цього обчислюємо необхідні значення:
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 3342 8 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,6 a3 = -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, n am 1, 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, n ak +1, n +1
... ... ... ... ... ... ... ... ... ... ... ... ... ... ... ...
um ym = am1 am2 ... amn am, n +1
1 Z = am 1, n am 1, 2 ... am 1, n am 1, n +1
vj - допоміжні змінні двоїстої задачі. Тоді j-е обмеження з таблиці має вигляд: vj = a1j u1 + a2j u2 + ... + amj um + am 1, j? 0, якщо xj? 0 Якщо змінна xj вільна, то їй відповідає обмеження-рівність двоїстої задачі: 0 = a1j u1 + a2j u2 + ... + amj um + am 1, j тобто замість vj фактично буде нуль. Крім того перший k змінних двоїстої задачі вільні, а інші невільні. Цільова функція двоїстої задачі W = a1, n +1 u1 + a2, n +1 u2 + ... + am, n 1 um + am 1, n +1 Поєднання в одній таблиці прямої і двоїстої задачі невипадково. Вирішуючи пряму задачу, ми отримуємо про дновременно рішення двоїстої задачі, причому max Z = min W = am 1, n +1 Зробимо заміну змінних в таблиці 1, перекинувши допоміжну змінну yr на верх таблиці зі знаком мінус, а основну пременную xs на бік таблиці (ars? 0). Це означає рух з вершини x = (0, ..., 0) в іншу вершину багатогранника? за його ребра. Елемент аrs називається що дозволяє, рядок r - роздільної рядком, стовпець s - що дозволяє стовпцем. Така заміна змінних носить назву модифікованих жорданових винятків (Мжі). Елементи матриці а, що не належать роздільної колонку або роздільної рядку, назвемо рядовими. 2.2 Опис вихідних даних і результатів розв'язання задачі лінійного програмування. Давай обговоримо це вихідні дані (текстовий файл simp.dat) і результати розв'язання задачі лінійного програмування (текстовий файл simp.res). На початку файлу simp.dat розташовані, так звані, представницькі дані - рядкові дані, кожне з яких розташований у файлі з нового рядка: 1. Рядок з номером варіанту, 2. Рядок з російською назвою модуля, 3. Рядок з координатами студента (ПІБ, факультет, курс, група), 4. Рядок з датою виконання. Далі йдуть рядки файлу з числовими вихідними даними: 1. Керуючий вектор kl - окремий рядок складається з трьох чисел kl1, kl2, kl3: kl1 = 0, якщо необхідно отримати рішення тільки прямої задачі. kl1 = 1, якщо необхідно отримати рішення тільки двоїстої задачі. kl1 = 2, якщо необхідно отримати рішення обох задач. kl2 = 0, якщо немає вільних змінних, інакше kl2 дорівнює числу цих нуль-рівнянь. 2. Число обмежень і змінних (окремий рядок вводу). 3. Коефіцієнти розширеної матриці a, починаючи з окремого рядка введення. 4. Вектор номерів вільних змінних, якщо вони є, починаючи з окремого рядка введення. Результати рішення залежать від значення kl. Якщо kl1 = 0, то при успішному результаті це буде вектор оптимального рішення прямої задачі і оптимальне значення цільової функції. За несприятливого результату, це одне з повідомлень: або "Система обмежень несумісні", або "Цільова функція необмежена". Якщо kl2 = 1, то ж для двоїстої задачі. Якщо kl2 = 2, то спочатку видається рішення прямій, а потім двоїстої задачі. При не успішному результаті повідомлення справедливі тільки для прямої задачі (для двоїстої аналогічні повідомлення не видаються). Результати поміщаються в файл simp.res. 3.2 Опис модуля типів. Для завдання типів і файлових змінних вступного та вивідного текстових файлів використовується модуль типів unit typesm, структура якого наведена нижче unit typesm; interface const mmax = 20; nmax = 20; e = 1e-5; type klt = array [1 .. 3] of integer; at = array [1 .. mmax 1,1 .. nmax 1] of real; vec1it = array [1 .. nmax] of integer; vec2it = array [1 .. mmax] of integer; vec1rt = array [1 .. nmax] of real; vec2rt = array [1 .. mmax] of real; var fi, fo: text; implementation end. У розділі констант задані константи nmax і mmax, які визначають максимальне число строк розширеної матриці a без одиниці, а також гранична константа ті, що використовується в модулі пошуку роздільної рядка. Константа е використовується для забезпечення стійкості алгоритму (модуль дозволяє елемента не повинен бути занадто малий, а саме, більше е). Нижче наведена таблиця фактичних і формальних параметрів підпрограм задач лінійного програмування. Розташування формальних і фактичних параметрів збігаються.
N/N Призначення Позначення Тип
1. Керуючий вектор k1 ki1t
2. Число обмежень m integer
3. Число змінних n integer
4. Матриця коефіцієнтів a at
5. Вектор номерів вільних змінних i1 vec1it
6. Відслідковує вектор основних змінних прямої задачі p1 vec1it
7. Відслідковує вектор допоміжних змінних двоїстої задачі q1 vec1it
8. Відслідковує вектор допоміжних змінних прямої задачі p2 vec2it
9. Відслідковує вектор основних змінних двоїстої задачі q2 vec2it
10. Роздільна рядок r integer
11. Дозволяє стовпець s integer
12. Вектор-рішення прямої задачі x vec1rt
13. Вектор-рішення двоїстої задачі u vec2rt
4.2 укрупнена блок-схема задачі лінійного програмування. 5.2 Параметри та заголовки процедур задачі лінійного програмування. В основній програмі використовуються наступні змінні, які описані в розділі var: m, n, r, s: integer; (числові змінні цілого типу) Процедури програми:
N/N Призначення Заголовок
1. Написання та контроль вихідних даних та виведення їх у файл результатів input (var k1: k1t; var m, n: integer; var a: at, var i1: vec1it; var p1, q1: vec1it; var p2, q2: vec2it) < br />
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 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
У підсумку отримуємо наступні результати: Пряма задача. Змінні прямої задачі, що знаходяться зверху таблиці рівні у вирішенні 0, а збоку - відповідним вільним членам: x1 = 1; x2 = 2; x3 = 2. Подвійна завдання. Змінні двоїстої задачі, що знаходяться зверху таблиці рівні 0, а збоку - відповідним коефіцієнта цільової функції: u1 = 0; u2 = 4; u3 = 0; u4 = 8; u5 = 0. Значення цільових функцій обох завдань zmax = wmin = 12. 9.2 Висновки. Отримані результати при ручному розрахунку збігаються з даними машинного рахунку. Це підтверджує правильність складання алгоритму та написання програми. Список використаної літератури. Турчак Л. І. "Основи чисельних методів". Марьям А. Г. "Застосування модульного способу програмування в середовищі Turbo Pascal 7.0 з метою вирішення повної задачі лінійного програмування".
-19 -
1
