О существовании решения линейной задачи.
Теорема
(Вейерштрасса).
Если множество
– компактно (замкнуто и ограничено) и
на этом множестве функция
,
по крайней мере, непрерывна, то у такой
задачи существует оптимальный план (
достигается в некоторой точке).
Определение.
.
называется
множеством
уровня.
Теорема (Критерий
существования).
Для того чтобы у задачи (1) существовал
– оптимальный план необходимо и
достаточно, чтобы для некоторого
конечного числа
множество
было либо непустой частью множества
минимального уровня, либо непустым
компактом, на котором функция
полунепрерывна снизу.
Действительно,задача
(1) эквивалентна задаче f(x)→min
(2), x
,
т.к. на части
и, следовательно, на ней не может быть
оптимального плана. У задачи (2) по
обобщенной теореме Вейерштрасса
существует оптимальный план, следовательно,
он существует и у задачи (1).
Ч.т.д.
Задача на безусловный минимум.
Задача имеет вид:
(1)
то есть
.
Условие оптимальности
Теорема 1. Если
– локально-оптимальный план, то
(2)
Теорема 2
(Необходимое условие оптимальности
второго порядка).
Если
– локально-оптимальный план, то
(3)
Определение.
Точка
называется стационарной
точкой
функции
,
если она является решением системы
(4)
(4)
Теорема 3
(Достаточное
условие оптимальности).
Если
– стационарная точка функции
и
,
(5)
то
– локально-оптимальный план (1) (по
крайней мере).
Доказательство. Доказательство теорем 1-3 основано на разложении функции ( переменных) в ряд в окрестности точки (см. главу 2).
Ч.т.д.
Схема исследования задач типа (1)
1)
Проверяем условие существования решения
задачи (1), при этом применяется критерий
существования решения
.
В общем случае, при
,
вызывает трудности проверка условий
существования решения, так как в редких
случаях можно представить (построить)
множество уровня.
2)
Составляем систему (4) и находим
стационарные точки функции
(все). Только среди них может находиться
оптимальный план и все локально-оптимальные
планы. Пусть
– все стационарные точки функции
.
3) Для каждой стационарной точки проверяем выполнение или невыполнение условий (3)-(5). Пусть – стационарная точка, тогда возможны случаи:
а)
.
Тогда, согласно теореме 3
– локально-оптимальный план.
б)
.
Тогда для нее выполняются условия
теоремы 2, но не выполняются условия
теоремы 3. Тем не менее, она остается
подозрительной на решение задачи (1) (то
есть она может оказаться и оптимальным
планом и локально-оптимальным планом).
в) Не выполняется ни а) ни б). Тогда эту точку исключают из дальнейшего рассмотрения.
4) Делаем окончательный вывод: среди точек, оказавшихся либо локально-оптимальными планами, либо подозрительных на решение, находим лучшую, то есть подставляем точки в целевую функцию и лучшей будет точка с наименьшим значением функции. Если доказано существование решения и построены все стационарные точки, то лучшая точка будет оптимальным планом. В общем случае, из-за сложности функции и невозможности найти все решения системы (4) исследование нельзя провести полностью и лучшая точка остается подозрительной на решение задачи.