Міністерство освіти і науки України Національний університет «Львівська політехніка» Кафедра АСУ Звіт про виконання лабораторної роботи № 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/ для роботи на нижній границі. Індивідуальне завдання: Варіант 2 Цільова функція Модель процесу Обмеження Виконання завдання Підстановка у: F(x1, x2) = 31х1 +74х2 Пошук лінії рівня: 31х1 -74х2 = 310 Лінія рівня: (0; 4,1) (10; 0) Пошук градієнта: Градієнт: (0;0) (31; 74) Графік обмежень: Пошук крайніх точок за методом Крамера Обмеження 4 і 6: Delta = 1 * 3 – 1 * (-1) = 4 Delta1 = 10 * 3 – 1 * (-6) =36 Delta2 = 1 * (-6) - 10 * (-1) = 4 Перетин в точці (9; 1). Обмеження 7 і 6: Delta = -1 * 3 – 3 * (-4) = 9 Delta1 = -6 * 3 – 3 * (-48) = 126 Delta2 = -1 * (-48) – (-6) * (-4) = 24 Перетин в точці (14; 2,7). Обмеження 7 і 8: Delta = -4 * 0 – 3 * 1 = -3 Delta1 = -48 * 0 – 16 * 3 = -48 Delta2 = -4 * 16 - 1 * (-48) = -16 Перетин в точці (16; 5,3) Обмеження 8 і 9: Delta = 1 * 4 – 0 * 1 = 4 Delta1 = 16 * 4 – 56 * 0 = 64 Delta2 = 1 * 56 – 16 * 1 = 40 Перетин в точці (16; 10). Обмеження 1 і 9: Delta = 0 * 4 – 1 * 1 = -1 Delta1 = 12 * 4 – 56 * 1 = -8 Delta2 = 0 * 56 – 1 * 12 = -12 Перетин в точці (8; 12). Обмеження 1 і 3: Delta = 0 * (-1) – 1 * 1 = -1 Delta1 = 12 * (-1) – (-10) * 1 = -2 Delta2 = 0 * (-10) – 1 * 12 = -12 Перетин в точці (2; 12). Перетин 4 і ОX2: (0; 10). Підставивши координати знайдених точок в цільову функцію маємо, що: Мінімальне значення 353 функція мети набуває в точці (9; 1). Максимальне значення 1236 функція мети набуває в точці (16; 10). Текст програми class LPSolver { private const int SIZE = 30; private PurposeFunction purpose = new PurposeFunction(); private Y y = new Y(); private List<Limitation> limitsList = new List<Limitation>(); private List<Double> valueList = new List<Double>(); public int sizeR, sizeC; private Point[,] pointsMs = new Point[SIZE, SIZE]; private List<Point> areaPoints = new List<Point>(); private Point maxPoint; private Point minPoint; private double max, min; public LPSolver(PurposeFunction purpose, Y y, List<Limitation> limitsList) { this.purpose.setA(purpose.getA()); this.purpose.setB(purpose.getB()); this.purpose.setC(purpose.getC()); this.y = y; for (int i = 0; i < limitsList.Count(); i++) { this.limitsList.Add(new Limitation(limitsList[i].getNum(), limitsList[i].getA(), limitsList[i].getB(), limitsList[i].getC(), limitsList[i].getZ(), limitsList[i].getSign())); } addY(); } public Point[,] findCrossingPoints() { int i, j; for(j = 0, i = 0; j < limitsList.Count(); j++, i = 0) { pointsMs[i, j] = findCrossingWithOX(limitsList[j]); isInArea(pointsMs[i++, j]); pointsMs[i,j] = findCrossingWithOY(limitsList[j]); isInArea(pointsMs[i++,j]); for (; i - 2 < limitsList.Count(); i++) if(j == i - 2) continue; else { pointsMs[i,j] = findCrossingPoint(limitsList[j], limitsList[i - 2]); isInArea(pointsMs[i,j]); } sizeR = i; } sizeC = j; return pointsMs; } public List<Point> getAreaPoints() { for (int i = 0; i < SIZE; i++) for(int j = 0; j < SIZE; j++) if (pointsMs[i,j] != null) if (pointsMs[i, j].getisInArea()) { areaPoints.Add(pointsMs[i,j]); foreach (Point areaPoint in areaPoints) // уникаємо повторень if (areaPoint.getX() == pointsMs[i,j].getX() && areaPoint.getY() == pointsMs[i,j].getY()) { areaPoints.RemoveAt(areaPoints.Count() - 1); break; } } return areaPoints; } public Point getPurposeMinPoint() { return minPoint; } public Point getPurposeMaxPoint() { return maxPoint; } public double findPurposeMaxValue() { return max; } public double findPurposeMinValue() { /* double value = -1; minPoint = new Point(-1, -1); for(Point point : areaPoints) if((value = (purpose.getA()*point.getX() + purpose.getB() * point.getY())) < min) { min = value; minPoint = point; }*/ return min; } public void findPurposeValues() { double value = -1; max = -1; min = 100000; maxPoint = new Point(-1, -1); foreach(Point point in areaPoints) { if ((value = (purpose.getA() * point.getX() + purpose.getB() * point.getY())) > max) { max = value; maxPoint = point; } if((value = (purpose.getA()*point.getX() + purpose.getB() * point.getY())) < min) { min = value; minPoint = point; } valueList.Add(value); } } public List<Double> getValueList() { return valueList; } private Point findCrossingPoint(Limitation limit1, Limitation limit2) { double del, del1, del2; double a11 = limit1.getA(); double a12 = limit1.getB(); double a21 = limit2.getA(); double a22 = limit2.getB(); double b11 = limit1.getZ(); double b21 = limit2.getZ(); del = a11 * a22 - a21 * a12; del1 = b11 * a22 - b21 * a12; del2 = a11 * b21 - a21 * b11; return new Point(del1/del, del2/del); } private Point findCrossingWithOX(Limitation limit) { if(limit.getA() == 0) return null; else return new Point(limit.getZ()/limit.getA(), 0); } private Point findCrossingWithOY(Limitation limit) { if(limit.getB() == 0) return null; else return new Point(0, limit.getZ()/limit.getB()); } private void addY() { if(y == null) return; foreach(Limitation item in this.limitsList) if(item.getC() != 0) { item.setA(item.getA() + y.getA() * item.getC()); item.setB(item.getB() + y.getB() * item.getC()); } if(purpose.getC() == 0) return; this.purpose.setA(purpose.getA() + y.getA() * purpose.getC()); this.purpose.setB(purpose.getB() + y.getB() * purpose.getC()); } private void isInArea(Point point) { if(point == null) return; foreach(Limitation limit in limitsList) if(limit.getSign() == 1) { if (limit.getA() * point.getX() + limit.getB() * point.getY() < limit.getZ()) { return; } } else if(limit.getSign() == -1) if(limit.getA() * point.getX() + limit.getB() * point.getY() > limit.getZ()) { return; } point.setInArea(true); foreach (Point p in areaPoints) if(p.getX() == point.getX() && p.getY() == point.getY()) return; areaPoints.Add(point); } } Результат виконання Висновок У результаті виконання цієї лабораторної роботи я навчилася працювати із задачею лінійного програмування з метою вирішення задач оптимізаційного керування при заданих, у вигляді лінійних функцій, цільової функції, обмежень та моделі процесу. Я навчилася програмувати алгоритм роботи системи розв’язку задач лінійного програмування для двовимірної задачі, що розв’язується графічним методом.