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

В тех случаях, когда в задаче ЛП лишь две переменные, можно использовать для решения графический метод. Пусть требуется найти максимальное ( минимальное ) значение функции Графический метод решения задач линейного программирования - student2.ru при ограничениях:

Графический метод решения задач линейного программирования - student2.ru (1.5)

Данный метод основывается на возможности графического изображения области допустимых решений задачи, т.е. удовлетворяющих системе (1.5), и нахождения среди них оптимального решения. Область допустимых решений задачи строится как пересечение (общая часть) областей решений каждого из заданных ограничений (1.5). Каждое из них определяет полуплоскость с границей Графический метод решения задач линейного программирования - student2.ru , Графический метод решения задач линейного программирования - student2.ru . Для того, чтобы определить, какая из двух полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку, если же неравенство не удовлетворяется, то областью решений является полуплоскость, не содержащая данную точку.

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

Линией уровня называется прямая, на которой целевая функция Графический метод решения задач линейного программирования - student2.ru принимает постоянное значение. Уравнение линии уровня имеет вид

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

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

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

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

Рис. 1.1

Значения Графический метод решения задач линейного программирования - student2.ru возрастают в направлении вектора Графический метод решения задач линейного программирования - student2.ru . Поэтому необходимо передвигать линию уровня Графический метод решения задач линейного программирования - student2.ru в направлении этого вектора параллельно самой себе до опорной прямой L1в задаче на максимум и в противоположном направлении – в задаче на минимум (до опорной прямой L2).

Приведём решение примера 1.1. Напомним, что нужно найти максимум функции Графический метод решения задач линейного программирования - student2.ru при ограничениях

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

Решение. Строим область допустимых решений. Нумеруем ограничения задачи. В прямоугольной декартовой системе координат (рис.1.2) строим прямую Графический метод решения задач линейного программирования - student2.ru Графический метод решения задач линейного программирования - student2.ru , соответствующую ограничению (1). Находим, какая из полуплоскостей, на которые эта прямая делит всю координатную плоскость, является областью решений неравенства (1).

Для этого достаточно координаты какой - либо точки, не лежащей на прямой, подставить в неравенство. Так как прямая Графический метод решения задач линейного программирования - student2.ru не проходит через начало координат, подставляем Графический метод решения задач линейного программирования - student2.ru в первое ограничение Графический метод решения задач линейного программирования - student2.ru . Получим строгое неравенство Графический метод решения задач линейного программирования - student2.ru . Следовательно, точка Графический метод решения задач линейного программирования - student2.ru лежит в полуплоскости решений. Аналогично строим прямую Графический метод решения задач линейного программирования - student2.ru Графический метод решения задач линейного программирования - student2.ru и область решений ограничения (2). Находим общую часть полуплоскостей решений, учитывая ограничения (3). Полученную область допустимых решений выделим на рис.1.2 тёмным цветом.

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

Рис.1.2

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

Наши рекомендации