鎖具裝箱問題

1、鎖具裝箱問題 學(xué)習(xí)目標(biāo) 1. 能表述鎖具裝箱問題的分析過程；2. 能表述模型的建立方法；3. 會利用排列組合來計算古典概型；4. 會利用 Matlab 求解鎖具裝箱問題。一、問題某廠生產(chǎn)一種彈子鎖具，每個鎖具的鑰匙有 5 個槽，每個槽的高度從 1 ，2，3，4，5， 66 個數(shù)（單位從略）中任取一數(shù)。由于工藝及其它原因，制造鎖具時對 5 個槽的高度有兩 個要求：一是至少有 3 個不同的數(shù)；二是相鄰兩槽的高度之差不能為5。滿足上述兩個條件制造出來的所有互不相同的鎖具稱為一批。 銷售部門在一批鎖具中隨意地抽取， 每 60 個裝一 箱出售。從顧客的利益出發(fā)，自然希望在每批鎖具中不能互開（“一把鑰匙開

2、一把鎖”）。但是， 在當(dāng)前工藝條件下，對于同一批中兩個鎖具是否能夠互開，有以下實驗結(jié)果：若二者相對應(yīng) 的 5 個槽的高度中有 4 個相同，另一個槽的高度差為1，則可能互開；在其它情況下，不可能互開。團(tuán)體顧客往往購買幾箱到幾十箱，他們會抱怨購得的鎖具中出現(xiàn)互開的情形?，F(xiàn)請回答 以下問題：1 每批鎖具有多少個，能裝多少箱？2按照原來的裝箱方案， 如何定量地衡量團(tuán)體顧客抱怨互開的程度 （試對購買一、 二箱 者給出具體結(jié)果）。二、問題分析與建立模型因為彈子鎖具的鑰匙有 5個槽，每個槽的高度從 1，2，3，4，5，6這 6個數(shù)中任取一 數(shù)，且 5 個槽的高度必須滿足兩個條件：至少有 3個不同的數(shù)；相鄰兩

3、槽的高度之差不能為 5。所以我們在求一批鎖具的總數(shù)時，應(yīng)把問題化為三種情況，即5 個槽的高度由 5 個不同數(shù)字組成、由 4 個不同數(shù)字組成、由 3 個不同數(shù)字組成，分別算出各種情況的鎖具個數(shù)，然后 相加便得到一批鎖具的總個數(shù)。在分別求這三種情況鎖具個數(shù)的時候，先求出滿足第 1 個條 件的鎖具個數(shù)再減去不滿足第 2 個條件的鎖具個數(shù)。在求這三種情況鎖具個數(shù)的時候，主要 依靠排列組合的不盡相異元素的全排列公式。下面用一個 5 元數(shù)組來表示一個鎖具：Key= （h1，h2，h3，h4， h5）其中 hi 表示第 i 個槽的高度， i =1，2，3，4，5。此 5 元數(shù)組表示一把鎖，應(yīng)滿足下述條 件：

4、條件 1: hi 1 , 2, 3, 4, 5, 6 , i = 1 , 2, 3, 4, 5。條件2:對于任意一種槽高排列hi, h2, ha, h4, h5,至少有3種不同的槽高。條件3:對于任意一種槽高排列hi,h2,ha,h4,h5,有|hi, hi-i|工5,i = 2 ,3,4, 5。而兩個鎖可以互開的條件為：兩個鎖的鑰匙有四個槽高相同，其中一個槽高相差為1。1一批鎖具個數(shù)的計算記一批鎖具的集合為：K=(hi,h2,h3,h4,h5)|hi 1 , 2, 3, 4,5,6 , i = 1 ,2,3,4,5,且(hi,h2,h3, h4, h5)為一鎖具，其個數(shù)小于65，可采用逐個檢

5、驗條件1, 2, 3的方法，求一批中的 所有鎖具，當(dāng)然也可計算出其個數(shù)。2抱怨程度的刻劃 在這里我們簡單地用平均互開總對數(shù)來刻劃抱怨程度,所以,關(guān)鍵是計算出顧客購買一 箱或兩箱時的平均互開總對數(shù),這可以用計算機(jī)模擬去計算。我們引入下面的記號：5P=(hi,h2,h3,h4,h5)| (hi,h2,h3,h4,h5) K,且 h 為偶數(shù)i15Q= (hi, h2, h3, h4, h5)| (hi, h2, h3, h4, h5) K,且 h 為奇數(shù)i1則可得到P中的鎖具不能互開，Q中的鎖具不能互開，P中的鎖具與Q中的才能互開。在計算中，判斷互開時，我們將 P和Q中的鎖具分別標(biāo)號為0, i,這樣

6、就減少了判斷時 的計算，大大提高了計算速度。說明：直接用平均互開總對數(shù)來刻劃抱怨程度有一定的不合理性。因為這樣來刻劃，購 買的箱數(shù)越多，抱怨程度就越大，而實際上，購買的越多，自然互開的可能性就越大，這是 顧客意料之中的，不應(yīng)有太多的抱怨，顧客所不能容忍的是在購買少量的鎖具而出現(xiàn)互開現(xiàn) 象。因此應(yīng)把購買箱數(shù)作為一個因素考慮到抱怨函數(shù)中。理想的抱怨函數(shù)應(yīng)該是，開始隨購 買量的增加而增加，到一定量后下降，這才合理。在這里，我們的主要任務(wù)是模擬求解，而 簡單地用平均互開總對數(shù)來刻劃抱怨程度。三、計算過程計算流程如下：1. 對(hi, h2, h3, h4, h5)的所有排列逐個檢驗條件 2、條件3,判

7、斷其是否為鎖具，55將鎖具放在數(shù)組key中,若 hi為奇數(shù),標(biāo)號為i,若 hi為偶數(shù),標(biāo)號為0 ,并計數(shù)count。iii i2. 輸出一批鎖具的總個數(shù) count。3. 多次用隨機(jī)數(shù)來模擬銷售一箱的情況 計算平均互開總對數(shù)。4. 輸出一箱平均互開總對數(shù) average 。注意：以上流程略去了某些細(xì)節(jié) 具體的細(xì)節(jié)可參看下面的程序。對上流程稍加修改 可用于研究2 , 3 , 4箱等的平均互開總對數(shù)。程序?qū)?hi , h2 , h3 , h4 , h5)的所有排列逐個 檢驗條件2、條件3時要進(jìn)行兩次判斷,一次是判斷(hi , h2 , h3 , h4 , h5)是否有3個不同的 數(shù) 另一次是相鄰槽

8、高之差是否為 5。在前一次判斷時 采用了比較簡捷的方法 請仔細(xì)考 察。找(hi, h2, h3, h4, h5)的所有排列，實際上可用五重循環(huán)來實現(xiàn)。具體程序如下:mnx ， kebe， k， j ， n ，Modelh1 , h2, h3, h4, h5, flag , cnt, key, flal , su, te, keel, i , aid, *計算一批鎖具的個數(shù) *)key=TableTable0 , 5 , 5880 ；keel=Table0 , 5 ；flag=Table-1 , 5880 ；cnt=0 ；Forh1=1 , h1<=6, h1+,Forh2=1 , h2&

9、lt;=6, h2+,Forh3=1, h3<=6, h3+,Forh4=1, h4<=6, h4+,Forh5=1, h5<=6, h5+, te=Table0 , 6；teh1=1；teh2=1；Te=h3=1；teh4=1 ；teh5=1 ；su=1 , 6 ；Ifsu>=3, keel1=h1；keel2=h2；keel3=h3 ；Forflal=1；i=2 , i<=5, i+,IfAbskeeli-keeli-1>=5, flal=0 , ；Ifflal= =1, cnt+ ； keycnt=keel ；flagcnt=IfMod1, 5 , 2

10、= =0 , 0 , 1 ；Print數(shù)*), , ；“count= ”, cnt ；*計算顧客購買一箱時的平均互開總對cnt=0 ；aid=Table1, 5 ； kebe=Table0 , 5 ；Forn=1 , n<=1000,n+,*模擬 1000 次*)Mnx=TableRndomInteger , 1 , 5880 , 60 ；Fori=1 , i<=60 , i+ ,Fork=i+11 , k<=60, k+,Ifflagmnxi! =flagmnxk IfAbskeymnxi.aid-keymnxk.aid= =1Keel=keymnxI； kebe=keymnxk ；, flal+ , ；Forflal=0 ；j=1 , j<=5 , j+ , Ifkeelj!=kebejIfflal= =1 , cnt