Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Оптимальне керування процессами з застосуванням методу лінійного програмування
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
Не вказано
Кафедра:
Не вказано
Інформація про роботу
Рік:
2010
Тип роботи:
Лабораторна робота
Предмет:
Інформаційні технології
Група:
КН-30
Частина тексту файла (без зображень, графіків і формул):
Міністерство освіти та науки України
Національний університет “Львівська політехніка”
Інститут комп’ютерних наук та інформаційних технологій
Кафедра АСУ
Лабораторна робота №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].
Варіант індивідуального завдання
Варіант 3
Цільова функція
Модель процесу
Обмеження
Математична модель задачі
Цільова функція мого індивідуального завдання має вигляд: G(x) = 49x1-7x2. Для знаходження вектору напрямку збільшення цільової функції потрібно взяти часткові похідні від заданої функції по x1 та x2 , отримані значення дорівнюють проекціям вектору на відповідні осі координат:
Для знаходження точок, які формують багатокутник області допустимих значень функції, потрібно знайти усі точки перетину обмежень і залишити тільки ті з них, які задовільняють усі задані рівняння. Для знаходження точки перетину я використовував метод Крамера для системи з двох рівнянь та двох невідомих. Приклад :
Побудуємо матрицю А і знайдем значення її визначника:
А=, С=; ∆А=1*3-4*(-1)=7;
Наступним кроком буде знаходження значення визначника матриці А, у якій почергово підставляєм замість і-го стовпця вектор вільних членів С.
; =56*3-4*(-6)=192;
; =1*(-6)-56*(-1)=50;
Згідно з методом Крамара :
;
Знайшовши решту точок перетину, потрібно підставити їх у кожне рівняння лінії обмеження. Точка належить області допустимих значень лише тоді, коли задовольняє усі нерівності. Останнім кроком буде знаходження мінімуму та максимуму шляхом підстановки точок, які залишились, у рівнянні цільової функції.
В результаті обчислень я отримав точки вершин многокутника області допустимих значень:
A(2.00,12.00);B(21.00,12.00);C(0.67,10.67);D(1.57,3.48);E(9.00,1.00); F(14.00,2.67);
Мінімум функції G(x) у точці C , де функція приймає значення -42.
Максимум у точці B , де значення функції дорівнює 945.
Блок-схема алгоритму рішення задачі
Текст програми
#include <conio.h>
#include <stdio.h>
#define BR 0 //Bilshe Rivno >=
#define MR 1 //Menshe Rivno <=
#define M 2 //Menshe <
#define B 3 //Bilshe >
int main()
{
clrscr();
double buf;
int index;
double Fmin;
double Fmax;
int i,j,vOblasti;
int maxI,minI;
index=0;
maxI=minI=0;
double detA[3];
int G[2]={49,-7};
int A[20][4]= { {0,1,12,MR},
{1,-1,-10,BR},
{8,1,16,BR},
{4,2,10,BR},
{1,3,12,BR},
{-4,3,-48,BR},
{-1,3,-6,BR}};
int count=7;
double Points[30][2];
for (i=0; i < count; i++)
for ( j= i+1; j<count; j++) {
detA[0]=A[i][0]*A[j][1]-A[i][1]*A[j][0];
if(detA[0]==0)continue;
detA[1]=A[i][2]*A[j][1]-A[i][1]*A[j][2];
detA[2]=A[i][0]*A[j][2]-A[i][2]*A[j][0];
Points[index][0]=detA[1]/detA[0];
Points[index][1]=detA[2]/detA[0];
vOblasti=1;
for (int k = 0;( k < count)&&vOblasti; k++) {
double buf=Points[index][0]*A[k][0]+Points[index][1]*A[k][1];
switch (A[k][3]) {
case BR: vOblasti=buf>=A[k][2];break;
case MR: vOblasti=buf<=A[k][2];break;
case B : vOblasti=buf> A[k][2];break;
case M : vOblasti=buf< A[k][2];break;
}
}
if (vOblasti)index++;
}
printf("\tVershunu mnogokytnuka oblasti znachen' :\n\r");
for (i = 0; i < index; i++) {
printf("%c(%.2lf,%.2lf)\n",65+i,Points[i][0],Points[i][1]);
}
printf("\tTochka Max i Min :\n\r");
Fmin=G[0]*Points[0][0]+G[1]*Points[0][1];
Fmax=Fmin;
for (i = 1; i <index; i++) {
buf=G[0]*Points[i][0]+G[1]*Points[i][1];
if(Fmin>buf){Fmin=buf;minI=i;}
if(Fmax<buf){Fmax=buf;maxI=i;}
}
printf("Min %c(%.2lf,%.2lf) de G(x)=%.4lf\n",'A'+minI,
Points[minI][0],Points[minI][1],Fmin);
printf("Max %c(%.2lf,%.2lf) de G(x)=%.4lf\n",'A'+maxI,
Points[maxI][0],Points[maxI][1],Fmax);
getch();
return 0;
}
//---------------------------------------------------------------------------
Графічне рішення задачі
1) ; 2) ; 3) ; 4) ; 5) ;
6) 7)
G(x) = 49x1-7x2;
Скріншот роботи програми:
Висновки
На цій лабораторній роботі я вивчав і застосовував метод лінійного програмування для рішення задач оптимального керування, у яких цільова функція, модель процесу й обмеження є лінійними функціями.
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора