Для решения задачи линейного программирования графическим методом выражение базисных переменных через свободные из (3.11) подставим в формулу (3.1), получим линейную функцию, зависящую от двух свободных переменных, то есть, Ф = Го + Г1· х1 + Г2· х2
В системе координат х 1О х 2 (рис. 3.2) - это уравнение прямой с угловым коэффициентом - Г1/Г2, перпендикулярную вектору-градиенту , выходящему из начала координат.
Для каждой точки плоскости линейная функция принимает фиксированное значение Ф=Фi. При различных значениях Ф получим семейство параллельных прямых – линий уровня.
При x 1 = x 2 = 0 получим Фо= Го, то есть, при Фо = Го имеем прямую, проходящую через начало координат. Если эту прямую передвигать параллельно самой себе в положительном направлении вектора Г, то значение линейной функции Ф будет возрастать, а в противоположном направлении – убывать.
Пусть при движении прямой Ф в положительном направлении вектора Г она впервые встретится с многоугольником решений в одной из его вершин, например, в вершине А и принимает значение ФА. В этом положении прямая Ф становится опорной, и на этой прямой функция Ф принимает наименьшее из значений, принимаемых на многоугольнике решений, то есть, Фmin = ФА.
|
|
При дальнейшем движении в том же (положительном) направлении значение линейной функции продолжает расти и в какой-то момент прямая Ф пройдет через крайнюю точку ОДР, наиболее удаленную от начала координат в направлении перемещения (точка В), которая также является опорной; на ней функция Ф принимает значение ФВ, которая является наибольшей среди всех значений, принимаемых на многоугольнике решений, то есть, Фmax = ФВ.
Таким образом, если число свободных переменных равно 2 (при любом числе базисных) решение ОЗЛП может быть получено простым геометрическим построением на плоскости.
Аналогично, линейная функция трех переменных Ф=Го+Г1·х1+Г2·х2+ Г3·х3 принимает постоянное значение на плоскости, перпендикулярной вектору Г (Г1;Г2;Г3). Наименьшее и наибольшее значения этой функции на многограннике решений достигаются в точках пересечения этого многогранника решения с опорными плоскостями, перпендикулярными вектору Г. Опорная плоскость может иметь с многогранником решений либо одну общую точку (вершину многогранника), либо бесконечное множество точек (ребро или грань многогранника).
Итак, если целевая функция задачи линейного программирования ограничена на многограннике решений, то:
1) каждый опорный план (допустимое базисное решение) соответствует угловой точке многогранника решений. Поэтому для решения ОЗЛП необходимо исследовать только угловые точки многогранника решений, т.е. только допустимые базисные решения (опорные планы).
|
|
2) существует такая угловая точка многогранника решений, в которой целевая функция достигает своего экстремума;
Идею графического метода решения задачи линейного программирования рассмотрим на конкретном примере.
Пример 3.1. Найти максимальное и минимальное значения
линейной функции Ф = 2· x 1 + 2· x 2
при ограничениях: 3· х 1 – 2· х 2 ≥ -6;
3· x 1 + x 2 ≥ 3;
х 1 ≤ 3.
******************* РЕШЕНИЕ ********************************
Заменив в системе ограничений условно знаки неравенств знаками равенств, получим систему уравнений
3· x 1 – 2· x 2 = – 6 (1);
3· x 1 + x 2 = 3 (2);
x 1 = 3 (3).
Построим по этим уравнениям прямые (рис. 3.1.1), затем согласно знакам неравенств выделим соответствующие полуплоскости, которые, пересекаясь, образуют общую часть – треугольник NPS.
Из этого треугольника с учетом условия неотрицательности переменных выделим область допустимых решений (ОДР), представляющую собой четырехугольник MNPQ.
Из начала координат построим вектор - градиент
{C1, C2} = (2; 2).
Затем через начало координат (то есть, при х1= х2 = 0) проведем линию уровня - прямую Фо ┴ Г, соответствующую значению целевой функции Фо = 0.
ФоÏОДР, перемещаем ее в направлении к ОДР. Так как направление перемещения прямой Ф совпадает с положительным направлением вектора Г, то значение целевой функции при этом возрастает.
|
Двигаем линию уровня Ф дальше в том же направлении (в положительном направлении Г), при этом значение целевой функции продолжает расти. В точке Р(3; 15/2) линия уровня встречается с ОДР в последний раз. В этой точке функция Ф достигает наибольшего значения, (удовлетворяющего системе ограничений), то есть Фр= maxФ = 2∙3 + 2∙(15/2) = 21.
Ответ: minФ = 2 при ХМ = (1, 0),
maxФ = 21 при ХР = (3; 15/2).
*******************