На головну    

 Рішення багатокритеріальної задачі лінійного програмування - Економіко-математичне моделювання

Міністерство загальної та професійної освіти РФ

ТДТУ

Кафедра ІСКурсовая робота з дисципліни

Теорія оптимального управління ЕС

Виконав: студент групи ІСЕ-32 Ченців Д.Є.

 Прийняв: д.т.н. професор

Берзін Е.А.

Твер

2000 годСодержаніе Введення

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

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

1.2. Умову задачі

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

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

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

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

3.1. Видалення пасивних обмежень

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

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

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

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

5. Складання зведеної таблиці

Висновок

Список літератури

Введення

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

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

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

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

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

 (1)

де ei- невід'ємні змінні (нев'язки, i = 1; m).

 (3)

 (2)

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

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

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

 (4)

і хоча б одне з них - строго (зі знаком>).

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

1.2.Условіе завдання

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

L1 = -x1 + 2x2 + 2,

L2 = x1 + x2 + 4,

L3 = x1- 4x2 + 20,

і система обмежень:

x1 + x2 ? 15,

5x1 + x2? 1,

-x1 + x2 ? 5,

x2 ? 20,

"Xj? 0.

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

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

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

 (6)

 (5)

 (7)

Сенс задачі лінійного програмування неважко зрозуміти, якщо врахувати, що dr- це прирощення ч-критерію Lr, одержуване при зсуві рішення х, в точку х. Тоді, якщо після рішення ЗЛП виявиться Dmax = 0, то це буде означати, що жоден з ч-критеріїв не можна збільшити (Dmax = 0), якщо не допускати зменшення будь-якого з інших ("dr? 0). Але це і є умова p -оптимальне х ,. Якщо ж при вирішенні виявиться, що D ? 0, то значить якийсь ч-критерій збільшив своє значення без погіршення значень інших ("dr? 0), і значить х, I Dpx.

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

L1 = -x1 + 2x2 + 2,

L2 = x1 + x2 + 4,

L3 = x1- 4x2 + 20,

x1 + x2 ? 15,

5x1 + x2? 1,

-x1 + x2 ? 5,

x2 ? 20,

"Xj? 0.

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

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

d1 = x1- 2x2 + 1

Dxkd2 = x1 + x2- 8

d3 = -x1 + 4x2- 7

D = x1 + 3x2- 14,

e1 = 15 - x1- x2

e2 = 5x1 + x2- 1,

Dxe3 = 5 + x1- x2

e4 = 20 - x2

"Xj? 0.

і у формі з-таблиці:

 Т 1

 х 1

 х 1 лютого

 e 1 -1 -1 16

 e 2 5 січня -4

 e 3 січня -1100

e4 0 -1 10

 d 1 січня -2 -4

 d 2 Будiвництво 1 1 -12

 d 3 -1 1 -8

 D 1 квітня -24

Застосовуючи з-метод, після заміни d3 «х2, отримуємо:

 Т 2

 х 1

 d 1 січня

 e 1 -3/2 ? 29/2

 e 2 11/2 -1/2 -1/2

 e 3 1/2 ? 9/2

 e 4 -1/2 ? 39/2

 X 2 1/2 -1/2 1/2

 d 2 3/2 -1/2 -15/2

 d 3 січня -2 -5

 D 5/2 -3/2 -25/2

Бачимо, що опорний план не отримано, отже робимо ще одну заміну: e1 «х1:

 Т 3

 e 3

 d 1 січня

 x 1 29/3

 e 2 316/6

 e 3 56/6

 e 4 88/6

 x 2 16/3

 d 2 липня

 d 3 14/3

 D -5/3 -2/3 70/6

У Т3получен опорний план. Так як при цьому D> 0, то, отже, система ч-критеріїв немає суперечлива і існує деяка область, зміщення в яку рішення х, здатне збільшити, принаймні, один ч-критерій без зменшення значень інших. Ця область і є конус домінування - д - конусом Dxk (на малюнку виділено штрихуванням). При R> n д-конус може виродитися в точку х, (вершина д-конуса). Отримано ціле безліч оптимальних рішень, що витягають із Т3: х0 = (29/3; 16/3). Таким чином, рішення х, = (5; 3) не є p-оптимальним, оскільки його вдалося поліпшити (Dmax> 0). Крім встановлення факту неефективності рішення х ,, розглянутий метод дозволив визначити найближче до нього p-оптимальне рішення.

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

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

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

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

L1 = x1- 2x2 + 2,

L2 = x1 + x2 + 4,

L3 = -x1 + 4x2- 20,

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

d1 = x1- 2x2 + 1, (5 - 2 * 3 + 1 = 1)

Dxkd2 = x1 + x2- 8, (5 + 3 + 4 = 12)

d3 = -x1 + 4x2- 7, (-5 + 4 * 3 - 20 = -13)

D = 2x1 + 4x2- 14,

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

1) d1 = x1- 2x2 + 1,

-x1 + 2x2 ? 1 (1; 1)

2) d2 = x1 + x2- 8,

x1 + x2? 8 (0; 8)

3) d3 = -x1 + 4x2- 7,

-x1 + 4x2? 7 (1, 2)

За отриманими точкам будуємо графік (малюнок 1). На малюнку штрихуванням показаний отриманий д-конус. Перехід до будь-якій точці всередині конуса забезпечує збільшення всіх критеріїв. Точка (29/3; 16/3) є p-оптимальним рішенням. Зміщуючи точку х, всередину д-конуса прийдемо на кордон e1. При цьому д-конус вийде з області допустимих рішень (ОДР) Dx. Тепер отримана точка не зможе поліпшити жоден ч-критерій без погіршення інших, значить вона p-оптимальна. Побудувавши д-конус в будь-якій точці боку e1, переконуємося, що кожна з точок p-оптимальна, значить вся сторона e1составляет p-безліч.

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

с-методом

3.1.Удаленіе пасивних обмежень

Перед побудовою p-безлічі з системи обмежень повинні бути видалені пасивні обмеження. Пасивним будемо називати нерівність (п-нерівність), межа якого не є частиною кордонів області Dx, за винятком, можливо, її окремої точки. Нерівності, що утворюють кордону Dx, назвемо активними (а-нерівності).

Щоб грані не були включені в Dxp, не маючи ніякого відношення до Dxp, нерівність e1должно бути видалено з вихідної системи обмежень. Умовою для виключення нерівності ei? 0 з системи є несумісними (або вирожденність) даної системи нерівностей за умови ei = 0. Геометрично це означає, що кордон ei = 0 нерівності ei? 0 не перетинається з областю Dxілі має одну спільну точку. Якщо межа ei = 0 має загальну кутову точку з Dx (вирожденність), то з видаленням п-нерівності ei? 0 ця крапка не буде загублена, так як вона входить в межі інших нерівностей. Крім заданих m нерівностей перевірці підлягають і n умов невід'ємності змінних, так як координатні площини (осі) також можуть входити до кордону Dx.

В якості примітки можна відзначити, що оскільки п-нерівності (пасивні нерівності) для будь-якої точки x I Dxбудут виконані, то у міру виявлення п-нерівностей і введення їх в базис вони видаляються з с-таблиці.

Запишемо систему нерівностей Dxв формі з-таблиці:

 Т 1

 х 1

 х 1 лютого

 b i / a is

 b i / a is

 e 1 -1 -1 15 15 15

 e 2 5 1 -1 1/5 1

 e 3 січня -1 5 - 5

 e 4 0 -1 20 - 20

 Т 2

 e 1

 x 1 лютого

 Т 2 '

 x 1

 e 1 лютого

 х 1 -1 -1 15

 e 1 квітня -1 14

 e 2 -5 -4 74

 x 2 -5 1 січня

 e 3 -1 -2 20

 e 2 березня -1 4

 e 4 0 -1 20

 e 1 квітня -1 19

ОП - отриманий, отже ОП - отриманий, отже

х2і e1- активні обмеження; x1і e2- активні обмеження;

з Т2получаем:

 Т 3

 e 1

 e 3 січня

 x 1 січня 1/2 5

 e 2 -3 2 34

 x 2 -1/2 -1/2 10

 e 2 квітня ? 10

звідси робимо висновок, що e3- активне обмеження;

з Т3получаем:

 Т 4

 e 4

 e 3 січня

 x 10 Січня

 e 19 лютого

 x 2 15/2

 e 1 -5

Опорний план не отримано, отже e4- пасивне обмеження.

3.2.Определеніе p-множини з-методом.

При підготовці рішення для ЛПР інтерес буде представляти інформація про все безлічі p-оптимальних (ефективних) рішень Dxp. Графічний метод дозволяє сформулювати досить простий підхід до визначення безлічі Dxp. Суть цього підходу в наступному. Вирішуючи усічену задачу лінійного програмування, встановлюємо факт існування д-конуса (Dmax> 0). Оскільки для лінійних ЦФ конфігурація д-конуса не залежить від положення його вершини х ,, то, поміщаючи її на межу eiобласті Dx, вирішуємо усічену ЗЛП з додаванням ei, відповідного i-й ділянці кордонів Dx. Виродження д-конуса в точку х, буде ознакою p-оптимальності і всіх інших точок даної грані. За допомогою з-методу зазначена процедура легко проробляється для простору будь-якої розмірності n. Незручність зазначеного методу полягає в тому, що потрібно на кожній грані ОДР Dxнайті точку х, (по числу граней Dx) сформулювати і вирішити стільки ж ЗЛП розміру Rxn.

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

Наведені до точки х, = (1) nпріращенія d-rи невязки eiзапішутся у вигляді:

 (8)

де межа зверху у d, e і D означає, що ці величини приведені до точки х, = (1) n.

По суті, (8) - ЗЛП розміру (R + m) xn (D®max), а її рішення дозволить знайти всі грані, складові p-безліч Dxp.

Складаємо з-таблицю, не враховуючи пасивні обмеження, т.е e1:

 Т 1

 х 1

 х 1 лютого

 e 2 -1 -1 2

 e 3 5 1 -6

 e 1 квітня -1 0

 х 1 1 0 -1

 х 2 0 1 -1

 d 1 січня -2 1

 d 2 Будiвництво 1 1 -2

 d 3 -1 4 -3

 D 3 січня -4

На початку вирішується усічена ЗЛП (під рискою):

 Т 2

 х 1

 d 1 січня

 e 1 -3/2 1/2 3/2

 e 2 11/2 -1/2 -11/2

 e 3 1/2 1/2 -1/2

 х 1 1 0 -1

 х 2 1/2 -1/2 -1/2

 x 2 1/2 -1/2 1/2

 d 2 3/2 -1/2 -3/2

 d 3 січня -2 -1

 D 5/2 -3/2 -5/2

 Т 3

 d 3

 d 1 січня

 e 1 -3/2 -5/2 0

 e 2 11/2 21/2 0

 e 3 1/2 3/2 0

 x 1 1 2 0

 х 2 1/2 1/2 0

 x 2 1/2 1/2 1

 d 2 3/2 5/2 0

 x 1 січня 2 січня

 D 5/2 7/2 0

 Т 4

 e 1

 d 1 січня

 d 3 0

 x 1 лютого

 d 2 0

 x 1 січня

 D -5/3 -2/3 0

e1I Dxp, так як Dmax = 0.

Даний метод побудови безлічі Dxpобладает недоліком, пов'язаним з руйнуванням області допустимих рішень (ОДР) Dxпрі перенесення її граней в х ,. Дійсно, вершини області Dxв перетвореної моделі ніяк не відображені, а саме одна з них може скласти p-безліч у разі його збігу з оптимальним рішенням. Такий збіг можливо, якщо все ч-критерії досягають максимум на одній вершині. Фізично це означає, що вони слабопротіворечіви - кут при вершині д-конуса наближається до 180 ° (градієнти ч-критеріїв мають практично збігаються напрямку). Даний випадок має місце, якщо в p-безліч не ввійшла жодна з граней ОДР Dx. Отже, p-безліч збігається з оптимальним рішенням. Для визначення p-множини вирішується звичайна ЗЛП з одним з ч-критеріїв. Якщо при цьому отримано безліч оптимальних рішень, то вирішується ЗЛП з іншим ч-критерієм. Перетин оптимальних рішень і є p-множиною. Для ЛПР вказівка ??на те, що деяка грань ei = eipI Dxpp-оптимальна, є тільки узагальненою інформацією.

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

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

При будь-якому довільному рішенні х I Dxкаждий з ч-критеріїв прийме певне значення і серед них знайдеться, принаймні, один, значення якого буде найменшим:

 (9)

Метод гарантованого результату (ГР) дозволяє знайти таке (гарантоване) рішення, при якому значення «найменшого» критерію стане максимальним. Таким чином, цільова функція (ЦФ) є деякою сверткой ч-критеріїв (9), а МЗЛП зводиться до задачі КВП (кусочно-опуклого програмування) при ОДР Dx, заданої лінійними обмеженнями.

Вихідні умови записуємо в канонічному вигляді:

d1 = х1- 2х2- j + 2,

d2 = х1 + Х2 j + 4,

d3 = -х1 + 4х2- j + 20,

e1 = -х1- х2 + 15,

e2 = 5х1 + Х2 1,

e3 = x1- х2 + 5,

потім у вигляді з-таблиці:

 Т 1

 х 1

 х 2 j 1

 e 1 -1 -1 0 15

 e 2 5 1 0 -1

 e 3 1 -1 0 5

 d 1 1 -2 -1 2

 d 2 Будiвництво 1 1 -1 4

 d 3 -1 4 -1 20

Вводячи в базис змінну j (d1 «j), отримуємо звичайну ЗЛП при максимізації ЦФ j.

 Т 2

 х 1

 х 2

 d 1 січня

 e 1 -1 -1 0 15

 e 2 5 1 0 -1

 e 3 1 -1 0 5

 j 1 -2 -1 2

 d 2 0 3 2 січень

 d 3 -2 6 1 18

 Т 3

 d 3

 x 2

 d 1 січня

 b i / a is

 e 1 1/2 -4 -1/2 6 6/4

 e 2 -5/2 16 5/2 44 -

 e 3 -1/2 2 2 14 -

 j -1/2 1 -1/2 11 -

 d 2 0 3 -1 2 -

 х 1 -1/2 3 1/2 9 -

 Т 4

 d 3

 e 1

 d 1 січня

 x 2 3/2

 e 2 68

 e 17 березня

 j -3/8 -1/4 -5/8 25/2

 d 2 13/2

 х 1 27/2

Рішення ЗЛП призводить до кінцевої з-таблиці Т4. Видно, що отримане гарантоване вирішення х p-оптимально, оскільки введення в базис будь-якої вільної змінної (тобто її збільшення) призведе до зниження j - нижнього рівня ч-критеріїв ("сj <0). З таблиці також видно, що рішення х0 = (27/2; 3/2) знаходиться на межі e4, при цьому значення ч-критеріїв рівні (знаходимо за формулою Lr (xr) = j + dr):

L1 = L3 = j = 25/2

L2 = j + d2 = 25/2 + 13/2 = 19

LS = 88/2 = 44

x ° = (27/2; 3/2)

Якби в рядку j були нулі, то це означало б, що одну з відповідних змінних можна ввести в базис (збільшити без зниження рівня j). Це могло б призвести і до збільшення приросту drдля деякого ч-критерію, що знаходиться в базисі.

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

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

 (9)

де

 (10)

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

 (11)

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

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

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

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

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

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

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

загальна виручка (грн.):

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

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

де cj- виручка від реалізації 1 од. продукції j-го виду (ціна); si- вартість (ціна) 1 од. ресурсу i-го виду (i = 1; m); Пj- прибуток від реалізації 1 од. продукції j-го виду (j = 1; n); aj- частка (відсоток податкових відрахувань від прибутку (виручки).

На закінчення зазначимо, що коефіцієнти mrне обов'язково повинні задовольняти умові (10), але обов'язково повинні бути позитивними, якщо все ч-критерії максимізуються.

Перейдемо до рішення:

 Т 1

 х 1

 х 1 лютого

 e 1 -1 -1 15

 e 2 5 січня -1

 e 3 січня -1 5

 L 1 січня -2 2

 L 1 лютого 4 січня

 L 3 -1 20 квітня

 L S 1 26 березня

 Т 2

 e 1

 x 1 лютого

 x 1 -1 -1 15

 e 2 -5 -4 74

 e 3 -1 -2 20

 L 1 -1 -1 17

 L 2 -1 0 19

 L 3 січня 5 травня

 L S -1 2 41

L1max = 17

L2 max = 19

L3 = 5

LS = 41

 Т 3

 e 1

 L 1 січня

 x 1 28/3

 e 2 154/3

 e 3 26/3

 x 2 17/3

 L 19 лютого

 L 3 -2/3 -5/3 100/3

 L S -5/3 -2/3 157/3

5. Складання зведеної таблиці.

Остаточне рішення зводиться в таблицю, де записуються альтернативні варіанти:

 Метод

 х 0

 L 1

 L 2

 L 3

 L S

 Метод гарантованого результату (27/2; 3/2) 25/2 19 25/2 44

 Метод згортки (28/3; 17/3) 0 19 33 1/3

 52 1/3

 Оптимізація L 1 (15; 0)

 17

 19 травня 41

 Оптимізація

 L 2, L 3 (28/3; 17/3) 0 19

 33 1/3 52 1/3

 xID x p (5; 3) 1 12 -13 0

© 8ref.com - українські реферати