Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Графоаналитический метод - один из простейших методов линейного программирования. Он наглядно раскрывает сущность линейного программирования, его геометрическую интерпретацию. Однако этот метод имеет существенный недостаток: с его помощью можно решать только те планово-экономические задачи, математическая модель которых представляет собой систему с двумя или тремя неизвестными.
Метод основан на графическом (геометрическом) представлении допустимых решений и целевой функции задачи.
Каждое из неравенств задачи линейного программирования определяет на координатной плоскости (х1, х2) некоторую полуплоскость, а система неравенств в целом – пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР графически может быть представлена выпуклым многоугольником, неограниченной выпуклой многоугольной областью, отрезком, одной точкой. В случае несовместности системы ограничений задачи ОДР является пустым множеством.
ЦФ при фиксированном значении определяет на плоскости прямую линию . Изменяя значения L, мы получим семейство параллельных прямых, называемых линиями уровня.
Это связано с тем, что изменение значения L повлечет изменение лишь длины отрезка, отсекаемого линией уровня на оси (начальная ордината), а угловой коэффициент прямой останется постоянным. Поэтому для решения будет достаточно построить одну из линий уровня, произвольно выбрав значение L.
Вектор с координатами из коэффициентов ЦФ при и перпендикулярен к каждой из линий уровня. Направление вектора совпадает с направлением возрастания ЦФ, что является важным моментом для решения задач. Направление убывания ЦФ противоположнонаправлению вектора .
Суть графического метода заключается в следующем. По направлению (против направления) вектора в ОДР производится поиск оптимальной точки . Оптимальной считается точка, через которую проходит линия уровня (), соответствующая наибольшему (наименьшему) значению функции . Оптимальное решение всегда находится на границе ОДР, например, в последней вершине многоугольника ОДР, через которую пройдет целевая прямая, или на всей его стороне.
При поиске оптимального решения задач ЛП возможны следующие ситуации: существует единственное решение задачи; существует бесконечное множество решений (альтернативный оптимум); ЦФ не ограничена; область допустимых решений – единственная точка; задача не имеет решений.
Дата публикования: 2015-04-10; Прочитано: 990 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!