Цель настоящей статьи — показать использование метода линейного программирования при решении текстовых задач по математике, предполагающих максимизацию (минимизацию) некоторой величины, например, объема выполняемой работы или объема получаемого денежного дохода. Данный метод имеет значение, например, при решении текстовых задач ЕГЭ с экономическим содержанием. Статья оформлена как результат выполнения проекта.
Задача линейного программирования заключается в изучении способов нахождения наибольшего или наименьшего значений некоторой линейной функции при наличии линейных ограничений [1, 2, 3].
Функция, наибольшее или наименьшее значение которой необходимо найти, называется целевой функцией, а совокупность значений переменных, удовлетворяющих ограничениям, определяет область решения.
Пусть ограничения заданы совместной системой m линейных неравенств с n переменными:
Среди неотрицательных решений этой системы требуется найти такое решение, при котором целевая функция линейного вида
принимает наибольшее (наименьшее) значение. Другими словами, необходимо максимизировать (минимизировать) линейную функцию L.
Покажем, как решается указанная задача геометрическим методом, для чего ограничимся рассмотрением совместной системы линейных неравенств с двумя и тремя переменными. Пусть, кроме того, задана линейная функция 
Найдем среди множества точек (
) из области решений (многоугольника решений) совместной системы неравенств такие, которые придают заданной линейной функции наибольшее (наименьшее) значение. Для каждой точки плоскости функция L принимает фиксированное значение 
. Множество всех таких точек есть прямая 
, перпендикулярная вектору 
, выходящему из начала координат. Если эту прямую передвигать параллельно самой себе в положительном направлении вектора 
, то линейная функция будет возрастать, а в противоположном направлении – убывать. Пусть при движении прямой L в противоположном вектору направлении она впервые встретится с многоугольником решений в его вершине, тогда в этом положении прямая L становится опорной и на этой прямой функция L принимает наименьшее значение. При движении в положительном направлении прямая L пройдет через другую вершину многоугольника решений при выходе из области решений, и станет также опорной прямой 
, на ней функция L принимает наибольшее значение среди всех значений, принимаемых на многоугольнике решений.
Таким образом, минимизация и максимизация линейной функции на многоугольнике решений достигаются в точках пересечения этого многоугольника с опорными прямыми, перпендикулярными вектору . Опорная прямая может иметь с многоугольником решений либо одну общую точку (вершина многоугольника), либо бесконечное множество точек (сторона многоугольника).
Аналогично, линейная функция трех переменных
примет постоянное значение на плоскости, перпендикулярной вектору 
. Наименьшее и наибольшее значение этой функции на многограннике решений достигаются в точках пересечения этого многогранника с опорными плоскостями, перпендикулярными вектору . Опорная плоскость может иметь с многогранником решений либо одну общую точку (вершину многоугольника), либо бесконечное множество точек (это множество есть ребро или грань многогранника).
Рассмотрим практические задачи.
Задача 1: Предприятие имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика — 400000 руб., пятитонного — 500000 руб. Предприятие может выделить для приобретения автомашин 14,1 млн. руб. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?
Составим математическую модель задачи. Пусть х1 — количество трехтонных автомашин, х2 — количество пятитонных. По условию задачи 0≤х1≤19, 0≤х2≤17. На приобретение грузовиков необходима сумма 400000х1+500000х2, при этом она должна удовлетворять неравенству 400000х1+500000х2≤14100000. Теперь введем целевую функцию — грузоподъемность автомашин L=3х1+5х2. Таким образом, задача заключается в максимизации целевой функции L=3х1+5х2 при следующих ограничениях:
Решим эту задачу графическим методом (рис.1). Построим область допустимых решений задачи, задаваемую следующими прямыми:
400000
+500000
=14100000 (I),
х1=19 (II),
=17(III).
Рис.1. Графическое решение задачи 1
Область решений — многоугольник ABCDO, в одной из вершин которого достигается максимум функции. Построим линию уровня 3х1+5х2=0 и вектор
. Будем передвигать линию уровня, пока она не выйдет из многоугольника ABCDO, что произойдет в точке В с координатами (14;17). В этой точке функция принимает максимальное значение, равное 127. Чтобы достичь этого значения грузоподъемности, нужно приобрести 14 трехтонных и 17 пятитонных грузовиков.
Задача 2: Предприятие выпускает два вида продукции: А и Б. На изготовление единицы продукции вида А требуется затратить 2 кг сырья первого типа, 3 кг сырья второго типа, 5 кг сырья третьего типа. На изготовление единицы продукции вида Б требуется затратить 5 кг сырья первого типа, 4 кг сырья второго типа, 3 кг сырья третьего типа. Производство обеспечено сырьем каждого типа в количестве 432 кг, 424 кг, 582 кг соответственно. Рыночная цена единицы продукции вида А составляет 34 тыс. руб., а единицы продукции вида Б — 50 тыс. руб. Какое количество продукции вида А и вида Б необходимо выпустить для получения максимальной выручки?
Решение: Пусть 
- необходимое для получения максимальной выручки количество продукции вида А и вида Б.
Тогда с учетом ограничений на сырье можно записать следующую систему неравенств:
Последние два условия записаны по смыслу задачи - количество продукции не может быть отрицательной величиной.
Целевая функция, выражающая получаемую от реализации продукции выручку:
Нужно найти максимум 
. Построим в системе координат x1Ox2 соответствующие неравенствам граничные прямые (рис. 2):
Найдем координаты точек, через которые проходят прямые:
(216; 0) и (0; 86,4)(1)
(141,3; 0) и (0; 106)(2)
(116,4; 0) и (0; 194)(3)
Решением каждого неравенства системы ограничений является полуплоскость, содержащая граничную прямую и расположенная по одну сторону от нее.
Областью допустимых решений является фигура ABCOE.
Рис.2. Графическое решение задачи 2
Строим вектор целевой функции 
, координаты которого 
равны коэффициентам целевой функции. Перпендикулярно к нему проводим линию уровня.
Далее перемещаем линию уровня в направлении вектора 
, пока она не выйдет из области допустимых решений в некоторой крайней точке. Координаты этой точки и будут являться решением. В нашем случае условию максимизации соответствует точка А. Координаты точки А находим, решив систему уравнений (1) и (2):
Решение системы: 
При этом максимум целевой функции будет равен:
Таким образом, необходимо выпускать 56 изделий вида А и 64 изделия вида Б. При этом будет обеспечена максимальная выручка от реализации изделий, которая составит 5 млн. 104 тыс. руб.
Заключение. Метод линейного программирования при решении текстовых задач графически имеет следующий алгоритм:
− записать систему неравенств и выражение для целевой функции;
− построить область допустимых решений на графике;
− построить вектор целевой функции и найти на области решений точку, соответствующую условию задачи;
− найти решение.
Метод может быть использован при решении текстовых задач ЕГЭ, имеющих экономическое содержание.
Литература:
1. Шикин Е. В., Чхартишвили А. Г. Математические методы и модели. – М., Издательство «КДУ», 2009, 440 с.
2. Садовничий Ю. В. ЕГЭ. Математика. Решение задач и уравнений в целых числах. – М., Издательство «Экзамен», 2015, 126 с.
3. Решение задачи линейного программирования графическим методом [Электронный ресурс]. URL: www. Mathburo.ru (дата обращения 15.04.2017).
