Решение ЗЛП графическим методом: Задача 131

Задача 131. Решить задачу линейного программирования (ЗЛП) графическим способом. Дана целевая функция: \[ L = -2x_1 + x_2 \rightarrow \max \] При ограничениях: \[ \begin{cases} x_1 + x_2 \ge 3 \\ x_1 + x_2 \le 7 \\ x_1 \le 6 \\ x_2 \le 3 \\ x_1 \ge 0; x_2 \ge 0 \end{cases} \] Решение: 1. Построим область допустимых решений (ОДР). Для этого построим прямые, соответствующие каждому ограничению, и определим полуплоскости, удовлетворяющие неравенствам. а) \( x_1 + x_2 \ge 3 \) Построим прямую \( x_1 + x_2 = 3 \). Если \( x_1 = 0 \), то \( x_2 = 3 \). Точка \( (0, 3) \). Если \( x_2 = 0 \), то \( x_1 = 3 \). Точка \( (3, 0) \). Для определения полуплоскости возьмем пробную точку \( (0, 0) \). \( 0 + 0 \ge 3 \Rightarrow 0 \ge 3 \) - ложно. Значит, полуплоскость находится выше прямой. б) \( x_1 + x_2 \le 7 \) Построим прямую \( x_1 + x_2 = 7 \). Если \( x_1 = 0 \), то \( x_2 = 7 \). Точка \( (0, 7) \). Если \( x_2 = 0 \), то \( x_1 = 7 \). Точка \( (7, 0) \). Для определения полуплоскости возьмем пробную точку \( (0, 0) \). \( 0 + 0 \le 7 \Rightarrow 0 \le 7 \) - истинно. Значит, полуплоскость находится ниже прямой. в) \( x_1 \le 6 \) Построим прямую \( x_1 = 6 \). Это вертикальная прямая. Полуплоскость \( x_1 \le 6 \) находится слева от этой прямой. г) \( x_2 \le 3 \) Построим прямую \( x_2 = 3 \). Это горизонтальная прямая. Полуплоскость \( x_2 \le 3 \) находится ниже этой прямой. д) \( x_1 \ge 0 \) и \( x_2 \ge 0 \) Эти ограничения означают, что ОДР находится в первом квадранте координатной плоскости. 2. Область допустимых решений (ОДР) будет многоугольником, образованным пересечением всех этих полуплоскостей. Найдем вершины этого многоугольника. Вершины ОДР: * Точка A: Пересечение \( x_1 + x_2 = 3 \) и \( x_2 = 0 \). \( x_1 + 0 = 3 \Rightarrow x_1 = 3 \). Точка \( A(3, 0) \). * Точка B: Пересечение \( x_1 + x_2 = 7 \) и \( x_2 = 0 \). \( x_1 + 0 = 7 \Rightarrow x_1 = 7 \). Но \( x_1 \le 6 \). Значит, эта точка не является вершиной. Вместо этого, рассмотрим пересечение \( x_1 = 6 \) и \( x_2 = 0 \). Точка \( (6, 0) \). Проверим, удовлетворяет ли она \( x_1 + x_2 \ge 3 \): \( 6 + 0 = 6 \ge 3 \) - да. Проверим, удовлетворяет ли она \( x_1 + x_2 \le 7 \): \( 6 + 0 = 6 \le 7 \) - да. Значит, точка \( B(6, 0) \) является вершиной. * Точка C: Пересечение \( x_1 = 6 \) и \( x_1 + x_2 = 7 \). \( 6 + x_2 = 7 \Rightarrow x_2 = 1 \). Точка \( C(6, 1) \). Проверим, удовлетворяет ли она \( x_2 \le 3 \): \( 1 \le 3 \) - да. Проверим, удовлетворяет ли она \( x_1 + x_2 \ge 3 \): \( 6 + 1 = 7 \ge 3 \) - да. * Точка D: Пересечение \( x_1 + x_2 = 7 \) и \( x_2 = 3 \). \( x_1 + 3 = 7 \Rightarrow x_1 = 4 \). Точка \( D(4, 3) \). Проверим, удовлетворяет ли она \( x_1 \le 6 \): \( 4 \le 6 \) - да. Проверим, удовлетворяет ли она \( x_1 + x_2 \ge 3 \): \( 4 + 3 = 7 \ge 3 \) - да. * Точка E: Пересечение \( x_1 + x_2 = 3 \) и \( x_2 = 3 \). \( x_1 + 3 = 3 \Rightarrow x_1 = 0 \). Точка \( E(0, 3) \). Проверим, удовлетворяет ли она \( x_1 \le 6 \): \( 0 \le 6 \) - да. Проверим, удовлетворяет ли она \( x_1 + x_2 \le 7 \): \( 0 + 3 = 3 \le 7 \) - да. * Точка F: Пересечение \( x_1 = 0 \) и \( x_2 = 3 \). Точка \( F(0, 3) \). Это та же точка, что и E. Таким образом, вершины ОДР: \( A(3, 0) \), \( B(6, 0) \), \( C(6, 1) \), \( D(4, 3) \), \( E(0, 3) \). 3. Найдем значение целевой функции \( L = -2x_1 + x_2 \) в каждой вершине ОДР. * Для \( A(3, 0) \): \( L_A = -2 \cdot 3 + 0 = -6 \). * Для \( B(6, 0) \): \( L_B = -2 \cdot 6 + 0 = -12 \). * Для \( C(6, 1) \): \( L_C = -2 \cdot 6 + 1 = -12 + 1 = -11 \). * Для \( D(4, 3) \): \( L_D = -2 \cdot 4 + 3 = -8 + 3 = -5 \). * Для \( E(0, 3) \): \( L_E = -2 \cdot 0 + 3 = 0 + 3 = 3 \). 4. Сравним полученные значения и выберем максимальное. \( L_A = -6 \) \( L_B = -12 \) \( L_C = -11 \) \( L_D = -5 \) \( L_E = 3 \) Максимальное значение целевой функции \( L \) равно \( 3 \) и достигается в точке \( E(0, 3) \). Ответ: Максимальное значение целевой функции \( L = -2x_1 + x_2 \) равно \( 3 \) и достигается в точке \( (x_1, x_2) = (0, 3) \).