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

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ

Теоретическое введение

Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи ЛП (1.1) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом – пересечение соотвествующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучем, одной точкой. В случае несовместности системы ограничений задачи (1.1) ОДР является пустым множеством.

Примечание №2.1. Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство

можно представить в виде системы двух неравенств (см. рис.2.1)

ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см. рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположнонаправлению вектора .

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня (), соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

 

Задача

Найдем оптимальное решение задачи №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

Примечания

L(X)®max

L(X)®min

L(X)®max

L(X)®min

Количество ограничений больше одного

Все ограничения - неравенства

Все ограничения - неравенства

Все ограничения - неравенства

Ограничения в виде равенств и неравенств

Вид оптимального решения

Единственное решение

Единственное решение

Бесконечное множество решений

ЦФ не ограничена снизу

ЦФ не ограничена сверху

Единственное решение

Бесконечное множество решений

Единственное решение

ЦФ не ограничена сверху

ЦФ не ограничена снизу

Единственное решение

Бесконечное множество решений

Решений нет

Решений нет

Решений нет

Вид ОДР

Многоугольная замкнутая

Многоугольная незамкнутая

Луч

Отрезок

Единственная точка

№

1.1

1.2

1.3

2.1

2.2

2.3

2.4

3.1

3.2

3.3

4.1

4.2

1. Анализ сокращения или увеличения ресурсов:

· на сколько можно увеличить (ограничения типа ) запас дефицитного ресурса для улучшения оптимального значения ЦФ?

· на сколько можно уменьшить (ограничения типа ) запас недефицитного ресурса при сохранении оптимального значения ЦФ?

2. Увеличение (ограничения типа ) запаса какого из ресурсов наиболее выгодно?

3. Анализ изменения коэффициентов ЦФ: каков диапазон изменения коэффициентов ЦФ, при котором не меняется оптимальное решение?

Правило №3.3

Чтобы определить максимальное уменьшение запаса недефицитного ресурса, не меняющее оптимальное решение,

необходимо передвигать соответствующую прямую до пересечения с оптимальной точкой.

Правило №3.4

Чтобы численно определить минимальную величину запаса недефицитного ресурса, не меняющую оптимальное решение,

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

Чтобы выяснить, до каких пределов падение спроса на краску 2-го вида не повлияет на производство в точке , используем правило №3.4. Подставляем в левую часть ограничения (4) координаты точки Е, получаем

.

Делаем вывод: предельный уровень, до которого может упасть спрос на краску 2-го вида и при котором не изменится оптимальность полученного ранее решения, равен т краски в сутки.

Экономический смысл ограничения (3)

в том, что объем продаж краски 2-го вида может превысить объем продаж краски 1-го вида максимум на 1 т. Дальнейшее увеличение продаж краски 2-го вида по сравнению с краской 1-го вида графически отобразится перемещением прямой (3) влево и вверх, но никак не повлияет на оптимальность точки Е. Но если разность спросов на краску 2-го и 1-го видов будет уменьшаться, то прямая (3) будет перемещаться ниже и правее. Последним положением прямой (3), при котором точка Е остается оптимальной, является пересечение с точкой Е (см. рис.3.1). Согласно правилу №3.4, подставим координаты точки в левую часть ограничения (3)

[т краски].

Получаем, что разность спросов на краску 2-го и 1-го вида в точке стала отрицательной. То есть, прохождение прямой (3) через точку Е означает, что краску 2-го вида будут покупать в меньшем объеме, чем краску 1-го вида

[т краски/сутки].

Делаем вывод: максимальное превышение спроса на краску 1-го вида над спросом на краску 2-го вида, при котором оптимальное решение в точке Е не изменится, составляет 2 т краски в сутки.

Результаты решения первой задачи анализа оптимального решения на чувствительность представлены в табл.3.1.

Таблица 3.1

Правило №3.5

Чтобы определить границы допустимого диапазона изменения коэффициента ЦФ, например и ,

необходимо приравнять тангенс угла наклона целевой прямой поочередно к тангенсам углов наклона прямых связывающих ограничений, например и (рис.3.5 и 3.6).

Рис.3.5. Определение

Рис.3.6. Определение

Определим насколько максимально может снизиться цена на краску 1-го вида, не изменяя оптимальную точку Е. Для этого применим правило №3.5 и формулу расчета тангенса угла наклона прямой (рис.3.7).

Рис.3.7. Определение тангенса угла наклона прямой

Определим тангенсы углов наклона:

1) целевой прямой , учитывая, что фиксировано

;

2) связывающего ограничения (1)

;

3) связывающего ограничения (2)

.

Для нахождения min целевая прямая должна совпасть с прямой (1) (см. рис.3.5):

;

;

[тыс.руб./т].

Для нахождения max целевая прямая должна совпасть с прямой (2) (см. рис.3.6):

;

;

[тыс.руб./т].

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

Из приведенных выше расчетов и графической их иллюстрации следует, что если цена на краску первого вида станет меньше 1 тыс.руб./т (), то наиболее выгодным будет производство красок в точке D (см. рис.3.5). При этом общее потребление ингредиента В снизится, что приведет к его недефицитности [ресурс (2)], а дефицитными будут ресурсы (1) и (4).

 

ГРАФИЧЕСКИЙ МЕТОД РЕШЕНИЯ

Теоретическое введение

Графический метод довольно прост и нагляден для решения задач ЛП с двумя переменными. Он основан на геометрическом представлении допустимых решений и ЦФ задачи.

Каждое из неравенств задачи ЛП (1.1) определяет на координатной плоскости некоторую полуплоскость (рис.2.1), а система неравенств в целом – пересечение соотвествующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, лучем, одной точкой. В случае несовместности системы ограничений задачи (1.1) ОДР является пустым множеством.

Примечание №2.1. Все вышесказанное относится и к случаю, когда система ограничений (1.1) включает равенства, поскольку любое равенство

можно представить в виде системы двух неравенств (см. рис.2.1)

ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.

Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным (см. рис.2.1). Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.

Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня (см. рис.2.1). Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположнонаправлению вектора .

Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня (), соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.

При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптиум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.

 

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

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) ЦФ и вычислите значение ЦФ . Для вычисления координат оптимальной точки решите систему уравнений прямых, на пересечении которых находится .

Задача

Найдем оптимальное решение задачи №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) является точкой максимума ЦФ, .