2.2 ГРАФИЧЕСКАЯ ИЛЛЮСТРАЦИЯ ПРОЦЕССА НАХОЖДЕНИЯ РЕШЕНИЯ ПОСТАВЛЕННОЙ ЗАДАЧИ
Каждое из n ограничений на объемы продаж
xmax > xt > xmln, / = 1, 2, ..., n
представляет собой выпуклый многогранник, лежащий в неотрицательной области n-мерного евклидова пространства Еп.
Каждое из m ограничений-неравенств
S ajjxi < bj , j = m i =1
определяет замкнутое полупространство в Еn, а именно множество точек, либо принадлежащих гиперплоскости, либо расположенных по одну сторону от нее.
Пересечение замкнутых полупространств из Еn представляет собой выпуклое многогранное множество, или также выпуклый многогранник, если это множество ограничено.Таким образом, допустимое множество решений, т.е. множество всех векторов x, удовлетворяющих m + n ограничениям объему продаж и расходу ресурсов (2.2), представляет собой замкнутое выпуклое многогранное множество, расположенное в неотрицательной области n-мерного евклидова пространства
S j = bj
i =1
jx є Er
Поверхность уровня целевой функции
{x є E" | qx = сопбі;}
представляет собой гиперплоскость в Еп. Если придавать константе q различные значения, то получим семейство параллельных гиперплоскостей. Направление наискорейшего роста задается градиентом, т.е. вектором-строкой из Е , ортогональным к поверхности уровня
dQ
— = q.
dx
С геометрической точки зрения задача линейного программирования состоит в отыскании точки (или множества точек) в Еп, принадлежащей допустимому выпуклому многогранному множеству, в которой достигается поверхность наибольшего уровня [19]. Из геометрических представлений ясно, что если решение существует, то оно не может быть внутренней точкой, а должно принадлежать границе допустимого множества. Следовательно, решением может являться точка, принадлежащая одной или нескольким граням, или, что эквивалентно, решением является одна вершина или несколько вершин и все точки, лежащие между этими вершинами, т.
е. все выпуклые линейные комбинации этих вершин [19].В случае, когда решение достигается в двух вершинах (на всей грани), т. е. когда решение не един-ственно, угол наклона параллельных линий уровня равняется углу наклона наивысшей граничной гиперплоскости. Решение достигается в двух вершинах и во всех точках прямой, соединяющей эти вершины. В трехмерном пространстве решением может быть точка вершины (пересечение трех или больше граней), отрезок прямой (пересечение двух граней) или часть некоторой плоскости (грань). Хотя решение может быть неединственным, максимальное значение целевой функции единственно.
Так как допустимое множество выпукло, а целевая функция линейна, то по теореме о достаточных условиях существования максимума локальный максимум является глобальным. Следовательно, если в вершине допустимого множества целевая функция принимает значение большее (или равное), чем во всех соседних вершинах, то данная вершина является решением задачи.
Так как целевая функция непрерывна, а допустимое множество замкнуто, то по теореме Вей- ерштрасса решение существует в том случае, если допустимое множество не пусто и ограничено.
Рассмотрим ряд конкретных примеров поставленной задачи (2.1) - (2.4) с целью иллюстрации отличий процесса нахождения решения от стандартной постановки задачи линейного программирования.
Задача 1 Пусть планируются к продаже два продукта: x1 и x2 на одном временном интервале [параметр t в модели (2.1) - (2.4) опущен]. Коэффициент дисконтирования равен единице. Целевая функция имеет следующий вид: Q = 10x1 + 15x2 - I, т.е. существует один вариант прибыли от единицы продукции и максимального объема продаж. Начальный запас ресурсов b0 = (4000, 7000, 4000). Система ограничений следующая:
250 x 1 +150 x 2 < b11, 350 x 1 + 250 x 2 < b12, 100 x 1 + 200 x 2 < b13, 0 < x 1 < 20, 0 < x 2 < 30.
Тогда максимально допустимый расход ресурсов bmax = (250-20 + + 150-30 = 9500; 350-20 + 250-30 = 14500; 100-20 + 200-30 = 8000).
Пусть увеличение запаса ресурса 1 на 100 единиц потребует инвестиций в размере А/1 = 5, ресурса 2 на 100 единиц - А/2 = 3, ресурса 3 на
100 единиц - А/3 = 6.
Тогда для выполнения максимальной производственной программы, требующей запас ресурсов b1max, необходимы инвестиции в размере: /(b0, b1max) = 275 + 225 + 240 = 740. Целевая функция примет вид: Q = 10х1 + 15х2 - 740.На рис. 2.1 представлены три различных варианта взаимного расположения системы ограничений и целевой функции:
1 Вариант для Qmin, L1mln, L2mln, L3mln. Он соответствует "минимальному" расходу ресурсов b0 = (4000, 7000, 4000). При этом величина инвестиций в увеличение запаса ресурсов /(b0, b0) = 0. Тогда целевая функция имеет вид: Qmln = 10х1 + 15х2.
Рис. 2.1 Графическая иллюстрация задачи 1
:L1, L2, L3 - ограничения на максимальный расход ресурсов; Q - целевая функция; х1 < 20 и х2 < 30 - ограничения на максимальный выпуск продукции;
ОДР - область изменения расположения допустимых решений задачи оптимизации
Вариант для Qmax, L1max, L2max, L3max. Он соответствует "максимальному" расходу ресурсов b1max = (9500, 14500, 8000). При этом величина инвестиций в увеличение запаса ресурсов /(b0, b1max) = 740. Тогда целевая функция имеет вид: Qmax = 10х1 + 15х2 - 740.
Вариант для Q', L' L2, L3. Данный вариант является промежуточным между первым и вторым ("минимальным" и "максимальным" или "безинвестиционным" и вариантом с максимальными инвестициями в увеличение запаса ресурсов предприятия). При этом b1' = (6000, 10000, 5000), величина инвестиций /(b0, b ) = 100 + 90 + 60 = 250, целевая функция прибыли имеет вид: Q' = 10х1 + 15х2 - 250.
Как видно из рис. 2.1 область допустимых решений варьируется в пределах области ОДР. Нижняя ее граница соответствует "минимальному" варианту запасов ресурсов b0, а верхняя - максимальному b1max . При решении задачи оптимизации прямая, соответствующая целевой функции Q, смещается в направлении, указанном на рисунке, т.е.
вправо - вверх. При этом по рис. 2.1, для вариантов Qmln и Q' указанные прямые лежат ниже верхней границы области допустимых решений, соответствующей данным вариантам, т.е. решение задачи оптимизации существует. Однако, для варианта Qmax прямая, соответст-вующая целевой функции, выходит за верхний край области допустимых решений. Таким образом, решения задачи оптимизации не существует.
Далее, как видно из рис. 2.1, максимальное значение Q для варианта Q' больше, чем для варианта Qmin. Нетрудно заметить, что и вариант Q' не самый оптимальный (есть постановки задачи, для которых
QQ > Q'). *
Таким образом, возникает задача определения такого варианта bi и соответствующего ему значения целевой функции Qmin < Q < Qmax , при котором решение будет существовать и при этом являться максимальным среди всех допустимых решений.
Теперь рассмотрим задачу (2.1) - (2.4) для нескольких вариантов прибыли от единицы и соответствующего максимального объема продаж.
Задача 2 Пусть планируются к продаже два продукта: x1 и x2 на одном временном интервале. Пусть прибыль от единицы первого продукта изменяется в диапазоне (8.20) при функции спроса x1max = 200 / q1. Прибыль от единицы второго продукта находится в диапазоне (12.30) при функции спроса x 2max = 450 / q2. Начальный запас ресурсов предприятия
b0 = (4000, 7000, 4000). Пусть увеличение запаса ресурса 1 на 100 единиц потребует инвестиций в размере AI1 = 5, ресурса 2 на 100 единиц - AI2 = 3, ресурса 3 на 100 единиц - AI3 = 6.
Представим данную задачу графически для двух вариантов q. Пусть первый вариант прибыли q = (10; 15). Ему соответствует максимальный объем производства продукции xmax = (20; 30). Пусть второй вариант прибыли q = (8; 12). Ему соответствует максимальный объем производства продукции xmax = (25; 37,5). Целевая функция имеет следующий вид:
Q = 10x1 + 15x2 - I для первого варианта и Q = 8x1 + 12x2 - I для второго. Максимально допустимый расход ресурсов для первого варианта bmax = (9500, 14500, 8000), для второго варианта b1max = (11875, 18125, 10000).
При этом максимальная величина инвестиций для первого варианта Imax = 5-55 + 3-75 + 6-40 = 740, для второго Imax = 5-78,75 + 3-111,25 + + 6-60 = 1087,5. Система ограничений (2.2) определяется b1 и xmax и примет следующий вид:250 x 1 +150 x 2 * Й11, 350 x 1 + 250 x 2 * Й12, 100 x 1 + 200 x 2 * Й13, 0 * x 1 * x 1max , 0 * x 2 * x 2max .
На рис. 2.2 сплошными линиями изображен первый вариант. Пунктирными линиями изображен второй вариант, для обозначения которого использовался индекс (i). Обозначениями с индексом min отмечены прямые, соответствующие задаче оптимизации с запасом ресурсов b1 = b0. Обозначениями с индексом max отмечены прямые, соответствующие задаче оптимизации с запасом ресурсов b1 = b1max . Обозначениями со штрихом ' отмечены прямые, соответствующие задаче оптимизации с запасом ресурсов b1 = (6000, 10000, 5000).
Как видно из рис. 2.2 задача 2 для второго варианта прибыли и максимального объема производства отличается от первого варианта:
Появилась новая постановки задачи оптимизации.
Прямые целевой функции приобрели другой наклон (Q min, Q , Q max) и расположение относительно первого варианта.
Область изменения расположения допустимых решений задачи оптимизации расширилась и составила ОДР + ОДР1. При этом ее "нижняя" граница осталась прежней b0, а "верхняя" сместилась из b1max для первого варианта в b1max для второго, т. е. расширилась.
Рис. 2.2 Графическая иллюстрация задачи 2:
L1, L2, L3 - ограничения на максимальный расход ресурсов; Q - целевая функция; х1 < 20, х2 < 30 и х1 < 25, х2 < 37,5 - ограничения на максимальный выпуск продукции; ОДР - область изменения расположения допустимых решений задачи оптимизации для
первого варианта q - прибыли от единицы продукции; ОДР + ОДР1 - область изменения расположения допустимых решений задачи оптимизации для второго варианта q Следует отметить, что для второго варианта прибыли q прямая Qmax оказалась выше области
допустимых решений, ограниченной прямыми L*max, L2max, L3max , xi < 25, x2 < 37,5. Таким образом, при условии, что
Q > 0, решения задачи оптимизации вообще не существует.