Решение многокритериальной завдання лінійного програмирования

1. Загальна постановка многокритериальной завдання лінійного программирования.

1.1. Формальна постановка многокритериальной завдання лінійного программирования.

1.2. Умова задачи.

2. Рішення многокритериальной завдання лінійного програмування графічним методом.

2.1. Формальне умова і зведення до ЗЛП.

2.2. Графічне визначення 2-множества.

3. Визначення Парето-оптимального безлічі с-методом.

3.1. Видалення пасивних ограничений.

3.2. Визначення 3-множества с-методом.

4. Визначення альтернативних варіантів многокритериальной задачи.

4.1. Метод гарантованого результата.

4.2. Метод лінійної пакунки приватних критериев.

5. Упорядкування зведеної таблицы.

Заключение

.

Лише в рідкісних випадках мети, які обличчя яка набирає рішення (ЛПР) прагне досягти в планованої їм операції, вдається описати з допомогою одного кількісного показника. Тому фахівці Системного аналізу і Дослідження операцій вважають доцільним уникати терміна «оптимізація», так як пошук оптимального рішення x, що доносить функції F (x) екстремальна значення, має цілком певний сенс і давно входить в арсенал основних понять математики. Розмаїття цілей ЛПР більш адекватно може бути описано з допомогою деякою сукупності приватних критеріїв (ч-критериев), характеризуючих ступінь досягнення приватних цілей. Суперечливий характер цілей зумовлює, як правило, і суперечливість ч-критериев. З формальної точки зору це наводить до тому, що свої екстремальні значення ч-критерии отримують в різних точках ТДР Dx. Отже, ЛПР приймаючи рішення x, завжди має йти на компроміс, в розумних межах допускаючи погіршення значень одних ч-критериев у ім'я поліпшення значень інших. Саме цей етап творчої діяльності ЛПР найменш формализуем і вимагає залучення попереднього досвіду, інтуїції і навіть мистецтва ЛПР, який володіє практичним досвідом в відповідної предметної області. Рішення, прийняте ЛПР з залученням сукупності ч-критериев, будемо називати компромісним, раціональним чи просто рішенням ЛПР, уникаючи при цьому терміна «оптимальний», має певний і цілком точний смысл.

Основна ідея обгрунтування і прийняття рішення ЛПР в умовах многокритериальности полягає в послідовному звуження ТДР Dx до мінімальних розмірів, що полегшує прийняття остаточного рішення ЛПР. Першим, найбільш істотним кроком в цьому напрямі буде бути звуження ТДР Dx до деякого підмножини DxxDx на підставі принципу доминирования.

1.Общая постановка многокритериальной завдання лінійного программирования.

1.1.Формальная постановка многокритериальной завдання лінійного программирования.

Формальна схема многокритериальной ЗЛП (МЗЛП) від звичайній ЗЛП відрізняється наявністю кількох цільових функций:

де гi — неотрицательные перемінні (невязки, і = 1; m).

Знак max означає той факт, що бажано збільшення кожної з лінійних форм Lr (х), що відбиває деяку r-ю мета ЛРП.

Вимога лише максимізації не звужує спільності завдання. Так, наприклад, вимога мінімізації витрат деяких ресурсів еквівалентно вимозі максимізації залишку від спочатку виділених ресурсів. Наличиемногих ч-критериев дозволяє зробити модель (1) — (3) більш адекватної досліджуваної ситуації, проте виводить її з класу завдань МП і вимагає розробки нових способів її аналізу. Початковий аналіз МЗЛП полягає в видаленні з області допустимих рішень (ТДР) Dх явно гірших, доминируемых рішень x. Рішення x, домінує рішення x (x, > x), якщо при x, хоча б один ч-критерий має більше значення при рівність інших. Тому рішення x може бути виключено з подальшого розгляду, як явно гірше, ніж x,. Якщо рішення x, не доминируется ні одним з рішень хDx, то його називають Паретто-оптимальным (а — оптимальним) чи ефективним рішенням (- рішенням). Таким чином, .-рішення — це неулучшаемое (недоминируемое) рішення, і ясно, що рішення ЛПР має мати цим властивістю — інші рішення немає сенсу рассматривать.

Формальне визначення о-оптимальности рішення x, записується як вимога про відсутності такого рішення x Dx, при якому б були виконані условия.

і хоча б одне з них — суворо (зі знаком >).

Іншими словами, умови (4) висловлюють вимога неможливості поліпшення рішення x, в межах ТДР Dx ні по одному ч-критерию без погіршення хоча б по одному з других.

1.2.Условие задачи.

Дани цільові функции:

L1 = -x1 + 2×2 + 2,.

L2 = x1 + x2 + 4,.

L3 = x1 — 4×2 + 20,.

і система ограничений:

x1 + x215,.

5x1 + x21,.

— x1 + x25,.

x220,.

xj0.

2. Рішення многокритериальной завдання лінійного програмування графічним методом.

2.1.Формальное умова і зведення до ЗЛП.

Щоб можна було перевірити умова (4) (Lr (x)) Lr (x'),'r) для деякою довільно взятій точки x, не вдаючись до попарному порівнянню з іншими, умова ,-оптимальності (4) переформулюємо в вигляді наступній завдання лінійного программирования:

Сенс завдання лінійного програмування нетруднопонять, якщо врахувати, що Сr — це прирощення ч-критерия Lr, одержуване під час усунення рішення x, в точку x. Тоді, якщо після рішення ЗЛП окажетсяmax = 0, то це буде означати, що ні один з ч-критериев не можна збільшити (max = 0), якщо не допускати зменшення будь-якого з інших (r0). Але це і є условие-оптимальности x,. Якщо ж при рішенні виявиться, що .0, то отже якийсь ч-критерий збільшив своє значення без погіршення значень інших ((r0), і отже х, DDx.

Тепер перейдемо до рішенню нашої задачи:

L1 = -x1 + 2×2 + 2,.

L2 = x1 + x2 + 4,.

L3 = x1 — 4×2 + 20,.

x1 + x215,.

5x1 + x21,.

— x1 + x25,.

x220,.

xj0.

Перевіримо деяку точку x, = (5; 3) (ця точка належить області Dx) на предмет)-оптимальности:

Запишемо ЗЛП в канонічному виде:

1 = x1 — 2×2 + 1.

Dxk 2 = x1 + x2 — 8.

3 = -x1 + 4×2 — 7.

= x1 + 3×2 — 14,.

1 = 15 — x1 — x2.

2 = 5×1 + 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 -½ -½.

?3 ½? 9/2.

?4 -½? 39/2.

X2 ½ -½ 1/2.

?2 3/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, то, отже, система ч-критериев не суперечлива і існує деяка область, усунення в яку рішення x, здатне збільшити, по крайньої мері, один ч-критерий без зменшення значень інших. Ця область і є конус домінування — буд — конусом Dxk (на малюнку виділено штрихуванням). При R > n д-конус може виродитися в точку x, (вершина д-конуса). Отримано ціле безліч оптимальних рішень, извлекаемое з Т3: х0 = (29/3; 16/3). Таким чином, рішення x, = (5; 3) не є)-оптимальним, так як його вдалося поліпшити (-max>0). Крім встановлення факту неефективності рішення x, розглянутий метод дозволив визначити найближче до нього ,-оптимальне решение.

2.2. Графічне визначення .-множества.

Спочатку необхідно побудувати график.

Для побудови графіка необхідні такі данные:

вихідні данные:

L1 = x1 — 2×2 + 2,.

L2 = x1 + x2 + 4,.

L3 = -x1 + 4×2 — 20,.

в канонічному вигляді (після підстановки точки (5;3)).

1 = x1 — 2×2 + 1, (5 — 2*3 + 1= 1).

Dxk 2 = x1 + x2 — 8,(5 + 3 + 4 = 12).

3 = -x1 + 4×2 — 7,(-5 + 4*3 — 20 = -13).

= 2×1 + 4×2 — 14,.

Знаходимо точки для побудови прямых:

1) 11 = x1 — 2×2 + 1,.

— x1 + 2×21(1;1).

2) 22 = x1 + x2 — 8,.

x1 + x2 2 8(0;8).

3) 33 = -x1 + 4×2 — 7,.

— x1 + 4×27 (1;2).

По отриманим точкам будуємо графік (малюнок 1). На малюнку штрихуванням показаний отриманий д-конус. Перехід до будь-який точці всередині конуса забезпечує збільшення всіх критеріїв. Крапка (29/3; 16/3) є)-оптимальнымрешением. Усуваючи З Посади точку x, всередину д-конуса прийдемо на границу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×2 1 Т2' x1 ?2 1.

х1 -1 -1 15 ?1 4 -1 14.

?2 -5 -4 74×2 -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 ½ 5.

?2 -3 2 34.

x2 -½ -½ 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). Оскільки для лінійних ЦФ конфігурація д-конуса не залежить від становища його вершини x, то, поміщаючи її на кордон ,і області Dx, вирішуємо усічену ЗЛП з додаванням ,і, відповідного i-му ділянці кордонів Dx. Виродження д-конуса в точку x, буде признаком-оптимальности і всіх інших точок даної межі. З допомогою с-метода зазначена процедура легко виконується для простору будь-який розмірності n. Незручність зазначеного методу полягає в тому, що знадобиться на кожної межі ТДР Dx знайти точку x, (по числу граней Dx) сформулювати і вирішити стільки ж ЗЛП розміру Rxn.

Істотно скоротити обсяг обчислень можна шляхом вибору вершиныд-конуса в фіксованою точці x, = (1)n і в неї ж паралельно собі перенести межі, складові кордону Dx.

Наведені до точці x, = (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 ½ 3/2.

?2 11/2 -½ -11/2.

?3 ½ 1/2 -½.

х1 1 0 -1.

х2 ½ -½ -½.

x2 ½ -½ 1/2.

?2 3/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 ½ 3/2 0.

х1 1 2 0.

х2 ½ 1/2 0.

x2 ½ 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 при перенесення її граней в x,. Справді, вершини області Dx в реформованій моделі ніяк не відбиті, а саме одна з них може составить-множество в разі його збіги з оптимальним рішенням. Таке збіг можливо, якщо все ч-критерии досягають максимум на однієї вершині. Фізично це отже, що вони слабопротиворечивы — кут при вершині д-конуса наближається до 180с (градієнти ч-критериев мають практично збіжні напрями). Цей випадок має місце, якщо в-множество не ввійшла ні одна з граней ТДР Dx. Следовательно,-множество збігається з оптимальним рішенням. Для визначення —безлічі вирішується звичайна ЗЛП з одним з ч-критериев. Якщо при цьому отримано безліч оптимальних рішень, то вирішується ЗЛП з іншим ч-критерием. Перетин оптимальних рішень і є а-множеством. Для ЛПР вказівку на то, що деяка граньі = iiDxxоптимальна, є лише узагальненої информацией.

4.Определение альтернативних варіантів многокритериальной задачи.

Найбільш природним і розумним рішенням мк-задачи було б органічне об'єднання всіх ч-критериев в вигляді єдиної ЦФ. Іноді це вдається зробити шляхом створення більш загальної моделі, в якої ч-критерии є аргументами більш загальної цільової функції, об'єднуючою в собі все приватні мети операції. На практиці цього рідко вдається досягти, що, власне, і є основний причиною появи проблеми многокритериальности. Проте найбільш поширений підхід до рішенню проблеми поки залишається все-таки один: тим чи іншим шляхом звести рішення мк-задачи до рішенню однокритериальной завдання. У основі підходу лежить припущення про існуванні певної функції корисності, об'єднуючою в собі ч-критерии, але яку в явному вигляді, як правило, отримати не вдається. Одержання найбільш обгрунтованою «пакунки» ч-критериев є предметом досліджень нового наукового напрями, виниклого в зв’язку з проблемою многокритериальности — теорії корисності. У даної роботі будуть розглянуті деякі підходи, дозволяють отримати варіанти рішення мк-задач при тих чи інших посилках і які обличчя яка набирає рішення (ЛПР) має розглядати як альтернативні при прийнятті остаточного рішення і які, звісно, повинні задовольняти необхідного условию-н-оптимальности.

4.1.Метод гарантованого результата.

При будь-якому довільному рішенні x П 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×2 ?1 1 bi/ais.

?1 ½ -4 -½ 6 6/4.

?2 -5/2 16 5/2 44 ;

?3 -½ 2 2 14 ;

? -½ 1 -½ 11 ;

?2 0 3 -1 2 ;

х1 -½ 3 ½ 9 ;

Т4 ?3 ?1 ?1 1.

x2 3/2.

?2 68.

?3 17.

? -3/8 -¼ -5/8 25/2.

?2 13/2.

х1 27/2.

Рішення ЗЛП наводить до кінцевої с-таблице Т4. Очевидно, що отримане гарантоване рішення x .-оптимально, оскільки запровадження в базис будь-який вільної перемінної (тобто. її збільшення) призведе до зниження е — нижнього рівня ч-критериев (с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.Метод лінійної пакунки приватних критериев.

Лінійна згортка ч-критериев виходить як x сума з деякими ваговими коэффициентамиr:

где.

Змінюючи порядок підсумовування і вводячи позначення cj і c0, остаточно получим:

Коефіцієнти ваги зазвичай виходять шляхом опитування експертів з відповідної предметної області. Оскільки вектор про = (r) — суть вектор-градиент ЦФ LL (x), то передбачається, що він вказує напрям до экстремуму невідомої функції корисності. Позитивна сторона такого підходу — нескладність, не завжди компенсує його серйозний недолік — втрату фізичного сенсу лінійної пакунки різнорідних ч-критериев. Це утрудняє інтерпретацію результатів, тому отримане таким шляхом рішення, слід розглядати лише як можливий (альтернативний) варіант рішення ЛПР. Для його порівняльного аналізу слід залучати будь-які інші варіанти і, звісно, значення ч-критериев, одержувані при цьому. Іноді при отриманні пакунки ч-критериев попередньо нормуються якимось способом.

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

На змістовному рівні дана МЗЛП полягає в необхідності прийняття такого компромісного рішення (плану випуску продукції) xkDx, яке забезпечить, по можливості, найбільшу сумарну виручку L1(x) отреализации виробленої продукції; найменший витрата ресурсів i-го виду Lpl (x) (і = 1; m); мінімальні податкові відрахування від прибутку LH (x) (чи загальної выручки).

Зазначені мети носять суперечливий характер, і фактично ми маємо МЗЛП з m+2 -мя ч-критериями (m — кількість видів споживаних ресурсів). ТДР обумовлена ресурсними обмеженнями і умовами неотрицательных переменных:

де aij — витрата ресурсу i-го виду для випуску 1 одиниці продукції j-го виду (j=1,n);

bi — запас ресурсу i-го вида;

і - залишок ресурсу i-го виду при плані випуску x = (xj)n. Ч-критерии однорідні, якщо вони можуть бути зведені до єдиної мері виміру. У ролі такий заходи можна взяти грошовий еквівалент. Тоді m+2 ч-критерия можуть бути з допомогою лінійної пакунки зведені до трем:

общаявыручка (крб.):

загальна економія ресурсів (крб.):

податкові відрахування (крб.):

де cj — виручка від реалізації 1 од. продукції j-го виду (ціна); si — вартість (ціна) 1 од. ресурсу 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×2 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.

25/2.

Метод пакунки (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.