Решение задач ЛП графоаналитическим методом

 

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

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

1. Геометрическое представление области (множества) допустимых решений.

2. Определение направления возрастания (в задаче максимизации) или убывания (в задаче минимизации) целевой функции.

3. Нахождение оптимального решения — точки (точек), в которой (которых) достигается максимум или минимум целевой функции.

 

 

Пример 3.2.

 

Требуется найти такие значения (х₁,х₂), которые обращают в максимум целевую функцию

 

Z = 5х₁ + x₂ max

 

и при этом удовлетворяют системе ограничений

3х₁ + 2x₂ 12,

x₁ + 2х₂ 4,

2x₁ - х₂ 1,

и условиям неотрицательности

x₁ 0, x₂ 0

 

Решение

 

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

Вектор, указывающий направление роста целевой функции Z= 5x₁ + х₂, имеет координаты = {5, 1}. Придадим Z какое-либо значение, например Z = 5. Уравнение линии уровня Z = 5 задает на графике прямую 5x₁ + x₂ = 5 (рис. 3.8). Очевидно, что чем далее будет перемещаться прямая в направлении , тем большие значения будет принимать Z. Область, в которой возможны перемещения, ограничена синим многоугольником ОДР. Следовательно, наибольшее значение будет достигнуто в крайней точке ОДР. Эта точка — (х_1орt,x_2opt). Именно в ней и достигается оптимальное решение, при котором Z будет наибольшим из всех возможных. Дальнейшее перемещение линии уровня за пределы ОДР будет приводить к росту Z, однако вне ОДР решения не имеют смысла, т. к. в этих точках будут нарушены ограничивающие условия. Содержательно это означает, что выполнение какой-либо производственной программы (x₁, x₂), «расположенной» вне области допустимых решений, невозможно из-за отсутствия достаточного для ее реализации запаса ресурсов.

 

Z=13

Z=5

-Вектор-градиент

X1

X1+2x2=4

3x1+2x2=12

2x1-x2=1

X₂

 

 

Рис.3.8.

а

Как следует из рис. 3.8, точка оптимума, в которой Z принимает наибольшее значение в ОДР, — это точка пересечения двух граничных прямых 3х₁ + 2х₂ = 12 и 2x₁ - х₂ = 1. Для того чтобы найти координаты точки, одновременно принадлежащей как первой, так и второй прямой, необходимо решить систему уравнений

3х₁ + 2х₂ = 12

2x₁ - х₂ = 1

Решая ее, находим

x_1opt = 2, x_2opt =3

Тогда максимальное значение целевой функции будет равно

Z_max =5 x_1opt + x_2opt = 5 • 2 + 3= 13

Таким образом, оптимальному решению соответствуют следующие значения переменных: x_lopt = 2, x_2opt = 3. Они обращают целевую функцию в максимум (Z_max = 13) и при этом удовлетворяют системе исходных ограничений.