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

Программирования

Для решения задачи линейного программирования графическим методом выражение базисных переменных через свободные из (3.11) подставим в формулу (3.1), получим линейную функцию, зависящую от двух свободных переменных, то есть, Ф = Го + Г1· х1 + Г2· х2

Графический метод решения задачи линейного - student2.ru В системе координат х1Ох2 (рис. 3.2) - это уравнение прямой с угловым коэффициентом - Г12, перпендикулярную вектору-градиенту Графический метод решения задачи линейного - student2.ru , выходящему из начала координат.

Для каждой точки плоскости линейная функция принимает фиксированное значение Ф=Фi. При различных значениях Ф получим семейство параллельных прямых – линий уровня.

При x1 = x2 = 0 получим Фо= Го, то есть, при Фо = Го имеем прямую, проходящую через начало координат. Если эту прямую передвигать параллельно самой себе в положительном направлении вектора Г, то значение линейной функции Ф будет возрастать, а в противоположном направлении – убывать.

Пусть при движении прямой Ф в положительном направлении вектора Г она впервые встретится с многоугольником решений в одной из его вершин, например, в вершине А и принимает значение ФА. В этом положении прямая Ф становится опорной, и на этой прямой функция Ф принимает наименьшее из значений, принимаемых на многоугольнике решений, то есть, Фmin = ФА.

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

Таким образом, если число свободных переменных равно 2 (при любом числе базисных) решение ОЗЛП может быть получено простым геометрическим построением на плоскости.

Графический метод решения задачи линейного - student2.ru Аналогично, линейная функция трех переменных Ф=Го1·х12·х2+ Г3·х3 принимает постоянное значение на плоскости, перпендикулярной вектору Г(Г123). Наименьшее и наибольшее значения этой функции на многограннике решений достигаются в точках пересечения этого многогранника решения с опорными плоскостями, перпендикулярными вектору Г. Опорная плоскость может иметь с многогранником решений либо одну общую точку (вершину многогранника), либо бесконечное множество точек (ребро или грань многогранника).

Итак, если целевая функция задачи линейного программирования ограничена на многограннике решений, то:

1) каждый опорный план (допустимое базисное решение) соответствует угловой точке многогранника решений. Поэтому для решения ОЗЛП необходимо исследовать только угловые точки многогранника решений, т.е. только допустимые базисные решения (опорные планы).

2) существует такая угловая точка многогранника решений, в которой целевая функция достигает своего экстремума;

Идею графического метода решения задачи линейного программирования рассмотрим на конкретном примере.

Пример 3.1.Найти максимальное и минимальное значения

линейной функции Ф = 2·x1 + 2·x2

при ограничениях: 3·х1 – 2·х2 ≥ -6;

3·x1 + x2 ≥ 3;

х1 ≤ 3.

******************* РЕШЕНИЕ ********************************

Заменив в системе ограничений условно знаки неравенств знаками равенств, получим систему уравнений

3·x1 – 2·x2 = – 6 (1) ;

3·x1 + x2 = 3 (2);

x1 = 3 (3).

Построим по этим уравнениям прямые (рис. 3.1.1), затем согласно знакам неравенств выделим соответствующие полуплоскости, которые, пересекаясь, образуют общую часть – треугольник NPS.

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

Из начала координат построим вектор - градиент

Графический метод решения задачи линейного - student2.ru Графический метод решения задачи линейного - student2.ru {C1, C2} = (2; 2).

Затем через начало координат (то есть, при х1= х2 = 0) проведем линию уровня - прямую Фо ┴ Г, соответствующую значению целевой функции Фо = 0.

ФоÏОДР, перемещаем ее в направлении к ОДР. Так как направление перемещения прямой Ф совпадает с положительным направлением вектора Г, то значение целевой функции при этом возрастает.

Рис. 3.1.1
И в точке М (1, 0) прямая Ф впервые встречается с ОДР и становится опорной. В этой точке целевая функция достигает минимального (удовлетворяющего системе ограничений) значения, то есть, minФ = 2×1 + 2×0 = 2.

Двигаем линию уровня Ф дальше в том же направлении (в положительном направлении Г), при этом значение целевой функции продолжает расти. В точке Р(3; 15/2) линия уровня встречается с ОДР в последний раз. В этой точке функция Ф достигает наибольшего значения, (удовлетворяющего системе ограничений), то есть Фр= maxФ = 2∙3 + 2∙(15/2) = 21.

Ответ: minФ = 2 при ХМ = (1, 0),

maxФ = 21 при ХР = (3; 15/2).

*******************

Наши рекомендации