Задача математического программирования

(1)

- допустимое огромное количество задачки математического программирования,

.

- функция Лагранжа задачки (1), где .

- градиент функции Лагранжа по координатам вектора , другими словами вектор, составленный из личных производных функции Лагранжа по координатам вектора :

.

- матрица вторых личных производных функции Лагранжа по координатам вектора .

Сформулируем узнаваемый из курса математического анализа итог о существовании решения задачки (1):


Аксиома 1 (Аксиома Вейерштрасса)

Пусть Задача математического программирования - компакт (ограниченное и замкнутое огромное количество) в , - непрерывная функция на . Тогда точка глобального минимума функции на (глобальное решение задачки (1)) существует.

1. Пусть - замкнутое огромное количество на , - непрерывная функция на , причём при неком огромное количество ограничено. Обосновать, что тогда точка глобального минимума функции на существует.

2. Понятно, что функция Задача математического программирования непрерывна на и удовлетворяет последующему условию: для хоть какой последовательности таковой, что , . Обосновать, что тогда функция добивается собственного малого значения на любом замкнутом огромном количестве из .

3. Пусть непрерывная функция имеет точку глобального минимума на . Следует ли отсюда, что функция имеет точку глобального минимума на любом замкнутом огромном количестве из ?

4. Пусть Задача математического программирования - точка серьезного локального минимума функции на ( ). Можно ли утверждать, что убывает в некой левой полуокрестности точки и растет в некой правой полуокрестности ?

5. Убедиться, что функция добивается локального минимума в точке = (0,0) повдоль каждой прямой, проходящей через , но не является точкой локального минимума этой функции.

Задачка математического программирования (1) именуется задачей Задача математического программирования бесспорной оптимизации, если , другими словами

(2)

Аксиома 2 (Нужное условие локальной оптимальности первого порядка)

Пусть функция дифференцируема в точке . Если - локальное решение задачки (2), то

. (3)

Аксиома 3 (Нужное условие локальной оптимальности второго порядка)

Пусть функция два раза дифференцируема в точке . Если - локальное решение задачки (2), то матрица - неотрицательно определена, другими словами

при всех . (4)


Аксиома 4 (Достаточное условие локальной оптимальности)

Пусть Задача математического программирования функция два раза дифференцируема в точке и , а матрица положительно определена, другими словами

при всех , . (5)

Тогда - серьезное локальное решение задачки (2).

Аксиома 5 (Аспект Сильвестра)

Симметрическая матрица является неотрицательно (положительно) определенной, и тогда только тогда, когда все её главные (угловые) миноры неотрицательны (положительны).

Пример 1.

Разглядим задачку бесспорной оптимизации:

.

Решение:

  1. Выпишем Задача математического программирования нужное условие локальной оптимальности первого порядка:

Решениями этой системы являются точки = (0,0),

  1. Разглядим гессиан функции в точках и :

, .

Матрица по аспекту Сильвестра не является неотрицательно определённой, другими словами нужное условие локальной оптимальности второго порядка не производится. Отсюда следует, что точка = (0,0) не может быть решением задачки.

Матрица положительно определена. Как следует, производится Задача математического программирования достаточное условие локальной оптимальности. Точка – серьезное локальное решение задачки.

В последующих задачках требуется привести примеры функций одной либо 2-ух переменных, в каких производятся обозначенные ниже требования.

6. Глобальные максимум и минимум достигаются в нескончаемом числе точек.

7. Функция ограничена, глобальный максимум достигается, а глобальный минимум не достигается.

8. Функция ограничена, но глобальные минимум Задача математического программирования и максимум не достигаются.

9. Функция ограничена, имеет локальные минимумы и максимумы, но глобальные максимум и минимум не достигается.

10. Имеется единственный локальный экстремум, не являющийся глобальным.

11. Имеется нескончаемое число локальных минимумов, но нет ни 1-го локального максимума.

12. Отыскать все точки локального минимума и локального максимума функции на .

Отыскать локальные Задача математического программирования решения в задачках 13-16.

13. .

14.

15.

16.

17. Отыскать меньшее значение функции , где ; - данные числа.

18. Показать, что в способе наискорейшего спуска направления и - ортогональны.

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

Задачка математического программирования (1) именуется традиционной задачей на условный экстремум, если , другими словами

(6)

Функция Лагранжа традиционной задачки на условный экстремум определена при , , .

Аксиома 6 (Нужное условие локальной оптимальности первого порядка)

Пусть функции безпрерывно дифференцируемы в некой округи точки . Если - локальное решение задачки (6), то существует число и вектор не равные нулю сразу и такие Задача математического программирования, что

. (7)

Если градиенты линейно независимы, то .

Условие линейной независимости градиентов ограничений в точке именуется условием регулярности. Числа именуются множителями Лагранжа. Функция Лагранжа, для которой , именуется постоянной.

Аксиома 7 (Нужное условие локальной оптимальности второго порядка)

Пусть функции два раза дифференцируемы в точке и безпрерывно дифференцируемы в некой её округи, причём градиенты линейно независимы Задача математического программирования. Если - локальное решение задачки (6), то

(8)

при всех , , удовлетворяющих (7), и всех таких, что

(9)

Аксиома 8 (Достаточное условие локальной оптимальности)

Пусть функции два раза дифференцируемы в точке , удовлетворяющей ограничениям . Представим, что при неких , производится условие (7), и не считая того

(10)

при всех ненулевых , удовлетворяющих условию (9).

Тогда - серьезное локальное решение задачки (6).

Пример 2.

Разглядим традиционную задачку на Задача математического программирования условный экстремум:

,

.

Решение:

1. Составим функцию Лагранжа:

= .

2. Выпишем нужные условия оптимальности и ограничение задачки:

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

Если то и , что противоречит необходимому условию оптимальности (не все множители Лагранжа равны нулю). Полагаем . Таким макаром, имеем Задача математического программирования регулярную функцию Лагранжа:

= .

Нужные условия перепишутся в виде:

Данная система имеет два решения:

1)

2)

3. Дальше разглядим матрицу вторых личных производных функции Лагранжа:

.

Для обозначенных решений матрица воспринимает соответственно вид:

, .

Выпишем условие (9):

, .

Исследуем приобретенные точки и :

3.1. Условие (9) для точки смотрится последующим образом: . Отсюда . Несложно проверить, что матрица удовлетворяет условию (10). Достаточное Задача математического программирования условие оптимальности выполнено, как следует, точка - серьезное локальное решение начальной задачки.

3.2. Из условия (9) для точки получаем . Проверим условие (8) для таких . Получаем , при . Нужное условие оптимальности второго порядка не производится. Точка не является решением задачки.

19. Из данного треугольника вырезать два равных круга большего радиуса.

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

21. Из всех треугольников с схожим основанием и одним и этим же углом при верхушке отыскать треугольник с большим периметром.

22. Даны две параллельные прямые и точка меж ними, лежащая на расстоянии от одной прямой и на Задача математического программирования расстоянии от другой прямой. Точка служит верхушкой прямых углов прямоугольных треугольников, две другие верхушки которых лежат на каждой из параллельных прямых. Какой из треугольников имеет меньшую площадь?

23. В треугольной пирамиде проводятся сечения, параллельные двум её непересекающимся рёбрам. Отыскать сечение с большей площадью.

24. Окно имеет форму прямоугольника, который Задача математического программирования сверху завершается полукругом. Каково должно быть основание прямоугольника для того, чтоб при данном периметре окно пропускало бы больше света?

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

26. В эллипс вписать Задача математического программирования прямоугольник большей площади.

27. Из всех эллипсов, у каких сумма осей постоянна и равна , отыскать больший по площади.

В задачках 28-31 требуется найти локальные минимумы и максимумы функции при выполнении ограничения .

28. , .

29. , .

30. , .

В задачках 28-30 .

31. , , - симметрическая матрица размера , .

32. Обосновать, что для всех 2-ух векторов , таких, что , справедливо неравенство .

Отыскать решения задач на условный Задача математического программирования экстремум:

33. , , .

34. , , .

35. , .

  1. Число разложить на множителей так, чтоб сумма их была меньшей.


zadachami-fotovistavki-yavlyayutsya.html
zadachami-izucheniya-disciplini-matematika-yavlyayutsya-sleduyushie.html
zadachami-kraevih-meropriyatij-yavlyayutsya-povishenie-urovnya.html