Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Комп’ютерні науки
Кафедра:
Не вказано
Інформація про роботу
Рік:
2011
Тип роботи:
Методичні вказівки до лабораторної роботи
Предмет:
Моделювання систем
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ
“ЛЬВІВСЬКА ПОЛІТЕХНІКА”
АВТОМАТИЗОВАНІ СИСТЕМИ УПРАВЛІННЯ
ОПТИМАЛЬНЕ КЕРУВАННЯ ПРОЦЕСАМИ З ЗАСТОСУВАННЯМ
МЕТОДУ ЛІНІЙНОГО ПРОГРАМУВАННЯ
Методичні вказівки
до лабораторної роботи №_1__
з курсу “Моделювання систем”
для студентів базової вищої освіти
за напрямком 6.050101 “Комп’ютерні науки”
Львів - 2011
Оптимальне управління процесами з застосуванням методу лінійного програмування. Методичні вказівки до лабораторної роботи № 1 з курсу “Моделювання систем” для студентів базової вищої освіти за напрямком 6.050101. “Комп'ютерні науки” Львів, НУ “Львівська політехніка”, 2011р.
Укладачі: Ткаченко Р.О.; д.т.н., проф.
Цмоць І.Г.; д.т.н., проф.
Батюк А.Є.; к.т.н., доц.
Відповідальний за випуск: __ к.т.н., доц.. Шпак З.Я _____________
Рецензент:___ д.т.н., проф. Різник В.В.______________
Мета роботи
Вивчення і застосування методу лінійного програмування для рішення задач оптимального керування, у яких цільова функція, модель процесу й обмеження є лінійними функціями.
Обсяг роботи: 4 години.
1. ТЕОРЕТИЧНІ ПОЛОЖЕННЯ
Лінійне програмування - розділ математичного програмування, що вивчає задачу знаходження максимуму (мінімуму) лінійної функції при лінійних обмеженнях у виді рівностей або нерівностей. Загальна задача лінійного програмування формулюється так: потрібно знайти максимум лінійної функції n змінних х1,х2, ... ,хn
/1/
при обмеженнях
, i=1,2,…,m /2/
, j=1,2,…,n. /3/
де G - цільова функція, kj (j=1,…,n). aij (i=1,…,n; j=1,…,n), bi (i=1,…,m) - задане число. Задача мінімізації цільової функції /1/ зводиться до задачі максимізації шляхом заміни знаків усіх коефіцієнтів kj, на протилежні.
Найбільше поширеним прикладом задачі лінійного програмування є задача планування роботи підприємства, що випускає деякий однорідний продукт. Ця задача ставиться наступним чином: є n різноманітних технологій і m ресурсів (робоча сила, сировина, енергія, транспорт і т.д.) виробництва. Відомі: kj - кількість одиниць продукту, що можна одержати при використанні j-ї технології в одиницю часу (j=1,...n), аij - виграти і-го ресурсу при використанні j-ї технології (і=1,...,m); (j=1,...,n), bi - загальний запас і-го ресурсу (і=1,...,m), хj - час, протягом якого виробництво ведеться по j-й технології.
Потрібно відшукати план Х=(x1, x2,..., хn), при якому з наявних запасів випускалася б максимальна кількість продукту, тобто G=>тах.
Призначення моделей фізичних процесів при рішенні питання оптимізації складається у встановленні зв'язків між змінними стану і змінними керування, причому оптимізується завжди цільова функція, а не модель процесу. Цільова функція і обмеження звичайно є функціями як змінних стану, так і змінних керування. Визначення цільової функції і перебування її екстремального значення є суттю проблеми оптимізації. На відміну від моделей фізичних процесів цільові функції звичайно виражають нефізичні величини, наприклад, прибуток, вартість, якість і т.п.
У найпростішому випадку цільова функція, модель фізичного процесу й обмеження є лінійними функціями. Оптимальне керування в задачах такого роду може бути знайдене за допомогою методу лінійного програмування.
Розглянемо лінійну цільову функцію з одною змінною і одною змінною стану:
F(у,х)=А+Вх+Су, /4/
де Х - змінна керування, у - змінна стану. Нехай при цьому лінійна модель фізичного процесу виражається як
у=D+Ех, /5/
де А, В, С,D, Е - задані числа.
Підставивши /5/ в /4/, одержимо цільову функцію, що залежить тільки від змінної керування
G(х)=А+Вх+СD+СEх /6/
або
G(х)=К0+К1X, /7/
де
К0=А+СD; К1=В+СЕ.
Лінійні цільові функції при відсутності обмеженні не мають кінцевого оптимуму. Тому в задачах оптимізації цільової функції обмеження грають принципову роль.
Оптимальне керування з лінійною цільовою функцією при наявності лінійних обмежень можна уявити як задачу оптимізації функції
/8/
при обмеженнях
; j=1,…,n /9/
; j=1,…,n /10/
де Rін і Rjb - нижня і верхня границі обмеження j-ї змінної керування; Qін, Qib ocі - нижня і верхня границі і-го обмеження на змінні стану, виражені у вигляді залежності між змінними керування; Kij - позитивна константа.
Нижня межа змінної керування, як правило, дорівнює нулю, а верхня границя є її фізичною границею (наприклад, цілком відкритий клапан).
Обмеження, що накладаються на межі зміни змінних керування, можна висловити у виді рівностей за допомогою введення позитивних допоміжних змінних:
Xj+Zj=Кjb; Хj-2j=Кjн.
Розмір Хj знаходиться на границі обмежень, коли Zjb=0 або Zjн=0.
Нерівність /10/ можна перетворити в рівність за допомогою введення допоміжних позитивних змінних Wib і Wiн:
;
;
Наприклад, для цільової функції з двома змінними керування таке обмеження, що накладається на кожну з змінних керування, можна висловити таким чином:
;
;
Вважаючи W1B=0, а потім W1н=0, можна отримати границі обмежень:
/11/
для роботи на верхній границі і
/12/
для роботи на нижній границі.
На мал.1 рівняння /11/ і /12/ представлені у вигляді прямих із кутовими коефіцієнтом - k1(k2). Лінія верхнього обмеження перетинає вісь Х2 в точці МB(0, Q1B/К2), у лінія нижнього обмеження - в точці Мн(0, Q1н/К2). На мал.2 показаний випадок трьох обмежень, що виражають залежність між змінними керування, нанесеними на площину (Х1,Х2). Областю можливих значень є ділянка (А, В, С, D, Е, F) оскільки він відповідає всім трьом обмеженням. Обмеження границь зміни змінних керування забезпечують невід'ємність величин Х1 і Х2.
Обмеження, що виражають залежність між змінними керування, можуть іноді взагалі заборонити будь-яке рішення. Так могло б трапитися, наприклад, якби нижня границя 3-го обмеження (Мал.2) розташувалася вище точки С.
Лініями рівного рівня цільових функцій є лінії, що з'єднують точки, у яких значення цільової функції рівні між собою. Для лінійної цільової функції з двома змінними керування.
лінії рівного рівня, нанесені на площину (Х1,Х2), являють собою множину паралельних прямих ліній:
, r=1,2....,8
або
Відрізком, що відганяється кожною r-ю прямою на осі X2, є (Lr-К0)/К2, а її кутовий коефіцієнт дорівнює – К1/К2.
Розглядаючи область обмеження і лінії рівного рівня цільової функції, легко зауважити, що максимум (або мінімум) цільовій функції знаходиться на одному з перетинів ліній обмеження і цільової функції. Наприклад, на мал.3 областю допустимих значень змінних керування є, ділянка АВСDEF, причому максимум досягається в точці С, а мінімум у точці F. Оптимум може бути знайдений обчисленням значень цільової функції в різноманітних вершинах області обмежень.
Таким чином, сукупність будь-якого числа лінійних обмежень виділяє в n-мірному просторі X1,Х2,...,Хn деякий опуклий багатогранник, що є областю допустимих значень змінних керування. Екстремум цільової функції досягається, як правило, в одній з його вершин. Проте навіть у порівняно простих задачах кількість вершин багатогранника може обчислюватися мільйонами або мільярдами. Перебрати таку величезну кількість вершин і зазначити ту, в якій значення цільової функції максимальне (або мінімальне), практично неможливо навіть при великій швидкодії ЕОМ керування процесом. Застосування методу лінійного програмування дозволяє швидко знаходити екстремум цільової функції, відмовившись від повного перебору усіх вершин.
Якщо кількість змінних керування більше двох або трьох, то для рішення задач лінійного програмування зручно використовувати ітераційну процедуру, що іменується сиплекс-методом [1].
ПРИКЛАД.
Модель фізичного процесу описується рівнянням
Необхідно оптимізувати цільову функцію
при наявності обмежень:
РІШЕННЯ.
Виражаючи змінну стану через змінні керування, представляємо цільову функцію і обмеження як функції змінних керування:
Графічне рішення задачі приведене на мал.4. Областю допустимих значень змінних є ділянка А В С D Е F G. Пунктиром показані лінії рівного рівня цільової функції. Координати точок перетину ліній обмеження: А (0.7); В (1.4); С (4.1); В (7.0); Е (10.0); F (10.8); G (0.8). Мінімум цільової функції знаходиться в точці С, а максимум - в точці F, причому Gmin=150, Gmin= 650.
Для висвітлення загальної картини оптимального керування процесами з застосуванням методу лінійного програмування на мал.5 приведена функціональна схема оптимального керування з використанням моделі процесу, цільової функції й обмежень. Суть керування полягає в вирішенні задачі оптимізації безпосередньо в ході керування фізичним процесом. Рівняння оптимальності, що вирішуються в системі керування за допомогою ЕОМ, дозволяють обчислити перемінні оптимального керування для необхідних робочих умов і параметрів. При цьому рівняння оптимального керування вводяться в систему керування ззовні з урахуванням моделі фізичного процесу, цільової функції й обмежень.
Мал.5. Функціональна схема оптимального керування з використанням моделі процесу, цільової функції й обмежень.
2. ПРОГРАМА І ПОРЯДОК ВИКОНАННЯ РОБОТИ
У процесі підготовки і виконання роботи необхідно вирішити такі задачі:
розробити алгоритм і скласти програму на одній з алгоритмічних мов для рішення задачі оптимального керування;
визначити за допомогою ЕОМ максимальне і мінімальне значення цільової функції при заданих обмеженнях.
При виконанні лабораторної роботи необхідно:
ознайомитися з теоретичними зведеннями і прикладами використання методу лінійного програмування для рішення задач оптимального керування;
представити цільову функцію і систему обмежень у вигляді функцій змінних керування шляхом заміни змінних стану змінних керування;
скласти блок-схему алгоритму і програму рішення задачі на мові С або Паскаль;
вивести на друк максимальне і мінімальне значення цільової функції, значення змінних керування, а також час обчислення екстремальних значень цільової функції;
побудувати на міліметровому папері область допустимих значень змінних керування.
3. ЗМІСТ ЗВІТУ ПО РОБОТІ
Мета роботи.
Вихідні дані відповідно до варіанта.
Математична модель задачі.
Блок-схема алгоритму рішення задачі.
Програма на мові С або Паскаль.
Результати розрахунку на ЕОМ оптимальних значень цільової функції і змінних керування.
Графічне рішення задачі.
Аналіз результатів. Висновки.
4. КОНТРОЛЬНІ ПИТАННЯ
Що є суттю проблеми оптимізації?
Яке призначення моделі фізичного процесу при рішенні задача оптимального керування?
Від яких змінних залежить значення цільової функції?
Яку роль при оптимізації грають обмеження на змінні стану і змінні керування?
Сформулювати загальну задачу лінійного програмування.
У яких випадках цільова функція не має кінцевого оптимуму?
Що таке область допустимих значень змінних керування?
Що таке лінії рівного рівня цільової функції?
Як визначити кутовий коефіцієнт ліній рівного рівня цільової функції?
У чому геометричний зміст лінійних обмежень?
Намалювати блок-схему алгоритму оптимізації цільової функції.
Додаток 1
Приклад тексту програми на мові Паскаль для
розрахунку оптимуму цільової функції
User Crt;
Var A: array [1..15] of real;
X: array [1..20] of real;
F: array [1..10] of real;
M, JM: integer;
i,j,k,l,li,kn,mn,n,il: byte;
A11,A22,A33,B11,B22,B33,DMIN,DMAX,x11,x22: real;
{-----------------------------------}
PROCEDURE Proc_CR(A1,A2,C1,B1,B2,C2,X1,X2: real);
label 1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19;
Var t: real;
Begin
if A1<0 then goto 1;
if A1=0 then goto 2;
if A1>0 then goto 1;
1:
if A2<0 then goto 3;
if A2=0 then goto 4;
if A2>0 then goto 3;
3:
if B1<0 then goto 5;
if B1=0 then goto 6;
if B1>0 then goto 5;
5:
if B2<0 then goto 7;
if B2=0 then goto 8;
if B2>0 then goto 7;
7:
T:=A1*B2-B1*B2;
X1:=(C1*B2-C2*B2)/T;
X2:=(A1*C2-B1*C1)/T;
2:
if A2<0 then goto 9;
if A2=0 then goto 10;
if A2>0 then goto 9;
9:
X2:=C1/A2;
if B1<0 then goto 11;
if B1=0 then goto 10;
if B1>0 then goto 11;
11:
if B2<0 then goto 12;
if B2=0 then goto 13;
if B2>0 then goto 12;
Exit;
12:
X1:=(C2-B2*X2)/B1;
Exit;
13:
X1:=C1/B1;
Exit;
4:
X1:=C1/A1;
if B1<0 then goto 15;
if B1=0 then goto 16;
if B1>0 then goto 15;
15:
if B2<0 then goto 17;
if B2=0 then goto 10;
if B2>0 then goto 17;
17:
X2:=(C2-B1*X1)/B2;
Exit;
16:
if B2<0 then goto 18;
if B2=0 then goto 10;
if B2>0 then goto 18;
18:
X2:=C2/B2;
Exit;
6:
if B2<0 then goto 19;
if B2=0 then goto 10;
if B2>0 then goto 19;
19:
X2:=C2/B2;
X1:=(C1-A2*X2)/A1;
Exit;
8:
X1:=C2/B1;
X2:=(C1-A1*X1)/A2;
Exit;
10:
Exit;
End;
Begin
TextBackGround(0);
ClrScr;
TextAttr:=16*5+14;
WriteLn ('Input the matrix A[15]:');
TextAttr:=16*0+3;
{ Initialization block for matrix A }
for i:=1 to 15 do
begin
write ('A[',i,']=');
readln (A[i]);
end;
write ('Input M: ');
readln (M);
JM:=M-3;
for i:=1 to JM*3 do
begin
k:=1;
A11:=A[i];
A22:=A[i+1];
A33:=A[i+2];
mn:=i+3;
for j:=mn to m*3 do
begin
B11:=A[j];
B22:=A[j+1];
B33:=A[j+2];
Proc_CR (A11,A22,A33,B11,B22,B33,X11,X22); {call the proc}
X[k]:=X11;
X[k+1]:=X22;
k:=k+2;
Inc(j,2);
end;
Inc(i,2);
end;
li:=k-1;
n:=1;
for l:=1 to li*2 do
begin
F[n]:=16*X[l]+32*X[l+1];
n:=n+1;
inc(i,1);
end;
kn:=n-1;
Dmin:=F[1];
Dmax:=F[1];
for k:=1 to kn do
begin
if Dmin>F[k] then Dmin:=F[k];
if Dmax<F[k] then Dmax:=F[k];
end;
writeln ('Top of polyhedron');
TextAttr:=16*4+14;
for il:=0 to 9 do
writeln ('X1=',x[i1*2+1],' X2=',x[i1*2+2]);
writeln ('Maximum= ', Dmax, 'Minimum= ',Dmin);
End.
Додаток З
ВАРІАНТИ ІНДИВІДУАЛЬНОГО ЗАВДАННЯ
Варіант 1
Цільова функція
Модель процесу
Обмеження
Варіант 2
Цільова функція
Модель процесу
Обмеження
Варіант 3
Цільова функція
Модель процесу
Обмеження
Варіант 4
Цільова функція
Модель процесу
Обмеження
Оптимальне управління процесами з застосуванням методу лінійного програмування. Методичні вказівки до лабораторної роботи № 1 з курсу “Моделювання систем” для студентів базової вищої освіти за напрямком 6.050101. “Комп'ютерні науки” Львів, НУ “Львівська політехніка”, 2011р.
Укладачі: Ткаченко Р.О.; д.т.н., проф.
Цмоць І.Г.; д.т.н., проф.
Батюк А.Є.; к.т.н., доц.
Відповідальний за випуск: __к.т.н., доц.. Шпак З.Я._____________
Рецензент:__д.т.н., проф. Різник В.В._______________
19.02.2013 22:02-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора