1、鎖具裝箱問題的數學模型,<第h卷第2期1995年6月鐵道學蘭州鐵道學院嘩?z/voi_14no.2jun.1995(蘭州鐵道學院土木系.蘭州730070)(蘭州道學院運輸系,蘭州73007o)何新宇(蘭州鐵道學院電詹系,蘭730070)摘要利用概率,組臺優化和圈論等知識.建立7七個模型.肼決7計算一枇鎖具的數量,估計團體顧客的抱怨程度等問題,并在考慮工廠連續生產,合理銷售的前提下,提出了較為優化的裝箱銷售方案及其改進方案.關鍵詞數學模型;裝箱:銷售;鎖具分類號o1224,o157.5,0211.67鎖廠生產的彈子鎖的鑰匙有5個槽,其槽高可以從l,2,6)六個數中任取一數,可見每個槽的高度

2、都有為1,2,6的可能.由于工藝及其它原因對制造鎖具有兩個限制條件:(1)至少有3個不同的槽高(2)相鄰兩槽高度之差不能為5,又指出由于當前工藝條件,一批鎖具中若有兩者相對應的5個槽中有4個槽高相同另一個相差為1,則兩者可能互開,在此條件下,要求建立縷型解決以下問題(1)一批鎂其的數量和裝箱數目.(2)提供一種銷售方案,包括裝箱,標記以及如何出售,使團體顧客不再或減少抱怨.(3)采取該方案,團體顧客的購買量不超過多少箱.就可以保證一定不會出現互開情形.(4)按原來的裝箱方法,定量地衡量團體顧客抱怨互開的程度(并對購買一,二箱者給出具體結果).1問題的分析鎖具的裝箱問題是一個很有實際價值的問題.

3、合理有效的裝箱方案,鎖售方案能提高工廠的信任度,擴大銷售額,增加利潤.為了達到此目的.本文首先應用排列組臺的有關知識,建立模型1(1)t并用basic編程求出結果,又用一種便于手葬的組合計算方法建立模型1(2).然后用fortran編程進行特征參數的求解,并刑foxbase進行數據分析,在綜合考慮生產實際與模型理論化的前提下,從大量方案比選中,擇選出裝箱,銷售較優,標記較合理的方案,并據此建立了模型i(1)和i(2)為解決問題(4),本文最后從圖論及古驄概率一:的角度收稿日期:19950314本文作者為全國大學生數學建模競賽一等羹獲得者(教練俞建寧副教授)蘭州鐵道學院第l4卷建立模型iv;采用

4、數學胡望的原始意義建立模型v?2模型假設及符號說明.2+1模型假設(1)兩把鎖具的5十槽中,如果有4個槽高度對應相同,另一個槽的高度差為i時,兩鎖必能互開(按最壞情況考慮).(2)隨機裝箱對鎖具來說是等可能概率.(3)工廠生產鎖具能按規格生產,團體顧客的抱怨程度只決定于買到互開鎖的對數.(4)生產線只有一條,即任兩把饋都不是同時生產,且該鎖具的鎖鐨配制為所有配制中的任意一個.(5)工廠生產鎖具時按批連續生產.2.2符合說明n一批鎖具中各槽可取高度千數(本題中n一6);m一把鑰匙的槽的個數(一5);6,一批鎖具中各鑰匙槽的可取高度值;x一批鎖具中鎖具的總數;一箱鎖具中鎖具總數(=60);y一批鎖

5、具所裝箱數;3模型設計3.1計算模型3.1.1求一批鎖具的數量x,據已知條件建立模型l(1)x:(c)4(,2)其中,a(mm)為限制條件下應除去的組合數.則一批鎖具可裝的輻數為y一對于這類問題,可用全枚舉浩求解,其運算通用框圖如圖1對于本題=5:6;限制條件為a(5,6)即為:(1)至少有3個不同的數.(2)相鄰兩槽的高度之差不能為5.利用計算機進行求解,礙如下結果=5880則y一一588098(箱)(程序略)3.1.2為了便于手算,我們利用組合汁算方法建立模型i(2).設at為滿足至少出現3個不同數的組臺.設a:為滿足相鄰兩槽高度差不等于5的所有第2期劉振等;鎖具裝箱閫題的數學模型?3組合

6、圖l通用框匿設b為槽高為1,6相鄰的組合.即第i與第i+1槽的高度分別1,6或6,1(14j表示滿足及a:的組合數.則nfana2laif一(cd一(一ci().一c)=7320(1)蘭州鐵道學院第l4卷11-j1ubt一耋曼ib?nbil_薈?nbin目1j一】jj4lj一lbnbnbnb.1lbl=c(c)l且nblc()(1i3)lb.nbl一2c?(c)(1i<,一13)lb.nbnb+ici-c(12)ibnbnbllbnbnbfi2clbnbnb3nb.1一clni=2ci則有1=1470ua11na一li(c)一1.n1i7746ll=(c).一lf=6306將以上結果代人

7、(1)式.得n=ana11al+a11a.uazl=58803.2裝箱銷售模型3.2.1設一批鎖具中第i把鑰匙從一端開始順次各槽的高度值組成一個向量記為b.b.一(,)并定義其模為】目li25從而有如下結論:結論i兩把鎖b和b,若llbj一1bll1b.與b必不能互開推論(1)要使團體顧客不再或減少抱怨,必須使llb.】一bll=1的兩互開鎖裝入編號相距盡可能大的箱中.推論(2)挺同為偶數的鎖具問不能互開;模同為奇數的鎖具問不能互開;模相等的鎖具問不能互開.由以上分析,我們可提出如下裝箱方案:即:摸為偶數的鎖具裝入前i箱,將模為奇數的鎖具裝入后箱,且分別從前至后按模從小到大的順序敝次裝箱,(j

8、;y).在考慮使團體頤客不再或減少抱怨的前提下兼顧銷售方便,我們擬采用連續數字作為箱的標志的方案,銷售時按箱子的編號連續銷售,并據此建立模型i(1).記模為ibi的所有鎖具數為(fb1)本文通過fortran對不同1日l對應的.(11)進行統計,結果如下:(8)一20,(9)一50,.(10)=120.(1】)-.162(12)=251,(13)一322,(14)一405,(15):508第2期劉振等:鐨裝箱問胚的數學模型口(16)一539,”(17)一563,口(18)一563,(19)=539a(20)=508,a(21)一405,a(22)=322.a(23)=25la(24)=162,

9、a(25)一l20.a(26)=50,(27)一20若b.與b能互開,記b所在箱與b所在箱在上述方案排序下的距編號差)為s并令m(s)一mlns.)l則m(s)表示從任意箱處連續拿取一定不會出現互開鎖的最大箱數.采用foxbase進行統計,可得s);50,49,48,47,46,45,44.43,d2.41.4o.39-38,3736j顯然m(s”)=35并進一步得到如下結論:(1)若購買箱數為35箱,可以從任一輻開始連續售出.保證一定不會出現互開鎖(2)若購買箱數為35<49,都可以找到相應的標號,并從該標號開始茬續拿取均能保證不會出現互開鎖.3.2.2模型l(1)只考慮了不同jb.1

10、之間的排序.沒有考慮相同l的鎖具之間的順序,田而裝箱較為方便.為了增加團體顧客的滿意程度,我們叉在模型i(1)的基礎上,對相同l.1的鎖具間進行字典排序,并將此字排序后所組成的有序向量集定義為向量集空問zk.zk=(20),120j,251),405,539.563j.208),322),l62j,50),50j,l62),322j,508),563),539),405r251),120,20j)其中,)表示含有”個有序向量的子向量集,顯然lzl一5880與zk對應的,由1b組成的有序向量記為t則丁=(8,l0,l2.14,16,l8,20,22,24.26,9.1l,t3,15,17,l9,

11、2l,23,25,27)將字典排序后的zk向量集空問中的5880個向量敝次從l,2,5880予以標碼.記四.中元素組成的,位數值為則朋一結論2m(s.)必然出現在ib(【-bli,:l的情形中.利用計算機對字典排序后的一批鎖具對應向量進行統計分析,結果為:最小距離對應向量標碼之差為2562.相應的互開鎖數為128把,即56對,上述結果表明:字典排序后,距離最近的兩互開鎖問有2562把鎖,即可裝=42.7箱,取整為42箱.uu于是m(s)一42箱.按模型11(1)的方式進行順次裝箱.連續編號后可得如下結論;(1)如果購買箱數42箱,可以從任一箱開始連續售出,保證不會出現互開鎖,(2)如果購買箱數

12、42<n49箱,則可以找到相應的標號,從該箱開始洼續售出,一定不會買到互開鎖.3.3抱怨程度評估模型3.3.1首先,筆者用概率和圈論的知識建立模型本模型用團體顧客購買箱錟具中包含的互開鎖的絕對數量來表示團體顧客的抱怨程蘭州鐵道學院弟l4卷度,由于采用隨機裝箱,所以互開鎖在y箱中是等可能分布的.本文中把所有鎖具都看作是一些離散點(g),能互開的鎖具問用邊e(g)相連,則模型為f()=.一jdeg(v)ile(g)l一墮j1一其中f()箱中互開鎖的對數e(g)j邊數deg(結點的度數.記最多可與把鎖互開的鎖數為p().本文用計算機對不同值對應的,j()進行統計,結果如下:p(4)9.,p(5

13、)210,p(6)592,p(7)=1398,p(8)=1802,p()一i488.p(10):300剛有deg(v)=45556【g)將x=5880,w=60,代入模型11.得f()3.95*10一(60一1)(如圖2)顯然n=i,f()=2.3303n=2,f()一9.401國2f()分斬圖圖3()分析圖.皇.:表達式,可以看出,隨著n增大,f()呈拋物線變化,當n增大到一定程度簍魯墨線幾乎豎直增長,這一點與實際不太相符,因此對模型i加以改進,采用購買鎖中互開鎂的相對數量來表示團體顧客的抱怨程度,建立模型.1f()一lie(g)1=(峨/n.deg(v)2第2期劉振等鎖具裝箱問題的數學模型

14、其中,f()表示葫中互開鎖的相對數.將模型l的相應數據代人.得f(n)一6.5910_.(60n-1)(如圖3)顯然n=1,f(n)一0.o389n一2,f(n)一0.0784由f()的表達式可知,隨著購買量增加團體顧客的抱怨程度呈線性增加,較為實際地反映了團體顧客的抱怨程度.3.3.3根據數學期望的原始意義建立模型v設團體顧客購買鎖數為把,記為(g)的所有元子集.引理矗ie(g()e(g)1?c筠假設顧客購買鎖時,所購鎖為從y(c)中隨機抽取,從而可假定這種選取為(g)上的等可能概型.由假設可得,對于團體顧客,購”把鎖時為上的一個等可能隨機試驗,記為,夸表示n把鎖中可互開鎖的對數.r1jp(

15、f=)=者v(1)jzl尸(=);p(f=)(2)-1cc)一k其中:g()表示g由的導出子圖.要求出式(2)的值是比較困難的,坦在實際上并不需要完全知道其分布函數,只要知道隨模型i(2)結果較優,但增加了裝箱的復雜性,二者各有優點,且均考慮了生產的連續和銷售的方便.42模型,采用不同方法對團體顧客的抱怨程度進行了定量評估,在模型中,當n一35箱時,f(35)=2904對;當n=42箱時.f(42)4183對.在采用優化裝箱方案后,模型i(1)保證35箱中無互開鎖,即f(35)=0,模型1(2)保證42箱中無互開鎮,即f(42)=0.可見采?b?蘭州鐵道學院第14卷用優化模型,對于工廠生產的改

16、善,銷售額的提高以及信任度的提高都有顯著的作用?4.3模型中利用互開鎖的相對含量表示團體顧客的抱怨程度,具有一定的現實性和可行性.5結語(1)由模型得到的裝箱銷售方案具有循環性,保證了生產銷售的連續性.(2)使用連續數字作為箱的標志,使銷售部門可據不同需要很方便地滿足顧客的需求.(3)模型靈活機動,適用性較廣,可推廣到種槽高,個槽數的情況,也可對每箱裝鎖數w進行改變.(4)模型的主要特點是求解過程大都運用計算機配臺進行,從而對計算手段要求較高.參考文獻1吳文瀧.圈論基礎及應用.北京:中國鐵道出版社.1984.131,105l27,1301382c.h.papadimitriou,k.steig

17、litz.組合晟優化算法和復雜性.北京t清華大學出版社,1988.22273周概窖.概率論與數理統計.北京:高等教育出版社.1984.14224粱之舜等.概率論及數理統計.北京:高等教育出版社,1988.1119themathematicalmoddsofloadinglocksintoboxeszhen(dept.ofcivilengineering,lanzhourailwayinstitutelartzhou730070)yangimengqing(dept.oftransportationmanagemem,lanzhourailwayinstitute,lanzhou730070)hexinyu(dept.ofteecommunication&autocomrol,lanzhourailwayinstltutt-.lanzhou730070)abstractinthispaper,sevenmathematicalmodelsarepresentedbycombiningprobabilitytheory,optimizedcombinationandgraphictheory.theproblemsofcalculati