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

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

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

Инструкция . Выберите количество строк (количество ограничений). Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x₁ ≤ 4 , то оно разбивается на два: x₁ ≥ 1 , x₁ ≤ 4 (т.е. количество строк увеличивается на 1).
Построить область допустимого решения (ОДР) можно также с помощью этого сервиса.

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

1. На плоскости X₁0X₂ строят прямые.
2. Определяются полуплоскости.
3. Определяют многоугольник решений;
4. Строят вектор N(c₁,c₂), который указывает направление целевой функции;
5. Передвигают прямую целевую функцию c₁x₂ + c₂x₂ = 0 в направлении вектора N до крайней точки многоугольника решений.
6. Вычисляют координаты точки и значение целевой функции в этой точке.

Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.

1. Сформулировать математическую модель задачи линейного программирования.
2. Решить задачу линейного программирования графическим способом (для двух переменных).

Если количество переменных в задаче линейного программирования больше двух, то задачу предварительно сводят к стандартной ЗЛП.
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅ → max при ограничениях:
x₁ + x₂ + x₃=12
2x₁ — x₂ + x₄=8
— 2x₁ + 2x₂ + x₅=10
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

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

Переменную x₂ принимаем в качестве дополнительной переменной и делаем замену на знак «≥»:
f=x₁ + 6x₃+ 27
x₁ + 3x₃≥6

Далее задача решается графическом способом.

Пример №2
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅ → max при ограничениях:
x₁ + x₂ + x₃=12
2x₁ — x₂ + x₄=8
— 2x₁ + 2x₂ + x₅=10
F(X) = 3x₁ — 2x₂ + 5x₃ — 4x₅
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:

1	1	1	0	0	12
2	-1	0	1	0	8
-2	2	0	0	1	10

Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x₃.
2. В качестве базовой переменной можно выбрать x₄.
3. В качестве базовой переменной можно выбрать x₅.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x₁ + x₂ + x₃ = 12
2x₁ — x₂ + x₄ = 8
— 2x₁ + 2x₂ + x₅ = 10
Выразим базисные переменные через остальные:
x₃ = — x₁ — x₂+12
x₄ = — 2x₁ + x₂+8
x₅ = 2x₁ — 2x₂+10
Подставим их в целевую функцию:
F(X) = 3x₁ — 2x₂ + 5(- x₁ — x₂+12) — 4(2x₁ — 2x₂+10)
или
F(X) = — 10x₁ + x₂+20 → max
Система неравенств:
— x₁ — x₂+12 ≥ 0
— 2x₁ + x₂+8 ≥ 0
2x₁ — 2x₂+10 ≥ 0
Приводим систему неравенств к следующему виду:
x₁ + x₂ ≤ 12
2x₁ — x₂ ≤ 8
— 2x₁ + 2x₂ ≤ 10
F(X) = — 10x₁ + x₂+20 → max

• Составить систему математических зависимостей (неравенств) и целевую функцию.
• Изобразить геометрическую интерпретацию задачи.
• Найти оптимальное решение.
• Провести аналитическую проверку.
• Определить существенные и несущественные ресурсы и их избытки.
• Определить значение целевой функции.
• Вычислить объективно обусловленные оценки.
• Составить соотношение устойчивости.

Источник

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

Графический метод используется для решения задач с двумя переменными вида: ; Данный метод основывается на возможности графического изображения области допустимых решений задачи и нахождении среди них оптимального решения. Область допустимых решений задачи строится как пересечение (общая часть) областей решений каждого из заданных ограничений. Областью решений линейного неравенства является одна из двух полуплоскостей, на которые прямая,соответствующая данному неравенству, делит всю координатную плоскость. Для того, чтобы определить, какая из двух координатных полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку, если же неравенство не удовлетворяется, то областью решений является полуплоскость, не содержащая данную точку. Областью допустимых решений задачи является общая часть полуплоскостей – областей решений всех неравенств системы ограничений. АЛГОРИТМ

1. Построить множество допустимых решений. В общем случае оно представляет собой выпуклый многоугольник. Если ограничения в задаче несовместны, множество допустимых решений является пустым множеством, а задача поиска экстремума не имеет смысла.
2. Найти градиент целевой функции , построить его.
3. Провести линию уровня целевой функции, перпендикулярную градиенту.
4. Перемещать линию уровня параллельно самой себе в направлении , найти точку, в которой f достигает максимума (минимума).
5. Найти координаты , решая систему уравнений прямых, пересекающихся в точке оптимума, вычислить .

В случае непустого множества допустимых решений возможны три типовых ситуации:

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

Пример 1. Решить задачу линейного программирования ; Решение. Построим множество допустимых решений. Нумеруем ограничения задачи. В прямоугольной декартовой системе координат строим прямую , соответствующую ограничению (1). Находим, какая из двух полуплоскостей является областью решений неравенства. Так, прямая (1) не проходит через начало координат, подставляем координаты точки О (0, 0) в первое ограничение. Получаем верное строгое неравенство 0 > -2. Следовательно, точка О лежит в полуплоскости решений. Аналогично строим прямые (2) – (4). Рис. 1. Нашли , провели линию уровня функции, перпендикулярно градиенту, передвигаем ее параллельно самой себе в направлении. Эта прямая проходит через точку Х* пересечения прямых, ограничивающих область допустимых решений и соответствующих неравенствам (1) и (2). Определяем координаты точки Х*, решая систему. Получаем Х*(1, 3). Вычисляем. Ответ: при Х* = (1, 3). Задача линейного программирования не всегда задается в виде математической модели. Пример составления математической модели рассмотрен на примере транспортной задачи (п. 3).

Для продолжения скачивания необходимо пройти капчу:

Источник

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

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

1) область допустимых решений — пустое множество;

2) область допустимых решений — единственная точка;

3) область допустимых решений — выпуклый многоугольник;

4) область допустимых решений — выпуклая неограниченная область.

В первом случае ЗЛП не имеет оптимального решения из-за несовместности системы ограничений.

Во втором случае — это единственное решение и будет оптимальным решением.

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

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

Пусть с₀ — некоторое число. Прямая является линией уровня целевой функции. В каждой точке этой прямой целевая функция принимает одно и то же значение, равное с₀. Вектор — градиент целевой функции

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

Если экстремум достигается в двух угловых точках, то, по теореме об альтернативном оптимуме, оптимальным решением будет любая точка отрезка, соединяющего эти точки:

, .

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

Пример 1. Решить графически следующую задачу:

,

Построим область допустимых решений системы ограничений:

Источник