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

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

Справочник / Студент / Линейное программирование /

Справочный материал Примеры Обратите внимание! Видео Модели Пройти тесты

Цель графического метода, в основном, сводится к наглядной иллюстрации решения ЗЛП, так как особенность таких задач состоит в том, что целевая функция достигает своего экстремума на границе области допустимых значений.

Задачи с двумя переменными всегда можно решить графически. Однако уже трехмерном пространстве решение осложняется, а в случае большего числа переменных становится и вовсе невозможным.

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

Задача:

$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.$

Найдем решение первого неравенства системы ограничений. Для этого построим прямую $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) ОДЗ – пустое множество (задача не имеет решений).

Программа для просмотра моделей (МК-плеер) Файлы для скачивания