黑白球三維排列游戲
《黑白球三維排列游戲》由會員分享，可在線閱讀，更多相關(guān)《黑白球三維排列游戲（16頁珍藏版）》請在裝配圖網(wǎng)上搜索。
1、黑白球三維排列游戲 一、問題提出 （略）. 二、問題假設(shè) 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的三維陣中,哪些小方盒連接起來可以構(gòu)成一條直線？這樣的直線共有多少條？ 為了確定這些直線，我們首先考慮此333的三維陣的行、列和縱三個方向上的9個截面上的直線有哪些，然后考慮不全在任何一個截面上直線有哪些。 與水平面平行的截面有三個，見圖2。對應(yīng)于每一個截面上的三點共線的情況共有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對應(yīng)的每一個截面上共線的三點情況也有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對應(yīng)的每一個截面上共線的三點情況也有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ù)前面分析的可能的直線的結(jié)果，我們來確定當放入黑白球之后，三個相同顏色的球在同一直線上滿足的條件。 設(shè)第j條直線上的三個盒子的編號分別為：j1，j2，j3，記為 ，在直線j上三個盒
6、子中放入的球的顏色情況為：。引入0--1變量：表示第j條直線上的三個球的顏色不完全相同，表示第j條直線上的三個球的顏色完全相同。這樣原問題轉(zhuǎn)化為求一種黑白球的方法，使得取得最小值。 并且有約束： （1） （2） 此即放入黑白球之后，每條直線上的所有球體顏色相同的條件為（1），每條直線上的所有球體顏色不相同的條件為（2）。此時如何將引入到（1）或者(2)中右邊的表達式中，成為我們考慮的重點。為了將引入表達式（1）中，變成 （3） 或者將引入表達式（2）中，變成 (4) 注1：此處（3）和（1）
7、并不等價，但是考慮到我們的目標為，這樣做也是可以的； 注2：此處（4）和（2）是等價的，但是與（3）相比增加了98個約束條件； 注3：在建立模型時，（3）和（4）這兩組約束條件只需要一組即可。 3. 數(shù)學(xué)模型 根據(jù)前面的分析，我們可以建立如下的0—1規(guī)劃的數(shù)學(xué)模型： 該模型是一個含有76個0—1變量，99個約束條件的0—1整數(shù)規(guī)劃問題。 五、模型求解 1.求解方法 理論上，對于0—1整數(shù)規(guī)劃問題可以采用基于線性規(guī)劃的分枝定界法求解。詳細算法參見[1]。 2.計算結(jié)果 利用數(shù)學(xué)軟件Lingo中已有的關(guān)于分枝定界法的實現(xiàn)，可以方便地求出原問題的解，程序及程序輸出見附錄1。
8、 根據(jù)我們計算出來的結(jié)果可知，相同顏色的最少的直線數(shù)為4條，并且有許多的備擇解，下面給出其中一種解的圖形表示（圖6），圖中灰色的盒子表示放黑球，白色的盒子放置白球。 黑白球按照圖6所示的放置方法，所形成的四條直線為： {4,13,22}，{10,13,16}全由白球相連構(gòu)成； {6,15,24}，{12,15,18}全由黑球相連構(gòu)成。 六、模型推廣及討論 （略）. 七、參考文獻 [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. 輸出結(jié)果 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
- 溫馨提示:
1: 本站所有資源如無特殊說明，都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請下載最新的WinRAR軟件解壓。
2: 本站的文檔不包含任何第三方提供的附件圖紙等，如果需要附件，請聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
3.本站RAR壓縮包中若帶圖紙，網(wǎng)頁內(nèi)容里面會有圖紙預(yù)覽，若沒有圖紙預(yù)覽就沒有圖紙。
4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
5. 裝配圖網(wǎng)僅提供信息存儲空間，僅對用戶上傳內(nèi)容的表現(xiàn)方式做保護處理，對用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯，并不能對任何下載內(nèi)容負責(zé)。
6. 下載文件中如有侵權(quán)或不適當內(nèi)容，請與我們聯(lián)系，我們立即糾正。
7. 本站不保證下載資源的準確性、安全性和完整性, 同時也不承擔(dān)用戶因使用這些下載資源對自己和他人造成任何形式的傷害或損失。
最新文檔
- 六級上冊科學(xué)ppt課件-誰選擇了它們-教科版
- 護理核心制度培訓(xùn)一_圖文課件
- 部編《池子與河流》課件
- SWOT分析法(非常全面)課件
- 主題班會我的成長目標課件
- 城市交通擁堵及治理總結(jié)課件
- 輸血相關(guān)性急性肺損傷課件
- 議論文的謀篇布局與論點的提出ppt課件
- 六級上冊科學(xué)ppt課件-地球的近鄰——月球-冀人版
- 疾病預(yù)防、冬季保暖-課件
- 中考英語語法復(fù)習(xí)之狀語從句ppt課件集4
- 《百分數(shù)的意義和讀寫》參考ppt課件
- 主題班會堅持就是勝利課件
- 第二章--用人單位對大學(xué)生的要求概況ppt課件
- 教科版六年級科學(xué)上冊第三單元檢測卷(含答案)課件
