Відмінності між версіями «Геометрична інтерпретація задачі лінійного програмування. Графічний метод розв’язування задач лінійного програмування»

Матеріал з Вікі ЦДУ
Перейти до: навігація, пошук
(→‎Приклад 2)
(→‎Приклад 2)
Рядок 74: Рядок 74:
 
# Розгялнемо пряму <math> \ x_1-2x_2=1</math>. При <math>x_1=0  x_2= \frac{-1}2</math> ,а при <math> \ x_2=0,x_1=1.</math> Таким чином, ця прияма проходить через точки <math> (0, \frac{-1}2)</math> і <math> \ (1,0).</math> Так як <math> \ 0-2*0<1</math> (4.б).
 
# Розгялнемо пряму <math> \ x_1-2x_2=1</math>. При <math>x_1=0  x_2= \frac{-1}2</math> ,а при <math> \ x_2=0,x_1=1.</math> Таким чином, ця прияма проходить через точки <math> (0, \frac{-1}2)</math> і <math> \ (1,0).</math> Так як <math> \ 0-2*0<1</math> (4.б).
  
−
# Нарешті, розгянемо <math> \ x_2=0 x_1=1</math> пряму <math> x_1+x_2=3 </math>. Вона проходе через точки <math> \ (0,3)</math> і <math> \ (3,0)</math>, і так як  <math> \ 0+0<3 </math> то цікавить нас півплощина, яка лежить нижче прямої, зображеної на рис. 4.в).
+
# Нарешті, розгянемо <math> \ x_2=0 x_1=1</math> пряму <math> x_1+x_2=3 </math>. Вона проходе через точки <math> \ (0,3)</math> і <math> \ (3,0)</math>, і так як  <math> \ 0+0<3 </math> то цікавить нас півплощина, яка лежить нижче прямої, зображеної на рис. 4.в.
 +
 
 +
[[Файл:1231.png]]
 +
 
 +
Зводячи все разом і додаючи умови <math>x_1 \ge 0</math>, <math>x_2 \ge 0</math> одержимо малюнок 5, де виділена область, в якій виконуються одночасно всі обмеження. Зверніть увагу на те, що отримана область має вигляд опуклого багатокутника.
 +
 
 +
Повернемося тепер до загального випадку, коли одночасно виконуються нерівності

Версія за 18:13, 27 квітня 2012

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

Для розуміння всього в подальшого корисно знати і уявляти собі геометричну інтерпретацію завдань лінійного програмування, яку можна дати для випадків Неможливо розібрати вираз (невідома помилка): \ 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;


Візьмемо на площині декартову систему координат і кожній парі чисел поставимо у відповідність точку на цій площині.

Безымянный1231.gif

Звернемо насамперед увагу на обмеження Неможливо розібрати вираз (невідома помилка): 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).

231.gif

Якщо ж Неможливо розібрати вираз (невідома помилка): \ 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).

Безымянный12312.png

Повернемося тепер до задачі лінійного програмування. Там мають місце 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.


  1. Розглянемо пряму Неможливо розібрати вираз (невідома помилка): \ -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.а).
  1. Розгялнемо пряму Неможливо розібрати вираз (невідома помилка): \ 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.б).
  1. Нарешті, розгянемо Неможливо розібрати вираз (невідома помилка): \ x_2=0 x_1=1 
пряму Неможливо розібрати вираз (невідома помилка):  x_1+x_2=3

. Вона проходе через точки Неможливо розібрати вираз (невідома помилка): \ (0,3) 

і Неможливо розібрати вираз (невідома помилка):  \ (3,0)

, і так як Неможливо розібрати вираз (невідома помилка): \ 0+0<3 

то цікавить нас півплощина, яка лежить нижче прямої, зображеної на рис. 4.в.

1231.png

Зводячи все разом і додаючи умови Неможливо розібрати вираз (невідома помилка): x_1 \ge 0 , Неможливо розібрати вираз (невідома помилка): x_2 \ge 0 

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

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

Отримано з https://wiki.cusu.edu.ua/index.php?title=Геометрична_інтерпретація_задачі_лінійного_програмування._Графічний_метод_розв’язування_задач_лінійного_програмування&oldid=66308