Maple 9.5/10 в математике, физике и образовании - Владимир Дьяконов

> maximize(x+y, {4*x+2*y <= 10, 3*x+4*y <= 16}, NONNEGATIVE);

> maximize(x+y, {3*x+2*y <= 5, 2*x+4*y <=4});

> z := 2*x1 - x2 + 3*x3;

z := 2x1 - x2 + 3x3

> cnts1 := [x2+2*x3 <= 1, 2*x1-4*x2+6*x3 <= 3, -x1+3*x2+4*x3 <= 12];

cnts1 := [x2+2x3 ≤ 1, 2x1-4x2+6x3 ≤ 3, -x1+3x2+4x3 ≤ 12]

> sol1 := maximize(z,cnts1,NONNEGATIVE);

При использовании функций minimize и maximize надо не забывать, что это переопределенные функции — аналогичные по названию функции есть в ядре и они реализуют иные методы вычислений. Для возврата к исходному определению функций надо выполнить команду restart.

6.5.4. Прочие функции пакета simplex

Функция basis(C) возвращает базис для системы линейных уравнений С. Например:

> basis([х = 2*z+w, z = 2*y-w]);

[x, z]

Функция convexhull(ps) возвращает выпуклую оболочку множества точек ps. Например:

> convexhull({[0,0], [1,1], [2,-1], [1,1/3],[1,1/2]));

[[0, 0], [2, -1], [1, 1]]

Для определения констант для системы линейных уравнений или неравенств служит функция cterm(C):

> cterm([2*х+y<=6,7*y-z-3=4]);

[6, 7]

Функция define zero(C) возвращает ближайшее ненулевое значение, зависящее от установки переменной Digits:

> define_zero();

.1000000000 10-7

> Digits:=40;

Digits := 40

> define_zero();

.1000000000000000000000000000000000000000 10-37

> define_zero(1*10^(-10));

.1000000000000000000000000000000000000000 10-9

Функция display(C) имеет еще и форму display(C,[x, у, z]). Она задает вывод линейных уравнений и неравенств в матричной форме:

> display({2*x+5*y-z<= 0, 2*w-4*y-z<=2});

Функция dual(f, С, у) имеет следующие параметры: f — линейное выражение, С — множество неравенств и у — имя. Эта функция возвращает сопряженное с f выражение:

> dual(х-y,{2*х+3*y<=5,3*х+6*y<=15}, z);

15z1+5z2, {1 ≤ 3z1+2z2, -1 ≤ 6z1+3z2}

Функция feasible может быть задана в трех формах:

feasible(С)

feasible(С,vartype)

feasible(С,vartype,'NewC','Transform')

Здесь параметр vartype может иметь значения NONNEGATIVE или UNRESTRICTED. Эта функция определяет систему как осуществимую или нет:

> feasible({2*х+3*y<=5, 3*х+6*y<=15), NONNEGATIVE);

true

> feasible({2*х+3*y<=5, 3*х+6*y<=-15}, NONNEGATIVE);

false

Если функция возвращает логическое значение true, то заданная система осуществима, а если false — неосуществима, то есть ни при каких значениях переменных не способна удовлетворить записанным неравенствам и равенствам.

Функция pivot(C, х, eqn) конструирует новую систему с заданным главным элементом:

> pivot({_SL1=5-4*x-3*y,_SL2=4-3*x-4*y),х,[_SL1=5-4*x-3*y]);

Функция pivoteqn(C, var) возвращает подсистему для заданного диагонального элемента С:

> pivoteqn((_SL1 = 5-3*х-2*y, _SL2 = 4-2*х-2*y}, х);

[_SL1 = 5 - 3х - 2y]

Функция pivotvar(f, List) или pivotvar(f) возвращает список переменных, имеющих положительные коэффициенты в выражении для целевой функции:

> pivotvar(x1-2*x2+3*x3-x4);

x1

> pivotvar(x1+2*х3-3*х4, [x4,x3,x1]);

x3

Функция ratio(C, х) возвращает список отношений, задающих наиболее жесткие ограничения:

> ratio([SL1=10-3*x-2*y, SL2=8-2*x-4*y], x);

Функция setup может иметь три формы:

setup(С)

setup(С, NONNEGATIVE)

setup(С, NONNEGATIVE, 't')

Она обеспечивает конструирование множества уравнений с переменными в левой части:

> setup({2*х+3*y<=5,3*х+5*y=15));

Последняя функция — standartize(C) — конвертирует список уравнений (неравенств) в неравенства типа «меньше или равно»:

> standardize({2*х+3*у<=5,3*х+5*у=15});

{2 х + 3 y ≤ 5, 3х + 5у ≤ 15, -3х -5y ≤ -15}

6.6. Новый пакет оптимизации Optimization в Maple 9.5

В систему Maple 9.5 был добавлен новый пакет оптимизации Optimization, основанный на новейших существенно улучшенных алгоритмах оптимизации. С его помощью можно решать не только задачи линейного, но и квадратичного и нелинейного программирований с повышенной степенью визуализации.

6.6.1. Доступ к пакету Optimization и его назначение

Пакет оптимизации Optimization вызывается как обычно:

> with(Optimization);

[ImportМPS, Interactive, LPSolve, LSSolve, Maximize, Minimize, NLPSolve, QPSolve]

Warning, the name changecoords has been redefined

Для получения справки по пакету надо исполнить команду:

> help(Optimization);

Пакет использует при вычислениях алгоритмы группы NAG, которые считаются наиболее эффективными при реализации численных методов вычислений, в частности реализующих алгоритмы оптимизации. Пакет вводит 8 функций. Две из них это переопределенные функции вычисления максимума Maximize и минимума Minimize. Кроме того, пакет имеет 4 решателя уравнений с заданными ограничениями, реализующих следующие методы:

• LPSolve — линейное программирование;

• LSSolve — улучшенная реализация метода наименьших квадратов;

• QPSolve — квадратичное программирование;

• NLPSolve — нелинейное программирование.

Функция ImportMPC обеспечивает ввод данных для оптимизации из файла, а функций Interactive позволяет работать с интерактивным Maplet-окном для оптимизации.

С пакетом Optimization можно познакомиться по его справке. В ее разделе Examples есть довольно обширный документ с примерами применения пакета — дополнительными к тем, которые даются к функциям пакета в справке. Начало этого документа представлено на рис. 6.3. В нем представлены основные задачи, решаемые пакетом Optimization — линейное, квадратичное и нелинейное программирование, а также приближение данных и функциональных зависимостей методом наименьших квадратов (нелинейная регрессия).

Рис. 6.3. Начало документа с примерами применения пакета Optimization

6.6.2. Работа с функциями Minimize и Maximize

Функции Minimize и Maximize служат для поиска минимумов и максимумов математических выражений с учетом ограничений самыми современными численными методами. Функции записываются в виде:

Minimize(obj [, constr, bd, opts])

Minimize(opfobj [, ineqcon, eqcon, opfbd, opts])

Maximize(obj [, constr, bd, opts])

Maximize(opfobj [, ineqcon, eqcon, opfbd, opts])

Параметры функций следующие:

• obj — алгебраический объект, целевая функция;

• constr — список с ограничивающими условиями;

• bd — последовательность вида name=range, задающая границы для одной или более переменных;

• opts — равенство или равенства вида option=value, где option одна из опции feasibilitytolerance, infinitebound, initialpoint, iterationlimit или optimalitytolerance, специфицированных в команде Minimize или Maximize.

• opfobj — процедура, целевая функция;

• ineqcon — множество или список процедур с ограничениями типа неравенств;

• eqcon — множество или список процедур с ограничениями типа равенств;

• opfbd — последовательность пределов; границы для всех переменных; Примеры применения этих функций представлены ниже:

> Maximize(sin(х)/х);

[1., [х=2.93847411867272567 10-11]]

> Minimize(х^2+у^2);

[0., [х=0., у=0.]]

> Minimize(sin(х)/х, initialpoint={x=5});

[-0.217233628211221636 , [х=4.49340945792364720 ]]

> Maximize(sin(x*y*z));

[1., [x=1.16244735150962364, z=1.16244735150962364, y=1.16244735150962364]]

> Minimize(2*х+3*y, {3*х-y<=9, х+y>=2}, assume=nonnegative);

[4., [х=2., y=0.]]

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

6.6.3. Линейное программирование — LPSolve

Для решения задач линейного программирования в пакете Optimization введена функция:

LPSolve(obj [, constr, bd, opts])

Она имеет следующие параметры:

• obj — алгебраическое выражений, целевая функция;

• constr — множество или список линейных ограничений;

• bd — последовательность вида name=range, задающая границы одной или многих переменных;

• opts — равенство или равенства в форме option=value, где option одна из опций assume, feasibilitytolerance, infinitebound, initialpoint, iterationlimit или maximize, специализированных для команды LPSolve.

Пример на решение задачи линейного программирования дан на рис. 6.4. Здесь оптимизируется целевая функция -3x-2у, которая линейно зависит от переменных х и у. В этом примере интересна техника графической визуализации решения.

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

Эта функция может задаваться также в матричной форме:

LPSolve(c [, lc, bd, opts])

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