Графический метод

Справочник / Студент / Линейное программирование / Графический метод
Справочный материал Примеры Обратите внимание! Видео Модели Пройти тесты
Цель графического метода, в основном, сводится к наглядной иллюстрации решения ЗЛП, так как особенность таких задач состоит в том, что целевая функция достигает своего экстремума на границе области допустимых значений.
Задачи с двумя переменными всегда можно решить графически. Однако уже трехмерном пространстве решение осложняется, а в случае большего числа переменных становится и вовсе невозможным. 
Приведем алгоритм решения ЗЛП с двумя переменными графическим методом.
Задача:
LaTeX formula: max(min) f(X)=c_{1}x_{1}+c_{2}x_{2}; LaTeX formula: (12.16)
LaTeX formula: \left\{\begin{matrix} a_{11}x_{1} +a_{12}x_{2}\leq (\geq , =)b_{1},& & \\ a_{21}x_{1} +a_{22}x_{2}\leq (\geq , =)b_{2}, & & \\ ... & & \\ a_{m1}x_{1} +a_{m2}x_{2}\leq (\geq , =)b_{m}. & & \end{matrix}\right. LaTeX formula: (12.17)
1. Строим область допустимых значений целевой функции – графическое решение системы ограничений (12.17).
2. Строим вектор-градиент целевой функции (12.16), который указывает направление ее наискорейшего возрастания: LaTeX formula: \bar{c}(f{}'_{x_{1}};f{}'_{x_{2}}). 
В случае минимизации целевой функции строим вектор-антиградиент: LaTeX formula: - LaTeX formula: \bar{c}(f{}'_{x_{1}};f{}'_{x_{2}}).
3. Строим линию уровня LaTeX formula: F_{0}=0  (линию постоянного значения целевой функции), проходящую через начало координат перпендикулярно вектору LaTeX formula: \bar{c}.
4. В случае максимизации целевой функции перемещаем линию уровня LaTeX formula: F_{0}=0  вдоль вектора-градиента так, чтобы она касалась ОДЗ в ее крайней точке (до ее разрешающего положения), и строим линию LaTeX formula: F_{max} . В случае минимизации целевой функции перемещаем линию уровня LaTeX formula: F_{0}=0  вдоль вектора-антиградиента так, чтобы она касалась ОДЗ в ее крайней точке, и строим линию LaTeX formula: F_{min} .
5. Определяем оптимальный план LaTeX formula: X^{*}=(x^{*}_{1};x^{*}_{2})  и оптимальное значение целевой функции LaTeX formula: f^{*}(X^{*})=c_{1}x^{*}_{1}+c_{2}x^{*}_{2}.
Пример 1. Решите графическим методом задачу:
LaTeX formula: max(min) f(X)=3x_{1}+2x_{2}; \left\{\begin{matrix} -3x_{1}+5x_{2}\leq 5, & \\ 4x_{1}+5x_{2} \geq 40; & \end{matrix}\right. x_{1}\geq 0, x_{2}\geq 0.   
Решение. 1. Построим область допустимых значений целевой функции – графическое решение системы ограничений.
Найдем решение первого неравенства системы ограничений. Для этого построим прямую LaTeX formula: -3x_{1}+5x_{2}= 5 (1) (рис. 12.1). Подставим в неравенство LaTeX formula: -3x_{1}+5x_{2}\leq 5  координаты любой точки плоскости, например точки LaTeX formula: O(0;0).  Так как получили верное числовое неравенство LaTeX formula: 0\leq 5, то решением данного неравенства является часть полуплоскости, содержащая точку LaTeX formula: O(0;0). 
Аналогично найдем решение второго неравенства системы ограничений. 
Пересечение решений неравенств системы ограничений и образуют ОДЗ целевой функции. А так как переменные неотрицательные, то решение системы неравенств будет находиться только в первой четверти координатной плоскости (рис. 12.1).
2. Построим вектор-градиент целевой функции: LaTeX formula: \bar{c}(f{}'_{x_{1}};f{}'_{x_{2}}) , LaTeX formula: \bar{c}(3;2)  (рис. 12.2).
3. Построим линию уровня LaTeX formula: F_{0}=0, проходящую через начало координат перпендикулярно вектору LaTeX formula: \bar{c}  (рис. 12.2).
4. Из рисунка 12.2 видим, что линию уровня  LaTeX formula: F_{max} построить невозможно, так как целевая функция в направлении вектора-градиента не ограничена. Линия уровня LaTeX formula: F_{min}  проходит через точку LaTeX formula: A, координаты которой найдем, решая систему уравнений:
 LaTeX formula: \left\{\begin{matrix} -3x_{1}+5x_{2}= 5, & \\ 4x_{1}+5x_{2} =40; & \end{matrix}\right. \left\{ \begin{array}{lcl} 7x_{1}=35, \\ 4x_{1} +5x_{2}=40;& \end{array} \right. \left\{\begin{matrix} x_{1}=5 & \\ x_{2}=4. & \end{matrix}\right.
5. Определяем оптимальный план LaTeX formula: X^{*}=(5;4)  и оптимальное значение целевой функции LaTeX formula: min f(X^{*})=3\cdot 5+2\cdot 4=23.
Ответ: LaTeX formula: min f(X^{*})=23.
Пример 2. Решите графическим методом задачу:
LaTeX formula: max f(X)=2x_{1}-2x_{2}; \left\{ \begin{array}{lcl} x_{1} -2x_{2}\leq 0,& \\ x_{1}+x_{2} \geq 6,& \\ x_{2}\leq 5. & & \end{array} \right.
Решение. 1. Построим область допустимых значений целевой функции – графическое решение системы ограничений.
Найдем решение первого неравенства системы ограничений. Для этого построим прямую LaTeX formula: x_{1}-2x_{2}=0  (рис. 12.3). Подставим в неравенство LaTeX formula: x_{1}-2x_{2}\leq 0  координаты любой точки плоскости, например точки  LaTeX formula: (1;0). Так как получили неверное числовое неравенство LaTeX formula: 1\leq 0, то решением данного неравенства является часть полуплоскости, не содержащая точку LaTeX formula: (1;0) . 
Аналогично найдем решения второго и третьего неравенств системы ограничений. 
Пересечение решений неравенств системы ограничений и образуют ОДЗ целевой функции: треугольник LaTeX formula: ABC на рисунке 12.3. 
2. Построим вектор-градиент целевой функции:  LaTeX formula: \bar{c}(f{}'_{x_{1}};f{}'_{x_{2}}) , \bar{c}(2;-2)  (рис. 12.4).
3. Построим линию уровня LaTeX formula: F_{0}=0, проходящую через начало координат перпендикулярно вектору  LaTeX formula: \bar{c}.
4. Из рисунка 12.4 видим, что линия уровня LaTeX formula: F_{max}  проходит через точку LaTeX formula: C, координаты которой найдем, решая систему уравнений:
 LaTeX formula: \left\{\begin{matrix} x_{1}-2x_{2}=0, & \\ x_{2} =5;& \end{matrix}\right.\left\{\begin{matrix} x_{1}=10, & \\ x_{2}=5. & \end{matrix}\right.
5. Определяем оптимальный план LaTeX formula: X^{*}=(10;5)  и оптимальное значение целевой функции LaTeX formula: f(X^{*})=2\cdot 10-2\cdot 5=10.
Ответ: LaTeX formula: min f(X^{*})=10.
При построении ОДЗ целевой функции возможны следующие случаи:
1) линия уровня в разрешающем положении и ОДЗ имеют одну общую точку – задача имеет единственное решение;
2) линия уровня в разрешающем положении и ОДЗ имеют множество общих точек (отрезок, прямую) – задача имеет бесконечное множество решений; 
3) целевая функция не ограничена (ОДЗ – неограниченная область) – задача не имеет оптимального решения;
4) ОДЗ состоит из одной точки, в которой целевая функция достигает одновременно и максимума и минимума;
5) ОДЗ – пустое множество (задача не имеет решений).
Программа для просмотра моделей (МК-плеер)
© Сиротина И.К., 2013—2026