Читайте также:
|
1. По ограничениям задачи строится область допустимых решений (ОДР). Каждому неравенству на плоскости соответствует полуплоскость, каждому уравнению соответствует прямая, ОДР будет пересечением построенных полуплоскостей. Возможны несколько вариантов ОДР (замкнутая область, неограниченная область, пустое множество). Если ОДР – пустое множество, то задача не имеет решения. Если ОДР не пусто, то переходим к шагу 2.
2. Строим вектор градиента с координатами начала (0,0) и конца (с1,с2),
где с1, с2 - коэффициенты целевой функции.
3. Строим линию уровня целевой функции. Линия уровня целевой функции в данной ЗЛП – прямая, перпендикулярная вектору градиента.
4. Определяем те точки ОДР, которые визуально наиболее соответствуют оптимальному решению. При этом, если задача на максимум, то линию уровня целевой функции перемещаем параллельно самой себе в направлении градиента до самой “дальней” точки (точек) ОДР. Если же задача на минимум, то линию уровня перемещаем в противоположном градиенту направлении.
5. Если очевидно, что некоторая угловая точка с координатами (x1,x2) является единственной кандидатурой на оптимальное решение, то находим эти координаты и подставляем их в целевую функцию. Если же таких точек несколько, то требуется сравнение значений целевой функции в этих точках. Для каждой точки составляем систему двух линейных уравнений. которые соответствуют прямым, задающим данные точки. Полученные решения подставляются в целевую функцию. В качестве оптимальной выбирается та точка, для которой значение целевой функции лучше.
Решение ЗЛП записываем в виде: x1, x2 и F(x1,x2)=c1*x1+c2*x2.
Замечание. Возможны несколько вариантов решений: оптимальное решение единственное (см. рис.), решений множество, целевая функция неограниченна.
Х2
C(х1,х2)
Пример ОДР,
которую фор- B
мируют 6
ограничений, D
включая 2
тривиальных:
x1³0, x2³0.
ОДР имеет 6
угловых точек: A
A,B,C,D,E,F (c1,c2) Х1
F E
Дата добавления: 2015-01-12; просмотров: 116 | Поможем написать вашу работу | Нарушение авторских прав |
| <== предыдущая лекция | | | следующая лекция ==> |
| Статья 2. | | | Часть первая |