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

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

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

Этапы графического метода:

1 Получить уравнения прямых путем замены в ограничениях задачи знаков неравенств на знаки точных равенств и построить это прямые.

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

Для этого необходимо подставить в конкретное неравенство координаты какой-либо точки, например, (0;0) и после этого проверить истинность полученного неравенства.

Если неравенство истинное то заштриховать полуплоскость, содержащую точку (0;0);

иначе (неравенство ложное) заштриховать полуплоскость, не содержащую точку (0;0).

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

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

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

Произвольный выбор F связан с тем, что, придавая F различные значения, мы будем получать различные прямые, параллельные друг другу. При этом будет изменяться лишь длина отрезка, отсекаемого прямой на оси (начальная ордината), а угловой коэффициент прямой, равный будет оставаться постоянным.

5 Построить вектор , который начинается в точке (0;0) и заканчивается в точке .

Вектор показывает направление возрастания значений ЦФ, а значит и значений F целевой прямой.

6 Передвигать целевую прямую

• в направлении вектора при поиске max ЦФ;
• или в направлении противоположном вектору при поиске min ЦФ.

В результате этого передвижения

• найти точку (или точки), в которой ЦФ принимает max (или min) значение;
• или установить, что ЦФ неограниченна на множестве планов сверху или снизу.

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

7 Определить координаты точки максимума (минимума) ЦФ . Для точного определения координат оптимальной точки необходимо решить систему уравнений прямых, на пересечении которых находится .

8 Вычислить значение ЦФ в точки максимума (минимума).

Пример 2.(см.условия примера1):

1) Построим следующие прямые (см.рис.1)

Для этого вычислим координаты точек пересечения этих прямых с осями координат

2), 3) После проведения штриховки допустимых полуплоскостей определяем, что ОДР — это многоугольник ABCDEF.

4) Целевую прямую можно построить по уравнению

5) Построить вектор , который начинается в точке (0;0) и заканчивается в точке(3,2).Если целевая прямая и вектор построены верно, то они будут перпендикулярны.

6) Точка Е — это последняя вершина многоугольника допустимых решений, через которую проходит целевая прямая, двигаясь по направлению вектора , т.е. т.Е — это точка максимума ЦФ.

7) Координаты точки Е, найдем как решение системы уравнений

8) Таким образом, максимальное значение ЦФ равно

Рисунок 1- График решения задачи

Источник

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

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

Инструкция . Выберите количество строк (количество ограничений). Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №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

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

Источник

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

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

Сначала на координатной плоскости x₁Ox₂ строится допустимая многоугольная область (область допустимых решений, область определения), соответствующая ограничениям.

При этом могут быть получены следующие области:

1. Основной случай – получающаяся область имеет вид ограниченного выпуклого многоугольника (рис. 2.2, а).
2. Неосновной случай – получается неограниченный выпуклый многоугольник, имеющий вид, подобный изображенному на рис. 2.2, б.
3. Возможен случай, когда неравенства противоречат друг другу и допустимая область вообще пуста.

Рис. 2.2. Области определения решения:

а – основной случай, б – неосновной случай

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

Приравняем целевую функцию постоянной величине “a”. Меняя значение “a”, получим семейство параллельных прямых, каждая из которых является линией уровня.

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

При поиске максимума ЦФ необходимо передвигать целевую прямую в направлении вектора , при поиске минимума ЦФ – против направления вектора . Последняя по ходу движения вершина ОДР будет точкой максимума или минимума ЦФ.

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

Если такой точки (точек) не существует, то можно сделать вывод о неограниченности ЦФ на множестве планов сверху (при поиске максимума) или снизу (при поиске минимум).

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

Вернемся к целевой функции: . Допустим, значение функции L = 1 (абсолютно произвольно выбранное число), тогда . Данное уравнение является уравнением прямой на плоскости. Известно, что данная прямая перпендикулярна вектору, координатами которого являются коэффициенты функции, а именно вектору .

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

Рис. 2.3. Допустимая область решения

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

Решая совместно эти два уравнения, получим координаты этой точки x₁ = 1; x₂ = 2. При этом значение целевой функции , что и дает ее максимальное значение.

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

Подводя итог, можно сформулировать следующие положения:

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

Источник