 |
|
Алгоритм геометрического метода ЛП
1. Строят прямые (3.4), и определяют полуплоскости (3.1) и (3.2). При этом необходимо учесть, что в силу условий (3.2), рисунок должен всегда находиться в первой координатной четверти, т. е. не заходить за начало координат ни левее, ни ниже. Затем определяют многоугольник решений. Если получили случай, представленный на рис. 5, то решений нет.
2. Строят градиент целевой функции, а именно вектор 
. Строят перпендикулярную градиенту линию уровня целевой функции, проходящую через начало координат 
.
Передвигаем линию уровня вдоль градиента параллельно самой себе и визуально определяем точки экстремума.
3. Определяют координаты точки максимума (минимума) целевой функции. Для этого решают систему уравнений прямых, точками пересечения которых является точка максимума (минимума). Затем подставляют координаты этих точек в целевую функцию и находят значение функции в этих точках.
Пример. Найдем наибольшее и наименьшее значения целевой функции Fпри заданных ограничениях:
Строим прямые (3.4), уравнения которых получаются в результате замены в ограничениях знаков неравенств на знаки точных равенств:
Определяем полуплоскость, соответствующие исходным неравенствам. В результате пересечения всех полуплоскостей находим многоугольник решений. Это будет треугольник ABC.
Построим градиент целевой функции 
и перпендикулярную ему прямую. Передвигая линию уровня вдоль градиента и перпендикулярно градиенту, находим, что максимум достигается в точке А, а минимум в точке В.
Рис.6.
Определим координаты точек максимума и минимума целевой функции и вычислим значения функции в найденных точках.
Точка максимума лежит на пересечении прямой (3) и горизонтальной осью системы координат, которая задается уравнением 
:
Точка минимума лежит на пересечении прямой (2) и горизонтальной осью системы координат:
Подставляем координаты найденных точек в целевую функцию. Минимальное значение целевой функции
.
Максимальное значение целевой функции
.