Решение задач линейного программирования
графическим методом
Существуют два наиболее распространенных способа решения задач линейного программирования (ЗЛП): графический метод и симплекс-метод. Графический метод существенно нагляднее и обычно проще для понимания и решения (хотя занимает много времени, так как требует тщательного построения чертежа). Также этот метод позволяет практически одновременно найти решение на минимум и максимум, тогда как симплекс-методом придется делать «два подхода».
Основные шаги по решению ЗПЛ графическим методом следующие: построить область допустимых решений задачи (выпуклый многоугольник), который определяется как пересечение полуплоскостей, соответствующих неравенствам задачи, построить линию уровня целевой функции, и, наконец, двигать линию уровня в нужном направлении, пока не достигнем крайней точки области — оптимальной точки (или множества). При этом можно найти единственное оптимальное решение (точку), множество (отрезок) или ни одного (область пустая или не ограниченная в нужном направлении).
А за конкретикой — к примерам ниже: вы найдете там решенные графическим способом задачи линейного программирования. Примеры решений выложены бесплатно для вашего удобства — изучайте, ищите похожие, решайте. Если вам нужна помощь в выполнении заданий по методам оптимальных решений, перейдите в раздел: Решение задач ЛП на заказ (решаем для студентов очников и заочников).
Графический метод решения ЗЛП: примеры онлайн
Задача 1. Колхоз имеет возможность приобрести не более 19 трехтонных автомашин и не более 17 пятитонных. Отпускная цена трехтонного грузовика — 4000 руб., пятитонного — 5000 руб. Колхоз может выделить для приобретения автомашин 141 тысяч рублей. Сколько нужно приобрести автомашин, чтобы их суммарная грузоподъемность была максимальной?
Задачу решить графическими и аналитическими методами.
Задача 2. Решить задачу графическим методом на минимум и на максимум
Задача 3. Решить задачу графическим методом на минимум и на максимум
Задача 4. Среди чисел x и y, удовлетворяющих условиям
найти такие, при которых разность этих чисел y-x принимает наибольшее значение.
Задача 5. Решить графическим методом ЗЛП, заданную указанной математической моделью.
Задача 6. Решите графически следующие задачи линейного программирования
Задача 7. Решить графическим методом
Графический метод решения ЗЛП
В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений (см. рисунок).
Инструкция . Выберите количество строк (количество ограничений). Если количество переменных больше двух, необходимо систему привести к СЗЛП (см. пример и пример №2). Если ограничение двойное, например, 1 ≤ x1 ≤ 4 , то оно разбивается на два: x1 ≥ 1 , x1 ≤ 4 (т.е. количество строк увеличивается на 1).
Построить область допустимого решения (ОДР) можно также с помощью этого сервиса.
Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.
- На плоскости X10X2 строят прямые.
- Определяются полуплоскости.
- Определяют многоугольник решений;
- Строят вектор N(c1,c2), который указывает направление целевой функции;
- Передвигают прямую целевую функцию c1x2 + c2x2 = 0 в направлении вектора N до крайней точки многоугольника решений.
- Вычисляют координаты точки и значение целевой функции в этой точке.
- Целевая функция принимает экстремальное (минимальное или максимальное) значение в единственной точке А.
- Сформулировать математическую модель задачи линейного программирования.
- Решить задачу линейного программирования графическим способом (для двух переменных).
Если количество переменных в задаче линейного программирования больше двух, то задачу предварительно сводят к стандартной ЗЛП.
F(X) = 3x1 — 2x2 + 5x3 — 4x5 → max при ограничениях:
x1 + x2 + x3=12
2x1 — x2 + x4=8
— 2x1 + 2x2 + x5=10
F(X) = 3x1 — 2x2 + 5x3 — 4x5
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x1 + x2 + x3 = 12
2x1 — x2 + x4 = 8
— 2x1 + 2x2 + x5 = 10
Выразим базисные переменные через остальные:
x3 = — x1 — x2+12
x4 = — 2x1 + x2+8
x5 = 2x1 — 2x2+10
Подставим их в целевую функцию:
F(X) = 3x1 — 2x2 + 5(- x1 — x2+12) — 4(2x1 — 2x2+10)
или
F(X) = — 10x1 + x2+20 → max
Система неравенств:
— x1 — x2+12 ≥ 0
— 2x1 + x2+8 ≥ 0
2x1 — 2x2+10 ≥ 0
Приводим систему неравенств к следующему виду:
x1 + x2 ≤ 12
2x1 — x2 ≤ 8
— 2x1 + 2x2 ≤ 10
F(X) = — 10x1 + x2+20 → max
Особенности решения задач линейного программирования графическим методом
Переменную x2 принимаем в качестве дополнительной переменной и делаем замену на знак «≥»:
f=x1 + 6x3+ 27
x1 + 3x3≥6
Далее задача решается графическом способом.
Пример №2
F(X) = 3x1 — 2x2 + 5x3 — 4x5 → max при ограничениях:
x1 + x2 + x3=12
2x1 — x2 + x4=8
— 2x1 + 2x2 + x5=10
F(X) = 3x1 — 2x2 + 5x3 — 4x5
Переход к СЗЛП.
Расширенная матрица системы ограничений-равенств данной задачи:
| 1 | 1 | 1 | 0 | 0 | 12 |
| 2 | -1 | 0 | 1 | 0 | 8 |
| -2 | 2 | 0 | 0 | 1 | 10 |
Приведем систему к единичной матрице методом жордановских преобразований.
1. В качестве базовой переменной можно выбрать x3.
2. В качестве базовой переменной можно выбрать x4.
3. В качестве базовой переменной можно выбрать x5.
Поскольку в системе имеется единичная матрица, то в качестве базисных переменных принимаем X = (3,4,5).
Соответствующие уравнения имеют вид:
x1 + x2 + x3 = 12
2x1 — x2 + x4 = 8
— 2x1 + 2x2 + x5 = 10
Выразим базисные переменные через остальные:
x3 = — x1 — x2+12
x4 = — 2x1 + x2+8
x5 = 2x1 — 2x2+10
Подставим их в целевую функцию:
F(X) = 3x1 — 2x2 + 5(- x1 — x2+12) — 4(2x1 — 2x2+10)
или
F(X) = — 10x1 + x2+20 → max
Система неравенств:
— x1 — x2+12 ≥ 0
— 2x1 + x2+8 ≥ 0
2x1 — 2x2+10 ≥ 0
Приводим систему неравенств к следующему виду:
x1 + x2 ≤ 12
2x1 — x2 ≤ 8
— 2x1 + 2x2 ≤ 10
F(X) = — 10x1 + x2+20 → max
- Составить систему математических зависимостей (неравенств) и целевую функцию.
- Изобразить геометрическую интерпретацию задачи.
- Найти оптимальное решение.
- Провести аналитическую проверку.
- Определить существенные и несущественные ресурсы и их избытки.
- Определить значение целевой функции.
- Вычислить объективно обусловленные оценки.
- Составить соотношение устойчивости.