PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 徵求神人幫解大地遊戲分組的超難排列組合

看板Prob_Solve (計算數學 Problem Solving)作者yr (Light be with you)時間9年前 (2015/06/19 22:40)推噓2(2推 0噓 6→)

留言8則, 4人參與討論串2/4 (看更多)

剛試了一下，似乎是無解。（註：改了最後一個條件解出來了） X[i][j][k][t] (BINARY): 0<=i,j<18 - team, 0<=k<10 - game, 0<=t<10 - time period Maximize 0 s.t. sum(X[i][i][k][t]) == 0, for all i 不配到自己 sum(X[i][j][k][t]) == 10, for all i 玩十場 sum(X[i][j][k][t]) == 1, for all (i,t) 每隊每時段一場 sum(X[i][j][k][t]) == 1, for all (i,k) 每遊戲每隊只玩一次 sum(X[i][j][k][t]) <= 1, for all (i,j) 兩隊只對到一次 sum(X[i][j][k][t]) <= 1, for all (k,t) 每遊戲在每個時段被玩最多一次 CPLEX 兩秒告訴我無解，不知道這些條件有沒有搞錯。 -- Some people are born on third base and go through life thinking they hit a triple. - Barry Switzer -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 42.60.214.239 ※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1434724814.A.CE7.html ※ 編輯: yr (42.60.214.239), 06/19/2015 22:51:13 ※ 編輯: yr (42.60.214.239), 06/19/2015 23:41:11

→

scwg

06/20 06:21, , 1^F

06/20 06:21, 1^F

※ 編輯: yr (155.69.185.196), 06/20/2015 10:54:32

→

06/20 10:54, , 2^F

06/20 10:54, 2^F

→

06/20 10:56, , 3^F

06/20 10:56, 3^F

大概五分鐘解出來，如下。 t0: 0(0,1) 1(7,14) 2(15,17) 3(11,12) 4() 5(2,5) 6(4,6) 7(3,10) 8(8,13) 9(9,16) t1: 0() 1(0,2) 2(8,9) 3(1,3) 4(13,14) 5(4,15) 6(16,17) 7(6,7) 8(10,12) 9(5,11) t2: 0(14,16) 1(5,17) 2(0,3) 3(2,9) 4(1,10) 5(7,13) 6(8,12) 7() 8(4,11) 9(6,15) t3: 0(7,17) 1(3,16) 2(2,12) 3(0,4) 4(6,9) 5(8,10) 6(5,13) 7(11,15) 8() 9(1,14) t4: 0(6,11) 1() 2(1,13) 3(7,15) 4(0,5) 5(12,14) 6(9,10) 7(4,16) 8(3,17) 9(2,8) t5: 0(3,9) 1(12,15) 2(11,16) 3(10,13) 4(8,17) 5(0,6) 6() 7(1,2) 8(5,14) 9(4,7) t6: 0(4,12) 1(10,11) 2() 3(8,14) 4() 5(1,16) 6(0,7) 7(5,9) 8(2,6) 9(13,17) t7: 0(2,10) 1(9,13) 2(4,5) 3(6,17) 4() 5(3,11) 6(14,15) 7(0,8) 8(1,7) 9() t8: 0() 1(6,8) 2(7,10) 3(5,16) 4(2,4) 5() 6(1,11) 7(14,17) 8(0,9) 9(3,12) t9: 0(5,8) 1(1,4) 2(6,14) 3() 4(7,11) 5(9,17) 6(2,3) 7(12,13) 8(15,16) 9(0,10) ※ 編輯: yr (155.69.185.196), 06/20/2015 11:07:48 ※ 編輯: yr (155.69.185.196), 06/20/2015 11:48:41

→

06/20 11:52, , 4^F

06/20 11:52, 4^F

改了一下，加一組 constraint 。 Maximize 0 s.t. sum(X[i][i][k][t]) == 0, for all i 不配到自己 X[i][j][k][t] - X[j][i][k][t] == 0, for all i<j sum(X[i][j][k][t]) == 10, for all i 玩十場 sum(X[i][j][k][t]) == 1, for all (i,t) 每隊每時段一場 sum(X[i][j][k][t]) == 1, for all (i,k) 每遊戲每隊只玩一次 sum(X[i][j][k][t]) <= 1, for all (i,j) 兩隊最多只對到一次 sum(X[i][j][k][t]) <= 1, for all (k,t) i<j 每遊戲在每個時段被玩最多一次 sum(X[i][j][k][t]) == 180 總共 180 場次（每個 match 算 2 場次）橫向是遊戲，縱向是時間 0 1 2 3 4 5 6 7 8 9 0,1 3,11 13,14 7,9 2,10 6,17 4,5 15,16 8,12 10,15 0,2 9,16 5,11 8,13 6,14 1,3 7,17 4,12 2,11 14,15 0,3 6,12 5,9 7,8 4,10 13,16 1,17 5,12 4,8 10,17 1,6 3,16 0,13 7,11 2,15 9,14 4,14 1,5 12,15 2,16 3,17 0,10 9,11 6,8 7,13 6,16 9,13 1,10 8,14 4,7 11,12 2,17 0,5 3,15 13,17 6,7 3,4 0,16 5,14 1,15 9,12 10,11 2,8 8,9 7,12 2,5 1,13 11,14 4,15 0,17 3,6 10,16 3,7 6,10 4,17 8,15 2,9 12,16 5,13 1,14 0,11 16,17 8,11 0,15 12,13 1,7 3,10 2,14 4,9 5,6 ※ 編輯: yr (155.69.185.196), 06/20/2015 13:02:52