整数规划求助
mathematica吧
全部回复
仅看楼主
level 3
2142 楼主
数模课老师布置了用Matlab的intlinprog指令求解这个0-1整数规划模型,但在MMA里面用Maximize这个指令算了很久都没得出结果。请各位大佬帮忙看看代码有没有什么错误或者应当改进的地方。。
X = Table[x[i, j], {i, 1, 1000}, {j, 1, 100}];
L = Table[
If[data[[i, j]] != 0, 11 - data[[i, j]], 0], {i, 1, 1000}, {j, 1,
100}];
con1 = Table[Total[X[[i]]] <= 3, {i, 1, 1000}];
con2 = Table[Total[X[[All, j]]] <= data2[[j]], {j, 1, 100}];
con3 = Table[X[[i, j]] <= L[[i, j]], {i, 1, 1000}, {j, 1, 100}];
con4 = Table[0 <= X[[i, j]] <= 1, {i, 1, 1000}, {j, 1, 100}] ;
G = Table[X[[i, j]]*L[[i, j]], {i, 1, 1000}, {j, 1, 100}];
Maximize[{Total[G, 2], Join[con1, con2, con3, con4]}, Flatten[X], Integers]
2019年10月27日 00点10分 1
level 3
2142 楼主
2019年10月27日 01点10分 2
吧务
level 12
mma里的线性规划建议用LinearProgramming,语法仔细看看帮助,乍一看可能会觉得有点懵,但其实就是把约束的等式和不等式都写成矩阵形式,没什么难的
(*定义部分*)
m = 1000;
n = 100;
d = RandomInteger[{0, 5}, n];
L = RandomInteger[{0, 10}, {m, n}];
(*求解部分*)
c = Flatten@L;
M = Join[
SparseArray[{{i_, j_} /; (i - 1) n < j <= i*n :> 1}, {m, m*n}],
SparseArray[Table[Band[{1, j}] -> 1, {j, 1, m*n, n}], {n, m*n}],
SparseArray[{Band[{1, 1}] -> 1}, {m*n, m*n}]
];
b = Join[
ConstantArray[3, m],
d,
Flatten@L
];
result = LinearProgramming[-c, -M, -b, ConstantArray[{0, 1}, m*n],
Integers]; // AbsoluteTiming
(*检验部分*)
X = ArrayReshape[result, {m, n}];
Total[X, {2}] // Max
Total[X] - d // Max
X - L // Max
{Total[X, 2], 3*m, Total[d]}
你的代码里L和d的定义都没给,我就随便生成了两组随机数。速度还可以,在我这3s之内就出来了。
(另:直接把Maximize换成NMaximize也可以解决你的问题,速度比LinearProgramming稍慢一点,但胜在直观
2019年10月27日 06点10分 4
可以了,我再仔细看看帮助,非常感谢!
2019年10月27日 09点10分
[大拇指]
2019年10月28日 08点10分
1