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

Двумерная задача линейного программирования – задача линейного программирования, количество переменных которой равно 2.

В общем виде двумерную задачу линейного программирования можно представить следующим образом.

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

F = c₁x₁+c₂x₂ → max(min) при ограничениях на переменные

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

Множество точек называется выпуклым, если оно вместе с любыми двумя точками содержит и их произвольную выпуклую комбинацию.

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

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

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

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

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

3. Строят многоугольник решений.

4. Строят векторN(с₁, c₂), который указывает направление возрастания целевой функции.

5. Строят начальную прямую целевой функции с₁х₁ + с₂х₂ =0 и затем передвигают ее в направлении вектора N до крайней угловой точки многоугольника решений. В результате находят точку, в которой целевая функция принимает максимальное значение, либо множество точек с одинаковым максимальным значением целевой функции, если начальная прямая сливается с одной из сторон многоугольника решений, либо устанавливают неограниченность сверху функции на множестве планов.

6. Определяют координаты точки максимум функции и вычисляют значение целевой функции в этой точке.

Минимальное значение линейной функции цели находится путем передвижения начальной прямой с₁х₁ + с₂х₂ = 0 в направлении, противоположном вектору N(c_1,c₂).