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

Дано:

F=2Х₁+3Х₂ max;

Х₁ ≥ 4

Х₂ ≥3

Х₁+Х₂ ≤ 8

Х₁,Х₂ ≥0

Решение.

1) В ограничениях задач линейного программирования заменяем знаки неравенств на знаки уравнений и строим соответственно прямые.

Х₁ = 4

Х₂ =3

Х₁+Х₂ = 8

Вычисляем координаты точек пересечения этих прямых с осями координат.

1-я прямая: Х₁=4

2-я прямая: Х₂=3

3-я прямая: Х₁=0 Х₁=8

Х₂=8 Х₂=0

2) Находим и штрихуем полуплоскости, разрешенные каждым из ограничений неравенств задачи. Для этого подставляем в конкретное неравенство координаты, какой либо точки и проверяем истинность полученного неравенства. Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку, иначе надо заштриховать полуплоскость, не содержащую данную точку.

3) Определяем область допустимых решений как часть плоскости принадлежащей одновременно всем разрешенным областям и выделяем ее. При отсутствии области допустимых значений - задача не имеет решений. Общей областью, разрешенной всеми ограничениями, является треугольник АВС.

4) Так как в нашем случае область допустимых решений не пустое множество, то строим целевую прямую С₁Х₁+С₂Х₂=F, где F - кратное число С₁ и С₂.

Целевая прямая: 2Х₁+3Х₂ =6

Координаты точек пересечения этой прямой с осями координат.

Х₁=0 Х₁=3

Х₂=2 Х₂=0

5) Строим вектор С, который начинается в точке (0;0) и заканчивается в точке (2;3). Если целевая прямая и вектор С построены верно, то они будут перпендикулярны.

6) При поиске максимума целевой функции передвигаем целевую прямую в направлении вектора С, при поиске минимума- против направления вектора С. Последняя по ходу движения вершина ОДР будет точкой максимума целевой функции, точка В- точка максимума целевой функции при пересечении 1-й и 3-й прямых.

7) Определяем координаты точки максимума целевой функции Х*(Х₁*;Х₂*) и вычисляем значение F(Х*). Для вычисления координат оптимальной точки Х* решаем систему уравнений прямых, на пересечении которых находится Х*.

Х1=4 Х1=4

Х1+Х2=8 Х2=4

F(Х*) =F(4;4) = 2∙Х₁*+3∙Х₂*=2∙4+3∙4=8+12=20

Рисунок 1 – Графическое решение задачи