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

{координати комірки мають бути записані у CurGridSolveRow і CurGridSolveCol:}Self. CurGridSolveRow=-bc_LTaskRowsBeforeVars then{якщо це комірка рядка-заголовка:}Length (Self. CurHeadRow)>Self. CurGridSolveCol then {якщо комірка

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

Дипломная работа

Компьютеры, программирование

Другие дипломы по предмету

Компьютеры, программирование

Сдать работу со 100% гаранией

1. Завдання

 

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

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

 

Z1= x1+2x2+x3 ® max

Z2= - x1 -2x2+x3+x4 ® min3= -2x1 -x2+x3+x4 ® max

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

x1 -x2+3x3+4x4 £ 10

x1+x2+x3 -x4 £ 5

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

"x ³ 0

 

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

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

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

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

 

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

 

 

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

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

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

 

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

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

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

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

 

 

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

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

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

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

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

 

v1=v2=…vk=W=--…-1-u1=1-u2=1…….....-uk=11Z =-1-1…-10

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

 

,

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

 

 

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

 

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

 

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

 

 

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

 

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

 

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

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

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

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

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

 

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

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

x1 = 0;

y2 = 0;

y1 = 0;

y3 = 0;

У стовпці-заголовку:= 2,33333333333333;= 4,55555555555556;= 1,88888888888889;

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

 

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

 

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

 

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

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

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

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

 

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

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

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

x1 = 0;

y2 = 0;

x3 = 0;

y3 = 0;

У стовпці-заголовку:= 14;= 5,33333333333333;= 0,333333333333333;

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

 

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

 

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

 

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

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

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

 

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

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

x1 = 0;

x2 = 0;

y1 = 0;

x4 = 0;

У стовпці-заголовку:= 3,33333333333333;= 1,66666666666667;= 18,6666666666667;

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

 

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

 

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

 

 

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

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

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

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

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

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

 

 

 

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

У рядку-заголовку:= 0,402684563758389;= 0,174496644295302;= 0,319280641167655;

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

Похожие работы

1 2 3 4 5 > >>