離散最優(yōu)化模型

算法設計算法分析模型設計計算機模擬離散問題是圖論、網絡流、整數規(guī)劃、組合數學等許多學科討論和研究的對象，這類問題在生產調度、交通控制、物流、管理科學和社會科學等有著廣泛的用途。在我們歷年的數模的競賽中，離散問題是很重要的一個方面。如“鎖具裝箱”，“天車作業(yè)調度”，“災情巡視路線”等等，本身就是個典型的離散問題；也有的問題里包含著離散的子問題，如“車輛安排問題”，是個受到整數的約束的優(yōu)化問題。近幾年的“乘公交，看奧運”，“體能測試時間安排”，“地面搜索”,“NBA賽程的分析與評價”,“眼科病床的合理安排”,“會議籌備”等等都屬于離散型問題。因此，在準備數模競賽的過程中，有必要認真的研究如何提高建立離散模型的質量。下面就離散優(yōu)化問題，討論如何設計算法的考慮；如何進行算法分析；如何作計算機模擬諸方面。一算法設計離散問題的難點往往在于它的算法設計,許多離散問題的計算量是非常大的，甚至是指數型的。誠然，我們已經有了大量的經典的算法，在解決離散問題時，我們經常使用分支定界法，割平面法，動態(tài)規(guī)劃法等一些有效的辦法，有時我們也會運用一些隨機搜索的辦法，如模擬退火法，遺傳算法等。應該知道，這些通用的方法，都會有它的局限性，有的時候表現并不好。作為建模比賽，我們必須通過研究具體問題中的特殊關系，提出適合特殊一類問題的好的算法，在這里，我們要兼顧計算精度和計算量兩個方面。背包問題

一旅行者隨身攜帶一個背包，準備在眾多的物品中挑選一些最必需的用品裝入背包。如果知道各件物品的重量和價值，他該如何選擇。顯然，他想攜帶的物品價值最大而又不能超過背包的容許承重。設第

j

類的物品單重為wj

，價值為vj，挑選

xj

件；背包的承重為b.這個問題的數學描述為：背包問題就是只有一個約束條件的整數線性規(guī)劃問題搜索樹（搜索空間）許多離散問題的求解，需要搜索滿足一定約束條件的所以可能的情況，尋找出合適的目標。通常，我們用n維向量來表示某一種情況，稱它為狀態(tài)或結點。滿足條件的狀態(tài)按它們互相之間的關系組成一個搜索空間。如果所有的狀態(tài)向量之間存在某種偏序關系，則可組成一棵搜索樹，樹的根結點表示狀態(tài)向量0，葉結點是問題的可行解。第k層的結點向量是，它的子結點是所謂搜索，就是把狀態(tài)空間中的各種狀態(tài)按某種策略排成一個序列，逐個地檢測。通常采用深度優(yōu)先的搜索次序，從樹根搜索起，尋找滿足特定要求的目標狀態(tài)，這也稱作回溯法。為了尋到目標狀態(tài)把整棵樹的各種可能結點都窮盡搜索，工作量是十分巨大的，即使對高速的計算機也是不現實的。如果對搜索樹的每個結點賦予一個成本C，對不可行的結點賦予高成本，那么，相當于在樹中搜索一個最小成本的向量。這些成本結構滿足：搜索樹中父結點的成本總是小于或等于子結點的成本，

在運用回溯法中，一旦發(fā)現一個結點的成本高于至今找到的解的最小成本，就砍掉這個結點以下的分支。如果有更好的解，就要修正這個界限。這就是分支定界的基本思想。例1假定我們有四種物件要裝包，限重10，各樣東西價值為 v={1,3,5,9},單重為w={2,3,4,7}。分支定界法我們用分支定界法求解背包問題，首先對變量重新排序，使，即背包問題的搜索樹是這樣定義的，第i層的結點到它的子結點的弧表示的第i種物品裝包的數量，一個子結點表示一種選擇。此問題的樹中，第一層有兩個分支，，第二、三、四層分別有三、四、五個分支，。重量和值標在相應的結點上。如果a）它的重量超過限重，或b）它的值不大于當前最好的可行值，那么，停止從這個結點向下搜索，砍去這條分支；回溯到后繼一個結點。結點的重量是，而它的值為(a)(b)否則當當(a)(b)否則(a)式中的值有兩部分組成，是所有已經搜索到的物件的值，而是尚剩下的容量。因變量是排了序的， 是未分配的變量中單位重量價值最大的值。因此，它所計算的結點值是它所有子結點值的上界。后一式計算的是葉結點，沒有其它物品可再放進背包里去了。(a)(b)否則當分支定界算法的關鍵是尋求比較精確的界限，使搜索樹盡量砍去更多的分支。這個算法的效率也取決于定界的好壞。分支定界法討論啟發(fā)式系數α

平均分叉系數r。對于層樹的總結點數有，于是。通過計算機多次模擬可以獲得N的平均值，從而估計出平均分叉系數。3.界的優(yōu)化。其中一個改進的方案是考慮后面兩類物品令 ，新的預測為用動態(tài)規(guī)劃法求解這個問題，是先考慮它的局部問題，即物品種類比較少的情況。引入一個函數動態(tài)規(guī)劃法是當總承重為y

時，只選擇前幾項物品裝包所能達到的最大價值。觀察這個函數，可以直接從定義得出遞推公式：這樣，選擇（決策）問題被順序恰當地劃分成若干個子問題（階段），階段變量k=1,…,n.每個階段的特征和演變的狀況用狀態(tài)變量y=1,2,…,b

描述。給定了每個階段的某個狀態(tài)，可以有多種不同的選擇方案，使它轉移到下一個階段的某個狀態(tài)，這種選擇或決定稱作決策。在多階段決策過程中任何一個可行的決策序列，稱為一個策略。上述遞推公式反映動態(tài)規(guī)劃的一個原則：一個最優(yōu)策略的任何子策略也是最優(yōu)的。用遞推公式自左而右地計算第一行，然后第二行，等等。

k╲Y1234567891010112233445201334667993013556810101140135569101012F(y)的值此表給出了Fk(y)的值，但未給出相應的xj

的值，還要另外再建n

行b

列的表，其中每一項x(k,y)是第k

個階段，狀態(tài)y

時應該選用到的物品類的最大序號。因此，若x(k,y)=j，意思是這個決策中僅選用了第1到j

類物品，即，而對任。在計算Fk(y)的過程中，可以同時記錄對應的值x(k,y)。xk(y)的邊界條件是x(1,y)=0當F1(y)=0，x(1,y)=1當F1(y)≠0。一般地，有F4(10)=12，i(4,10)=4，i(4,10-7)=i(4,3)=2，i(4,3-3)=i(4,0)=0，表示結果為x=(0,1,0,1)當一個深入研究的算法背包問題的困難在于“整數”約束。如果對背包問題進一步研究，我們會考慮這樣一個問題，若去掉xi

的整數約束，允許xi

為任何非負實數，影響如何呢？顯然，問題變得十分容易求解的了，我們按物品的單價重新編號，使ρ1≥ρ2≥…≥ρn。憑直觀，我們知道要盡量裝第一類物品，剩下多余的空間裝第二類物品，依次類推。這種直觀方法經常會得到很好的結果，但由于整數的約束，不能總是得到最優(yōu)解。假若最優(yōu)解中x1=0，那么最優(yōu)的總價值肯定不會超過ρ2b，然而只用第一類物品裝入背包，則價值有如果時，最優(yōu)解中必定x1≥1，或者有我們定義，表示目標函數的最優(yōu)值在有無整數約束條件下的差額。在b足夠大時，我們有函數θ(b)呈現周期性，周期為w1。顯然，當w1整除b時，θ(b)=0，而在b(modw1)≠0的情況下，就不得不另選其它物品，由于，我們選取xj

(j≠1)要使得由于整數約束而引起的損失最小，損失，重量限制減至b-wj。于是，可在所有關于j

的損失中取其最小的來決定j對于較小的b值，我們可以用這個遞歸公式計算θ(b)。其實在許多問題中，θ(b)的周期開始的位置比我們的估計要小得多。例如，v={18，14，8，4，0}，w={15，12，7，4，1}，當b=1000時，此背包問題的最優(yōu)解是什么？若背包限重超過，最優(yōu)解中肯定有x1≠0，而且x1為滿足b-x1w1≥540的整數，若b=1000，那么x1≥30。要得到背包問題精確的周期解，需要從b=0,1,…開始計算所有b值的θ(b)：b01234567891011121314θ01.22.41.6.82.01.20.41.60.82.01.20.41.60.8b151617181920212223242526272829θ1.2b303132333435363738394041424344θ2.01.2b454647484950515253545556575859θ2.01.2計算表明當b≥26時θ(b)=θ(b+15)，這比剛才估計的540小得多了。二算法分析對于離散問題，經常這些問題是NP的，我們也就常常會提出新的算法，有時還是近似算法，特別是啟發(fā)式算法。因為啟發(fā)式算法是憑經驗得出的，沒有嚴格的數學證明，所以我們必須仔細的考察算法的效率和精度。這里只討論離散優(yōu)化中啟發(fā)式算法的誤差。我們說誤差，指計算結果與最優(yōu)解的誤差。當然，誤差估計有最理想的，平均的和最壞的情況三種。平均誤差不容易分析，我們常常用下一節(jié)所說的計算機模擬得到。最好的情況就是沒有誤差，啟發(fā)式的解就是最優(yōu)解，這時，我們要估計啟發(fā)解就是最優(yōu)解的輸入數據的范圍。啟發(fā)式算法的最優(yōu)解的范圍估計還是以背包問題為例。我們假定表示第n個物品在單位重量下的價值最高。我們用函數Fk(y)表示對前k種物品裝入限重為y的背包中，用最優(yōu)算法算得的總價值。這里，注意在遞歸調用中，要檢查xk+1

的每個可能的值，才可能獲得最佳的結果。再用函數Gk(y)表示對前k種物品裝入限重為y的背包中，用貪婪算法算得的總價值。第二式的右端表示，盡可能多裝第k+1種物件，余下的部分再用貪婪解。貪婪算法Gk(y)的計算量只有O(k)，與y值無關。于是有可見對所有的y有。一般地，有。那么，什么時候不能對所有的y都成立呢?(證明略）裝箱問題裝箱問題是說給了一批已知大小的物件，目的是把全部物件裝進最少數目的稱為箱子的相同容器，使沒有哪個箱子所裝的物件的總和超過規(guī)定的體積W。

裝箱問題可能在多種不同的實際情況中出現，例如，試圖用盡量少的標準長度的線形材料（鋁合金條，塑料管等），按所需的尺寸截成一批配件；電視臺如何把時間長短不一的商業(yè)廣告安排到幾個時間相同的節(jié)目間隙中；等等。一般的裝箱問題非常難解，如果去檢查所有可能的裝法，從中選出最好的一種，這在問題的規(guī)模比較大時，幾乎是不可能的。通常我們是采用啟發(fā)式的辦法來解決這類問題的，雖然這種辦法并不一定能夠尋找出最優(yōu)的裝法，但往往能找到一些次最優(yōu)的結果。

在設計啟發(fā)式算法時，由于不是總能得到最優(yōu)解，需要考慮輸入數據在什么條件下這個算法能夠獲得最優(yōu)解；或者，這個算法在最壞的情況下離最優(yōu)解的誤差有多大。假設每一個箱子Bi

容量都為1，現有n個物件其中對。箱子Bi

的裝入量記為c(Bi)。用貪婪法求解裝箱問題可表示成裝入B1

直到裝入B2直到┇一般，ak

裝入Bi只要Bi

還有足夠空間，否則就裝到Bi+1。這時，并不考慮前面的箱子中是否還有合適的空余地方。這個啟發(fā)式算法稱順序適合裝入（NF）算法。設NF(L)為NF算法對于輸入為L的情況下，需要的箱子數，L*為最優(yōu)算法中需要的箱子數。那么啟發(fā)算法的最大偏差可定義為NF(L)和L*比值的上界。但這個比值與L*有關，實際度量時取它的漸近性能。即如何評價算法的精度呢？根據NF算法的定義，對任兩個相鄰的箱子，它們裝載量的和大于1，計算算法的精度若NF(L)=m，這m個箱子的總裝重有可見最優(yōu)裝箱至少需要，或寫成。

給定一個輸入特例，總共4N–1件物件。理想的裝箱結果應該是每兩個1/2大小的物件裝一箱，共N箱，其余2N-1個物件裝一箱，因此L*=N+1，或N=L*

-1。然而，NF算法需要2N=2(L*

-1)個箱子。由定義可知，r(NF)=2，則表明NF算法的漸近最大偏差是真正需要的2倍，這個誤差太大了。

原因是在抉擇過程中只考慮當前的物品，而不管后面會有什么情況出現，即所謂的“在線”算法緣故。另一方面，對物件的信息完全不知道。若能知道物件的大小范圍，算法的性能就會有所改善。這個啟發(fā)式算法的一個改進算法，叫首次適合裝入(FF)算法，它將物件ak

放入Bj，如果1-c(Bj)≥ak且1-c(Bi)<ak

對i<j。即自左向右掃描每一個非空的箱子，將ak

放入第一個可容納的箱子。有人給出FF(L)下界的一個輸入表的例子：L={6,6,6,6,6,6,6,10,10,10,10,10,10,10,16,16,16,34,34,34,34,34,34,34,34,34,3451,51,51,51,51,51,51,51,51,51}箱子容量W=101時，最優(yōu)裝法需要10只箱子，每個箱子安排{6,10,34,51}或{16,34,51}兩種情況；首次適合裝入需要17只箱子。如果在執(zhí)行首次適合裝入算法之前，先將輸入物件表按大小重新遞減排序，這叫首次適合裝入遞減（FFD）算法。這是一種離線的啟發(fā)式算法，效果比較好。三數模算法的選擇我們碰到一個新問題時，如何去構造它的算法呢？（1）肯定想發(fā)現一個新的有效的算法，對所有的輸入條件總能得到一個最優(yōu)解。如果我們懷疑這個問題是NP-完全的，那怎么辦呢？最好先去證明它是NP-完全的。對于指數的算法、或者冪高于n3的多項式算法，我們都是不夠滿意的。這時，我們試著考慮下面幾點：（2）如果一下找不到有效的算法，可以考慮先把問題限制在某些特殊情況或極端情況，在研究了特殊情況的結果后，再逐步推廣到一般的結果。我們習慣地把當前的問題歸結到一個已知的問題，但這樣在處理過程中可能會丟失某些結構。（3）如果碰到的問題輸入規(guī)模很大，又很復雜，設法把這些輸入分成幾個子集合，從而得到幾個可以分別求解的子問題，在分別地解決各個子問題后，還可以找到適當的方法把它們合并成原問題的解。這是分而治之的策略。（4）我們也可以考慮用一些通用的方法來求解這個問題，如分支定界法、動態(tài)規(guī)劃或割平面法等。（5）啟發(fā)式算法。最優(yōu)算法有時是有效的，也有些卻十分麻煩，計算量非常大，以至于實際上是不可行的。實際求解問題要考慮經濟效果，最優(yōu)難以達到，次最優(yōu)已經足夠好的了。這就考慮采用啟發(fā)式算法，直觀上看很好，或者有時候還能夠得到最優(yōu)解。通常，我們考察若干個實際情況，先在一些小的數值樣本上做試驗，形成我們的直覺，并從中構造出一個啟發(fā)式算法。這個算法在有些情況下取得成功，得到最優(yōu)解，而在另一些情況下卻行不通了。我們應該研究輸入數據的特征，考慮在什么樣的輸入數據范圍內才能保證這個啟發(fā)式算法能夠正常地工作，得到最優(yōu)解；若不能得到最優(yōu)解的情況，應該建立（相對）誤差的上界。如果這個算法的適用范圍又廣，誤差又能夠接受，四計算機模擬

我們可以通過分析的方法研究算法的精度和效率，但是這并不總是可行的。我們經常得借助于計算機來分析。例如，我們通過蒙特卡羅方法，檢查分支定界法的分叉系數，研究啟發(fā)式算法的平均效果，等等。

在一定的假設條件下，在計算機上運用數學運算模擬系統(tǒng)的運行，稱為計算機模擬。

蒙特卡洛（MonteCarlo）方法是一種應用隨機數來進行計算機模擬的方法．此方法對研究的系統(tǒng)進行隨機觀察抽樣，通過對樣本值的觀察統(tǒng)計，求得所研究系統(tǒng)的某些參數。計算機模擬的優(yōu)點：

計算機模擬可以反復進行，改變系統(tǒng)的結構和系數都比較容易。在實際問題中，面對一些帶隨機因素的復雜系統(tǒng)，用分析方法建模常常需要作許多簡化假設，與面臨的實際問題可能相差甚遠，以致解答根本無法應用。這時，計算機模擬幾乎成為唯一的選擇。例1在我方某前沿防守地域，敵人以一個炮排（含兩門火炮）為單位對我方進行干擾和破壞．為躲避我方打擊，敵方對其陣地進行了偽裝并經常變換射擊地點。經過長期觀察發(fā)現，我方指揮所對敵方目標的指示有50％是準確的，而我方火力單位，在指示正確時，有1/3的射擊效果能毀傷敵人一門火炮，有1/6的射擊效果能全部消滅敵人?，F在希望能用某種方式把我方將要對敵人實施的20次打擊結果顯現出來，確定有效射擊的比率及毀傷敵方火炮的平均值。分析：這是一個概率問題，可以通過理論計算得到相應的概率和期望值.但這樣只能給出作戰(zhàn)行動的最終靜態(tài)結果，而顯示不出作戰(zhàn)行動的動態(tài)過程.需要模擬以下兩件事1.問題分析[2]當指示正確時，我方火力單位的射擊結果情況模擬試驗有三種結果：毀傷一門火炮的可能性為1/3，毀傷兩門的可能性為1/6，沒能毀傷敵火炮的可能性為1/2。這時可用投擲骰子的方法來確定：如果出現的是１、２、３三個點：則認為沒能擊中敵人；如果出現的是４、５點：則認為毀傷敵人一門火炮；若出現的是６點：則認為毀傷敵人兩門火炮．[1]觀察所對目標的指示正確與否模擬試驗有兩種結果，每一種結果出現的概率都是1/2。可用投擲一枚硬幣的方式予以確定，當硬幣出現正面時為指示正確，反之為不正確。2.符號假設i：要模擬的打擊次數；k1：沒擊中敵人火炮的射擊總數；k2：擊中敵人一門火炮的射擊總數；k3：擊中敵人兩門火炮的射擊總數．E：有效射擊比率；E1：20次射擊平均每次毀傷敵人的火炮數．3.模擬框圖初始化:i=0,k1=0,k2=0,k3=0i=i+1骰子點數?k1=k1+1k2=k2+1k3=k3+1k1=k1+1i＜20?E=(k2+k3)/20E1=0*k1/20+1*k2/20+2*k3/20停止硬幣正面?YNNY1，2，34，564.模擬結果模擬結果：設：A0：射中敵方火炮的事件；

A1：射中敵方一門火炮的事件；

A2：射中敵方兩門火炮的事件．則由全概率公式：5.理論計算觀察所對目標指示不正確觀察所對目標指示正確6.結果比較理論計算和模擬結果的比較分類項目無效射擊有效射擊平均值模擬0.650.350.5理論0.750.250.33

雖然模擬結果與理論計算不完全一致，但它卻能更加真實地表達實際戰(zhàn)斗動態(tài)過程．用蒙特卡洛方法進行計算機模擬的步驟：[1]設計一個邏輯框圖，即模擬模型．這個框圖要正確反映系統(tǒng)各部分運行時的邏輯關系。[2]模擬隨機現象．可通過具有各種概率分布的模擬隨機數來模擬隨機現象．產生模擬隨機數

在Matlab軟件中，可以直接產生滿足各種分布的隨機數，命令如下：

1．產生m×n階［a,b］均勻分布U(a,b)的隨機數矩陣：

unifrnd(a,b,m,n)產生一個［a,b］均勻分布的隨機數：unifrnd(a,b)

當只知道一個隨機變量取值在（a,b）內，但不知 道它在何處取值的概率大，在何處取值的概率小， 就只好用U(a,b)來模擬它。2．產生m×n階［0,1］均勻分布的隨機數矩陣：rand(m,n)產生一個［0,1］均勻分布的隨機數：randA題自動化車床管理一道工序用自動化車床連續(xù)加工某種零件，由于刀具損壞等原因該工序會出現故障，假定在生產任一零件時出現故障的機會均相同。工作人員通過檢查零件來確定工序是否出現故障?，F積累有100次刀具故障記錄，故障出現時該刀具完成的零件數如附表?，F計劃在刀具加工一定件數后定期更換新刀具。已知生產工序的費用參數如下：故障時產出的零件損失費用f=200元/件；進行檢查的費用t=10元/次；發(fā)現故障進行調節(jié)使恢復正常的平均費用d=3000元/次(包括刀具費)；未發(fā)現故障時更換一把新刀具的費用k=1000元/次。1)假定工序故障時產出的零件均為不合格品，正常時產出的零件均為合格品,試對該工序設計效益最好的檢查間隔（生產多少零件檢查一次）和刀具更換策略。2)如果該工序正常時產出的零件不全是合格品，有2%為不合格品；而工序故障時產出的零件有40%為合格品，60%為不合格品。工序正常而誤認有故障仃機產生的損失費用為1500元/次。對該工序設計效益最好的檢查間隔和刀具更換策略。3）在2)的情況,可否改進檢查方式獲得更高的效益。4593626245425095844337488155056124524349826407425657065936809266531644877346084281153593844527552513781474388824538862659775859755649697515628954771609402960885610292837473677358638699634555570844166061062484120447654564339280246687539790581621724531512577496468499544645764558378765666763217715310851

附:100次刀具故障記錄(完成的零件數)

當研究對象視為大量相互獨立的隨機變量之和，且其中每一種變量對總和的影響都很小時，可以認為該對象服從正態(tài)分布。

機械加工得到的零件尺寸的偏差、射擊命中點與目標的偏差、各種測量誤差、人的身高、體重等，都可近似看成服從正態(tài)分布。3.產生一個均值為，方差為的正態(tài)分布的隨機數：normrnd()4．產生m×n階期望值為的指數分布的隨機數矩陣： exprnd(,m,n)5．產生m×n

階參數為的帕松分布的隨機數矩陣： poissrnd(,m,n)設離散型隨機變量X

的所有可能取值為0,1,2,…,且取各個值的概率為連續(xù)系統(tǒng)模擬實例:追逐問題

狀態(tài)隨時間連續(xù)變化的系統(tǒng)稱為連續(xù)系統(tǒng)。對連續(xù)系統(tǒng)的計算機模擬只能是近似的，只要這種近似達到一定的精度，也就可以滿足要求。例追逐問題:如圖,正方形ABCD的四個頂點各有一人。在某一時刻，四人同時出發(fā)以勻速v=1米/秒按順時針方向追逐下一人，如果他們始終保持對準目標，則最終按螺旋狀曲線于中心點O。試求出這種情況下每個人的行進軌跡。OBCDA1.建立平面直角坐標系:A(x1,y1),B(x2,y2),C(x3,y3),D(x4,y4).2.

取時間間隔為Δt,計算每一點在各個時刻的坐標。設某點在t

時刻的坐標為:則在時刻的坐標為:其中4.對每一個點，連接它在各時刻的位置,即得所求運動軌跡.求解過程:3.取足夠小的時結束算法。v=1;dt=0.05;x=[001010];y=[010100];fori=1:4plot(x(i),y(i),'.'),holdonendd=20;while(d>0.1)x(5)=x(1);y(5)=y(1);

fori=1:4d=sqrt((x(i+1)-x(i))^2+(y(i+1)-y(i))^2);x(i)=x(i)+v*dt*(x(i+1)-x(i))/d;y(i)=y(i)+v*dt*(y(i+1)-y(i))/d;plot(x(i),y(i),'.'),holdon

endend計算程序:離散系統(tǒng)模擬實例:排隊問題

排隊論主要研究隨機服務系統(tǒng)的工作過程。

在排隊系統(tǒng)中，服務對象的到達時間和服務時間都是隨機的。排隊論通過對每個個別的隨機服務現象的統(tǒng)計研究，找出反映這些隨機現象平均特性的規(guī)律，從而為設計新的服務系統(tǒng)和改進現有服務系統(tǒng)的工作提供依據。

對于排隊服務系統(tǒng),顧客常常注意排隊的人是否太多,等候的時間是否長,而服務員則關心他空閑的時間是否太短.于是人們常用排隊的長度、等待的時間及服務利用率等指標來衡量系統(tǒng)的性能.[1]系統(tǒng)的假設：(1)顧客源是無窮的；(2)排隊的長度沒有限制；(3)到達系統(tǒng)的顧客按先后順序依次進入服務.單服務員的排隊模型：在某商店有一個售貨員，顧客陸續(xù)來到，售貨員逐個地接待顧客。當到來的顧客較多時，須排隊等待，被接待后的顧客便離開商店．設：1．顧客到來間隔時間服從參數為0.1的指數分布．２．對顧客的服務時間服從［4,15］上的均勻分布．３．排隊按先到先服務規(guī)則，隊長無限制．

假定一個工作日為8小時，時間以分鐘為單位。[1]模擬一個工作日內完成服務的個數及顧客平均等待時間t．[2]模擬100個工作日，求出平均每日完成服務的個數及每日顧客的平均等待時間。[2]符號說明

w：總等待時間；ci：第i個顧客的到達時刻；

bi：第i個顧客開始服務時刻；ei：第i個顧客服務結束時刻．

xi：第i-1個顧客與第i個顧客之間到達的間隔時間

yi：對第i個顧客的服務時間c1b1c3c4c5c2e1b2e2b3e3b4e4b5ci=ci-1+xiei=bi+yibi=max(ci,ei-1)t[3]模擬框圖初始化：令i=1，ei-1=0，w=0產生間隔時間隨機數xi~參數為0.1的指數分布ci=xi,bi=xi

產生服務時間隨機數yi~[4,15]的均勻分布ei=bi+yi累計等待時間：w=w+bi-ci準備下一次服務：i=i+1產生間隔時間隨機數xi~參數為0.1的指數分布ci=ci-1+xi

確定開始服務時間：bi=max(ci,ei-1)bi＞480?YNi=i-1,t=w/i輸出結果：完成服務個數：m=i

平均等待時間：t停止用蒙特卡洛法解非線性規(guī)劃問題基本假設試驗點的第j個分量xj服從[aj,bj]內的均勻分布．符號假設求解過程先產生一個隨機數作為初始試驗點,以后則將上一個試驗點的第j個分量隨機產生，其它分量不變而產生一新的試驗點．這樣，每產生一個新試驗點只需一個新的隨機數分量．當K>MAXK或P>MAXP時停止迭代．框圖初始化:給定MAXK,MAXP;k=0,p=0,Q:大整數xj=aj+R(bj-aj)j=1,2,…,nj=0j=j+1,p=p+1P>MAXP?YNxj=aj+R(bj-aj)gi(X)≥0?i=1,2…nYNj<n?f(X)≥Q?YNX*=X,Q=f(X)k=k+1k>MAXK?YN輸出X,Q,停止YN

在Matlab軟件包中編程，共需三個Ｍ－文件:randlp.m,

mylp.m,

lpconst.m.主程序為randlp.m.%mylp.mfunctionz=mylp(x)

%目標函數z=2*x(1)^2+x(2)^2-x(1)*x(2)-8*x(1)-3*x(2);

%轉化為求最小值問題%randlp.m

function[sol,r1,r2]=randlp(a,b,n