數(shù)學(xué)規(guī)劃課程設(shè)計-- 通訊設(shè)備分配問題

1、<p><b>　　數(shù)學(xué)規(guī)劃課程設(shè)計</b></p><p>　　題目 通訊設(shè)備分配問題 </p><p>　　姓名 </p><p>　　班級 </p><p>　　學(xué)號 <

2、;/p><p>　　1.課程設(shè)計評價參考標(biāo)準(zhǔn)及得分</p><p>　　論 文 成 績 </p><p>　　指導(dǎo)教師簽名 </p><p><b>　　通訊設(shè)備分配問題</b></p>&l

3、t;p>　　摘要：數(shù)學(xué)規(guī)劃是運籌學(xué)的一個重要組成部分，它是近幾十年里發(fā)展起來的一門新興科學(xué)。隨著電子計算機的普及與發(fā)展，它在自然科學(xué)，社會科學(xué)，工程技術(shù)和現(xiàn)代管理中得到了廣泛的應(yīng)用，日益受到人們的重視。而作為數(shù)學(xué)規(guī)劃中的一個重要分支的動態(tài)規(guī)劃，是一種解決復(fù)雜系統(tǒng)優(yōu)化問題的方法，是目前解決多階段決策過程問題的基本理論之一。由于動態(tài)規(guī)劃不是一種特定的算法，因而它不像線性規(guī)劃那樣有自己標(biāo)準(zhǔn)的數(shù)學(xué)表達式和統(tǒng)一的求解方法，而必須對具體問題進

4、行具體的分析處理。因此其更具有實用價值，解決了我們現(xiàn)實生活中許多實際問題。實踐證明，動態(tài)規(guī)劃在工程技術(shù)，經(jīng)濟管理，工業(yè)生產(chǎn)，軍事以及現(xiàn)代控制工程等領(lǐng)域都有廣泛的應(yīng)用，并獲得顯著效果。在本文中，我們主要介紹的運用動態(tài)規(guī)劃的思想，利用計算機軟件Excel,解決資源分配問題，就是一個現(xiàn)實生活中動態(tài)規(guī)劃的運用實例，同時，又充分利用計算機技術(shù)，使計算更為便捷有效，從而更方便的解決了實際問題。</p><p>　　關(guān)鍵詞：數(shù)

5、學(xué)規(guī)劃；動態(tài)規(guī)劃；多階段決策過程問題；計算機軟件Excel；資源分配問題</p><p><b>　　一．引言</b></p><p>　　正所謂資源分配，即是將數(shù)量一定的或若干種，諸如：材料，設(shè)備，人力，資金，時間等資源，合理地分給若干個使用者，而是目標(biāo)函數(shù)最大。在此處，由于分配的資源過多，且目標(biāo)函數(shù)是非線性函數(shù)，可將其看成一個多階段決策問題，利用動態(tài)規(guī)劃的方法求解

6、。在動態(tài)規(guī)劃方法求解時，通常以把資源分配給一個或幾個使用者的過程作為一個階段，把規(guī)劃問題中的變量取為決策變量，將累計的量或遞推過程變化的量選為狀態(tài)變量。</p><p><b>　　二．問題闡述</b></p><p>　　某郵局有4套通訊設(shè)備準(zhǔn)備分給甲乙丙三個地區(qū)，事先調(diào)查了各地原有生產(chǎn)活動情況，在此基礎(chǔ)上對各種分配方案的經(jīng)濟效益進行了估計，得下表1（附錄）的數(shù)據(jù)，

7、例如：甲區(qū)原有生產(chǎn)活動的收益為38萬元，當(dāng)新增加一套通訊設(shè)備時總收益為41萬元，其他類推。試求4套設(shè)備的分配方案，使3地區(qū)總利益最大。</p><p>　　三．模型的建立和求解</p><p><b>　　3.1 模型的建立</b></p><p>　　首先我們對設(shè)備的分配規(guī)定一個順序，即先考慮分配給甲區(qū)，其次乙區(qū)，最后丙區(qū)，但分配時必須保證郵

8、電局德宗受益最大。</p><p>　　將問題按分配過程分為3個階段，根據(jù)動態(tài)規(guī)劃逆序算法，可設(shè)：</p><p>　　階段數(shù)t=1,2,3(即甲，乙，丙3個地區(qū)的編號分別為1，2，3)；</p><p>　　狀態(tài)變量dk:表示分配給第k個地區(qū)至第3地區(qū)的設(shè)備套數(shù)（即第k階段初尚未分配的設(shè)備套數(shù)）；</p><p>　　決策變量Xk：表示分配

9、給第k個地區(qū)的設(shè)備套數(shù)；</p><p>　　狀態(tài)轉(zhuǎn)移方程：dk+1=dk-Xk；</p><p>　　Rt（Xk）：表示Xk臺設(shè)備分配到第k個地區(qū)所得的收益值，它由表1查得；</p><p>　　Ft(dk):表示將dk臺設(shè)備分配到第k個地區(qū)至第3地區(qū)所得的最大收益</p><p>　　值，因而可得出遞推方程：</p><

10、;p>　　Ft(dk)= max [Rt（Xk）+Ft+1（dk- Xk）] (k=1,2,3；t=1,2,3； Xk=0，</p><p><b>　　1，2，3，4)</b></p><p><b>　　F4(d4)=0</b></p><p><b>　　3.2 模型的求解</b><

11、;/p><p>　　運用動態(tài)規(guī)劃的思想，利用窮舉的方法以及計算機軟件Excel，進行模型求解。根據(jù)問題分析中的相關(guān)公式，此處，為方便，令Jt（dk, Xk）= Rt（Xk）+Ft+1（dk- Xk）。</p><p><b>　　求解步驟：</b></p><p>　?。?）根據(jù)表1 數(shù)據(jù)，將Rt（Xk）輸入A4：F7來構(gòu)建電子表格，如圖1（附錄中

12、）所示。例如：將R2（2）=50輸入到單元格D6中；</p><p>　　（2）在B11：F11中的各單元各內(nèi)輸入0，因為對所有的dk都有F4(dk)=0；</p><p>　　在第18~20行，設(shè)置計算指令求出Jt（dk, Xk），此處使用Excel中的</p><p>　　HLOOKUP命令來查找Rt（Xk）(在第5行至第7行)和Ft+1（dk- Xk）(在第1

13、1行至第14行)的值。例如，要計算J3（3, 1），需要將下列公式輸入單元格I18中：=HLOOKUP（I$17,$B$4：$F$7,$A18+1）+HLOOKUP(I$16-I$17,$B$10：$F$14,$A18+1)。(其中，該公式前半部分HLOOKUP（I$17,$B$4：$F$7,$A18+1）表示在B4：F7中查找第一項與I17匹配的列，再取出該列的第A18+1 行中的項，返回值為R3（1）=64，命令中H表示水平查找；后

14、一部分HLOOKUP(I$16-I$17,$B$10：$F$14,$A18+1)表示在B10：F14中查找第一項與I16-I17匹配的列，再取出該列第A18+1 行中的項，返回值為F4（3- 1）=0。)現(xiàn)在將公式復(fù)制到范圍B18：P20中；</p><p>　　在Q18：U20中計算Ft（dk）?，F(xiàn)將用于計算F3（0），F(xiàn)3（1），F(xiàn)3（dk），</p><p>　　F3（2），F(xiàn)3（3

15、），F(xiàn)3（4）的如下公式手工輸入到Q18：U18中：</p><p><b>　　Q18：=48</b></p><p>　　R18：=MAX（C18：D18）</p><p>　　S18：=MAX（E18：G18）</p><p>　　T18：=MAX（H18：K18）</p><p>　　U1

16、8：=MAX ( L18：P18)</p><p>　　現(xiàn)在把這些公式從Q18：U18復(fù)制到范圍Q18：U20；</p><p>　?。?）在B12中輸入=Q18,再把這個公式復(fù)制到范圍B12：F14中。</p><p><b>　　注意：</b></p><p>　?。?）在公式中某列或某行地之前加上美元符號$示這個地

17、址是絕對地址，否則為相對地址。絕對地址副職是不會改變，而相對地址在復(fù)制時會發(fā)生改變，在Excel公式中使用絕對地址和相對地，址是為了方便復(fù)制；</p><p>　?。?）該電子表格的第11～14行是根據(jù)第18～20行定義的，而第18～20行又是根據(jù)第11～14行定義的，這可以在電子表格中創(chuàng)建循環(huán)性或循環(huán)引用。要解析Excel中的循環(huán)引用，只需選擇Tools,Option,Calculations,并選中Inter

18、ation復(fù)選框，這將使Excel解析所有的循環(huán)引用，直至解析循環(huán)性，此外，也可通過幾次按下F9鍵來解析循環(huán)引用。</p><p>　　具體如圖2（附錄中）所示：</p><p>　　3.3結(jié)論及其分析：</p><p>　　要確定如何將4套通訊設(shè)備分配給3個地區(qū)，需要注意到F1（4）=164，因為由表中結(jié)果知J1（4, 3）= F1（4）=164，因此應(yīng)將3套設(shè)備

19、分配給地區(qū)1，階段收益R,1（3）=60，；再由F2（4-3）=164-60=104= J2（1, 0）,可得出應(yīng)將0套設(shè)備分配給地區(qū)2，階段收益R,2（0）=40；最后由F3（1-0）=104-60=64= J3（1, 1），可知將剩余的1套設(shè)備分配給項目3，階段收益R,3（1）=64。所得結(jié)果用表2（附錄中）顯示：</p><p><b>　　四．參考文獻：</b></p>

20、<p>　　【1】范玉妹，徐爾，趙金玲，胡毅慶，數(shù)學(xué)規(guī)劃及其應(yīng)用（第3版），冶金工業(yè)出版社</p><p><b>　　附 錄</b></p><p>　　表1 通訊設(shè)備在不同地區(qū)的收益 （萬元）</p><p><b>　　表2 結(jié)果顯示</b></p><p&