Міністерство освіти та науки України
Вінницький національний технічний університет
Інститут автоматики та компютерних систем управління
Факультет автоматики та компютерних систем управління
Розвязання задач лінійного програмування(А)
Пояснювальна записка
з дисципліни «Математичне програмування та дослідження операцій»
до курсової роботи за спеціальністю
«Системи управління та автоматики»
08-01.МПДО.342.00.000-ПЗ
Вінниця, ВНТУ 2007
Анотація
В даній курсові роботі розглянуто методи розвязку задач лінійного програмування. Такі задачі досить поширені у повсякденному житті. Тому в даній роботі розглянуто рішення на окремій задачі, а також розглянуто як їх можна розвязувати вручну і за допомогою спеціального програмного продукту.
Було розроблено математичну модель і програмне забезпечення. Дана задача вирішується симплекс методом, тому досліджується основний принцип метода, особливості і переваги в порівнянні з іншими методами.
Зміст
У класичній математиці методи пошуку оптимальних рішень розглядають у розділах класичної математики, звязаних з вивченням екстремумів функцій, у математичному програмуванні.
Існує багато розділів в математичному програмуванні, серед них лінійне і нелінійне програмування, опукле і квадратичне, і багато інших. Але всі вони зводяться до отримання оптимального рішення у великій кількості задач різних промислових і виробничих гілках суспільства. Розглянемо лінійне програмування та визначимо основні принципи і алгоритми даного розділу математичного програмування.
Лінійне програмування є найбільш часто використовуваним методом оптимізації. До завдань лінійного програмування можна віднести:
- раціональне використання сировини і матеріалів;
- завдання оптимального розкрою;
-оптимізації виробничої програми підприємств;
-оптимального розміщення і концентрації виробництва;
-складання оптимального плану перевезень, роботи транспорту;
-управління виробничими запасами і ін.
Для великої кількості практично цікавих завдань цільова функція виражається лінійно - через характеристики плану, причому допустимі значення параметрів підпорядковані лінійній рівності або нерівностям. Знаходження за даних умов абсолютного екстремуму цільової функції носить назву лінійного програмування.
Першим дослідженням по лінійному програмуванню є робота Л. В. Кантфовіча “Математичні методи організації і планування виробництва”, яке було опубліковане в 1939 р. У ньому розміщена постановка завдань лінійного програмування, розроблений метод результуючих множників вирішення завдань лінійного програмування і дано його теоретичне обґрунтування.
Головна мета лінійного програмування є математичне формулювання проблеми складання такого плану використання різних способів виробництва, який дозволяє отримати максимальну кількість однорідного продукту при ресурсах, що є в наявності.
1 Опис існуючих методів розвязку задач лінійного програмування
Лінійне програмування розвязує велику кількість задач з різними типами обмежень. Тому їх можна розвязати різними методами. Розглянемо їх принцип.
1.1 Постановка задачі
Методи лінійного програмування - чисельні методи вирішення оптимізаційних задач, що зводяться до формальних моделей лінійного програмування[1].
Як відомо, будь-яке завдання лінійного програмування може бути приведене до канонічної моделі мінімізації лінійної цільової функції з лінійними обмеженнями типу рівності. Оскільки число змінних в завданні лінійного програмування більше числа обмежень (), то можна отримати рішення, прирівнявши нулю () змінних, які називаються вільними. Решта m змінних, які називаються базисними, можна легко визначити з системи обмежень звичайними методами лінійної алгебри. Якщо рішення існує, то воно називається базисним. Якщо задача лінійного програмування має оптимальні рішення, то хоча б один із них є базисним.
Приведені міркування означають, що при пошуку оптимального рішення задачі лінійного програмування досить обмежитися перебором базисних допустимих рішень. Те, що не всі базисні рішення є допустимими, істотно проблеми не міняє, оскільки щоб оцінити допустимість базисного рішення, його необхідно отримати.
В загальному постановка задачі має вигляд:
Нехай маємо деякі змінні і функцію цих змінних, яка називається цільовою функцією. Потрібно найти екстремум (максимум чи мінімум) цільової функціїпри умові,що змінні належать деякій області :
(1.1.1)
В залежності від виду функції і області G розрізняють розділи математичного програмування: квадратичне програмування, випукле і ін.
Лінійне програмування характеризується тим, що функція і лінійною функцією змінних і область G визначається системою лінійних рівнянь чи нерівностей.
1.2 Графічний метод
Якщо модель містить тільки дві змінні, задачу можна розвязати графічно. У випадку трьох змінних графічний розвязок стає менш наочним, а при більшому числі змінних - взагалі неможливим. Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розвязання задач лінійного програмування[2].
Перший крок при використанні графічного методу полягає в поданні області допустимих розвязків, у якій водночас задовольняються всі обмеження моделі. Нехай шукана область (простір) розвязків задачі показана. Умови невідємності змінних обмежують область їх допустимих значень. Інші межі простору розвязків потрібно зобразити прямими лініями, побудованими по рівняннях, що отримані заміною знака «?» чи «?» знаком “=" в обмеженнях. Області, в яких відповідні обмеження виконуються як нерівності, указуються стрілками, спрямованими вбік допустимих значень змінних. Отримуємо простір розвязків задачі. У кожній точці, що належить внутрішній області або межам, всі обмеження виконуються, тому розвязки, що відповідають цим точкам, є допустимими. Серед безкінечного числа таких точок можна знайти точку оптимального розвязку, якщо зясувати, в якому напрямку зростає цільова функція. На графік наносять лінію рівня цільової функції , де - довільне значення . Будують вектор , що є нормаллю до ліній рівня цільової функції й визначає напрямок оптимізації . Лінію рівня зрушують паралельно самій собі вздовж вектора доти, поки вона не вийде за межі області допустимих розвязків. Остання точка цієї області й буде точкою оптимуму.
Значення та в розвязуючій точці визначаються шляхом розвязання системи рівнянь.
Зазначимо, що у випадку, коли лінії рівня мають такий самий нахил, як пряма звязуючого обмеження (тобто такого, що проходить через оптимальну точку), матимемо безліч оптимумів на відрізку.
Графічний спосіб розвязування ґрунтується на геометричній інтерпретації задачі лінійного програмування, тому він досить простий для розуміння. Недоліком є те, що графічним способом можна розвязати задачу, в якій в обмеженнях є лише дві змінні, потрібно намагатися малювати лінії з найбільшою точністю, в протилежному випадку можна отримати велику похибку, а в результаті неправильне рішення.
1.3 Симплекс-метод
Симплекс-метод застосовується до рішення будь-якої задачі лінійного програмування[3].
Симплекс метод в порівнянні з графічним методом забезпечує більш раціональне рішення задачі. Розпочинаючи з будь-якої вершини багатокутника, твореного обмеженнями, переходять до розрахунку тільки тієї вершини, в якій значення лінійної форми буде більшим, чим в попередніх. Решту варіантів не обчислюють. Тоді при кінцевому числі кроків може бути найдений оптимальний план. Таким чином, виконується впорядкований перебір вершин, при яких відбувається постійне збільшення лінійної форми. Тому симплекс-метод також називають методом послідовного покращення оптимального плану. Рішення задачі симплекс-методом включає в себе два етапи. Спочатку потрібно найти вершину багатокутника обмежень, координати якої визначають початковий опорний план. Потім послідовно переходимо від однієї вершини багатокутника до іншої, яка сусідня попередній. Так як прилеглих вершин багато, то кожний раз вибирається така вершина, при переході до якої забезпечується найбільший приріст лінійної форми. На кожному кроці процесу покращення плану виконується перевірка на оптимальність. Очевидно, що план буде оптимальний, якщо серед вершин, які прилягають до даної, немає такої, при переході до якої відбувається ріст лінійної функції.
За звичай, симплекс-метод реалізується у вигляді симплекс-таблиць. У першому стовпчику цієї таблиці зазначають вектори, які входять в базис. У другому - коефіцієнти цільової функції, які відповідають векторам, що входять в базис. Третій стовпчик - компоненти опорного плану.
Головною перевагою симплекс-методу є його універсальність, будь-яку задачу лінійного програмування можна з легкістю вирішити як за допомогою програмного забезпечення так і вручну. Якщо обчислення і створення симплекс-таблиць пишеться вручну, то єдиною трудністю може стати обчислення: якщо велика кількість обмежень через неуважність можна отримати хибне рішення.
1.4 Двоїстий симплекс-метод
Двоїстий симплекс-метод і симплекс-метод за алгоритмом досить схожі. Однак двоїстий симплекс-метод можна застосовувати при рішенні задач лінійного програмування, вільні члени системи рівнянь якої можуть бути будь-якими числами (при рішенні задачі симплексним методом ці числа передбачалися ненегативними).
Нехай за умовою задачі потрібно визначити максимальне значення функції:
.(1.4.1)
Нехай
(1.4.2)
де - одиничні вектори.
Для того, щоб вирішити задачу двоїстим симплекс-методом потрібно виконати дві умови. Спочатку необхідно знайти так званий псевдо план задачі. Рішення системи лінійних рівнянь(1.4.2), приймаючи до уваги базис(одиничні вектори), називається псевдопланом задачі, якщо всі умови даної системи задоволені. Потім рішення зводиться до перевірки отриманого псевдоплану. Якщо він оптимальний, то отримане значення і є розвязком задачі. Якщо ж ні, то потрібно знову встановлювати псевдоплан. Після цього, вибирають рядок, що дозволяє, за допомогою визначення найбільшого по абсолютній величині негативного числа стовпця вектора і результуючого стовпчика, знаходження найменшого по абсолютній величині відношення елементів () і рядка до відповідного негативним елементам результуючого рядка. Знаходять новий псевдоплан і цикл розвязку задачі повторюється.
В порівнянні з методами, описаними раніше, двоїстий симплекс-метод дає змогу вирішувати задачі лінійного програмування, системи обмежень яких при позитивному базисі містять вільні члени будь-якого знаку. Цей метод дозволяє зменшити кількість перетворень системи обмежень, а також розміри симплексної таблиці.
1.5 Транспортна задача
В найпростішому варіанті транспортна задача формулюється наступним чином: є n постачальників із запасами однорідного штучного товару та m споживачів із потребами цього товару . Не порушуючи загальності, можна вважати транспортну задачу закритою, тобто, що сума всіх запасів дорівнює сумі всіх потреб, в противному разі задача є відкритою і простими відомими методами (введенням фіктивного постачальника чи фіктивного споживача) зводиться до закритої. Нехай матриця є матрицею цін перевезень, тобто кожен її елемент є ціною за перевезення одиниці продукції від i-го постачальника j-му споживачу, а матриця такої ж розмірності є планом перевезень, тобто кожне є цілим невідємним числом, що дорівнює кількості товару, що перевозиться від i-го постачальника j-му споживачу. Метою розвязку транспортної задачі є пошук такого плану перевезень Х, при якому загальна вартість перевезень була б найменшою з можливих за умови, що весь товар від постачальників перевозиться до споживачів. Транспортна задача є задачею цілочислового лінійного програмування. З основами лінійного програмування можна ознайомитись, з науковим обґрунтуванням алгоритмів розвязку задач лінійного програмування, зокрема транспортної задачі. Відзначимо лише, що по-перше, жоден з відомих алгоритмів не є досконалим, а по-друге, зажди пропонується шукати один оптимальний план перевезень, а решта оптимальних планів залишається або без уваги, або в кращому випадку залишається на розгляд методами після оптимізаційного аналізу. Досі було важко запропонувати достойну альтернативу цим методам через відсутність потужної обчислювальної техніки, але тепер це можливо[4].
Для сучасної ЕОМ не представляє ніяких складностей вирішення задач за допомогою даного методу, що можна сміливо віднести до першої переваги методу розвязку транспортної задачі. Навіть враховуючи те, що кількість варіантів дуже швидко ростиме зі збільшенням кількостей постачальників, споживачів, запасів та потреб, в багатьох випадках ЕОМ розвяже задачу цим методом швидше, ніж людина - іншим методом. Зазначимо, що описаний алгоритм підрахунку кількості можливих варіантів є водночас і алгоритмом власне перебору цих варіантів.
Другою перевагою цього методу є те, що в ході перебору легко отримати не один, а всі оптимальні плани перевезень , для яких досягається спільне мінімальне значення вартості перевезень, які в свою чергу, для зручності аналізу можна згрупувати по кількості відмінних елементів.
Третьою суттєвою перевагою цього методу є його прозорість (порівняно з іншими методами) та можливість легкого програмування. Єдиним недоліком цього методу є те, що при великих розмірах матриці та великих значеннях обсягів потреб та запасів час роботи програми може складати кілька годин, хоча і такий час може бути виправданий, коли мова йде про конкретну практичну задачу.
1.6 Вибір методу розвязку задачі
Так як симплекс-метод є універсальним, будь-яку задачу лінійного програмування можна з легкістю вирішити як за допомогою програмного забезпечення так і вручну, то для вирішення заданої задачі він підійде найкраще. За допомогою програми можна буде вирішувати велику кількість схожих задач.
2 Опис метода розвязку задачі
Нехай у задачі представлено n видів виробничої діяльності, інтенсивності використання котрих (шукані величини) складають . Для здійснення усіх видів виробничої діяльності є в наявності видів ресурсів, можливі обсяги споживання яких обмежені значеннями . Витрати і-го ресурсу на одиницю продукції j-го виду виробництва дорівнюють . Тому сума, яка являє собою загальний обсяг і-го ресурсу, що використовується n видами виробництва, не може перевищувати величини .
Структура цільової функції відбиває внесок кожного виду виробничої діяльності в загальний результат. У випадку максимізації величина являє собою прибуток від j-го виду виробничої діяльності на одиницю відповідної продукції, а у випадку мінімізації характеризує питомі витрати. Зауважимо, що «корисність» деякого виду виробничої діяльності не можна встановити тільки за значенням відповідного коефіцієнта цільової функції, оскільки обсяг споживання обмежених ресурсів також є важливим чинником. Оскільки усі види виробничої діяльності, подані в моделі, претендують на використання обмежених ресурсів, відносна корисність деякого виду виробництва (у порівнянні з іншими видами виробничої діяльності) залежить як від величини коефіцієнта цільової функції , так і від інтенсивності споживання ресурсів . Тому можлива ситуація, коли через занадто великі витрати обмежених ресурсів деякий j-й вид виробничої діяльності, що характеризується високим прибутком, використовувати недоцільно (тобто в оптимальному розвязку відповідна змінна виявиться небазисною).
В основі симплекс-методу є процес побудови початкової симплекс-таблиці, та перехід від однієї симплекс-таблиці до наступної згідно певних правил. Такі переходи виконуються доти, доки не буде виконано критерій оптимальності або не стане зрозумілим, що розвязку не існує. Перехід від однієї симплекс-таблиці до наступної здійснюється наступним чином. Згідно певних критеріїв вибирається провідний елемент таблиці (bk,l), який стоїть на перетині рядка, який виводиться з базису, та стовпчика, який буде введено до базису. Елементи таблиці перераховуються так:
. (2.
)
Очевидним чином дану формулу можна спростити до наступної:
. (2.2)
тобто всі елементи нової таблиці матимуть вигляд ai,j / x, де х - провідний елемент попередньої таблиці (зауваження: якщо дроби можна скоротити, то цього НЕ слід робити для правильності подальших міркувань).
Нехай тепер маємо симплекс-таблицю, що складається з цілих чисел (тобто коефіцієнти рівнянь цілі чи раціональні, що зводяться до цілих). Після першого кроку перетворень отримується така таблиця (провідний елемент дорівнює х):
Таблиця 2.1 - Симплекс-таблиця
|
ј |
ј |
|||
|
ј |
a/x |
b/x |
ј |
|
|
ј |
c/x |
d/x |
ј |
|
|
ј |
ј |
Нехай на другому кроці провідним буде елемент d/x. Тоді елемент a/x перераховується за загальним правилом:
(2.3)
причому легко переконатися, що чисельник (ad-bc)/x буде цілим числом.
Отже, після другого кроку всі елементи знову мають загальний вигляд зі спільним знаменником, що дорівнює чисельнику провідного елемента попередньої таблиці. А в наступній таблиці чисельники будуть знову скорочуватись на цей знаменник і будуть цілими.
Якщо більш розгорнуто записати декілька переходів від однієї таблиці до іншої, то можна помітити, що числа у чисельниках та знаменниках є мінорами різних порядків, які складені з елементів початкової таблиці. Позначимо через мінор, що складений з елементів перетину рядків зі стовпцями початкової таблиці. Сама таблиця матиме вигляд:
Таблиця 2.2 - Симплекс-таблиця
|
A11 |
A21 |
... |
An1 |
|
|
A12 |
A22 |
... |
An2 |
|
|
... |
... |
... |
... |
|
|
A1m |
A2m |
... |
Anm |
Процес переходу від попередньої таблиці до наступної взагалі спрощується: достатньо дописати номер рядка та стовпчика провідного елемента до всіх мінорів таблиці, що стоять у чисельниках, крім елементів того ж рядка, та до всіх мінорів знаменників (в початковій таблиці знаменник рівний одиниці).
Але слід звернути увагу на такий випадок: якщо провідний елемент опинився у тому ж рядку, що і раніше введений елемент, то “більш застарілий” слід викинути з мінору, а новий загальним чином дописати в кінець списку рядків та стовпчиків мінору відповідно. Звідси випливає, що рядки в мінорі не можуть повторюватись, тобто їх не може бути більше, ніж рівнянь обмежень, і мінори не будуть нескінченно розростатись. Але може зустрітися випадок, коли в списку стовпців, з яких складається мінор, зустрінуться однакові стовпці, тобто мінор рівний нулю. Це якраз відповідає нульовим елементам таблиці на відповідному кроці і вписується в загальне правило.
За допомогою даного методу можна набагато точніше обчислювати розвязки задач лінійного програмування без накопичування похибки (при використанні компютера), яка виникає при діленні. Цього можна досягти, якщо зберігати чисельники окремо, а знаменники взагалі завжди однакові.
3 Розробка моделі розвязку задачі
За умовою задачі необхідно знайти оптимальний варіант розподілу бюджету на різний вид реклами, завдяки якому він в результаті дав би найбільшій прибуток фірмі.
Для розрахунку здачі введемо деякі позначення:
- витрати бюджету фірми на телерекламу;
- витрати на рекламу по радіо;
- витрати на рекламу у газетах.
В результаті потрібно отримати прибуток, тому цільова функція буде максимізуватися. Завдяки досвіду минулих років, відомо, який прибуток буде отриманий фірмою, при витраті одного долара на різні види реклами, тому можна записати цільову функцію, вона матиме наступний вигляд:
(3.1)
За умовою задачі витрати не повинні перевищувати 10000, тому можемо записати перше обмеження:
(3.2)
Витрати на теле- та радіорекламу не повинна перевищувати шістдесят відсотків бюджетних коштів, тому можна записати друге обмеження:
(3.3)
За умовою витрати на газетну рекламу не повинні перевищувати більш як удвічі витрати на радіо рекламу:
(3.4)
Обовязково потрібно врахувати наступні нерівності, адже вони суттєво вплинуть на розвязок задачі:
(3.5)
Оскільки дана задача буде розвязуватись симплекс методом, приведемо модель до вигляду, який буде зручним для використання симплекс методу. Всі вище записані обмеження обєднаємо до системи і отримаємо:
(3.6)
Для того, щоб розвязати задачу симплекс-методом необхідно систему обмежень, яка містить нерівності, перетворити до системи рівнянь. Для цього введемо додаткові змінні . При використанні симплекс методу, цільова функція повинна мінімізуватися, для цього помножимо її на -1 та додамо додаткові змінні з відповідними коефіцієнтами. Тоді функція мети перетвориться до наступного вигляду:
(3.7)
Розвязок цієї моделі наведений у розділі тестування даної курсової роботи.
4 Розробка програмного забезпечення
В даному розділі розглянемо логічний опис та структуру програми, вхідні та вихідні дані, зробимо аналіз отриманих результатів.
4.1 Призначення програми
Дана програма призначена для розвязку задач лінійного програмування за допомогою симплекс методу. Вона дозволяє отримати швидкий розвязок задачі за умови введення коректних даних та виконання умов використання програми. Програма виконує розвязок задачі, обмеження якої задаються системою рівнянь. Можна розвязувати задачі з різною кількістю змінних і знаходити як мінімум так і максимум функції мети.
4.2 Вибір середовища програмування
Microsoft Office є єдиним пакетом, встановленим на більшості компютерів. Excel -- це організатор будь-якого типа даних, будь вони числовими, текстовими або якими-небудь ще. Оскільки в цій програмі є багато вбудованих обчислювальних можливостей, більшість людей звертаються до Excel, коли потрібно створити таблиці для фінансових розрахунків, працювати із статистичними даними. За допомогою даної програми можна зробити свої звіти професіональнішими і виконати додаткове фінансування за допомогою красивих ділових презентацій. За допомогою даного пакету можна створювати різноманітні графіки і діаграми для більш наочного представлення результатів.
Excel -- це великий охоронець списків (хоча їх прийнято називати в Excel базами даних) і творець таблиць. Тому Excel як не можна краще підходить для відстежування інформації про товари, що продаються, про обслуговуваних клієнтів, про службовців, яких контролює будь-яка організація і т.д.
Кожна одиниця інформації (імя, адреса, число продажів в місяць і ін.) займає свою власну клітинку в створюваній робочій таблиці. У кожній робочій таблиці 256 стовпців (з яких в новій робочій таблиці на екрані видно, як правило, тільки перші 10 або 11 (від А до J) і 65 536 рядків (з яких зазвичай видні тільки перші 15-20). Кожна нова робоча книга містить три чистих листа робочої таблиці.
Вся інформація, що поміщається в електронну таблицю, зберігається в окремих клітинках робочої таблиці. Але ввести інформацію можна тільки в поточну клітинку. За допомогою адреси в рядку формул і табличний курсор Excel вказує, який з 16 мільйонів клітинок робочої таблиці є поточним.
Excel є чудовим інструментом для виконання розрахунків по формулах, а також для зберігання інформації у вигляді списків і таблиць. Це дає можливість набагато спростити роботу із статистичними даними, які розраховуються по складних формулах. В програмі закладені багато груп формул, в тому числі і статистичні, або користувач сам може записати формулу.
Тому можна зробити висновок, що даний програмний пакет найкраще підходить для розвязку задач лінійного програмування.
4.3 Опис вхідних та вихідних даних
Дана програма написана в Excel. В ній задаються обмеження і значення цільової функції, які можна змінювати. Потім програма проводить розрахунки і в клітинках, яким попередньо були присвоєнні спеціальні імена, записує розвязок функції мети і значення змінних, при яких цей оптимальний розвязок був отриманий. Розглянемо всі введення даних детальніше.
Вхідними даними для даної задачі є виражені з обмежень значення кожної змінної та вираз для обчислення цільової функції. Значення змінних вводяться в поле «Ограничения» в меню інструменту Пошук розвязку. Вираз значення цільової функції вводиться в комірку робочого аркуша.
Вихідними даними є значення кожної змінної та максимальне значення цільової функції, які будуть записані у визначених клітинках робочої таблиці.
4.4 Розробка структури програми
Щоб отримати розвязок задачі лінійного програмування за допомогою 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, що вирішує задачу симплекс-методом та виводить результат.
Програму можна використовувати для розрахунку різних видів оптимізації і не тільки витрат, а інших коштів, що проходять через будь-яку організацію.
Література
1. http://www.kgtu.runnet.ru/WD/TUTOR/lp/lp01.html#$lp01.1;
2. http://semenets.by.ru/public/graphic.html;
3. http://dl.sumdu.edu.ua/e-pub/mo/rus/m_simpl.html;
4. http://www.kgtu.runnet.ru/WD/TUTOR/lp/lp05.html;
5. http://dl.sumdu.edu.ua/e-pub/mo/rus/m_excel.html - Приклад розвязку задач лінійного програмування в Excel;
6. Гавриленко В., Пархоменко Л., "Решение задач аппроксимации средствами MS EXCEL", "Компьютеры+программы", №12/2002р., с.42.http://imcs.dvgu.ru/lib/nurmi/finmath/node42.html.
| ! | Как писать курсовую работу Практические советы по написанию семестровых и курсовых работ. |
| ! | Схема написания курсовой Из каких частей состоит курсовик. С чего начать и как правильно закончить работу. |
| ! | Формулировка проблемы Описываем цель курсовой, что анализируем, разрабатываем, какого результата хотим добиться. |
| ! | План курсовой работы Нумерованным списком описывается порядок и структура будующей работы. |
| ! | Введение курсовой работы Что пишется в введении, какой объем вводной части? |
| ! | Задачи курсовой работы Правильно начинать любую работу с постановки задач, описания того что необходимо сделать. |
| ! | Источники информации Какими источниками следует пользоваться. Почему не стоит доверять бесплатно скачанным работа. |
| ! | Заключение курсовой работы Подведение итогов проведенных мероприятий, достигнута ли цель, решена ли проблема. |
| ! | Оригинальность текстов Каким образом можно повысить оригинальность текстов чтобы пройти проверку антиплагиатом. |
| ! | Оформление курсовика Требования и методические рекомендации по оформлению работы по ГОСТ. |
| → | Разновидности курсовых Какие курсовые бывают в чем их особенности и принципиальные отличия. |
| → | Отличие курсового проекта от работы Чем принципиально отличается по структуре и подходу разработка курсового проекта. |
| → | Типичные недостатки На что чаще всего обращают внимание преподаватели и какие ошибки допускают студенты. |
| → | Защита курсовой работы Как подготовиться к защите курсовой работы и как ее провести. |
| → | Доклад на защиту Как подготовить доклад чтобы он был не скучным, интересным и информативным для преподавателя. |
| → | Оценка курсовой работы Каким образом преподаватели оценивают качества подготовленного курсовика. |
| Курсовая работа | Деятельность Движения Харе Кришна в свете трансформационных процессов современности |
| Курсовая работа | Маркетинговая деятельность предприятия (на примере ООО СФ "Контакт Плюс") |
| Курсовая работа | Политический маркетинг |
| Курсовая работа | Создание и внедрение мембранного аппарата |
| Курсовая работа | Социальные услуги |
| Курсовая работа | Педагогические условия нравственного воспитания младших школьников |
| Курсовая работа | Деятельность социального педагога по решению проблемы злоупотребления алкоголем среди школьников |
| Курсовая работа | Карибский кризис |
| Курсовая работа | Сахарный диабет |
| Курсовая работа | Разработка оптимизированных систем аспирации процессов переработки и дробления руд в цехе среднего и мелкого дробления Стойленского ГОКа |