высшая математика
ВЫСШАЯ МАТЕМАТИКА

Главная >> Лекции >> Линейное программирование (ЛП) >>Графическое решение задачи ЛП

Графическое решение задачи ЛП

Если задача линейного программирования ЛП содержит только две переменные, то ее можно решить графически. В случае трех переменных графическое решение становится менее наглядным, а при большем числе переменных - даже невозможным. Несмотря на это, графическое решение позволяет сделать некоторые выводы, которые служат основой для разработки общего метода решения задач ЛП.

Пример 1. Мебельная фабрика выпускает книжные полки и шкафы. Их производство ограничено наличием необходимых ресурсов (древесно-стружечных плит (ДСП), высококачественных досок (ВД) и стекла). Нормы затрат ресурсов на единицу продукции, запасы ресурсов и прибыль от реализации единицы продукции приведены в табл. 1. Требуется составить производственный план выпуска продукции с учетом имеющихся, который обеспечил бы наибольшую прибыль.

Приведенные выше условия являются экономической постановкой задачи. Составим теперь математическую модель (постановку) задачи.

Табл. 1

Виды
ресурсов
Виды продукции Запасы
ресурсов
Полки Шкафы
ДСП
ВД
Стекло

3
2
2

2
4
3

27
28
23

Прибыль

4

7

 

 

Пусть x1и x2 - количество полок и шкафов соответственно, планируемое к выпуску. Тогда суммарная прибыль от реализации всей плановой продукции (целевая функция) составит z=4x1+7x2--->max.

При этом общий расход ДСП равен 3x1+2x2, и он не должен превышать имеющегося запаса 27. Это приводит к ограничению 3x1+2x2<=27. Аналогично учитываются ограничения по ВД и стеклу: 2x1+4x2<=28, 2x1+3x2<=23. Т.к. объемы выпускаемых изделий не могут быть отрицательными, то x1=>0, x2=>0. Т.о. математическая модель задачи имеет вид:

математическая модель задачи ЛП

Таким образом, задача состоит в том, чтобы найти неотрицательные значения x1 и x2, удовлетворяющие системе неравенств, для которых функция z принимает наибольшее значение.

Найдем решение Примера 1 графическим способом. Сначала строится область допустимых решений (ОДР), затем на ней ищется zmax. Начнем с геометрического представления ОДР. Условия (6) ограничивают ОДР первой четвертью.

Каждое из неравенств определяет на координатной плоскости x1Ox2 некоторую полуплоскость, а система неравенств - их пересечение. Находим полуплоскости, в которых выполняются данные неравенства. Для этого вследствие выпуклости любой полуплоскости достаточно взять произвольную точку, через которую не проходит соответствующая граничная прямая, и проверить, удовлетворяют ли эта пробная точка ограничению-неравенству.

Если удовлетворяет, то данное неравенство выполняется в полуплоскости, содержащую пробную точку. В противном случае берется полуплоскость, не содержащая пробной точки. В качестве пробной точки часто удобно брать начало координат O(0,0). Заметим, что при построении ОДР ограничения-неравенства (6) лучше переписать в виде уравнения прямой в отрезках:

границы ОДР в виде уравнения прямых в отрезках

Как известно, в уравнении прямой в отрезках числа, стоящие в знаменателях, показывают, сколько единиц отсекает прямая, соответствующая данному ограничению на той или иной оси. Например, в первом ограничении на оси Ox1отсекается 9 единиц, а на оси Ox2 - 27/2=13,5.

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

область ОДР

Кроме выпуклого многоугольника (рис. 1), ОДР может представлять собой неограниченную выпуклую многоугольную область (рис. 2а) или быть пустым множеством (рис. 2б) в этом случае задача ЛП не имеет решений по причине пустоты ОДР), а так же лучом, отрезком или точкой.

ОДР не ограничена или пуста

Перейдем к геометрической интерпретации целевой функции. Уравнение z=c1x1+c2x2 = 4x1+7x2 при фиксированном значении z=z0 определяет на плоскости прямую линию z0= 4x1+7x2. При изменении z получим семейство параллельных прямых, называемых линиями уровня. Вектор с=(с1; c2) с координатами из коэффициентов при x1 и x2 в целевой функции z перпендикулярен к каждой из линий уровня. вектор с (-с) показывает направление наибольшего возрастания (убывания) целевой функции.

Если построить на одном рисунке ОДР, вектор с и одну из линей уровня, например, z=0, то задача сводится к определению в ОДР точки в направлении вектора с (-с), через которую проходит линия уровня zmax (zmin), соответствующая наибольшему (наименьшему) значению функции z. Перпендикулярно к вектору с проводим линию уровня z=0 (на рисунке она пунктирная). Параллельным перемещением прямой z=0 находим крайнюю точку, в которой целевая функция достигает максимума рис. 3а.

геометрическое решение задачи ЛП

Т.к. точка B находится на пересечении прямых (2) и (3), то координаты точки B определяются системой уравнений

определение точки max из системы

откуда В(4;5) zmax=z(B)=4*4+7*5=51. Это и есть графический способ решения задачи ЛП.