Читайте также:
|
Графический метод применяется при решении ЗЛП с 2-мя переменными, заданными в стандартном виде, и многими переменными в канонической форме, при условии, что n - r ≤ 2, где n – число неизвестной системы ограничений, r – ранг системы векторов условий.
Решение системы графическим методом выполняется в 2 этапа: построение области допустимых решений и нахождение в этой области оптимального решения.
Z=c₁x₁ + c₂x₂ max
Ограничения: a₁₁x₁ + a₁₂x₂≤b₁
a₂₁x₁ + a₂₂x₂≤b₂
- - - - - - - -
am₁x₁ + am₂x₂≤bm
x₁≥0, х₂≥0
Для построения ОДР вводится на плоскости прямоугольная система координат Х₁ и Х₂.
Геометрическое место точек плоскости, координаты которых удовлетворяют системе линейных неравенств, образует выпуклый многоугольник. Он образуется в результате пересечения полуплоскостей каждой из построенных прямых.
В задаче ЛП ищется такая точка, или набор точек из ОДР, на которой достигается самая верхняя (или самая нижняя) линия уровня, расположенная дальше (или ближе) остальных в направлении роста целевой функции.
Для нахождения искомой точки используется теорема:
Значение целевой функции в точках линии уровня увеличивается, если линию уровня перемещать параллельно начальному положению в направлении нормали, и убывает при перемещении в противоположном направлении.
26. Алгоритм решения задачи ЛП с двумя переменными графическим методом.
1) Строится область допустимых решений (ОДР).
2) Если ОДР является не пустым множеством, то строится вектор
n (с₁,с₂), выходящий из начала координат.
3) Перпендикулярно вектору n проводится одна из линий уровня, например: линия уровня, соответствующая уровню с₁х₁ + с₂х₂ = 0
4) Линия уровня перемещается параллельно самой себе в направлении вектора n.
5) Перемещения линии уровня происходит до тех пор, пока у неё не окажется только одна общая точка с ОДР. Эта точка определяет единственное решение задачи и является точкой экстремизма.
6) Находим координаты точки экстремизма и значение целевой функции в ней.
Дата добавления: 2015-08-20; просмотров: 76 | Нарушение авторских прав
| <== предыдущая страница | | | следующая страница ==> |
| Транспортная задача. | | | Особые случаи при решении задачи ЛП. |