Задача 94. Решить графически задачу линейного программирования. \begin{cases} x_1 - x_2 \le 2 \\ x_1 + x_2 \le 4 \\ x_1 + 3x_2 \le 5 \\ 2x_1 + x_2 \ge 2 \\ x_1 \ge 0, x_2 \ge 0 \end{cases} Z = 4x_1 + x_2 \rightarrow max

Решение:

Для решения задачи линейного программирования графическим методом, построим область допустимых решений, соответствующую системе неравенств, и найдем точку, в которой целевая функция Z = 4x₁ + x₂ принимает максимальное значение.

1. Построение линий ограничений:

• x₁ - x₂ = 2: Проходит через точки (2, 0) и (0, -2). Область решения: ниже линии.
• x₁ + x₂ = 4: Проходит через точки (4, 0) и (0, 4). Область решения: ниже линии.
• x₁ + 3x₂ = 5: Проходит через точки (5, 0) и (0, 5/3). Область решения: ниже линии.
• 2x₁ + x₂ = 2: Проходит через точки (1, 0) и (0, 2). Область решения: выше линии.
• x₁ = 0 (ось x₂): Область решения: правее оси.
• x₂ = 0 (ось x₁): Область решения: выше оси.

2. Определение области допустимых решений (ОДР):

ОДР — это многоугольник, образованный пересечением всех этих областей. Вершинами ОДР являются точки пересечения граничных линий.

3. Нахождение вершин ОДР:

• A: Пересечение 2x₁ + x₂ = 2 и x₂ = 0. Подставляем x₂=0 во второе уравнение: 2x₁ = 2 => x₁ = 1. Точка A(1, 0).
• B: Пересечение x₁ - x₂ = 2 и x₁ + x₂ = 4. Складываем уравнения: 2x₁ = 6 => x₁ = 3. Подставляем x₁=3 в x₁ + x₂ = 4: 3 + x₂ = 4 => x₂ = 1. Точка B(3, 1).
• C: Пересечение x₁ + x₂ = 4 и x₁ + 3x₂ = 5. Вычитаем первое из второго: 2x₂ = 1 => x₂ = 0.5. Подставляем x₂=0.5 в x₁ + x₂ = 4: x₁ + 0.5 = 4 => x₁ = 3.5. Точка C(3.5, 0.5).
• D: Пересечение 2x₁ + x₂ = 2 и x₁ + 3x₂ = 5. Из первого: x₂ = 2 - 2x₁. Подставляем во второе: x₁ + 3(2 - 2x₁) = 5 => x₁ + 6 - 6x₁ = 5 => -5x₁ = -1 => x₁ = 0.2. Подставляем x₁=0.2 в x₂ = 2 - 2x₁: x₂ = 2 - 2(0.2) = 2 - 0.4 = 1.6. Точка D(0.2, 1.6).
• E: Пересечение x₁ - x₂ = 2 и x₁ = 0. Подставляем x₁=0: -x₂ = 2 => x₂ = -2. Эта точка не входит в ОДР, так как x₂ должно быть >=0.
• F: Пересечение x₁ + 3x₂ = 5 и x₁ = 0. Подставляем x₁=0: 3x₂ = 5 => x₂ = 5/3. Точка F(0, 5/3). (Проверка: 5/3 ≈ 1.667. Условие 2x₁ + x₂ ≥ 2: 2(0) + 5/3 = 5/3 < 2, значит эта точка не удовлетворяет условию. Пересмотрим пересечение 2x₁ + x₂ = 2 и x₁ + 3x₂ = 5. Точка D(0.2, 1.6) Проверим условия: x₁ - x₂ = 0.2 - 1.6 = -1.4 ≤ 2 (верно) x₁ + x₂ = 0.2 + 1.6 = 1.8 ≤ 4 (верно) x₁ + 3x₂ = 0.2 + 3(1.6) = 0.2 + 4.8 = 5 ≤ 5 (верно) 2x₁ + x₂ = 2(0.2) + 1.6 = 0.4 + 1.6 = 2 ≥ 2 (верно) x₁ ≥ 0, x₂ ≥ 0 (верно). Точка D(0.2, 1.6) входит в ОДР. Пересмотрим пересечение x₁ + 3x₂ = 5 и x₁=0. Точка F(0, 5/3). Проверим условия: x₁ - x₂ = 0 - 5/3 = -5/3 ≤ 2 (верно) x₁ + x₂ = 0 + 5/3 = 5/3 ≤ 4 (верно) x₁ + 3x₂ = 0 + 3(5/3) = 5 ≤ 5 (верно) 2x₁ + x₂ = 2(0) + 5/3 = 5/3 ≥ 2 (НЕВЕРНО). Значит точка F не входит в ОДР. Проверим точку пересечения x₁ + x₂ = 4 и x₁ + 3x₂ = 5. Точка C(3.5, 0.5) x₁ - x₂ = 3.5 - 0.5 = 3 ≤ 2 (НЕВЕРНО). Точка C не входит в ОДР. Пересмотрим пересечение x₁ - x₂ = 2 и x₁ + x₂ = 4. Точка B(3, 1) x₁ - x₂ = 3 - 1 = 2 ≤ 2 (верно) x₁ + x₂ = 3 + 1 = 4 ≤ 4 (верно) x₁ + 3x₂ = 3 + 3(1) = 6 ≤ 5 (НЕВЕРНО). Точка B не входит в ОДР. Пересмотрим пересечение x₁ - x₂ = 2 и 2x₁ + x₂ = 2. Складываем уравнения: 3x₁ = 4 => x₁ = 4/3. Подставляем x₁=4/3 в x₁ - x₂ = 2: 4/3 - x₂ = 2 => x₂ = 4/3 - 2 = 4/3 - 6/3 = -2/3. Не подходит, т.к. x₂ < 0. Давайте перерисуем и определим вершины. Линии: 1. x₂ = x₁ - 2 2. x₂ = 4 - x₁ 3. x₂ = (5 - x₁)/3 4. x₂ = 2 - 2x₁ Вершины: * Пересечение x₁ = 0 и x₂ = 0: (0,0) - не подходит, т.к. 2x₁+x₂ >= 2. * Пересечение 2x₁ + x₂ = 2 и x₁ = 0: x₂ = 2. Точка (0, 2). Проверим: 0 - 2 = -2 <= 2 (верно), 0 + 2 = 2 <= 4 (верно), 0 + 3*2 = 6 <= 5 (НЕВЕРНО). * Пересечение 2x₁ + x₂ = 2 и x₂ = 0: x₁ = 1. Точка (1, 0). Проверим: 1 - 0 = 1 <= 2 (верно), 1 + 0 = 1 <= 4 (верно), 1 + 0 = 1 <= 5 (верно), 2*1 + 0 = 2 >= 2 (верно). Точка A(1, 0) - ВЕРШИНА. * Пересечение x₁ + x₂ = 4 и x₁ + 3x₂ = 5. x₁ = 4 - x₂. (4 - x₂) + 3x₂ = 5 => 4 + 2x₂ = 5 => 2x₂ = 1 => x₂ = 0.5. x₁ = 4 - 0.5 = 3.5. Точка (3.5, 0.5). Проверим: 3.5 - 0.5 = 3 <= 2 (НЕВЕРНО). * Пересечение x₁ + x₂ = 4 и x₁ - x₂ = 2. 2x₁ = 6 => x₁ = 3. x₂ = 1. Точка (3, 1). Проверим: 3 - 1 = 2 <= 2 (верно), 3 + 1 = 4 <= 4 (верно), 3 + 3*1 = 6 <= 5 (НЕВЕРНО). * Пересечение x₁ + 3x₂ = 5 и 2x₁ + x₂ = 2. x₂ = 2 - 2x₁. x₁ + 3(2 - 2x₁) = 5 => x₁ + 6 - 6x₁ = 5 => -5x₁ = -1 => x₁ = 0.2. x₂ = 2 - 2(0.2) = 1.6. Точка (0.2, 1.6). Проверим: 0.2 - 1.6 = -1.4 <= 2 (верно), 0.2 + 1.6 = 1.8 <= 4 (верно), 0.2 + 3*1.6 = 0.2 + 4.8 = 5 <= 5 (верно), 2*0.2 + 1.6 = 0.4 + 1.6 = 2 >= 2 (верно). Точка D(0.2, 1.6) - ВЕРШИНА. * Пересечение x₁ - x₂ = 2 и x₁ + 3x₂ = 5. x₁ = 2 + x₂. (2 + x₂) + 3x₂ = 5 => 2 + 4x₂ = 5 => 4x₂ = 3 => x₂ = 0.75. x₁ = 2 + 0.75 = 2.75. Точка (2.75, 0.75). Проверим: 2.75 - 0.75 = 2 <= 2 (верно), 2.75 + 0.75 = 3.5 <= 4 (верно), 2.75 + 3*0.75 = 2.75 + 2.25 = 5 <= 5 (верно), 2*2.75 + 0.75 = 5.5 + 0.75 = 6.25 >= 2 (верно). Точка C(2.75, 0.75) - ВЕРШИНА. Пересечение x₁ + x₂ = 4 и x₂ = 0. Точка (4, 0). Проверим: 4-0=4<=2 (НЕВЕРНО). Пересечение x₁ - x₂ = 2 и x₂ = 0. Точка (2, 0). Проверим: 2-0=2<=2 (верно), 2+0=2<=4 (верно), 2+0=2<=5 (верно), 2*2+0=4>=2 (верно). Точка B(2, 0) - ВЕРШИНА. Определим точки, которые формируют ОДР: A(1, 0) B(2, 0) C(2.75, 0.75) D(0.2, 1.6)

4. Вычисление значения целевой функции Z в вершинах:

• Z(A) = Z(1, 0) = 4*(1) + 0 = 4
• Z(B) = Z(2, 0) = 4*(2) + 0 = 8
• Z(C) = Z(2.75, 0.75) = 4*(2.75) + 0.75 = 11 + 0.75 = 11.75
• Z(D) = Z(0.2, 1.6) = 4*(0.2) + 1.6 = 0.8 + 1.6 = 2.4

5. Определение максимального значения:

Максимальное значение функции Z достигается в вершине C.

Финальный ответ: Максимальное значение Z = 11.75 достигается в точке (2.75, 0.75).