Студопедия

Главная страница Случайная страница

КАТЕГОРИИ:

АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника






Графическое решение задач




 

Задача ЛП в симметричной форме (17) – (19) может быть решена графически, если пространство управляемых параметров содержит две или три переменные.

Пусть = 2, тогда задача ЛП в симметричной форме выглядит так:

(34) (35)   (36)

Изобразим область допустимых решений в пространстве управляемых параметров. Для этого рассмотрим множество точек, удовлетворяющих неравенству (35). Это будет полуплоскость, ограниченная прямой.

 

(37)
Построим прямую .

Эта прямая делит все пространство на две полуплоскости. Для определения допустимой полуплоскости выбираем произвольную точку пространства, не лежащую на прямой (37) (лучше всего точку (0,0)), и подставляем её координаты в ограничение (35). Если ограничение выполняется, то полуплоскость, содержащая эту точку, допустимая.

Пересечение плоскостей образует область допустимых решений .

Поведение функции можно изобразить в пространстве управляемых параметров. Для этого достаточно построить семейство линий уровня функции. Линия уровня – это множество точек, в которых функция принимает постоянные значения.

 

(38)

Для задачи линейного программирования это прямые с разными константами в правой части уравнения (38).

Для построения линий уровня используем понятие градиента функции.

Градиент – это вектор частных производных функции.

= = ( )

Его можно вычислить в любой конкретной точке пространства переменных.

Свойства градиента функции

· Градиент функции, вычисленный в точке, перпендикулярен линии уровня функции, проходящей через эту точку.

· Направление градиента показывает направление максимального возрастания функции.

 

Пример

 

=

Линии уровня для нелинейных функций хорошо иллюстрируются линиями постоянной высоты над уровнем моря на географических картах. В задачах линейного программирования линии уровня – это параллельные прямые вида (38), а градиент функции – это вектор коэффициентов целевой функции. Он одинаков для всех точек пространства управляемых параметров.

Для построения линий уровня в задаче линейного программирования можно выбрать произвольную точку области, построить в этой точке вектор градиента функции и перпендикулярно ему провести через выбранную точку линию уровня функции.

Для получения оптимального решения нужно перемещать линию уровня в направлении градиента до тех пор, пока она имеет общие точки с областью. Крайнее положение линии уровня называется опорной прямой (здесь вся область находится по одну сторону прямой и касается прямой в точке или отрезке). Общие точки опорной прямой с областью и являются оптимальными решениями.



Координаты оптимального решения находятся точно. Для этого нужно записать активные ограничения в виде равенств и решить совместно систему уравнений

 

Пример

Решим графически задачу 2 из примеров раздела 1.3.

 

§

§

§

§

– оптимальное решение двумерной задачи, в пространстве x2,x4.

Остальные компоненты решения можно найти из общего решения исходной системы уравнений.

­– полное оптимальное решение пятимерной задачи.

Графическое решение наглядно иллюстрирует свойства области допустимых решений задачи линейного программирования.

 


mylektsii.ru - Мои Лекции - 2015-2019 год. (0.007 сек.)Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав Пожаловаться на материал