Команда bintprog из Optimization Toolbox решает проблемы программирования 0-1 с ограничением неравенства и необязательным ограничением равенства: Ax ‹= b, где A - матрица, а b - вектор-столбец.
У меня проблема вида | Ax | ‹= B или, что то же самое, -b‹ = Ax ‹= b. Есть ли способ решить такую проблему с помощью Matlab?
Это очень просто:
У вас есть |Ax| <= b. Это эквивалентно (как вы сами отметили) -b <= Ax <= b.
Итак, у вас есть дополнительные ограничения неравенства: Ax <= b и -Ax <= b.
Таким образом, у вас есть все AA = [ A ; -A ] и bb = [b;b], определяющие ваш пресс. ограничения стоимости:
x = bintprog( f, AA, bb );
Если size (A) = [n, m], ваши ограничения имеют вид
for each {i in 1..m}
-b <= sum {j in 1..n} a_{ij} * x_{ij} <= b
это то же самое, что и два набора ограничений
for each {i in 1..m}
sum {j in 1..n} a_{ij} * x_{ij} <= b
sum {j in 1..n} a_{ij} * x_{ij} >= -b
Поскольку вам нужно записать его в виде Ax ‹= b, это будет выглядеть так:
for each {i in 1..m}
sum {j in 1..n} a_{ij} * x_{ij} <= b
sum {j in 1..n} -a_{ij} * x_{ij} <= b
В MATLAB, учитывая ваши исходные A и b, вы можете сделать эти "удвоенные" матрицы ограничений с
A = [A; -A];
b = [b; b];
и решите свою целочисленную программу с этими новыми (A, b).
