Приведем геометрический метод решения задачи ЛП.
Найти максимум функции
F = c1 x1 + c2 x2 (6.8)
при условиях
(6.9)
Решение:
Каждое из неравенств системы (6.9) геометрически определяет полуплоскость с граничными прямыми ai1 x1 + ai2 x2 = bi (i = 1,k), x1 = 0, x2 = 0.
Если система (6.9) – совместна, то геометрически, множество решений есть многоугольник.
Стороны этого многоугольника лежат на уравнениях прямых, которые получаются из уравнений системы, заменой неравенство на равенство.
Для определения вершины многогранника, в котором целевая функция F достигает максимума, поступают следующим образом:
1) строят линию уровня с1 х1 + с2 х2 = h;
2) передвигают линию уровня в направлении вектора С = (с1,с2) до тех пор, пока она не пройдет через последнюю точку многогранника решений;
3) координаты указанной точки есть оптимальный план данной задачи.
Пример: возможны следующие случаи:
а) единственное решение;
б) все точки на [АВ] – есть решение ЗЛП;
в) решение неограниченное;
г) решение системы несовместно.
Обзорные вопросы
Какой из методов решения задач ЛП является наиболее наглядным?
Когда используется геометрический метод решения задачи ЛП?
Сколько шагов содержит алгоритм решения задач геометрическим методом?
3. Симплексный метод решения задач линейного программирования
Одним из наиболее распространенных (универсальных) методов решения задач линейного программирования является симплексный метод (табличный).
Геометрическая интерпретация задач линейного программирования большей размерности (n2) аналогична.
Ограничения определяют допустимое множество, являющееся пересечением конечного числа полупространств и гиперплоскостей, которое называют многогранным множеством. Оно выпукло и замкнуто. В частности, оно может оказаться пустым или неограниченным.
Достарыңызбен бөлісу: |
