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