Математические основы решения задачи линейного программирования графическим способом, Математический аппарат - Линейное программирование

Математический аппарат

Для понимания всего дальнейшего полезно знать и представлять себе геометрическую интерпретацию задач линейного программирования, которую можно дать для случаев n = 2 и n = 3.

Наиболее наглядна эта интерпретация для случая n = 2, т. е. для случая двух переменных x1 и x2. Пусть нам задана задача линейного программирования в стандартной форме

Возьмем на плоскости декартову систему координат и каждой паре чисел (x1, x2 )поставим в соответствие точку на этой плоскости.

Обратим прежде всего внимание на ограничения x1 ?0 и x2 ? 0. Они из всей плоскости вырезают лишь ее первую четверть (см. рис. 1). Рассмотрим теперь, какие области соответствуют неравенствам вида a1 x1 + a2 x2 ? b. Сначала рассмотрим область, соответствующую равенству a1 x1 + a2 x2 = b. Как Вы, конечно, знаете, это прямая линия. Строить ее проще всего по двум точкам.

Пусть b ? 0. Если взять x1 = 0, то получится x2 = b/a2. Если взять x2 = 0, то получится x1 = b/a1. Таким образом, на прямой лежат две точки (0, b/a2 ) и (b/a1, 0). Дальше через эти две точки можно по линейке провести прямую линию (рисунок 2).

Если же b=0, то на прямой лежит точка (0, 0). Чтобы найти другую точку, можно взять любое отличное от нуля значениеx1 и вычислить соответствующее ему значение x2.

Эта построенная прямая разбивает всю плоскость на две полуплоскости. В одной ее части a1 x1 + a2 x2 < b, а в другой наоборот a1 x1 + a2 x2 > b. Узнать, в какой полуплоскости, какой знак имеет место проще всего посмотрев, какому неравенству удовлетворяет какая-то точка плоскости, например, начало координат, т. е. точка (0, 0).

2. Теоретическое введение

Графический метод довольно прост и нагляден для решения задач линейного программирования с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи линейного программирования (1.2) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т. е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучом, одной точкой. В случае несовместности системы ограничений задачи (1.2) ОДР является пустым множеством.

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

Можно представить в виде системы двух неравенств (см. рис.2.1)

ЦФ при фиксированном значенииопределяет на плоскости прямую линию. Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

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

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположно направлению вектора.

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

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений - единственная точка; задача не имеет решений.

Похожие статьи




Математические основы решения задачи линейного программирования графическим способом, Математический аппарат - Линейное программирование

Предыдущая | Следующая