運籌學(xué)實驗報告 調(diào)水優(yōu)化設(shè)計問題

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