Интернет магазин китайских планшетных компьютеров



Компьютеры - Графический метод решения задачи линейного программирования

22 января 2011





Область применения.


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

Пусть задача линейного программирования задана в двумерном пространстве, то есть ограничения содержат две переменные. Найти минимальное значение функции

:\ Z = c_1x_1 + c_2x_2\,

при

:\ a_{11}x_1 + a_{22}x_2 <= b_1,\ a_{21}x_1 + a_{22}x_2 <= b_2,\ \ldots\ ,\ a_{n1}x_1 + a_{n2}x_2 <= b_n;\:\ x_1>=0,\  x_2>=0\,

Допустим, что система при условии совместна и её многоугольник решений ограничен. Каждое из неравенств и, как отмечалось выше, определяет полуплоскость с граничными прямыми: a_{i1}x_1 + a_{i2}x_2 + a_{i3}x_3 = b_i,, x_1=0, x_2=0. Линейная функция при фиксированных значениях Z\, является уравнением прямой линии: c_1x_1 + c_2x_2 = const\,. Построим многоугольник решений системы ограничений и график линейной функции при Z = 0\,. Тогда поставленной задаче линейного программирования можно дать следующую интерпретацию. Найти точку многоугольника решений, в которой прямая c_1x_1 + c_2x_2 = const\, опорная и функция Z\, при этом достигает минимума.

Значения Z = c_1x_1 + c_2x_2\, возрастают в направлении вектора N =\,, поэтому прямую Z = 0\, передвигаем параллельно самой себе в направлении вектора N\,. Прямая дважды становится опорной по отношению к многоугольнику решений, причем минимальное значение принимает в точке A\,. Координаты точки A\, находим, решая систему уравнений прямых AB\, и AE\,.


Если многоугольник решений представляет собой неограниченную многоугольную область, то возможны два случая.

Случай 1. Прямая c_1x_1 + c_2x_2 = const\,, передвигаясь в направлении вектора N\, или противоположно ему, постоянно пересекает многоугольник решений и ни в какой точке не является опорной к нему. В этом случае линейная функция не ограничена на многоугольнике решений как сверху, так и снизу.

Случай 2. Прямая, передвигаясь, всё же становится опорной относительно многоугольника решений. Тогда в зависимости от вида области линейная функция может быть ограниченной сверху и неограниченной снизу, ограниченной снизу и неограниченной сверху, либо ограниченной как снизу, так и сверху.




Просмотров: 1190


<<< Билинейная интерполяция
Двоичное разбиение пространства >>>