Розв’язання задач лінійного програмування
4.2 Вибір середовища програмування
Microsoft Office є єдиним пакетом, встановленим на більшості комп'ютерів. Excel — це організатор будь-якого типа даних, будь вони числовими, текстовими або якими-небудь ще. Оскільки в цій програмі є багато вбудованих обчислювальних можливостей, більшість людей звертаються до Excel, коли потрібно створити таблиці для фінансових розрахунків, працювати із статистичними даними. За допомогою даної програми можна зробити свої звіти професіональнішими і виконати додаткове фінансування за допомогою красивих ділових презентацій. За допомогою даного пакету можна створювати різноманітні графіки і діаграми для більш наочного представлення результатів.
Excel — це великий охоронець списків (хоча їх прийнято називати в Excel базами даних) і творець таблиць. Тому Excel як не можна краще підходить для відстежування інформації про товари, що продаються, про обслуговуваних клієнтів, про службовців, яких контролює будь-яка організація і т.д.
Кожна одиниця інформації (ім'я, адреса, число продажів в місяць і ін.) займає свою власну клітинку в створюваній робочій таблиці. У кожній робочій таблиці 256 стовпців (з яких в новій робочій таблиці на екрані видно, як правило, тільки перші 10 або 11 (від А до J) і 65 536 рядків (з яких зазвичай видні тільки перші 15-20). Кожна нова робоча книга містить три чистих листа робочої таблиці.
Вся інформація, що поміщається в електронну таблицю, зберігається в окремих клітинках робочої таблиці. Але ввести інформацію можна тільки в поточну клітинку. За допомогою адреси в рядку формул і табличний курсор Excel вказує, який з 16 мільйонів клітинок робочої таблиці є поточним.
Excel є чудовим інструментом для виконання розрахунків по формулах, а також для зберігання інформації у вигляді списків і таблиць. Це дає можливість набагато спростити роботу із статистичними даними, які розраховуються по складних формулах. В програмі закладені багато груп формул, в тому числі і статистичні, або користувач сам може записати формулу.
Тому можна зробити висновок, що даний програмний пакет найкраще підходить для розв’язку задач лінійного програмування.
Опис вхідних та вихідних даних
Дана програма написана в Excel. В ній задаються обмеження і значення цільової функції, які можна змінювати. Потім програма проводить розрахунки і в клітинках, яким попередньо були присвоєнні спеціальні імена, записує розв’язок функції мети і значення змінних, при яких цей оптимальний розв’язок був отриманий. Розглянемо всі введення даних детальніше.
Вхідними
даними для
даної задачі
є виражені з
обмежень значення
кожної змінної
та вираз
для обчислення
цільової функції.
Значення змінних
вводяться
в поле «Ограничения»
в меню інструменту
Пошук розв'язку.
Вираз значення
цільової функції
вводиться в
комірку робочого
аркуша.
Вихідними
даними є значення
кожної змінної
та максимальне
значення цільової
функції, які
будуть записані
у визначених
клітинках
робочої таблиці.
Розробка структури програми
Щоб отримати розв'язок задачі лінійного програмування за допомогою Excel потрібно виконати наступні дії:
1. В заданій
задачі три
змінних, тому
клітинкам
потрібно присвоїти
імена відповідно
- витрати
на рекламу по
телебаченню;
-
витрати на
радіорекламу;
- витрати
на рекламу
у газетах. Для
цього викликаємо
команду Вставка
→ Имя → Присвоить.
У вікні, що появилося
записуємо ім’я,
яке хочемо
присвоїти
клітинці, для
першої клітинки
це буде
,
і натиснути
Enter. Для двох решти
клітинок, що
залишилися
виконуємо
аналогічні
дії у присвоєнні
імені. Після
цього у клітинці
аналогічно,
як і для змінних,
присвоюємо
ім’я
,
в ній програма
запише розв’язок
даної задачі
(рисунок 4.4.1):

Рисунок 4.4.1 – Вікно для присвоєння імені для комірки цільової функції
Після
цього у цій же
комірці записуємо
формулу для
обчислення
значення цільової
функції у наступному
вигляді:
Запускаємо програму. Спочатку натискаємо на вкладку Сервис, що знаходиться на панелі інструментів, і в меню, що появилося, вибираємо Поиск решения (рисунок 4.4.2):

Рисунок 4.4.2 – Заповнення вікна Поиск решения
В даному
діалоговому
вікні встановлюємо
значення цільової
клітинки
та зазначаємо
пошук максимуму
цільової функції.
Задаємо клітинки,
в яких буде
розв'язок даної
задачі — діапазон
клітинок від
до
.
За допомогою
кнопки Добавить
додаємо обмеження
у вигляді восьми
обмежень (рисунок
4.4.3):

Рисунок 4.4.3 – Вікно для додавання обмежень
В меню Параметры відмічаємо, що модель лінійна (рисунок 4.4.4):

Рисунок 4.4.4 – Вікно для визначення параметрів
Натиснувши на кнопку Вьполнить отримуємо розв'язок задачі (рисунок 4.4.5):

Рисунок 4.4.5 – Розв’язок даної задачі
В
комірках
отримали відповідні
значення
,
а в комірці
максимальне
значення цільової
функції.
4.5 Розробка схеми алгоритму
На рисунку 4.5.1 приведена схема алгоритму програми:
Рисунок 4.5.1 – Схема алгоритму програми
4.6 Розробка тестів
У якості тесту будемо використовувати розв'язок задачі, отриманий вручну. Для цього отриману у третьому розділі даної роботи модель заносимо до симплекс таблиці (таблиця 4.6.1):
Таблиця 4.6.1 – Ітерація 1
|
|
|
|
|
|
|
|
|
|
|
1 | 1 | 1 | 1 | 0 | 0 | 10000 |
|
|
1 |
1 | 0 | 0 | 1 | 0 | 6000 |
|
|
0 | 2 | -1 | 0 | 0 | 1 | 0 |
|
|
20 | 8 | 12 | 0 | 0 | 0 | 0 |
Знаходимо
базисний елемент:
шукаємо стовпчик
з максимальним
коефіцієнтом
і рядок з мінімальним
відношенням
/
.
Отриманий
елемент є базисним
елементом.
Тепер змінну
виводимо з
базису, а
вводимо в базис.
Кожний елемент
вибраного рядка
ділимо на базисний
елемент і
перераховуємо
таблицю за
правилом
прямокутника.
Елементи
перераховуємо
за коефіцієнтами.
Отримуємо
симплекс-таблицю
4.6.2.
Таблиця 4.6.2 – Ітерація 2
|
|
|
|
|
|
|
|
|
|
|
0 | 0 |
1 |
1 | -1 | 0 | 4000 |
|
|
1 | 1 | 0 | 0 | 1 | 0 | 6000 |
|
|
0 | 2 | -1 | 0 | 0 | 1 | 0 |
|
|
0 | -12 | 12 | 0 | -20 | 0 | -120000 |
Перевіряємо
елементи рядка
.
Оскільки вони
всі не від’ємні
і не нульові,
продовжуємо
розрахунок
далі. Отримуємо
базисний елемент.
Перераховуємо
таблицю, як
було показано
раніше. Отримуємо
симплекс-таблицю
4.6.3.
Таблиця 4.6.3 – Ітерація 3
|
|
|
|
|
|
|
|
|
|
|
0 | 0 | 1 | 1 | -1 | 0 | 4000 |
|
|
1 | 1 | 0 | 0 | 1 | 0 | 6000 |
|
|
0 | 2 | 0 | 1 | -1 | 1 | 4000 |
|
|
0 | -12 | 0 | -12 | -8 | 0 | -168000 |
Як бачимо,
всі елементи
від’ємні або
дорівнюють
нулю. Отже, знайдений
розв’язок.
Запишемо його
у вигляді:
Значення
змінних:
.
Так як за умовою задачі необхідно було знайти максимум функції, але симплекс-метод дозволяє знайти лише мінімум і тому було попередньо змінено знак цільової функції, то отриманий розв’язок задачі знову потрібно помножити на -1, тому ми отримаємо наступне значення:
Цільова
функція:
.
4.7 Аналіз результатів тестування
Проаналізувавши отримані результати бачимо, що значення цільової функції однакове як при вирішені задачі вручну так i при обрахунку програми.
За звичай, при обрахунку вручну появляється деяка похибка, але в даній задачі цього не відбувається, так як числа за умовою досить прості і при обрахунку ніяких заокруглень не робимо, тому отримаємо точно такі самі значення, що і при розрахунку з використання програми.
4.8 Інструкція користувачеві
Для вирішення
заданої задачі
відкриваємо
файл «Kursach.xls».
Перед користувачем
відкриється
на перший погляд
майже чистий
лист робочої
таблиці Excel,
лише в комірці
буде записаний
нуль, але це не
так. Потрібно
натиснути
на вкладку
Сервис, що
знаходиться
на панелі
інструментів,
і в меню, що
появилося,
вибрати Поиск
решения (див.
рисунок 4.4.2). Потім
у вікні, що появилося
натиснути на
кнопку Выполнить(див.
рисунок 4.4.4) і
програма все
зробить сама.
Перед користувачем з’явиться розв’язок даної задачі у вигляді як це показано на рисунку 4.4.5.
При
необхідності
можна змінити
цільову функцію
і значення
параметрів.
Для того, щоб
змінити цільову
функцію необхідно
в комірці
ввести ту формулу,
яку необхідно.
А якщо необхідно
змінити обмеження,
то це можна
зробити у вікні
Поиск решения
так, як це було
описано у пункті
4.4.
Висновки
В процесі написання даної роботи я усвідомила різницю в трактуванні понять “модель” і “метод”, необхідність поглибленого оволодіння математичними та статистичними знаннями. Приведені в роботі приклади з застосуванням математичних моделей, на мою думку, досить добре проілюстрували весь процес прийняття рішення з боку даної методології.
Незалежно від обраної професії, незалежно від життєвої ситуації людина повинна приймати раціональне рішення. Для того щоб запобігти помилок і отримати необхідну користь, потрібно розуміти весь процес прийняття рішення. Отже стає зрозуміло, що методи науки управління підвищують якість рішень, що приймаються за рахунок використання наукового підходу, системної орієнтації та моделей.
Дана курсова робота складається з багатьох розділів, що дозволяють повність зрозуміти суть проблеми, зв’язаної з оптимізацією, а також розібратися з програмним забезпеченням, що вирішує задану задачу.
Метою виконаної курсової роботи є вирішення конкретної задачі та створення програми для обчислення даних. Робота виконана з детальним описом кожного з розділів. Також приведений опис аналітичного розв'язку задачі, та порівняння результатів з розрахунком вручну.
При розв’язку задачі як в ручну так і за допомогою програми було отримано значення цільової функції та значення шуканих змінних. Тобто визначивши всі витрати на рекламу, можна отримати максимальний прибуток фірмі.
Результатом виконання даної курсової роботи є розроблена програма у найпоширенішому програмного пакеті Excel, що вирішує задачу симплекс-методом та виводить результат.
Програму можна використовувати для розрахунку різних видів оптимізації і не тільки витрат, а інших коштів, що проходять через будь-яку організацію.
Література
kgtunnet/WD/TUTOR/lp/lp01.html#$lp01.1;
semenets/public/graphic.html;
dl.sumdu.edu/e-pub/mo/rus/m_simpl.html;
kgtunnet/WD/TUTOR/lp/lp05.html;
dl.sumdu.edu/e-pub/mo/rus/m_excel.html - Приклад розв’язку задач лінійного програмування в Excel;
Гавриленко В., Пархоменко Л., "Решение задач аппроксимации средствами MS EXCEL", "Компьютеры+программы", №12/2002р., с.42.imcs.dvgu/lib/nurmi/finmath/node42.html.
Додаток А
Міністерство освіти і науки України
Вінницький національний технічний університет
Інститут автоматики, електроніки і комп’ютерних систем управління
Факультет управління та комп’ютерних систем управління
Кафедра комп’ютерних систем управління
ТЕХНІЧНЕ ЗАВДАННЯ
на виконання курсової роботи на тему:
“ Розв’язок задач лінійного програмування ”
з дисципліни
“Математичне програмування та дослідження операцій”
Мета: Метою курсової роботи є розробка програмного забезпечення для розв’язку симплекс задачі
Для цього необхідно виконати наступні етапи:
1.1 Найменування та галузь застосування об’єкта розробки: Дана робота присвячена розробці програмного забезпечення для розв’язку симплекс задачі .
1.2 Підстава для проведення робіт: Підставою для розробки програмного забезпечення є навчальний план спеціальності 7.091401, робоча програма для
33
дисципліни “Математичне програмування та дослідження операцій”, індивідуальне завдання.
1.3 Дата початку роботи: “__” “______”2007р.
1.4 Дата закінчення роботи: “__” “_______”2007р.
1.5 Мета призначення розробки: Метою даної роботи є розробка програмного забезпечення для автоматизації роботи симплекс задачі.
1.6 Вимоги до надійності: Надійність даного проекту забезпечується використанням структурного програмування; а також тим, що програма працює під керівництвом єдиного меню; в ній передбачені переривання, тобто програма реагує на невірні дії користувача, вказуючи на дії, які необхідно виконати.
Все програмне забезпечення та супроводжуюча техніка документація повинні задовольняти наступним ГОСТам:
ГОСТ 19.701-90
ІСО 5807 – 85 ГОСТ на розробку програмних документів, схем, алгоритмів програм, даних та систем.
ГОСТ 19.781 – 74 – Вимоги до розробки програмного забезпечення
ГОСТ 19.101-77(СТ СЭВ 1626 - 79) – Держстандарт на розробку програмної документації, видів програм та програмних документів.
ГОСТ 29.401-78- Текст програми. Вимоги до змісту та оформлення.
ГОСТ 19.106-78- Вимоги до програмної документації.
ГОСТ 7.1- 84 та ДСТУ 3008- 95- Розробка технічної документації.
1.7 Стадії та етапи розробки:
1. Уточнення постановки задачі та розробка технічного завдання на виконання курсової роботи “Розв’язок симплекс задачі” (до 14.09.07).
2. Варіантний аналіз існуючих методів розв’язання поставленої задачі та вибір програмного середовища для вирішення задачі курсової роботи “Розв’язок симплекс задачі” (до28.09.07).
3. Розробка структури програми та наповнення файлів бази даних для розв’язку симплекс задачі (до 12.10.07).
34
4. Розробка програмного забезпечення для розв’язку симплекс задачі (до 2.11.07).
5. Розробка інтерфейсу , планування, тестування розробленої програми та створення бази даних для розв’язку симплекс задачі (до 20.11.07).
6. Демонстрація програмного забезпечення для розв’язку симплекс (до 30.11.07).
7. Розробка пояснювальної записки (до 7.12.07).
8. Захист курсової роботи (до 21.12.07).
1.8 Вимоги до безпеки: Розроблене програмне забезпечення повинно відповідати сучасним вимогам СНІП та ДЕСТів до робочого місця операторів ЕОМ.