Лінійне програмування графічний онлайн. Симплексний метод розв'язання задач лінійного програмування. Графічний метод розв'язання задач ЛП

Графічний метод досить простий і наочний на вирішення завдань ЛП із двома змінними. Він заснований на геометричномуподанні допустимих рішень та ЦФ задачі.

Кожна з нерівностей завдання ЛП визначає на координатній площині (х 1 ,х 2 ) деяку полуплоскость (рис. 1), а система нерівностей загалом - перетин відповідних площин. Безліч точок перетину даних напівплощин називається областю допустимихрішень(ОДР). ОДР завжди є опуклуфігуру, тобто. яка має наступну властивість: якщо дві точки А і В належать цій фігурі, то і весь відрізок АВ належить їй. ОДР графічно може бути представлена ​​опуклим багатокутником, необмеженою опуклою багатокутною областю, відрізком, променем, однією точкою. У разі несумісності системи обмежень завдання ОДР є пустою множиною.

Примітка № 1. Все вищесказане відноситься і до випадку, коли система обмежень (1.1) включає рівності, оскільки будь-яка рівність

a il x 1 +a i 2 x 2 =b

можна у вигляді системи двох нерівностей (рис. 1)

A i 2 x 2<Ь 1э +a i 2 x 2 >bj.

ЦФ L(x)= с1х1 + с2х2 при фіксованому значенні L(х)=L визначає на площині пряму лінію с1х1 + с2х2 = L. Змінюючи значення L, ми отримаємо сімейство паралельних прямих, званих лініями рівня.

Це пов'язано з тим, що зміна значення L спричинить зміну лише довжини відрізка, що відсікається лінією рівня на осі х2 (початкова ордината), а кутовий коефіцієнт прямої tgа = - залишиться постійним (рис. 1).

Тому для вирішення достатньо побудувати одну з ліній рівня, довільно обравши значення L.

Вектор C = (c1; c2) з координатами з коефіцієнтів ЦФ при х1 і х2 перпендикулярний до кожної лінії рівня (див. рис. 1). Напрямоквектора З збігаєтьсяз напрямком зростанняЦФ, що є важливим моментом для вирішення задач. Напрямок спаданняЦФ протилежнонапрямку вектора С.

Суть графічного методу ось у чому. У напрямку (проти напрямку) вектора С в ОДР проводиться пошук оптимальної точки X = (х1; х2 ). Оптимальною вважається точка, якою проходить лінія рівня L max (L min), що відповідає найбільшому (найменшому) значенню функції L(x). Оптимальне рішення завжди знаходиться на межі ОДР, наприклад, в останній вершині багатокутника ОДР, якою пройде цільова пряма, або на всій його стороні.

При пошуку оптимального розв'язання задач ЛП можливі такі: існує єдине рішення задачі; існує безліч рішень (альтернативний оптіум);ЦФ не обмежена; область допустимих рішень – єдина точка; Завдання немає рішень.

Допустима область - напівплощина

Малюнок 1

1.2. Методика вирішення задач лп графічним методом

I. У обмеженнях завдання замініть знаки нерівностей на знаки точних рівностей та побудуйте відповідні прямі.

ІІ. Знайдіть і заштрихуйте напівплощини, дозволені кожним з обмежень-нерівностей завдання. Для цього підставте в конкретну нерівність координати будь-якої точки [наприклад, (0;0)], та перевірте істинність отриманої нерівності.

Якщонерівність істинна, то треба заштрихувати напівплощину, що містить цю точку; інакше (Нерівність хибне) треба заштрихувати напівплощину, що не містить дану точку.

Оскільки х1 і х2 повинні бути неотрицательными, їх допустимі значення завжди будуть перебувати вище осі х 1 і правіше осі х2, тобто. у 1-му квадранті.

Обмеження-рівності дозволяють лише ті точки, які лежать на відповідній прямій, тому виділіть на графіку такі прямі.

Визначте ОДР як частину площини, що належить одночасно всім дозволеним областям, та виділіть її. За відсутності ОДР завдання не має рішень, про що зробіть відповідний висновок.

Якщо ОДР - не пусте безліч, то побудуйте цільову пряму, тобто. будь-яку з ліній рівня з 1 х 1 + з 2 х 2 = L де L - довільне число, наприклад, кратне з 1 і з 2, тобто. зручне щодо розрахунків. Спосіб побудови аналогічний до побудови прямих обмежень.

V. Побудуйте вектор C = (c 1, з 2), який починається в точці (0; 0), закінчується в точці (c 1, з 2). Якщо цільова пряма та вектор С побудовані правильно, то вони будуть перпендикулярні.

VI. При пошуку max ЦФ пересувайте цільову пряму в напрямку вектора С при пошуку min ЦФ - проти спрямування вектор С. Останняпо ходу руху вершина ГДР буде точкою max або min ЦФ. Якщо такої точки (точок) не існує, то зробіть висновок необмеженості ЦФ на безлічі планів зверху (під час пошуку шах) чи знизу (під час пошуку min).

Визначте координати точки max(min) ЦФ X = (х1*; х2* ) та обчисліть значення ЦФ l(x *). Для обчислення координат оптимальної точки X * розв'яжіть систему рівнянь прямих, на перетині яких знаходиться X * .

Завдання 1

Знайдемо оптимальне вирішення задачі, математична модель якої має вигляд

L(Х) = 3x1 + 2x2 → max

х 1 + 2х 2< 6, (1)

2х 1 + х 2< 8, (2)

Х 1 + х 2<1, (3)

х 2< 2, (4)

х 1 >0,х 2 >0.

Побудуємо прямі обмеження, для чого обчислимо координати точок перетину цих прямих з осями координат (рис. 2).

х 1 + 2х 2 = 6, (1)

2х1+х2 = 8, (2)

(1) х1 = 0, х1 = 6, х2 = 3, х2 = 0,

(2) х1 = 0, х1 = 4, х2 = 8, х2 = 0,

(3) х1 = 0, х1 = -1, х2 = 1, х2 = 0,

Пряма (4) проходить через точку х 2 = 2 паралельно до осі L(Х).

Рис. 2. Графічне розв'язання задачі

Визначимо ОДР. Наприклад, підставимо точку (0;0) у вихідне обмеження (3), отримаємо 0< 1, что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, міститьточку (0; 0), тобто. розташовану правіше і нижче прямої (3). Аналогічно визначимо допустимі напівплощини для інших обмежень та вкажемо їх стрілками у відповідних прямих обмежень (рис. 2). Спільною областю, дозволеної усіма обмеженнями, тобто. ОДР є багатокутник ABCDEF.

Цільову пряму можна побудувати за рівнянням

Будуємо вектор З точки (0;0) в точку (3;2). Точка Е-це остання вершина багатокутника допустимих рішень ABCDEF, через яку проходить цільова пряма, рухаючись у напрямку вектора З. Тому Е-це точка максимуму ЦФ. Визначимо координати точки Е із системи рівнянь прямих обмежень (1) та (2)

Х1+2х2=6, (1) х1=10/3=3 1/3, х2=4/3=1 1/3

2 Х1 + х 2 = 8, (2) Е 3 1/3; 1 1/3

Максимальне значення ЦФ дорівнює L(E) = 3*10/3+2*4/3 = 12 2/3

Розглянемо спочатку найпростіший випадок, коли в ЗЛП включені рівно дві змінні:

Кожна з нерівностей (a)-(b) системи обмежень задачі (3.8) геометрично визначає напівплощину відповідно до граничних прямих , Х 1 =0 і Х 2 =0. Кожна з граничних прямих поділяє площину х 1 Ох 2 на дві півплощини. Усі рішення вихідної нерівності лежать у одній з освічених полуплоскостей (всі точки полуплоскости) і, отже, при підстановці координат будь-якої її точки відповідне нерівність звертає їх у правильне тотожність. З огляду на це і визначається та полуплоскость, у якій лежать розв'язання нерівності, тобто. шляхом вибору будь-якої точки з будь-якої напівплощини та підстановки її координат у відповідну нерівність. Якщо нерівність виконується для цієї точки, воно виконується і для будь-якої іншої точки з цієї ж напівплощини. В іншому випадку розв'язання нерівності лежать в іншій напівплощині.

У разі, якщо система нерівностей (a)-(b) спільна, то область її розв'язків є безліч точок, що належать усім зазначеним полуплоскостям. Оскільки безліч точок перетину даних напівплощин випукло, то область допустимих розв'язків задачі (3.8) є опукла безліч, яка називається багатокутником розв'язків (введений раніше термін "багатогранник розв'язків" зазвичай вживається, якщо n 3). Сторони цього багатокутника лежать на прямих, рівняння яких виходять вихідної системиобмежень заміною знаків нерівностей на знаки точної рівності.

Таким чином, вихідна ЗЛП полягає у знаходженні такої точки багатокутника рішень, в якій цільова функція F набуває максимального (мінімального) значення.

Ця точка існує тоді, коли багатокутник розв'язків не порожній і на ньому цільова функція обмежена зверху. За зазначених умов однієї з вершин багатокутника рішень цільова функція набуває максимального значення. Для визначення даної вершини будують лінію рівня L: c 1 x 1 +c 2 x 2 =h (де h - деяка постійна), перпендикулярну вектору-градієнту і проходить через багатокутник рішень, і пересувають її паралельно вздовж вектора-градієнта доти, поки вона не пройде через останню її загальну точку перетину з багатокутником рішень (при побудові вектора-градієнта відкладають точку (з 1; з 2) у площині х 1 Ох 2 і проводять до неї з початку координат спрямований відрізок). Координати зазначеної точки визначають оптимальний план даного завдання.

Підсумовуючи вищевикладене, наведемо алгоритм графічного методу рішення ЗЛП.

Алгоритм графічного методу розв'язання ЗЛП

1. Побудувати багатокутник рішень, що задається системою обмежень вихідної ЗЛП.

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

3. Обчислити координати знайденої оптимальної точки, розв'язавши систему рівнянь двох граничних прямих, що перетинаються в ній.

4. Підстановкою знайденого оптимального рішення на цільову функцію завдання обчислити оптимальне її значення, тобто: .

При графічному побудові безлічі допустимих рішень ЗЛП (багатокутника розв'язків) можливі такі ситуації.

Розглянуто розв'язання задач лінійного програмування графічним методом. Опис методу. Приклади розв'язання задач.

Див. також: Розв'язання задач симплекс методом

Опис методу

Якщо задачі лінійного програмування є лише дві змінні, її можна вирішити графічним методом.

Розглянемо задачу лінійного програмування з двома змінними та :
(1.1) ;
(1.2)
Тут є довільні числа. Завдання можливе як на знаходження максимуму (max), так і на знаходження мінімуму (min). У системі обмежень можуть бути як знаки, і знаки.

Побудова області допустимих рішень

Графічний метод розв'язання задачі (1) наступний.
Спочатку ми проводимо осі координат і вибираємо масштаб. Кожна з нерівностей системи обмежень (1.2) визначає напівплощину, обмежену відповідною прямою.

Так, перша нерівність
(1.2.1)
визначає напівплощину, обмежену прямою . З одного боку від цієї прямої, з другого боку. На самій прямій. Щоб дізнатися, з якого боку виконується нерівність (1.2.1), ми вибираємо довільну точку, що не лежить на прямій. Далі підставляємо координати цієї точки (1.2.1). Якщо нерівність виконується, то напівплощина містить вибрану точку. Якщо нерівність не виконується, напівплощина розташована з іншого боку (не містить обрану точку). Заштриховуємо напівплощину, на яку виконується нерівність (1.2.1).

Те саме виконуємо для інших нерівностей системи (1.2). Так ми отримаємо заштрихованих напівплощин. Точки області допустимих рішень задовольняють всі нерівності (1.2). Тому, графічно, область допустимих рішень (ОДР) є перетином всіх побудованих напівплощин. Заштриховуємо ОДР. Вона є опуклим багатокутником, грані якого належать побудованим прямим. Також ОДР може бути необмеженою опуклою фігурою, відрізком, променем або прямою.

Може виникнути і такий випадок, що напівплощини не містять спільних точок. Тоді областю допустимих рішень є безліч. Таке завдання рішень немає.

Можна спростити метод. Можна не заштриховувати кожну напівплощину, а спочатку збудувати всі прямі
(2)
Далі вибрати довільну точку, що не належить жодній із цих прямих. Підставити координати цієї точки у систему нерівностей (1.2). Якщо всі нерівності виконуються, то область допустимих рішень обмежена побудованими прямими і включає обрану точку. Заштриховуємо область допустимих рішень за межами прямих так, щоб воно включало обрану точку.

Якщо хоча б одна нерівність не виконується, то вибираємо іншу точку. І так далі, доки не буде знайдено одну точку, координати якої задовольняють системі (1.2).

Знаходження екстремуму цільової функції

Отже, маємо заштриховану область допустимих рішень (ОДР). Вона обмежена ламаною, що складається з відрізків та променів, що належать побудованим прямим (2). ОДР завжди є опуклим безліччю. Воно може бути як обмеженою безліччю, так і не обмеженою вздовж деяких напрямків.

Тепер ми можемо шукати екстремум цільової функції
(1.1) .

Для цього вибираємо будь-яке число та будуємо пряму
(3) .
Для зручності подальшого викладу вважаємо, що ця пряма проходить через ОДР. На цій прямій цільова функція постійна і рівна. така пряма називається лінією рівня функції. Ця пряма розбиває площину на дві півплощини. На одній півплощині
.
На іншій півплощині
.
Тобто з одного боку від прямої (3) цільова функція зростає. І що далі ми відсунемо крапку від прямої (3), то більше буде значення . З іншого боку від прямої (3) цільова функція зменшується. І що далі ми відсунемо точку від прямої (3) в інший бік, то менше буде значення . Якщо ми проведемо пряму, паралельну до прямої (3), то нова пряма також буде лінією рівня цільової функції, але з іншим значенням .

Таким чином, щоб знайти максимальне значення цільової функції, треба провести пряму, паралельну прямій (3), максимально віддалену від неї у бік зростання значень і проходить хоча б через одну точку ОДР. Щоб знайти мінімальне значення цільової функції, треба провести пряму, паралельну прямій (3) і максимально віддалену від неї у бік зменшення значень , і проходить хоча б через одну точку ОДР.

Якщо ОДР необмежена, може виникнути випадок, коли таку пряму провести не можна. Тобто як би ми не видаляли пряму від лінії рівня (3) у бік зростання (зменшення), то пряма завжди проходитиме через ОДР. В цьому випадку може бути як завгодно великим (малим). Тому максимального (мінімального) значення немає. Завдання рішень немає.

Розглянемо випадок, коли крайня пряма, паралельна довільному прямому виду (3), проходить через одну вершину багатокутника ОДР. З графіка визначаємо координати цієї вершини. Тоді максимальне (мінімальне) значення цільової функції визначається за такою формулою:
.
Розв'язанням задачі є
.

Також може зустрітися випадок, коли пряма паралельна до однієї з граней ОДР. Тоді пряма проходить через дві вершини багатокутника ОДР. Визначаємо координати цих вершин. Для визначення максимального (мінімального) значення цільової функції можна використовувати координати будь-якої з цих вершин:
.
Завдання має безліч рішень. Рішенням є будь-яка точка, розташована на відрізку між точками та , включаючи самі точки та .

Приклад розв'язання задачі лінійного програмування графічним методом

Фірма випускає сукні двох моделей А та В. При цьому використовується тканина трьох видів. На виготовлення однієї сукні моделі А потрібно 2 м тканини першого виду, 1 м тканини другого виду, 2 м тканини третього виду. На виготовлення однієї сукні моделі потрібно 3 м тканини першого виду, 1 м тканини другого виду, 2 м тканини третього виду. Запаси тканини першого виду становлять 21 м, другого виду – 10 м, третього виду – 16 м. Випуск одного виробу типу А приносить дохід 400 ден. од., одного виробу типу В – 300 ден. од.

Скласти план виробництва, що забезпечує фірмі максимальний дохід. Завдання вирішити графічним способом.

Нехай змінні та означають кількість вироблених суконь моделей А та В відповідно. Тоді кількість витраченої тканини першого виду становитиме:
(м)
Кількість витраченої тканини другого виду становитиме:
(м)
Кількість витраченої тканини третього виду складе:
(м)
Оскільки вироблена кількість суконь не може бути негативною, то
та .
Дохід від вироблених суконь складе:
(Ден. од.)

Тоді економіко-математична модель завдання має вигляд:

Вирішуємо графічним способом.
Проводимо осі координат і .

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 7) та (10,5; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 10) та (10; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 8) та (8; 0).

Заштриховуємо область, щоб крапка (2; 2) потрапила до заштрихованої частини. Отримуємо чотирикутник OABC.

(П1.1) .
При .
При .
Проводимо пряму через точки (0; 4) та (3; 0).

Далі помічаємо, що оскільки коефіцієнти при цільової функції позитивні (400 і 300), то вона зростає при збільшенні і . Проводимо пряму, паралельну до прямої (П1.1), максимально віддалену від неї у бік зростання , і проходить хоча б через одну точку чотирикутника OABC. Така пряма проходить через точку C. З побудови визначаємо її координати.
.

Рішення завдання: ;

.
Тобто для отримання найбільшого доходу необхідно виготовити 8 суконь моделі А. Дохід при цьому складе 3200 ден. од.

Приклад 2

Розв'язати задачу лінійного програмування графічним методом.

Вирішуємо графічним способом.
Проводимо осі координат і .

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 6) та (6; 0).

Будуємо пряму.
Звідси.
При .
При .
Проводимо пряму через точки (3; 0) та (7; 2).

Будуємо пряму.
Будуємо пряму (вісь абсцис).

Область допустимих рішень (ОДР) обмежена побудованими прямими. Щоб дізнатися, з якого боку, зауважуємо, що точка належить ОДР, оскільки задовольняє системі нерівностей:

Заштриховуємо область за межами побудованих прямих, щоб крапка (4; 1) потрапила до заштрихованої частини. Отримуємо трикутник ABC.

Будуємо довільну лінію рівня цільової функції, наприклад,
.
При .
При .
Проводимо пряму лінію рівня через точки (0; 6) та (4; 0).
Оскільки цільова функція збільшується при збільшенні , то проводимо пряму, паралельну лінії рівня і максимально віддалену від неї у бік зростання , і проходить хоча б через одну точку трикутника АВС. Така пряма проходить через точку C. З побудови визначаємо її координати.
.

Рішення завдання: ;

Приклад відсутності рішення

Розв'язати графічно завдання лінійного програмування. Знайти максимальне та мінімальне значення цільової функції.

Розв'язуємо задачу графічним методом.
Проводимо осі координат і .

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 8) та (2,667; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (0; 3) та (6; 0).

Будуємо пряму.
При .
При .
Проводимо пряму через точки (3; 0) та (6; 3).

Прямі є осями координат.

Область допустимих рішень (ОДР) обмежена побудованими прямими та осями координат. Щоб дізнатися, з якого боку, зауважуємо, що точка належить ОДР, оскільки задовольняє системі нерівностей:

Заштриховуємо область, щоб крапка (3; 3) потрапила до заштрихованої частини. Отримуємо необмежену область, обмежену ламаною ABCDE.

Будуємо довільну лінію рівня цільової функції, наприклад,
(П3.1) .
При .
При .
Проводимо пряму через точки (0; 7) та (7; 0).
Оскільки коефіцієнти при позитивні, то зростає при збільшенні і .

Щоб знайти максимум, потрібно провести паралельну пряму, максимально віддалену у бік зростання і проходить хоча б через одну точку області ABCDE. Однак, оскільки область необмежена з боку великих значень та , то таку пряму провести не можна. Яку б пряму ми провели, завжди знайдуться точки області, більш віддалені убік збільшення і . Тому максимуму немає. можна зробити як завгодно великий.

Шукаємо мінімум. Проводимо пряму, паралельну прямій (П3.1) і максимально віддалену від неї у бік зменшення, і проходить хоча б через одну точку області ABCDE. Така пряма проходить через точку C. З побудови визначаємо її координати.
.
Мінімальне значення цільової функції:

Максимального значення немає.
Мінімальне значення
.

Найбільш простим та наочним методом вирішення задачі лінійного програмування (ЗЛП) є графічний метод. Він заснований на геометричній інтерпретації задачі лінійного програмування та застосовується при вирішенні ЗЛП із двома невідомими:

Розглянемо розв'язання цього завдання на площині. Кожна нерівність системи функціональних обмежень геометрично визначає напівплощину з граничною прямою а пх, + + a j2 х 2 = b n i = 1, т.е.Умови невід'ємності визначають напівплощини з граничними прямими х (= 0, х 2= 0 відповідно. Якщо система спільна, то напівплощини, перетинаючи, утворюють загальну частину, яка є опуклим безліччю і є сукупністю точок; координати кожної з цих точок є розв'язком цієї системи. Сукупність цих точок називають багатокутником розв'язків.Він може бути точкою, відрізком, променем, обмеженим та необмеженим багатокутником.

Геометрично ЗЛП є відшукання такої кутової точки багатокутника рішень, координати якої доставляють максимальне (мінімальне) значення лінійної цільової функції,причому допустимими рішеннями є всі точки багатокутника розв'язків.

Лінійне рівняння описує безліч точок, що лежать на одній прямій. Лінійна нерівність визначає деяку область на площині.

Визначимо, яку частину площини визначає нерівність 2х (+ Зх 2 12.

По-перше, побудуємо пряму 2х, + Зх 2 = 12. Вона проходить через точки (6; 0) та (0; 4). По-друге, визначимо, яка напівплощина задовольняє нерівність. Для цього вибираємо будь-яку точку на графіку, що не належить прямої, і підставляємо її координати в нерівність. Якщо нерівність виконуватиметься, то дана точкає допустимим рішенням і напівплощина, що містить точку, задовольняє нерівності. Для підстановки у нерівність зручно використовувати початок координат. Підставимо х ( = х 2 = 0 у нерівність 2х, + Зх 2 12. Отримаємо 2 0 + 3 0

Аналогічно графічно можна зобразити всі обмеження задачі лінійного програмування.

Рішенням кожної нерівності системи обмежень ЗЛП є напівплощина, що містить граничну пряму і розташована з одного боку від неї. Перетин напівплощин, кожна з яких визначається відповідною нерівністю системи, називається областю допустимих рішень(ОДР) або областю визначення.

Необхідно пам'ятати, що область допустимих рішень задовольняє умовам негативності (Xj > 0, j = 1, д).Координати будь-якої точки, що належить області визначення, є допустимим розв'язанням задачі.

Для знаходження екстремального значення цільової функції при графічному рішенні ЗЛП використовують вектор-градієнт,координати якого є приватними похідними цільової функції:

Цей вектор показує напрямок якнайшвидшої зміни цільової функції. Пряма c [ x l + с 2 х 2 = f(x 0),перпендикулярна вектору-градієнту, є лінією рівняцільової функції (рис. 2.2.2). У будь-якій точці лінії рівня цільова функція набуває одного і того ж значення. Прирівняємо цільову функцію постійної величини а.Змінюючи значення а,отримаємо сімейство паралельних прямих, кожна з яких є лінією рівня цільової функції.

Рис. 2.2.2.

Важлива властивість лінії рівня лінійної функції полягає в тому, що при паралельному зміщенні лінії в один бік рівень лише зростає,а при зміщенні в інший бік - тільки зменшується.

Графічний метод вирішення ЗЛП складається з чотирьох етапів:

• 1. Будується область допустимих рішень (ОДР) ЗЛП.
• 2. Будується вектор-градієнт цільової функції (ЦФ) із початком у точці х 0(0; 0): V = (с, з 2).
• 3. Лінія рівня CjXj+ з 2 х 2 = а (а -постійна величина) - пряма, перпендикулярна вектору-градієнту V, - пересувається у напрямку вектора-градієнта у разі максимізації цільової функції f(x v х 2)доти, доки залишить меж ОДР. При мінімізації /(*, х 2)лінія рівня переміщується у напрямку, протилежному вектору-градієнту. Крайня точка (або точки) ОДР при цьому русі є точкою максимуму (мінімуму) f(x p jc 2).

Якщо пряма, відповідна лінії рівня, при своєму русі не залишає ОДР, то мінімум (максимум) функції f(xр х 2) немає.

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

4. Визначаються координати точки максимуму (мінімуму). Для цього достатньо вирішити систему рівнянь прямих, що дають у перетині точку максимуму (мінімуму). Значення f(x ( , х 2),знайдене в отриманій точці є максимальним (мінімальним) значенням цільової функції.

Можливі ситуації графічного рішення ЗЛП представлені у табл. 2.2.1.

Таблиця 2.2.1

Приклад 2.2.1. Планування випуску продукції пошиття підприємства (завдання про костюми).

Намічається випуск двох видів костюмів - чоловічих та жіночих. На жіночий костюм потрібен 1 м вовни, 2 м лавсану і 1 людина день трудовитрат; на чоловічий - 3,5 м вовни, 0,5 м лавсану і 1 людина день трудовитрат. Усього є 350 м вовни, 240 м лавсану і 150 человекодней трудовитрат.

Потрібно визначити, скільки костюмів кожного виду необхідно пошити, щоб забезпечити максимальний прибуток, якщо прибуток від жіночого костюма становить 10 ден. од., як від чоловічого - 20 ден. од. При цьому слід мати на увазі, що необхідно пошити не менше 60 чоловічих костюмів.

Економіко-математична модель задачі

Змінні: х, - кількість жіночих костюмів; х 2 -кількість чоловічих костюмів.

Цільова функція:

Обмеження:

Перше обмеження (вовна) має вигляд х (+ 3,5 х 2 х ( + 3,5 х 2 = 350 проходить через точки (350; 0) і (0; 100). Друге обмеження (по лавсану) має вигляд 2х (+ 0,5 х 2 2х х + 0,5 х 2 = 240 проходить через точки (120; 0) та (0; 480). Третє обмеження (по праці) має вигляд х у +х 2150. Пряма х (+ х 2 = 150 проходить через точки (150; 0) та (0; 150). Четверте обмеження (за кількістю чоловічих костюмів) має вигляд х 2> 60. Вирішенням цієї нерівності є напівплощина, що лежить вище за пряму х 2 = 60.

В результаті перетину побудованих чотирьох напівплощин отримуємо багатокутник, який і є областю допустимих рішень нашого завдання. Будь-яка точка цього багатокутника задовольняє всі чотири функціональні нерівності, а для будь-якої точки поза цим багатокутником хоча б одна нерівність буде порушена.

На рис. 2.2.3 затінена область допустимих рішень (ОДР). Для визначення напрямку руху до оптимуму збудуємо вектор-градієнт V, координати якого є приватними похідними цільової функції:

Щоб побудувати такий вектор, потрібно з'єднати точку (10; 20) із початком координат. Для зручності можна будувати вектор, пропорційний вектору V. Так, на рис. 2.2.3 зображено вектор (30; 60).

Потім побудуємо лінію рівня 10xj + 20х2 = а.Прирівняємо цільову функцію постійної величини а.Змінюючи значення а, отримаємо сімейство паралельних прямих, кожна з яких є лінією рівня цільової функції:

Далі пересуватимемо лінію рівня до її виходу з ОДР. У нашому випадку (при максимізації цільової функції) рух лінії рівня здійснюватимемо у напрямку градієнта. У крайній кутовій точці досягається максимум цільової функції. Для знаходження координат цієї точки розв'язуємо систему із двох рівнянь прямих, що дають у перетині точку максимуму:

Отримуємо При цих значеннях

Відповідь. Для отримання максимального прибутку (2300) необхідно пошити 70 жіночих (xj 1 = 70) та 80 чоловічих (х 2 = 80) костюмів.

Рис. 2.2.3. Крапка (70; 80) - оптимальне рішення задачі Приклад 2.2.2. Знайти максимум та мінімум f(X):

при обмеженнях

Рішення. При вирішенні даного прикладуна максимум виникає ситуація, коли лінія рівня Зх + 3 х 2 = апаралельна першому обмеженню: х х +х 2 8. Цільова функція досягає максимального значення у двох точках: А(3; 5) та В(6; 2) - та приймає на відрізку АВодне й те саме значення, що дорівнює 24:

При вирішенні цього прикладу на мінімум цільової функції лінію рівня 3xj + 3 х 2 - аслід рухати у напрямку, зворотному напрямку вектора-градієнта. Цільова функція досягає мінімального значення у точці D (0,5; 0):

Графічне рішення прикладу наведено на рис. 2.2.4.

Рис. 2.2.4.

Відповідь: max /(2Q = 24; min /( X)= 1,5. Приклад 2.2.3. Знайти максимум / ( X):

при обмеженнях

Рішення. Завдання немає рішення, оскільки ЦФ не обмежена зверху на ОДР (рис. 2.2.5).

У лінійному програмуванні використовується графічний метод, за допомогою якого визначають опуклі множини (багатогранник рішень). Якщо основне завдання лінійного програмування має оптимальний план, то цільова функція набуває значення однієї з вершин багатогранника рішень (див. малюнок).

Призначення сервісу. За допомогою даного сервісуможна в онлайн режимівирішити задачу лінійного програмування геометричним методом, і навіть отримати рішення двоїстої завдання (оцінити оптимальність використання ресурсів). Додатково створюється шаблон рішення в Excel.

Інструкція. Виберіть кількість рядків (кількість обмежень). Якщо кількість змінних більше двох, необхідно систему привести до СЗЛП (див. приклад №2). Якщо обмеження подвійне, наприклад, 1 ≤ x 1 ≤ 4 , воно розбивається на два: x 1 ≥ 1 , x 1 ≤ 4 (тобто кількість рядків збільшується на 1).
Побудувати область допустимого рішення(ОДР) можна також за допомогою цього сервісу.

Разом з цим калькулятором також використовують такі:
Симплексний метод вирішення ЗЛП

Розв'язання транспортного завдання
Рішення матричної гри
За допомогою сервісу в онлайн режимі можна визначити ціну матричної гри (нижню та верхню межі), перевірити наявність сідлової точки, знайти рішення змішаної стратегії методами: мінімакс, симплекс-метод, графічний (геометричний) метод, методом Брауна.
Екстремум функції двох змінних
Обчислення меж

Розв'язання задачі лінійного програмування графічним методом включає наступні етапи:

1. На площині X10X2 будують прямі.
2. Визначаються напівплощини.
3. Визначають багатокутник розв'язків;
4. Будують вектор N(c 1 ,c 2), який вказує напрямок цільової функції;
5. Пересувають пряму цільову функцію c 1 x 2 + c 2 x 2= 0 у напрямку вектора N до крайньої точки багатокутника розв'язків.
6. Обчислюють координати точки та значення цільової функції у цій точці.

Приклад. Компанія виготовляє два види продукції - П1 та П2. Для виробництва використовуються два види сировини - С1 та С2. Оптові ціни одиниці виробленої продукції дорівнює: 5 д.е. для П1 і 4 д.о. для П2. Витрата сировини на одиницю продукції виду П1 та виду П2 дано в таблиці.
Таблиця - Витрата сировини виробництва продукції

1. Сформулювати математичну модель задачі лінійного програмування.
2. Розв'язати задачу лінійного програмування графічним способом(Для двох змінних).

Обмеження ресурсів
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6

Обмеження щодо попиту
x 1 +1 ≥ x 2
x 2 ≤ 2

Цільова функція
5x 1 + 4x 2 → max

Тоді отримуємо наступну ЗЛП:
6x 1 + 4x 2 ≤ 24
x 1 + 2x 2 ≤ 6
x 2 - x 1 ≤ 1
x 2 ≤ 2
x 1 , x 2 ≥ 0
5x 1 + 4x 2 → max

Якщо кількість змінних задачі лінійного програмування більше двох, то завдання попередньо зводять до стандартної ЗЛП .
→ max при обмеженнях:
x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x1+2x2+x5=10
F(X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Перехід до СЗЛП.

Особливості розв'язання задач лінійного програмування графічним методом

f=x 1 +13x 2 -x 3 +2x 4 +3x 5
-x 2 +x 3 -x 5 =-3
x 1 -4x 2 +3x 3 -x 4 +2x 5 =3
4x 2 -x 3 +x 4 -x 5 =6

З першого рівняння виражаємо x 5:
x 5 = -x 2 +x 3 +3

f=x 1 +13x 2 -x 3 +2x 4 +3(-x 2 +x 3 +3)
x 1 -4x 2 +3x 3 -x 4 +2(-x 2 +x 3 +3)=3
4x 2 -x 3 +x 4 -(-x 2 +x 3 +3)=6
або
f=x 1 +10x 2 +2x 3 +2x 4 +9
x 1 -6x 2 +5x 3 -x 4 =-3
5x 2 -2x 3 +x 4 =9

З другого рівняння виражаємо х 4:
x 4 = 9-5x2 +2x3
і підставимо в усі вирази:
f=x 1 +6x 3 +27
x 1 -x 2 +3x 3 = 6

Змінну x 2 приймаємо як додаткову змінну і робимо заміну на знак «≥»:
f=x 1 + 6x 3 + 27
x 1 + 3x 3 ≥6

Приклад №2

x 1 + x 2 + x 3 = 12
2x 1 - x 2 + x 4 = 8
- 2x1+2x2+x5=10
F(X) = 3x 1 - 2x 2 + 5x 3 - 4x 5
Перехід до СЗЛП.
Розширена матриця системи обмежень-рівностей даного завдання:

Приклад №3. Скласти математичну модель задачі лінійного програмування та знайти рішення геометричним способом.

• Скласти систему математичних залежностей (нерівностей) та цільову функцію.
• Зобразити геометричну інтерпретацію задачі.
• Знайти оптимальне рішення.
• Провести аналітичну перевірку.
• Визначити суттєві та несуттєві ресурси та їх надлишки.
• Визначити значення цільової функції.
• Обчислити об'єктивно обумовлені оцінки.
• Скласти співвідношення стійкості.