Графический метод

Графическим методом в основном решаются задачи с малым числом переменных. Он включает следующие этапы:

1. Строится многогранник решений.

Геометрический смысл системы ограничений состоит в следующем: уравнение представляет собой гиперплоскость в n-мерном пространстве, неравенство же есть точки подпространства, лежащие по одну сторону от гиперплоскости и образующие выпуклое множество. Следовательно, система ограничений (1.2) задачи ЛП есть множество точек n-мерного пространства, причем это множество выпуклое и каждая точка является решением системы неравенств.

2. Находятся вектор и вершина многоугольника решений, на которой достигаетсяmax z.

Известно, что вектор-градиент функции z показывает направление наибольшего роста функции. Строится линия уровня , проходящая через начало координат. Линия уровня обладает замечательным свойством: после подстановки координат любой ее точки в выражение целевой функции z последняя принимает постоянное значение. Далее перемещаем линию уровня в направлении вектора до тех пор, пока не будет достигнута угловая вершина многоугольника решений либо устанавлена неограниченность функции на множестве решений.

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

Замечание. При нахождении решения задачи ЛП графическим методом могут встретиться случаи, изображенные на следующих рисунках.

На первом рисунке изображен случай, когда целевая функция принимает максимальное значение в единственной точке M. Из второго рисунка видно, что максимальное значение целевая функция принимает в любой точке отрезка AB. На третьем рисунке изображен случай, когда целевая функция не ограничена сверху на множестве допустимых решений.

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

Дата добавления: 2015-11-14