Решить задачу линейного программирования графическим методом.
Конечно! Сейчас я подробно объясню, как решить задачу линейного программирования графическим методом.
Задача выглядит так:
Максимизировать функцию: \[ L = 2x_1 - 3x_2 \]
при ограничениях: \[ \begin{cases} -x_1 + x_2 \leq 2 \\ 2x_1 + 3x_2 \geq 16 \\ x_1 + x_2 \leq 10 \\ 2x_1 - x_2 \leq 8 \\ x_1 \geq 0, \quad x_2 \geq 0 \end{cases} \]
Шаг 1: Построение графика ограничений
Графики линий ограничений — это линии, соответствующие равенствам при равных ограничениях.
Перепишем ограничения в виде уравнений:
\( -x_1 + x_2 = 2 \)
\( 2x_1 + 3x_2 = 16 \)
\( x_1 + x_2 = 10 \)
\( 2x_1 - x_2 = 8 \)
Также учитываем неотрицательность \( x_1 \geq 0, \, x_2 \geq 0 \).
Шаг 2: Построение линий и определение допустимой области
- Для каждой линии найдём две точки.
Линия 1: \( -x_1 + x_2 = 2 \)
Когда \( x_1=0 \), \( x_2=2 \).
Когда \( x_2=0 \), \( -x_1=2 \Rightarrow x_1=-2 \) (отрицательное, не в области допустимых значений).
Значит, ограничивающая точка на оси \( x_2 \): (0, 2).
В области допустимых решений, так как неравенство — \( -x_1 + x_2 \le 2 \), то эта линия служит границей, и допустимая область — ниже или слева от неё (зависит от знака).
Линия 2: \( 2x_1 + 3x_2=16 \)
\( x_1=0 \Rightarrow x_2=16/3 \approx 5.33 \)
\( x_2=0 \Rightarrow x_1=8 \)
Точки: (0, 16/3), (8, 0).
Линия 3: \( x_1 + x_2=10 \)
\( x_1=0 \Rightarrow x_2=10 \)
\( x_2=0 \Rightarrow x_1=10 \)
Точки: (0,10), (10,0).
Линия 4: \( 2x_1 - x_2=8 \)
\( x_1=0 \Rightarrow x_2=-8 \) (отрицательное, вне области).
\( x_2=0 \Rightarrow 2x_1=8 \Rightarrow x_1=4 \).
Точки: (4,0).
Шаг 3: Определение области допустимых решений
Область допустимых решений — это множество точек, удовлетворяющих все неравенства.
Особенно обратим внимание на знак неравенств:
\( -x_1 + x_2 \le 2 \)
\( 2x_1 + 3x_2 \ge 16 \) — “более равно 16” означает, что допустимая область — то, что находится слева или выше линии.
\( x_1 + x_2 \le 10 \)
\( 2x_1 - x_2 \le 8 \)
Поскольку ограничение \( 2x_1 + 3x_2 \ge 16 \) — неравенство “больше или равно”, это означает, что допустимая зона — слева или выше линии \( 2x_1 + 3x_2=16 \).
Шаг 4: Построение многоугольника допустимых решений
- Начинаем с построения линий на координатной плоскости, отмечая точки пересечения.
- Определяем, какие части области удовлетворяют всем неравенствам.
Следуем по границам и проверяем в каждом углу или ключевой точке, входит ли она в допустимую область.
Шаг 5: Поиск вершин многоугольника
Геометрически ищем точки пересечения линий, которые могут быть кандидатами на максимум функции.
Пересечения линий:
- Пересечение \( -x_1 + x_2=2 \) и \( x_1 + x_2=10 \):
- из второго \(\Rightarrow x_2=10 - x_1 \).
Подставляем в первое:
\[ -x_1 + (10 - x_1)= 2 \Rightarrow -x_1 +10 - x_1=2 \Rightarrow -2x_1= -8 \Rightarrow x_1=4. \]
Тогда
\[ x_2=10 -4=6. \]
Точка: \((4, 6)\).
Проверяем не входит ли эта точка в допустимую область (учитываем неравенства). Она подходит, так как:
\( -x_1 + x_2= -4 +6=2 \le 2 \checkmark \)
\( x_1 + x_2= 4 +6=10 \le 10 \checkmark \)
\( 2x_1 + 3x_2= 8 + 18=26 \ge 16 \checkmark \)
\( 2x_1 - x_2=8 -6=2 \le 8 \checkmark \)
Также \( x_1, x_2 \ge 0 \).
- Пересечение \( 2x_1 + 3x_2=16 \) и \( x_1 + x_2=10 \):
Ранее:
- \( x_2 = 10 - x_1 \).
Подставляем:
\[ 2x_1 + 3(10 - x_1 )=16 \]
\[ 2x_1 + 30 -3 x_1=16 \]
\[ - x_1= -14 \Rightarrow x_1=14 \]
Тогда:
\[ x_2=10 -14= -4 \]
Это отрицательная точка, не входит в область: исключаем.
- Пересечение \( 2x_1 + 3x_2=16 \) и \( 2x_1 - x_2=8 \):
Из второго:
\[ x_2= 2x_1 -8 \]
Подставляем в первое:
\[ 2x_1 + 3(2x_1 -8)=16 \]
\[ 2x_1 +6x_1 -24=16 \]
\[ 8x_1=40 \Rightarrow x_1=5 \]
Тогда
\[ x_2= 2*5 -8=2 \]
Проверяем вход в допустимую область:
\( -x_1 + x_2= -5 +2= -3 \le 2 \checkmark \)
\( 2x_1 + 3x_2= 10 +6=16 \checkmark \)
\( x_1 + x_2=5 +2=7 \le 10 \checkmark \)
\( 2x_1 - x_2=10 -2=8 \le8 \checkmark \)
Положительные \(x_1=5, x_2=2 \).
- Также вершинами могут стать точки пересечения с осями:
- \( (0, 0) \), но она, скорее всего, не входит в допустимую область, так как ограничения требуют, например, \( 2x_1 +3x_2 \ge 16 \).
Шаг 6: Расчет значения целевой функции в вершинах многоугольника
Вычислим \(L= 2x_1 -3x_2\):
- в точке \((4,6)\):
\[ L= 2*4 - 3*6=8 -18= -10 \]
- в точке \((5, 2)\):
\[ L= 2*5 -3*2=10 -6=4 \]
- в точке \((0, 10)\):
\[ L= 0 -30= -30 \]
- проверим еще вершины, например, \((0,16/3)\), если она входит в допустимую область, но так как там (2x_1 + 3x
