Розв'яжемо це завдання графічним методом у табличному редакторі Microsoft Excel(Рис. 1). Для побудови ОДР та ліній рівня скористаємося Майстром діаграм . ОДР є багатокутником з вершинами в точках: (0; 0), (0; 6), (2; 5), (4; 3), (5; 0).
При переміщенні лінії рівня у напрямку вектора отримуємо оптимальне рішення у точці з координатами (2; 5).
Аналогічним чином можна вирішити це завдання графічним методом у табличному редакторі OpenOffice.org Calc скориставшись пунктом меню Діаграма .
Рішення ЗЛПу Microsoft Excel та OpenOffice.org Calc за допомогою вбудованої функції Пошук рішення
У табличному процесорі Microsoft Excel існує вбудована функція Пошук рішення , за допомогою якої можна вирішити задачу лінійного програмування. Якщо цей модуль встановлено, його можна запустити, вибравши команду Сервіс/Пошук рішення (Рис. 2). На екрані з'явиться діалогове вікно Пошук рішення (Рис. 3).
Мал. 2. Р та с. 3.
Якщо такого пункту в меню Сервіс не виявилося, слід завантажити відповідну програму-надбудову. Для цього виберіть команду Сервіс/Надбудови (рис. 4) та у діалоговому вікні Надбудови встановіть прапорець у рядку Пошук рішення (Рис. 5).
Розберемо рішення ЗЛП за допомогою функції Пошук рішення на прикладі задачі 1.
1. Створимо таблицю для введення вихідних даних: змінних, цільової функції, обмежень.
2. Введемо початкові нульові значеннядля і .
3. Задамо цільову функцію в комірці D41 та обмеження в комірках Е39, Е40 та E41 (рис. 6).
Мал. 4. Р та с. 5.
4. Виберемо команду Сервіс/Пошук рішення , у вікні Пошук рішення встановимо цільову комірку D41, задамо умову відшукання максимального значення (рис. 7).
5. У полі Змінюючи комірки встановимо посилання на комірки С40 та С41, які будуть змінені (можна ввести адреси або імена комірок з клавіатури або вказати діапазон комірок на робочому аркуші за допомогою миші). При натисканні на кнопці Припустити автоматично виділяються осередки, на які є пряме або непряме посилання у формулі цільового осередку (рис. 7).
6. Визначимо обмеження, для цього клацанням по кнопці Додати відкриємо діалогове вікно Додавання обмеження . Введемо обмеження для осередків E39, E40, E41. Обмеження можна встановити як для змінних осередків, так і для цільового осередку, а також для інших осередків, що прямо або опосередковано присутні в моделі (рис. 8, 9).
Мал. 8. Р та с. 9.
7. Клацніть на кнопці Параметри відкриємо діалогове вікно Параметри пошуку рішення . У цьому вікні виберемо лінійну модельта невід'ємні значення (невід'ємні значення для осередків С40 та С41 можна було також встановити при визначенні обмежень). Детальніше дізнатися про параметри, що задаються, можна клацнувши на кнопці Довідка (Рис. 10).
8. Після того, як всі параметри та обмеження задані, запускаємо пошук рішення, клацнувши на кнопці Виконати (Рис. 9). У міру того як йде пошукокремі його кроки відображаються в рядку стану. Коли пошук буде закінчено, до таблиці буде внесено нові значення і на екрані з'явиться діалогове вікно Результати пошуку рішення , що повідомляють про завершення операції (рис. 11).
Рішення знайдено. Усі обмеження та умови оптимальності виконані. Збережемо знайдене рішення. У цьому випадку таблицю буде оновлено. У разі потреби завжди можна буде відновити вихідні дані за допомогою звіту. Для вибору типу звіту достатньо виділити назву потрібного звіту у списку Тип звіту (або кілька назв, утримуючи клавішу Сtrl). Вони будуть вставлені на окремих листаху робочу книгу перед аркушем із вихідними даними.
Пропоновані звіти містять наступну інформацію:
звіт Результати містить відомості про початкові та поточні значення цільового осередку та змінних осередків, а також про відповідність значень заданим обмеженням;
звіт Стійкість відображає знайдений результат, а також нижні та верхні граничні значення для комірок, що змінюються;
звіт Межі показує залежність рішень від зміни формули чи обмежень.
Якщо планується використати створену модель надалі, знайдене рішення можна зберегти як сценарій. Для цього у діалоговому вікні Результати пошуку рішення необхідно клацнути на кнопці Зберегти сценарій .
Аналогічно Пошук рішення здійснюється в OpenOffice.org Calc.
Завдання
1. Розв'язати задачі 2 та 3 графічним методом.
2. Вирішити завдання 2 і 3 у редакторі Microsoft Excel або OpenOffice.org Calc, використовуючи вбудовану функцію Пошук рішення .
3. Порівняти та проаналізувати отримані результати.
4. Відповісти на контрольні питання.
5. Оформити звіт.
Завдання 2. Фармацевтична фірма Ozark щодня виробляє не менше 800 фунтів певної харчової добавки – суміші кукурудзяного та соєвого борошна, склад якої представлений у таблиці 2.
Таблиця 2
Дієтологи вимагають, щоб у харчовій добавці було не менше 30% білка та не більше 5% клітковини. Фірма Ozark хоче визначити рецептуру суміші мінімальної вартості з урахуванням вимог дієтологів.
Завдання 3.Підприємство, що спеціалізується на виробництві трикотажного полотна двох видів, використовує для свого виробництва чотири види сировини (вовняну, бавовняну, віскозну та акрилову нитки), запаси якого на планований період становлять відповідно 80, 80, 260 і 410 бобін. У наведеній нижче таблиці наведено технологічні коефіцієнти, тобто. витрата кожного виду сировини виробництва одного метра кожного виду трикотажу.
Таблиця 3
Прибуток від 1м трикотажного полотна першого виду становить 2 у.о., а трикотажного полотна другого виду 3 у.о. Необхідно визначити оптимальний план випуску трикотажного полотна першого та другого виду, щоб забезпечити максимальний прибуток від їх реалізації.
1. Що означає скласти математичну модель ЗЛП?
2. З яких етапів складається графічний методрішення ЗЛП?
3. Яка геометрична інтерпретація рішення системи лінійних нерівностейіз двома змінними?
4. Як визначається напрямок якнайшвидшого зростання цільової функції?
5. Яке рішення називається оптимальним рішенням ЗЛП?
6. У якому разі ЗЛП має множину рішень?
7. За яких умов ЗЛП може бути нерозв'язною?
8. Як встановити модуль Пошук рішення ?
9. Для чого призначена кнопка Припустити у вікні Пошук рішення ?
10. Які типи звітів можна отримати при вирішенні ЗЛП за допомогою вбудованої функції Пошук рішення ?
Симплексний метод. Завдання визначення оптимального планувипуску продукції Використання вбудованих функцій редакторів Microsoft Excel та OpenOffice.org Calc для побудови математичної моделі та вирішення ЗЛП.
Ціль лабораторного заняття:
Набуття навичок рішення ЗЛП симплекс-Методом. Освоєння прийомів запису математичної моделі ЗЛП з великою кількістюневідомих у табличних редакторах Microsoft Excel та OpenOffice.org Calc за допомогою вбудованої функції СУММПРОИЗВ. Набуття навичок рішення ЗЛП з великою кількістю невідомих за допомогою функції Пошук рішення .
Завдання лабораторного заняття:
1. Освоєння симплекс-методу розв'язання ЗЛП.
2. Побудова математичної моделі задачі табличних редакторів Microsoft Excel і OpenOffice.org Calc за допомогою вбудованої функції СУММПРОИЗВ.
3. Знаходження максимуму (мінімуму) цільової функції за допомогою команди Пошук рішення .
4. Аналіз одержаних результатів.
5. Оформлення звіту.
1. Короткі теоретичні відомості.
2. Рішення ЗЛП симплекс методом без використання табличних редакторів.
3. Рішення ЗЛП на визначення оптимального плану випуску продукції Microsoft Excel і OpenOffice.org Calc за допомогою вбудованої функції Пошук рішення .
4. Завдання.
5. Контрольні питання.
Короткі теоретичні відомості
В основу симплекс-методу (симплексного методу) лягла ідея послідовного покращення рішення.
Геометричний зміст симплексного методу полягає в послідовному переході від однієї вершини багатогранника обмежень (званої первісної) до сусідньої, в якій лінійна цільова функція приймає краще або, Крайній мірі, Не гірше значення. Цей процес здійснюється доти, доки не буде знайдено оптимальне рішення – вершина, де досягається оптимальне значенняцільової функції (якщо завдання має кінцевий оптимум).
Реалізація симплекс-метода передбачає зміст трьох основних елементів:
1. Визначення будь-якого початкового допустимого базисного розв'язання задачі (базисне рішення називається допустимим, якщо значення, що входять до нього змінних, невід'ємні);
2. Правила переходу до кращого (точніше, не гіршого) рішення;
3. Критерій перевірки оптимальності знайденого рішення.
Для використання симплексного методу завдання лінійного програмування має бути приведено до канонічному вигляду, тобто. система обмежень має бути представлена у вигляді рівнянь.
Практичні розрахунки під час вирішення прикладних завдань симплексним методомвиконуються в даний час за допомогою комп'ютерних програм, таких як табличний процесор Microsoft Excel, пакети прикладних програм MathCAD, Math Lab та ін. Однак, якщо розрахунки здійснюються вручну, зручно використовувати так звані симплексні таблиці.
Для вирішення задач лінійного програмування симплекс-методомсеред MS Excel заповнюються осередки вихідними даними як чисел і формулами математичної моделі.
MS Excel дозволяє одержати оптимальне рішення без обмеження розмірності системи нерівностей цільової функції.
Вирішимо завдання про вироби, що випускаються, симплекс-методом застосовуючи надбудову «Пошук рішення» в MS Excel.
1. Заповніть таблицю Excelу режимі чисел (рис.1)
2. Заповніть таблицю Excel як формул (рис.2)
Рис.1 Таблиця як чисел
Рис.1 Таблиця як формул
Тут: В9: С9 – результат ( оптимальна кількістьвиробів кожного виду);
В6: С6 – коефіцієнти цільової функції;
В10 - значення цільової функції;
В3:С5 – коефіцієнти обмежень;
D12:D14 – права частина обмежень;
B12:B14 – обчислювані (фактичні) значення лівої частини обмежень.
Вирішимо завдання за допомогою команди Дані/Пошук рішення. На екрані з'являється діалогове вікно Пошук рішення.
У полі Встановити цільову функцію буде показано посилання на активний осередок, тобто. на В10. Причому це посилання є абсолютним. У секції Рівної встановлюємо перемикач Максимальному (мінімальному) значення залежно від цільової функції. Обмеження встановлюються за допомогою кнопки Додати, яка викликає діалогове вікно їх введення Додавання обмеження.
У полі введення Посилання на комірку: вказується адреса комірки, що містить формулу лівої частини обмеження. Потім вибирається зі списку знак співвідношення. У полі Обмеження вказується адреса комірки, що містить праву частинуобмеження. Клацаємо на кнопку Додати та повторюємо до наступного обмеження. Після введення всіх обмежень натискаємо ОК.
Оскільки всі змінні несуть умови неотрицательности, їх позитивність задається через кнопку Параметри у вікні діалогу Пошук рішення. Після клацання по ній, на екрані вікно Параметри пошуку рішення.
Встановлюємо прапорець Зробити змінні без обмежень невід'ємними та вибрати Метод розв'язання Пошук вирішення лінійних задач симплекс-методом. Клацаємо на кнопці Знайти рішення.
Excel пред'явить вікно Результати пошуку рішення з повідомленням про те, що рішення знайдено, або про те, що не може знайти відповідного рішення.
Якщо обчислення виявились успішними, Excel пред'явить наступне вікно підсумків. Їх можна зберегти чи відмовитися. Крім того, можна отримати один з трьох видівзвітів (Результати , Стійкість , Межі), що дозволяють краще усвідомити отримані результати, зокрема, оцінити їх достовірність.
Після знайденого рішення, у осередках В9:С9 з'явиться оптимальна кількість виробів кожного виду.
У разі збереження звіту виберіть – Звіт за результатами (рис.3).
Зі звіту видно, що ресурс 1 не використовується повністю на 150 кг, а ресурс 2 і 3 використовується повністю.
В результаті отримано оптимальний план, при якому виробів 1 виду необхідно випустити в кількості 58 прим., а виробів 2 виду в кількості 42 прим. У цьому прибуток від реалізації максимальної і становить 4660 тыс.руб.
Рис.3 Звіт за результатами
1. Зі станції формування щодня відправляються пасажирські та швидкі поїзди, складені з плацкартних, купейних та м'яких вагонів. Число місць у плацкартному вагоні – 54, у купейному – 36, у м'якому – 18. У таблиці вказано склад поїзда кожного типу та кількість наявних у парку вагонів різного типу. Визначити кількість швидких і пасажирських поїздів, які необхідно формувати щодня, щоб кількість пасажирів, що перевозилися, була максимальною.
Розв'язання транспортних завдань
Транспортними завданнями називаються завдання визначення оптимального плану перевезень вантажу з даних пунктів відправлення задані пункти споживання.
| b 1 | b 2 | … | b k | … | b g | |
| a 1 | }РекомендуємоЩо стоїть за останнім обвалом ринку криптовалюту?МОСКВА, 14 листопада — РІА Новини, Наталія Дембінська. Ще в серпні найпопулярніша і найдорожча криптовалюта у світі — біткоїн — розділилася на дві: Bitcoin...
|
