Пусть необходимо найти оптимальный план производства двух видов продукции ( x 1 и x 2 ), т.е. такой план, при котором целевая функция (общая прибыль) была бы максимальной, а имеющиеся ресурсы использовались бы наилучшим образом. Условия задачи приведены в табл. 3.1.
Таблица 3.1 – Данные о запасе и нормах расхода ресурсов
Вид продукции | Норма расхода ресурса на единицу продукции | Прибыль на единицу изделия | ||
А | В | С | ||
0,1 | 3,5 | |||
0,5 | ||||
Объем ресурса |
Оптимизационная модель задачи запишется следующим образом:
а) целевая функция:
б) ограничения:
(ограничение по ресурсу А ),
(ограничение по ресурсу B ),
(ограничение по ресурсу C );
в) условие неотрицательности переменных:
Данную и подобные оптимизационные модели можно продемонстрировать графически (рис. 3.3).
Преобразуем нашу систему ограничений, найдя в каждом из уравнений x 2 , и отложим их на графике. Любая точка на данном графике с координатами x 1 и x 2 представляет вариант искомого плана. Однако ограничение по ресурсу А сужает область допустимых решений. Ими могут быть все точки, ограниченные осями координат и прямой АА , так как не может быть израсходовано ресурса А больше, чем его на предприятии имеется. Если точки находятся на самой прямой, то ресурс используется полностью.
Аналогичные рассуждения можно привести и для ресурсов В и С . В результате условиям задачи будет удовлетворять любая точка, лежащая в пределах заштрихованного многоугольника. Данный многоугольник называется областью допустимых решений.
Рисунок 3.3.– Геометрическая интерпретация оптимизационной задачи линейного программирования
Однако нам необходимо найти такую точку, в которой достигался бы максимум целевой функции. Для этого построим произвольную прямую 4 x 1 + 5x 2 = 20, как x 2 = 4 - 4/ 5x 1 (число 20 произвольное). Обозначим эту линию РР . В каждой точке этой линии прибыль одинакова. Перемещая эту линию параллельно ее исходному положению, найдем точку, которая удалена от начала координат в наибольшей мере, однако не выходит за пределы области допустимых решений. Это точка М , которая лежит на вершине многоугольника. Координаты этой точки ( x' 1 = 3,03 и x' 2 = 7,4) и будут искомым оптимальным планом.