Розв’язання задач лінійного програмування
Міністерство освіти та науки України
Вінницький національний технічний університет
Інститут автоматики та комп’ютерних систем управління
Факультет автоматики та комп’ютерних систем управління
Розв’язання задач лінійного програмування(А)
Пояснювальна записка
з дисципліни «Математичне програмування та дослідження операцій»
до курсової роботи за спеціальністю
«Системи управління та автоматики»
08-01.МПДО.342.00.000-ПЗ
Вінниця, ВНТУ 2007
Анотація
В даній курсові роботі розглянуто методи розв’язку задач лінійного програмування. Такі задачі досить поширені у повсякденному житті. Тому в даній роботі розглянуто рішення на окремій задачі, а також розглянуто як їх можна розв’язувати вручну і за допомогою спеціального програмного продукту.
Було розроблено математичну модель і програмне забезпечення. Дана задача вирішується симплекс методом, тому досліджується основний принцип метода, особливості і переваги в порівнянні з іншими методами.
Зміст
Вступ
1 Опис існуючих методів розв’язку задач лінійного програмування
1.1 Постановка задачі
1.2 Графічний метод
1.3 Симплекс-метод
1.4 Двоїстий симплекс метод
1.5 Транспортна задача
1.6 Вибір методу розв’язку задачі
2 Опис метода розв’язку задачі
3 Розробка моделі розв’язку задачі
4 Розробка програмного забезпечення
4.1 Призначення програми
4.2 Вибір середовища програмування
4.3 Опис вхідних та вихідних даних
4.4 Розробка структури програми
4.5 Розробка схеми алгоритму
4.6 Розробка тестів
4.7 Аналіз результатів тестування
4.8 Інструкція користувачеві
Висновки
Література
Додаток А.
Технічне завдання
Вступ
В даний час лінійне програмування є одним з найбільш популярних апаратів математичної теорії оптимального управління рішень, у тому числі і у фінансовій математиці. Для вирішення завдань лінійного програмування розроблено складне програмне забезпечення, що дає можливість ефективно і надійно вирішувати практичні завдання великих об'ємів. Ці програми і системи забезпечені розвиненими системами підготовки початкових даних, засобами їх аналізу і представленням отриманих результатів. У розвиток і вдосконалення цих систем вкладена праця і талант багатьох математиків, досвід вирішення тисяч завдань. Знання системи лінійного програмування необхідні кожному спеціалісту в області прикладної математики.
У класичній математиці методи пошуку оптимальних рішень розглядають у розділах класичної математики, зв'язаних з вивченням екстремумів функцій, у математичному програмуванні.
Існує багато розділів в математичному програмуванні, серед них лінійне і нелінійне програмування, опукле і квадратичне, і багато інших. Але всі вони зводяться до отримання оптимального рішення у великій кількості задач різних промислових і виробничих гілках суспільства. Розглянемо лінійне програмування та визначимо основні принципи і алгоритми даного розділу математичного програмування.
Лінійне програмування є найбільш часто використовуваним методом оптимізації. До завдань лінійного програмування можна віднести:
раціональне використання сировини і матеріалів;
завдання оптимального розкрою;
-оптимізації виробничої програми підприємств;
-оптимального розміщення і концентрації виробництва;
-складання оптимального плану перевезень, роботи транспорту;
-управління виробничими запасами і ін.
Для великої кількості практично цікавих завдань цільова функція виражається лінійно – через характеристики плану, причому допустимі значення параметрів підпорядковані лінійній рівності або нерівностям. Знаходження за даних умов абсолютного екстремуму цільової функції носить назву лінійного програмування.
Першим дослідженням по лінійному програмуванню є робота Л. В. Кантфовіча “Математичні методи організації і планування виробництва”, яке було опубліковане в 1939 р. У ньому розміщена постановка завдань лінійного програмування, розроблений метод результуючих множників вирішення завдань лінійного програмування і дано його теоретичне обґрунтування.
Головна мета лінійного програмування є математичне формулювання проблеми складання такого плану використання різних способів виробництва, який дозволяє отримати максимальну кількість однорідного продукту при ресурсах, що є в наявності.
1 Опис існуючих методів розв’язку задач лінійного програмування
Лінійне програмування розв’язує велику кількість задач з різними типами обмежень. Тому їх можна розв’язати різними методами. Розглянемо їх принцип.
Постановка задачі
Методи лінійного програмування - чисельні методи вирішення оптимізаційних задач, що зводяться до формальних моделей лінійного програмування[1].
Як відомо, будь-яке завдання лінійного програмування може бути приведене до канонічної моделі мінімізації лінійної цільової функції з лінійними обмеженнями типу рівності. Оскільки число змінних в завданні лінійного програмування більше числа обмежень (), то можна отримати рішення, прирівнявши нулю () змінних, які називаються вільними. Решта m змінних, які називаються базисними, можна легко визначити з системи обмежень звичайними методами лінійної алгебри. Якщо рішення існує, то воно називається базисним. Якщо задача лінійного програмування має оптимальні рішення, то хоча б один із них є базисним.
Приведені міркування означають, що при пошуку оптимального рішення задачі лінійного програмування досить обмежитися перебором базисних допустимих рішень. Те, що не всі базисні рішення є допустимими, істотно проблеми не міняє, оскільки щоб оцінити допустимість базисного рішення, його необхідно отримати.
В загальному постановка задачі має вигляд:
Нехай маємо деякі змінні і функцію цих змінних, яка називається цільовою функцією. Потрібно найти екстремум (максимум чи мінімум) цільової функціїпри умові,що змінні належать деякій області :
(1.1.1)
В залежності від виду функції і області G розрізняють розділи математичного програмування: квадратичне програмування, випукле і ін.
Лінійне програмування характеризується тим, що функція і лінійною функцією змінних і область G визначається системою лінійних рівнянь чи нерівностей.
Графічний метод
Якщо модель містить тільки дві змінні, задачу можна розв’язати графічно. У випадку трьох змінних графічний розв’язок стає менш наочним, а при більшому числі змінних - взагалі неможливим. Незважаючи на це, розгляд графічного методу дасть змогу зробити висновки, що послужать основою для розробки загального методу розв’язання задач лінійного програмування[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 Вибір методу розв’язку задачі
Так як симплекс-метод є універсальним, будь-яку задачу лінійного програмування можна з легкістю вирішити як за допомогою програмного забезпечення так і вручну, то для вирішення заданої задачі він підійде найкраще. За допомогою програми можна буде вирішувати велику кількість схожих задач.
Опис метода розв’язку задачі
Нехай у задачі представлено 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.1)
За умовою задачі витрати не повинні перевищувати 10000, тому можемо записати перше обмеження:
(3.2)
Витрати на теле- та радіорекламу не повинна перевищувати шістдесят відсотків бюджетних коштів, тому можна записати друге обмеження:
(3.3)
За умовою витрати на газетну рекламу не повинні перевищувати більш як удвічі витрати на радіо рекламу:
(3.4)
Обов’язково потрібно врахувати наступні нерівності, адже вони суттєво вплинуть на розв’язок задачі:
(3.5)
Оскільки дана задача буде розв'язуватись симплекс методом, приведемо модель до вигляду, який буде зручним для використання симплекс методу. Всі вище записані обмеження об’єднаємо до системи і отримаємо:
(3.6)
Для того, щоб розв’язати задачу симплекс-методом необхідно систему обмежень, яка містить нерівності, перетворити до системи рівнянь. Для цього введемо додаткові змінні . При використанні симплекс методу, цільова функція повинна мінімізуватися, для цього помножимо її на -1 та додамо додаткові змінні з відповідними коефіцієнтами. Тоді функція мети перетвориться до наступного вигляду:
(3.7)
Розв'язок цієї моделі наведений у розділі тестування даної курсової роботи.
Розробка програмного забезпечення
В даному розділі розглянемо логічний опис та структуру програми, вхідні та вихідні дані, зробимо аналіз отриманих результатів.
Призначення програми
Дана програма призначена для розв’язку задач лінійного програмування за допомогою симплекс методу. Вона дозволяє отримати швидкий розв’язок задачі за умови введення коректних даних та виконання умов використання програми. Програма виконує розв’язок задачі, обмеження якої задаються системою рівнянь. Можна розв’язувати задачі з різною кількістю змінних і знаходити як мінімум так і