 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Пример 5. Данное множество является неограниченным – см
Данное множество является неограниченным – см. рис. 4.5.
 |
Линии уровня целевой функции 
представляют собой семейство параллельных гиперплоскостей в n- мерном пространстве. Заметим, что при решении задачи линейного программирования константу 
можно отбросить (перенести в правую часть), поскольку на поиск оптимальной точки она не влияет. Однако при вычислении оптимального значения целевой функции ее следует прибавить. Если по условию задачи требуется добиться максимума целевой функции, то константу 
следует увеличивать до тех пор, пока гиперплоскость все еще будет пересекать допустимое множество, т.е. сдвигать ее в направлении градиента целевой функции 
. Если же требуется минимизировать значение целевой функции, то гиперплоскость следует сдвигать в направлении, противоположном градиенту целевой функции, т.е. в направлении ее антиградиента.
Нетрудно понять, что возможны следующие случаи:
10. Задача не имеет решения. Это возможно, если допустимое множество пусто или не ограничено (в последнем случае задача может иметь, а может и не иметь решение – см. рис. 4.6).
20. Задача имеет единственное решение. В этом случае решение достигается в так называемой вершине многогранного множества. Если все ограничения задачи имеют вид неравенств, то обычно это точка, в которой являются активными не менее n ограничений, причем какие-либо n из них имеют линейно независимые градиенты – см. рис. 4.7.
 |
30. Задача имеет бесконечное множество решений. В этом случае решение достигается на всем ребре или грани (некоторой размерности) допустимого множества – см. рис. 4.8.
Следует заметить, что:
1) Если допустимое множество ограничено и не пусто, то решение всегда существует. Это следует из теоремы Вейерштрасса.
2) Если решение достигается в каких-то двух точках, то оно достигается и во всех точках грани минимальной размерности, которая содержит эти точки.
3) Если допустимое множество не ограничено, то это еще не означает отсутствия решения – все зависит от того, в какую сторону направлен градиент целевой функции.
Поиск по сайту: