Курсовая работа: Багатокритеріальна задача лінійного програмування

Курсовая работа: Багатокритеріальна задача лінійного програмування

1. Завдання

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

Задача (варіант 1):

Z1= x1+2x2+x3 ® max

Z2= – x1 –2x2+x3+x4 ® min

Z3= –2x1 –x2+x3+x4 ® max

з обмеженнями

2x1 –x2+3x3+4x4 £ 10

x1+x2+x3 –x4 £ 5

x1+2x2 –2x3+4x4 £ 12

"x ³ 0

2. Теоретичні відомості

У цій роботі реалізовано вирішування таких задач лінійного програмування: розв’язування задач багатокритеріальної оптимізації, тобто пошук компромісного рішення для задач з кількома функціями мети.

Ця задача така:

Задано об’єкт управління, що має n входів і k виходів. Вхідні параметри складають вектор X = {xj}, . Кожен з вхідних параметрів може мати обмеження, що накладене на область його значень. В програмі підтримуються параметри без обмежень на значення, і з обмеженнями невід’ємності (з областю ). Також на комбінації вхідних значень можуть бути накладені обмеження як система лінійних рівнянь або нерівностей:

Вихідні сигнали об’єкта є лінійними комбінаціями вхідних сигналів. Для досягнення ефективності роботи об’єкта управління частину вихідних сигналів треба максимізувати, інші – мінімізувати, змінюючи вхідні сигнали і дотримуючись обмежень на ці сигнали (задоволення усіх нерівностей, рівнянь і обмежень області значень кожного з вхідних параметрів). Тобто вихідні сигнали є функціями мети від вхідних:

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

Тут реалізовано пошук компромісного розв’язку за допомогою теоретико-ігрового підходу, що був розроблений під керівництвом доцента ХАІ Яловкіна Б.Д. Цей підхід дозволяє знайти компромісний розв’язок з мінімальним сумарним відхиленням всіх виходів (значень функцій мети) від їхніх екстремальних значень за даної системи обмежень.

Йде пошук компромісного вектора значень змінних в такому вигляді:

тут  – вектор, що оптимальний для i-го критерію (функції мети); li – вагові коефіцієнти.

Для отримання цього вектора виконуються такі кроки розв’язування:

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

2) Підраховуються міри неоптимальності для всіх можливих підстановок кожного вектора значень змінних у кожну з функцій мети, за такою формулою:

де Cj – вектор коефіцієнтів j-ої функції мети;

X*i – вектор, що оптимальний для i-ої функції мети;

X*j – вектор, що оптимальний для j-ої функції мети;

Всі ці міри неоптимальності складають квадратну матрицю, рядки якої відповідають k оптимальним векторам X*i для кожної функції мети, а стовпці – k функціям мети Cj. Ця матриця розглядається як платіжна матриця матричної гри двох партнерів X* і Z, що визначена множиною стратегій X*={X*1, …, X*k} першого гравця, і Z={C1X, …, CkX} другого. Всі міри неоптимальності є недодатними, і є коефіцієнтами програшу першого гравця. На головній діагоналі вони рівні нулю (бо є мірами неоптимальності оптимального вектора для своєї ж функції).

3) Матриця мір неоптимальності заміняється еквівалентною їй матрицею додаванням до кожної міри неоптимальності , тобто найбільшого з абсолютних значень всіх мір. Якщо таке найбільше значення рівне нулю, то всі міри рівні нулю, і в такому випадку замість нього до усіх мір додається число 1. В результаті отримуємо матрицю з невід’ємними елементами. На головній діагоналі усі вони рівні максимальному значенню. Така заміна матриці не змінює рішення гри, змінює тільки її ціна. Тобто тепер гра має вигляд не гри програшів, а гри з пошуком максимального виграшу. Для пошуку оптимальної стратегії для першого гравця гра подається як пара взаємнодвоїстих однокритеріальних задач ЛП. Для першого гравця потрібні значення змінних двоїстої задачі :

Розв’язавши цю задачу і отримавши оптимальні значення max(Z) = min(W), що досягаються при значеннях змінних двоїстої задачі , можна обчислити вагові коефіцієнти  для компромісного розв’язку багатокритеріальної задачі:

,

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

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

3. Вирішування

Рівняння, нерівності та функції записуються у таблицю:

Розв’язування задачі ЛП для кожної функції мети окремо:

Пошук оптимального розв’язку для функції Z1

Задача для симплекс-метода з функцією Z1

Незалежних змінних немає.

Виключення 0-рядків: немає.

Опорний розв’язок: готовий (усі вільні члени невід’ємні).

Пошук оптимального розв’язку:

Результат для прямої задачі:

У рядку-заголовку:

– x1 = 0;

– y2 = 0;

– y1 = 0;

– y3 = 0;

У стовпці-заголовку:

x3 = 2,33333333333333;

x2 = 4,55555555555556;

x4 = 1,88888888888889;

Функція мети: Z1 = 11,4444444444444.

Пошук оптимального розв’язку для функції Z2

Функцію Z2, що мінімізується, замінили на протилежну їй – Z2, що максимізується. Запис для вирішування симплекс-методом максимізації

Незалежних змінних немає.

0-рядків немає.

Опорний розв’язок: готовий.

Пошук оптимального:

Після отримання розв’язку максимізації для – Z2, взято протилежну до неї функцію Z2, і отримано розв’язок мінімізації для неї

Результат для прямої задачі:

У рядку-заголовку:

– x1 = 0;

– y2 = 0;

– x3 = 0;

– y3 = 0;

У стовпці-заголовку:

y1 = 14;

x2 = 5,33333333333333;

x4 = 0,333333333333333;

Функція мети: Z2 = -10,3333333333333.

Пошук оптимального розв’язку для функції Z3

Задача для симплекс-методу максимізації

Незалежних змінних і 0-рядків немає.

Опорний розв’язок вже готовий.

Пошук оптимального:

Результат для прямої задачі:

У рядку-заголовку:

– x1 = 0;

– x2 = 0;

– y1 = 0;

– x4 = 0;

У стовпці-заголовку:

x3 = 3,33333333333333;

y2 = 1,66666666666667;

y3 = 18,6666666666667;

Функція мети: Z3 = 3,33333333333333.

Підрахунок мір неоптимальності

Матриця мір неоптимальності та рядок функції мети, стовпець вільних членів і заголовки задачі ЛП, що будуть використані далі

До мір додана найбільша за модулем міра . Матриця у формі задачі ЛП

Розв’язування ігрової задачі:

Незалежних змінних немає.

0-рядків немає.

Опорний розв’язок вже готовий.

Пошук оптимального розв’язку:

Результат для двоїстої задачі (відносно розв'язаної):

У рядку-заголовку:

u1 = 0,402684563758389;

u3 = 0,174496644295302;

v1 = 0,319280641167655;

У стовпці-заголовку:

– v3 = 0;

– v2 = 0;

– u2 = 0;

Функція мети: Z = 0,577181208053691.

############

Вагові коефіцієнти (Li[Func]=ui/W(U)):

l[Z1] = 0,697674418604651

l[Z2] = 0

l[Z3] = 0,302325581395349

Компромісні значення змінних

x1 = 0

x2 = 3,17829457364341

x3 = 2,63565891472868

x4 = 1,31782945736434

Компромісні значення функцій мети:

Z1 = 8,9922480620155

Z2 = -2,4031007751938

Z3 = 0,775193798449612

Вирішування закінчено. Успішно.

4. Текст програми

Модуль опису класу, що виконує роботу з задачами ЛП:

unit UnMMDOpr;

interface

Uses SysUtils, Types, Classes, Forms, Controls, StdCtrls, Dialogs, Graphics,

Grids, UControlsSizes, Menus;

Const sc_CrLf=Chr(13)+Chr(10);

sc_Minus='-';

sc_Plus='+';

sc_Equal='=';

sc_NotEqual='<>';

sc_Mul='*';

sc_Space=' ';

sc_KrKm=';';

sc_BrOp=' ('; sc_BrCl=')';

sc_XVarName='x';

sc_YFuncName='y';

sc_DualTaskFuncNameStart='v';

sc_DualTaskVarNameStart='u';

sc_RightSideValsHdr='1';

sc_DestFuncHdr='Z';

sc_DualDestFuncHdr='W';

sc_TriSpot='…'; sc_Spot='.';

sc_DoubleSpot=':';

sc_DoubleQuot='"';

lwc_DependentColor:TColor=$02804000;

lwc_IndependentColor:TColor=$02FF8000;

lwc_RightSideColColor:TColor=$02FFD7AE;

lwc_HeadColColor:TColor=$02808040;

lwc_FuncRowColor:TColor=$02C080FF;

lwc_DestFuncToMaxNameColor:TColor=$024049FF;

lwc_DestFuncToMinNameColor:TColor=$02FF4940;

lwc_DestFuncValColor:TColor=$02A346FF;

lwc_ValInHeadColOrRowColor:TColor=$025A5A5A;

lwc_SolveColColor:TColor=$02AAFFFF;

lwc_SolveRowColor:TColor=$02AAFFFF;

lwc_SolveCellColor:TColor=$0200FFFF;

bc_FixedRows=2; bc_FixedCols=1;

{Кількість стовпців перед стовпцями змінних та після них,

які можна редагувати, для редагування таблиці задачі

лінійного програмування (максимізації чи мінімізації функції):}

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10