2014-02-02
1243
Рассмотрим задачу линейного программирования с двумя переменными 
.
Пусть геометрическим изображением системы ограничений является многоугольник (рис.4.1). Чтобы решить задачу необходимо среди вершин этого многоугольника найти вершину, в которой функция цели принимает минимальное значение.
Рис. 4.1.
| Рассмотрим линию уровня линейной функции Q(x), то есть линию вдоль которой эта функция принимает одно и то же фиксированное значение a. График этой линии задается уравнением
|
Для различных значений величины a линии уровня линейной функции параллельны. Одно из свойств линий уровня линейной функции состоит в том, что при параллельном смещении линии в одну сторону значение функции только возрастает, а при смещении в другую сторону – только убывает. Направление, в котором следует осуществлять сдвиг, чтобы достичь меньших значений целевой функции, можно найти построением другой линии уровня. Путем параллельного переноса прямой Q(x)=a в направлении меньших значений целевой функции достигают того, что эта прямая будет пересекать допустимую область решений (многоугольник) по части ее границы – множеству точек Р. (В общем случае параллельная прямая может пересекать допустимую область в одной точке, по отрезку, лучу или прямой.) Все другие допустимые точки лежат на линиях уровня, принадлежащих большим значениям целевой функции. Все точки, лежащие на линиях уровня с меньшими значениями, являются не допустимыми. Таким образом, множество точек Р является множеством оптимальных решений.
|
|
|
Пример. Решить геометрическим методом следующую задачу линейного программирования:
