Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Оптимизация методами матана (с пом. производных)

На главную Математический раздел Криптография и т.д. Новости

Что-то вроде теории

Существуют задачи оптимизации, которые удобно решать следующим образом: составляется целевая функция f и методами матанализа ищется, при каких значениях аргумента эта функция принимает наибольшее (наименьшее) значение. В частности, если f - функция одной переменной: f=f(x), при этом x лежит на отрезке [a; b], то нужно посмотреть, какие значения принимает f на концах отрезка и в точках экстремума, поскольку в других местах оптимального решения не может быть. Если же x лежит в промежутке (a; b), то ограничиваемся точками экстремума: оптимальное решение может быть только там.

Точки экстремума ищутся обычно с помощью производных (ну то есть вычисляется производная от f, зануляется, далее смотрим, в каких точках она обращается в нуль, причём так, что слева и справа от точки имеет разные знаки. Если слева от точки x0 производная отрицательна, справа положительна, то x0 - точка минимума, поскольку до этой точки функция f убывала, а при переходе через точку стала расти. Ну соответственно про точку максимума догадаетесь сами :-) ).

Иногда везёт - функция несложная (синус, парабола), и тогда точки экстремума удаётся найти и без производных. Скажем, если f(x) = a*x*x + b*x + c, то "вершина" ищется как -b/(2a). Эта формула выводится с помощью производной, но её легко запомнить и не выводить по-честному)))

Немного практики: парочка задач на оптимизацию

Нам поступило сверхсекретное задание, где требуется выполнить оптимизацию. Нам нужно занять территорию как можно большей площади, огородив её забором. Площадка должна быть прямоугольной, у нас есть доски на то, чтобы построить забор периметра p. Каковы должны быть стороны прямоугольника x, y?

Сначала попробуем прикинуть без особых выкрутасов. Пусть, скажем, p = 16, тогда x + y=8. Если берём стороны 2 и 6, получаем площадь 12, если 3 и 5 - 15, если 4 и 4 - 16. Кажется, что правильным ответом должно быть x=y=p/4, то есть это квадрат... Это действительно так, но далее обоснуем это строго.

Выражаем y: 2(x+y) = p; y = p/2 - x. Тогда S(x) = x(p/2 - x) = px/2 - x*x, x - из множества (0; p/2).

S(x) - целевая функция, нужно добиться, чтобы её значение было наибольшим. Берём производную целевой функции: S'(x) = p/2 - 2x. При x = p/4 производная обнуляется. Если x < p/4, производная положительна, при x > p/4 производная отрицательна. Стало быть, x = p/4 и есть точка наибольшего значения целевой функции. Дальше вспоминаем, как y зависит от x и видим: в натуре квадрат.

Теперь попробуем решить другую задачку на оптимизацию. Пусть теперь нужно огородить прямоугольную площадку заданной площади так, чтобы периметр был наименьшим (соответственно мы тратим меньше материала на забор). Искомые параметры: стороны x, y.

И ежу понятно, что S = xy. Это нам и понадобится. Избавляемся временно от y: y = S/x; p = 2(x+y) = 2(x + S/x). Далее минимизируем периметр p, для упрощения вместо p разберёмся с полупериметром. Итак, целевая функция: f(x) = x + S/x, множество значений аргумента: x > 0. Берём производную целевой функции: f'(x) = 1-S/(x*x). Точка экстремума: . Слева от неё производная отрицательна, справа положительна. Стало быть, мы нашли точку минимума. Дальше остаётся опять найти y и снова убедиться "ёлки-палки, да это же квадрат!".

copyright © Исканцев Н.В., 2012

К математическому разделу
На главную
X