Рецензент: В.Н. Гусаков, к.ф-м.н., доцент

О.Н. Копычко, к.ф-м.н., доцент

Ответственный за выпуск: В.М. Левин, д.т.н., профессор

ОГЛАВЛЕНИЕ

Геометрический метод решения задач ЛП (линейного програмирования) 4

РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ ГЕОМЕТРИЧЕСКИМ МЕТОДОМ в ms excel. 7

ПРИМЕР РЕШЕНИЯ ЗАДАЧИ ЛИНЕЙНОГО ПРГРАММИРОВАНИЯ С ИСПОЛЬЗОВАНИЕМ ДОПОЛНИТЕЛЬНЫХ ВОЗМОЖНОСТЕЙ мs excel «Поиск решения». 9

ВарИанти ИндивИдуальнЫх заданИЙ.. 11

ЛИтература.. 14

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

Геометрический метод позволяет решать задачи линейного программирования (ЛП) с двумя или тремя неизвестными.

Схема решения задачи ЛП с двумя переменными геометрическим методом:

1. Находим и изображаем на плоскости область допустимых значений (ОДЗ) – множество точек, координаты которых удовлетворяют системе ограничений. Если эта область пустая, то задача не имеет решения. Если эта область выпуклый многоугольник, то задача всегда имеет решение. В случае неограниченной области, задача может, как иметь решение, так и нет.

2. Среди множества точек ОДЗ находим точку, в которой целевая функция L=C₁*x₁ + C₂*x₂ принимает оптимальное значение. Для этого:

а) строим градиент - вектор, который определяет направление максимального роста целевой функции. Он выходит с т. О(0;0) и направлен в точку с координатами, которые являются коэффициентами при соответствующих переменных в уравнении целевой функции (C₁,C₂).

б) строим прямую линию, которая называется опорной, перпендикулярно к градиенту. Строим ее таким образом, чтобы ОДЗ находилась между точкой координат (C₁,C₂) и опорной прямой. Опорная прямая обладает свойством, что вдоль нее значение целевой функции остается постоянным. При параллельном перемещении прямой самой себе в направлении градиента значение целевой функции возрастает, поэтому первое касание опорной прямой с ОДЗ есть точка минимума, а последнее – максимума.

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

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

Пример:

L=2x₁-2x₂ - min

при ограничениях:

На плоскости строим систему координат и соответственно прямые для уравнений:

–x₁+x₂=2, 5x₁+3x₂=18, x₁-2x₂=1

ОДЗ определяем, как совокупность точек, где выполняются все ограничения одновременно. Строим вектор (градиент), с координатами (2,-2) и область допустимых значений (ОДЗ).

Областью допустимых значений (ОДЗ) будет пятиугольник OABCD. Строим опорную прямую перпендикулярно вектору Grad. Если прямую перемещать параллельно самой себе в направлении вектора Grad до тех пор, пока она не станет опорной к ОДЗ, тогда видим, что L достигает максимума в точке C, а минимума в любой точке отрезка AB (прямая параллельна прямой –x₁+x₂=2).

Координатами точки A являются x₁=0, x₂=2. Поэтому, подставив эти значения в линейную форму уравнения целевой функции, получим

Определим по графику координаты т. C:

Подставив эти значения в линейную форму уравнения целевой функции, получим

Для проверки найденных значений решим систему уравнений

Решением этой системы есть точки x₁=3, x₂=1. Поэтому точка C имеет координаты x₁=3, x₂=1.