Методика решения задач ЛП графическим методом

I. В ограничениях задачи (1.1) замените знаки неравенств на знаки точных равенств и постройте соответствующие прямые.

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

Еслинеравенство истинное,

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

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

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

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

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

IV. Если ОДР – не пустое множество, то постройте целевую прямую, т.е. любую из линий уровня , где L – произвольное число, например, кратное и , т.е. удобное для проведения расчетов. Способ построения аналогичен построению прямых ограничений.

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

VI. При поиске max ЦФ передвигайте целевую прямую в направлении вектора , при поиске min ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой max или min ЦФ. Если такой точки (точек) не существует, то сделайте вывод о неограниченности ЦФ на множестве планов сверху (при поиске max) или снизу (при поиске min).

VII. Определите координаты точки max (min) ЦФ и вычислите значение ЦФ . Для вычисления координат оптимальной точки решите систему уравнений прямых, на пересечении которых находится .

Задача №2.01

Найдем оптимальное решение задачи №1.01 о красках, математическая модель которой имеет вид

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

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

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

Рис.2.2. Графическое решение задачи №2.01

 

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

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

,

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

,

[т/сутки].

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

Задача №2.02

Построим ограничения (рис.2.3).

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

(4) –

 

 

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

,

Определим ОДР. Ограничение-равенство (4) допускает только точки, лежащие на прямой (4). Подставим точку (0;0) в ограничение (3), получим , что является ложным неравенством, поэтому стрелкой (или штрихованием) обозначим полуплоскость, не содержащую точку (0;0), т.е. расположенную выше прямой (3). Аналогично определим и укажем допустимые полуплоскости для остальных ограничений (см. рис.2.3). Анализ полуплоскостей, допустимых остальными ограничениями-неравенствами, позволяет определить, что ОДР – это отрезок АВ.

Строим вектор из точки (0;0) в точку (-2;-1). Для поиска минимума ЦФ двигаем целевую прямую против направления вектора . Точка В – это последняя точка отрезка АВ, через которую проходит целевая прямая, т.е. В – точка минимума ЦФ.

Определим координаты точки В из системы уравнений прямых ограничений (3) и (4)

.

Минимальное значение ЦФ равно

.

При поиске точки максимума ЦФ будем двигать целевую прямую по направлению вектора . Последней точкой отрезка АВ, а значит, и точкой максимума будет А. Определим координаты точки А из системы уравнений прямых ограничений (1) и (4)

.

Максимальное значение ЦФ равно

.

Таким образом, В(3,46; 1,85) – точка минимума, ;

– точка максимума,

Задача №2.03

Построим ограничения (рис.2.4)

(1) – (2) – (4) –

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

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

,

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

 

 

 

Рис.2.4. Графическое решение задачи №2.03

 

Аналогично определим и укажем допустимые полуплоскости для остальных ограничений (см. рис.2.4). Анализ допустимых полуплоскостей позволяет определить, что ОДР – это незамкнутая область, ограниченная прямыми (2), (3), (4) и осью .

Строим вектор из точки (0;0) в точку (1;-3). Для поиска минимума ЦФ двигаем целевую прямую против направления вектора . Поскольку в этом направлении ОДР не ограничена, то невозможно в этом направлении найти последнюю точку ОДР. Отсюда следует, что ЦФ не ограничена на множестве планов снизу (поскольку идет поиск минимума).

При поиске максимума ЦФ будем двигать целевую прямую по направлению вектора до пересечения с вершиной А – последней точкой ОДР в этом направлении. Определим координаты точки А из системы уравнений прямых ограничений (2) и (4)

.

Максимальное значение ЦФ равно

.

Таким образом, в данной задаче ЦФ не ограничена на множестве планов снизу, а А(1;4) является точкой максимума ЦФ, .

 

Варианты задач ЛП для решения графическим методом

Задача №2.1	Задача №2.2
Задача №2.3	Задача №2.4
Задача №2.5	Задача №2.6
Задача №2.7*	Задача №2.8*
Задача №2.9*

Задача №2.10*

Не привязываясь к конкретным числовым данным, проиллюстрируйте графически ситуации из табл.2.1. Для каждой ситуации на графике изобразите:

1) ограничения;

2) ЦФ в виде одной из линий уровня;

3) вектор ;

4) ОДР;

5) оптимальное решение.