Геометрична інтерпретація задачі лінійного програмування. Графічний метод розв’язування задач лінійного програмування
Геометрична інтерпретація задач лінійного програмування
Для розуміння всього в подальшого корисно знати і уявляти собі геометричну інтерпретацію завдань лінійного програмування, яку можна дати для випадків Неможливо розібрати вираз (невідома помилка): \ n = 2
і Неможливо розібрати вираз (невідома помилка): \ n = 3
.
Найбільш наочна ця інтерпретація для випадку Неможливо розібрати вираз (невідома помилка): \ n = 2 , тобто для випадку двох змінних і. Нехай нам задана задача лінійного програмування в стандартній формі
Неможливо розібрати вираз (невідома помилка): c_1x_1+c_2x_2 \rArr max
Неможливо розібрати вираз (невідома помилка): a_{11}x_1+a_{12}x_2 \le b_1
Неможливо розібрати вираз (невідома помилка): a_{21}x_1+a_{22}x_2 \le b_2
......
Неможливо розібрати вираз (невідома помилка): a_{m1}x_1 + a_{m2}x_2 \le b_m
Неможливо розібрати вираз (невідома помилка): x_1 \ge 0;
Неможливо розібрати вираз (невідома помилка): x_2 \ge 0;
Візьмемо на площині декартову систему координат і кожній парі чисел поставимо у відповідність точку на цій площині.
Звернемо насамперед увагу на обмеження Неможливо розібрати вираз (невідома помилка): x_1 \ge 0
і Неможливо розібрати вираз (невідома помилка): x_2 \ge 0 . Вони з усієї площині вирізають лише її першу чверть (див. рис. 1). Розглянемо тепер, які області відповідають нерівностям виду Неможливо розібрати вираз (невідома помилка): a_1x_1+a_2x_2 \ =b
. Спочатку розглянемо область, відповідну рівності Неможливо розібрати вираз (невідома помилка): a_1x_1+a_2x_2 \le =b . Як ви, звичайно, знаєте, це пряма лінія. Будувати її простіше всього по двом точкам.
Нехай Неможливо розібрати вираз (невідома помилка): b \ne 0
. Якщо взяти Неможливо розібрати вираз (невідома помилка): \ x_1 , то вийде Неможливо розібрати вираз (невідома помилка): x_2=\frac ba_2 . Якщо взяти Неможливо розібрати вираз (невідома помилка): \ x_2 , то вийде Неможливо розібрати вираз (невідома помилка): x_1=\frac ba_1 . Таким чином, на прямий лежать дві точки Неможливо розібрати вираз (невідома помилка): ( 0, \frac ba_2 ) і Неможливо розібрати вираз (невідома помилка): ( \frac ba_1, 0 )
. Далі через ці дві точки можна по лінійці провести пряму лінію (дивися рисунок 2).
Якщо ж Неможливо розібрати вираз (невідома помилка): \ b = 0 , то на прямий лежить точка Неможливо розібрати вираз (невідома помилка): \ (0,0) . Щоб знайти іншу точку, можна взяти будь-яке відмінне від нуля значення Неможливо розібрати вираз (невідома помилка): \ x_1
і обчислити відповідне йому значення Неможливо розібрати вираз (невідома помилка): \ x_2
.
Ця побудована пряма розбиває всю площину на дві півплощини. В одній її частині Неможливо розібрати вираз (невідома помилка): a_1x_1+a_2x_2 \ < b , а в інший навпаки Неможливо розібрати вираз (невідома помилка): a_1x_1+a_2x_2 \ > b . Дізнатися, якою напівплощини який знак має місце найпростіше подивившись, якому нерівності задовольняє якась точка площині, наприклад, початок координат, тобто точка Неможливо розібрати вираз (невідома помилка): \ (0,0) .
Приклад 1
Визначити півплощину, яка визначається нерівністю Неможливо розібрати вираз (невідома помилка): 4x_1 - 6x_2 \le3 .
Розв'зок:
Спочатку будуємо пряму Неможливо розібрати вираз (невідома помилка): \ x_1 - 6x_2 = 3. Вважаючи Неможливо розібрати вираз (невідома помилка): \ x_1 = 0
отримаємо Неможливо розібрати вираз (невідома помилка): \ -6x_1 = 3 або Неможливо розібрати вираз (невідома помилка): x_2= \frac{-1}2
. Вважаючі Неможливо розібрати вираз (невідома помилка): \ x_1 = 0
отримаємо Неможливо розібрати вираз (невідома помилка): \ -4x_1 = 3 або Неможливо розібрати вираз (невідома помилка): x_2= \frac34
. Таким чином, наша пряма проходить через точку Неможливо розібрати вираз (невідома помилка): (0, \frac-12 )
і Неможливо розібрати вираз (невідома помилка): (\frac34, 0 ) (див.рис.3)
Тепер подивимось, в якій півплощині точка Неможливо розібрати вираз (невідома помилка): \ (0,0) . Маємо Неможливо розібрати вираз (невідома помилка): \ 4*0-6*0<3 , де початок координат належить півплощині, де Неможливо розібрати вираз (невідома помилка): 4x_1 - 6x_2 \le3 . Тим самим визначилася і потрібна нам півплощина (див. рис. 3).
Повернемося тепер до задачі лінійного програмування. Там мають місце m нерівностей