Графический метод решения ЗЛП

ЗЛП с двумя переменными можно представить в виде:

F(Х) = → max (min), (6)

(7)

≥ 0, j = 1, 2. (8)

Пусть система ограничений (7) совместна, т.е. имеет решения.

Введём на плоскости прямоугольную систему координат. Тогда ОДР можно рассматривать как множество точек плоскости, координаты которых (х1, х2) удовлетворяют условиям (7) и (8).

Каждое из неравенств (7) определяет полуплоскость, лежащую по одну сторону прямой (i = 1, 2, …, m). Чтобы определить, какую же полуплоскость определяет данное неравенство, можно выполнить следующее: взять произвольную точку плоскости с координатами (х1, х2) и подставить эти координаты в неравенство (обычно в качестве произвольной точки берут начало координат). Если оно удовлетворяется, то полуплоскость, в которой лежит эта точка есть искомая; если нет, то искомая полуплоскость лежит по другую сторону прямой .

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

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

Линией уровня называют прямую, на которой целевая функция принимает одно и то же постоянное значение.

Уравнение линии уровня имеет вид = α, где α = const.

При α = 0 линия уровня пройдёт через начало координат; другим значениям α будут соответствовать прямые, параллельные друг другу (рис. 1).

х2

В

С

D

= ( ; )

E

О

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

Известно, что коэффициенты при переменных в линейном уравнении являются координатами нормального вектора к соответствующей прямой или плоскости. Следовательно, нормальный вектор линий уровня имеет координаты и , т.е. = ( ; ).

Значения целевой функции в точках линии уровня увеличиваются, если линию уровня перемещать параллельно начальному положению в направлении нормали, и убывают при перемещении в противоположном направлении.

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

Для случая, рассмотренного на рис. 1, минимум целевой функции достигается в точке А, т.к. в этой точке линия уровня впервые встретилась с ОДР. Максимум достигается в точке С, т.к. это последняя точка, в которой линия уровня коснулась ОДР.

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

Алгоритм решения ЗЛП графическим методом:

1) Строим ОДР как пересечение полуплоскостей, определяемых условиями (7) и (8); если оно пусто, то решения ЗЛП не имеет.

2) Строим нормальный вектор = ( ; ) с точкой приложения в начале координат.

3) Проводим перпендикулярно вектору любую линию уровня, например, соответствующую уравнению = 0.

4) Перемещаем линию уровня до положения опорной прямой. На этой прямой и будет находиться экстремум (максимум или минимум) функции.

5) Вычисляем значение целевой функции в точке экстремума (максимума или минимума).

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

Если ЗЛП имеет единственное решение, то следует найти вершину, в которой достигается искомое экстремальное значение целевой функции; вычислить её координаты и вычислить значение целевой функции в точке экстремума.

Если ЗЛП имеет бесконечное множество решений, то это означает, что экстремум достигается на отрезке, на полупрямой или на прямой. В этом случае следует описать множество решений.

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

Пример 1. Решить графическим методом ЗЛП:

F(Х) = → max,

≥ 0, ≥ 0.

Решение. 1) ОДР является многоугольник АВСDЕ (рис. 2).

2) Найдём нормальный вектор и построим его. = (1; 2).

3) Перпендикулярно вектору проведём линию уровня = 0.

4) Линию уровня перемещаем в направлении вектора до последней точки D, в которой она касается ОДР. В ней достигается максимум целевой функции.

Координаты точки D ( ). Значение целевой функции в точке максимума: F(D) = F ( ) = ≈ 7,12.

Заметим, что минимум целевой функции достигается в точке В ( ). Значение целевой функции в точке минимума: F(В) = = 3,6.

х2

D

С

= (1; 2)

В

О

E

Рис. 2. Пример решения ЗЛП графическим методом

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

F(Х) = max,

.

Решение. 1) ОДР является многоугольник ОАВСD (рис.3).

2) Нормальный вектор = (2; 4).

3) Перпендикулярно вектору проведём линию уровня

= 0.

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

Координаты точки С найдём как пересечение прямых, заданных уравнениями:

Решая систему, получим координаты точки С ( ), в которой находится одно из оптимальных решений. Значение целевой функции в точке С: F(С) = F( ) = 12. Координаты точки В найдём из системы уравнений:

Решая систему, получим координаты точки В (2; 2). Значение целевой функции в точке В: F(В) = F(2; 2) = 12.

х2

В

С

= (2; 4)

О

Рис. 3. Пример решения ЗЛП графическим методом

Таким образом, ЗЛП имеет бесконечное множество решений

Наибольшее значение целевой функции F_max ( ; ) =12 достигается на отрезке ВС прямой , .

Замечание. ЗЛП с n неизвестными (n ≥ 2) можно решить графическим методом, если она имеет каноническую форму и удовлетворяет условию

n – r ≤ 2,

где n - число неизвестных системы; r - ранг системы векторов-условий (число линейно независимых уравнений системы).

Если уравнения системы ограничений линейно независимы, то r = m, где m - число уравнений.

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

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

Контрольные вопросы:

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

2. Что является исходными данными для математической модели? Дайте их характеристику.

3. Сформулируйте задачу математического программирования в общем виде.

4. Дайте классификацию задач математического программирования. От чего зависит выбор метода их решения?

5. Каким образом ставится задача линейного программирования? Дайте определение допустимого плана, оптимального плана ЗЛП.

6. Расскажите алгоритм решения ЗЛП графическим методом.

Литература:

1. Высшая математика для экономистов: Учебник для вузов / Н.Ш. Кремер, Б.А. Путко, И.М. Тришин, М.Н.Фридман. Под ред. Н.Ш. Кремера. – М.: ЮНИТИ, 2005. – 471 с.

2. Данко П.Е., Попов А.Г., Кожевникова Т.Я. Высшая математика в упражнениях и задачах. Ч. 1, 2. – М.: Оникс 21 век: Мир и образование, 2005. – 304 с. Ч. 1; – 416 с. Ч. 2.

3. Математика в экономике: Учебник: В 2-х ч. / А.С. Солодовников, В.А. Бабайцев, А.В. Браилов, И.Г. Шандара. – М.: Финансы и статистика, 2006.

4. Общий курс высшей математики для экономистов: Учебник. / Под ред. В.И. Ермакова. –М.: ИНФРА-М, 2006. – 655 с.

5. Сборник задач по высшей математике для экономистов: Учебное пособие / Под ред.В.И. Ермакова. М.: ИНФРА-М, 2006. – 574 с.

6. Шипачев В.С. Высшая математика: Учебник для студ. вузов – М.: Высшая школа, 2007. – 479 с.