所以Q=M=PPT-E。
即定理得證。
3.2 約束條件
結合問題中的條件,我們定義變量xijk表示第i個人在第j場次的會議中分在第k組,
則xijk=1在第j場會議中,xi∈Gk
0在第j場會議中,xiGk,
其中
i=1…37,表示37個家具公司董事;
i=1…9,表示9個家具公司的雇員董事;
i=10…37表示28個家具公司的外部董事;
j=1…7表示全天開了7場次的會議;
k=1…6表示上午的三個場次的會議中,每個場次的會議分為6個小組,k=1…4表示下午的四個場次的會議中,每個場次的會議分為4個小組。
對于每個場次的分組來說,都一定存在有分組矩陣Pj,即:Pj=x1j1…x1jk
x2j1…x2jk
………
x37j1…x37jk,其中k=6(上午)或者4(下午)。
再根據題目給定的要求,可以得到如下的約束條件:
(1)每一次分組中,每個與會董事唯一的分在一組,
即∑6k=1xijk=1j=1,2,3i=1,…,37
∑4k=1xijk=1j=4,5,6,7i=1,…,37
(2)每次分組時,每組中的家具公司雇員董事應當合比例,
有1≤∑9i=1xijk≤2k=1,…,6j=1,2,3
2≤∑9i=1xijk≤3k=1,…,4j=4,5,6,7
(3)每次分組時,各小組的人數盡量平均分配,
有6≤∑37i=1xijk≤7k=1,…,6j=1,2,3
9≤∑37i=1xijk≤10k=1,…,4j=4,5,6,7
(4)xijk=1在第j場會議中,xi∈Gk
0在第j場會議中,xiGk
3.3 目標函數
7次分組會議完成以后,董事成員1-37之間相互見面的次數可由如下的公式表示:Qsum=∑7j=1Qj=(qsumij)37×37,Qsum為總的相遇矩陣。
其中
qsumij=∑3l=1∑6k=1xilk·xjlk+∑7l=4∑4k=1xilk·xjlki,j=1,…,37 i≠j
0i=j
3.3.1 目標函數Ⅰ的給出
考慮到與會董事之間的充分交流,要盡量保證每個與會董事之間都有見面的機會,即在Qsum中除了主對角線上元素外,0元素個數應盡可能少,首先對Qsum進行處理,得到Q(1)sum=Qsum+E37×37=(qsum(1)ij)37×37。
令mij=1qsum(1)ij=0
0否則,得到M=(mij)37×37,則目標函數I為m(x)=∑37i=1∑37j=1mij最小。
3.3.2 目標函數Ⅱ的給出
考慮到任意兩個董事重復見面的次數應盡可能相同,通過(qsumij)k可以放大不同董事與其他的董事見面次數上的單個差異,k的取值越大,放大的程度就越大。在本模型中,我們取定k=2,即‖Qsum‖2F,因此得到目標函數Ⅱ為g(x)=‖Qsum‖2F=∑37i=1∑37j=1(qsumij)2。
在這里,我們認為g(x)達到最小時,任意兩個成員重復見面次數達到盡量平均這個目標就得以實現,而當m(x)達到最小時,充分見面這個目標也得以最好地滿足。
3.3.3 總目標函數的得到
考慮到兩個目標函數m(x)和g(x)存在著著不同的優先級和數量級,于是對兩目標函數采用加以不同權系數衡量,得到總目標函數表達式,為f(x)=λ1m(x)+λ2g(x),其中λ1+λ2=1,λ1,λ2為權系數,這里取λ1=0.6,λ2=0.4。
4 模型的建立
綜合所述,得到如下模型:
目標函數Minf(x)=0.6m(x)+0.4g(x)
約束條件∑6k=1xijk=1j=1,2,3i=1,…,37
∑4k=1xijk=1j=4,5,6,7i=1,…,37
1≤∑9i=1xijk≤2k=1,…6j=1,2,3
2≤∑9i=1xijk≤3k=1,…4j=4,5,6,7
6≤∑37i=1xijk≤7k=1,…6j=1,2,3
9≤∑37i=1xijk≤10k=1,…4j=4,5,6,7
xijk只能是0或者1,i=1,…,37,j=1,……,7,k=1,…,6。
5 模型的求解
5.1 尋找問題的可行解空間
對于模型中的每個決策變量只能0或者1,因此可以看作是多目標0-1整數規劃問題,其變量的個數多達37×6×3+37×4×4=1258個,使用窮舉法搜索顯然是不可行的。考慮到模型中決策變量特點,采用每一場次會議的分組矩陣作為變量,決策變量的個數將會降低到7個,該模型可看作是參會成員集合的組合優化問題。考慮到分組矩陣的每一行中只能有一個元素為1,其余的元素全部為0,對于第一場和第四場的分組矩陣來說有:
X1=1
1
1
1
1
1
………
1
1
1
1
1037×6,X4=1
1
1
1
……
1
1
[1]
即定理得證。
3.2 約束條件
結合問題中的條件,我們定義變量xijk表示第i個人在第j場次的會議中分在第k組,
則xijk=1在第j場會議中,xi∈Gk
0在第j場會議中,xiGk,
其中
i=1…37,表示37個家具公司董事;
i=1…9,表示9個家具公司的雇員董事;
i=10…37表示28個家具公司的外部董事;
j=1…7表示全天開了7場次的會議;
k=1…6表示上午的三個場次的會議中,每個場次的會議分為6個小組,k=1…4表示下午的四個場次的會議中,每個場次的會議分為4個小組。
對于每個場次的分組來說,都一定存在有分組矩陣Pj,即:Pj=x1j1…x1jk
x2j1…x2jk
………
x37j1…x37jk,其中k=6(上午)或者4(下午)。
再根據題目給定的要求,可以得到如下的約束條件:
(1)每一次分組中,每個與會董事唯一的分在一組,
即∑6k=1xijk=1j=1,2,3i=1,…,37
∑4k=1xijk=1j=4,5,6,7i=1,…,37
(2)每次分組時,每組中的家具公司雇員董事應當合比例,
有1≤∑9i=1xijk≤2k=1,…,6j=1,2,3
2≤∑9i=1xijk≤3k=1,…,4j=4,5,6,7
(3)每次分組時,各小組的人數盡量平均分配,
有6≤∑37i=1xijk≤7k=1,…,6j=1,2,3
9≤∑37i=1xijk≤10k=1,…,4j=4,5,6,7
(4)xijk=1在第j場會議中,xi∈Gk
0在第j場會議中,xiGk
3.3 目標函數
7次分組會議完成以后,董事成員1-37之間相互見面的次數可由如下的公式表示:Qsum=∑7j=1Qj=(qsumij)37×37,Qsum為總的相遇矩陣。
其中
qsumij=∑3l=1∑6k=1xilk·xjlk+∑7l=4∑4k=1xilk·xjlki,j=1,…,37 i≠j
0i=j
3.3.1 目標函數Ⅰ的給出
考慮到與會董事之間的充分交流,要盡量保證每個與會董事之間都有見面的機會,即在Qsum中除了主對角線上元素外,0元素個數應盡可能少,首先對Qsum進行處理,得到Q(1)sum=Qsum+E37×37=(qsum(1)ij)37×37。
令mij=1qsum(1)ij=0
0否則,得到M=(mij)37×37,則目標函數I為m(x)=∑37i=1∑37j=1mij最小。
3.3.2 目標函數Ⅱ的給出
考慮到任意兩個董事重復見面的次數應盡可能相同,通過(qsumij)k可以放大不同董事與其他的董事見面次數上的單個差異,k的取值越大,放大的程度就越大。在本模型中,我們取定k=2,即‖Qsum‖2F,因此得到目標函數Ⅱ為g(x)=‖Qsum‖2F=∑37i=1∑37j=1(qsumij)2。
在這里,我們認為g(x)達到最小時,任意兩個成員重復見面次數達到盡量平均這個目標就得以實現,而當m(x)達到最小時,充分見面這個目標也得以最好地滿足。
3.3.3 總目標函數的得到
考慮到兩個目標函數m(x)和g(x)存在著著不同的優先級和數量級,于是對兩目標函數采用加以不同權系數衡量,得到總目標函數表達式,為f(x)=λ1m(x)+λ2g(x),其中λ1+λ2=1,λ1,λ2為權系數,這里取λ1=0.6,λ2=0.4。
4 模型的建立
綜合所述,得到如下模型:
目標函數Minf(x)=0.6m(x)+0.4g(x)
約束條件∑6k=1xijk=1j=1,2,3i=1,…,37
∑4k=1xijk=1j=4,5,6,7i=1,…,37
1≤∑9i=1xijk≤2k=1,…6j=1,2,3
2≤∑9i=1xijk≤3k=1,…4j=4,5,6,7
6≤∑37i=1xijk≤7k=1,…6j=1,2,3
9≤∑37i=1xijk≤10k=1,…4j=4,5,6,7
xijk只能是0或者1,i=1,…,37,j=1,……,7,k=1,…,6。
5 模型的求解
5.1 尋找問題的可行解空間
對于模型中的每個決策變量只能0或者1,因此可以看作是多目標0-1整數規劃問題,其變量的個數多達37×6×3+37×4×4=1258個,使用窮舉法搜索顯然是不可行的。考慮到模型中決策變量特點,采用每一場次會議的分組矩陣作為變量,決策變量的個數將會降低到7個,該模型可看作是參會成員集合的組合優化問題。考慮到分組矩陣的每一行中只能有一個元素為1,其余的元素全部為0,對于第一場和第四場的分組矩陣來說有:
X1=1
1
1
1
1
1
………
1
1
1
1
1037×6,X4=1
1
1
1
……
1
1
本文為全文原貌 未安裝PDF瀏覽器用戶請先下載安裝 原版全文