7.3. Графическое решение задачи линейного программирования
решения задач с двумя переменными, когда ограничения выражены неравенствами;
решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.
Запишем задачу линейного программирования с двумя переменными:
целевая функция:
^тах = СХХХ + С2*2; (7-34)
ограничения:
^21*1 +^22*2 — (7.35)
amxxx-vam2x2 Каждое из неравенств (7.35) — (7.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми aixxx + ai2x2 = bf> (і = 1,/w); хх = 0; х2 = 0. Областью допустимых решений системы неравенств (7.35) — (7.36) может быть: выпуклый многоугольник; выпуклая многоугольная неограниченная область; пустая область; луч; отрезок; единственная точка. Целевая функция (7.34) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значение Z. Вектор С = (сс2) с координатами С\ и с2, перпендикулярный этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор - направление убывания Z. Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (7.35) - (7.36) и семейство параллельных прямых (7.34), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. Для определения данной вершины построим линию уровня Z = qxj + ^2*2 = 0> проходящую через начало координат и перпендикулярную вектору С = (q;^), и будем передвигать ее в направлении вектора С = (cj;c2) до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты указанной точки и определяют оптимальный план данной задачи. Заканчивая рассмотрение геометрической интерпретации задачи (7.34) — (7.36), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 7.1 — 7.4. Рис. 7.1 харак- Рис. 7.1. Оптимум функции Z достижим в точке А > Х1 Рис. 7.4. Область допустимых решений — пустая область теризует такой случай, когда целевая функция принимает макси-мальное значение в единственной точке А. Из рис. 7.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 7.3 изображен случай, когда максимум недостижим, а на рис. 7.4 — случай, когда система ограничений задачи несовмест-на. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора С = (с^), а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения. Для практического решения задачи линейного программирования (7.34) — (7.36) на основе ее геометрической интерпретации необходимо следующее. Построить прямые, уравнения которых получаются в результате замены в ограничениях (7.35) — (7.36) знаков неравенств на знаки равенств. Найти полуплоскости, определяемые каждым из ограничений задачи. Определить многоугольник решений. Построить вектор С = (с1;с2). Построить прямую Z = + = 0, проходящую через начало координат и перпендикулярную вектору С. _ 6. Передвигать прямую Z = сххх + в направлении вектора С, в результате чего либо находят точку (точки), в которой целевая функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов. 7. Пример 7.10. Рассмотрим решение задачи об ассортименте продукции (пример 7.2) геометрическим способом. Решение Построим многоугольник решений (рис. 7.5). Для этого в системе координат Х{0Х2 на плоскости изобразим граничные прямые: 2*1 + Зх2 = 9 (Ьх); Зх{ + 2Х2 = 13 (L2); хх-х2 =1 (Z,3); *2 = 2 (L4). Взяв какую-либо точку, например начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Полуплоскости, определяемые неравенствами, на рис. 7.5 показаны стрелками. Областью решений является многоугольник OABCD. Для построения прямой Z= Зхх + 4;с2 = 0 строим вектор-градиент С = (3;4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z_= 0 перемещаем параллельно самой себе в направлении вектора С. Из рис. 7.5 следует, что по отноше-нию к многоугольнику решений опорной эта прямая становится в точке С, где функция принимает максимальное значение. Точка С лежит на пересечении прямых Lxn L3. Для определения ее координат решим систему уравнений: \2х{ +3х2 =9; \х\ —х2 = 1. Оптимальный план задачи хх = 2,4; х2=1,4. Подставляя значения хх и х2 в линейную функцию, получим: Zmax= 3-2,4 + 4- 1,4= 12,8. Полученное решение означает, что объем производства продукции П{ должен быть равен 2,4 ед., а продукции П2 — 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д. е. Рис. 7.5. Решение задачи линейного программирования геометрическим способом Геометрическим способом можно также решать задачи линейного программирования с числом переменных более двух. Для этого исходную задачу преобразуют методом Жордана—Гаусса (приложение 11). Пример 7.11. х\ ~х2 +4*3 -2X4 =2 - Зхі +2x2 +4x4 =3; X/ > 0, / = 1,4 Zmax = 4Xj - 2х2 + Х3 - Х4. Используя метод Жордана—Гаусса, произведем два полных исключения Xj и х4:
-1 4 -2 2 4 1 -1 4 2 4
2-14 3 И 0 5 -13 |10| -3 -1
1 0 1,4 0 1,4 3,2
0 0,5 -1,3 1 -0,3 -0,1
В результате приходим к системе X] +1,4хз =1,4; откуда 0,5x2 - 1,3хз + х4 = -0,3, х\ =1,4-1,4хз; х4 = -0,3 - 0,5Х2 + 1,Зх3. Подставляя эти значения в линейную функцию Z и отбрасывая в последней системе базисные переменные, получим задачу, выра- женную только через свободные неизвестные *2 и *3. Z= 5,9-5,9*3-1,5*2 при следующих ограничениях: *3 < 1; 0,5х2 - 1,3*з ^ °>3- Построим многоугольник решений и линейную функцию в системе координат Х20Х3 (рис. 7.6). Согласно рис. 7.6 линейная функция принимает максимальное значение в точке А, которая лежит на пересечении прямых Ь2 и Х2 = 0. Ее координаты (0;0,23). Максимальное значение функции ^шах = 5,9 - 5,9 • 0,23 - 1,5 . 0 - 4,54. Для отыскания оптимального плана исходной задачи подставляем в преобразованную систему *2 и *3.Окончательно получаем Х= (1,078; 0; 0,23; 0,001).