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

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

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

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

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

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

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

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

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

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

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

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

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

13、n=1-(1-P) n2當 n=60(1箱)時, C(60)=0.9031,n=120(1箱)時, C(120)=0.99992.這樣定義的抱怨程度最大是1,當n2較小時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這樣定義的抱怨程度似乎顯得顧客過分挑剔,他們不容忍任何互開的現(xiàn)象. 2nC2nC2nC.252、對一般顧客、對一般顧客 另一種抱怨程度可以用每批鎖具中平均每把鎖互開對數(shù)來定義,設(shè)顧客購n把鎖b1,b2,bn.b1與bi可以互開的概率均為P,故與b1可互開的鎖的對數(shù)

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

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

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