黑白球三维排列游戏.doc

黑白球三维排列游戏一、问题提出（略）.二、问题假设1将黑白球视作没有大小的点，将每个小方盒也视作一个点。三、符号说明： 0表示第i个盒子放白球，1表示第i个盒子放黑球；：0表示第j条直线上所有的球为相同颜色，1表示第j条直线上的球为不同颜色,j=1，2，27.四、问题分析与建模这虽然是一个排列游戏，但是其中蕴含有相当丰富的整数规划特性，因此在此讨论它。将14个黑球和13个白球放入333的三维阵中，其排列方式非常多，要想采用穷举法求解的原问题非常困难的。首先，我们对小方盒编号为1到27，具体的编号规则为参见图1。于是，对于每个小方盒，我们可以引入一个0-1变量：表示第i个盒子中装有白球，表示第i个盒子中装有黑球，如此引入的01变量共有27个。并且由于黑球的个数为14，因此。1. 可能的直线对于此问题，首先需要知道：在这个333的三维阵中,哪些小方盒连接起来可以构成一条直线？这样的直线共有多少条？为了确定这些直线，我们首先考虑此333的三维阵的行、列和纵三个方向上的9个截面上的直线有哪些，然后考虑不全在任何一个截面上直线有哪些。与水平面平行的截面有三个，见图2。对应于每一个截面上的三点共线的情况共有8种，分别记为：s3=19，20，21,22，23，24,25,26,27,19,22,25,20,23,26,21,24,27,19,23,27,21,23,25；s2=10,11,12,13,14,15,16,17,18,10,13,16,11,14,17,12,15,18,10,14,18,12,14,16；s1=1,2,3,4,5,6,7,8,9,1,4,7,2,5,8,3,6,9,1,5,9,3,5,7。与水平面相垂直的截面共有6个，见图3和图4。与图3对应的每一个截面上共线的三点情况也有8种，由于它们与图1中的情况会出现重叠，去掉重叠的三种情况，新增加的三点共线情况各有5种，分别记为：s4=1,10,19，2,11,20，3,12,21，1,11,21，3,11,19；s5=4,13,22，5,14,23，6,15,24，4,14,24，6,14,22；s6=7,16,25，8,17,26，9,18,27，7,17,27，9,17,25。与图4对应的每一个截面上共线的三点情况也有8种，由于它们与图1和图2中的情况会出现重叠，去掉重叠的6种情况，新增加的三点共线情况各有2种，分别记为：s7=1,13,25,7,13,19；s8=2,14,26,8,14,20；s9=3,15,27,9,15,21。三个点不同在上面所介绍的任何一个或者两个截面的情况参见图5。新增加的三点共线的情况有4种，记为：s10=1,14,27,3,14,25,9,14,19,7,14,21。综合前面的分析，在此333的三维阵中，所有能够共线的三点共有49种情况，它们组成49条不同的直线，用s表示，则.2. 成为直线的条件根据前面分析的可能的直线的结果，我们来确定当放入黑白球之后，三个相同颜色的球在同一直线上满足的条件。设第j条直线上的三个盒子的编号分别为：j1，j2，j3，记为 ，在直线j上三个盒子中放入的球的颜色情况为：。引入0-1变量：表示第j条直线上的三个球的颜色不完全相同，表示第j条直线上的三个球的颜色完全相同。这样原问题转化为求一种黑白球的方法，使得取得最小值。并且有约束： （1） （2）此即放入黑白球之后，每条直线上的所有球体颜色相同的条件为（1），每条直线上的所有球体颜色不相同的条件为（2）。此时如何将引入到（1）或者(2)中右边的表达式中，成为我们考虑的重点。为了将引入表达式（1）中，变成 （3）或者将引入表达式（2）中，变成 (4) 注1：此处（3）和（1）并不等价，但是考虑到我们的目标为，这样做也是可以的；注2：此处（4）和（2）是等价的，但是与（3）相比增加了98个约束条件；注3：在建立模型时，（3）和（4）这两组约束条件只需要一组即可。3. 数学模型根据前面的分析，我们可以建立如下的01规划的数学模型：该模型是一个含有76个01变量，99个约束条件的01整数规划问题。五、模型求解1.求解方法理论上，对于01整数规划问题可以采用基于线性规划的分枝定界法求解。详细算法参见1。2.计算结果利用数学软件lingo中已有的关于分枝定界法的实现，可以方便地求出原问题的解，程序及程序输出见附录1。根据我们计算出来的结果可知，相同颜色的最少的直线数为4条，并且有许多的备择解，下面给出其中一种解的图形表示（图6），图中灰色的盒子表示放黑球，白色的盒子放置白球。黑白球按照图6所示的放置方法，所形成的四条直线为：4,13,22，10,13,16全由白球相连构成；6,15,24，12,15,18全由黑球相连构成。六、模型推广及讨论（略）.七、参考文献1 八、附录1. 程序model:sets:linecols/1.3/:;linerows/1.49/: r;links(linerows,linecols):lines;balls/1.27/:delta;endsetsmin=sum(linerows(i):r(i);sum(balls(i):delta(i)=14;for(linerows(i):sum(linecols(j):delta(lines(i,j)+r(i)=1);for(linerows(i):sum(linecols(j):delta(lines(i,j)-r(i)=2);for(linerows(i):bin(r(i);for(balls(i):bin(delta(i);data:lines=1 2 3 4 5 6 7 8 9 1 4 7 2 5 8 3 6 9 1 5 9 3 5 7 10 11 12 13 14 15 16 17 18 10 13 16 11 14 17 12 15 18 10 14 18 12 14 16 19 20 21 22 23 24 25 26 27 19 22 25 20 23 26 21 24 27 19 23 27 21 23 25 1 10 19 2 11 20 3 12 21 1 11 21 3 11 19 4 13 22 5 14 23 6 15 24 4 14 24 6 14 22 7 16 25 8 17 26 9 18 27 7 17 27 9 17 25 1 13 25 7 13 19 2 14 26 8 14 20 3 15 27 9 15 21 1 14 27 3 14 25 7 14 21 9 14 19;enddataend2. 输出结果 global optimal solution found at iteration: 103652 objective value: 4.000000 variable value reduced cost r( 1) 0.000000 1.000000 r( 2) 0.000000 1.000000 r( 3) 0.000000 1.000000 r( 4) 0.000000 1.000000 r( 5) 0.000000 1.000000 r( 6) 0.000000 1.000000 r( 7) 0.000000 1.000000 r( 8) 0.000000 1.000000 r( 9) 0.000000 1.000000 r( 10) 0.000000 1.000000 r( 11) 0.000000 1.000000 r( 12) 1.000000 1.000000 r( 13) 0.000000 1.000000 r( 14) 1.000000 1.000000 r( 15) 0.000000 1.000000 r( 16) 0.000000 1.000000 r( 17) 0.000000 1.000000 r( 18) 0.000000 1.000000 r( 19) 0.000000 1.000000 r( 20) 0.000000 1.000000 r( 21) 0.000000 1.000000 r( 22) 0.000000 1.000000 r( 23) 0.000000 1.000000 r( 24) 0.000000 1.000000 r( 25) 0.000000 1.000000 r( 26) 0.000000 1.000000 r( 27) 0.000000 1.000000 r( 28) 0.000000 1.000000 r( 29) 0.000000 1.000000 r( 30) 1.000000 1.000000 r( 31) 0.000000 1.000000 r( 32) 1.000000 1.000000 r( 33) 0.000000 1.000000 r( 34) 0.000000 1.000000 r( 35) 0.000000 1.000000 r( 36) 0.000000 1.000000 r( 37) 0.000000 1.000000 r( 38) 0.000000 1.000000 r( 39) 0.000000 1.000000 r( 40) 0.000000 1.000000 r( 41) 0.000000 1.000000 r( 42) 0.000000 1.000000 r( 43) 0.000000 1.000000 r( 44) 0.000000 1.000000 r( 45) 0.000000 1.000000 r( 46) 0.000000 1.000000 r( 47) 0.000000 1.000000 r( 48) 0.000000 1.000000 r( 49) 0.000000 1.000000 lines( 1, 1) 1.000000 0.000000 lines( 1, 2) 2.000000 0.000000 lines( 1, 3) 3.000000 0.000000 lines( 2, 1) 4.000000 0.000000 lines( 2, 2) 5.000000 0.000000 lines( 2, 3) 6.000000 0.000000 lines( 3, 1) 7.000000 0.000000 lines( 3, 2) 8.000000 0.000000 lines( 3, 3) 9.000000 0.000000 lines( 4, 1) 1.000000 0.000000 lines( 4, 2) 4.000000 0.000000 lines( 4, 3) 7.000000 0.000000 lines( 5, 1) 2.000000 0.000000 lines( 5, 2) 5.000000 0.000000 lines( 5, 3) 8.000000 0.000000 lines( 6, 1) 3.000000 0.000000 lines( 6, 2) 6.000000 0.000000 lines( 6, 3) 9.000000 0.000000 lines( 7, 1) 1.000000 0.000000 lines( 7, 2) 5.000000 0.000000 lines( 7, 3) 9.000000 0.000000 lines( 8, 1) 3.000000 0.000000 lines( 8, 2) 5.000000 0.000000 lines( 8, 3) 7.000000 0.000000 lines( 9, 1) 10.00000 0.000000 lines( 9, 2) 11.00000 0.000000 lines( 9, 3) 12.00000 0.000000 lines( 10, 1) 13.00000 0.000000 lines( 10, 2) 14.00000 0.000000 lines( 10, 3) 15.00000 0.000000 lines( 11, 1) 16.00000 0.000000 lines( 11, 2) 17.00000 0.000000 lines( 11, 3) 18.00000 0.000000 lines( 12, 1) 10.00000 0.000000 lines( 12, 2) 13.00000 0.000000 lines( 12, 3) 16.00000 0.000000 lines( 13, 1) 11.00000 0.000000 lines( 13, 2) 14.00000 0.000000 lines( 13, 3) 17.00000 0.000000 lines( 14, 1) 12.00000 0.000000 lines( 14, 2) 15.00000 0.000000 lines( 14, 3) 18.00000 0.000000 lines( 15, 1) 10.00000 0.000000 lines( 15, 2) 14.00000 0.000000 lines( 15, 3) 18.00000 0.000000 lines( 16, 1) 12.00000 0.000000 lines( 16, 2) 14.00000 0.000000 lines( 16, 3) 16.00000 0.000000 lines( 17, 1) 19.00000 0.000000 lines( 17, 2) 20.00000 0.000000 lines( 17, 3) 21.00000 0.000000 lines( 18, 1) 22.00000 0.000000 lines( 18, 2) 23.00000 0.000000 lines( 18, 3) 24.00000 0.000000 lines( 19, 1) 25.00000 0.000000 lines( 19, 2) 26.00000 0.000000 lines( 19, 3) 27.00000 0.000000 lines( 20, 1) 19.00000 0.000000 lines( 20, 2) 22.00000 0.000000 lines( 20, 3) 25.00000 0.000000 lines( 21, 1) 20.00000 0.000000 lines( 21, 2) 23.00000 0.000000 lines( 21, 3) 26.00000 0.000000 lines( 22, 1) 21.00000 0.000000 lines( 22, 2) 24.00000 0.000000 lines( 22, 3) 27.00000 0.000000 lines( 23, 1) 19.00000 0.000000 lines( 23, 2) 23.00000 0.000000 lines( 23, 3) 27.00000 0.000000 lines( 24, 1) 21.00000 0.000000 lines( 24, 2) 23.00000 0.000000 lines( 24, 3) 25.00000 0.000000 lines( 25, 1) 1.000000 0.000000 lines( 25, 2) 10.00000 0.000000 lines( 25, 3) 19.00000 0.000000 lines( 26, 1) 2.000000 0.000000 lines( 26, 2) 11.00000 0.000000 lines( 26, 3) 20.00000 0.000000 lines( 27, 1) 3.000000 0.000000 lines( 27, 2) 12.00000 0.000000 lines( 27, 3) 21.00000 0.000000 lines( 28, 1) 1.000000 0.000000 lines( 28, 2) 11.00000 0.000000 lines( 28, 3) 21.00000 0.000000 lines( 29, 1) 3.000000 0.000000 lines( 29, 2) 11.00000 0.000000 lines( 29, 3) 19.00000 0.000000 lines( 30, 1) 4.000000 0.000000 lines( 30, 2) 13.00000 0.000000 lines( 30, 3) 22.00000 0.000000 lines( 31, 1) 5.000000 0.000000 lines( 31, 2) 14.00000 0.000000 lines( 31, 3) 23.00000 0.000000 lines( 32, 1) 6.000000 0.000000 lines( 32, 2) 15.00000 0.000000 lines( 32, 3) 24.00000 0.000000 lines( 33, 1) 4.000000 0.000000 lines( 33, 2) 14.00000 0.000000 lines( 33, 3) 24.00000 0.000000 lines( 34, 1) 6.000000 0.000000 lines( 34, 2) 14.00000 0.000000 lines( 34, 3) 22.00000 0.000000 lines( 35, 1) 7.000000 0.000000 lines( 35, 2) 16.00000 0.000000 lines( 35, 3) 25.00000 0.000000 lines( 36, 1) 8.000000 0.000000 lines( 36, 2) 17.00000 0.000000 lines( 36, 3) 26.00000 0.000000 lines( 37, 1) 9.000000 0.000000 lines( 37, 2) 18.00000 0.000000 lines( 37, 3) 27.00000 0.000000 lines( 38, 1) 7.000000 0.000000 lines( 38, 2) 17.00000 0.000000 lines( 38, 3) 27.00000 0.000000 lines( 39, 1) 9.000000 0.000000 lines( 39, 2) 17.00000 0.000000 lines( 39, 3) 25.00000 0.000000 lines( 40, 1) 1.000000 0.000000 lines( 40, 2) 13.00000 0.000000 lines( 40, 3) 25.00000 0.000000 lines( 41, 1) 7.000000 0.000000 lines( 41, 2) 13.00000 0.000000 lines( 41, 3) 19.00000 0.000000 lines( 42, 1) 2.000000 0.000000 lines( 42, 2) 14.00000 0.000000 lines( 42, 3) 26.00000 0.000000 lines( 43, 1) 8.000000 0.000000 lines( 43, 2) 14.00000 0.000000 lines( 43, 3) 20.00000 0.000000 lines( 44, 1) 3.000000 0.000000 lines( 44, 2) 15.00000 0.000000 lines( 44, 3) 27.00000 0.000000 lines( 45, 1) 9.000000 0.000000 lines( 45, 2) 15.00000 0.000000 lines( 45, 3) 21.00000 0.000000 lines( 46, 1) 1.000000 0.000000 lines( 46, 2) 14.00000 0.000000 lines( 46, 3) 27.00000 0.000000 lines( 47, 1) 3.000000 0.000000 lines( 47, 2) 14.00000 0.000000 lines( 47, 3) 25.00000 0.000000 lines( 48, 1) 7.000000 0.000000 lines( 48, 2) 14.00000 0.000000 lines( 48, 3) 21.00000 0.000000 lines( 49, 1) 9.000000 0.000000 lines( 49, 2) 14.00000 0.000000 lines( 49, 3) 19.00000 0.000000 delta( 1) 1.000000 0.000000 delta( 2) 1.000000 0.000000 delta( 3) 0.00