Линейное программирование. 
Линейное программирование

Графический метод

Рассмотрим графический метод решения ЗЛП в стандартной форме с двумя переменными, т. е. задачи вида:

Найти вектор удовлетворяющий системе ограничений:

для которого функция цели Z = c₁x₁+c₂x₂ достигает максимума.

Графический метод решения ЗЛП условно можно разбить на два этапа:

1. Построение ОДР ЗЛП.

2. Нахождение среди всех точек ОДР такой точки в которой целевая функция принимает максимальное значение.

Перейдем к рассмотрению этих этапов.

Этап 1

Геометрическая интерпретация множества решений линейного неравенства Рассмотрим неравенство:

.

Известно, что точки, координаты которых удовлетворяют уравнению, лежат на прямой. Назовем эту прямую граничной. Граничная прямая разбивает плоскость на две полуплоскости. Координаты точек одной полуплоскости удовлетворяют исходному неравенству, а другой полуплоскости — неравенству Следовательно, геометрической интерпретацией множества решений линейного неравенства является полуплоскость, лежащая по одну сторону от граничной прямой, включая прямую.

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

Если координаты взятой точки удовлетворяют данному неравенству, то искомой является та полуплоскость, которой эта точка принадлежит, в противном случае — другая полуплоскость.

Пример 1. Геометрической интерпретацией решений неравенства является полуплоскость, изображенная на рис. 4.1 стрелками. Покажем это.

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

Геометрическая интерпретация множества решений системы линейных неравенств Пусть дана система линейных неравенств с двумя неизвестными:

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

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

а.

Б

в

г

д

е

ж.

Рис. 22. Возможные случаи ОДР

Этап 2

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

Из курса высшей математики известно, что уравнение при фиксированном значении Z определяет прямую, а при изменении значения Z — семейство параллельных прямых. Для всех точек, лежащих на одной из прямых, функция Z принимает одно и то же значение, поэтому указанные прямые называются линиями уровня для функции Z.

Вектор называется градиентом функции Z. Он перпендикулярен линиям уровня и показывает направление наибольшего возрастания функции Z. Так как, то .

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

Рис. 23. Функция Z принимает максимальное значение в точке М.

Пусть, например, выпуклый многоугольник АВМСD является ОДР, а расположен так, как изображено на рис. 23. Тогда принимает максимальное значение в точке М.

Условия Производитель может работать на внутренний рынок или на экспорт. При этом на внутренний рынок производитель может произвести 3 продукта за единицу времени, а на экспорт 8. Зная ограничения на количество сырья, затраченную электроэнергию и затраты на транспортировку, найти максимум производства на внутренний рынок.

Таблица 1.

Постановка задачи и ограничений.

Значения ограничивающих функций Для ограничивающих функций X1=X, X2=Y.

Таблица 2.

Нахождение ОДР.

Рис. 24 ОДР и целевая функция.

Черной линией отмечена целевая функция.

Градиент F (x)={(0;0),(3;-8)}.

Антиградиент F (x)={(0;0),(-3;8)}.

Так как находится максимум, то движение целевой функции происходит в направление вектора градиента.

Черной точкой отмечено решение, которое находится в точке (2,6875;0).

Значение исходное функции в оптимальной точке F (2,6875;0)=8,0625.