Решение линейной модели графическим методом

Пусть имеется следующая математическая модель.

Целевая функция

,

при ограничениях

Алгоритм решения. 1. В ограничениях задачи замените знаки неравенств на знаки точных равенств и постройте соответствующие прямые.

2. Найдите и заштрихуйте полуплоскости, разрешенные каждым из ограничений-неравенств задачи. Для этого подставьте в конкретное неравенство координаты какой-либо точки [например, (0; 0)], и проверьте истинность полученного неравенства.

Если неравенство истинное, то надо заштриховать полуплоскость, содержащую данную точку, иначе (неравенство ложное) надо заштриховать полуплоскость, не содержащую данную точку.

Поскольку x₁ и x₂ должны быть неотрицательными, то их допустимые значения всегда будут находиться выше оси x₁ и правее оси x₂, т.е. в I-м квадранте.

Ограничения-равенства разрешают только те точки, которые лежат на соответствующей прямой, поэтому выделите на графике такие прямые.

3. Определите область допустимых решений как часть плоскости, принадлежащую одновременно всем разрешенным областям, и выделите ее. При отсутствии области допустимых решений задача не имеет решений, о чем сделайте соответствующий вывод.

4. Если область допустимых решений – не пустое множество, то постройте целевую прямую, т.е. любую из линий уровня с₁x₁+с₂x₂=F, где F – произвольное число, например, кратное с₁ и с₂, т.е. удобное для проведения расчетов. Способ построения аналогичен построению прямых ограничений.

5. Постройте вектор , который начинается в точке (0; 0), заканчивается в точке (с₁, с₂). Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

6. При поиске максимума целевой функции передвигайте целевую прямую в направлении вектора , при поиске минимума целевой функции – против направления вектора . Последняя по ходу движения вершина области допустимых решений будет точкой максимума или. Если такой точки (точек) не существует, то сделайте вывод о неограниченности целевой функции на множестве планов сверху (при поиске максимума) или снизу (при поиске минимума).

7. Определите координаты точки максимума (минимума) целевой функции и вычислите значение целевой функции . Для вычисления координат оптимальной точки решите систему уравнений прямых, на пересечении которых находится .

Задача. Решитьзадачу, представленную следующей математической моделью:

Построим прямые ограничений, для чего вычислим координаты точек пересечения этих прямых с осями координат (см. рисунок).

(1) – (2) – (3) –

Прямая (4) проходит через точку параллельно оси .

Определим область допустимых решений. Например, подставим точку (0; 0) в исходное ограничение (3), получим , что является истинным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, содержащую точку (0; 0), т.е. расположенную правее и ниже прямой (3). Аналогично определим допустимые полуплоскости для остальных ограничений и укажем их стрелками у соответствующих прямых ограничений (см. рисунок). Общей областью, разрешенной всеми ограничениями, т.е. областью допустимых решений является многоугольник ABCDEF.

Целевую прямую можно построить по уравнению

,

Строим вектор из точки (0; 0) в точку (3; 2). Точка Е – это последняя вершина многоугольника допустимых решений ABCDEF, через которую проходит целевая прямая, двигаясь по направлению вектора .

Поэтому Е – это точка максимума ЦФ. Определим координаты точки Е из системы уравнений прямых ограничений (1) и (2)

,

[т/сутки].

Максимальное значение ЦФ равно [млн. руб./сутки]. Таким образом, наилучшим режимом работы фирмы является ежесуточное производство краски 1-го вида в объеме т и краски 2-го вида в объеме т. Доход от продажи красок составит млн. руб. в сутки.

Задание для самостоятельного выполнения. Решить графически линейную модель, построенную в примере в предыдущей работе.