Геометрична інтерпретація задачі лінійного програмування. Графічний метод розв’язування задач лінійного програмування
Зміст
Що вдає із себе геометрична інтерпретація задачі лінійного програмування
Для розуміння всього в подальшого корисно знати і уявляти собі геометричну інтерпретацію завдань лінійного програмування, яку можна дати для випадків Неможливо розібрати вираз (невідома помилка): \ 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
Неможливо розібрати вираз (невідома помилка): \ldots
Неможливо розібрати вираз (невідома помилка): 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 нерівностей
Неможливо розібрати вираз (невідома помилка): a_{11}x_1+a_{12}x_2 \le b_1
Неможливо розібрати вираз (невідома помилка): a_{21}x_1+a_{22}x_2 \le b_2
(1.1)
Неможливо розібрати вираз (невідома помилка): \ldots
Неможливо розібрати вираз (невідома помилка): a_{m1}x_1 + a_{m2}x_2 \le b_m
Кожне з них задає на площині деяку півплощина. Нас цікавлять ті точки, які задовольняють всім цим m нерівностям, тобто точки, які належать усім цим півплощини одночасно. Отже, область, яка визначається нерівностями виду (1.1), геометрично зображається загальною частиною (перетином) всіх півплощини, що визначаються окремими обмеженнями (до них, звичайно, треба додати обмеження
Неможливо розібрати вираз (невідома помилка): x_1 \ge 0
і Неможливо розібрати вираз (невідома помилка): x_2 \ge 0 )
Як вже говорилося вище, ця область називається допустимою областю завдання лінійного програмування.
Приклад 2
Знайти допустиму область задачі лінійного програмування, яка визначається обмеженнями
Неможливо розібрати вираз (невідома помилка): \left\{ \begin{array}{ccc} -x_1+x_2 \le 1, \\ x_1-x_2 \le 1, \\ x_1+x_2 \le 3, \\ x_1 \ge 0, x_2 \ge 0 \end{array}\right.
Розв'язок
- Розглянемо пряму Неможливо розібрати вираз (невідома помилка): \ -x_1+x_2=1.
При Неможливо розібрати вираз (невідома помилка): \ x1=0, x_2=1
, а при Неможливо розібрати вираз (невідома помилка): \ x_2=0 x_1=-1 . Таким чином, ця пряма проходить через точки Неможливо розібрати вираз (невідома помилка): \ (0,1)
і Неможливо розібрати вираз (невідома помилка): \ (0,-1)
. Взявши Неможливо розібрати вираз (невідома помилка): \ x_1=x_2=0
откримаємо, що Неможливо розібрати вираз (невідома помилка): \ -0+0<1 і тому цікавою для нас є півплощина, що лежить нижче прямої, зображеної на рис. (4.а).
- Розгялнемо пряму Неможливо розібрати вираз (невідома помилка): \ x_1-2x_2=1
. При Неможливо розібрати вираз (невідома помилка): x_1=0 x_2= \frac{-1}2
,а при Неможливо розібрати вираз (невідома помилка): \ x_2=0,x_1=1.
Таким чином, ця прияма проходить через точки Неможливо розібрати вираз (невідома помилка): (0, \frac{-1}2)
і Неможливо розібрати вираз (невідома помилка): \ (1,0).
Так як Неможливо розібрати вираз (невідома помилка): \ 0-2*0<1
(4.б).
- Нарешті, розгянемо Неможливо розібрати вираз (невідома помилка): \ x_2=0 x_1=1
пряму Неможливо розібрати вираз (невідома помилка): x_1+x_2=3
. Вона проходе через точки Неможливо розібрати вираз (невідома помилка): \ (0,3)
і Неможливо розібрати вираз (невідома помилка): \ (3,0)
, і так як Неможливо розібрати вираз (невідома помилка): \ 0+0<3
то цікавить нас півплощина, яка лежить нижче прямої, зображеної на рис. 4.в.
Зводячи все разом і додаючи умови Неможливо розібрати вираз (невідома помилка): x_1 \ge 0 , Неможливо розібрати вираз (невідома помилка): x_2 \ge 0
одержимо малюнок 5, де виділена область, в якій виконуються одночасно всі обмеження. Зверніть увагу на те, що отримана область має вигляд опуклого багатокутника.
Повернемося тепер до загального випадку, коли одночасно виконуються нерівності
Неможливо розібрати вираз (невідома помилка): a_{11}x_1+a_{12}x_2 \le b_1
Неможливо розібрати вираз (невідома помилка): a_{21}x_1+a_{22}x_2 \le b_2
(1.2)
Неможливо розібрати вираз (невідома помилка): \ldots
Неможливо розібрати вираз (невідома помилка): a_{m1}x_1 + a_{m2}x_2 \le b_m
Неможливо розібрати вираз (невідома помилка): x_1 \ge 0;
Неможливо розібрати вираз (невідома помилка): x_2 \ge 0;
Разрешить написание латиницей
Не наводячи строгих доказів, вкажемо ті випадки, які отут можуть вийде.
1. Основний випадок - отримана область має вигляд обмеженого опуклого багатокутника (див. рис. 6).
2. Неосновної випадок- виходить необмежений опуклий багатокутник, що має вигляд, подібний зображеному на рис. 7. Подібна ситуація, наприклад, вийде, якщо в розглянутому вище прикладі прибрати обмеження Неможливо розібрати вираз (невідома помилка): x_1+x_2 \le 3 . Залишилася частина буде необмеженим опуклим багатокутником.
3. Нарешті, можливий випадок, коли нерівності (1.2) суперечать один одному, і допустима область взагалі порожня.
Повернемося тепер до вихідної задачі лінійного програмування. У ній, крім системи нерівностей, є ще цільова функція Неможливо розібрати вираз (невідома помилка): c_1x_1+c_2x_2 \rArr max
Розглянемо пряму Неможливо розібрати вираз (невідома помилка): \ c_1x_1+c_2x_2 = L.
Будемо збільшувати L. Що буде відбуватися з нашою прямій?
Легко здогадатися, що пряма рухатиметься паралельно самій собі в тому напрямку, який дається вектором Неможливо розібрати вираз (невідома помилка): \ (c_1,c_2) , так як це - вектор нормалі до нашої прямий і одночасно вектор градієнта функції Неможливо розібрати вираз (невідома помилка): \ f(x_1,x_2) = c_1x_1+c_2x_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
Неможливо розібрати вираз (невідома помилка): \ldots
Неможливо розібрати вираз (невідома помилка): a_{m1}x_1 + a_{m2}x_2 \le b_m
Неможливо розібрати вираз (невідома помилка): x_1 \ge 0;
Неможливо розібрати вираз (невідома помилка): x_2 \ge 0;
Обмеження завдання вирізають на площині деякий багатокутник. Нехай при деякому L пряма Неможливо розібрати вираз (невідома помилка): \ c_1x_1+c_2x_2 = L
перетинає допустиму область. Це перетин дає якісь значення змінних Неможливо розібрати вираз (невідома помилка): \ (x_1, x_2),
які є планами.
Збільшуючи L ми почнемо рухати нашу пряму і її перетин з допустимою областю буде змінюватися (див. рис. 9). Зрештою ця пряма вийде награниці допустимої області - як правило, це буде одна з вершин багатокутника. Подальше збільшення L призведе до того, що перетин
прямої Неможливо розібрати вираз (невідома помилка): \ c_1x_1+c_2x_2 = L,
при якому вона вийшла на граничну точку допустимої області, і дасть рішення задачі, а відповідне значення L і буде оптимальним значенням цільової функції.
Приклад 3
Розв'язати задачу
Неможливо розібрати вираз (невідома помилка): \left\{ \begin{array}{ccc} x_1+2x_2 \rArr max \\ -x_1+x_2 \le 1, \\ x_1-x_2 \le 1, \\ x_1+x_2 \le 3, \\ x_1 \ge 0, x_2 \ge 0 \end{array}\right.
Розв'язок
Допустиму область ми вже будували - вона зображена на рис. 5.
Повторимо ще раз цей малюнок, залишивши тільки допустиму область і намалювавши додатково прямі Неможливо розібрати вираз (невідома помилка): \ c_1x_1+c_2x_2 = L,
(див. рис. 10).
Нехай, наприклад, L=2. Тоді пряма Неможливо розібрати вираз (невідома помилка): x_1+2x_2 \rArr max
проходить через точки Неможливо розібрати вираз (невідома помилка): \ (2,0) і Неможливо розібрати вираз (невідома помилка): \ (0,1) зображена на рис. 10. Будемо тепер збільшувати L. Тоді пряма почне рухатися паралельно самій собі в напрямку стрілки. Легко здогадатися, що максимальне значення L вийде тоді, коли пряма пройде через вершину багатокутника, зазначену на малюнку, і подальше збільшення L призведе до того, що пряма вийде за межі багатокутника та її перетин з допустимою областю буде порожнім.
Виділена вершина лежить на перетині прямих Неможливо розібрати вираз (невідома помилка): \left\{ \begin{array}{ccc} -x_1+x_2 \le 1, \\ x_1+x_2 \le 3 \end{array}\right.
і тому має координати Неможливо розібрати вираз (невідома помилка): \ x_1=1
,Неможливо розібрати вираз (невідома помилка): \ x_2=2
Це і є рішення нашої задачі, Неможливо розібрати вираз (невідома помилка): \ x_1=1 ,Неможливо розібрати вираз (невідома помилка): \ x_2=2
є оптимальним планом нашої задачі. При цьому значення цільової функції Неможливо розібрати вираз (невідома помилка): \ L=1+2*2=5, що і дає її максимальне значення.
Зверніть увагу на те, що оптимальний план, як правило, відповідає якийсь вершині багатокутника, який зображує допустиму область. І лише в тому випадку, коли пряма Неможливо розібрати вираз (невідома помилка): \ c_1x_1+c_2x_2 = L,
рапитися так, що рішення не буде єдиним. Але і в цьому випадку вершини, відповідні межам цього боку, дають оптимальні плани нашої задачі лінійного програмування. Таким чином, вершини допустимої області грають у вирішенні завдань лінійного програмування особливу роль.
Ну, а якщо допустима область необмежена, то і значення цільової функції може бути необмеженим.
Підводячи підсумок цих прикладів, можна сформулювати такі положення:
- допустима область - це опуклий багатокутник;
- оптимальність досягається в вершині допустимої області (якщо допустима область обмежена і не порожня);
- обмеженість цільової функції в допустимій області є необхідною і достатньою умовою розв'язання задачі.
