MathCAD: задача оптимизации в целых числах

По случаю, помогал тут человеку... Известно, что в Excel при решении задач линейного или нелинейного программирования инструментом "Поиск решения" можно дополнительно указывать, что искомые значения должны быть целочисленными. Можно ли аналогично решать целочисленные задачи в Маткаде стандартными функциями Maximize/Minimize?

Рассмотрим пример решения такой задачи обычным способом: для целевой функции f(x1,x2)=5*x2-3*x1 найти минимум при системе ограничений 2x1+3x2≤5, x1≥0, x2≥0:

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

Для некоторых версий MathCAD существует пакет расширения SOEP (Solving and Optimization Extension Pack), в котором имеется возможность уточнить тип результата - просто в завершающих функциях блока Given последним параметром ставится строка, указывающая тип переменной в системе уравнений. Местоположение целой переменной обозначается
I, бинарной - В, и т.д.:

f(x1,x2)=5*x2-3*x1
Given
2x1+3x2≤5 x1≥0 x2≥0
Minimize (f,x1,x2,"II")

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

Решение целочисленной задачи оптимизации перебором

Здесь мы, с учётом ограничений на неотрицательность x1 и x2 и ограничения-неравенства, просматриваем область с целочисленными значениями аргументов от 0 до 5 включительно и формируем матрицу из значений целевой функции от пар аргументов (x1,x2). При этом мы заменяем "неподходящие", то есть, не отвечающие ограничению-неравенству позиции в матрице "заведомо большим" значением MAX. После этого остаётся только найти в матрице минимальный элемент и определить его индексы стандартной функцией match.

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

07.05.2013, 15:11 [23223 просмотра]