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

 

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

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

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

2. Далее строится вектор–градиент линейной формы в какой-нибудь точке х₀, принадлежащей допустимой области . Координаты вектора можно пропорционально увеличивать или уменьшать, при этом направление вектора не изменяется.

3. Строится прямая , перпендикулярная вектору-градиенту, и передвигается в направлении этого вектора в случае максимизации  до тех пор, пока не покинет пределов многоугольной области. В случае минимизации целевой функции, прямую передвигают в направлении противоположном вектору-градиенту. Предельная точка (или точки) области при этом движении и является точкой максимума (минимума) . Если прямая при своем движении не покидает допустимой области, то соответствующий максимум или минимум  не существует.

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

 

Пример.

Решить графическим методом следующую ЗЛП:

f(х₁,х₂) = (2х₁+3х₂)  → max

х₁+3х₂ £ 300

  х₁+х₂ £ 150

 х_1,2 ³ 0

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

Этап 1. Определим множество решений первого неравенства. Оно состоит из решения уравнения и строгого неравенства. Решением уравнения служат точки прямой х₁+3х₂ =300. Построим прямую по двум точкам (0;100) и (300;0).

Множество решений строгого неравенства – одна из полуплоскостей, на которую делит плоскость построенная прямая. Какая из них является искомой, можно выяснить при помощи одной контрольной точки. Если в произвольно взятой точке, не принадлежащей прямой, неравенство выполняется, то оно выполняется и во всех точках той полуплоскости, которой принадлежит контрольная точка, и не выполняется во всех точках другой полуплоскости. В качестве контрольной точки удобно брать начало координат. Подставим значение координат (0;0) в неравенство, получим 0<300, т.е. оно выполняется. Следовательно, областью решения неравенства служит нижняя полуплоскость.

Аналогичным образом построим ОДР второго неравенства.

х₁+х₂ = 150             Точки (0;150) и (150;0).

х₁+х₂ < 150, при х₁ = х₂ = 0 неравенство 0 < 150 выполняется, область решения – нижняя полуплоскость.

Заштрихуем общую область для всех неравенств, обозначим вершины многоугольника латинскими буквами А, В, С.

 

Этап 2.  Для определения направления движения к оптимуму построим вектор-градиент, соединив его вершину ∆(100;150) с началом координат О (0;0).

Этап 3.   Построим прямую (линию уровня), перпендикулярную вектору-градиенту.

Будем передвигать линию уровня до ее пересечения с точкой В. Далее она выходит из ОДР. Следовательно, именно в этой точке достигается максимум целевой функции.

Этап 4. Координаты точки В найдем, решив систему из двух уравнений:

х₁+3х₂ = 300

х₁+х₂ = 150

х₁ = 75   х₂ = 75

Координаты точки А (0;100) и точки С (150,0).

 

Т.к. координаты точки В равны х₁ = 75 и х₂ = 75, то максимум ЦФ равен 375.

 

 

А

В

С