кових досліджень, було відведено вирішенню завдань лінійного програмування та їх численних модифікацій [4].
В даний час лінійне програмування є одним з найбільш уживаних апаратів математичної теорії оптимального прийняття рішення [32].
Стандартна задача лінійного програмування
Основна задача лінійного програмування виглядає наступним чином [47].
Дана система m лінійних рівнянь з n невідомими:
(1.1)
де всі невідомі можуть приймати тільки невід'ємні значення:
(1.2)
і лінійна функція від тих же змінних
(1.3)
звана цільовою функцією.
Необхідно серед всіх рішень системи рівнянь в (1.1) знайти таке невід'ємне рішення, при якому цільова функція у формулі (1.3) приймає найбільше можливе значення.
Будь-яке невід'ємне рішення системи рівнянь в (1.1) називають допустимим рішенням, а то допустиме рішення, при якому цільова функція в (1.3) приймає найменше значення, називають оптимальним рішенням задачі лінійного програмування у формулах (1.1) - (1.3). Коротко задачу формулюють так: знайти вектор, минимизирующий цільову функцію в (1.3) при лінійних обмеженнях в (1.1) і (1.2).
Якщо в конкретній задачі буде необхідно знайти найменше можливе значення деякої лінійної функції, як у формулі (1.3) при лінійних обмеженнях, то для приведення такого завдання до прийнятого нами увазі основного завдання лінійного програмування досить лінійну функцію Z замінити протилежної їй функцією
(1.4)
так як якщо функція -Z приймає найбільше значення при деяких значеннях змінних, то при тих же значеннях змінних функція Z прийме найменше можливе значення [33,47,48].
1.2 Багатокритерійна оптимізація
Методи розв'язування задач лінійного програмування з одним критерієм інтенсивно розроблялися протягом декількох десятків років. Але незабаром, у міру розвитку інформатики та технології, до сьогоднішнього дня, можна з упевненістю сказати, що будь-яка серйозна проблема характеризується більше ніж одним критерієм. Можна зрозуміти, що задачі багатокритеріальної оптимізації (МО) виникають у тих випадках, коли є кілька цілей, які не можуть бути відображені одним критерієм (наприклад, вартість, надійність і т. П.). Особи, які приймають рішення (ОПР), значно більшою мірою, ніж будь-коли, відчувають необхідність оцінювати альтернативні рішення з погляду декількох критеріїв [28,51].
Результати дослідження завдань планування та управління показують, що в реальному постановці ці завдання є багатокритеріальної. Так, часто зустрічається вираз «досягти максимального ефекту при найменших витратах» вже означає прийняття рішення при двох критеріях. Оцінка діяльності підприємств та планування як системи прийняття рішень проводиться на основі більше десятка критеріїв: виконання плану виробництва за обсягом, за номенклатурою, плану реалізації, прибутку за показниками рентабельності, продуктивності праці і т.д. [51].
Раніше, при дослідженні проблеми многокритериальности часто всі критерії, крім одного, обраного домінуючим, приймалися в якості обмежень, оптимізація проводилася по домінуючому критерію [36]. Такий підхід до вирішення практичних завдань значно знижує ефективності прийнятих рішень. Тут потрібно знайти точку області допустимих рішень, яка мінімізує або максимізує всі ці критерії. У зв'язку з цим, дослідники почали розвивати наявні теоретичні та практичні результати методів вирішення завдань з одним критерієм таким чином, щоб вони були застосовні до дослідження багатокритеріальних задач лінійного програмування [51].
Зважаючи на це в теорії багатокритеріальної оптимізації поняття оптимальності отримує різні тлумачення, і тому сама теорія містить три основні напрямки:
. Розробка концепції оптимальності.
. Доказ існування рішення, оптимального у відповідному сенсі.
. Розробка методів знаходження оптимального рішення.
Позначимо i-й приватний критерій через, а область допустимих рішень через Q. Врахуємо, що зміною знака функції завжди можна звести задачу мінімізації до задачі максимізації, і навпаки, ми можемо сформулювати коротко задачу векторної оптимізації наступним чином:
, при (1.5)
Якщо так дивитися, то по суті багатокритеріальна задача відрізняється від звичайної задачі оптимізації тільки наявністю декількох цільових функцій замість однієї. Але на відміну від завдань оптимізації з одним критерієм у багатокритеріальної оптимізації є невизначеність цілей. Дійсно, існування рішення, максимизирующего кілька цільових функцій, є рідк...
