Задачи линейного программирования. I. Задачи линейного программирования

I. Задачи линейного программирования

Раздел 1

Геометрический (графический) метод решения

Рассмотрим задачу линейного программирования в стандартной форме, содержащую две переменные:

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

Алгоритм геометрического метода решения

задачи линейного программирования.

1. Сначала строится многоугольная область допустимых решений (ОДР), соответствующая ограничениям. Далее строится вектор-градиент линейной формы .

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

3. Для нахождения максимума прямая (перпендикулярная вектору-градиенту) передвигается в направлении этого вектора до тех пор, пока не покинет пределов многоугольной области. Предельная точка (или точки) области при этом движении и является точкой максимума.

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

Для нахождения минимума прямая передвигается в направлении противоположном направлению вектора-градиента до тех пор, пока не покинет пределов многоугольной области. Предельная точка (или точки) области при этом движении и является точкой минимума.