Суть метода линейного программирования удобнее всего рассмотреть применительно к конкретной практической ситуации: допустим перед руководителем стоит задача разработать оптимальный план использования ресурсов при изготовлении двух видов продукции P1 и P2, используя три вида сырья: с1, с2, и с3 (показатели приведены в таблице 1). Этот план должен быть не только правильным, допустимым планом распределения ресурсов, по которому можно работать. Оптимальный план, кроме того, что должен удовлетворять перечисленным требованиям, должен быть еще и самым эффективным, либо приносящим максимум прибыли, либо ориентирован на минимум затрат (в нашем случае цель - максимизация прибыли).
Обозначим через х1 количество единиц продукции Р1, а через х2 – количество продукции Р2. Поскольку производство продукции ограниченно имеющимся в распоряжении предприятия сырьем и количество изготавливаемой продукции не может иметь отрицательное значение то должны выполняться ряд условий.
Потребности в сырье
Таблица 1
| Вид сырья | Запас сырья | Количество единиц сырья на изго- товление единицы продукции | |
| Р1 | Р2 | ||
| С1 | |||
| С2 | |||
| С3 | |||
| Прибыль от реализации одного изделия |
Учитывая количество единиц сырья, расходуемое на изготовление единицы продукции, а так же запасы сырья, можно записать математическое выражение данного условия поставленной задачи в виде системы ограничений:
12х1 + 4х2 ≤ 300,
4х1 + 4 х2 ≤120,
3х1 + 12 х2≤252,
х1, х2 ≥ 0.
которая показывает, что количество сырья, расходуемое на изготовление продукции, не может превышать имеющихся запасов.
Конечную цель решаемой задачи – получение максимальной прибыли от реализации продукции – выразим как функцию двух переменных х1 и х2.
Реализация х1 единиц продукции Р1 дает прибыль 30 х1, а реализация х2 единиц продукции Р2 дает прибыль 40х2. Суммарная прибыль будет равна:
L = 30х1 + 40х2
Необходимо найти такое значение х1 и х2, при которых функция L достигает максимума - это и будет целевая функция.
1 Если в условиях задачи не оговорена неделимость единицы продукции, то значения х1 и х2 могут быть и дробными числами.
Для нахождения решения сформулированной задачи, необходимо использовать ее геометрическую интерпретацию. Сначала определим многоугольник решений. Для этого в неравенствах системы ограничений и условиях не отрицательности переменных знаки неравенств заменим на знаки точных равенств и найдем соответствующие прямые:
12х1 + 4х2 = 300,
4х1 + 4 х2 = 120,
3х1 + 12 х2 = 252,
х1 = 0, х2 = 0.
Прямые изображены графически на рисунке 1. Каждая из построенных прямых делит плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой – нет. Чтобы определить искомую полуплоскость, нужно взять любую точку, принадлежащую, одной из полуплоскостей, и проверить, удовлетворяют ли ее координаты данному неравенству. Если координаты данной точки удовлетворяют данному неравенству, то полуплоскость, которой принадлежит эта точка является искомой, в противном случае – искомой будет другая полуплоскость.
После того, как на графике будут построены все прямые и определены все полуплоскости, удовлетворяющие неравенствам системы, необходимо определить области пересечения всех полуплоскостей. Пересечение всех полуплоскостей и определяет многоугольник решений и является областью допустимых решений (см. рис. 1). Как видно из рисунка 1 областью альтернативных решений является многоугольник ОАВСD. Координаты любой точки, принадлежащей этому пятиугольнику, удовлетворяют данной системе неравенств и условию не отрицательности значений переменных. Поэтому, сформулированная задача будет решена при определении координат любой точки принадлежащей многоугольнику ОАВСD, в которой функция L принимает максимальное значение.
Рис. 1. Многоугольник решений
Чтобы найти указанную точку, построим вектор С = (30, 40) и прямую 30х1 + 40х2 = h, где h – некоторая постоянная точка, такая, что прямая 30х1 + 40х2 = h имеет общие точки с многоугольником решений.
Например, h = 480 и построим прямую 30х1 + 40х2 = 480 (см. рис. 1). Далее, пологая h некоторому числу больше 480, мы будем получать различные параллельные прямые. Если они имеют общие точки с многоугольником решений, то эти точки определяют планы производства изделий P1 и P2, при которых прибыль от их реализации превзойдет 480 руб. Перемещая построенную прямую 30х1 + 40х2 = 480 в направлении вектора С, видно, что последней общей точкой ее с многоугольником решений задачи служит точка В. Координаты этой точки и определяют оптимальный план выпуска изделий P1 и P2, при котором прибыль от их реализации будет максимальной.
Определим координаты точки В как точки пересечения прямых
4х1 + 4 х2 = 120,
3х1 + 12 х2 = 252,
Решив эту систему уравнений, получаем х1 = 12, х2 = 18.
Следовательно, если предприятие изготавливает 12 изделий вида P1 и 18 изделий вида P2, то оно получит максимальную прибыль, равную 1080 рублей (см. рис 1).
Lmax = 30 * 12 + 40 * 18 = 1080.
. ИСХОДНЫЕ ДАННЫЕ ЗАДАНИЯ
Управленческая ситуация: для производства двух видов изделий (афиш) А и В предприятие использует три вида сырья (краску красную, бумагу, краску черную). Нормы расхода сырья каждого вида на изготовление единицы продукции данного вида приведены в таблице. Там же указаны прибыль от реализации одного изделия каждого вида и общее количество сырья данного вида, которое необходимо для производства. Принимаем, что сбыт обеспечен и что изделия А и В могут производиться в любых соотношениях. Перед менеджером по выпуску товара поставлена задача составить такой план выпуска при котором прибыль предприятия от реализации всех изделий была бы максимальной.
Варианты задачи:
Вариант 1
Вариант 2
Вариант 3
Вариант 4
Вариант5
Вариант 6
Вариант 7
Вариант 8
Вариант 9
Вариант 10
