排列与统筹学结合的经典问题,非高手勿入。
问题:
设方程组(如下)有解:
X1+3+X12=X2
X2+4+X13=X3
X2+4+X14=X4
X3+5+X15=X5
X4+7+X16=X5
X5+8+X17=X6
X6+1+X18=48
X7+5+X19=X8
X8+1+X20=X9
X8+1+X21=X10
X10+2+X22=29
X9+9+X23=X11
X11+7+X24=29
(Xi≥0;i =1,2,…24)
集合:
A={X1,X3,X5,X7,X8,X10,X11};
B={X2,X4,X6,X9};
设A中元素组成m组排列,B中元素组成n组排列.
每个集合中的元素取且仅取一次.(如A中可以形成3组排列:X3X8X7,X1,X5X10X11)
每个排列中元素按照排列顺序满足条件:
Xi+Txi≤Xj (j为排在i后元素,Txi为Xi所在上述方程式左侧时,该方程式中的常量,如Tx2=4)
(如:排列X1X3X7,满足条件
X1+3≤X3
X3+5≤X7 )
求满足方程组时,m+n最小时的排列.