9. Оптимизационные задачи

Оптимизационные задачи

Поиск максимального и минимального чисел в списке

В практике математических прикладных вычислений важная роль принадлежит оптимизационным задачам, например таким, как поиск минимальных и максимальных значений функций одной или нескольких переменных. Mathematica дает разнообразные возможности решения задач оптимизации — от поиска элементов списка с минимальным или максимальным значением до поиска локальных и даже глобальных минимумов функций, заданных аналитически.

Для поиска максимального и минимального значений ряда чисел, входящих в список, система Mathematica предоставляет следующие средства:

• Max [xl, х2,...]— возвращает наибольшее значение из xi;
• Max[{xl, x2,...}, {yl,...},...] — выбирает наибольший элемент из нескольких списков;
• Min[xl, x2,...] — возвращает наименьшее значение из xi;
• Min[{xl, x2,...}, {yl,...},...] — выбирает наименьший элемент из нескольких списков.

Следующие примеры показывают действие этих простых функций.

Поиск локального минимума аналитической функции

Если нужен поиск локального минимума некоторой аналитической функции, используется функция FindMinimum [ f, {х, х0 } ], которая выполняет поиск локального минимума функции f, начиная со значения х=х0, и возвращает его значение.

Для указания градиента минимизируемой функции используется опция Gradient.

Приведем примеры применения функции FindMinimum:

FindMinimum[-хЕхр[-2 х] , {х, 1}]

{-0.18394, {х^ 0.5}}

FindMinimum[-хЕхр[-2 х] , {х, 0.2, 6, 1}]

{-0.18394, {х^ 0.5}}

FindMinimum [-5 xExp[-x/2] (2 + Sin[3x]), {х, 1}]

{-7.17833, {х^ 0.783139}}

FindMinimum[-5xExp[- x/2] (2 + Sin[3 x]) , {x, 3}]

(-10.6299, {x^ 2.5805}}

FindMinimum[-5xExp[- x/2] (2+Sin[3x]), {x, 4}]

{-6.79134, {x^ 4.6179}}

FindMinimum[l00 (y-x2)2+ (1 -x)2, {x, 0}, {y, 0},

AccuracyGoal-»Automatic]

{9.90511X10-13, {x->l., y^ 0.999999}}

Эти примеры показывают, что выбирая разные начальные значения х, можно найти ряд минимумов функции f(x), разумеется, если таковые имеют место. Если необходимо разыскивать локальные максимумы, достаточно перед функцией поставить знак «минус» или умножить ее на -1.

Поиск глобального максимума и минимума аналитической функции

Следующие две функции служат для поиска глобального максимума и минимума аналитически заданной функции:

• ConstrainedMax [f, {inequalities}, {x, у,...}] — ищет глобальный максимум функции f в области, определяемой неравенствами inequalities. Полагается, что все переменные х, у... неотрицательны;
• ConstrainedMin [f, {inequalities}, {x, у,...}]— ищет глобальный минимум функции f в области, определяемой неравенствами inequalities. Все переменные х, у... полагаются неотрицательными.

Решение задач линейного программирования

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

LinearProgramming[с, m, b]

которая ищет вектор х, минимизирующий величину с. х в соответствии с условиями m.x>=b и х>=0.

Рассмотрим типичный пример на линейное программирование. Пусть цех малого предприятия должен изготовить 100 изделий трех типов, причем не менее 20 штук каждого. На изготовление этих изделий уходит, соответственно, 4, 3,4 и 2 кг металла. Имеющийся в наличии запас материала — 700 кг. Спрашивается, сколько изделий xl, х2 и хЗ каждого типа надо выпустить для обеспечения максимальной стоимости продукции, если цена изделий равна, соответственно, 4, 3 и 2 рубля.

Ниже представлено решение этой задачи с помощью функции ConstrainedMax:

ConstrainedMax [

4 * xl + 3 * x2 + 2 * хЗ ,

{xl >= 20, x2 >= 20, хЗ >= 20,

4 * xl + 3 . 4 * x2 + 2 * x3 <= 340 ,

4 .75 * xl + 11 * x2 + 2 * x3 < = 700 ,

xl + x2 + x3 == 100},

{xl, x2, x3}]

{332., {xl^ 56^x2^ 20., x3^24.}}

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

Задачи минимизации традиционно относятся к сложным задачам программирования — особенно при поиске глобального минимума. Наличие в ядре системы Mathematica их реализаций делает систему привлекательной для решения задач этого класса.