Графический метод решения ЗЛП

 

Рассмотрим сначала простейший случай, когда в ЗЛП включены ровно две переменные:

(3.8)

Каждое из неравенств (a)-(b) системы ограничений задачи (3.8) геометрически определяет полуплоскость соответственно с граничными прямыми , Х1=0 и Х2=0. Каждая из граничных прямых делит плоскость х1Ох2 на две полуплоскости. Все решения исходного неравенства лежат в одной из образованных полуплоскостей (все точки полуплоскости) и, следовательно, при подстановке координат любой ее точки в соответствующее неравенство обращает его в верное тождество. С учетом этого и определяется та полуплоскость, в которой лежат решения неравенства, т.е. путем выбора любой точки из какой-либо полуплоскости и подстановки ее координат в соответствующее неравенство. Если неравенство выполняется для данной точки, то оно выполняется и для любой другой точки из этой же полуплоскости. В противном случае решения неравенства лежат в другой полуплоскости.

В том случае, если система неравенств (a)-(b) совместна, то область её решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей выпуклое, то область допустимых решений задачи (3.8) является выпуклое множество, которое называется многоугольником решений (введённый ранее термин “многогранник решений” обычно употребляется, если n 3). Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки точных равенств.

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

Эта точка существует тогда, когда многоугольник решений не пуст и на нём целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины строят линию уровня L: c1x1+c2x2=h (где h – некоторая постоянная), перпендикулярную вектору-градиенту и проходящую через многоугольник решений, и передвигают её параллельно вдоль вектора-градиента до тех пор, пока она не пройдёт через последнюю её общую точку пересечения с многоугольником решений (при построении вектора-градиента откладывают точку (с1; с2) в плоскости х1Ох2 и проводят к ней из начала координат направленный отрезок). Координаты указанной точки и определяют оптимальный план данной задачи.

Суммируя все выше изложенное, приведем алгоритм графического метода решения ЗЛП.

 

Алгоритм графического метода решения ЗЛП

1. Построить многоугольник решений, задаваемый системой ограничений исходной ЗЛП.

2. Если построенный многоугольник решений – пустое множество, то исходная ЗЛП решений не имеет. В противном случае построить вектор-градиент и провести произвольную линию уровня L, перемещая которую при решении задачи на максимум в направлении вектора (или в обратном направлении для задачи на минимум) определить крайнюю точку многоугольника решений, где и достигается максимум (минимум) целевой функции задачи.

3. Вычислить координаты найденной оптимальной точки , решив систему уравнений двух граничных прямых, пересекающихся в ней.

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

При графическом построении множества допустимых решений ЗЛП (многоугольника решений) возможны следующие ситуации:

1. Множество допустимых решений – замкнутый многоугольник:

a)

 
 

оптимальное решение достигается в единственной точке:

точка А – точка максимума, точка В – точка минимума;

b)
оптимальное решение достигается во всех точках грани (отрезка) многоугольника:

 

все точки отрезка АВ – оптимальные решения ЗЛП (точки максимума); максимальное значение целевой функции в этом случае находится подстановкой координат любой из этих точек в целевую функцию исходной задачи.

2. Множество допустимых решений – незамкнутый многоугольник:

 
 

В первом случае (рисунок слева) целевая функция не ограничена сверху на множестве допустимых решений и поэтому она не достигает своего максимального значения, на втором же рисунке (справа) иллюстрируется случай, когда целевая функция задачи не ограничена снизу на множестве допустимых решений и поэтому она не достигает своего минимального значения.

3.
Множество допустимых решений – пустое множество:

Данная ЗЛП решений не имеет.

Рассмотрим теперь случай, когда n-m=2, т.е. число переменных больше числа линейно независимых уравнений на 2.

Две из n переменных, например, x1 и х2, можно выбрать в качестве свободных, а остальные m сделать базисными и выразить их через свободные:

(3.9)

где - константы, полученные после алгебраических преобразований системы ограничений задачи (3.6), записанной в канонической форме, к виду (3.9).

Учитывая условия неотрицательности переменных: , систему равенств (3.9) можно записать в виде:

(3.10)

Подставляя в целевую функцию задачи (3.6) выражения (3.10) для базисных переменных, получим ЗЛП, приведенную к виду (3.8):

(3.11)

где - коэффициенты при переменных в целевой функции исходной ЗЛП после преобразования (3.10).

 

Задача (3.11) решается с помощью описанного выше алгоритма.

Рассмотрим примеры решения ЗЛП графическим методом для техническо-экономических задач, математические модели которых были построены в разделе 2.


Пример 3.1 Задача об использовании сырья (пример 2.1, раздел 2)

Математическая модель задачи имеет вид:

Математическая модель данной задачи содержит ровно n=2 переменные. Решаем ее с помощью описанного выше алгоритма.

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

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

  1. : (0; 3), (6; 0);
  2. : (3; 2), (4; 0);
  3. : (0; 1), (2; 3);
  4. ;
  5. .

 

Пятиугольник АВСDО – искомая область допустимых решений. Максимальное значение целевая функция задачи достигает на границе данного пятиугольника: либо в одной из его вершин, либо на одной из его граней. Чтобы выяснить этот вопрос, строим вектор-градиент , проводя направленный отрезок из начала координат в точку (3; 2), и перпендикулярную ему произвольную линию уровня L, перемещая которую по направлению вектора , находим крайнее положение, которое она займет в пересечении с областью допустимых решений АВСDО. Как видно из рис. 3.1, крайнее положение линия уровня займет в точке С, т.е. в данной точке целевая функция задачи достигает своего максимального значения на заданном множестве допустимых решений.

 

 
 

Координаты точки С вычисляем, решая систему уравнений прямых (1)-(2), пересекающихся в данной точке, т.е.:

 

, откуда .

 

Тогда максимальное значение целевой функции исходной задачи будет равно:

.

 

Пример 3.2 Задача о распределении руды (пример 2.6, раздел 2)

Математическая модель задачи имеет вид:

Данная задача содержит n>2 переменных. Поэтому преобразуем сначала неравенства системы ограничений задачи к равенствам, введя в левые части 2-го и 3-го ограничений дополнительные переменные х4 и х5 соответственно. Получим задачу:

Преобразованная ЗЛП имеет 3 линейно независимых ограничения-равенства (m=3) и 5 переменных (n=5), т.е. число свободных переменных задачи (k=n-m) равно 2. Значит, выразив базисные переменные х3, х4 и х5 через свободные переменные х1 и х2, получим:

После подстановки х3 в целевую функцию, 2-е и 3-е ограничения будем иметь задачу:

Учитывая условие неотрицательности переменных: , можно записать:

или

Последняя задача содержит ровно n=2 переменные и может быть решена графическим методом.

Строим область допустимых решений, задаваемую системой ограничений математической модели задачи (см. рис. 3.2).

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

  1. : (0; 10), (10; 0);
  2. : (0; 5), (10; 0);
  3. : (5; 0), (0; 20/3);
  4. .

Четырехугольник АВСD – искомая область допустимых решений. Минимальное значение целевая функция задачи достигает на границе данного четырехугольника: либо в одной из его вершин, либо на одной из его граней. Чтобы выяснить этот вопрос, строим вектор-градиент (для удобства построения и наглядности рисунка значения координат вектора-градиента удвоены) , проводя направленный отрезок из начала координат в точку (8; 10) и перпендикулярную ему произвольную линию уровня L, перемещая которую в направлении, обратном вектору (для задачи на минимум), находим крайнее положение, которое она займет в пересечении с областью допустимых решений АВСD. Как видно из рис. 3.2, крайнее положение линия уровня займет в точке С, т.е. в данной точке целевая функция задачи достигает своего минимального значения на заданном множестве допустимых решений.


 

Координаты точки С вычисляем, решая систему уравнений прямых (2)-(3), пересекающихся в данной точке, т.е.:

, откуда .

Тогда минимальное значение целевой функции задачи будет равно:

.

Используя обратные преобразования, вычисляем оптимальные значения всех переменных исходной задачи:

Таким образом, окончательно можно записать:

.