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

Задача. Решить графически задачу линейного программирования, определив экстремальное значение целевой функции:

при ограничениях

Решение.

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

Построим уравнение 3x₁+x₂ = 9 по двум точкам.
Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 9. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 3. Соединяем точку (0;9) с (3;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 3 • 0 + 1 • 0 - 9 ≤ 0, т.е. 3x₁+x₂ - 9≥ 0 в полуплоскости выше прямой.
Построим уравнение x₁+2x₂ = 8 по двум точкам.
Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 4. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 8. Соединяем точку (0;4) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 2 • 0 - 8 ≤ 0, т.е. x₁+2x₂ - 8≥ 0 в полуплоскости выше прямой.
Построим уравнение x₁+x₂ = 8 по двум точкам.
Для нахождения первой точки приравниваем x₁ = 0. Находим x₂ = 8. Для нахождения второй точки приравниваем x₂ = 0. Находим x₁ = 8. Соединяем точку (0;8) с (8;0) прямой линией. Определим полуплоскость, задаваемую неравенством. Выбрав точку (0; 0), определим знак неравенства в полуплоскости: 1 • 0 + 1 • 0 - 8 ≤ 0, т.е. x₁+x₂ - 8≤ 0 в полуплоскости ниже прямой.

Пересечением полуплоскостей будет являться область, координаты точек которого удовлетворяют условию неравенствам системы ограничений задачи.
Обозначим границы области многоугольника решений.

Проверить правильность построения графиков функций можно с помощью калькулятора

Рассмотрим целевую функцию задачи F = 4x₁+6x₂ → min.
Построим прямую, отвечающую значению функции F = 0: F = 4x₁+6x₂ = 0. Вектор-градиент, составленный из коэффициентов целевой функции, указывает направление минимизации F(X). Начало вектора – точка (0; 0), конец – точка (4; 6). Будем двигать эту прямую параллельным образом. Поскольку нас интересует минимальное решение, поэтому двигаем прямую до первого касания обозначенной области. На графике эта прямая обозначена пунктирной линией.

Прямая F(x) = 4x₁+6x₂  пересекает область в точке B. Так как точка B получена в результате пересечения прямых (1) и (2), то ее координаты удовлетворяют уравнениям этих прямых:
3x₁+x₂=9
x₁+2x₂=8

Решив систему уравнений, получим: x₁ = 2, x₂ = 3
Откуда найдем минимальное значение целевой функции:
F(X) = 4*2 + 6*3 = 26