Графическое решение

Геометрическая интерпретация задачи ЛП.

В многомерном пространстве линейное уравнение или задает гиперплоскость с вектором нормали , которая является аналогом плоскости для (или прямой для ). Соответственно, линейное неравенство или задает замкнутое полупространство. Тогда система таких неравенств задает пересечение соответствующих полупространств, т.е. геометрически область ограничений G для задачи ЛП есть некоторый многомерный многогранник, называемый симплексом. Симплекс, как и обычные многогранники, является выпуклым телом, лежит по одну сторону от любой своей грани (содержит весь отрезок, соединяющий любые две свои точки).

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

Рис.6. Сравнение градиента и граней симплекса

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

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

Если градиент не перпендикулярен грани, то возможно движение по этой грани в направлении градиента, а точнее – в направлении проекции градиента на эту грань (рис.6, б) и, следовательно, увеличение значения целевой функции до перехода на следующую грань, для которой следует повторить эту процедуру. В итоге либо движение по симплексу неограниченно, т.е. неограниченно увеличивается целевая функция и у нее нет наибольшего значения (задача ЛП не имеет решения), либо через несколько шагов попадем на грань, перпендикулярную grad f (множество решений), либо окажемся в вершине, из которой невозможно движение в направлении градиента для увеличения значения целевой функции (вершина A на рис.7). В последнем случае получим единственное решение. Таким образом, оптимальное значение, если оно есть, достигается всегда по крайней мере в одной из вершин симплекса.

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

  Рис.7. Геометрическое решение задачи ЛП    

Пример 16. Решить задачу ЛП при ограничениях вида

Решение. Здесь – уравнение стороны I ; – уравнение стороны II ; – уравнение стороны III ; , grad f = .

По диаграмме взаимного расположения нормалей и градиента (рис.6, а) и по проекциям градиента на оси координат (рис.7) определим направления движения по границам области ограничений и оптимальное решение, т.е. вершину A (рис.7), координаты которой есть пересечение сторон II и III:

.

Заметим, что для построения области ограничений достаточно найти точки пересечения сторон I и II, II и III и точки пересечения осей координат и границы I (наименьшая точка пересечения на оси ) и границы II (наименьшая точка пересечения на оси ).

Дата добавления: 2017-02-01