1994年B題鎖具裝箱（課堂PPT）

1、.11994年年B題題 鎖具裝箱問(wèn)題鎖具裝箱問(wèn)題 制作小組：董敏敏制作小組：董敏敏 鄭珊鄭珊 張壽張壽.2小知識(shí)點(diǎn)補(bǔ)充：小知識(shí)點(diǎn)補(bǔ)充：.3鎖的歷史中華古鎖起源于5000年前的仰韶文化時(shí)期，體現(xiàn)出了各歷史時(shí)期豐富的社會(huì)文化內(nèi)涵，展示中華古鎖工藝的精湛。.4鎖的歷史佩飾與紋樣 從古至今，人們都喜歡以麒麟的工藝造像作為護(hù)身符佩戴在身上，其質(zhì)地有金、銀、銅、玉等，尤其講究為嬰幼兒佩戴“麒麟鎖”，以此為孩子祈禱長(zhǎng)命百歲。 .5鎖的歷史文字組合鎖，即“密碼鎖”。清朝出現(xiàn)的文字密碼鎖，是編對(duì)字句才能開(kāi)啟的藏品對(duì)字（句）鎖。利用分別刻有漢字的幾個(gè)轉(zhuǎn)環(huán)套定鎖身，只有旋動(dòng)轉(zhuǎn)環(huán)拼成一句暗定的字句，才能開(kāi)啟。 .6國(guó)

2、家標(biāo)準(zhǔn)：GB-9303-88（輕工業(yè)）門鎖， 1988年頒布互開(kāi)率： 優(yōu)等品和一等品：0.204%; 合格品： 0.286%?；ラ_(kāi)率檢驗(yàn)： 抽取50把，分5組檢驗(yàn)， 9分鐘換一次，共45分鐘；互開(kāi)率： R為互開(kāi)出現(xiàn)次數(shù)，T為抽樣數(shù)。現(xiàn)代.7.8.9問(wèn)題：某廠生產(chǎn)一種彈子鎖具,每個(gè)鎖具的鑰匙有5個(gè)槽,每個(gè)槽的高度從1,2,3,4,5,66個(gè)數(shù)(單 位略)中任取一數(shù).由于工藝及其它原因,制造鎖具時(shí)對(duì)5個(gè)槽的高度還有兩個(gè)限制:至少有3 個(gè)不同的數(shù);相鄰兩槽的高度之差不能為5.滿足以上條件制造出來(lái)的所有互不相同的鎖具稱 為一批. 從顧客的利益出發(fā),自然希望在每批鎖具中“一把鑰匙開(kāi)一把鎖”.但是在當(dāng)前工

3、藝條件下, 對(duì)于同一批中兩個(gè)鎖具是否能夠互開(kāi),有以下試驗(yàn)結(jié)果:若二者相對(duì)應(yīng)的5個(gè)槽的高度中有4個(gè) 相同,另一個(gè)槽的高度差為1,則能互開(kāi);在其它情形下,不可能互開(kāi).10原來(lái),銷售部門在一批鎖具中隨意地取每60個(gè)裝一箱出售.團(tuán)體顧客往往購(gòu)買幾箱到幾十箱, 他們抱怨購(gòu)得的鎖具會(huì)出現(xiàn)互開(kāi)的情形.現(xiàn)聘你為顧問(wèn),回答并解決以下的問(wèn)題:1）、每一批鎖具有多少個(gè),裝多少箱.2）、為銷售部門提出一種方案,包括如何裝箱(仍是60個(gè)鎖具一箱),如何給箱子以標(biāo)志,出售 時(shí)如何利用這些標(biāo)志,使團(tuán)體顧客不再或減少抱怨.3）、采取你提出的方案,團(tuán)體顧客的購(gòu)買量不超過(guò)多少箱,就可以保證一定不會(huì)出現(xiàn)互開(kāi)的情 形.4）、按照原來(lái)

4、的裝箱辦法,如何定量地衡量團(tuán)體顧客抱怨互開(kāi)的程度(試對(duì)購(gòu)買一、二箱者給 出具體結(jié)果).11某廠生產(chǎn)一種彈子鎖具,每個(gè)鎖具的鑰匙有5個(gè)槽,令hi(i=1,2,3,4,5)為鑰匙第i個(gè)槽的高度，則一批鎖具應(yīng)滿足如下三個(gè)條件。而同時(shí)滿足下面兩個(gè)條件的兩個(gè)鎖具可以互開(kāi)，并把這兩個(gè)而同時(shí)滿足下面兩個(gè)條件的兩個(gè)鎖具可以互開(kāi)，并把這兩個(gè)鎖具稱為一個(gè)互開(kāi)對(duì)：鎖具稱為一個(gè)互開(kāi)對(duì)：*1.兩個(gè)鎖的鑰匙有四個(gè)槽高度相同；兩個(gè)鎖的鑰匙有四個(gè)槽高度相同；*1.其余一個(gè)槽高度相差其余一個(gè)槽高度相差1.條件3 對(duì)任意一種槽高排列h1h2h3h4h5有|hi-hi-1|5（i=2,3,4,5）. 條件1 對(duì)任意一種槽高排列h1

5、h2h3h4h5有hi1,2,3,4,5,6（i=1,2,3,4,5）.條件2 對(duì)任意一種槽高排列h1h2h3h4h5，至少有三個(gè)槽高互不相同。 .12 鎖廠銷售部門原先在一批鎖具中隨機(jī)地取60個(gè)裝為一箱出售，這樣一來(lái)，成箱購(gòu)買鎖具的顧客總抱怨購(gòu)得的鎖具有互開(kāi)現(xiàn)象。我們所關(guān)心的問(wèn)題是：每一批鎖具共有多少個(gè)，如何衡量隨機(jī)裝箱造成的團(tuán)體顧客的抱怨程度以及采取何種方案裝箱來(lái)盡量避免團(tuán)體顧客的抱怨。由一批鎖具中，互開(kāi)對(duì)總數(shù)是確定的，但在隨機(jī)裝箱之后，對(duì)于每一箱而言，鎖具互開(kāi)現(xiàn)象就不可避免地帶有了隨機(jī)性，因而可以用統(tǒng)計(jì)平均值定量地衡量隨機(jī)裝箱造成的團(tuán)體顧客抱怨程度。為了能夠提出一種方案來(lái)裝箱和標(biāo)志，以盡

6、量避免團(tuán)體顧客的抱怨，就需要找出能夠互開(kāi)的鎖具之間的特性，從而使能夠互開(kāi)的鎖具分開(kāi)裝箱和標(biāo)記。 .13 1.鎖具廠在生產(chǎn)鎖具過(guò)程中能夠準(zhǔn)確地知道鑰匙的每個(gè)槽的高度。 2.對(duì)于同一批兩個(gè)鎖具，若二者相對(duì)應(yīng)的5個(gè)槽的高度中有4個(gè)相同，且另一個(gè)槽的 高度差為1，則一定能互開(kāi)。 .141.確定一批鎖具的總數(shù)確定一批鎖具的總數(shù)我們根據(jù)生產(chǎn)一批鎖具的三個(gè)條件，用排列組合的知識(shí)對(duì)一批鎖具的總數(shù)目進(jìn)行求解，其主要過(guò)程如下： （1）根據(jù)條件1，鑰匙槽高度的可能排列有65=7776種（2）受條件2和條件3的約束，實(shí)際制鎖時(shí)還要除去一部分鑰匙槽高度的排列方式，我們稱這些排列方式形成的集合為除去集D. （3）條件3可

7、等價(jià)為鑰匙槽高度排列方式中不能出現(xiàn)1和6相鄰的情況.15（4）對(duì)除去集D可進(jìn)行如下劃分： 令D1=h1=h2=h3=h4=h5的排列； D2=hi（i=1,2,3,4,5）中只有兩個(gè)不同數(shù)的排列； D3=hi（i=1,2,3,4,5）中有三個(gè)不同數(shù)且1和6相鄰的排列； D4=hi（i=1,2,3,4,5）中有四個(gè)不同數(shù)且1和6相鄰的排列； D5=hi（i=1,2,3,4,5）各不相同且1和6相鄰的排列；.16 顯然，Di（ i=1,2,3,4,5）是 D的一個(gè)完全劃 分，即D1D2D3D4D5=D且DiDj= （i=1,2,3,4,5且ij）我們分別求出了 Di(i=1,2,3,4,5)中的元

8、素個(gè)數(shù)（詳細(xì)計(jì)算見(jiàn)附錄1） 如下：|D1|=6；|D2|=450；|D3|=456；|D4|=792； |D5|=192（|D|表示集合D中元素的個(gè)數(shù)） .17綜上，一批鎖具的總數(shù)為綜上，一批鎖具的總數(shù)為7776-（6+456+792+192）=5880件 可裝的箱數(shù)為可裝的箱數(shù)為5880/60=98箱.18 2.裝箱方案裝箱方案 （理論分析法理論分析法 ）（1）對(duì)鎖具進(jìn)行分類）對(duì)鎖具進(jìn)行分類當(dāng)兩個(gè)鎖相對(duì)應(yīng)的5個(gè)槽的高度中有4個(gè)相同,另一個(gè)槽的高度差為1時(shí),它們可以互開(kāi).我們發(fā)現(xiàn)了下面的規(guī)律. 定理定理1 在一批鎖具中,設(shè)能夠互開(kāi)的兩鎖具的槽高排列h1h2h3h4h5和h1 h2 h3 h4

9、h5,其各槽高度之和H= 和H= 必然具有不同的奇偶性. 51iih51iih.19（定理1闡述）因?yàn)榛ラ_(kāi)的兩個(gè)鎖具有四個(gè)槽高度相同,僅有一個(gè)槽高度差1,那么高度之和H= 和H= 必為兩個(gè)相鄰的自然數(shù),而兩個(gè)相鄰的自然數(shù)中,必有一個(gè)為奇數(shù),另一個(gè)為偶數(shù).根據(jù)定理1,我們把鎖具按鑰匙槽高度這和H的奇偶分為兩類,H為奇數(shù)的屬于奇類,H為偶數(shù)的屬于偶類.這樣,能夠互開(kāi)的鎖具一定分屬于奇類和偶類. 51ihi51iih.20（2）求解奇類和偶類中鎖具的個(gè)數(shù)）求解奇類和偶類中鎖具的個(gè)數(shù)對(duì)一個(gè)鎖具的鑰匙槽高度的排列h1h2h3h4h5,我們用7分別減去每個(gè)高度hi(i=1,2,3,4,5),形成另一個(gè)與其

10、對(duì)偶的排列:(7-h1)(7-h2)(7-h3)(7-h4)(7-h5)記原排列的高度和H0= ,新排列的高度和H1= 。則有H0+H1=3551ii)h7(51iih為使上式成立,H0,H1中必有一個(gè)偶數(shù)和一個(gè)奇數(shù).而每一個(gè)奇(偶)類中的排列必能從偶數(shù)(奇)類中找出與其對(duì)應(yīng)的對(duì)偶排列,這種對(duì)偶關(guān)系是一一對(duì)應(yīng)的,所以:奇類中鎖具數(shù)=偶類中鎖具數(shù)= 294025880故奇類和偶類中的鎖具數(shù)都為故奇類和偶類中的鎖具數(shù)都為2940件件 .21（3）裝箱的標(biāo)記）裝箱的標(biāo)記生產(chǎn)鎖具過(guò)程中記錄每個(gè)鑰匙槽的高度,從而確定H的奇偶性,將生產(chǎn)出來(lái)的鎖具分奇類和偶類. 將奇類和偶類分別裝為49箱并做”奇”和”偶”

11、的標(biāo)志.這樣,銷售部門可以根據(jù)所做標(biāo)記只選同類的箱子售給團(tuán)體顧客.只要他們一次購(gòu)買的箱數(shù)不超過(guò)49箱(即2940個(gè)鎖具),我們就可以保證他們的鎖具不會(huì)有互開(kāi)現(xiàn)象,他們也就不會(huì)抱怨了. 但按槽高之和的奇偶分類是不是最優(yōu)方案,即能否找到更好的分類裝箱方案,使不可互開(kāi)的鎖具個(gè)數(shù)大于2940.所給方案最優(yōu)性的證明可以通過(guò)圖論知識(shí)和計(jì)算機(jī)實(shí)現(xiàn).22 （4）顧客抱怨程度的衡量）顧客抱怨程度的衡量 抱怨與顧客所購(gòu)鎖具有互開(kāi)個(gè)數(shù)的大小有關(guān),不考慮質(zhì)量問(wèn)題該問(wèn)題中計(jì)算互開(kāi)對(duì)的個(gè)數(shù)的概率非常困難. 1、對(duì)特挑剔的顧客、對(duì)特挑剔的顧客一批鎖具中,能與一把鎖互開(kāi)的鎖可以由4到10.如 35554號(hào)鎖 25554,36

12、554,35654,35564可與其互開(kāi);如 24534號(hào)鎖14534,34534,25534,23534,24434,24634,24544,24524,24533,24535號(hào)鎖可以與之互開(kāi).23為了便于分析,我們可以求出與任一把鎖可互開(kāi)的鎖具數(shù)目的平均值.經(jīng)過(guò)上機(jī)計(jì)算,平均數(shù)為 故我們可以認(rèn)為任意從一批鎖中拿出兩套來(lái),它們可以互開(kāi)的概率是 3101378. 158807476. 7P任意取出n把鎖時(shí),這n把鎖中沒(méi)有互開(kāi)鎖具的概率是(1-P) n2故互開(kāi)現(xiàn)象發(fā)生的概率Pn=1-(1-P) n22nC2nC.24互開(kāi)的情況(概率)愈大顧客的抱怨程度越大,故定義顧客的抱怨程度如下C(n)= P

13、n=1-(1-P) n2當(dāng) n=60(1箱)時(shí), C(60)=0.9031,n=120(1箱)時(shí), C(120)=0.99992.這樣定義的抱怨程度最大是1,當(dāng)n2較小時(shí)C(n)= 1-(1-P) PC(2) P, C(6) 15PC(3) 3P, C(7) 21PC(4) 6P, C(8) 28PC(5) 10P, C(9) 36P這樣定義的抱怨程度似乎顯得顧客過(guò)分挑剔,他們不容忍任何互開(kāi)的現(xiàn)象. 2nC2nC2nC.252、對(duì)一般顧客、對(duì)一般顧客 另一種抱怨程度可以用每批鎖具中平均每把鎖互開(kāi)對(duì)數(shù)來(lái)定義,設(shè)顧客購(gòu)n把鎖b1,b2,bn.b1與bi可以互開(kāi)的概率均為P,故與b1可互開(kāi)的鎖的對(duì)數(shù)

14、為(n-1)P,下面考慮b2,b2與b3,bn可互開(kāi)的概率也為P,故除b1外，與b2可互開(kāi)的鎖的對(duì)數(shù)為（n-2）p,故n把鎖可互開(kāi)的鎖的對(duì)數(shù)之“平均值”為(n-1)P+(n-2)P+2P+P=所以定義抱怨度為d(n)=當(dāng)n=60， d(60)=3059P=59P7.6710-2當(dāng)n=120 d(120)=60119P=119P0.156當(dāng)然也可以采取其它的方法，定義顧客的抱怨程度。 .26在一批鎖具中，互開(kāi)對(duì)總數(shù)為m=22778對(duì)，則平均每個(gè)鎖具與其它鎖具能組成的互開(kāi)對(duì)數(shù)為 )(75. 72940mE對(duì)對(duì)于任一個(gè)指定鎖具S，從其它5879把鑰匙中任取一把，能打開(kāi)該鎖的概率是均等的。這樣，如果從

15、另外5879全鎖具中隨意取出59個(gè)鎖具與S裝成一箱，則在這一箱中能與S組成互開(kāi)對(duì)的鎖具個(gè)數(shù)平均有 )(078. 0587959EE1個(gè)3、對(duì)于隨機(jī)裝箱的方案、對(duì)于隨機(jī)裝箱的方案 平均含有的互開(kāi)對(duì)數(shù)為)(33.22E60)1m(E1對(duì).27E58792)1k60(k602Ek60k)1k60(k98587922778同理可以得知，k箱鎖具中，能與某一個(gè)鎖具互開(kāi)的鎖具個(gè)數(shù)平均為 平均含有的互開(kāi)對(duì)數(shù)為E(mk)=58791k60EEk.28 顯然，Ek和E（mk）的大小反映了購(gòu)買k箱的顧客的抱怨程度，即Ek 或E（mk）越大，顧客抱怨程度越大，表1給出了幾個(gè)具體結(jié)果。 表1 k=1,k=2和k=49

16、的具體結(jié)果 箱數(shù)k1249含有的互開(kāi)對(duì)數(shù)E（mk）2.339.415693.5能與某一鎖具S互開(kāi)的鎖具數(shù)Ek0.0780.1573.87.294、對(duì)于奇偶分類裝箱的方案、對(duì)于奇偶分類裝箱的方案 由前面的分析知，給 箱子進(jìn)行奇?zhèn)乳撕笤俪鍪?，只要顧客?gòu)買量k不超過(guò)49箱，就可以保證不出現(xiàn)互開(kāi)的情況，顧客自然不會(huì)抱怨，當(dāng)購(gòu)買量k超過(guò)49箱時(shí)，可以先從奇（偶）類鎖具有取出49箱，再?gòu)钠妫ㄅ迹╂i具中任取k-49箱出售給顧客，互開(kāi)對(duì)顯然只產(chǎn)生在49箱奇（偶）類鎖具與k-49箱偶（奇）類鎖具之間。 此時(shí)，k箱鎖具中的平均互開(kāi)對(duì)數(shù)為 )(4949k227782940)49k(6022778)m(Ek對(duì).30對(duì)比隨意裝箱的互開(kāi)對(duì)數(shù)為)1k60(k98587922778)m(Ek可知：當(dāng)k49時(shí)，E(mk)=0,而E(mk)0，此時(shí)顧客的抱怨被避免；當(dāng)49k98時(shí)，E(mk)49時(shí),取奇(偶)類49箱后剩下的k-49箱在偶(奇)類中按序號(hào)從小到大取箱.使得在k箱中互開(kāi)總數(shù)盡量減少,這樣必然更能減小顧客的所怨程度.33 1本模型利用數(shù)的奇妙的奇偶性為制鎖廠提供了一項(xiàng)很好的鎖具裝箱方案。此方案在最大范圍內(nèi)消除了鎖具的互開(kāi)