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

Микола Кузнєцов керує невеликим механічним заводом. Наступного місяця він планує виготовляти два продукти (А і В), за якими питомий маржинальний прибуток оцінюється в 2500 і 3500 руб. відповідно.

Виготовлення обох продуктів вимагає витрат на машинну обробку, сировину та працю. На виготовлення кожної одиниці продукту А відводиться 3 години машинної обробки, 16 одиниць сировини та 6 одиниць праці. Відповідні вимоги до одиниці продукту складають 10, 4 і 6. Микола прогнозує, що наступного місяця він може надати 330 годин машинної обробки, 400 одиниць сировини і 240 одиниць праці. Технологія виробничого процесу така, що не менше 12 одиниць продукту необхідно виготовляти в кожен конкретний місяць.

Микола хоче побудувати модель для того, щоб визначити кількість одиниць продуктів А і В, які він повинен виробляти наступного місяця для максимізації маржинального прибутку.

Рішення задачі

Етап 1. Визначення змінних

Існує цільова змінна (позначимо її Z), яку необхідно оптимізувати, тобто максимізувати чи мінімізувати (наприклад, прибуток, виторг чи витрати). Микола прагне максимізувати маржинальний прибуток, отже, цільова змінна:

Z - це сумарний маржинальний прибуток (у рублях), отриманий наступного місяця в результаті виробництва продуктів А і Ст.

Існує ряд невідомих шуканих змінних (позначимо їх х 1 , х 2 , х 3 та ін), чиї значення необхідно визначити для отримання оптимальної величини цільової функції, яка, у нашому випадку є сумарним маржинальним прибутком. Цей маржинальний прибуток залежить від кількості вироблених продуктів А і В. Значення цих величин необхідно розрахувати, і тому вони є шуканими змінними в моделі. Отже, позначимо:

х 1 - кількість одиниць продукту А, вироблених наступного місяця.

х 2 - кількість одиниць продукту, вироблених наступного місяця.

Дуже важливо чітко визначити усі змінні величини; особливу увагу приділіть одиницям виміру та періоду часу, до якого відносяться змінні.

Етап. 2. Побудова цільової функції

Цільова функція - це лінійне рівняння, яке має бути або максимізовано або мінімізовано. Воно містить цільову змінну, виражену за допомогою змінних, тобто Z виражену через х 1 , х 2 ... у вигляді лінійного рівняння.

У нашому прикладі кожен виготовлений продукт А приносить 2500 руб. маржинального прибутку, а при виготовленні х 1 одиниць продукту А, маржинальний прибуток складе 2500х1. Аналогічно маржинальний прибуток від виготовлення х 2 одиниць продукту складе 3500х 2 . Таким чином, сумарний маржинальний прибуток, отриманий наступного місяця за рахунок виробництва х 1 одиниць продукту А і х 2 одиниць продукту, тобто, цільова змінна Z складе: Z = 2500х 1 +3500х 2 .

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

Етап. 3. Визначення обмежень

Обмеження – це система лінійних рівнянь та/або нерівностей, які обмежують величини змінних, що шукаються. Вони математично відбивають доступність ресурсів, технологічні чинники, умови маркетингу та інші вимоги. Обмеження може бути трьох видів: «менше чи одно», «більше чи одно», «строго одно».

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

Виготовлення кожної одиниці продукту вимагає 10 годин і, отже, якщо вироблено х 2 продуктів, то потрібно 10х 2 годин. Таким чином, загальний обсяг машинного часу, необхідного для виробництва х 1 одиниць продукту А і х 2 одиниць продукту, становить 3х 1 +10х 2 . Це загальне значення машинного часу не може перевищувати 330 годин. Математично це записується так:

3х 1+10х2 ≤330

Аналогічні міркування застосовуються до сировини та праці, що дозволяє записати ще два обмеження:

16х 1 +4х 2 ≤400

6х 1 +6х 2 ≤240

Нарешті слід зазначити, що існує умова, згідно з якою має бути виготовлено не менше 12 одиниць продукту:

Етап. 4. Запис умов невід'ємності

Перемінні, що шукаються, не можуть бути негативними числами, що необхідно записати у вигляді нерівностей х 1 ≥0 і х 2 ≥0. У прикладі друге умови є надлишковим, оскільки вище було визначено, що х 2 може бути менше 12.

\[\left\( (\begin(array)()
(3(x_1) + 10(x_2) \le 330)\\
(16(x_1) + 4(x_2) \le 400)\\
(6(x_1) + 6(x_2) \le 240)\\
((x_1) \ge 0)\\
((x_2) \ge 12)
\end(array)) \right.\]

Рішення симплекс-методом

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

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

Алгорим симплексного методу можна описати так:

1. Привести завдання до канонічного вигляду
2. Знайти невід'ємне базисне рішення системи обмежень
3. Розрахувати оцінки вільних змінних за формулою:

\[(\Delta)_j = \sum\limits_(i = 1)^r ((c_i)(h_(ij)) – (c_j)) ,\;j = \overline (1,n) ,\]

де h ij - Коефіцієнти при вільній змінній x j ,

c i – коефіцієнти при базисних змінних цільової функції,

c j - коефіцієнти при вільній змінній в цільовій функції,

1. Перевірити знайдене опорне рішення на оптимальність:

а) якщо всі оцінки \((\Delta)_j \ge 0\) , то знайдене рішення оптимальне і завдання вирішено;

б) якщо хоча б одна оцінка \((\Delta)_j< 0\) , а при соответствующей переменной x j нет ни одного положительного коэффициента, то задача не имеет оптимального рішеннячерез обмеженість цільової функції

в) якщо хоча б одна оцінка \((\Delta)_j< 0\) , а при соответствующей переменной x j есть хотя бы один положительный коэффициент, то решение не оптимально и его можно улучшить переходом к новому базису. Если отрицательных оценок несколько,то в базис ввести переменную с наибольшей по абсолютной величине отрицательной оценкой.

Наведемо завдання до канонічному вигляду.

Повна модель лінійного програмування для виробничого завдання Миколи може бути записана у вигляді:

\[\left\( (\begin(array)()
(3(x_1) + 10(x_2) + (x_3) = 330)\\
(16(x_1) + 4(x_2) + (x_4) = 400)\\
(6(x_1) + 6(x_2) + (x_5) = 240)\\
(-(x_2) +(x_6) = 12)\\
((x_j) \ge 0\;j = \overline (1,n))
\end(array)) \right.\]

\[\bar(x)_(\text(опор))=(0;0;330;400;20;12)\]

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

Це рішенняне оптимально, оскільки в нижньому рядку є негативні значення. Оскільки є позитивні коефіцієнти, рішення можна поліпшити, для цього введемо змінну в базис x 2 . Так як у колонці x 2 є кілька позитивних коефіцієнтів, то визначаємо відношення вільного члена b i до відповідних коефіцієнтів у цій колонці та вибираємо найменший результат.

Перетворимо таблицю та повторимо розрахунок.

Дане рішення не оптимальне, оскільки в нижньому рядку є негативні значення. Оскільки є позитивні коефіцієнти, рішення можна поліпшити, для цього введемо змінну в базис x 1 .

Отримане рішення (10; 30) оптимальне.

Рішення за допомогою Excel та LibreOffice

Рішення в Excel здійснюється за допомогою надбудови "Пошук рішення", що також використовує симплекс-метод.

Аналогічно цю задачу можна вирішити за допомогою Решателя в LibreOffice. Слід зазначити, що в LibreOffice немає обмежень на кількість змінних, на відміну від Excel.

Рішення у R

Для вирішення завдань лінійного програмування в GNU R можна використовувати такі пакети:

• lpSolve
• linprog

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

Рішення з пакетом lpSolve

Результат

Таким чином, максимальне значення цільової функції дорівнює 130000 і воно досягається при х 1 і х 2 рівними, відповідно: 10 і 30.

Рішення з пакетом linprog

Оскільки пакет linprogє доповненням до попереднього пакету, то змінні вже всі ініціалізовані.

Library(linprog) ## Warning: package "linprog" was built under R version 3.2.2 (result<-solveLP(f.obj, b.vec, a.mat, TRUE,const.dir=a.dir,lpSolve=T)) ## ## ## Results of Linear Programming / Linear Optimization ## (using lpSolve) ## ## Objective function (Maximum): 130000 ## ## Solution ## opt ## A 10 ## B 30 ## ## Constraints ## actual dir bvec free ## 1 330 <= 330 0 ## 2 280 <= 400 120 ## 3 240 <= 240 0 ## 4 10 >= 0 10 ## 5 30 >= 12 18

Результат вийшов той самий, додатково виведено інформацію з вільних ресурсів. Таким чином, GNU R надає досить зручний механізм для вирішення задач лінійного програмування.

Вконтакте

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

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

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

Побудуємо рівняння 3x1+x2=9 по двох точках.
Для знаходження першої точки прирівнюємо x 1 = 0. Знаходимо x 2 = 9. Для знаходження другої точки прирівнюємо x 2 = 0. Знаходимо x 1 = 3. З'єднуємо точку (0; 9) з (3; 0) прямою лінією. Визначимо напівплощину, що задається нерівністю. Вибравши точку (0; 0), визначимо знак нерівності у напівплощині: 3 . 0+1. 0 - 9 ≤ 0, тобто. 3x 1 +x 2 - 9≥ 0 у напівплощині вище прямої.
Побудуємо рівняння x1+2x2=8 по двох точках.
Для знаходження першої точки прирівнюємо x 1 = 0. Знаходимо x 2 = 4. Для знаходження другої точки прирівнюємо x 2 = 0. Знаходимо x 1 = 8. З'єднуємо точку (0; 4) з (8; 0) прямою лінією. Визначимо напівплощину, що задається нерівністю. Вибравши точку (0; 0), визначимо знак нерівності у напівплощині: 1 . 0+2. 0 - 8 ≤ 0, тобто. x 1 +2x 2 - 8≥ 0 у напівплощині вище прямої.
Побудуємо рівняння x 1 + x 2 = 8 по двох точках.
Для знаходження першої точки прирівнюємо x 1 = 0. Знаходимо x 2 = 8. Для знаходження другої точки прирівнюємо x 2 = 0. Знаходимо x 1 = 8. З'єднуємо точку (0; 8) з (8; 0) прямою лінією. Визначимо напівплощину, що задається нерівністю. Вибравши точку (0; 0), визначимо знак нерівності у напівплощині: 1 . 0+1. 0 - 8 ≤ 0, тобто. x 1 +x 2 - 8≤ 0 у напівплощині нижче прямої.

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

Перевірити правильність побудови графіків функцій можна за допомогою калькулятора

Розглянемо цільову функцію задачі F = 4x1+6x2 → min.
Побудуємо пряму, що відповідає значенню функції F = 0: F = 4x1 +6x2 = 0. Вектор-градієнт, складений з коефіцієнтів цільової функції, вказує напрямок мінімізації F(X). Початок вектора – точка (0; 0), кінець – точка (4; 6). Рухатимемо цю пряму паралельним чином. Оскільки нас цікавить мінімальне рішення, то рухаємо пряму до першого торкання зазначеної області. На графіці ця пряма позначена пунктирною лінією.

Пряма F(x) = 4x 1 +6x 2 перетинає область у точці B. Оскільки точка B отримана в результаті перетину прямих (1) і (2) , її координати задовольняють рівнянням цих прямих:
3x 1 +x 2 =9
x 1 +2x 2 =8

Розв'язавши систему рівнянь, отримаємо: x 1 = 2, x 2 = 3
Звідки знайдемо мінімальне значення цільової функції:
F(X) = 4*2 + 6*3 = 26

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

Кожна з нерівностей (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), підставимо координати (0;0) у відповідну нерівність. Т.к. нерівність вірна:

Області розв'язків відповідної 1-ї нерівності відповідає ліва напівплощина

Візьмемо будь-яку точку, наприклад точку, що не належить прямої (2), підставимо координати (0;0) у відповідну нерівність. Т.к. нерівність вірна:

Області розв'язків відповідної 2-ї нерівності відповідає ліва напівплощина

Для визначення напівплощини візьмемо будь-яку точку, наприклад точку, що не належить прямої (3), підставимо координати (0;0) у відповідну нерівність. Т.к. нерівність вірна:

Області розв'язків відповідної 3-ї нерівності відповідає нижня напівплощина

Областю допустимих рішень є фігура.

Будуємо вектор координати якого пропорційні коефіцієнтам цільової функції.

Перпендикулярно до побудованого вектора проводимо лінію рівня.

Знаходження оптимального плану

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

Отже, необхідно випускати 40 од. вироби Б. Виріб випускати невигідно. При цьому прибуток буде максимальним і складе 720 д.е.

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

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

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

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

Теоретичні основи графічного методу

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

при яких лінійна форма набуває оптимального значення.

приклад 3.

приклад 4.Вирішити графічним методом завдання лінійного програмування, в якому потрібно знайти мінімум функції при обмеженнях

Продовжуємо вирішувати завдання графічним методом разом

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

Приклад 5.Розв'язати графічним методом завдання лінійного програмування, у якому потрібно знайти максимум функції при обмеженнях

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

Легко помітити, що функція Fможе необмежено зростати при заданій системі обмежень, тому можна умовно записати, що .

Приклад 6.Розв'язати графічним методом завдання лінійного програмування, у якому потрібно знайти максимум функції при обмеженнях