黑白球三维排列游戏.docx
《黑白球三维排列游戏.docx》由会员分享，可在线阅读，更多相关《黑白球三维排列游戏.docx（21页珍藏版）》请在冰点文库上搜索。
黑白球三维排列游戏
黑白球三维排列游戏
一、问题提出
.
二、问题假设
1．将黑白球视作没有大小的点，将每个小方盒也视作一个点。
三、符号说明
：
0表示第i个盒子放白球，1表示第i个盒子放黑球；
：
0表示第j条直线上所有的球为相同颜色，1表示第j条直线上的球为不同颜色,j=1，2，…，27.
四、问题分析与建模
这虽然是一个排列游戏，但是其中蕴含有相当丰富的整数规划特性，因此在此讨论它。
将14个黑球和13个白球放入3×3×3的三维阵中，其排列方式非常多，要想采用穷举法求解的原问题非常困难的。
首先，我们对小方盒编号为1到27，具体的编号规则为参见图1。
于是，对于每个小方盒，我们可以引入一个0--1变量
：
表示第i个盒子中装有白球，
表示第i个盒子中装有黑球，如此引入的0—1变量共有27个。
并且由于黑球的个数为14，因此
。
1.可能的直线
对于此问题，首先需要知道：
在这个3×3×3的三维阵中,哪些小方盒连接起来可以构成一条直线？
这样的直线共有多少条？
为了确定这些直线，我们首先考虑此3×3×3的三维阵的行、列和纵三个方向上的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}}。
综合前面的分析，在此3×3×3的三维阵中，所有能够共线的三点共有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.数学模型
根据前面的分析，我们可以建立如下的0—1规划的数学模型：
该模型是一个含有76个0—1变量，99个约束条件的0—1整数规划问题。
五、模型求解
1.求解方法
理论上，对于0—1整数规划问题可以采用基于线性规划的分枝定界法求解。
详细算法参见[1]。
2.计算结果
利用数学软件Lingo中已有的关于分枝定界法的实现，可以方便地求出原问题的解，程序及程序输出见附录1。
根据我们计算出来的结果可知，相同颜色的最少的直线数为4条，并且有许多的备择解，下面给出其中一种解的图形表示（图6），图中灰色的盒子表示放黑球，白色的盒子放置白球。
黑白球按照图6所示的放置方法，所形成的四条直线为：
{4,13,22}，{10,13,16}全由白球相连构成；
{6,15,24}，{12,15,18}全由黑球相连构成。
八、附录
1.程序
model:
Sets:
LineCols/1..3/:
;
LineRows/1..49/:
r;
Links（LineRows,LineCols）:
Lines;
Balls/1..27/:
delta;
endsets
min=@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=123
456
789
147
258
369
159
357
101112
131415
161718
101316
111417
121518
101418
121416
192021
222324
252627
192225
202326
212427
192327
212325
11019
21120
31221
11121
31119
41322
51423
61524
41424
61422
71625
81726
91827
71727
91725
11325
71319
21426
81420
31527
91521
11427
31425
71421
91419;
enddata
end
2.输出结果
Globaloptimalsolutionfoundatiteration:
103652
Objectivevalue:
4.000000
VariableValueReducedCost
R
（1）0.0000001.000000
R
（2）0.0000001.000000
R（3）0.0000001.000000
R（4）0.0000001.000000
R（5）0.0000001.000000
R（6）0.0000001.000000
R（7）0.0000001.000000
R（8）0.0000001.000000
R（9）0.0000001.000000
R（10）0.0000001.000000
R（11）0.0000001.000000
R（12）1.0000001.000000
R（13）0.0000001.000000
R（14）1.0000001.000000
R（15）0.0000001.000000
R（16）0.0000001.000000
R（17）0.0000001.000000
R（18）0.0000001.000000
R（19）0.0000001.000000
R（20）0.0000001.000000
R（21）0.0000001.000000
R（22）0.0000001.000000
R（23）0.0000001.000000
R（24）0.0000001.000000
R（25）0.0000001.000000
R（26）0.0000001.000000
R（27）0.0000001.000000
R（28）0.0000001.000000
R（29）0.0000001.000000
R（30）1.0000001.000000
R（31）0.0000001.000000
R（32）1.0000001.000000
R（33）0.0000001.000000
R（34）0.0000001.000000
R（35）0.0000001.000000
R（36）0.0000001.000000
R（37）0.0000001.000000
R（38）0.0000001.000000
R（39）0.0000001.000000
R（40）0.0000001.000000
R（41）0.0000001.000000
R（42）0.0000001.000000
R（43）0.0000001.000000
R（44）0.0000001.000000
R（45）0.0000001.000000
R（46）0.0000001.000000
R（47）0.0000001.000000
R（48）0.0000001.000000
R（49）0.0000001.000000
LINES（1,1）1.0000000.000000
LINES（1,2）2.0000000.000000
LINES（1,3）3.0000000.000000
LINES（2,1）4.0000000.000000
LINES（2,2）5.0000000.000000
LINES（2,3）6.0000000.000000
LINES（3,1）7.0000000.000000
LINES（3,2）8.0000000.000000
LINES（3,3）9.0000000.000000
LINES（4,1）1.0000000.000000
LINES（4,2）4.0000000.000000
LINES（4,3）7.0000000.000000
LINES（5,1）2.0000000.000000
LINES（5,2）5.0000000.000000
LINES（5,3）8.0000000.000000
LINES（6,1）3.0000000.000000
LINES（6,2）6.0000000.000000
LINES（6,3）9.0000000.000000
LINES（7,1）1.0000000.000000
LINES（7,2）5.0000000.000000
LINES（7,3）9.0000000.000000
LINES（8,1）3.0000000.000000
LINES（8,2）5.0000000.000000
LINES（8,3）7.0000000.000000
LINES（9,1）10.000000.000000
LINES（9,2）11.000000.000000
LINES（9,3）12.000000.000000
LINES（10,1）13.000000.000000
LINES（10,2）14.000000.000000
LINES（10,3）15.000000.000000
LINES（11,1）16.000000.000000
LINES（11,2）17.000000.000000
LINES（11,3）18.000000.000000
LINES（12,1）10.000000.000000
LINES（12,2）13.000000.000000
LINES（12,3）16.000000.000000
LINES（13,1）11.000000.000000
LINES（13,2）14.000000.000000
LINES（13,3）17.000000.000000
LINES（14,1）12.000000.000000
LINES（14,2）15.000000.000000
LINES（14,3）18.000000.000000
LINES（15,1）10.000000.000000
LINES（15,2）14.000000.000000
LINES（15,3）18.000000.000000
LINES（16,1）12.000000.000000
LINES（16,2）14.000000.000000
LINES（16,3）16.000000.000000
LINES（17,1）19.000000.000000
LINES（17,2）20.000000.000000
LINES（17,3）21.000000.000000
LINES（18,1）22.000000.000000
LINES（18,2）23.000000.000000
LINES（18,3）24.000000.000000
LINES（19,1）25.000000.000000
LINES（19,2）26.000000.000000
LINES（19,3）27.000000.000000
LINES（20,1）19.000000.000000
LINES（20,2）22.000000.000000
LINES（20,3）25.000000.000000
LINES（21,1）20.000000.000000
LINES（21,2）23.000000.000000
LINES（21,3）26.000000.000000
LINES（22,1）21.000000.000000
LINES（22,2）24.000000.000000
LINES（22,3）27.000000.000000
LINES（23,1）19.000000.000000
LINES（23,2）23.000000.000000
LINES（23,3）27.000000.000000
LINES（24,1）21.000000.000000
LINES（24,2）23.000000.000000
LINES（24,3）25.000000.000000
LINES（25,1）1.0000000.000000
LINES（25,2）10.000000.000000
LINES（25,3）19.000000.000000
LINES（26,1）2.0000000.000000
LINES（26,2）11.000000.000000
LINES（26,3）20.000000.000000
LINES（27,1）3.0000000.000000
LINES（27,2）12.000000.000000
LINES（27,3）21.000000.000000
LINES（28,1）1.0000000.000000
LINES（28,2）11.000000.000000
LINES（28,3）21.000000.000000
LINES（29,1）3.0000000.000000
LINES（29,2）11.000000.000000
LINES（29,3）19.000000.000000
LINES（30,1）4.0000000.000000
LINES（30,2）13.000000.000000
LINES（30,3）22.000000.000000
LINES（31,1）5.0000000.000000
LINES（31,2）14.000000.000000
LINES（31,3）23.000000.000000
LINES（32,1）6.0000000.000000
LINES（32,2）15.000000.000000
LINES（32,3）24.000000.000000
LINES（33,1）4.0000000.000000
LINES（33,2）14.000000.000000
LINES（33,3）24.000000.000000
LINES（34,1）6.0000000.000000
LINES（34,2）14.000000.000000
LINES（34,3）22.000000.000000
LINES（35,1）7.0000000.000000
LINES（35,2）16.000000.000000
LINES（35,3）25.000000.000000
LINES（36,1）8.0000000.000000
LINES（36,2）17.000000.000000
LINES（36,3）26.000000.000000
LINES（37,1）9.0000000.000000
LINES（37,2）18.000000.000000
LINES（37,3）27.000000.000000
LINES（38,1）7.0000000.000000
LINES（38,2）17.000000.000000
LINES（38,3）27.000000.000000
LINES（39,1）9.0000000.000000
LINES（39,2）17.000000.000000
LINES（39,3）25.000000.000000
LINES（40,1）1.0000000.000000
LINES（40,2）13.000000.000000
LINES（40,3）25.000000.000000
LINES（41,1）7.0000000.000000
LINES（41,2）13.000000.000000
LINES（41,3）19.000000.000000
LINES（42,1）2.0000000.000000
LINES（42,2）14.000000.000000
LINES（42,3）26.000000.000000
LINES（43,1）8.0000000.000000
LINES（43,2）14.000000.000000
LINES（43,3）20.000000.000000
LINES（44,1）3.0000000.000000
LINES（44,2）15.000000.000000
LINES（44,3）27.000000.000000
LINES（45,1）9.0000000.000000
LINES（45,2）15.000000.000000
LINES（45,3）21.000000.000000
LINES（46,1）1.0000000.000000
LINES（46,2）14.000000.000000
LINES（46,3）27.000000.000000
LINES（47,1）3.0000000.000000
LINES（47,2）14.000000.000000
LINES（47,3）25.000000.000000
LINES（48,1）7.0000000.000000
LINES（48,2）14.000000.000000
LINES（48,3）21.000000.000000
LINES（49,1）9.0000000.000000
LINES（49,2）14.000000.000000
LINES（49,3）19.000000.000000
DELTA
（1）1.0000000.000000
DELTA
（2）1.0000000.000000
DELTA（3）0.0000000.000000
DELTA（4）0.0000000.000000
DELTA（5）0.0000000.000000
DELTA（6）1.0000000.000000
DELTA（7）1.0000000.000000
DELTA（8）0.0000000.000000
DELTA（9）0.0000000.000000
DELTA（10）0.0000000.000000
DELTA（11）0.0000000.000000
DELTA（12）1.0000000.000000
DELTA（13）0.0000000.000000
DELTA（14）1
升级会员 