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

Графический метод основан на геометрической интерпретации зада­чи линейного программирования и применяется в основном при реше­нии задач с двумя независимыми переменными х₁ и х₂ и когда ограниче­ниями являются неравенства.

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

1. На плоскости в координатных осях х₁ о х₂ строятся прямые соответст­вующие исходным ограничениям — неравенствам.

2. Указываются полуплоскости, удовлетворяющие каждому из ограни­чений.

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

4. Экстремальные величины можно определить непосредственно, по­строив линию уровня, полагая Z = 0 или принимая значение целевой функции Z = const.

∂Z ∂Z

Определяется grad Z: градиент целевой функции grad Z = -----; = -----

∂х₁ ∂х₂

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

Пример 3.1

Найти графически экстремальные значения целевой функции: (3.1)

при линейных ограничениях-неравенствах:

(3.2)

и условиях: (3.3)

Решение

Так как каждое ограничение-неравенство графически представляет полуплоскость, то пересечение этих полуплоскостей определяет область допустимых решений (ОДР) задачи линейного программирования. Для определения ОДР заменяем нестрогие неравенства системы (3.2) уравне­ниями (3.4) и строим соответствующие прямые в координатных осях ххох2 (рис. 3.1):

(3.4)

Многоугольником решений является пятиугольник АВСДЕ, коорди­наты точек которого удовлетворяют ограничениям (3.2) и условиям не­отрицательности (3.3). Координаты вершин пятиугольника соответству­ют базисным решениям задачи, которые называются опорными решения­ми. Среди этих решений находятся и оптимальные решения, которые можно определить двумя способами.

I способ. Определяем координаты вершин многоугольника решений АВСДЕ и подставим в целевую функцию.

Точка А получена в результате пересечения прямых (2) и (5) сис­темы (3.4):

Рис. 3.1

(3.5)

Решая систему (3.5), получаем

Подставляя эти координаты в функцию (3.1), получаем

Аналогично определяем координаты вершин многоугольника реше­ний В, С, D и Е, а также значения целевой функции в этих точках.

точка В:

точка С:

точка D:

точка Е:

Выделяя наибольшее значение и наименьшее

целевой функции, определяем

II способ позволяет определять непосредственно положение точек А и Д соответствующие экстремальным значениям целевой функции.

Определяем градиент целевой функции

Построим линию уровня, пологая Z = 0, т.е. -4x₁ + 10х₂ = 0. Эта линия перпендикулярна grad (-4; 10) рис. 3.1.

Перемещая линию уровня в направлении градиента Z до точки А, которая, являясь касательной к ОДР, определяет максимальное значение целевой функции.

Перемещая линию уровня в направлении противоположном grad Z = = (-4; 10), она займет положение опорной линии в точке что соответствует минимальному значению целевой функции, т.е.

Пример 3.2

Построить на плоскости область решений системы линейных нера­венств (3.6) и условий (3.7). Определить максимальное и минимальное значения линейной функции (3.8) в этой области:

(3.6)

(3.7)

(3.8)

Решение

1) Заменяем знаки неравенств на знаки точных равенств, получаем сис­тему уравнений (3.9):

(3.9)

2). Построим соответствующие прямые (3.9) на плоскости в координат­ных осях Х1ОХ2 и определим область допустимых решений, удовле­творяя ограничениям (3.6).

3). Многоугольником решений является пятиугольник ABCDE, коорди­наты точек которого удовлетворяют условиям (3.7) и неравенствам системы ограничений (3.6) задачи.

4) Для определения точек, соответствующих экстремальным значениям функции (3.8), построим линию уровня 6х₁ - 4х₂ = 0 и grad Z (6; -4). Перемещая линию уровня в направлении grad Z до точки ее касания к ОДР в точке В, определим максимальное значение целевой функции в этой точке. Вычислим координаты точки В, решая систему:

Перемещая линию уровня параллельно самой себе в направлении противоположном grad Z, она займет положение опорной прямой на от­резке АЕ (так как прямая (4) параллельна линии уровня). Следовательно, в точках А и Е функция принимает минимальные значения.

Определим координаты точки А, решая систему:

Целевая функция в точке А имеет значение:

Искомая функция в токе Е с координатами х₁ = 0 и х₂ = 3 равна:

Z_E = 6∙0-4∙3 = -12.

Следовательно, в любой точке отрезка АЕ линейная функция имеет одинаковые значения

Zmin = -12.

Ответ: {-12; 52}.

Пример 3.3

Определить экстремальные значения линейной функции

Z = - 4x₁ + 10х₂ (3.10)

при линейных ограничениях: (3.11)

и условиях:

(3.12)

Решение

Находим область допустимых решений, заменяя систему неравенств (3.10) уравнениями (3.13) (рис. 3.3):

(3.13)

Областью допустимых решений является открытая область ABC. Определяем координаты точки В, решая систему:

Рис. 3.3

Вычисляем целевую функцию в точке

Передвигая прямую 4х₁ + 10х₂ = 0 параллельно самой себе в направле­нии grad (-4;10), она уходит в Следовательно, целевая функция огра­ничений на максимум не имеет.

Ответ:

Пример 3.4

Графическим методом может быть решена задача линейного про­граммирования, у которой система ограничений имеет n неизвестных m уравнениями, которые связаны соотношением n – m = 2.

Найти экстремальные значения целевой функции

Z = x₁+ 4x₂ - 2x₄ + 5 → extr (3.14)

при линейных ограничениях-равенствах:

(3.15)

и условиях:

(3.16)

Решение

1. Для системы (3.14) составляем расширенную матрицу А, ранг которой равен 3.

2. Выделяем базисные переменные х₃, х₄ и х₅, используя метод Жордана - Гаусса:

(3.17)

На основании полученной матрицы (3.14) ограничения задачи пере­пишем в виде: (3.18)

Выделяя базисные переменные х₃, х₄, х₅, систему (3.18) перепишем в виде: (3.19)

Подставляя значения переменных в целевую функцию 3.14, получаем:

Опуская базисные переменные х₃ ≥ 0, х₄ ≥ 0 и х₅ ≥ 0 в системе (3.19), получаем задачу линейного программирования в виде:

Z = 5х₁ - 2х₂ - 5 → extr (3.20)

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

(3.21)

и условиях

х1 ≥0,х2 ≥ 0 (3.22)

Задачу линейного программирования (3.20)-(3.22) решаем графи­чески.

Построим четырехугольник ОАВС решений, grad Z и линию уровня 2х₁ — 2х₂ —5 = 0, которые позволяют найти максимальное (в точке В) и минимальное (в точке Л) значения целевой функции (рис. 3.4).

Вычисляем значение целевой функции:

Координаты точки А:

Определяем координаты точки В, решая систему:

Рис. 3.4

Для отыскания оптимального плана исходной задачи подставим в (3.18) найденные значения для х₁ и х₂.

Для максимальной величины целевой функции базисные перемен­ные имеют значения:

Для минимального значения целевой функции базисные переменные имеют следующие величины:

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

1. Какие задачи линейного программирования решаются графическим ме­тодом?

2. Что называется областью допустимых решений?

3. Как определяется положение линии уровня?

4. С какой целью определяется градиент целевой функции?

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

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

ЗАДАЧИ 3.1-3.10

Не нашли, что искали? Воспользуйтесь поиском по сайту: