Цех может производить стулья и столы. На производство стула идет 5 единиц материала, на производство стола - 20 единиц (футов красного дерева). Стул требует 10 человеко-часов, стол - 15. Имеется 400 единиц материала и 450 человеко-часов. Прибыль при производстве стула - 45 долларов США, при производстве стола - 80 долларов США. Сколько надо сделать стульев и столов, чтобы получить максимальную прибыль?
Обозначим: Х1 - число изготовленных стульев, Х2 - число сделанных столов. Задача оптимизации имеет вид:
45 Х1 + 80 Х2 → max,
5 Х1 + 20 Х2 ≤ 400,
10 Х1 + 15 Х2 ≤ 450,
Х1 ≥ 0,
Х2 ≥ 0.
В первой строке выписана целевая функция - прибыль при выпуске Х1 стульев и Х2 столов. Ее требуется максимизировать, выбирая оптимальные значения переменных Х1 и Х2. При этом должны быть выполнены ограничения по материалу (вторая строчка) - истрачено не более 400 футов красного дерева. А также ограничения по труду (третья строчка) - затрачено не более 450 часов. Кроме того, нельзя забывать, что число столов и число стульев неотрицательны.
Условия производственной задачи можно изобразить на координатной плоскости. Будем по горизонтальной оси абсцисс откладывать значения Х1, а по вертикальной оси ординат - значения Х2. Тогда ограничения по материалу и последние две строчки оптимизационной задачи выделяют возможные значения (Х1, Х2) объемов выпуска в виде треугольника (рис.1).
Таким образом, ограничения по материалу изображаются в виде выпуклого многоугольника, конкретно, треугольника. Прямая пересекает ось Х1, соответствующую стульям, в точке (80,0). Это означает, что если весь материал пустить на изготовление стульев, то будет изготовлено 80 стульев. Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,20). Это означает, что если весь материал пустить на изготовление столов, то будет изготовлено 20 столов. Для всех точек внутри треугольника выполнено неравенство, а в противном случае материал останется.
Аналогичным образом можно изобразить и ограничения по труду (рис.2).
Таким образом, ограничения по труду также изображаются в виде треугольника. Прямая пересекает ось Х1, соответствующую стульям, в точке (45,0). Это означает, что если все трудовые ресурсы пустить на изготовление стульев, то будет сделано 45 стульев. Та же прямая пересекает ось Х2, соответствующую столам, в точке (0,30). Это означает, что если всех рабочих поставить на изготовление столов, то будет сделано 30 столов. Для всех точек внутри треугольника выполнено неравенство, в противном случае часть рабочих будет не задействовано.
Мы видим, что очевидного решения нет - для изготовления 80 стульев есть материал, но не хватает рабочих, а для производства 30 столов есть рабочая сила, но нет материала, Значит, надо изготавливать и то, и другое. Но в каком соотношении?
Чтобы ответить на этот вопрос, надо "совместить" рис.1 и рис.2, получив область возможных решений, а затем проследить, какие значения принимает целевая функция на этом множестве (рис.3).
Таким образом, множество возможных значений объемов выпуска стульев и столов (Х1, Х2 ), или, в других терминах, множество А, задающее ограничения на параметр управления в общей оптимизационной задаче, представляет собой пересечение двух треугольников, т.е. выпуклый четырехугольник, показанный на рис.3. Три его вершины очевидны - это (0,0), (45,0) и (0,20). Четвертая - это пересечение двух прямых - границ треугольников на рис.1 и рис.2, т.е. решение системы уравнений
5 Х1 + 20 Х2 = 400,
10 Х1 + 15 Х2 = 450.
Из первого уравнения:
5 Х1 = 400 - 20 Х2,
Х1 = 80 - 4 Х2.
Подставляем во второе уравнение:
10 (80 - 4 Х2) + 15 Х2 = 800 - 40Х2 + 15 Х2 = 800 - 25 Х2 = 450,
Следовательно:
25 Х2 = 350,
Х2 = 14, откуда Х1 = 80 - 4 х 14 = 80 -56 = 24.
Итак, четвертая вершина четырехугольника - это (24, 14).
Надо найти максимум линейной функции на выпуклом многоугольнике. Основная идея линейного программирования состоит в том, что максимум достигается в вершинах многоугольника. В общем случае - в одной вершине, и это - единственная точка максимума. В частном - в двух, и тогда отрезок, их соединяющий, тоже состоит из точек максимума.
Целевая функция 45 Х1 + 80 Х2 принимает минимальное значение, равное 0, в вершине (0,0). При увеличении аргументов эта функция увеличивается. В вершине (24,14) она принимает значение 2200. При этом прямая 45 Х1 + 80 Х2 = 2200 проходит между прямыми ограничений 5 Х1 + 20 Х2 = 400 и 10 Х1 + 15 Х2 = 450, пересекающимися в той же точке. Отсюда, как и из непосредственной проверки двух оставшихся вершин, вытекает, что максимум целевой функции, равный 2200, достигается в вершине (24,14).
Ответ: Наилучшим вариантом является выпуск 24 стульев и 14 столов, при этом используется весь материал и все трудовые ресурсы, а прибыль равна 2200 у.е.