Подякувати Студентському архіву довільною сумою
Admin
26.02.2023 12:38
Дякуємо, що користуєтесь нашим архівом!
Лабораторна робота №1
Інформація про навчальний заклад
ВУЗ:
Національний університет Львівська політехніка
Інститут:
Не вказано
Факультет:
КН
Кафедра:
Кафедра САПР
Інформація про роботу
Рік:
2013
Тип роботи:
Лабораторна робота
Предмет:
Математичні методи дослідження операцій
Частина тексту файла (без зображень, графіків і формул):
МІНІСТЕРСТВО ОСВІТИ I НАУКИ, МОЛОДІ ТА СПОРТУ УКРАЇНИ
Національний університет "Львівська політехніка"
Кафедра САПР
Лабораторна робота №1
з курсу: “Математичні методи дослідження операцій ”
Підготувала:
студентка КН – 2
Прийняла:
к.т.н., доц.каф. САПР
Марікуца У.Б.
ЛЬВІВ - 2013 р.
Мета роботи : ознайомитися з розв’язанням оптимізаційних задач за допомогою застосування Solver в середовищі електронних таблиць EXEL.
Теоретичні відомості.
Задачі математичного програмування
У цьому розділі розглядаються задачі знаходження точок, у яких досягаються максимальні і мінімальні значення функцій декількох змінних, визначених на множинах з лінійними і нелінійними обмеженнями. Іншими словами — знаходиться оптимальний розв’язок задачі управління з обмеженнями. До цього кола задач належать:
Визначення виробничого плану з метою отримання максимального прибутку від продажу зробленої продукції при наявності обмежень на ресурси;
Вибору оптимального плану перевезень продукції з мережі складів у пункти призначення.
Рис. 1. Вікно діалогу “Надбудови”
За замовчуванням надбудова відключена в Excel, але може бути в будь-який час активована засобами самого редактора, без установки якихось додаткових додатків. Для активації виконуємо такі дії:
Запускаєм табличний редактор і розкриваємо головне меню. Для цього треба клікнути мишкою синю кнопку з написом “Файл”.
Відкриваємо список налаштувань редактора.
Вікно з установками табличного редактора розбито на два вертикальних фрейма: в лівій поміщений список розділів, а в правій – пов’язані з розділом настройки. У списку знаходимо і клацаємо “Надстройки”
Усі задачі цього розділу вирішуються за допомогою інструмента Excel Пошук рішення.
Після завантаження інструмента Пошук рішення в списку опцій спадаючого меню Сервіс (Tools) з'явиться нова команда Пошук рішення (Solver). У результаті виконання цієї команди з'являється вікно діалогу “Пошук рішення” (рис.2).
У поле введення Установити цільову комірку (Set Target Cells) указується посилання на комірку з цільовою функцією, значення якої буде максимальним, мінімальним або нулем у залежності від обраного вами перемикача.
У поле введення Змінюючи комірки (By Changing Cell) вказуються комірки, що відведені під змінні цільової функції.
Кнопка Параметри (Options) викликає вікно діалогу “Параметри пошуку рішення”, у якому ви можете змінювати параметри алгоритму пошуку рішення.
Лінійне програмування
До кола задач лінійного програмування належать задача про використання сировини, транспортна задача, задача про складання суміші. При цьому вирішується задача оптимізації з лінійною цільовою функцією й обмеженнями у виді рівностей і нерівностей.
Розглянемо два конкретних приклади.
Приклад 1. Задача про використання сировини.
У цьому прикладі вам потрібно визначити оптимальний план випуску продукції в умовах дефіциту продукції.
Припустимо, що ваше підприємство випускає два види продукції. Ціна одиниці 1 виду продукції дорівнює 25000, 2 виду — 50000.
Для виготовлення продукції використовуються три види сировини, запаси якого оцінюються в 37, 57,6 і 7 умовних одиниць. На кожний вид сировини є коефіцієнт його витрати на одиницю продукції. Відповідні коефіцієнти приведений у табл.1.
Табл. 1. Коефіцієнти витрати сировини на одиницю продукції
Продукція Запаси сировини
вид 1 вид 2 (ум. од.)
1,2 1,9 37
2,3 1,8 57,6
0,1 0,7 7
Позначимо кількість виробленої продукції 1 виду через c1, 2 види — c2. Цільова функція є вираз наступного виду:
Q(c1,c2) = 25000*c1 + 50000*c2
Це є вартість виробленої продукції. Наше рішення повинне забезпечити максимальне значення цієї функції.
Табл. 1 накладає на величини c1 і c2 обмеження наступного виду:
1,2*c1 + 1,9*c2 <= 37
2,3*c1 + 1,8*c2 <= 57,6
0,1*c1 + 0,7*c2 <= 7
c1 >= 0
c2 >= 0
Задача поставлена і приступаємо до її рішення. Виконайте наступні дії:
Введіть в комірку A1 формулу для цільової функції: =25000*c1+50000*c2.
Введіть в комірку A3 формулу для обмеження: =1,2*c1+1,9*c2.
Введіть в комірку A4 формулу для обмеження: =2,3*c1+1,8*c2.
Введіть в комірку A5 формулу для обмеження: =0,1*c1+0,7*c2.
Введіть в комірку A6 формулу для обмеження: =c1.
Введіть в комірку A7 формулу для обмеження: =c2.
Введіть в комірки C1:C2 початкові значення змінних. У нашому випадку приймемо ці значення нульовими.
Виконайте команду Сервіс | Пошук рішення. З'явиться вікно діалогу “Пошук рішення”.
У поле введення Установити цільову комірку вкажіть посилання на комірку A1.
У поле введення Змінюючи комірки вкажіть посилання на комірки C1:C2.
Рис. 3. Вікно діалогу “Додати обмеження”
Рис. 4. Вікно діалогу “Пошук рішення” після введення параметрів
Починаємо вводити інформацію в поле введення Обмеження. Натисніть кнопку Додати. З'явиться вікно діалогу “Додати обмеження”. У поле введення Посилання на комірку вкажіть посилання на комірку A3. У поле введення Обмеження введіть <= і число 37 (рис.3).
Скористайтеся кнопкою Додати для введення інших обмежень. Після введення параметрів вікно діалогу “Пошук рішення” буде мати вигляд аналогічний рис.4. Для зміни обмеження встановіть на нього курсор і натисніть кнопку Змінити.
Натисніть кнопку Виконати. Після закінчення розрахунку Excel відкриє вікно діалогу “Результати пошуку рішення” (рис. 5).
Рис. 5. Вікно діалогу “Результати пошуку рішення”
Виберіть у вікні “Тип звіту” Результати і натисніть кнопку OK. Перед тим листом, де записана постановка задачі, буде вставлений лист “Звіт за результатами 1”, а на екрані ви побачите відповідь на поставлену задачу (рис. 6). В комірках c1 і c2 відображаються значення змінних, на яких досягається максимальне значення цільової функції.
Рис. 6. Результат роботи інструмента Пошук рішення
Натисніть курсором ярлик “Звіт за результатами 1”. На екрані з'явиться звіт Excel про вирішену задачу (рис. 7).
Зверніть увагу на те, що ресурси при обсягах випуску продукції 19,38 і 7,23 умовних одиниць виявляються використаними цілком.
Рис. 7. Звіт Excel за результатами
Приклад 2. Транспортна задача
У цьому прикладі потрібно визначити оптимальний план перевезень продукції зі складів у пункти реалізації.
Припустимо, що вам потрібно перевести весь вантаж із трьох складів у 2 пункти, причому весь вантаж повинний бути перевезений в усі пункти. У 1 пункт повинне бути перевезено 45 одиниць вантажу, у 2— 79. На складах вантаж розподілений у такий спосіб: на 1— 18, 2— 75, 3— 31 умовних одиниць.
Вартість перевезення одиниці вантажу зі складу в пункт визначається табл. 2.
Табл. 2. Вартість перевезення одиниці вантажу
Пункти Склади
п.1 п.2 номер вантаж
17 6 с.1 18
12 13 с.2 75
9 8 с.3 31
45 79
У табл. 3 приведені змінні, котрі позначають обсяги перевезень зі складу в пункти призначення. Наприклад, змінна c4 позначає величину вантажу, що перевезений зі складу 1 у пункт 2.
Табл. 3. Позначення для об'ємів перевезень
Пункти Склади
1 2 номер
c1 c4 1
c2 c5 2
c3 c6 3
У даному прикладі цільова функція, визначена як сума витрат на перевезення, має такий вигляд:
Q(c1,c2,c3,c4,c5,c6) = 17*c1 + 12*c2 + 9*c3 + 6*c4 + 13*c5 + 8*c6
Запишемо рівняння для обмежень. Той факт, що усі вантажі перевезені записується у виді трьох рівнянь:
c1 + c4 = 18
c2 + c5 = 75
c3 + c6 = 31
Сума вантажів у кожному пункті дає ще два рівняння:
c1 + c2 + c3 = 45
c4 + c5 + c6 = 79
Ще два обмеження являються цілком природними. Усі значення змінних повинні бути цілими і ненегативними.
Задача поставлена і приступаємо до її вирішення.
Виконайте наступні дії:
Введіть в комірку A1 формулу для цільової функції: =17*c1+12*c2+9*c3+6*c4+13*c5+8*c6.
Введіть в комірку A3 формулу для обмеження: =c1+c4.
Введіть в комірку A4 формулу для обмеження =c2+c5.
Введіть в комірку A5 формулу для обмеження =c3+c6.
Введіть в комірку A6 формулу для обмеження =c1+c2+c3.
Введіть в комірку A7 формулу для обмеження =c4+c5+c6.
Введіть в комірки C1:C6 початкові значення змінних. У даному випадку приймемо ці значення нульовими.
Виконайте команду Сервіс | Пошук рішення. З'явиться вікно діалогу “Пошук рішення”.
У поле введення Установити цільову комірку введіть посилання на комірку A1.
Встановіть перемикач Мінімальне значення.
У поле введення Змінюючи комірки вкажіть посилання на комірки C1:C6.
Починаємо вводити інформацію в поле введення Обмеження. Натисніть кнопку Додати. З'явиться вікно діалогу “Додати обмеження”. У поле введення Посилання на комірку введіть посилання на комірку A3. У поле введення Обмеження введіть = і число 18. Аналогічну операцію проробіть з комірками A4:A7.
Для введення обмеження на невід’ємність змінних у вікні діалогу “Додати обмеження” у поле введення Посилання на комірку введіть посилання на комірки C1:C6. У поле введення Обмеження введіть >= і число 0 (рис.8). Аналогічну операцію проробіть для введення обмеження на цілочисельність змінних.. У поле введення Обмеження введіть: цілий (рис.9). На рис. 10 представлене заповнене вікно діалогу “Пошук рішення”.
Рис. 8. Обмеження на невід’ємність
Рис. 9. Обмеження на цілочисельність
Рис. 10. Заповнене вікно діалогу “Пошук рішення”
Натисніть кнопку Виконати. Виведіть результати розрахунків на окремий лист.
Транспортна задача вирішена і її результат представлений на рис. 11.
Рис. 11. Результат вирішення транспортної задачі
Рішення в цілих числах не завжди може бути отримане. У таких випадках у вікні діалогу “Результати пошуку рішення” виводиться відповідне повідомлення. Однією з можливих причин може бути помилка в записі обмежень.
Задачі нелінійного програмування
До задач нелінійного програмування належать задачі з нелінійною функцією мети або нелінійними обмеженнями. У цьому розділі ми розглянемо два приклади вирішення задач такого виду. В одному прикладі буде вирішена задача з нелінійною цільовою функцією і з лінійними обмеженнями, а в іншому — крім нелінійної цільової функції будуть і нелінійні обмеження. Інструмент для вирішення залишається колишнім — Пошук рішення.
Приклад 3. Задача з нелінійною функцією мети
У цьому прикладі потрібно знайти мінімум нелінійної функції мети наступного вигляду: Q(c1, c2) = -2*c1 - 6*c2 + c1*c1 - 2*c1*c2 + 2*c2*c2
Обмеження записуються у вигляді нерівностей:
c1 + c2 <= 2
-c1 + 2*c2 <= 2
c1 >= 0, c2 >= 0
Для вирішення поставленої задачі виконайте наступні дії:
Введіть в комірку A1 вираз для функції мети:=-2*c1-6*c2+c1*c1-2*c1*c2+2*c2*c2.
Введіть обмеження в комірки A3:A4, введіть нульові значення в комірки C1:C2.
Виконайте команду Сервіс | Пошук рішення і заповніть параметри у вікні діалогу “Пошук рішення” (рис.12).
Рис. 12. Параметри задачі з нелінійною цільовою функцією
Натисніть кнопку Виконати і виведіть результат розрахунків на окремий лист (рис. 13).
Рис. 13. Звіт за рішенням задачі з нелінійною цільовою функцією
Приклад 4. Задача з нелінійними обмеженнями
У цьому прикладі потрібно знайти мінімум нелінійної функції мети наступного виду: Q(c1, c2) = c1*c1 + (c2 - 4)*(c2 - 4)
Обмеження записуються у виді однії лінійної й однії нелінійної нерівностей:
c2 - c1 - 2 <= 0
2*c2 - c1*c1 => 0
Рис. 14. Параметри задачі з нелінійними обмеженнями
Рис. 15. Рішення задачі з нелінійними обмеженнями
Для вирішення поставленої задачі виконайте наступні дії:
Введіть в комірку A1 вираз для функції мети: =c1*c1+(c2-4)*(c2-4).
Введіть обмеження в комірки A3:A4 введіть нульові значення в комірки C1:C2.
Виконайте команду Сервіс | Пошук рішення і заповніть параметри у вікні діалогу “Пошук рішення” (рис. 14).
Натисніть кнопку Виконати і виведіть результати розрахунків на окремий лист (рис. 15).
Порядок виконання роботи
Ознайомитися з переліком надбудов (Add-Ins) для EXEL та порядком їх інсталяції.
Вивчити основні пункти меню надбудови Solver (Пошук розв’язку).
Ознайомитися з прикладами розв’язання оптимізаційних задач за допомогою Solver.
Оформити звіт про пророблену роботу.
03.05.2014 20:05-
Ділись своїми роботами та отримуй миттєві бонуси!
0%
Оголошення від адміністратора