Построение области допустимых решений целевой функции F

Графический метод решения двумерной задачи линейного программирования

Пример 1

Решим полученную двумерную задачу линейного программирования графически:

F = 2_x1+4x2 → max

Решение

Построение области допустимых решений целевой функции F

Построим прямоугольную систему координат, где ось ОX обозначим за x₁, а OY – за x₂. Так как, согласно условию x₁ и x₂ неотрицательны, то можно ограничиться рассмотрением первого квадранта.

Рассмотрим первое ограничение: 3x₁+4x₂ ≤ 1700 (1)

Заменим в данном ограничении знак неравенства знаком равенства и построим прямую.

3x₁+4x₂ = 1700 (1')

Для этого найдем две точки, принадлежащие данной прямой. Пусть, например, x₁ = 0, тогда подставив 0 в (1') получим 4x₂ = 1700 или x₂ = 425. (0; 425) – координаты первой точки, принадлежащей прямой.

Пусть x₂ = 0, то 3x₁ = 1700, следовательно, x₁ = 567. (567; 0) – координаты второй точки, принадлежащей прямой. Отметим эти точки на числовых осях.

Аналогично для второго ограничения: 2x₁+5x₂ ≤ 1600 (2)

2x₁+5x₂ = 1600 (2')

При x₁=0, x₂ = 320 (0; 320)

При x₂=0, x₁ = 800 (800; 0)

Построим данные прямые (на рис. 3.2.1 они соответственно обозначены (1') и (2')).

Теперь найдем на чертеже такие полуплоскости, которые соответствуют неравенствам (1) и (2).

Прямая (1') 3x₁+4x₂=1700 делит координатную плоскость на две полуплоскости. Одна полуплоскость расположена выше прямой, вторая ниже. Чтобы найти ту полуплоскость, которая соответствует неравенству (1), необходимо взять какую-либо точку, принадлежащую одной из полуплоскостей и подставить ее координаты в неравенство. Если неравенство будет верным, то данная полуплоскость является искомой.

Например, возьмем точку с координатами (0; 0) и подставим ее координаты в неравенство (1) 3x₁+4x₂ ≤ 1700 или 0+0 ≤ 1700. Получается 0 ≤ 1700 – данное неравенство является верным, следовательно, неравенству (1) удовлетворяет полуплоскость, лежащая ниже прямой (1').

Аналогично, поступим для неравенства (2) 2x₁+5x₂ ≤ 1600. Возьмем точку с координатами (0; 0). Получается 0 ≤ 1600 – данное неравенство верно. Неравенству (2) удовлетворяет полуплоскость, расположенная ниже прямой (2').

Стрелки на каждой границе указывают то направление, где выполнены ограничения. Учитывая то, что x₁ и x₂ являются неотрицательными, получаем, что четырехугольник ОАВС является областью, содержащей точки, для которых выполнены условия, заключенные в фигурные скобки.

Точки, лежащие внутри и на границе этой области являются допустимыми решениями, но нам нужны, только те, при которых функция F будет принимать максимальные значения.