Зміст
Введення
1. Загальна постановка багатокритеріальної задачі лінійного програмування.
1.1. Формальна постановка багатокритеріальної задачі лінійного програмування.
1.2. Умова задачі
2. Рішення багатокритеріальної задачі лінійного програмування графічним методом
2.1. Формальне умова і зведення до ЗЛП
2.2. Графічне визначення 2-безлічі
3. Визначення Парето-оптимального множини з-методом
3.1. Видалення пасивних обмежень
3.2. Визначення 3-множини з-методом
4. Визначення альтернативних варіантів багатокритеріальної завдання
4.1. Метод гарантованого результату
4.2. Метод лінійної згортки приватних критеріїв
5. Складання зведеної таблиці
Висновок
Список літератури
Введення
Лише в рідких випадках цілі, які особа приймає рішення (ОПР) прагне досягти в планованої їм операції, вдається описати за допомогою одного кількісного показника. Тому фахівці Системного аналізу та Дослідження операцій вважають за доцільне уникати терміну «оптимізація», так як пошук оптимального рішення х, що доставляє функції F (x) екстремальне значення, має цілком певний сенс і давно входить в арсенал основних понять математики. Різноманіття цілей ОПР більш адекватно може бути описаний за допомогою деякої сукупності приватних критеріїв (ч-критеріїв), що характеризують ступінь досягнення приватних цілей. Суперечливий характер цілей обумовлює, як правило, і суперечливість ч-критеріїв. З формальної точки зору це призводить до того, що свої екстремальні значення ч-критерії отримують в різних точках ОДР Dx. Отже, ОПР приймаючи рішення х, завжди має йти на компроміс, в розумних межах допускаючи погіршення значень одних ч-критеріїв в ім'я покращення значень інших. Саме цей етап творчої діяльності ОПР найменш формалізуємо і вимагає залучення попереднього досвіду, інтуїції і навіть мистецтва ОПР, що володіє практичним досвідом у відповідній предметній області. Рішення, прийняте ОПР із залученням сукупності ч-критеріїв, будемо називати компромісним, раціональним або просто рішенням ОПР, уникаючи при цьому терміну «оптимальний», що має визначений та цілком точний зміст.
Основна ідея обгрунтування та прийняття рішення ОПР в умовах багатокритеріального полягає в послідовному звуженні ОДР Dx до мінімальних розмірів, що полегшує прийняття остаточного рішення ОПР. Першим, найбільш суттєвим кроком у цьому напрямку буде звуження ОДР Dx до деякого підмножини DxxDx на підставі принципу домінування.
1.Загальна багатокритеріальної постановка задачі лінійного програмування.
1.1.Формальная багатокритеріальної постановка задачі лінійного програмування.
Формальна схема багатокритеріальної ЗЛП (МЗЛП) від звичайної ЗЛП відрізняється наявністю декількох цільових функцій:
де гi - невід'ємні змінні (нев'язки, i = 1; m).
Знак max означає той факт, що бажано збільшення кожної з лінійних форм Lr (х), що відображає деяку r-ю мета ЛРП.
Вимога тільки максимізації не звужує спільності завдання. Так, наприклад, вимога мінімізації витрат деяких ресурсів еквівалентно вимозі максимізації залишку від самого початку виділених ресурсів. Налічіемногіх ч-критеріїв дозволяє зробити модель (1) - (3) більш адекватної досліджуваної ситуації, проте виводить її з класу задач МП і вимагає розробки нових способів її аналізу. Початковий аналіз МЗЛП полягає у видаленні з області допустимих рішень (ОДР) Dх явно гірших, домініруемих рішень х. Рішення х, домінує рішення х (х,> х), якщо при х, хоча б один ч-критерій має більше значення при рівності інших. Тому рішення х може бути виключено з подальшого розгляду, як явно гірше, ніж х,. Якщо рішення х, не домінує ні одним з рішень хDx, то його називають Паретто-оптимальним (а - оптимальним) або ефективним рішенням (- рішенням). Таким чином, .- рішення - це неулучшаемое (недомініруемое) рішення, і ясно, що рішення ОПР має володіти цією властивістю - інші рішення немає сенсу розглядати.
Формальне визначення о-оптимальності рішення х, записується як вимога про відсутність такого рішення х Dx, при якому б були виконані умови
і хоча б одна з них - суворо (зі знаком>).
Іншими словами, умови (4) висловлюють вимогу неможливості поліпшення рішення х, у межах ОДР Dx по жодному ч-критерію без погіршення хоча б по одному з інших.
1.2.Условіе завдання
Дано цільові функції:
L1 =-x1 + 2x2 + 2,
L2 = x1 + x2 + 4,
L3 = x1 - 4x2 + 20,
і система обмежень:
x1 + x215,
5x1 + x21,
-x1 + x25,
x220,
xj0.
2. Рішення багатокритеріальної задачі лінійного програмування графічним методом.
2.1.Формальное умова і зведення до ЗЛП
Щоб можна було перевірити умову (4) (Lr (x)) Lr (x '),' r) для деякої довільно взятої точки х,, не вдаючись до попарному порівнянні з іншими, умова,-оптимальності (4) переформуліруем у вигляді такої задачі лінійного програмування:
Сенс задачі лінійного програмування нетруднопонять, якщо врахувати, що Сr - це приріст ч-критерію Lr, що отримується при зсуві рішення х, в точку х. Тоді, якщо після рішення ЗЛП окажетсяmax = 0, то це буде означати, що жоден з ч-критеріїв не можна збільшити (max = 0), якщо не допускати зменшення будь-якого з інших (r0). Але це і є умова оптимальності-х,. Якщо ж при вирішенні виявиться, що .0, то значить якийсь ч-критерій збільшив своє значення без погіршення значень інших ((r0), і значить х, DDx.
Тепер перейдемо до вирішення нашого завдання:
L1 =-x1 + 2x2 + 2,
L2 = x1 + x2 + 4,
L3 = x1 - 4x2 + 20,
x1 + x215,
5x1 + x21,
-x1 + x25,
x220,
xj0.
Перевіримо деяку точку х, = (5; 3) (ця точка належить області Dx) на предмет)-оптимальності:
Запишемо ЗЛП в канонічному вигляді:
1 = x1 - 2x2 + 1
Dxk 2 = x1 + x2 - 8
3 =-x1 + 4x2 - 7
= X1 + 3x2 - 14,
1 = 15 - x1 - x2
2 = 5x1 + x2 - 1,
Dx3 = 5 + x1 - x2
4 = 20 - x2
xj0.
і в формі з-таблиці:
Т1 х1 х2 1
? 1 -1 -1 16
? 2 5 1 -4
? 3 1 -1 100
? 4
0 -1 10
? 1 1 -2 -4
? 2 1 1 -12
? 3 -1 1 -8
? 1 4 -24
Застосовуючи з-метод, після заміни П3х2, отримуємо:
Т2 х1? 1 1
? 1 -3/2? 29/2
? 2 11/2 -1/2 -1/2
? 3 1/2? 9/2
? 4 -1/2? 39/2
X2 1/2 -1/2 1/2
? 2 3/2 -1/2 -15/2
? 3 1 -2 -5
? 5/2 -3/2 -25/2
Бачимо, що опорний план не отримано, отже робимо ще одну заміну:? 1? х1:
Т3? 3? 1 1
x1 29/3
? 2 316/6
? 3 56/6
? 4 88/6
x2 16/3
? 2 7
? 3 14/3
? -5/3 -2/3 70/6
У Т3 отриманий опорний план. Оскільки при цьому> 0, то, отже, система ч-критеріїв не суперечлива і існує деяка область, зсув до якої рішення х, здатне збільшити, принаймні, один ч-критерій без зменшення значень інших. Ця область і є конус домінування - д - конусом Dxk (на малюнку виділено штрихуванням). При R> n д-конус може виродитися в точку х, (вершина д-конуса). Отримано ціле безліч оптимальних рішень, що витягають із Т3: х0 = (29/3; 16/3). Таким чином, рішення х, = (5; 3) не є)-оптимальним, тому що його вдалося поліпшити (-max> 0). Крім встановлення факту неефективності рішення х,, розглянутий метод дозволив визначити найближче до нього,-оптимальне рішення.
2.2. Графічне визначення .- безлічі
Спочатку необхідно побудувати графік.
Для побудови графіка необхідні наступні дані:
вихідні дані:
L1 = x1 - 2x2 + 2,
L2 = x1 + x2 + 4,
L3 =-x1 + 4x2 - 20,
в канонічному вигляді (після підстановки точки (5; 3))
1 = x1 - 2x2 + 1, (5 - 2 * 3 + 1 = 1)
Dxk 2 = x1 + x2 - 8, (5 + 3 + 4 = 12)
3 =-x1 + 4x2 - 7, (-5 + 4 * 3 - 20 = -13)
= 2x1 + 4x2 - 14,
Знаходимо точки для побудови прямих:
1) 11 = x1 - 2x2 + 1,
-x1 + 2x21 (1; 1)
2) 22 = x1 + x2 - 8,
x1 + x2 2 8 (0; 8)
3) 33 =-x1 + 4x2 - 7,
-x1 + 4x27 (1; 2)
За отриманими точками будуємо графік (малюнок 1). На малюнку штрихуванням показаний отриманий д-конус. Перехід до будь-якій точці усередині конуса забезпечує збільшення всіх критеріїв. Точка (29/3; 16/3) є)-оптімальнимрешеніем. Зміщаючи точку х, всередину д-конуса прийдемо на граніцу1. При етомд-конус вийде з області допустимих рішень (ОДР) Dx. Тепер отримана точка не зможе поліпшити жоден ч-критерій без погіршення інших, значить вона-оптимальна. Побудувавши д-конус у будь-якій точці боку -1, переконуємося, що кожна з точок,-оптимальна, значить вся сторона -1 складає-безліч.
3.Определеніе Парето-оптимального безлічі
с-методом
3.1.Удаленіе пасивних обмежень
Перед побудовою П-безлічі з системи обмежень повинні бути видалені пасивні обмеження. Пасивним будемо називати нерівність (п-нерівність), межа якого не є частиною меж області Dx, за виключенням, можливо, її окремої точки. Нерівності, що утворюють кордону Dx, назвемо активними (а-нерівності).
Щоб межі не були включені в Dxx, не маючи ніякого відношення до Dxx, нерівність, 1 має бути видалене з іншої системи обмежень. Умовою для виключення неравенстваi0 із системи є несумісні (або виродженністю) даної системи нерівностей за умови тi = 0. Геометрично це означає, що граніцаi = 0 неравенстваi0 не перетинається з областю Dx або має одну спільну точку. Якщо граніцаi = 0 має загальну кутову точку з Dx (виродженністю), то з удаленіемп-нерівності нi0 ця точка не буде втрачено, тому що вона входить в межі інших нерівностей. Крім заданих m нерівностей перевірці підлягають і n умов точність змінних, так як координатні площини (осі) також можуть входити в межі Dx.
В якості примітки можна відзначити, що оскільки п-нерівності (пасивні нерівності) для будь-якої точки xDx будуть виконані, то в міру виявлення п-нерівностей і введення їх в базис вони видаляються з з-таблиці.
Запишемо систему нерівностей Dx у формі з-таблиці:
Т1 х1 х2 1 bi/ais bi/ais
? 1 -1 -1 15 15 15
? 2 5 1 -1 1/5 1
? 3 1 -1 5 - 5
? 4 0 -1 20 - 20
Т2? 1 x2 1 Т2 'x1? 2 1
х1 -1 -1 15? 1 4 -1 14
? 2 -5 -4 74 x2 -5 1 1
? 3 -1 -2 20? 3 2 -1 4
? 4 0 -1 20? 4 1 -1 19
ОП - отримана, отже ОП - отримана, отже
х2 и1 - активні обмеження; x1 і 2 - активні обмеження;
з Т2 отримуємо:
Т3? 1? 3 1
x1 1 1/2 5
? 2 -3 2 34
x2 -1/2 -1/2 10
? 4 2? 10
звідси робимо висновок, що? 3 - активне обмеження;
з Т3 отримуємо:
Т4? 4? 3 1
x1 10
? 2 19
x2 15/2
? 1 -5
Опорний план не отримано, отже О4 - пасивне обмеження.
3.2.Определеніе О-множини з-методом.
При підготовці рішення для ОПР інтерес буде представляти інформація про все безлічі П-оптимальних (ефективних) рішень Dxx. Графічний метод дозволяє сформулювати досить простий підхід до визначення безлічі Dxx. Суть цього підходу в наступному. Вирішуючи усічену задачу лінійного програмування, встановлюємо факт існування д-конуса (. Max> 0). Оскільки для лінійних ЦФ конфігурація д-конуса не залежить від положення його вершини х,, то, розміщуючи її на кордон, i області Dx, вирішуємо усічену ЗЛП з додаванням, i, що відповідає i-му ділянки кордонів Dx. Виродження д-конуса в точку х, буде ознакою-оптимальності і всіх інших точок даної межі. За допомогою з-методу зазначена процедура легко проробляється для простору будь-якої розмірності n. Незручність зазначеного методу полягає в тому, що буде потрібно на кожній грані ОДР Dx знайти точку х, (за кількістю граней Dx) сформулювати і вирішити стільки ж ЗЛП розміру Rxn.
Істотно скоротити обсяг обчислень можна шляхом вибору вершінид-конуса у фіксованій точці х, = (1) n і в неї ж паралельно собі перенести межі, що становлять кордону Dx
Наведені до точки х, = (1) n приросту-r і невязкіi запишуться у вигляді:
де межа зверху у г,, іозначает, що ці величини приведені до точкех, = (1) n.
По суті, (8) - ЗЛП розміру (R + m) xn (max), а її рішення дозволить знайти всі грані, що становлять е-безліч Dxx.
Складаємо з-таблицю, не враховуючи пасивні обмеження, тобто С1:
Т1 х1 х2 1
? 2 -1 -1 2
? 3 5 1 -6
? 4 1 -1 0
х1 1 0 -1
х2 0 1 -1
? 1 1 -2 1
? 2 1 1 -2
? 3 -1 4 -3
? 1 3 -4
На початку вирішується усічена ЗЛП (під рисою):
Т2 х1? 1 1
? 1 -3/2 1/2 3/2
? 2 11/2 -1/2 -11/2
? 3 1/2 1/2 -1/2
х1 1 0 -1
х2 1/2 -1/2 -1/2
x2 1/2 -1/2 1/2
? 2 3/2 -1/2 -3/2
? 3 1 -2 -1
? 5/2 -3/2 -5/2
Т3? 3? 1 1
? 1 -3/2 -5/2 0
? 2 11/2 21/2 0
? 3 1/2 3/2 0
х1 1 2 0
х2 1/2 1/2 0
x2 1/2 1/2 1
? 2 3/2 5/2 0
x1 1 2 1
? 5/2 7/2 0
Т4? 1? 1 1
? 3 0
x2 1
? 2 0
x1 1
? -5/3 -2/3 0
? 1? Dx?, Так як? Max = 0.
Даний метод побудови безлічі Dxx має недоліком, пов'язаним з руйнуванням області допустимих рішень (ОДР) Dx при перенесенні її граней в х,. Дійсно, вершини області Dx в перетвореної моделі ніяк не відображені, а саме одна з них може скласти-безліч в разі його збігу з оптимальним рішенням. Такий збіг можливо, якщо все ч-критерії досягають максимум на одній вершині. Фізично це означає, що вони слабопротіворечіви - кут при вершині д-конуса наближається до 180с (градієнти ч-критеріїв мають практично збігаються напрямку). Даний випадок має місце, якщо по-безліч не увійшла жодна з граней ОДР Dx. Отже,-безліч збігається з оптимальним рішенням. Для визначення - безлічі вирішується звичайна ЗЛП з одним з ч-критеріїв. Якщо при цьому отримано безліч оптимальних рішень, то вирішується ЗЛП з іншим ч-критерієм. Перетин оптимальних рішень і є а-безліччю. Для ОПР вказівка на те, що деяка грань-i = iiDxx-оптимальна, є тільки узагальненою інформацією.
4.Визначення альтернативних варіантів багатокритеріальної завдання
Найбільш природним і розумним рішенням мк-завдання було б органічне об'єднання всіх ч-критеріїв у вигляді єдиної ЦФ. Іноді це вдається зробити шляхом створення більш загальної моделі, в якій ч-критерії є аргументами більш загальної цільової функції, що об'єднує в собі всі приватні цілі операції. На практиці цього рідко вдається досягти, що, власне, і є основною причиною появи проблеми багатокритеріального. Проте найбільш поширений підхід до вирішення проблеми поки що залишається все-таки один: тим чи іншим шляхом звести рішення мк-завдання до вирішення однокрітеріальним завдання. В основі підходу лежить припущення про існування якоїсь функції корисності, що поєднує в собі ч-критерії, але яку в явному вигляді, як правило, отримати не вдається. Отримання найбільш обгрунтованою «пакунки» ч-критеріїв є предметом досліджень нового наукового напрямку, що виник у зв'язку з проблемою багатокритеріального - теорії корисності. У даній роботі будуть розглянуті деякі підходи, що дозволяють отримати варіанти вирішення мк-завдань при тих чи інших посилках і які особа приймає рішення (ОПР) повинна розглядати як альтернативні при прийнятті остаточного рішення і які, звичайно, повинні задовольняти необхідному умові-н-оптимальності.
4.1.Метод гарантованого результату
При будь-якому довільному рішенні х П Dx кожен з ч-критеріїв прийме певне значення і серед них знайдеться, принаймні, одна, значення якого буде найменшим:
Метод гарантованого результату (ГР) дозволяє знайти таке (гарантоване) рішення, при якому значення «найменшого» критерію стане максимальним. Таким чином, цільова функція (ЦФ) є деякою згортком ч-критеріїв (9), а МЗЛП зводиться до задачі КВП (кусково-лінійного програмування) при ОДР Dx, заданої лінійними обмеженнями.
Вихідні умови записуємо в канонічному вигляді:
1 = х1 - 2х2 - + 2,
2 = х1 + х2 - + 4,
3 =-х1 + 4х2 - + 20,
1 =-х1 - х2 + 15,
2 = 5х1 + х2 - 1,
3 = x1 - х2 + 5,
потім у вигляді з-таблиці:
Т1 х1 х2? 1
? 1 -1 -1 0 15
? 2 5 1 0 -1
? 3 1 -1 0 5
? 1 1 -2 -1 2
? 2 1 1 -1 4
? 3 -1 4 -1 20
Запроваджуючи в базис змінну? (? 1??), Отримуємо звичайну ЗЛП при максимізації ЦФ?.
Т2 х1 х2? 1 1
? 1 -1 -1 0 15
? 2 5 1 0 -1
? 3 1 -1 0 5
? 1 -2 -1 2
? 2 0 3 1 2
? 3 -2 6 1 18
Т3? 3 x2? 1 1 bi/ais
? 1 1/2 -4 -1/2 6 6/4
? 2 -5/2 16 5/2 44 -
? 3 -1/2 2 2 14 -
? -1/2 1 -1/2 11 -
? 2 0 3 -1 2 -
х1 -1/2 3 1/2 9 -
Т4? 3? 1? 1 1
x2 3/2
? 2 68
? 3 17
? -3/8 -1/4 -5/8 25/2
? 2 13/2
х1 27/2
Рішення ЗЛП призводить до кінцевої з-таблиці Т4. Видно, що отримане гарантоване вирішення х .- оптимально, оскільки введення в базис будь-якій вільній змінної (тобто її збільшення) призведе до зниження е - нижнього рівня ч-критеріїв (сj <0). З таблиці також видно, що рішення х0 = (27/2; 3/2) знаходиться на межі) 4, при цьому значення ч-критеріїв рівні (знаходимо по формулі Lr (xr) =) + r):>
L1 = L3 = = 25/2
L2 = +2 = 25/2 + 13/2 = 19
LL = 88/2 = 44
xx = (27/2; 3/2)
Якщо б у рядку Е були нулі, то це означало б, що одну з відповідних змінних можна ввести в базис (збільшити без зниження рівня). Це могло б призвести і до збільшення приросту лr для некоторогоч-критерію, що знаходиться в базисі.
4.2.Метод лінійної згортки приватних критеріїв
Лінійна згортка ч-критеріїв виходить як х сума з деякими ваговими коеффіціентаміr:
де
Змінюючи порядок підсумовування і вводячи позначення cj і c0, остаточно отримаємо:
Коефіцієнти ваги зазвичай виходять шляхом опитування експертів з відповідної предметної області. Оскільки вектор про = (r) - суть вектор-градієнт ЦФ LL (x), то передбачається, що він вказує напрямок до екстремуму невідомої функції корисності. Позитивна сторона такого підходу - нескладність, не завжди компенсує його серйозний недолік - втрату фізичного значення лінійної згортки різнорідних ч-критеріїв. Це ускладнює інтерпретацію результатів, тому отримане таким шляхом рішення, слід розглядати тільки як можливий (альтернативний) варіант рішення ОПР. Для його порівняльного аналізу слід залучати будь-які інші варіанти і, звичайно, значення ч-критеріїв, одержувані при цьому. Іноді при отриманні згортки ч-критеріїв попередньо нормуються яким-небудь способом.
Найбільш прийнятною лінійна згортка ч-критеріїв може опинитися в тому випадку, коли ч-критерії однорідні і мають єдиний еквівалент, що погоджує їх найбільш природним чином.
На змістовному рівні дана МЗЛП полягає у необхідності прийняття такого компромісного рішення (плану випуску продукції) xkDx, яке забезпечить, по можливості, найбільшу сумарну виручку L1 (x) отреалізаціі виробленої продукції; найменший витрата ресурсів i-го виду Lpl (x) (i = 1; m); мінімальні податкові відрахування від прибутку LH (x) (або загальної виручки).
Зазначені цілі носять суперечливий характер, і фактично ми маємо МЗЛП з m +2-ч-ма критеріями (m - кількість видів споживаних ресурсів). ОДР обумовлена ресурсними обмеженнями та умовами невід'ємних змінних:
де aij - витрата ресурсу i-го виду для випуску 1 одиниці продукції j-го виду (j = 1, n);
bi - запас ресурсу i-го виду;
i - залишок ресурсу i-го виду при плані випуску x = (xj) n. Ч-критерії однорідні, якщо вони можуть бути зведені до єдиної мірою виміру. В якості такого заходу можна взяти грошовий еквівалент. Тоді m 2 ч-критерію можуть бути за допомогою лінійної згортки зведені до трьох:
общаявиручка (руб.):
загальна економія ресурсів (руб.):
податкові відрахування (руб.):
де cj - виручка від реалізації 1 од. продукції j-го виду (ціна); si - вартість (ціна) 1 од. ресурсу i-го виду (i = 1; m); Пj - прибуток від реалізації 1 од. продукції j-го виду (j = 1; n); aj - частка (відсоток податкових відрахувань від прибутку (виручки).
На закінчення зазначимо, що коефіцієнти Вr не обов'язково повинні задовольняти умові (10), але обов'язково повинні бути позитивними, якщо все ч-критерії максимізують.
Перейдемо до вирішення:
Т1 х1 х2 1
? 1 -1 -1 15
? 2 5 1 -1
? 3 1 -1 5
L1 1 -2 2
L2 1 1 4
L3 -1 4 20
L? 1 3 26
Т2? 1 x2 1
x1 -1 -1 15
? 2 -5 -4 74
? 3 -1 -2 20
L1 -1 -1 17
L2 -1 0 19
L3 1 5 5
L? -1 2 41
L1 max = 17
L2 max = 19
L3 = 5
L? = 41
Т3? 1 L1 1
x1 28/3
? 2 154/3
? 3 26/3
x2 17/3
L2 19
L3 -2/3 -5/3 100/3
L? -5/3 -2/3 157/3
5. Складання зведеної таблиці.
Остаточне рішення зводиться до таблиці, де записуються альтернативні варіанти:
Метод х0 L1 L2 L3 L?
Метод гарантованого результату
(27/2; 3/2)
25/2
19
25/2
44
Метод згортки (28/3; 17/3) 0 19 33 1/3 52 1/3
Оптимізація L1 (15; 0) 17 19 5 41
Оптимізація
L2, L3 (28/3; 17/3) 0 19 33 1/3 52 1/3
x? Dx? (5; 3) 1 12 -13 0
