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

Рассмотрим графический способ решения задач линейного программирования на примере задач с двумя переменными, когда ограничения выражены неравенствами.

Запишем задачу линейного программирования с двумя переменными:

целевая функция:

ограничения:

. . .

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

Областью допустимых решений системы неравенств может быть:

· выпуклый многоугольник;

· выпуклая многоугольная неограниченная область;

· пустая область;

· луч;

· отрезок;

· единственная точка.

Целевая функция определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение Z.

Вектор С = (с₁, с₂) с координатами с₁ и с₂, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор - направление убывания Z.

Если в одной и той же системе координат изобразить область допустимых решений системы неравенств и семейство параллельных прямых, то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z =const, и которая соответствует наибольшему значению параметра Z.

Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение.

Для практического решения задачи линейного программирования на основе ее геометрической интерпретации необходимо следующее:

1. построить прямые, уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки равенств;

2. найти полуплоскости, определяемые каждым из ограничений задачи;

3. определить многоугольник решений;

4. построить вектор C = (c₁,c₂);

5. построить прямую Z = c₁x₁ + c₂x₂ = 0, проходящую через начало координат и перпендикулярную вектору С;

6. передвигать прямую Z = c₁x₁ + c₂x₂ в направлении вектора С, в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов;

7. определить координаты точки максимума функции и вычислить значение целевой функции в этой точке.

Рассмотрим решение задачи об ассортименте продукции (условие задачи см. пример 1) геометрическим способом.

Решение

Построим многоугольник решений следующим образом. Для этого в системе координат Х10х2 на плоскости изобразим граничные прямые:

2x1 + 3x2 = 9 (L1)

3x1 + 2x2 = 13 (L2)

x1-x2 = 1 (L3)

x2 = 2 (L4)

x1 = 0

x2 = 0.

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

РИСУНОК стр 205 (Бережн)

Для построения прямой Z = 3x1 + 4x2 = 0 строим вектор-градиент С = (3,4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора С. Из рисунка .... следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке F, где функция принимает максимальное значение. Точка F лежит на пересечении прямых L1 и L3. Для определения ее координат решим систему уравнений:

2x1 +3x2 = 9

x1-x2 = 1.

Оптимальный план задачи: x1 = 2,4; x2 = 1,4. Подставляя значения x1 и x2 в линейную функцию получим:

Zmax = 3*2,4 + 4*1,4 = 12,8.

Полученное решение означает, что объем производства продукции П1 должен быть равен 2 ,4 ед., а продукции П2 - 1,4 ед. Доход, получаемый в этом случае, составит 12,8 д.е.

///////////////////////////////////////\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\\