![]() |
Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | |
|
Графический метод основан на геометрической интерпретации задач линейного программирования и применяется в основном при решении задач двумерного пространства, т.к. трудно построить многогранник решений даже для трехмерного пространства. А для пространства размерности больше трех построить многогранник решений вообще невозможно.
Пусть задача линейного программирования задана в двумерном пространстве:
(1)
при ограничениях
(2)
Областью допустимых решений задачи может быть либо выпуклый многогранник, либо выпуклая многоугольная неограниченная область, либо единственная точка. Уравнение задачи (1) определяет на плоскости семейство параллельных прямых, каждой из которых отвечает определенное значениефункции
. Вектор
, перпендикулярный к этим прямым, указывает направление скорейшего возрастания функции
, а противопо-ложный вектор
– направление скорейшего убывания.
![]() |
|
Решение задачи линейного программирования можно проводить в такой последовательности:
|
2) определяем полуплоскости, соответствующие исходным ограничениям-неравенств. Для этого берем произвольную точку, лежащую по ту или иную сторону от граничной прямой, и ее координаты подставляем в левую часть ограничения-неравенства. Если оно удовлетворяется, то искомой будет полуплоскость, которая содержит выбранную точку; если не удовлетворяется, то искомой будет полуплоскость, которой данная точка не принадлежит;
3) выделяем область допустимых решений задачи, как общую часть полуплоскостей, соответствующих исходным неравенствам;
4) строим вектор и перпендикулярно к нему одну из прямых семейства
, например,
;
5) определяем экстремальную точку многоугольника решений путем параллельного перемещения вспомогательной прямой в направлении вектора
. Наиболее удаленная угловая точка, в которой прямая
встречается с областью допустимых решений, соответствует максимуму функции.Если необходимо найти точку, которой соответствует минимальное значение функции
, то вспомогательную прямую перемещаем в направлении вектора
до пересечения с первой точкой допустимой области (либо прямую
перемещаем в направлении вектора
);
6) определяем координаты точки С (точки А), решив систему линейных уравнений прямых, пересекающихся в этой точке, и находим экстремальное значение .
Пример 1. Найти графически минимальное и максимальное значения функции при заданных ограничениях:
где .
Дата публикования: 2015-01-10; Прочитано: 418 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!