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

Графический метод характеризуется простотой и наглядностью, однако он недостаточно точен и применим только для задач с не более чем тремя переменными. Последнее обусловлено тем, что человек, живущий в трехмерном пространстве, практически не способен представить себе визуально пространство более высокого порядка.

Метод основан на том, что каждое ограничение неравенство отсекает в n-мерном пространстве n-мерную полуплоскость (в данной курсовой работе это – двухмерное пространство (плоскость) и простая полуплоскость). Совокупность этих полуплоскостей (если ограничения совместны) образует n-мерный многогранник допустимых решений. Оптимальное решение достигается в одной из вершин многогранника. Для определения этой вершины необходимо построить поверхность уровня целевой функции (в курсовом проекте – линию уровня). Затем следует перемещать эту поверхность (линию) в направлении градиента до крайней точки области допустимых решений (ОДР).

Рассмотрим следующий простой пример решения задачи линейного программирования (ЗЛП) графическим методом.

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

2Х1+3Х2≤60;

3Х1+2Х2≤60;

4Х1+20Х2≤200;

Х1≥0; Х2≥0;

F=40Х1+30Х2→Мах.

Перейдем от неравенств к равенствам:

2Х1+3Х2=60;

3Х1+2Х2=60;

4Х1+20Х2=200.

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

для первого ограничения –

Х1=0; Х2=20;

Х2=0; Х1=30.

для второго ограничения –

Х1=0; Х2=30;

Х2=0; Х1=20.

для третьего ограничения –

Х1=0; Х2=10;

Х2=0; Х1=50.

Градиент целевой функции – это вектор, характеризующий направление и скорость изменения функции (в данном случае – целевой функции). Он определяется ее частными производными по каждой переменной:

Линия уровня целевой функции перпендикулярна градиенту.

Графическое решение данной задачи приведено на рисунке 6.1.

Рис. 6.1. Графическое решение задачи

Область допустимых решений (ОДР) в данном случае образуется четырехугольником ОВСД. Ни одна точка внутри его или на его границе не противоречит ни одному из ограничений. Оптимальное решение находится в одной из вершин четырехугольника. Для нахождения оптимального решения перемещаем линию уровня целевой функции в направлении градиента до крайней точки ОДР. Такой точкой является точка С с координатами: Х1=16; Х2=8. Значение целевой функции F=40×16+30×8=880. Очевидно, что это решение не отличается высокой точностью, что характерно для графического метода. Из рисунка видно, что ресурсы второго и третьего видов использованы полностью, а ресурс первого вида оказался в избытке. Для количественной оценки этого избытка определим сначала расход данного ресурса: 2×16+3×8=56. Запас равен 60, тогда остаток составит 60–56=4.

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

Графическим методом в основном решаются задачи с малым числом переменных. Он включает следующие этапы:

1. Строится многогранник решений.

Геометрический смысл системы ограничений состоит в следующем: уравнение a11x1 + ... + a1nxn = b1 представляет собой

гиперплоскость в n-мерном пространстве, неравенство же есть точки подпространства, лежащие по одну сторону от

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

программирования есть множество точек n-мерного пространства, причем это множество выпуклое и каждая точка является

решением системы неравенств.

2. Находятся вектор

и вершина многоугольника решений, на которой достигается max z.

Известно, что вектор-градиент функции z показывает направление наибольшего роста функции. Строится линия уровня c1x1

+...+ cnxn = h, проходящая через начало координат. Линия уровня обладает замечательным свойством: после подстановки

координат любой ее точки в выражение целевой функции z последняя принимает постоянное значение. Далее перемещаем

линию уровня в направлении вектора с до тех пор, пока не будет достигнута угловая вершина многоугольника решений либо

установлена неограниченность функции на множестве решений.

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

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

случаи, изображенные на следующих рисунках.

На первом рисунке изображен случай, когда целевая функция принимает максимальное значение в единственной точке M.

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

значения лишь тем, что линия уровня c1x1 +... + cnxn = h перемещается не в направлении вектора с, а в противоположном направлении.