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