Багатокритерiальна задача лiнiйного програмування
Дипломная работа - Компьютеры, программирование
Другие дипломы по предмету Компьютеры, программирование
1. Завдання
Розвязати багатокритерiальну задачу лiнiйного програмування з отриманням компромiсного розвязку за допомогою теоретико-iгрового пiдходу.
Задача (варiант 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. Теоретичнi вiдомостi
У цiй роботi реалiзовано вирiшування таких задач лiнiйного програмування: розвязування задач багатокритерiальноСЧ оптимiзацiСЧ, тобто пошук компромiсного рiшення для задач з кiлькома функцiями мети.
Ця задача така:
Задано обСФкт управлiння, що маСФ n входiв i k виходiв. Вхiднi параметри складають вектор X = {xj}, . Кожен з вхiдних параметрiв може мати обмеження, що накладене на область його значень. В програмi пiдтримуються параметри без обмежень на значення, i з обмеженнями невiдСФмностi (з областю ). Також на комбiнацiСЧ вхiдних значень можуть бути накладенi обмеження як система лiнiйних рiвнянь або нерiвностей:
Вихiднi сигнали обСФкта СФ лiнiйними комбiнацiями вхiдних сигналiв. Для досягнення ефективностi роботи обСФкта управлiння частину вихiдних сигналiв треба максимiзувати, iншi - мiнiмiзувати, змiнюючи вхiднi сигнали i дотримуючись обмежень на цi сигнали (задоволення усiх нерiвностей, рiвнянь i обмежень областi значень кожного з вхiдних параметрiв). Тобто вихiднi сигнали СФ функцiями мети вiд вхiдних:
Як правило, для багатокритерiальноСЧ задачi не iснуСФ розвязку, який би був найкращим (оптимальним) для усiх функцiй мети одночасно. Проте можна пiдiбрати такий розвязок, який СФ компромiсним для усiх функцiй мети (в точцi цього розвязку кожна з функцiй мети якнайменше вiдхиляСФться вiд свого оптимального значення в заданiй системi умов (обмежень).
Тут реалiзовано пошук компромiсного розвязку за допомогою теоретико-iгрового пiдходу, що був розроблений пiд керiвництвом доцента ХАРЖ Яловкiна Б.Д. Цей пiдхiд дозволяСФ знайти компромiсний розвязок з мiнiмальним сумарним вiдхиленням всiх виходiв (значень функцiй мети) вiд СЧхнiх екстремальних значень за даноСЧ системи обмежень.
Йде пошук компромiсного вектора значень змiнних в такому виглядi:
тут - вектор, що оптимальний для i-го критерiю (функцiСЧ мети); li - ваговi коефiцiСФнти.
Для отримання цього вектора виконуються такi кроки розвязування:
) РозвязуСФться k однокритерiальних задач ЛП за допомогою симплекс-методу (для кожноСЧ з функцiй мети окремо, з тiСФю самою системою обмежень, що задана для багатокритерiальноСЧ задачi). Так отримуСФмо k оптимальних векторiв значень змiнних (для кожноСЧ з цiльових функцiй - свiй).
) Пiдраховуються мiри неоптимальностi для всiх можливих пiдстановок кожного вектора значень змiнних у кожну з функцiй мети, за такою формулою:
де Cj - вектор коефiцiСФнтiв j-оСЧ функцiСЧ мети;
X*i - вектор, що оптимальний для i-оСЧ функцiСЧ мети;
X*j - вектор, що оптимальний для j-оСЧ функцiСЧ мети;
Всi цi мiри неоптимальностi складають квадратну матрицю, рядки якоСЧ вiдповiдають k оптимальним векторам X*i для кожноСЧ функцiСЧ мети, а стовпцi - k функцiям мети Cj. Ця матриця розглядаСФться як платiжна матриця матричноСЧ гри двох партнерiв X* i Z, що визначена множиною стратегiй X*={X*1, тАж, X*k} першого гравця, i Z={C1X, тАж, CkX} другого. Всi мiри неоптимальностi СФ недодатними, i СФ коефiцiСФнтами програшу першого гравця. На головнiй дiагоналi вони рiвнi нулю (бо СФ мiрами неоптимальностi оптимального вектора для своСФСЧ ж функцiСЧ).
) Матриця мiр неоптимальностi замiняСФться еквiвалентною СЧй матрицею додаванням до кожноСЧ мiри неоптимальностi , тобто найбiльшого з абсолютних значень всiх мiр. Якщо таке найбiльше значення рiвне нулю, то всi мiри рiвнi нулю, i в такому випадку замiсть нього до усiх мiр додаСФться число 1. В результатi отримуСФмо матрицю з невiдСФмними елементами. На головнiй дiагоналi усi вони рiвнi максимальному значенню. Така замiна матрицi не змiнюСФ рiшення гри, змiнюСФ тiльки СЧСЧ цiна. Тобто тепер гра маСФ вигляд не гри програшiв, а гри з пошуком максимального виграшу. Для пошуку оптимальноСЧ стратегiСЧ для першого гравця гра подаСФться як пара взаСФмнодвоСЧстих однокритерiальних задач ЛП. Для першого гравця потрiбнi значення змiнних двоСЧстоСЧ задачi :
v1=v2=тАжvk=W=--тАж-1-u1=тАж1-u2=тАж1тАжтАж.....-uk=тАж11Z =-1-1тАж-10
Розвязавши цю задачу i отримавши оптимальнi значення max(Z) = min(W), що досягаються при значеннях змiнних двоСЧстоСЧ задачi , можна обчислити ваговi коефiцiСФнти для компромiсного розвязку багатокритерiальноСЧ задачi:
,
Компром