黑白球三維排列游戲

《黑白球三維排列游戲》由會員分享，可在線閱讀，更多相關《黑白球三維排列游戲（16頁珍藏版）》請在裝配圖網上搜索。

1、黑白球三維排列游戲 一、問題提出 （略）. 二、問題假設 1．將黑白球視作沒有大小的點，將每個小方盒也視作一個點。 三、符號說明 ： 0表示第i個盒子放白球，1表示第i個盒子放黑球； ：0表示第j條直線上所有的球為相同顏色，1表示第j條直線上的球為不同顏色,j=1，2，…，27. 四、問題分析與建模 這雖然是一個排列游戲，但是其中蘊含有相當豐富的整數(shù)規(guī)劃特性，因此在此討論它。將14個黑球和13個白球放入333的三維陣中，其排列方式非常多，要想采用窮舉法求解的原問題非常困難的。 首先，我們對小方盒編號為1到27，具體的編號規(guī)則為參見圖1。 于是，對于每個小方盒，我們可以引入

2、一個0--1變量： 表示第i個盒子中裝有白球，表示第i個盒子中裝有黑球，如此引入的0—1變量共有27個。并且由于黑球的個數(shù)為14，因此。 1. 可能的直線 對于此問題，首先需要知道：在這個333的三維陣中,哪些小方盒連接起來可以構成一條直線？這樣的直線共有多少條？ 為了確定這些直線，我們首先考慮此333的三維陣的行、列和縱三個方向上的9個截面上的直線有哪些，然后考慮不全在任何一個截面上直線有哪些。 與水平面平行的截面有三個，見圖2。對應于每一個截面上的三點共線的情況共有8種，分別記為： S3={{19，20，21},{22，23，24},{25,26,27},{19,22,25},

3、{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中的情況會出現(xiàn)重疊，去掉重疊的三種情況，新增加的三點共線情況

4、各有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中的情況會出現(xiàn)重疊，去掉重疊的6種情況，新增加的三點共線情況各有2種，分別記為： S7={{1,13,25},{7,13,19}}；S8={{2,14,26},

5、{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ù)前面分析的可能的直線的結果，我們來確定當放入黑白球之后，三個相同顏色的球在同一直線上滿足的條件。 設第j條直線上的三個盒子的編號分別為：j1，j2，j3，記為 ，在直線j上三個盒

6、子中放入的球的顏色情況為：。引入0--1變量：表示第j條直線上的三個球的顏色不完全相同，表示第j條直線上的三個球的顏色完全相同。這樣原問題轉化為求一種黑白球的方法，使得取得最小值。 并且有約束： （1） （2） 此即放入黑白球之后，每條直線上的所有球體顏色相同的條件為（1），每條直線上的所有球體顏色不相同的條件為（2）。此時如何將引入到（1）或者(2)中右邊的表達式中，成為我們考慮的重點。為了將引入表達式（1）中，變成 （3） 或者將引入表達式（2）中，變成 (4) 注1：此處（3）和（1）

7、并不等價，但是考慮到我們的目標為，這樣做也是可以的； 注2：此處（4）和（2）是等價的，但是與（3）相比增加了98個約束條件； 注3：在建立模型時，（3）和（4）這兩組約束條件只需要一組即可。 3. 數(shù)學模型 根據(jù)前面的分析，我們可以建立如下的0—1規(guī)劃的數(shù)學模型： 該模型是一個含有76個0—1變量，99個約束條件的0—1整數(shù)規(guī)劃問題。 五、模型求解 1.求解方法 理論上，對于0—1整數(shù)規(guī)劃問題可以采用基于線性規(guī)劃的分枝定界法求解。詳細算法參見[1]。 2.計算結果 利用數(shù)學軟件Lingo中已有的關于分枝定界法的實現(xiàn)，可以方便地求出原問題的解，程序及程序輸出見附錄1。

8、 根據(jù)我們計算出來的結果可知，相同顏色的最少的直線數(shù)為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):Li

9、nes; 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:

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

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

12、 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; enddata end 2. 輸出結果 Global optimal solution found at iteration: 103652 Objective value:

13、 4.000000 Variable Value Reduced Cost R( 1) 0.000000 1.000000 R( 2) 0.000000 1.000000 R( 3) 0.000000 1.000000

14、 R( 4) 0.000000 1.000000 R( 5) 0.000000 1.000000 R( 6) 0.000000 1.000000 R( 7) 0.000000 1.000000

15、 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.00000

16、0 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

17、 R( 17) 0.000000 1.000000 R( 18) 0.000000 1.000000 R( 19) 0.000000 1.000000 R( 20) 0.000000 1.000000

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

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

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

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

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

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

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

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

26、 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)

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

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

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

30、 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.

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

32、 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) 1

33、1.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.000

34、000 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 L

35、INES( 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.0

36、0000 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

37、 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 LINE

38、S( 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.0000

39、0 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

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

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

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

43、 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,

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

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

46、 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)

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

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

49、 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)

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

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

52、 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)

53、 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.

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

55、 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) 1

56、4.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.000

57、000 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 L

58、INES( 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

59、0000 0.000000 DELTA( 4) 0.000000 0.000000 DELTA( 5) 0.000000 0.000000 DELTA( 6) 1.000000 0.000000 DELTA( 7) 1.000000 0.000000

60、 DELTA( 8) 0.000000 0.000000 DELTA( 9) 0.000000 0.000000 DELTA( 10) 0.000000 0.000000 DELTA( 11) 0.000000 0.000000 D

61、ELTA( 12) 1.000000 0.000000 DELTA( 13) 0.000000 0.000000 DELTA( 14) 1.000000 0.000000 DELTA( 15) 1.000000 0.000000 DELTA( 16) 0.00000

62、0 0.000000 DELTA( 17) 1.000000 0.000000 DELTA( 18) 1.000000 0.000000 DELTA( 19) 1.000000 0.000000 DELTA( 20) 1.000000 0.000000

63、 DELTA( 21) 0.000000 0.000000 DELTA( 22) 0.000000 0.000000 DELTA( 23) 1.000000 0.000000 DELTA( 24) 1.000000 0.000000 DELT

64、A( 25) 1.000000 0.000000 DELTA( 26) 0.000000 0.000000 DELTA( 27) 0.000000 0.000000 Row Slack or Surplus Dual Price 1 4.000000

65、 -1.000000 2 0.000000 0.000000 3 1.000000 0.000000 4 0.000000 0.000000 5 0.000000 0.000000

66、 6 1.000000 0.000000 7 0.000000 0.000000 8 0.000000 0.000000 9 0.000000 0.000000 10 0.000000 0.000000 11 0.000000 0.000000 12 1.000000 0.000000