II. Решение задачи линейного программирования геометрическим методом

 

Общей задачей линейного программирования называется задача нахожде­ния минимума (максимума) линейной функции

 

Z = c₁ x₁ + c₂ x₂ +...+ c_n x_n ® min (max) (1)

 

при ограничениях:

a₁₁ x₁ + a₁₂ x₂ +...+ a_1n x_n £ (=, ³) b₁

a₂₁ x₁ + a₂₂ x₂ +...+ a_2n x_n £ (=, ³) b₂ (2)

..................................

a_m1 x₁ + a_m2 x₂ +...+ a_mn x_n £ (=, ³) b_m,

x_j ³ 0, j = 1,..., n (3)

 

где c_j, a_ij, b_i - заданные числа, x_j - неизвестные, i = 1,…,m, j = 1,…,n и в лю­бом из ограничений вида (2) может встречаться любой из знаков £, = или ³.

Если число неизвестных n = 2, то задача (1) – (3) примет вид

 

Z = c₁ x + c₂ y ® min (max) (4)

a₁₁ x + a₁₂ y £ (=, ³) b₁

a₂₁ x + a₂₂ y £ (=, ³) b₂ (5)

......................

a_m1 x + a_m2 y £ (=, ³) b_m,

x ³ 0, y ³ 0. (6)

 

и ее можно решить геометрическим методом, так как каждая пара неизвестных (х, y) может быть представлена точкой на координатной плоскости хОy.

При решении задачи (4) – (6) сначала строят так называемую допустимую область, т.е. множество точек (х, y) плоскости, координаты которых удовлет­воряют всем ограничениям (5) и лежат в первой четверти координатной плос­кости (ограничение (6)). Поскольку все ограничения (5) – линейные, то допус­тимая область будет представлять собой выпуклый многоугольник (конечный или бесконечный) или пустое множество.

Затем среди точек допустимой области находят оптимальную, т.е. такую точку М₀ координаты которой (х₀ , y₀) доставляют минимум (максимум) целе­вой функции Z. Для этого по виду целевой функции (4) строят линию уровня функции Z, соответствующую Z=0, т.е. прямую L₀: c₁ x + c₂ y = 0 и находят градиент функции Z – вектор , который пока­зывает направление наибыстрейшего возрастания функции Z. Вектор анти­градиента (-с₁, -с₂) будет показывать направление наибыстрейшего убывания целевой функции Z. Вектор градиента перпендикулярен линии уровня L₀.

Перемещая линию уровня L₀ параллельно самой себе в направлении градиента (с₁, с₂), находим последнюю точку допустимой области, которую она пересекает при таком движении. Очевидно, что это будет точка максимума. Перемещая линию уровня в противоположном направлении (-с₁, -с₂), находим точку минимума. Поясним этот метод на конкретном примере.

Геометрическим методом найти максимум и минимум функции Z для

x, y ³ 0 при заданных ограничениях.

Z = x – 3y

-x + y £ 4

5x + 4y £ 34

x + 8y ³ 14

Решение. Построим допустимую область. Для этого в системе координат х0y строим прямую - x + y= 4 - границу первого ограничения. Затем определяем, в какой полуплоскости находятся точки (х, y), для которых -x + y < 4. Для этого выбираем любую точку, например (0, 0), и проверяем, удовлетворяет ли она этому неравенству. Поскольку -0 + 0 = 0 < 4, то точки, для которых - x+y£ 4 лежат в той же полуплоскости, что и точка О(0, 0), т.е. справа (ниже) от границы -x + y = 4.

 

y

8,5 -x + y = 4

L₂

 

C

L₀

4 B L₁

E

1,75 A D

0 1 6,8 14 y

x + 8y =14

-3 5x + 4y = 34

 

Аналогично строятся остальные полуплоскости, соответствующие ограничениям 5 х + 4 у £ 34 и х + 8 у ³ 14 (ниже прямой 5 х + 4 у = 34 и выше прямой х + 8 у = 14). Множество точек, удовлетворяющих всем трем нера­венствам, образуют треугольник ECD. Учитывая ограничение х ³ 0 и у ³ 0, получаем допустимую область – четырехугольник ABCD.

Проведем линию уровня L ₀, соответствующую значению Z =0, т.е. пря­мую х – 3 у = 0 (для точек, лежащих на этой прямой, значение Z =0). Она будет проходить через точку О(0, 0) перпендикулярно вектору . Пере­мещая линию уровня в направлении градиента , т.е. в направлении возраста­ния Z, находим последнюю точку допустимой области, которую линия уровня пересекает при этом движении (линия L₁). Это будет точка максимума. В нашем случае – это точка D (6, 1), координаты которой можно найти, решив систему линейных уравнений 5 х + 4 у = 34 и х + 8 у = 14. Аналогично, двигая линию уровня в противоположном направлении до линии L₂, находим точку минимума – точку С (2, 6). Таким образом, Z_max= Z (6,1)= 6 - 3×1=3, Z_min=Z (2,6)=2-3×6=-16.

Задача решена полностью.

 

 

КОНТРОЛЬНЫЕ ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

 

Задание 2. Геометрическим методом найти максимум и минимум функции Z для x, y ³ 0 при заданных ограничениях:

 

Варианты:

 

1. Z = 2x + y 2. Z = 3x + y

3x - 4y £ 4 y £ 1

-x + 6y £ 8 x - 2y £ 3

x + y ³ 1 2x + y ³ 1

 

3. Z = 2x - y 4. Z = x + y

2x + y £ 3 y ³ 2

x + y ³ 6 x + y £ 7

x - 3y £ 3 -x + 2y £ 2

 

5. Z = 4x + y 6. Z = 3x - y

x - 2y ³ 0 2x + 3y £ 13

4x - y £ 14 x ³ 2

3x + y ³ 7 5x - 3y £ 22

 

 

7. Z = 2x + y 8. Z = x + 5y

x ³ 2 3x - y ³ 3

4x - y £ 8 x - y £ 4

x - y ³ -1 x + y ³ 6

 

9. Z = 5x + y 10. Z = 3x

x - 4y ³ -3 x + y £ 7

4x - 3y £ 14 2x - y £ 11

3x + y ³ 4 4x + y ³ 19