ЛP№1_Симплекс-метод окон

ЗАДАЧА ЛІНІЙНОГО ПРОГРАМУВАННЯ
ЗЛП є задачею знаходження найбільшого (чи найменшого) значення лінійної функції.
Лінійне програмування - це напрям математичного програмування, що вивчає методи рішення екстремальних завдань, які характеризуються лінійною залежністю між змінними і лінійним критерієм.
F = c1x1 + c2x2 + … + cnxn → max / min
За умови, що змінні x1,x2 … xn задовольняють систему лінійних обмежень
a11x1 + a12x2 + … + a1nxn {≤, ≥, =} b1
a21x1 + a22x2 + … + a2nxn {≤, ≥, =} b2
…..
am1x1 + am2x2 + … + amnxn {≤, ≥, =} bm .

Симплекс-метод — це поетапна обчислювальна процедура, в основу якої покладено принцип послідовного поліпшення значень цільової функції переходом від одного опорного плану задачі лінійного програмування до іншого. Він є універсальним методом, який дозволяє вирішувати ЗЛП з будь-якою кількістю змінних.
алгоритм симплекс-методу дає можливість розв'язувати ЗЛП незалежно від геометричного образу області допустимих розв'язків.
метод визначає початкове опорне рішення, яке задовольняє систему обмежень, але не є оптимальним;
вказує напрямок переходу до наступного рішення, яке покращує значення цільової функції.
Симплекс-метод

Алгоритм розв'язування задачі лінійного програмування симплекс-методом складається з таких етапів:
Визначення початкового опорного плану задачі лінійного програмування.
Побудова симплексної таблиці.
Перевірка опорного плану на оптимальність за допомогою оцінок. Якщо всі оцінки задовольняють умову оптимальності, то визначений опорний план є оптимальним планом задачі. Якщо хоча б одна з оцінок не задовольняє умову оптимальності, то переходять до нового опорного плану або встановлюють, що оптимального плану задачі не існує.
Перехід до нового опорного плану задачі виконується визначенням розв'язувального елемента та розрахунком нової симплексної таблиці.
Повторення дій починаючи з 3-го пункту.
АЛГОРИТМ Симплекс-методу

* вважати, що 1 мілілітр = 1 грам
Визначити:
1) скільки філіжанок кожного виду кави необхідно продавати щодня, щоб місячний дохід був максимальний;
2) суму місячного доходу BUNKER coffee house від продажу кави, якщо відомо, що у звітний період було 22 робочі дні, а кількість проданих філіжанок не змінюється в залежності від дня тижня.
3) рекомендації щодо покращення роботи закладу.
Умова задачі

РОЗВ’ЯЗАННЯ ЗАДАЧІ

F = 12x1 + 13x2 + 18x3 + 0x4 + 0x5 + 0x6 + 0x7 → max
в останньому рядку симплекс-таблиці є від'ємні елементи

шукаємо розв'язуючий стовпчик – стовпчик x3
додаємо стовпчик «Симплекс-відношення» та розраховуємо його значення

шукаємо розв'язуючий рядок – x5
шукаємо розв'язуючий елемент – x53
Виводимо з базису x5 , а вводимо – x3
Оскільки в останньому стовпці є кілька мінімальних елементів 100, то номер рядка вибираємо за правилом Креко.

Елементи рядків, що мають однакові найменші значення (у нашому випадку min=100) , поділяються на передбачувані роздільники, а результати заносяться в додаткові рядки. За провідний рядок вибирається той, у якому раніше зустрінеться найменше приватне під час читання таблиці зліва направо стовпцями.
Отже, при діленні 100 на 150 буде меньше часне, чим при діленні 100 на 50.
Правило Креко

в стовпчик «Базис» вводимо нову базисну змінну x3 , зберігаючи порядок змінних
в комірках на перетині базисних змінних ставимо 1, в інших комірках відповідних стовпчиків – 0
усі елементи розв'язуючого рядка ділимо на розв'язуючий елемент
інші елементи розраховуємо за правилом прямокутника

Уявно малюємо прямокутник, одна вершина якого збігається з розв'язуючим елементом, інша - з елементом, образ якого ми шукаємо. Дві інші вершини визначаються однозначно.
Тоді елемент у новій таблиці буде дорівнює відповідному елементу попередньої таблиці мінус дріб, в знаменнику якої знаходиться розв'язуючий елемент, а в чисельнику - добуток елементів з двох невикористаних вершин прямокутника.
Треба перерахувати елемент
Елемент
Елемент
Роздільний елемент
Правило прямокутника

Заповнюємо другу симплексну таблицю:
X41 = 10 – 50*10/150 = 6,6 X71 = 5 – 50*10/150 = 1,6
X42 = 10 – 1500/150 = 0 X61 = 0 – 50*50/150 = -16,6
X62 = 0 – 50*150/150 = -50 X72 = 10 – 1500/150 = 0
X45 = 0 – 10*1/150 = -1/15=-0,0667 X65 = 0 – 50*1/150 = -1/3 = -0,3
X75 = 0 – 10*1/150 = -1/15 = -0,0667 X4вч = 3000 – 150000/150 = 2000
X6вч = 5000 – 15000*50/150 = 0 X7вч = 20000 – 15000*10/150 = 19000
-12 – 50*(-18)/150 = -6 -13 – 150 *(-18)/150 = 5
0 – 0*(-18)/150 = 0,12
Не є оптимальним рішенням, з тої причини що в останньому рядку є від’ємне значення. Умови оптимальності не виконані

Використовуємо той самий алгоритм, та шукаємо нові симплекс-відношення
2000/20/3 = 3/10 = 300
100/(50/150)=3/10=300
19000/(5/3)=57/5=11400

Заповнюємо третю симплексну таблицю:
X32 = 10=1
X62 = (-50) – 0 = -50
X34 = 0 – 1*(50/150)/(20/3) = -1.20
X64 = 0 - 1*(-50/3)/(20/3) = -5/2
X74 = 0 – 1*(5/3) )/(20/3) = -1/4
X35 = 1/150 - (-1/15)*(50/150)/(20/3) = 1/100
X65 = (-1/3) – (-50/3)*(-1/15) )/(20/3)= -1/2
X75 = (-1/15)-5/3*(-1/15) )/(20/3) = -1/12 = 0,083
0 – 1*(-6)/(20/3) = 0,9
(3/25) – (-6)*(-1/15) )/(20/3) = 0,06
X3вч = 0,1 – 2*(50/150) )/(20/3) = 0
X6вч = 0 – (-50/3)*2)/(20/3) = 5
Х7вч = 19 – (5/3)*2)/(20/3) = 37/2 = 18,5
Умова оптимальності виконана:
в останньому рядку симплекс-таблиці усі елементи невід'ємні.

Отже, маємо таке оптимальне рішення:

У оптимальний план увійшла додаткова змінна x6. Отже, під час реалізації такого плану є недовикористані ресурси 3-го виду у кількості 5кг.
Молоко не рекомендуется використовувати
У оптимальний план увійшла додаткова змінна x7. Отже, під час реалізації такого плану є недовикористані ресурси 4-го виду у кількості 181/2.
Використано 20-18,5 = 1,5 кг цукру
Значення 300 у стовпці x1 означає, що
Кава використана майже повністю, у залишку 300 грам
Значення змінних х2 и х5 равных 0 свідчать про те, що вода була використана повністю.
Аналіз оптимального плану

Вхідні дані
Опорний план
Розрахунок оптимального плану
Задача вироджена
(нема рішень)
Оптимальный план знайдено
Вивід на екран
Значення задані в програмі
Короткий алгоритм програми

Результат роботи
програми
1
4
2
1
2
3
Перша симплексна таблиця
Друга симплексна таблиця
Третя симплексна таблиця
3
4
Максимальне значення

РЕКОМЕНДАЦІЇ
За даними умовами та обмеженнями максимальний виторг на день буде складати 3600 грн, та 79200 на місяць. Використовувати рекомендується з наявних ресурсів тільки каву та воду. Все інше з метою збільшення прибутку використовувати не рекомендується.
Щоб досягти максимального прибутку, рекомендується продавати виключно еспресо, в кількості 300 чашок на день, з урахуванням наявних обмежень у ресурсах. За таких умов прибуток буде 3600 грн. на день, що буде максимально можливим показником. З метою приведення до рентабельності надання інших послуг рекомендується значно підвищити вартість.
Також, якщо збільшити кількість води на 1,5 літри, можна підвищити щоденний виторг на 10% (360 грн), за наявності таких саме обсягів кави, та коштовності. Відповідно місячний виторг зросте до 87120 грн (+7920 грн).

При виконанні даної лабораторної роботи, основна мета поставленого завдання була досягнута.
Було вивчено базові завдання лінійного програмування, розраховано симплекс-таблиці та проаналізовано отриманий результат.
Також було написано програму, яка автоматизує вирішення задачі лінійного програмування симплекс-методом.
ВИСНОВОК