運(yùn)籌學(xué)課程設(shè)計(jì)3-水庫調(diào)水優(yōu)化設(shè)計(jì)

設(shè)計(jì)題目某城市自來水的水源地為A、B、C三個(gè)水庫，分別由地下管道把水送往該市所轄甲、乙、丙、丁四個(gè)區(qū)。唯一的例外是C水庫與丁區(qū)沒有地下管道。由于地理位置的差別，各水庫通往各區(qū)的輸水管道經(jīng)過的涵洞、橋梁、加壓站和凈水站等設(shè)備各不相同，因此該公司對(duì)各區(qū)的引水管理費(fèi)（元/千噸）各不相同（見下表）。但是對(duì)各區(qū)自來水的其他管理費(fèi)均為45元/千噸，而且對(duì)各區(qū)用戶都按統(tǒng)一標(biāo)準(zhǔn)計(jì)費(fèi)，單價(jià)為90元/千噸。目前水庫將臨枯水期，該公司決策機(jī)構(gòu)正考慮如何分配現(xiàn)有供水量的問題。首先，必須保證居民生活用水和某些重要機(jī)關(guān)、企業(yè)、事業(yè)單位用水的基本需求，各區(qū)的這部分用水量由下表的“最低需求”行表示，但是擁有一個(gè)獨(dú)立水源的丙區(qū)這部分水量可自給自足，無須公司供給。其次，除乙區(qū)外，其他三個(gè)區(qū)都已向公司申請(qǐng)額外再分給如下水量（千噸/天）：甲區(qū)：20；丙區(qū)：30；丁區(qū)要求越多越好，無上限。這部分水量包含于“最高需求”行中。該公司應(yīng)如何分配供水量，才能在保障各區(qū)最低需求的基礎(chǔ)上獲利最多？并按要求分別完成下列分析：（1）水庫B供應(yīng)甲區(qū)的引水管理費(fèi)（元/千噸）在何范圍內(nèi)變化時(shí)最優(yōu)分配方案不變？（2）水庫A的供水量在何范圍內(nèi)變化時(shí)最優(yōu)基不變？（3）乙區(qū)的日供水量為80千噸時(shí)的最優(yōu)分配方案。區(qū)水區(qū)水庫（千/噸）甲乙丙丁供水量（元/千噸）A1613221750B1413191560C192023—50最低需求（千噸/天）3070010最高需求（千噸/天）507030不限3.建模過程：3.1設(shè)定變量設(shè)Xij表示從第i個(gè)水庫輸水到第j個(gè)區(qū)的供水量,其中i=1、2、3（1、2、3分別代表A、B、C三個(gè)水庫）；j=1、2、3、4（1、2、3、4分別表示甲、乙、丙、丁四個(gè)區(qū)）設(shè)Z為總的飲水管理費(fèi);設(shè)Y表示公司的獲利。3.2根據(jù)題意推理A水庫到甲區(qū)的飲水管理費(fèi)為：16X11A水庫到乙區(qū)的飲水管理費(fèi)為：13X12A水庫到丙區(qū)的飲水管理費(fèi)為：22X13A水庫到丁區(qū)的飲水管理費(fèi)為：17X14B水庫到甲區(qū)的飲水管理費(fèi)為：14X21B水庫到乙區(qū)的飲水管理費(fèi)為：13X22B水庫到丙區(qū)的飲水管理費(fèi)為：19X23B水庫到丁區(qū)的飲水管理費(fèi)為：15X24C水庫到甲區(qū)的飲水管理費(fèi)為：19X31C水庫到乙區(qū)的飲水管理費(fèi)為：20X32C水庫到丙區(qū)的飲水管理費(fèi)為：23X33A水庫的供水量為：X11+X12+X13+X14≤50B水庫的供水量為：X21+X22+X23+X24≤60C水庫的供水量為：X31+X32+X33≤50甲區(qū)的最低需求為：X11+X21+X31≥30乙區(qū)的最低需求為：X12+X22+X32≥70丁區(qū)的最低需求為：X14+X24≥10甲區(qū)的最高需求為：X11+X21+X31≤50乙區(qū)的最高需求為：X12+X22+X32≤70丙區(qū)的最高需求為：X13+X23+X33≤30則得該問題的LP問題為：MinZ=16X11+13X12+22X13+17X14+14X21+13X22+19X23+15X24+19X31+20X32+23X33X11+X12+X13+X14≤50X21+X22+X23+X24≤60X31+X32+X33≤50X11+X21+X31≥30X12+X22+X32=70X14+X24≥10X11+X21+X31≤50X13+X23+X33≤30Xij≥0,i=1,2,3,4;j=1,2,3,43.3計(jì)算機(jī)求解前的手工數(shù)據(jù)準(zhǔn)備3.3.1數(shù)學(xué)模型數(shù)據(jù)準(zhǔn)備將原問題第一、二、三、四、六、七、八個(gè)約束條件添加松弛變量X1、X2、X3、X4、X5、X6、X7；將原問題第四、五、六個(gè)約束條件添加人工變量X8、X9、X10；將問題化為標(biāo)準(zhǔn)形式：MaxZ=-[16X11+13X12+22X13+17X14+14X21+13X22+19X23+15X24+19X31+20X32+23X33]X11+X12+X13+X14+X1=50X21+X22+X23+X24+X2=60B水庫的供水量X31+X32+X33+X3=50X11+X21+X31-X4+X8=30甲區(qū)的最低需求X12+X22+X32+X9=70乙區(qū)的最低需求X14+X24-X5+X10=10丁區(qū)的最低需求X11+X21+X31+X6=50甲區(qū)的最高需求X13+X23+X33+X7=30丙區(qū)的最高需求Xij≥0,Xr≥0,i=1,2,3,4;j=1,2,3,4;r=1,2,3,4,5,6,7,83.3.2Lindo6.1數(shù)據(jù)準(zhǔn)備在模型編譯框內(nèi)輸入原模型的程序規(guī)范模式如下：Min16X11+13X12+22X13+17X14+14X21+13X22+19X23+15X24+19X31+20X32+23X33SUBJECTTOX11+X12+X13+X14<=50X21+X22+X23+X24<=60X31+X32+X33<=50X11+X21+X31>=30X12+X22+X32=70X14+X24>=10X11+X21+X31<=50X13+X23+X33<=30END4．程序功能介紹4.1總體介紹此問題求解過程，分別運(yùn)用了C語言和LINDO數(shù)學(xué)建模軟件進(jìn)行分析。C語言是一種計(jì)算機(jī)程序設(shè)計(jì)語言。它既具有高級(jí)語言的特點(diǎn)，又具有匯編語言的特點(diǎn)。它可以作為工作系統(tǒng)設(shè)計(jì)語言，編寫系統(tǒng)應(yīng)用程序，也可以作為應(yīng)用程序設(shè)計(jì)語言，編寫不依賴計(jì)算機(jī)硬件的應(yīng)用程序。它的應(yīng)用范圍廣泛，具備很強(qiáng)的數(shù)據(jù)處理能力，不僅僅是在軟件開發(fā)上，而且各類科研都需要用到C語言。C語言有一個(gè)突出的優(yōu)點(diǎn)就是適合于多種操作系統(tǒng)；也適用于多種機(jī)型。C語言具有強(qiáng)大的繪圖能力，可移植性好，并具備很強(qiáng)的數(shù)據(jù)處理能力，因此適于編寫系統(tǒng)軟件，三維，二維圖形和動(dòng)畫，它也是數(shù)值計(jì)算的高級(jí)語言。該程序通過C語言編寫，表現(xiàn)了運(yùn)籌學(xué)中的如何求解線性規(guī)劃問題的最優(yōu)解的方法，該程序運(yùn)行過程中需要人工輸入需要求解的目標(biāo)函數(shù)類型，決策變量的個(gè)數(shù)、變量的系數(shù)、約束條件的個(gè)數(shù)、約束條件的符號(hào)以及變量系數(shù)、不等式右端項(xiàng)等。通過輸入的數(shù)據(jù)確定原問題，以及原問題的標(biāo)準(zhǔn)形式，接著程序自行判斷是否加入人工變量，進(jìn)行二階段法的第一階段，迭代得出第一階段的最優(yōu)表，然后接著進(jìn)行第二階段，繼續(xù)自行迭代，最后得出最優(yōu)解及最優(yōu)值。并通過LINDO軟件進(jìn)行靈敏度分析。該程序可以用于解決生活中的運(yùn)籌學(xué)線性規(guī)劃問題。主要包括研究經(jīng)濟(jì)活動(dòng)和軍事活動(dòng)中能用數(shù)量來表達(dá)的有關(guān)策劃、管理方面的問題。當(dāng)然，隨著客觀實(shí)際的發(fā)展，運(yùn)籌學(xué)的許多內(nèi)容不但研究經(jīng)濟(jì)和軍事活動(dòng)，有些已經(jīng)深入到日常生活當(dāng)中去了。運(yùn)籌學(xué)可以根據(jù)問題的要求，通過數(shù)學(xué)上的分析、運(yùn)算，得出各種各樣的結(jié)果，最后提出綜合性的合理安排，已達(dá)到最好的效果?？捎秒娮佑?jì)算機(jī)來處理成千上萬個(gè)約束條件和變量的大規(guī)模線性規(guī)劃問題，從解決技術(shù)問題的最優(yōu)化，到工業(yè)、農(nóng)業(yè)、商業(yè)、交通運(yùn)輸業(yè)以及決策分析部門都可以發(fā)揮作用。從范圍來看，小到一個(gè)班組的計(jì)劃安排，大至整個(gè)部門，以至國民經(jīng)濟(jì)計(jì)劃的最優(yōu)化方案分析，它都有用武之地，具有適應(yīng)性強(qiáng)，應(yīng)用面廣，計(jì)算技術(shù)比較簡便的特點(diǎn)。LINDO是一種專門用于求解數(shù)學(xué)規(guī)劃問題的軟件包。由于LINDO執(zhí)行速度很快、易于方便輸入、求解和分析數(shù)學(xué)規(guī)劃問題。因此在數(shù)學(xué)、科研和工業(yè)界得到廣泛應(yīng)用。LINDO主要用于解線性規(guī)劃、非線性規(guī)劃、二次規(guī)劃和整數(shù)規(guī)劃等問題。也可以用于一些非線性和線性方程組的求解以及代數(shù)方程求根等。LINDO中包含了一種建模語言和許多常用的數(shù)學(xué)函數(shù)（包括大量概論函數(shù)），可供使用者建立規(guī)劃問題時(shí)調(diào)用。4.2程序流程圖4.2.1第一階段程序流程圖圖1第一階段程序流程圖否否是是開始變量個(gè)數(shù)11、約束條件個(gè)數(shù)8、方程組矩陣系數(shù)A值、約束條件常數(shù)項(xiàng)b值、選擇目標(biāo)函數(shù)類型、目標(biāo)函數(shù)化成標(biāo)準(zhǔn)形式：加入松弛變量，將數(shù)據(jù)輸入相應(yīng)的數(shù)組中，形成初始單純形表存在人工變量為基變量去掉這些人工變量的列中具有1的所有行，再去掉相應(yīng)的行無解進(jìn)入第二階段求解結(jié)束否否是加入人工變量，調(diào)整約束方程位置Z＝-選擇主元行、列迭代檢驗(yàn)數(shù)≥0人工變量值全為04.2.2用實(shí)際的目標(biāo)函數(shù)取代余下的人工目標(biāo)函數(shù)用實(shí)際的目標(biāo)函數(shù)取代余下的人工目標(biāo)函數(shù)是是否否否是否是結(jié)束輸出最優(yōu)解和最優(yōu)值存在bij>0選擇主元素行r=min{bi0／bis}換元后計(jì)算各行新的系數(shù)1、brj=brj／brs2、bij=bij–brs*brj選擇主元素列s用非基變量的線性組合來表示基變量讀取第一階段計(jì)算結(jié)果：A和b的值開始存在cj<0無有界最優(yōu)解是否進(jìn)行靈敏度分析重新計(jì)算并輸出Z、X*。重新計(jì)算Z、X*。，并代入單純行表，重新迭代，輸出結(jié)果。c、b的變化是否影響最優(yōu)解和最優(yōu)基圖2第二階段程序流程圖4.3數(shù)據(jù)錄入4.3.14.3.24.34.3.44.3.54.4程序運(yùn)行由于程序使用的是C語言編寫的應(yīng)用程序，因此整個(gè)程序運(yùn)行輸入比較簡單，只要準(zhǔn)確無誤的輸入數(shù)據(jù)，一般都可得到最優(yōu)解與最優(yōu)基。程序運(yùn)行過程如下：4.4.14.4.24.44.4圖34.4.5同時(shí)程序自動(dòng)生成原問題的輔助LP問題方程組，如圖4：圖44.4.6按回車后，程序進(jìn)行第一階段迭代迭代，得到圖54.4.7按回車后，程序進(jìn)行第二階段迭代，迭代后得到最優(yōu)值和最優(yōu)解，如圖6圖6圖65.結(jié)果分析思路：5.1參數(shù)C的變化5.1.1問題（1）中水庫B供應(yīng)甲區(qū)的飲水管理費(fèi)的變化屬于LP問題模型中參數(shù)C的變化，而此問題中C是基變量X先確定基變量系數(shù)變化范圍，基變量系數(shù)變化影響所有非基變量的檢驗(yàn)數(shù)和目標(biāo)函數(shù)值。如果Cj的變化范圍在基變量Cj增量的變化范圍之內(nèi)則其最優(yōu)解、最優(yōu)值均不變；反之如果Cj的變化范圍超出基變量Cj增量的變化范圍，則需要重新迭代求出最優(yōu)值。5.1.2問題（2）中水庫A的供水量變化和問題（4）中乙區(qū)供水量的變化都屬于LP問題模型中參數(shù)b的變化根據(jù)max{-bi/βir|βir>0}<=b<=min{-bi/βir|βir<0}確定b的變化范圍。如果b的變化在該范圍之內(nèi)最優(yōu)基不變最優(yōu)解變化，最優(yōu)解由公式XB=B-1b求得。如果b的變化超出該范圍最優(yōu)基最優(yōu)解均發(fā)生變化，重新計(jì)算CBB-1b、B-1b代入最優(yōu)表中重新迭代。5.2問題分析通過對(duì)題目的正確理解和分析，依據(jù)題意可以得到在保證各區(qū)最低供水量的基礎(chǔ)上運(yùn)費(fèi)最低，也就是獲利最大的模型，以這個(gè)模型為基礎(chǔ)，可以得到公司分配供水量的最優(yōu)決策方案。然后通過靈敏度分析（1）水庫B供應(yīng)甲區(qū)的引水管理費(fèi)（元/千噸）在何范圍內(nèi)變化時(shí)最優(yōu)分配方案不變（2）水庫A的供水量在何范圍內(nèi)變化時(shí)最優(yōu)基不變（3）乙區(qū)的日供水量為80千噸時(shí)的最優(yōu)分配方案。5.3計(jì)算機(jī)的求解結(jié)果及分析5.3.1數(shù)據(jù)錄入，輸入變量個(gè)數(shù)以及變量系數(shù)和約束條件個(gè)數(shù)，依次輸入約束條件中變量的系數(shù)，以及右端常數(shù)項(xiàng)的值，輸入確定并回車后可得最優(yōu)解和最優(yōu)值。如圖圖7由圖可知，最優(yōu)分配供水量方案為：X12=50，X21=30，X22=20，X24=10，其余變量的值為0；即A水庫輸水到乙區(qū)50千噸，B水庫輸入到甲區(qū)30千噸，到乙區(qū)20千噸，到丁區(qū)10千噸。此時(shí)MinZ=1480，即最低總的飲水管理費(fèi)為1480元，則最大獲利為：Y=（90-45）*（50+30+20+10）-1480=3470（元）5.4靈敏度分析5.4.1根據(jù)結(jié)果分析當(dāng)目標(biāo)函數(shù)的變量系數(shù)在什么變化范圍內(nèi)時(shí)，最優(yōu)基不變。VARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX1116.000000INFINITY2.000000X1213.0000000.000000INFINITYX1322.000000INFINITY22.000000X1417.000000INFINITY2.000000X2114.0000002.00000014.000000X2213.0000007.0000000.000000X2319.000000INFINITY19.000000X2415.0000002.00000015.000000X3119.000000INFINITY5.000000X3220.000000INFINITY7.000000X3323.000000INFINITY23.000000其中各列表頭釋義為，CURRENTCOEF：初始目標(biāo)函數(shù)系數(shù)；ALLOWABLEINCREASE：允許變量系數(shù)增加的范圍；ALLOWABLEDECREASE：允許變量系數(shù)減少的范圍。則當(dāng)目標(biāo)函數(shù)的系數(shù)C在[初始目標(biāo)函數(shù)的系數(shù)-允許變量系數(shù)減少的范圍，初始目函數(shù)的系數(shù)+允許變量系數(shù)增加的范圍]內(nèi)變化時(shí)，最優(yōu)基不變，最優(yōu)解也不變，由于目標(biāo)函數(shù)的系數(shù)發(fā)生改變了，所以最優(yōu)值有可能改變。5.4.2根據(jù)結(jié)果分析約束條件右端項(xiàng)在什么范圍內(nèi)變化時(shí)，最優(yōu)基不變ROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000020.0000000.000000360.000000INFINITY0.000000450.000000INFINITY50.000000530.0000000.00000030.000000670.0000000.00000020.000000710.0000000.00000010.000000850.000000INFINITY20.000000930.000000INFINITY30.000000其中各列表頭釋義為，CURRENTRHS：初始約束條件右端項(xiàng)的值；ALLOWABLEINCREASE：允許b值增加的范圍；ALLOWABLEDECREASE：允許b值減少的范圍當(dāng)約束條件右端項(xiàng)的值在[初始約束條件右端項(xiàng)的值-允許b值減少的范圍，初始約束條件右端項(xiàng)的值+允許b值增加的范圍]內(nèi)變化時(shí)最優(yōu)基不變，最優(yōu)解不變。5.5原問題分析5.5.1水庫B供應(yīng)甲區(qū)的引水管理費(fèi)（元/千噸）在何變化范圍時(shí)最優(yōu)分配方案不變解：因?yàn)樗畮霣供應(yīng)甲區(qū)的飲水管理費(fèi)為C21，由上列計(jì)算結(jié)果可得允許變量系數(shù)增加的范圍為[0，2]，允許變量系數(shù)減少的范圍[0，14]，所以水庫B供應(yīng)甲區(qū)的飲水管理費(fèi)在[0,16]范圍內(nèi)變化時(shí)最優(yōu)基不變。5.5.2水庫A的供水量在何范圍內(nèi)變化時(shí)最優(yōu)基不變解：因?yàn)樗畮霢的供水量年是第1個(gè)約束條件的右端項(xiàng)，即該問題求的是b1的