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

Графический метод решения задач линейного программирования с двумя переменными Графический метод используется для решения задач с двумя переменными следующего вида: (1) (2) , (3) Данный метод основывается на возможности графического изображения области допустимых решений задачи и нахождении среди них оптимального решения. Область допустимых решений задачи строится как пересечение (общая часть) областей решений каждого из заданных ограничений (2), (3). Областью решений линейного неравенства из двух полуплоскостей, на которые прямая является одна , соответствующая данному неравенству, делит всю координатную плоскость. Для того чтобы определить, какая из двух координатных полуплоскостей является областью решений, достаточно координаты какой-либо точки, не лежащей на прямой, подставить в неравенство: если оно удовлетворяется, то областью решений является полуплоскость, содержащая данную точку, если же неравенство не удовлетворяется, то областью решений является полуплоскость, не содержащая данную точку. Областью допустимых решений задачи является общая часть полуплоскостей — областей решений всех неравенств системы ограничений. Для нахождения среди допустимых решений оптимального решения используют линии уровня и опорные прямые. Линией уровня называется прямая, на которой целевая функция задачи принимает постоянное значение. Уравнение линии уровня в общем случае имеет вид 1 , где нормаль . Все линии уровня параллельны между собой. Их . Опорной прямой называется линия уровня, которая имеет хотя бы одну общую точку с областью допустимых решений и по отношению к которой эта область находится в одной из полуплоскостей. Область допустимых решений любой задачи имеет не более двух опорных прямых, на одной из которых может находится оптимальное решение. Значения целевой функции на линиях уровня возрастают, если линии уровня перемещать в направлении их нормали, и убывают при перемещении линий уровня в противоположном направлении. Алгоритм графического метода решения задач линейного программирования с двумя переменными: 1. Построить область допустимых решений. 2. Если область допустимых решений является пустым множеством, то задача не имеет решения ввиду несовместности системы ограничений. 3. Если область допустимых решений является непустым множеством, построить нормаль линий уровня и одну из линий уровня, имеющую общие точки с этой областью. 4. Линию уровня переместить до опорной прямой в задаче на максимум в направлении нормали, в задаче на минимум — в противоположном направлении. 5. Если при перемещении линии уровня по области допустимых решений в направлении, соответствующем приближению к экстремуму целевой функции, 2 линия уровня уходит в бесконечность, то задача не имеет решения ввиду неограниченности целевой функции. 6. Если задача линейного программирования имеет оптимальное решение, то для его нахождения решить совместно уравнения прямых, ограничивающих область допустимых решений и имеющих общие точки с соответствующей опорной прямой. Если целевая функция задачи достигает экстремума в двух угловых точках, то задача имеет бесконечное множество решений. Оптимальным решением является любая выпуклая линейная комбинация этих точек. После нахождения оптимальных решений вычислить значение целевой функции на этих решениях. 3