黑白球三维排列游戏Word格式文档下载.docx
《黑白球三维排列游戏Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《黑白球三维排列游戏Word格式文档下载.docx（21页珍藏版）》请在冰点文库上搜索。
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的三维阵中，所有能够共线的三点共有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）;
delta（Lines（i,j）））-r（i）<
=2）;
@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
升级会员 