Багатокритеріальна булева оптимізація. 
Задача про водопровідника з двома цільовими функціями

КУРСОВА РОБОТА

«Багатокритеріальна булева оптимізація. Задача про водопровідника з двома цільовими функціями»

Вступ

До класу задач багатокритеріальної оптимізації з булевими змінними відносяться такі задачі оптимізації з декількома цільовими функціями, в яких змінні можуть приймати тільки значення 0 або 1. При цьому на характер цільових функцій і обмежень в загальному випадку не накладаються ніякі додаткові умови. Більш точне визначення даного класу задач можна отримати на основі узагальнення математичної постановки задачі оптимізації з булевими змінними. Оскільки до задач цього класу зводиться багато інших задач багатокритеріальної оптимізації, зокрема, багатокритеріальне узагальнення задач оптимізації на графах і задач комбінаторної оптимізації.

1. Теоретична частина

1.1 Загальна характеристика задач багатокритеріальної оптимізації з булевими змінними

В загальному випадку під задачею багатокритеріальної оптимізації з булевими змінними мається на увазі така задача оптимізації, яка має декілька булевих функцій, а змінні можуть приймати тільки булеві значення. Оскільки розв’язання багатьох прикладних задач багатокритеріальної оптимізації за допомогою програми MS Excel припускає постановку цих задач у формі узагальненої моделі булевого програмування. Більш точне визначення класу задач багатокритеріальної оптимізації з булевими змінними можна отримати на основі конкретизації загальної математичної постановки задач багатокритеріальної оптимізації.

В загальному випадку математична постановка задачі багатокритеріальної оптимізації з булевими змінними може бути сформульована наступним чином:

або, (1)

де (2)

і. (3)

Математичну модель (1) — (3) називають також задачею багатокритеріального булевого програмування. Якщо додатково в дану математичну модель вводяться припущення про лінійний характер цільової функції і лівих частин обмежень, то відповідну задачу часто називають задачею багатокритеріального булевого лінійного програмування.

Властивості задач багатокритеріальної оптимізації з булевими змінними аналогічні загальним властивостям задач багатокритеріальної оптимізації. Метод поступок і метод мінімального відхилення від ідеальної точки являються базовими для розв’язання задач багатокритеріальної оптимізації з булевими змінними. В той час як графічний спосіб побудови множини Парето для даного класу задач не може бути використаний.

Задача водопровідника

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

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

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

1.2 Математична постановка задачі водопровідника

Для розробки математичної моделі індивідуальної задачі водопровідника з конкретною схемою розташування труб необхідно пронумерувати всі, які маємо плити від 1 до 16, а труби від 1 до 5.

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

Тоді математична постановка задачі водопровідника може бути записана наступним чином:

(1)

де множина допустимих альтернатив формується наступною системою обмежень нерівностей:

(2)

Помітимо, що кожній трубі відповідає одне обмеження, яке означає, що для отримання доступу до тої чи іншої труби необхідно підняти хоча б одну з плит, під якими проходить дана труба. Так, наприклад, для встановлення перекриття на першій трубі необхідно підняти плиту 1 або 2, або 3, або будь-яку їх комбінацію, яка відповідає першому обмеженню (2). Аналогічно інтерпретуються і наступні 4 із перших 5 обмежень даної математичної моделі (2). Цільова функція (1) відповідає вимогам мінімізації загальної кількості піднятих плит при виконанні даної роботи.

Вказівка

Може здатися, що дана задача може бути розв’язана методом простого вибору для кожної труби одна плита, яку необхідно підняти для установки на ній вентильного перекриття. В цьому випадку кількість плит буде дорівнювати кількості труб, прокладених під плитами. Для розглядуваної задачі це число дорівнює 5. Однак, ця кількість плит не є оптимальним розв’язком задачі.

Дана математична модель відноситься до класу булевих задач лінійного програмування, яка може бути розв’язана за допомогою програми MS Excel.

1.3 Аналітичний розв’язок задачі водопровідника

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

(2)

В рівнянні операції визначають операції булевого додавання і множення відповідно. Булеве рівняння (2) еквівалентне вимогам, щоб кожний вираз (в дужках) був рівним 1, тобто на кожній трубі повинно бути встановлено вентильне перекриття. При цьому потрібно мінімізувати загальну кількість змінних х_і, яка приймає значення 1, оскільки кожна рівність означає, що і-ту плиту потрібно підняти.

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

По-перше, замітимо, що при розкриванні дужок у виразі (2) ліва частина розглядуваного булевого рівняння буде представляти собою булеву суму добутків змінних виду:. Загальні кількість таких добутків змінних дорівнює .

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

Для мінімізації кількості цих змінних потрібно скористатися наступною тотожністю:. Очевидно, що цю тотожність можна застосувати тільки для тих добутків, які містять однакові змінні в різних дужках лівої частини рівняння (2). Таких змінних відносно небагато. Це змінна, яка входить у співмножники 1 і 2; змінна, яка входить у співмножники 1 і 3; змінна, яка входить у співмножники 2 і 4; змінна, яка входить у співмножники 3 і 4; змінна, яка входить у співмножники 2 і 5; змінна, яка входить у співмножники 4 і 5. При цьому відсутні змінні, які одночасно входили б в 3 і більшу кількість співмножників.

Таким чином, із всіх добутків виду, можна виключати із розглядання ті, які містять 5 різних змінних, які б входили в різні пари співмножників. В якості таких змінних можна взяти, наприклад, змінні і. Так само може бути отримано 4 оптимальні розв’язки, які основані на розв’язанні рівнянь:. Перший з цих оптимальних розв’язків:, ,, другий —, ,, , третій —, , і четвертий —, , .

Другу групу оптимальних розв’язків можна отримати, якщо замість шуканих змінних взяти змінні і. Даним способом можна отримати ще 5 оптимальних розв’язків, основаних на розв’язанні рівнянь:. Перший із оптимальних розв’язків другої групи:, ,, другий —, ,, третій —, , і т.д.

Аналогічним чином можна отримати оптимальні розв’язки третьої групи, якщо замість шуканих змінних взяти змінні і, четвертої групи, якщо заміть шуканих змінних взяти змінні і, і п’ятої групи, якщо замість шуканих змінних взяти змінні і .

Таким чином, задача водопровідника, яка розглядається, має декілька оптимальних рішень, кожне з яких потребує для установки вентильних перекриттів підняття 3-х плит. Програма MS Excel дозволяє знайти тільки один оптимальний розв’язок, в чому проявляється деяка обмеженість її можливостей.

1.4 Задача водопровідника з двома цільовими функціями

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

1.5 Математична постановка задачі водопровідника з двома цільовими функціями

Для розв’язання задачі водопровідника з двома цільовими функціями вводять дві додаткові характеристики, які зв’язані з часом і вартістю підняття плит при установці вентильних перекриттів. В цьому випадку для розробки математичної моделі задачі водопровідника з двома цільовими функціями маємо для кожної плити задати точне значення відповідних характеристик.

Припустимо, що час підйому кожної плити фіксований і дорівнює в хвилинах:, ,, ,, ,, ,, ,, ,, ,,. Вартість робіт після підйому кожної плити також фіксована і дорівнює в тис. грн.:, ,, ,, ,, ,, ,, ,, ,, .

Потребується визначити номера плит, які необхідно підняти для установки вентильних перекриттів, щоб загальні час і вартість виконання робіт були мінімальними.

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

Тоді математична постановка даної задачі водопровідника з двома цільовими функціями може бути записана наступним чином:

(4)

(5)

де множина допустимих альтернатив формується наступною системою обмежень нерівностей:

(6)

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

Математична модель (4) — (6) відноситься до класу задач багатокритеріального булевого програмування, яку можна розв’язати за допомогою методів поступок і мінімального відхилення від ідеальної точки. При цьому загальна схема даних методів залишається попередньою, змінюються лише особливості пошуку розв’язку відповідних задач оптимізації з однією цільовою функцією за допомогою програми MS Excel.

2. Практична частина

2.1 Розв’язання задачі водопровідника за допомогою програми MS Excel 2007

Для розв’язання задачі водопровідника за допомогою програми MS Excel створимо новий робочий лист. Далі виконуємо наступні дії:

1. Внесемо назви плит в комірки А2:А17.

2. В комірку С2 введемо формулу цільової функції (1).

3. В комірку С4 введемо формулу: =В2+В3+В4, яка виражає ліву частину першого обмеження.

4. В комірку С5 введемо формулу: =В3+В6+В7+В10, яка виражає ліву частину другого обмеження.

5. В комірку С6 введемо формулу: =В4+В8+В9+В13+В17, яка виражає ліву частину третього обмеження.

6. В комірку С7 введемо формулу: =В7+В8+В11+В12, яка виражає ліву частину четвертого обмеження.

7. В комірку С8 введемо формулу: =В10+В11+В15+В16, яка виражає ліву частину п’ятого обмеження.

Загальний вид робочого листа MS Excel 2007 з вихідними даними для розв’язання задачі водопровідника представлений на Рис. 1

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

1. Клацнути значок Кнопка Microsoft Office, а потім Параметры Excel.

2. Вибрати команду Надстройки, а потім у вікні Управление вибрати пункт Надстройки Excel.

3. Нажати кнопку Перейти.

4. У вікні Доступные надстройки встановити флажок Поиск решения и нажати кнопку ОК.

5. На вкладці Данные стає доступною команда Поиск решения.

Після появи діалогового вікна Поиск решения виконуємо наступні дії:

1. В полі Установить целевую ячейку встановлюємо значення $C$ 2.

2. Для групи Равной вибрати варіант пошуку розв’язку — минимальному значению.

3. В полі з назвою Изменяя ячейки вводимо $B$ 2:$B$ 17.

4. Добавити 5 перших обмежень. Виконуємо наступні дії:

— нажати кнопку з назвою Добавить у вихідному діалоговому вікні Поиск решения;

— у вікні, яке з’явилося, вибираємо діапазон комірок $C$ 4:$C$ 8, який повинен відобразитися в полі Ссылка на ячейку;

— із випадаючого списку вибираємо знак «>=»;

— в полі Ограничение набираємо 1, що відповідає правим частинам обмежень;

— для додавання цієї групи обмежень нажимаємо кнопку Добавить.

5. Додаємо обмеження на булеві значення змінних:

— вибираємо діапазон комірок $B$ 2:$B$ 17, який повинен відобразитися в полі Ссылка на ячейку;

— із випадаючого списку вибираємо «двоич»;

— в полі Ограничение оставляємо без змін встановлене програмою значення «двоичное», що відповідає правим частинам обмежень.

Виконане зображено на Рис. 2.

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

Результатом розв’язку даної задачі водопровідника є отримані оптимальні значення змінних: х₂=1, х₃=1, х₁₀=1, інші змінні рівні 0, яким відповідає значення цільової функції: .

Аналіз знайденого розв’язку показує, що при виконанні робіт по встановленню перекриття на водопровідні труби потрібно підняти 3 плити, а саме плити з номерами 2, 3 і 10. При цьому загальна кількість плит є мінімальною.

Особливості математичної моделі задачі водопровідника дозволяють знайти аналітичний її розв’язок, який може бути використаний для перевірки правильності розв’язання, знайденого за допомогою програми MS Excel 2007.

2.2 Розв’язання задачі водопровідника з двома цільовими функціями за допомогою програми MS Excel 2007 методом поступок

Розв’язання даної задачі багатокритеріальної оптимізації за допомогою програм MS Excel 2007 методом поступок буде складатися з двох етапів. На першому етапі необхідно розв’язати звичайну задачу оптимізації, використовуючи замість критеріальної функції першу цільову функцію (4), яка є важливішою, ніж друга цільова функція. Для розв’язання цієї задачі виконаємо наступні дії:

1. Внесемо назви змінних в комірки А2:А17. Назви обмежень, значення першої цільової функції, значення другої цільової функції відповідно у E1, F1, G1.

2. В комірки С2:С17 введемо значення коефіцієнтів першої цільової функції:, ,, ,, ,, ,, ,, ,, ,, .

3. В комірки D2:D17 введемо значення коефіцієнтів другої цільової функції:, ,, ,, ,, ,, ,, ,, ,, .

4. В комірку E2 введемо формулу: =B2:B4, які виражають ліву частину першого обмеження (6).

5. В комірку E3 введемо формулу: =B3+B6+B7+B10, які виражають ліву частину другого обмеження (6).

6. В комірку E4 введемо формулу: =B4+B8+B9+B13+B17, які виражають ліву частину третього обмеження (6).

7. В комірку E5 введемо формулу: =B7+B8+B11+B12, які виражають ліву частину четвертого обмеження (6).

8. В комірку E6 введемо формулу: =B10+B11+B15+B16, які виражають ліву частину п’ятого обмеження (6).

9. В комірку F2 введемо формулу: =СУММПРОИЗВ (B2:B17; С2:С17), яка представляю першу цільову функцію (4).

10. В комірку G2 введемо формулу: =СУММПРОИЗВ (B2:B17; D2:D17), яка представляю першу цільову функцію (5).

Загальний вигляд робочого листа MS Excel 2007 з вихідними даними для розв’язання задачі водопровідника з двома цільовими функціями методом поступок на першому етапі зображений на Рис. 4.

Для подальшого розв’язання задачі на першому етапі потрібно визвати майстра пошуку розв’язання «Поиск решения».

Після того, як з’явиться діалогове вікно «Поиск решения» потрібно виконати наступні дії:

1. В полі Установить целевую ячейку встановлюємо значення $F$ 2.

2. Для групи Равной вибрати варіант пошуку розв’язку — минимальному значению.

3. В полі з назвою Изменяя ячейки вводимо $B$ 2:$B$ 17.

4. Добавити 5 перших обмежень. Виконуємо наступні дії:

· нажати кнопку з назвою Добавить у вихідному діалоговому вікні Поиск решения;

· у вікні, яке з’явилося, вибираємо діапазон комірок $E$ 2:$E$ 6, який повинен відобразитися в полі Ссылка на ячейку;

· із випадаючого списку вибираємо знак «>=»;

· в полі Ограничение набираємо 1, що відповідає правим частинам обмежень;

· для додавання цієї групи обмежень нажимаємо кнопку Добавить.

5. Додаємо обмеження на булеві значення змінних:

· вибираємо діапазон комірок $B$ 2:$B$ 17, який повинен відобразитися в полі Ссылка на ячейку;

· із випадаючого списку вибираємо «двоич»;

· в полі Ограничение оставляємо без змін встановлене програмою значення «двоичное», що відповідає правим частинам обмежень.

6. В додатковому вікні Параметры поиска решения вибрати Линейная модель.

Загальний вид вікна майстра пошуку розв’язку на першому етапі з заданими параметрами представлений на Рис. 5.

Після того, як обмеження і цільова функція будуть задані можна розпочати пошук чисельного розв’язку, для цього нажимаємо кнопку Выполнить. Після виконання розрахунків програмою MS Excel 2007 ми отримаємо кількісний розв’язок, який представлений на Рис. 6.

Результатом розв’язку розглядуваної задачі водопровідника є знайдені оптимальні значення змінних: х₃=1, х₅=1, х₁₀=1, інші змінні рівні 0, яким відповідає значення цільової функції:. Аналіз знайденого розв’язку показує, що загальний час підняття плит складає 130 хв. При цьому вартість виконаних робіт при піднятті плит з номерами 3, 5 і 10 складає 11 тис. грн.

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

З цією метою слід розглянути додаткові обмеження наступного виду:

(7)

в якому права частина дорівнює значенню суми: +30, а знак обмеження обрано таким чином, щоб відповідати розв’язку задачі мінімізації при першій цільовій функції.

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

1. Скопіюємо формулу з комірки F2 в комірку Е8, яка представляє ліву частину додаткових обмежень (7).

2. В комірку F8 введемо значення 160, яке представляє праву частину додаткових обмежень (7).

3. Видалимо значення змінних із комірок B2:B17, отриманих в результаті розв’язання задачі на першому етапі.

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

1. В полі Установить целевую ячейку встановлюємо значення $G$ 2.

2. Для групи Равной вибрати варіант пошуку розв’язку — минимальному значению.

3. В полі з назвою Изменяя ячейки вводимо $B$ 2:$B$ 17.

4. Додаємо обмеження на булеві значення змінних:

· у вихідному діалоговому вікні Поиск решения нажати кнопку Добавить;

· вибираємо діапазон комірок $E$ 8, який повинен відобразитися в полі Ссылка на ячейку;

· із випадаючого списку вибираємо знак «<=»;

· в полі Ограничение вибрати комірку $F$ 8;

· нажати кнопку Ок.

5. В додатковому вікні Параметры поиска решения вибрати Линейная модель.

Після того як обмеження і цільова функція будуть задані на другому етапі можна приступити до пошуку остаточного розв’язку задачі водопровідника з двома цільовими функціями, для цього потрібно нажати кнопку Выполнить. Після виконання розрахунків програмою MS Excel 2007 отримані кількісні розв’язки, які зображені на Рис. 8.

Результатом розв’язку задачі водопровідника з двома цільовими функціями є знайдені оптимальні значення змінних: х₃=1, х₉=1, х₁₀=1, інші змінні рівні 0, яким відповідає значення цільових функцій:, .

Аналіз знайденого розв’язку показує, що загальний час підняття плит складає 160 хв. При цьому вартість виконаних робіт при піднятті плит з номерами 3, 9 і 10 складає 9,3 тис. грн.

2.3 Розв’язання задачі водопровідника з двома цільовими функціями за допомогою програми MS Excel 2007 методом мінімального відхилення

Для розв’язання задачі водопровідника з двома цільовими функціями за допомогою програми MS Excel 2007 методом мінімального відхилення від ідеальної точки будемо використовувати ті ж значення параметрів розглядуваної задачі водопровідника.

Розв’язання даної задачі багатокритеріальної оптимізації методом мінімального відхилення від ідеальної точки буде складатися з двох етапів. На першому етапі необхідно розв’язати дві звичайні задачі оптимізації, використовуючи в якості критеріальних функцій, відповідно, цільові функції (4) і (5).

Для розв’язання задачі виконаємо наступні дії, які аналогічні діям при розв’язання задачі водопровідника з двома цільовими функціями методом поступок:

1. Внесемо назви змінних в комірки А2:А17. Назви обмежень, значення першої цільової функції, значення другої цільової функції відповідно у E1, F1, G1.

2. В комірки С2:С17 введемо значення коефіцієнтів першої цільової функції:, ,, ,, ,, ,, ,, ,, ,, .

3. В комірки D2:D17 введемо значення коефіцієнтів другої цільової функції:, ,, ,, ,, ,, ,, ,, ,, .

4. В комірку E2 введемо формулу: =B2:B4, які виражають ліву частину першого обмеження (6).

5. В комірку E3 введемо формулу: =B3+B6+B7+B10, які виражають ліву частину другого обмеження (6).

6. В комірку E4 введемо формулу: =B4+B8+B9+B13+B17, які виражають ліву частину третього обмеження (6).

7. В комірку E5 введемо формулу: =B7+B8+B11+B12, які виражають ліву частину четвертого обмеження (6).

8. В комірку E6 введемо формулу: =B10+B11+B15+B16, які виражають ліву частину п’ятого обмеження (6).

9. В комірку F2 введемо формулу: =СУММПРОИЗВ (B2:B17; С2:С17), яка представляю першу цільову функцію (4).

10. В комірку G2 введемо формулу: =СУММПРОИЗВ (B2:B17; D2:D17), яка представляю першу цільову функцію (5).

Загальний вигляд робочого листа MS Excel 2007 з вихідними даними для розв’язання задачі водопровідника з двома цільовими функціями методом мінімального відхилення від ідеальної точки на першому етапі зображений на Рис. 9.

Для подальшого розв’язання задачі на першому етапі потрібно визвати майстра пошуку розв’язання «Поиск решения».

Після того, як з’явиться діалогове вікно «Поиск решения» потрібно виконати наступні дії:

1. В полі Установить целевую ячейку встановлюємо значення $F$ 2.

2. Для групи Равной вибрати варіант пошуку розв’язку — минимальному значению.

3. В полі з назвою Изменяя ячейки вводимо $B$ 2:$B$ 17.

4. Добавити 5 перших обмежень. Виконуємо наступні дії:

· нажати кнопку з назвою Добавить у вихідному діалоговому вікні Поиск решения;

· у вікні, яке з’явилося, вибираємо діапазон комірок $E$ 2:$E$ 6, який повинен відобразитися в полі Ссылка на ячейку;

· із випадаючого списку вибираємо знак «>=»;

· в полі Ограничение набираємо 1, що відповідає правим частинам обмежень;

· для додавання цієї групи обмежень нажимаємо кнопку Добавить.

5. Додаємо обмеження на булеві значення змінних:

· вибираємо діапазон комірок $B$ 2:$B$ 17, який повинен відобразитися в полі Ссылка на ячейку;

· із випадаючого списку вибираємо «двоич»;

· в полі Ограничение оставляємо без змін встановлене програмою значення «двоичное», що відповідає правим частинам обмежень.

6. В додатковому вікні Параметры поиска решения вибрати Линейная модель.

Загальний вид вікна майстра пошуку розв’язку на першому етапі з заданими параметрами представлений на Рис. 10.

Після того як обмеження і цільова функція будуть задані можна розпочати пошук чисельного розв’язку, для цього нажимаємо кнопку Выполнить. Після виконання розрахунків програмою MS Excel 2007 ми отримаємо кількісний розв’язок, який представлений на Рис. 11.

Результатом розв’язку розглядуваної задачі водопровідника значення цільової функції: .

Діалогове вікно завдання параметрів для майстра пошуку розв’язання задачі водопровідника по другій цільовій функції представлено на Рис. 12.

Після того як обмеження і друга цільова функція будуть задані можна розпочати пошук чисельного розв’язання по другому критерію, для цього слід видалити раніше знайдені значення змінних і нажати кнопку Выполнить. Після виконання розрахунків програмою MS Excel 2007 отримаємо відповідний кількісний розв’язок. Результатом розв’язку задачі водопровідника з однією цільовою функцією на першому етапі є знайдене значення другої цільової функції. Результат показаний на Рис. 13.

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

1. Введемо додатковий напис в комірку Н1.

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

3. В комірку G3 введемо знайдене на першому етапі оптимальне значення другої цільової функції .

4. В комірку H2 введемо формулу: =(F2-F3)^2+(G2-G3)^2, яка представляє мінімальне відхилення від знайденої ідеальної точки, отриманої в результаті розв’язання задачі на першому етапі.

Зовнішній вигляд робочого листа MS Excel 2007 з вихідними даними для розв’язання задачі водопровідника методом мінімального відхилення від ідеальної точки на другому етапі має наступний вигляд (Рис. 14):

Для подальшого отримання розв’язку задачі на другому етапі слід визвати майстра пошуку рішення «Поиск решения»:

1. В полі Установить целевую ячейку встановлюємо значення $Н$ 2.

2. Для групи Равной вибрати варіант пошуку розв’язку — минимальному значению.

3. В полі з назвою Изменяя ячейки вводимо $B$ 2:$B$ 17.

В додатковому вікні Параметры поиска решения слід обов’язково зняти позначку Линейная модель. Загальний вигляд майстра пошуку розв’язку з заданими параметрами представлений на Рис. 15.

Після того, як обмеження і цільова функція на другому етапі задані можні приступати до пошуку кінцевого розв’язку задачі водопровідника з двома цільовими функціями, для цього слід нажати кнопку Выполнить. Після виконання розрахунків програмою MS Excel 2007 буде отримано кількісний розв’язок, який зображений на Рис. 16.

Результатом розв’язку задачі водопровідника з двома цільовими функціями методом мінімального відхилення від ідеальної точки є знайдені оптимальні значення змінних: х₃=1, х₅=1, х₁₀=1, інші змінні рівні 0, яким відповідає значення цільових функцій:, .

Аналіз знайденого розв’язку показує, що загальний час підняття плит складає 130 хв. При цьому вартість виконаних робіт при піднятті плит з номерами 3, 5 і 10 складає 11 тис. грн.

2.4 Розв’язання задачі водопровідника з двома цільовими функціями за допомогою програми MS Excel 2007 методом адитивного згортку

Для розв’язання задачі водопровідника з двома цільовими функціями за допомогою програми MS Excel 2007 методом адаптивного згортка на основі задавання ваги окремих цільових функцій будемо використовувати ті ж значення параметрів розглядуваної раніше задачі водопровідника. Додатково слід задати кількісні значення вагів вихідних цільових функцій. Такі значення будуть і .

Для розв’язання задачі водопровідника з двома цільовими функціями методом адаптивного згортка на основі задавання вагів окремих цільових функцій внесемо такі зміни:

1. В комірку Н2 введемо формулу: =0.5*F2/195+0.5*G2/11, яка представляє адитивну згортку вихідних цільових функцій з використанням заданих раніше вагів критеріїв і шкалюванням критеріїв відносно максимальних значень цільових функцій.

Загальний вигляд робочого листа з вихідними даними для розв’язання задачі водопровідника методом адитивного згортку має наступний вигляд (Рис. 17):

Для подальшого розв’язання задачі слід визвати майстра пошуку рішення «Поиск решения». В діалоговому вікні Поиск решения слід задати цільову комірку, діапазон змінюваних комірок і обмеження задачі. В додатковому вікні «Параметры поиска решения» слід вибрати Линейная модель. Загальний вид вікна майстра пошуку з заданими параметрами зображений на Рис. 18.

Після того, як обмеження і цільова функція будуть задані на другому етапі можна приступити до пошуку розв’язку задачі водопровідника з двома цільовими функціями, для чого потрібно нажати кнопку Выполнить. Після виконання розрахунків програмою будуть отримані кількісні розв’язки (Рис. 19).

Результатом розв’язання задачі водопровідника з двома цільовими функціями методом адитивного згортку на основі задавання вагів окремих цільових функцій є знайдені оптимальні значення змінних: х₃=1, х₆=1, х₁₄=1, яким відповідають значення цільових функцій, .

Аналіз знайденого розв’язку вказує на те, що при виконанні робіт по установці перекриття на водопровідні труби слід підняти три плити, а саме плити з номерами 3, 6 і 14. При цьому буде досягнуто деякий компроміс відносно загального часу і вартості виконання робіт.

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

Висновок

В цій курсовій роботі була розглянута багатокритеріальна задача, а саме задача водопровідника з двома цільовими функціями. Були розглянуті три методи розв’язання: метод поступок, метод мінімального відхилення від ідеальної точки і метод адитивного згортку. Всі ці методи були розв’язані за допомогою програми MS Excel 2007. Аналіз знайдених розв’язків вказує на те, що при виконанні робіт по установці перекриття на водопровідні труби слід підняти три плити. При цьому буде досягнуто деякий компроміс відносно загального часу і вартості виконання робіт.

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

1. http://uk.wikipedia.org/

2. Леоненков А. В. Решение задач оптимизации в среде MS Excel. — Санкт Петербург: БХВ-Петербург, 2005. — 704 с.