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

1. Завдання

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

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

Z ₁ = x ₁ +2 x ₂ + x ₃ ® max

Z₂ = – x₁ –2x₂ +x₃ +x₄ ® min

Z₃ = –2x₁ –x₂ +x₃ +x₄ ® max

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

2 x ₁ – x ₂ +3 x ₃ +4 x ₄ £ 10

x ₁ + x ₂ + x ₃ – x ₄ £ 5

x ₁ +2 x ₂ –2 x ₃ +4 x ₄ £ 12

" x ³ 0

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

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

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

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

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

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

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

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

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

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

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

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

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

--> ЧИТАТЬ ПОЛНОСТЬЮ <--