Задачи линейного программирования (ЗЛП).
Методы решения ЗЛП.
1. Графический метод решения ЗЛП.
Лесхозу требуется не более 12 трехтонных машин и не более 10 пятитонных автомашин. Отпускная цена машины первой марки 2 тыс. ден. единиц, а второй марки — 4 тыс. ден. единиц. Лесхоз может выделить для приобретения автомашины 52 тыс. ден. единиц. Сколько следует приобрести автомашин каждой марки в отдельности, чтобы их общая (суммарная) грузоподъемность была максимальной?
Постройте математическую модель и решите задачу графическим методом.
Решение.
Составим математическую модель задачи. Предположим, что х1 машин будет куплено трехтонных, х2 машин – пятитонных. Тогда суммарная грузоподъемность машин будет равна z = 3x1+ 5x2 .
По смыслу задачи должны выполняться ограничения:
1) x1 ≤12, (не более 12 трехтонных машин);
2) x2 ≤10, (не более 10 пятитонных автомашин);
3) 2x1+ 4x2 ≤ 52 (лесхоз может выделить для приобретения автомашины 52 тыс. ден. единиц)
4) x1 > 0, x2 > 0.
Таким образом, получили задачу линейного программирования (ЗЛП) в нормальной форме:
Лесхозу требуется не более 12 трехтонных машин и не более 10 пятитонных автомашин. Отпускная цена машины первой марки 2 тыс. ден. единиц, а второй марки — 4 тыс. ден. единиц. Лесхоз может выделить для приобретения автомашины 52 тыс. ден. единиц. Сколько следует приобрести автомашин каждой марки в отдельности, чтобы их общая (суммарная) грузоподъемность была максимальной?
Постройте математическую модель и решите задачу графическим методом.
Решение.
Составим математическую модель задачи. Предположим, что х1 машин будет куплено трехтонных, х2 машин – пятитонных. Тогда суммарная грузоподъемность машин будет равна z = 3x1+ 5x2 .
По смыслу задачи должны выполняться ограничения:
1) x1 ≤12, (не более 12 трехтонных машин);
2) x2 ≤10, (не более 10 пятитонных автомашин);
3) 2x1+ 4x2 ≤ 52 (лесхоз может выделить для приобретения автомашины 52 тыс. ден. единиц)
4) x1 > 0, x2 > 0.
Таким образом, получили задачу линейного программирования (ЗЛП) в нормальной форме:
\[\begin{array}{l}
\left\{ \begin{array}{l}
{\rm{2}}{{\rm{x}}_{\rm{1}}} + {\rm{ 4}}{{\rm{x}}_{\rm{2}}} \le {\rm{52}}{\rm{,}}\\
{{\rm{x}}_{\rm{1}}} \le 12,\\
{{\rm{x}}_{\rm{2}}} \le 10;
\end{array} \right.\\
{{\rm{x}}_{\rm{1}}} \ge 0,{{\rm{x}}_{\rm{1}}}\, \ge 0\,\,\\
{\rm{3}}{{\rm{x}}_{\rm{1}}} + {\rm{ 5}}{{\rm{x}}_{\rm{2}}} \to \max
\end{array}\]
Решим задачу графическим методом. На плоскости х10x2строим область D. Для этого на плоскости построим (граничные) прямые (l1) 2x1+ 4x2=52,(l2) x2=10 ,(l3) x1=12 , (l4) x1=0,(l5) x2=0.
Подставляя координаты какой-нибудь точки, не лежащей на граничной прямой, в левую часть каждого из неравенств, установим, какие полуплоскости они определяют.
Пересечением полученных полуплоскостей будет область D пятиугольник ОAВСD. Из z получим gradz = {3; 5}; построим его (или вектор, сонаправленный ему) из начала координат. Построим линию уровня z = 0. Т. е. прямую Lu : 3x1 + 5x2 = 0 (она перпендикулярна grad z). Перемещая линию уровня параллельно самой себе в направлении вектора gradz, определяем, что в точке C целевая функция принимает максимальное значение (пунктирная линия на графике). Найдем координаты точки C (это точка пересечения прямых l1 и l2). X1 = 12, x2 =(52-2×12)/4=7
Таким образом, оптимальный план X* = (12; 7) и суммарная грузоподъемность
zmax = 3×12+ 5× 7 = 71 (тонны).
Ответ: X* = (12; 7) , zmax = 71.
Пересечением полученных полуплоскостей будет область D пятиугольник ОAВСD. Из z получим gradz = {3; 5}; построим его (или вектор, сонаправленный ему) из начала координат. Построим линию уровня z = 0. Т. е. прямую Lu : 3x1 + 5x2 = 0 (она перпендикулярна grad z). Перемещая линию уровня параллельно самой себе в направлении вектора gradz, определяем, что в точке C целевая функция принимает максимальное значение (пунктирная линия на графике). Найдем координаты точки C (это точка пересечения прямых l1 и l2). X1 = 12, x2 =(52-2×12)/4=7
Таким образом, оптимальный план X* = (12; 7) и суммарная грузоподъемность
zmax = 3×12+ 5× 7 = 71 (тонны).
Ответ: X* = (12; 7) , zmax = 71.