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

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

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

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

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

Серед прямих згаданого сімейства паралельних прямих прямі mn (зеленого кольору) і MN (червоного кольору), які назвемо опорними. Опорними зазвичай називають такі прямі, які мають з багатокутником ABCDE хоча б одну спільну точку, і багатокутник ABCDE цілком лежить по одну сторону від цієї прямої. Як видно з креслення, пряма mn є опорною, так як вона стосується багатокутника в точці A і багатокутник цілком лежить правіше (або вище) цієї прямої. Пряма MN також є опорною, так як має з багатокутником загальну точку С і багатокутник цілком лежить лівіше цієї прямої.

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

1. Побудувати багатокутник рішень системи нерівностей.

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

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

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

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

Аналогічно будуємо інші граничні прямі. Друга пряма від осей координат відсікає відрізки, рівні 6. Третя пряма проходить паралельно осі , Відсікаючи на осі відрізок, рівний 2. Четверта пряма має рівняння . Вона збігається з віссю .

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

Отже, чотирикутник ABDE є багатокутником рішень системи (заштрихований всередину).

Накреслимо лінію рівних значень функції мети. Прийнявши в рівність F = 1, отримаємо, що ця лінія відсікає відрізки 1 і 1/3 відповідно на осі і на осі . Проведемо пряму через ці точки (на кресленні вона чорного кольору).

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

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

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

де .

Правильне рішення і відповідь .

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

де .

Правильне рішення і відповідь .

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

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

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

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

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

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

Рішення. Зображена на малюнку нижче область не містить жодної спільної точки, яка б задовольняла всім нерівностям системи обмежень. Тобто система обмежень суперечлива і не може містити жодного рішення, в тому числі і оптимального.

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

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

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

Всі точки відрізка CD дають одне і те ж значення функції мети, яке і служить її оптимальним значенням: . Отже, є не одне, а безліч оптимальних рішень, які збігаються з точками відрізка CD, зокрема, з двома кутовими точками C і D. Цей приклад показує, що в деяких випадках єдиність оптимального рішення порушується.

На сайті є Онлайн калькулятор вирішення завдань лінійного програмування симплекс-методом .

Наостанок слід зауважити, що будувати багатогранник рішень можна й іншим способом, що відрізняється від того, який ми розглядали. А саме: можна не шукати точки перетину прямих з осями координат, а шукати точки перетину прямих. Для цього послідовно вирішуються системи з двох рівнянь, так, щоб рішеннями були точки перетину всіх прямих. Отримані точки і будуть вершинами багатогранника рішень. Цей спосіб іноді буває зручним у випадках, коли точки перетину прямих з осями координат - дробові числа і, неправильно відклавши точку перетину, можна отримати помилку і в пошуку точок перетину самих прямих.

Початок теми "Лінійне програмування"

Поділитися з друзями