Графический метод решения задач линейного программирования.

 

Наиболее простым и наглядным методом линейного программирования (ЛП) является графический метод. Он применяется для решения задач ЛП с двумя переменными.

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

Линейное уравнение описывает множество точек, лежащих на одной прямой. Линейное неравенство описывает одну из плоскостей, образованных этой прямой в координатной плоскости.

Пример. 2 Решить неравенство графическим методом.

Определим, какую часть плоскости описывает неравенство . Во-первых, построим прямую рис. 1.

x1
x2

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

неравенству. Удобной для использования при подстановке в неравенство является начало координат. Подставим х₁=х₂=0 в неравенство . Получим . Данное утверждение является верным, следовательно, неравенству соответствует нижняя полуплоскость, содержащая точку (0.0). Это отражено на графике, изображенном на рис.1.

 

Рис. 1 Графический метод решения неравенств

При решении системы неравенств необходимо изобразить графически каждое неравенство и пересечение найденных полуплоскостей и будет решением системы.

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

условиям неотрицательности (x_j ³ 0, j=1, …, n). Координаты любой точки, принадлежащей области определения являются допустимым решением задачи.

Рассмотрим графический метод решения общей задачи ЛП (2.1-2.2), полагая n=2, т.е. рассмотрим эту задачу на плоскости.

Каждое неравенство этой системы геометрически определяет полуплоскость с граничной прямой a_i1 x₁ + a_i2 x₂ = b_i, . Условия неотрицательности определяют полуплоскости, соответственно, с граничными прямыми x₁=0, x₂ =0, т.е. определяют первую координатную четверть. Следует отметить, что область допустимых решений может быть как замкнутой (рис. 2), так и не замкнутой (рис. 3). В этих случаях система ограничений совместна (имеет хотя бы одно решение).

 

Рис. 2 Область допустимых решений замкнута

Рис. 3 Область допустимых решений не замкнута

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

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

Таким образом, геометрически задача линейного программирования (ЗЛП) представляет собой отыскание такой точки многоугольника решений, координаты которой доставляют линейной функции цели максимальное (минимальное) значение, причем допустимыми решениями являются все точки многоугольника решений.

Для нахождения экстремального значения целевой функ­ции при графическом решении задач ЛП используют вектор–градиент, координаты которого являются частными производными целевой функции, т.е.

 

.

Этот вектор показывает направление наискорейшего изменения це­левой функции. Прямая , перпендикулярная вектору–градиенту, является линией уровня целевой функции. В любой точке линии уровня целевая функция принимает одно и то же значение . Получаем семейство параллельных прямых, каждая из которых является линией уровня.

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

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

Графический метод решения ЗЛП состоит из следующих этапов.

1. Строится многоугольная область допустимых решений ЗЛП – ОДР.

2. Строится вектор-градиент целевой функции в какой-нибудь точке Х_0, принадлежащей ОДР – .

3. Линия уровня C₁x₁+C₂x₂ = С (С–const) - прямая, перпендикулярная вектору–градиенту передвигается в направлении этого вектора в случае максимизации Z(x_1, x₂) до тех пор, пока не покинет пределов ОДР. Предельная точка (или точки) области при этом движении и является точкой максимума Z(x_1, x₂).

4. Для нахождения ее координат достаточно решить систему двух уравнений прямых, получаемых из соответствующих ограничений и дающих в пересечении точку максимума. Значение Z(x_1, x₂), найденное в получаемой точке, является максимальным.

При минимизации Z(x_1, x₂) линия уровня перемещается в направлении, противоположном вектору-градиенту. Если прямая при своем движении не покидает ОДР, то соответствующий максимум или минимум Z(x_1, x₂) не существует.

Если линия уровня параллельна какому-либо функциональному ограничению задачи, то оптимальное значение целевой функции будет достигаться в любой точке этого ограничения, лежащей между двумя оптимальными угловыми точками, и, соответственно, любая из этих точек является оптимальным решением ЗЛП.

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

Пример 3

Предприятие может выпускать продукцию двух видов: П₁ и П₂. Используется три вида ресурсов: оборудование, сырье и электроэнергия. Нормы расхода, запасы ресурсов и прибыль от реализации единицы продукции представлены в таблице 3.

Таблица 3

Ресурсы	Нормы расхода на единицу продукции	Запас ресурса
П1	П2
Оборудование, ч
Сырье, кг
Электроэнергия, кВт-ч
Прибыль от реализации единицы продукции, ден. ед.

 

Найти оптимальный план выпуска продукции, учитывая, что предприятие уже заключило контракт на поставку 2 единиц продукции П₂.

Решение

Введем переменные (управляющие параметры):

, – объем выпускаемой продукции П₁ и П₂ соответственно.

Z – прибыль от реализации всей выпущенной продукции.

Экономико-математическая модель данной задачи будет иметь вид

;

Вначале построим многоугольник решений или ОДР задачи (рисунок 1). Для этого в системе координат на плоскости изобразим граничные прямые:

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

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

 

Рис. 4 Пример решения задачи графо-аналитическим методом.

Точка является точкой пересечении прямых и . Для определения ее координат необходимо решить систему уравнений:

Откуда . Это и есть оптимальный план задачи. Подставив значение и в целевую функцию Z, получаем

.

Таким образом, для того чтобы получить максимальную прибыль в размере 56 ден. ед., необходимо запланировать выпуск 8 ед. продукции вида П₁ и 4 ед. продукции П₂.

⇐ Предыдущая1234Следующая ⇒

Поделиться: