нкції, на невідомі якої накладені лінійні обмеження. Таким чином, завдання лінійного програмування відносяться до завдань на умовний екстремум функції.
1.3 Основне завдання лінійного програмування
В
Основне завдання лінійного програмування (ОЗЛП) ставиться таким чином: Є ряд змінних. Потрібно знайти такі їх невід'ємні значення, які задовольняли б системі лінійних рівнянь:
В {1.1}
p> і, крім того, звертали б у мінімум лінійну цільову функцію (ЦФ)
В
Очевидно, випадок, коли ЦФ потрібно звернути не в мінімум, а в максимум, легко зводиться до попередньому, якщо змінити знак функції і розглянути замість неї функцію
В
Припустимим рішенням ОЗЛП називають будь-яку сукупність змінних, задовольняє рівнянням (1.1). p> Оптимальним рішенням називають те з допустимих рішень, при якому ЦФ звертається в мінімум. p> На практиці обмеження в задачі лінійного програмування часто задано не рівняннями, а нерівностями. У цьому випадку можна перейти до основному завданню лінійного програмування. p> Розглянемо задачу лінійного програмування з обмеженнями-нерівностями, які мають вигляд
{1.2}
і є лінійно-незалежними. Останнє означає, ніяке з них не можна уявити у вигляді лінійної комбінації інших. Потрібно знайти, які задовольняють неравенствам і звертають в мінімум
p> Введемо рівняння:
{1.3}
де - додаткові змінні, які також як і є невід'ємними. p> Таким чином, маємо спільну задачу лінійного програмування - знайти невід'ємні, щоб вони задовольняли системі рівнянь (1.3) і звертали в мінімум.
Коефіцієнти у формулі (1.3) перед дорівнюють нулю.
2. ГРАФИЧЕСКИЙ МЕТОД ВИРІШЕННЯ ЗАВДАННЯ лінійного програмування
В
2.1. Теоретичне введення
Графічний метод досить простий і наочний для вирішення завдань лінійного програмування з двома змінними. Він заснований на геометричному поданні допустимих рішень і ЦФ завдання.
Кожне з нерівностей задачі лінійного програмування (1.2) визначає на координатної площині деяку напівплощина (рис.2.1), а система нерівностей в цілому - перетин відповідних площин. Безліч точок перетину даних півплощин називається областю допустимих рішень (ОДР). ОДР завжди являє собою опуклу фігуру, тобто володіє наступною властивістю: якщо дві точки А і В належать цій фігурі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлена опуклим багатокутником, необмеженою опуклою багатокутної областю, відрізком, променем, однією точкою. У разі несумісності системи обмежень задачі (1.2) ОДР є порожнім безліччю.
Всі вищесказане відноситься і до випадку, коли система обмежень (1.2) включає рівності, оскільки будь-яке рівність
В
можна представити у вигляді системи двох нерівностей (див. рис.2.1)
В
ЦФ при фіксованому значенні визначає на площині пряму лінію. Змінюючи значення L, ми отримаємо сімейство паралельних прямих, званих лініями рівня .
Це пов'язано з тим, що зміна значення L спричинить зміну лише довжини відрізка, відсікається лінією рівня на осі (початкова ордината), а кутовий коефіцієнт прямий залишиться постійним (см.ріс.2.1). Тому для вирішення буде досить побудувати одну з ліній рівня, довільно вибравши значення L.
ВекторВ з координатами з коефіцієнтів ЦФ при та перпендикулярний до кожної з ліній рівня (див. рис.2.1). Напрямок вектора збігається з напрямком зростання ЦФ, що є важливим моментом для вирішення завдань. Напрямок убування ЦФ протилежно напрямку вектора. p> Суть графічного методу полягає в наступному. У напрямку (проти напрямку) вектора в ОДР проводиться пошук оптимальної точки. Оптимальною вважається точка, через яку проходить лінія рівня, відповідна найбільшому (найменшому) значенню функції. Оптимальне рішення завжди знаходиться на кордоні ОДР, наприклад, в останній вершині багатокутника ОДР, через яку пройде цільова пряма, або на всій його боці.
При пошуку оптимального вирішення завдань лінійного програмування можливі такі ситуації: існує єдине рішення задачі; існує нескінченна безліч рішень (альтернативний оптіум); ЦФ не обмежена; область допустимих рішень - єдина точка; задача не має рішень.
В
Малюнок 2.1 Геометрична інтерпретація обмежень і ЦФ завдання. b>
2.2. Методика рішення задач ЛП графічним методом.
I. У обмеженнях задачі (1.2) замінити знаки нерівностей знаками точних рівностей і побудувати відповідні прямі.
II. Знайти і заштрихувати напівплощині, дозволені кожним з обмежень-нерівностей завдання (1.2). Для цього потрібно підставити в конкретне нерівність координати якої точки [наприклад, (0, 0)], і перевірити істинність отриманого нерівності.
Якщо нерівність істинне,
то...
