Розв'язання технологічних задач лінійної оптимізації з використанням можливостей програми Microsoft Excel

Мета роботи: навчитися в середовищі програми Microsoft Excel знаходити розв’язок технологічних задач на основі лінійних оптимізаційних моделей.

Короткі теоретичні відомості.

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

Для виготовлення декількох (n) видів продукції Р₁, Р₂,…, Р_n використовують m видів ресурсів S₁, S₂,…, S_m. Це можуть бути різні матеріали, електроенергія, напівфабрикати і тому подібне. Об'єм кожного виду ресурсів обмежений і відомий (b₁, b₂,…, b_m). Відомо також a_ij (i = 1,2,…, m; j=1,2…, n) — кількість кожного i-го виду ресурсу, що витрачається на виробництво одиниці j-го виду продукції. Відомий прибуток, що отримується від реалізації одиниці кожного виду продукції (c₁, c₂,…, c_n).

Умови задачі можна представити у вигляді таблиці:

Таблиця 1.

Нехай х_j (j = 1,2,…, n) — кількість кожного виду продукції, яке необхідно виробити.

Для першого ресурсу має місце нерівність-обмеження.

a11×1+ а12×2+… + а1nхn? b1.

Аналогічні нерівності будуть і для останніх видів ресурсів. Слід ураховувати також, що всі значення х_j? 0, j = 1,2,…, n.

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

L (X)=c₁x₁+c₂x₂+…+c_nx_n.

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

(система обмежень);

(цільова функція).

У компактнішій формі цільову функцію і систему обмежень можна записати, використовуючи знак підсумовування:

2. Моделі задачі оптимального розкрою матеріалів.

Є одиниці матеріалу заданих розмірів (заготовки). Ці заготовки потрібно розрізати на деталі різної довжини, причому задані розміри деталей кожного виду і необхідна кількість деталей. Відомі також варіанти розкрою заготовок, причому за кожним відомі отримувана кількість деталей кожного виду і довжина відходів.

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

Уведемо умовні позначення:

х_j — кількість заготовок, які потрібно розрізати способом j;

j — номер способу розкрою заготовки;

n — кількість варіантів розкрою;

a_ij — кількість деталей i-го виду, після розкрою однієї заготовки способом j;

i — номер виду деталі;

m — кількість видів деталей;

b_i — кількість деталей i-го виду;

L — цільова функція; для якої потрібно знайти мінімальне значення;

c_j — довжина відходів після розкрою однієї заготовки способом j.

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

3. Моделі задачі оптимального складу сумішей.

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

Є набір вихідних компонентів, що містять певні складові елементи. Для кожного компонента відомі процентний склад кожної складової і вартість одиниці компонента. З цих компонентів виготовляється суміш, яка повинна містити певний рівень складових елементів.

Математична модель оптимального вибору складу суміші:

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

Таблиця 2.

Визначити в Microsoft Excel план випуску продукції з умови максимізації прибутку від її реалізації.

Розв’язок. Створимо математичну модель даної задачі. Для даної задачі:

• — кількість видів сировини (ресурсів) m = 3;
• — кількість видів продукції n = 4;

Змінні:

х₁ — кількість виробів виду А, яке необхідно виробити;

х₂ — кількість виробів виду Б, яке необхідно виробити;

х₃ — кількість виробів виду В, яке необхідно виробити;

х₄ — кількість виробів виду Г, яке необхідно виробити.

Математична модель даної задачі:

Цільова функція:

L (Х)=5x₁+3x₂+7x₃+8x₄ > max.

Обмеження моделі:

2x₁+x₂+3x₃+2x₄? 200;

x₁+2x₂+4x₃+8x₄? 160;

2x₁+4x₂+x₃+x₄? 170;

x₁, x₂, x₃, x₄? 0;

x₁, x₂, x₃, x₄ — цілі.

Задачі такого типу розв’язуються в редакторі електронних таблиць Microsoft Excel за допомогою надбудови Поиск решения (пункт меню Сервис). Для цього на робочому аркуші Microsoft Excel створимо форму (рис. 1.1), увівши в неї вихідні дані.

Рис. 1.1 Вихідний вигляд форми для введення даних і залежностей

Далі потрібно ввести у відповідні комірки формули для обчислення результатів. У комірки стовпця «Использовано сырья, кг» уводимо формули, відповідні лівим частинам обмежень для видів сировини I, II, III відповідно. Ці значення надбудова обчислить сама.

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

• 1. У комірка із значенням цільової функції вводимо формулу. Можна скористатися стандартною функцією СУММПРОИЗВ, для якої як аргументи вказати комірки рядка «Цена изделия, грн» і комірки із значеннями змінних. Таким чином, перед зверненням до надбудови, коли введені всі формули, комірки із значеннями змінних порожні, а у комірці зі значенням цільової функції і у комірках стовпця «Использовано сырья, кг» будуть нулі.
• 2. Для розв’язання завдань оптимізації досить зручним і простим у використанні є засіб Microsoft Ехсеl Поиск решения. Для виклику цього засобу в меню Сервис виберіть команду Поиск решения.

Якщо команда Поиск решения відсутня в меню Сервис, то треба встановити цю надбудову. У меню Сервис виберіть команду Надстройки. У діалоговому вікні Надстройки встановить прапорець Поиск решения.

Для розв’язання завдання необхідно в діалоговому вікні Поиск решения (рис. 1.2) увести модель.

Рис. 1.2 Діалогове вікно «Поиск решения»

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

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

Перемикач Равной служить для вибору варіанта оптимізації значення цільової комірки (максимізація, мінімізація або рівність заданому числу). Аби встановити задане число, уведіть його в поле. У нашому прикладі для максимізації прибутку ми натискуємо перемикач максимального значення.

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

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

Кнопка Добавить служить для відображення діалогового вікна Добавление ограничения (рис. 1.3).

Рис. 1.3 Диалоговое окно «Добавление ограничения»

У полі Ссылка на ячейку вводиться адреса або ім'я комірок діапазону, на значення яких накладаються обмеження.

Виберіть зі списку, що розкривається, умовний оператор, який необхідно розмістити між посиланням та її обмеженням. Це знаки операторів «не більш», не «менше», «дорівнює» і так далі.

Умовні оператори цілого і двійкового типу можна застосовувати лише при накладенні обмежень на змінні комірки.

У полі Ограничение введіть число, формулу або комірки діапазону, які містять або обчислюють обмежуючі значення.

Щоб приступити до набору нової умови, натисніть кнопку Добавить.

Щоб повернутися в діалогове вікно «Поиск решения», натисніть кнопку ОК.

Команда Изменить діалогового вікна «Поиск решения» служить для відображення діалогового вікна Изменение ограничения.

Команда Удалить служить для зняття вказаного курсором обмеження.

Команда Выполнить служить для запуску пошуку рішення поставленої задачі.

Команда Закрыть служить для виходу з вікна діалогу без запуску пошуку рішення поставленої задачі. При цьому зберігаються установки, зроблені у вікнах діалогу, які з’являлися після натискань на кнопки Параметры, Добавить, Изменить або Удалить.

Кнопка Параметры служить для відображення діалогового вікна Параметры поиска решения, в якому можна завантажити або зберегти модель, і вказати передбачені варіанти пошуку рішення.

Настроювання параметрів алгоритму і програми виробляється в діалоговому вікні Параметры поиска решения (рис. 1.4).

Рис. 1.4 Діалогове вікно «Параметры поиска решения»

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

Після закінчення розрахунків з’являється діалогове вікно Результаты поиска решения (рис. 1.5).

Рис. 1.5 Діалогове вікно «Результаты поиска решения»

Вигляд вікна Поиск решения для розглянутого прикладу наведений на рис. 1.6, робочого аркуша з результатами — на рис. 1.7.

Рис. 1.6 Вікно Поиск решения з уведеними параметрами для випадку чотирьох змінних (виробів А, Б, В, Г)

Рис. 1.7 Вигляд робочого аркуша з результатами

Порядок виконання роботи з використанням програми Microsoft Excel.

• 1. Ознайомитися з короткими теоретичними відомостями.
• 2. Відкрити робочу книгу Microsoft Excel.

Зробити це можна:

• а) клацнувши лівою кнопкою «миші» по ярлику Microsoft Excel на робочому столі Windows;
• б) натиснувши лівою кнопкою «миші» кнопку Пуск у лівому нижньому кутку екрану, навівши на пункт Все Программы, далі - Microsoft Office і вибравши в нім підпрограму Microsoft Excel.
• 3. Зберегти відкриту робочу книгу. Для цього відкрити пункт верхнього меню Файл, в нім вибрати рядок Сохранить как, вибрати папку Мои документы. У віконці Имя файла видалити наявну назву, для чого натиснути клавіші Delete або Backspase на клавіатурі. Увести в режимі російської мови своє прізвище як ім'я файла. Натиснути ОК.
• 4. Розглянути приклад виконання роботи. Увести на аркуші 1 робочої книги форму вихідних даних (рис. 1.1) за прикладом виконання роботи. У вікні Поиск решения ввести обмеження моделі.
• 5. Увести на аркуші 2 робочої книги форму вихідних даних і результатів для свого варіанта за наведеною методикою.

Варіанти завдань для самостійного виконання.

• 1. Для виготовлення виробів двох видів є 100 кг металу. На виготовлення одного виробу першого виду витрачається 2 кг металу, а одного виробу другого виду — 4 кг. Скласти план виробництва, що забезпечує отримання найбільшого прибутку від продажу виробів, якщо відпускна вартість одного виробу першого виду складає 3 грн, а одного виробу другого виду — 2 грн, причому виробів першого виду треба виготовити не більше 40, а виробів другого виду — не більше 20.
• 2. Для виготовлення виробів двох видів склад може відпустити металу не більше 350 кг, причому на виріб першого виду витрачається 5 кг, а на виріб другого виду — 7 кг металу. Вимагається спланувати виробництво так, щоб був забезпечений найбільший прибуток, якщо виробів першого виду вимагається виготовити не більше 35 шт., а виробів другого виду — не більше 25 шт., причому один виріб першого виду коштує 20 грн, а другого виду — 40 грн
• 3. З відходів основного виробництва підприємство може організувати випуск чотирьох видів продукції - А, Б, В, Г. Для цього планується використовувати два типи взаємозамінного устаткування. Кількість виробів кожного виду, яке може бути виготовлене на відповідному устаткуванні в перебігу однієї години, а також витрати, пов’язані з виробництвом одного виробу, наведені в таблиці

Таблиця 3.

Устаткування I типу підприємство може використовувати не більше 80 годин, а устаткування II типу — не більше 60 годин.

Ураховуючи, що підприємству слід виготовити виробів кожного виду відповідно не менше 240, 160, 150 і 220 штук, визначити, протягом якого часу і на якому устаткуванні слід виготовляти кожен з виробів так, щоб отримати не менш потрібної кількості виробів при мінімальних витратах на їх виробництво.

4. Сталевий круглий прокат необхідно розрізати на заготовки завдовжки 45, 35 і 50 см. Необхідна кількість заготовок кожного виду складає відповідно 40, 30 і 20 шт. Можливі варіанти розрізу і величина відходів при кожному з них наведені в таблиці.

Таблиця 4.

Скільки штук прокату слід розрізати за кожним із можливих варіантів, щоб отримати не менше потрібної кількості заготовок при мінімальних відходах?

5. Листи матеріалу розміром 6Ч13 м2 потрібно розкроїти так, щоб вийшли заготовки двох типів: 800 штук заготовок розміром 4Ч5 м2 і 400 штук заготовок розміром 2Ч3 м2. Витрата матеріалу при цьому має бути мінімальною. Способи розкрою матеріалу і кількість заготовок кожного типу, що отримуються при розкрої одного аркуша, представлені в таблиці.

Таблиця 5.

6. На меблевій фабриці зі стандартних листів фанери необхідно вирізувати заготовки чотирьох видів у кількостях, відповідно рівних 24, 31, 18 і 32 шт. Кожен аркуш фанери може розрізати на заготовки двома способами. В таблиці наведені кількість отримуваних заготовок при кожному способі розкрою та величина відходів, що отримуються при кожному способі розкрою одного аркуша фанери.

Таблиця 6.

7. Фірма має у своєму розпорядженні транспорт, що дозволяє однократно перевезти не більше 800 т вантажу загальним об'ємом, що не перевищує 600 м³. Цей транспорт передбачається використовувати для перевезення 11 найменувань вантажу, маса, об'єм і ціна одиниці кожного з яких наведені в таблиці.

Таблиця 7.

Визначити, скільки одиниць кожного вантажу слід розмістити, щоб загальна вартість розміщеного вантажу була максимальною.

• 8. Для створення суміші використовують два види речовин; вартість 1 кг речовини першого виду — 10 грн, а речовини другого виду — 7 грн. У кожному кілограмі речовини першого виду міститься 6 од. компоненту А, 18 од. компоненту Б і 3 од. компоненту В, а в кожному кілограмі речовини другого виду відповідно 3, 4 і 5 од. Потрібно, щоб у суміш компоненту, А входило не менше 430 од., типу Б — не менше 75 од. і типу В — не менше 120 од. Яку кількість речовини кожного виду необхідно витратити, щоб витрати на суміш були мінімальними?
• 9. З чотирьох видів сировини необхідно скласти суміш, до складу якої повинно входити не менше 26 одиниць речовини А, 30 од. — речовини В і 24 од. — речовини С. Кількість одиниць речовини, що міститься в 1 кг сировини кожного виду і ціна 1 кг сировини вказані в таблиці. Скласти суміш, що містить не менш потрібної кількості речовин А, В і С і має мінімальну вартість.

Таблиця 8.

10. У розпорядженні підприємства є три види агломерату, корисних компонентів, А і Б, що відрізняються вмістом, і ціною.

Таблиця 9.

Знайти рішення, що забезпечує мінімізацію сумарної вартості суміші при виконанні таких умов:

• — вміст компонента, А в суміші повинен бути в інтервалі 30−35 т;
• — вміст компонента Б в суміші повинен бути в інтервалі 10−20 т;
• — кількість суміші - 175 т.

Зміст звіту.

• 1. Мета роботи.
• 2. Короткі теоретичні відомості.
• 3. Опис усіх етапів виконання роботи.
• 4. Опис отриманих результатів.
• 5. Висновки за результатами роботи.
• 1. Дати визначення математичної моделі.
• 2. У чому полягає основна мета економіко-математичного моделювання?
• 3. Що прийнято називати цільовою функцією під час моделювання системи?
• 4. Яка функція використовується як цільова функція в моделях оптимального розкрою матеріалів?
• 5. Що дозволяють знайти моделі оптимального вибору складу суміші?
• 6. Як викликати в програмі Microsoft Excel надбудову «Поиск решения» ?