Полезное:
Как сделать разговор полезным и приятным
Как сделать объемную звезду своими руками
Как сделать то, что делать не хочется?
Как сделать погремушку
Как сделать так чтобы женщины сами знакомились с вами
Как сделать идею коммерческой
Как сделать хорошую растяжку ног?
Как сделать наш разум здоровым?
Как сделать, чтобы люди обманывали меньше
Вопрос 4. Как сделать так, чтобы вас уважали и ценили?
Как сделать лучше себе и другим людям
Как сделать свидание интересным?
Категории:
АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника
Задачи линейного программирования
|
|
Если число входных параметров (искомых переменных) равно 2, то задача ЛП имеет наглядную графическую интерпретацию.
Пример
q (`x) = x1 - x2 ® min
D: x1 - 2x2 £ 1
-2 x1 + x2 £ 2
3x1 + x2 £ 3
x1 ³ 0, x2 ³ 0
1 этап графического решения – изображение на плоскости области D.
1 условие: x1 - 2x2 £ 1. Обозначим D1 – множество точек (x1; x2) удовлетворяющих 1-ому ограничению. Вся плоскость разбивается на множество точек Î D1 (условие выполнено) и Ï D1 (условие не выполнено). Построим границу области D1. Это будет множество точек x1 - 2x2 = 1.
На плоскости это будет прямая x2 = 0,5 x1 – 0,5. Её можно построить по 2-м точкам:
1) x1=0; x2 = - 0,5 2) x1 =1; x2 =0.
Полученная линия делит плоскость на 2 части. Одна часть удовлетворяет условию, вторая нет. Чтобы проверить какая часть удовлетворяет условию, надо взять любую точку и подставить в условие (1). Если оно выполняется для одной точки, то выполняется и для всей части. Например, (0;0). Условие (1) выполняется => множество D1 – это область выше прямой, штрихуем эту часть.
Аналогично для условия (2).
D2: -2 x1 + x2 £ 2.
Граница -2 x1 + x2 = 2. По двум точкам 1) x1=0; x2 = 2; 2) x1 = -1; x2 =0.
Чтобы проверить какая часть D2 подставим (0;0). Штрихуем ту часть, в которой начало координат, т.е. под прямой. Допустимыми являются точки, которые одновременно Î D1 и D2, т.е. их общая часть.
(3) условие 3x1 + x2 £ 3
1) x1=0; x2 = 3; 2) x1 = 1; x2 =0.
Замечание
Если условие имеет вид равенства, то множество точек удовлетворяющих ему - это прямая.
Например,
D: x1 + x2 £ 2
x1 - x2 = 0
x1 ³ 0, x2 ³ 0
2 этап – изображение целевой функции q. Целевая функция – это функция, для которой в задаче надо найти max или min. Если она зависит от двух переменных x1 и x2 , то её изображают в виде линий равного уровня – таких линий, в каждой точке которых функция имеет одинаковое значение.
Способ построения линий равного уровня.
q = x1 - x2. Зафиксируем любое значение q, например q = 2. Получим уравнение 2 = x1 - x2. Это будет линия q = 2.
Далее пусть q = 0 = > 0 = x1 - x2. Получаем линию уровня q = 0.
Пусть q = -2 = > -2 = x1 - x2. Получаем линию уровня q = -2.
Получаем 3 линии уровня – 3 параллельные прямые. При переходе от линии q = 2 к линии q = -2 целевая функция уменьшается, и т.к. надо найти min, то она улучшается, т.е. при перемещении линий уровня в направлении, указанном стрелкой целевая функция улучшается.
Для решения задачи ЛП надо найти такую точку, чтобы она легла в область D и при этом через неё проходила линия уровня с min q. Очевидно, что линия q = -2 не является оптимумом. Этим свойством будет обладать линия проходящая через точку В.
Если аналитически определить её координаты, то можно убедиться, q = -2,2. Точка В крайняя из области D.
Выводы. Чтобы графически решить задачу ЛП надо: построить обл. D; построить линии уровня целевой функции (достаточно 2-х линий) и определить, в какую сторону надо их перемещать, чтобы функция улучшалась; найти крайнюю точку, через которую проходит линия с наилучшим уровнем.
Замечание Иногда линия уровня параллельна какой-нибудь линии ограничения = > оптимальным решением будет целый отрезок.
Например,
q = x1 + x2 ® max
D: x1 + x2 £ 2
x1 - x2 ³ 0
x1 ³ 0, x2 ³ 0
Date: 2015-07-24; view: 413; Нарушение авторских прав