Лінійна оптимізацій на задача

Розглянемо три типи лінійних оптимізаційних задач, які розв‘язуються з використанням засобів Пошук рішення:

- планування виробництва;

- складання сплавів чи суміші;

- планування штатного розпису.

Задача про знаходження оптимального виробництва фарб.

Невелика фабрика випускає два типи фарб: для внутрішніх (І) і зовнішніх робіт (Е). Продукція обох видів надходить для оптового продажу. Для виробництва фарб використовуються два вихідних продукти — А і В. Максимально можливі добові запаси цих продуктів складають 6 т і 8 т відповідно. Витрати А и В на 1 т відповідних фарб приведені в табл. 5.1.

Таблиця 5.1 – Вихідні дані задачі про виробництво фарб

Вихідний продуктВитрати вихідних продуктів (т) на тону фарбиМаксимально можливий запас, т

Фарба ЕФарба І

А126

В218

Вивчення ринку збуту показало, що добовий попит на фарбу І ніколи не перевищує попиту на фарбу Е більш ніж на 1 т. Крім того, встановлено, що попит на фарбу І ніколи не перевищує 2 т у добу.

Оптові ціни однієї тонни фарб рівні: 3000 грн для фарби Е и 2000 грн для фарби I.

Яку кількість фарби кожного виду повинна виготовляти фабрика, щоб прибуток від реалізації продукції був максимальним?

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

У нашому випадку фабриці необхідно спланувати обсяг виробництва фарб так, щоб максимізувати прибуток. Нехай хІ — добовий обсяг виробництва фарби І; хЕ — добовий обсяг виробництва фарби Е. Тоді сумарний добовий прибуток від виробництва хІ фарби І й і хЕ фарби Е дорівнює

Z = 3000 хЕ + 2000 хІ.

Метою фабрики є визначення серед усіх допустимих значень хІ і хЕ таких, котрі максимізують сумарний прибуток, тобто цільову функцію Z.

Оскільки об‘єм виробництва фарб не може бути від‘ємним, то обмеження, що накладаються на хІ і хЕ можна задати наступним чином:

хІ, хЕ≥0

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

хЕ+2 хІ ≤6

2хЕ+ хІ ≤8

Крім того, обмеження на величину попиту на фарби мають вигляд:

хІ- хЕ ≤1,

хІ ≤2.

Таким чином, математична модель даної задачі має наступний вид. Максимізувати:

Z = 3000 хЕ + 2000 хІ.

при обмеженнях:

хЕ+2 хІ ≤6

2хЕ+ хІ ≤8

хІ- хЕ ≤1,

хІ ≤2.

хІ, хЕ≥0

Побудована нами модель є лінійною, тому що цільова функція й обмеження лінійно залежать від змінних.

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

1. Відведіть чарунки А3 та В3 під значення змінних хЕ і хІ відповідно (рис. 5.1).

2. Введіть в чарунку С4 цільову функцію

=3000*АЗ+2000*ВЗ

3. Введіть в чарунки діапазону А7:А10 ліві частини обмежень, а в чарунки діапазону В7:В10 відповідні праві частини обмежень

Рис. 5.1 - Діапазони, відведені під змінні, цільову функцію і змінні в задачі про виробництво фарб

Переходимо до знаходження оптимального виробництва фарб.

1. Виберіть команду Сервіс│Пошук рішення. На екрані відобразиться діалогове вікно Пошук рішення (рис. 5.2). Вікно Пошук рішення має елементи, перераховані в табл. 5.2.

Рис. 5.2 - Вікно „Пошук рішення” після заповнення обмежень для задачі оптимального виробництва фарб

Таблиця 5.2 - Елементи вікна „Пошук рішення”

елементопис

Поле Встановити цільову чарункуПриводиться посилання на чарунку функцією, максимум чи мінімум значенням якої Пошук рішення буде шукати, змінюючи значення параметрів так, щоб вони задовольняли накладені на них обмеження.У нашому випадку з задачею про фарби в поле Встановити цільову чарунку вводимо С4

Група РівноїТип взаємозв'язку між рішенням і цільовою чарункою встановлюється шляхом вибору перемикача в групі Рівної. Для відшукання максимального значення цільової функції вибирається перемикач максимальному значенню, мінімального — перемикач мінімальному значенню. Якщо відшукуються значення змінних, для яких значення функції з цільової чарунки дорівнює встановленому в полі групи Рівної значенню, то вибирається перемикач значенню.В нашому випадку: для задачі про фарби виберіть перемикач максимальному значенню, тому що знаходимо план виробництва фарб із максимальними доходами

Поле Змінюючи чарункиПриводиться посилання на діапазон чарунок чи групу діапазонів чарунок, відведених під невідомі. Значення в цих чарунках повинні змінюватися в процесі пошуку рішення задачі, так щоб знайти рішення, що задовольняє заданим обмеженням.У нашому випадку введемо в поле Змінюючи чарунки діапазон АЗ:ВЗСписок ОбмеженняДопускаються обмеження у виді рівностей, нерівностей, вимог того, що невідомі можуть приймати тільки цілі значення, або тільки значення 0 чи 1.Обмеження додаються по одному за раз і відображаються у вікні Додавання обмеження, що викликається натисканням кнопки Додати (рис. 5.3).• У поле Посилання на чарунку введіть ліву частину обмежень — A3:ВЗ, у поле Обмеження — праву частину, у нашому випадку — 0. Список, що розкривається, дозволяє задати тип співвідношення між лівою і правою частинами обмеження. У нашому випадку виберіть співвідношення >=. Таким чином, вимога невід‘ємності змінних задана.• Натисніть кнопку Додати і за допомогою вікна Додавання обмеження введіть другу групу обмежень, що накладаються на змінні А7: А10 <= В7: В10.• Натисніть кнопку ОК для завершення введення обмежень. На екрані знову відобразиться вікно Пошук рішення, але тепер уже заповнене

Рис. 5.3 - Вікно „Додавання обмеження”

2. Натисніть кнопку Параметри. На екрані відобразиться діалогове вікно Параметри пошуку рішення (рис. 5.4). У діалоговому вікні Параметри пошуку рішення можна змінювати умови і варіанти пошуку рішення досліджуваної задачі, а також завантажувати і зберігати оптимізовувані моделі. Значення і стани елементів управління, використовувані за замовчуванням, підходять для рішення більшості задач. Опишемо елементи цього вікна (табл. 5.3).

Рис. 5.4 - Вікно Параметри пошуку рішення

Таблиця 5.3 - Елементи вікна „Параметри пошуку рішення”

ЕлементОпис

Поле Максимальний часСлужить для обмеження часу, що відпускається на пошук рішення задачі

Поле Граничне число ітераційСлужить для обмеження числа проміжних обчислень

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

Прапорець Лінійна модельСлужить для пошуку рішення лінійної задачі чи оптимізації лінійної апроксимації нелінійної задачі. У випадку нелінійної задачі цей прапорець повинний бути скинутий. Для лінійної задачі — установлений, тому що в противному випадку можливе одержання невірного результату

Прапорець Показувати результати ітераційСлужить для припинення пошуку рішення і огляду результатів окремих ітерацій

Прапорець Невід‘ємні значення Дозволяє установити нульову нижню границю для тих впливових чарунок, для яких вона не була вказана в полі Обмеження діалогового вікна Додати обмеження

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

Група ОцінкиСлужить для вибору методу екстраполяції

Група РізниціСлужить для вибору методу чисельного диференціювання

Група Метод пошукуСлужить для вибору алгоритму оптимізації

У нашому конкретному випадку встановіть прапорець Лінійна модель, а інші значення, що використовуються за замовчуванням, можна залишити так, як вони і є. Натисніть кнопку ОК. На екрані знову відобразиться вікно Пошук рішення.

3. Натисніть кнопку Виконати. На екрані відобразиться вікно Результати пошуку рішення (рис. 5.5).

Рис 5.5 – Вікно „Результати пошуку рішення”

4. Після натискання кнопки ОК, результати будуть внесені в робочий лист (рис. 5.6).

Рис. 5.6 - Оптимальне рішення

Використовуючи Пошук рішення знайдено оптимальний план виробництва фарб, що дає максимальний прибуток. З рис. 5.6 видно, що оптимальним є виробництво в добу 3,333 т фарби Е и 1,333 т фарби І. Цей обсяг виробництва принесе 12,667 тис грн прибутку.

Задача про оптимальний склад сплаву

Для одержання сплавів А і В використовуються чотири метали I, II, III і IV. Вимоги до складу металів у сплавах А і В приведені в табл. 5.4.

Таблиця 5.4 - Вимоги до складу металів

сплаввимоги до складу матеріалусплаввимоги до складу матеріалу

АНе більше 70% металу ІВВід 50 до 80 % металу ІІ

Не більше 30% металу ІІНе менше 20% металу ІІІ

Не більше 50 % матеріалу ІV

Характеристики і запаси руд, з яких отримують метали I, II, III і IV, зазначені в табл. 5.5.

Таблиця 5.5 - Характеристики і запаси руд

РудаМаксимальний запас, тСклад, %Ціна, $/т

ІІІІІІIVІнші компоненти

12000201030301035

24000103020301050

3100010501020030

Нехай ціна 1 т сплаву А дорівнює $220, а 1 т сплаву в — $250. Необхідно максимізувати прибуток від продажу сплавів А и В.

Позначимо х1А, х2А, х3А, х4А (х1В, х2В, х3В, х4В) кількість I, II, III і IV металів, що використовуються для одержання сплаву А (В), а уі, де іÎ[1; 3] — кількість використаної і- ї руди.

Тоді математична модель даної задачі має вид:Максимізувати:

Z=220(х1А+х2А+х3А+х4А)+250(х1В+х2В+ х3В+х4В)-35yl-50y2 -30у3

при обмеженнях:

- на склад сплавів:

х1А≤0,7(х1А+х2А+х3А+х4А),

х2А≤0,3(х1А+х2А+х3А+х4А),

х2В ≥0,5(х1В+х2В+ х3В+х4В),

х2В≤0,8 (х1В+х2В+ х3В+х4В),

х3В≥0,2 (х1В+х2В+ х3В+х4В),

х4В≤ 0,5(х1В+х2В+ х3В+х4В).

- на характеристики та склад руд:

х1А+ х1В ≤0,2 у1+0,1 у2+ 0,1у3,

х2А+ х2В ≤0,1 у1+0,3 у2+ 0,5у3,

х3А+ х3В ≤0,3 у1+0,2 у2+ 0,1у3,

х4А+ х4В ≤0,3 у1+0,3 у2+ 0,2у3,

- на діапазони використання змінних:

хіА≥0, хіВ≥0, іÎ[1; 4]

0 ≤ у1≤2000

0 ≤ у2≤4000

0 ≤ у3≤1000

Перейдемо до рішення задачі про сплави. Спочатку треба ввести вихідні дані в чарунки робочого листа.

1. Відведіть під змінні хіА, хіВ, іÎ[1; 4] діапазон чарунок СЗ:D6, а під змінні уі, іÎ[1; 3] — F3:F5.

2. Введіть:

• у діапазон чарунок G3: G5 — наявні запаси руд;

• у діапазон чарунок Н3:Н5 — ціни за одну тонну руди;

• у діапазон чарунок І3: M5 — характеристики складу руд.

3. В чарунку G9 введіть цільову функцію, яка у даному випадку є функцією масиву. Тому не забудьте завершити її введення натисканням комбінації клавіш ++.

{=220*СУМ (СЗ : Сб) +250*СУМ (D3 : D6) -СУМ (НЗ : H5*F3 : F5 )}

4. В чарунки діапазону С8:С17 введіть ліві частини обмежень, а в D 8: D 17 — праві частини в такий спосіб:

чарункаформулачарункаформула

С8=C3D8=0,7*СУММ(C3:C6)

C9=C4D9=0,3*СУММ(C3:C6)

C10=D4D10=0,5*СУММ(D3:D6)

C11=D4D11=0,8*СУММ(D3:D6)

C12=D5D12=0,2*СУММ(D3:D6)

C13=D6D13=0,5*СУММ(D3:D6)

C14=СУММ(C3:D3)D14=СУММ(F3:F5*I3:I5)

C15=СУММ(C4:D4)D15=СУММ(F3:F5*J3:J5)

C16=СУММ(C5:D5)D16=СУММ(F3:F5*K3:K5)

C17=СУММ(C3:C6)D17=СУММ(F3:F5*L3:L5)

Примітка

Чотири останні формули — це формули масивів. Тому не забудьте завершити введення кожної з них натисканням комбінації клавіш ++ +.

Перейдемо до безпосереднього рішення задачі за допомогою засобу Пошук рішення. Для цього:

1. Виберіть команду Сервіс | Пошук рішення. На екрані відобразиться діалогове вікно Пошук рішення.

2. Заповните діалогове вікно Пошук рішення, як показано на рис. 5.7.

3. Натисніть кнопку Виконати. На рис. 5.8 показані результати роботи засобу Пошук рішення.

Рис. 5.7 – Вихідні дані та заповнене діалогове вікно „Пошук рішення”

Рис.5.8 – Результат розв‘язання задачі засобами „Пошуку рішення”

Задача про оптимальне планування штатного розпису

Розглянемо задачу оптимального планування штатів. Авіакомпанії "Перманентний рейс" потрібно визначити, скільки стюардес варто прийняти на роботу протягом шести місяців за умови, що кожна з них, перш ніж приступить до самостійного виконання обов'язків стюардеси, повинна пройти попередню підготовку. Потреби в кількості (с.-год.) літного часу відомі і приведені в табл. 5.6.

Таблиця 5.6 - Потреби в стюардесо-годинах у задачі про оптимальне планування штатного розкладу

МісяцьПотреба, с.-год.МісяцьПотреба, с.-год.

Січень8000Квітень10000

Лютий9000Травень90000

Березень8000Червень12000

Підготовка стюардеси до виконання своїх обов'язків на регулярних авіалініях займає один місяць. Отже, прийом на роботу повинний, принаймні, на місяць випереджати "початок виконання обов‘язків на борту". Крім того, кожна стюардеса-учениця повинна протягом місяця, відведеного на її підготовку, пройти 100-годинну практику безпосередньо під час польотів. Таким чином, за рахунок кожної стюардеси-учениці протягом місяця звільняється 100 ч робочого часу, відведеного для вже кваліфікованих стюардес.

Кожна цілком кваліфікованих стюардеса протягом місяця може мати наліт до 150 ч. Авіакомпанія на початку січня вже має 60 досвідчених стюардес. При цьому ні одну з них не знімають з роботи. Встановлено також, що приблизно 10% кваліфікованих стюардес звільняються за власним бажанням за сімейними чи іншими обставинами.

Досвідчена стюардеса обходиться авіакомпанії в $800, а стюардеса-учениця — у $400 на місяць. Необхідно спланувати штат авіакомпанії, мінімізуючи витрати за шість звітних місяців.

Для даної задачі також можна представити математичну модель, але її зручніше проаналізувати в більш розгорнутій формі. А саме:

1. Відведіть діапазон чарунок В3:В8 під число нових стюардес, прийнятих на роботу із січня по червень (мал. 5.9).

2. В чарунку В2 введемо число працюючих стюардес у грудні.

3. В чарунках діапазону D3:D8 будемо обчислювати число постійно працюючих стюардес у поточному місяці. Для цього

• в чарунку D3 введіть формулу

=В2

• в чарунку D4 введіть формулу

= D3+0.9*ВЗ

• виберіть чарунку D4, розташуєте покажчик миші на її маркері заповнення і простягніть його вниз на діапазон D5:D8. Тепер, в чарунках діапазону D3:D8 будемо обчислювати число постійно працюючих стюардес у поточному місяці.Рис. 5.9 - Вихідні дані задачі про штатний розклад і заповнене діалогове вікно Пошук рішення

4. В чарунках діапазону ЕЗ:Е8 обчислимо наліт по місяцях. Для цього

• ведіть в чарунку ЕЗ формулу

=D3*$G$12+B3*$F$12

де в чарунках F12 і G12 введений припустимий наліт стюардеси-учениці і працюючої стюардеси.

• виберіть чарунку ЕЗ, розташуєте покажчик миші на її маркері заповнення і простягніть його вниз на діапазон Е4:Е8. Тепер, в чарунках діапазону ЕЗ:Е8 будемо обчислювати наліт по місяцях.

5. В чарунках діапазону F3:F8 обчислимо витрати по місяцях. Для цього

• введіть в чарунку F3 формулу

=D3*$E$12+B3*$D$12

де в ачрунках D12 і Е12 введена зарплата стюардеси-учениці і працюючої стюардеси.

• виберіть чарунку F3, розташуєте покажчик миші на її маркері заповнення, і простягніть його на діапазон F4: F8.

6. Залишилося обчислити сумарні витрати за планований період. Для цього в чарунку F9 введіть формулу

=CУMM(F3:F8)

Переходимо до рішення задачі про складання штатного розкладу за допомогою засобу Підбор параметра.

1. Виберіть команду Сервіс | Пошук рішення.

2. На екрані відобразиться діалогове вікно Пошук рішення. Заповните діалогове вікно Пошук рішення, як показано на рис. 5.9.

Результати розрахунку оптимального штату стюардес приведені на рис. 5.10.

Рис. 5.10 - Знайдене рішення задачі про штатний розклад

Цікавою особливістю цього рішення є те, що фірма в останній місяць планового періоду бере на навчання 17 нових стюардес. Припустимо, що авіакомпанія не так упевнена в майбутніх перспективах і вирішила в червні не брати на навчання нових співробітників. Тоді в поле Обмеження діалогового вікна Пошук рішення треба додати В8=0. Оптимальне рішення при цьому додатковому обмеженні приведе до тимчасового підвищення поточних витрат (рис. 5.11).

Рис. 5.11 - Внесення додаткових умов в поле „Обмеження” діалогового вікна „Пошук рішення”

Рис. 5.12- Результат рішення задачі про штатний розклад при накладанні додаткових умов

ЛІТЕРАТУРА

1.Бухвалов А.В. и др. Финансовые вычисления для профессионалов.- СПб.: БХВ-Петербург, 2001.-320с. ил.

2.Гарнаев А.Ю. Excel, VBA, Internet в экономике и финансах.- СПб.: БХВ-Петербург, 2001.- 816с.:ил.

3.Евдокимов В.В. и др. Экономическая информатика. Учебник для вузов. Под ред. Д.э.н., проф. В.В.Евдокимова. – СПб.: Питер, 1997. – 592с.

4.Згуровський М.З., Коваленко І.І., Міхайленко В.М. Вступ до комп’ютерних інформаційних технологій: Навч.посіб. – К.: Вид-во Європ. ун-ту (фінанси, інформ. системи, менеджм. і бізнес), 2000.- 265 с.

5.Информатика. Базовый курс/ Симонович С.В. и др.- СПб.: Питер, 2000.- 640с.:ил.

6.Карлберг, Конрад. Бизнес-анализ с помощью Excel.: Пер с англ.- К.: Диалектика, 1997.- 448с.: ил.

7.Лук‘янова В.В. Комп‘ютерний аналіз даних: Посібник. – К.: Видавничий центр „Академія”, 2003. – 344с. (Альма-матер)