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

Графический метод применяется при решении ЗЛП с 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) Находим координаты точки экстремизма и значение целевой функции в ней.


documentaixcjlx.html
documentaixcqwf.html
documentaixcygn.html
documentaixdfqv.html
documentaixdnbd.html
Документ Геометрическая интерпретация задач линейного программирования.