黑白球三維排列游戲

1、黑白球三維排列游戲一、問(wèn)題提出（略）.二、問(wèn)題假設(shè)1將黑白球視作沒(méi)有大小的點(diǎn)，將每個(gè)小方盒也視作一個(gè)點(diǎn)。三、符號(hào)說(shuō)明： 0表示第i個(gè)盒子放白球，1表示第i個(gè)盒子放黑球；：0表示第j條直線上所有的球?yàn)橄嗤伾?表示第j條直線上的球?yàn)椴煌伾?j=1，2，27.四、問(wèn)題分析與建模這雖然是一個(gè)排列游戲，但是其中蘊(yùn)含有相當(dāng)豐富的整數(shù)規(guī)劃特性，因此在此討論它。將14個(gè)黑球和13個(gè)白球放入333的三維陣中，其排列方式非常多，要想采用窮舉法求解的原問(wèn)題非常困難的。首先，我們對(duì)小方盒編號(hào)為1到27，具體的編號(hào)規(guī)則為參見(jiàn)圖1。于是，對(duì)于每個(gè)小方盒，我們可以引入一個(gè)0-1變量：表示第i個(gè)盒子中裝有白球，表示第i

2、個(gè)盒子中裝有黑球，如此引入的01變量共有27個(gè)。并且由于黑球的個(gè)數(shù)為14，因此。1. 可能的直線對(duì)于此問(wèn)題，首先需要知道：在這個(gè)333的三維陣中,哪些小方盒連接起來(lái)可以構(gòu)成一條直線？這樣的直線共有多少條？為了確定這些直線，我們首先考慮此333的三維陣的行、列和縱三個(gè)方向上的9個(gè)截面上的直線有哪些，然后考慮不全在任何一個(gè)截面上直線有哪些。與水平面平行的截面有三個(gè)，見(jiàn)圖2。對(duì)應(yīng)于每一個(gè)截面上的三點(diǎn)共線的情況共有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,

3、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個(gè)，見(jiàn)圖3和圖4。與圖3對(duì)應(yīng)的每一個(gè)截面上共線的三點(diǎn)情況也有8種，由于它們與圖1中的情況會(huì)出現(xiàn)重疊，去掉重疊的三種情況，新增加的三點(diǎn)共線情況各有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

4、,25，8,17,26，9,18,27，7,17,27，9,17,25。與圖4對(duì)應(yīng)的每一個(gè)截面上共線的三點(diǎn)情況也有8種，由于它們與圖1和圖2中的情況會(huì)出現(xiàn)重疊，去掉重疊的6種情況，新增加的三點(diǎn)共線情況各有2種，分別記為：s7=1,13,25,7,13,19；s8=2,14,26,8,14,20；s9=3,15,27,9,15,21。三個(gè)點(diǎn)不同在上面所介紹的任何一個(gè)或者兩個(gè)截面的情況參見(jiàn)圖5。新增加的三點(diǎn)共線的情況有4種，記為：s10=1,14,27,3,14,25,9,14,19,7,14,21。綜合前面的分析，在此333的三維陣中，所有能夠共線的三點(diǎn)共有49種情況，它們組成49條不同的直線，

5、用s表示，則.2. 成為直線的條件根據(jù)前面分析的可能的直線的結(jié)果，我們來(lái)確定當(dāng)放入黑白球之后，三個(gè)相同顏色的球在同一直線上滿足的條件。設(shè)第j條直線上的三個(gè)盒子的編號(hào)分別為：j1，j2，j3，記為 ，在直線j上三個(gè)盒子中放入的球的顏色情況為：。引入0-1變量：表示第j條直線上的三個(gè)球的顏色不完全相同，表示第j條直線上的三個(gè)球的顏色完全相同。這樣原問(wèn)題轉(zhuǎn)化為求一種黑白球的方法，使得取得最小值。并且有約束： （1） （2）此即放入黑白球之后，每條直線上的所有球體顏色相同的條件為（1），每條直線上的所有球體顏色不相同的條件為（2）。此時(shí)如何將引入到（1）或者(2)中右邊的表達(dá)式中，成為我們考慮的重點(diǎn)。

6、為了將引入表達(dá)式（1）中，變成 （3）或者將引入表達(dá)式（2）中，變成 (4) 注1：此處（3）和（1）并不等價(jià)，但是考慮到我們的目標(biāo)為，這樣做也是可以的；注2：此處（4）和（2）是等價(jià)的，但是與（3）相比增加了98個(gè)約束條件；注3：在建立模型時(shí)，（3）和（4）這兩組約束條件只需要一組即可。3. 數(shù)學(xué)模型根據(jù)前面的分析，我們可以建立如下的01規(guī)劃的數(shù)學(xué)模型：該模型是一個(gè)含有76個(gè)01變量，99個(gè)約束條件的01整數(shù)規(guī)劃問(wèn)題。五、模型求解1.求解方法理論上，對(duì)于01整數(shù)規(guī)劃問(wèn)題可以采用基于線性規(guī)劃的分枝定界法求解。詳細(xì)算法參見(jiàn)1。2.計(jì)算結(jié)果利用數(shù)學(xué)軟件lingo中已有的關(guān)于分枝定界法的實(shí)現(xiàn)，可以方

7、便地求出原問(wèn)題的解，程序及程序輸出見(jiàn)附錄1。根據(jù)我們計(jì)算出來(lái)的結(jié)果可知，相同顏色的最少的直線數(shù)為4條，并且有許多的備擇解，下面給出其中一種解的圖形表示（圖6），圖中灰色的盒子表示放黑球，白色的盒子放置白球。黑白球按照?qǐng)D6所示的放置方法，所形成的四條直線為：4,13,22，10,13,16全由白球相連構(gòu)成；6,15,24，12,15,18全由黑球相連構(gòu)成。六、模型推廣及討論（略）.七、參考文獻(xiàn)1 八、附錄1. 程序model:sets:linecols/1.3/:;linerows/1.49/: r;links(linerows,linecols):lines;balls/1.27/:delta

8、;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

9、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 2

10、7 3 14 25 7 14 21 9 14 19;enddataend2. 輸出結(jié)果 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

11、.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.0

12、00000 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.0

13、00000 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.0

14、00000 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

15、) 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 l

16、ines( 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

17、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(

18、 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.0

19、0000 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.00000

20、0 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,

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

22、 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 li

23、nes( 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)

24、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.0

25、00000 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(

26、 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.00

27、0000 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.00000

28、0 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,

29、 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