線性規(guī)劃的實際應(yīng)用

-.z..--.可修編-線性規(guī)劃的實際應(yīng)用摘要線性規(guī)劃模型是科學(xué)與工程領(lǐng)域廣泛應(yīng)用的數(shù)學(xué)模型。本文應(yīng)用線性規(guī)劃模型，以*水庫輸水管的選擇為研究對象，以實現(xiàn)輸水管的選擇既能保證供水，又能使造價最低為目標(biāo)，根據(jù)水庫的特點和實際運行情況，分析了其輸水管選擇過程中線性規(guī)劃模型的建立方法，并分別通過單純形法和MATLAB軟件進行求解。關(guān)鍵詞線性規(guī)劃模型單純形法MATLAB一、專著背景簡介《最優(yōu)化方法》介紹最優(yōu)化模型的理論與計算方法，其中理論包括對偶理論、非線性規(guī)劃的最優(yōu)性理論、非線性半定規(guī)劃的最優(yōu)性理論、非線性二階錐優(yōu)化的最優(yōu)性理論；計算方法包括無約束優(yōu)化的線搜索方法、線性規(guī)劃的單純形方法和內(nèi)點方法、非線性規(guī)劃的序列二次規(guī)劃方法、非線性規(guī)劃的增廣Lagrange方法、非線性半定規(guī)劃的增廣Lagrange方法、非線性二階錐優(yōu)化的增廣Lagrange方法以及整數(shù)規(guī)劃的Lagrange松弛方法?！蹲顑?yōu)化方法》注重知識的準(zhǔn)確性、系統(tǒng)性和算法論述的完整性，是學(xué)習(xí)最優(yōu)化方法的一本入門書。最優(yōu)化方法（也稱做運籌學(xué)方法）是近幾十年形成的，它主要運用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù)。最優(yōu)化方法的主要研究對象是各種有組織系統(tǒng)的管理問題及其生產(chǎn)經(jīng)營活動。最優(yōu)化方法的目的在于針對所研究的系統(tǒng)，求得一個合理運用人力、物力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效能及效益，最終達到系統(tǒng)的最優(yōu)目標(biāo)。實踐表明，隨著科學(xué)技術(shù)的日益進步和生產(chǎn)經(jīng)營的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法，被人們廣泛地應(yīng)用到公共管理、經(jīng)濟管理、工程建設(shè)、國防等各個領(lǐng)域，發(fā)揮著越來越重要的作用。本章將介紹最優(yōu)化方法的研究對象、特點，以及最優(yōu)化方法模型的建立和模型的分析、求解、應(yīng)用。主要是線性規(guī)劃問題的模型、求解（線性規(guī)劃問題的單純形解法）及其應(yīng)用-運輸問題；以及動態(tài)規(guī)劃的模型、求解、應(yīng)用-資源分配問題。二、專著的主要結(jié)構(gòu)內(nèi)容《最優(yōu)化方法》是一本著重實際應(yīng)用又有一定理論深度的最優(yōu)化方法教材，內(nèi)容包括線性規(guī)劃、運輸問題、整數(shù)規(guī)劃、目標(biāo)規(guī)劃、非線性規(guī)劃（無約束最優(yōu)化與約束最優(yōu)化）、動態(tài)規(guī)劃等最基本、應(yīng)用最廣又最有代表性的最優(yōu)化方法。各章都由實例引入，對主要定理進行證明，引入相應(yīng)的數(shù)學(xué)模型與算法，配有算法例題與詳細步驟.章末附有習(xí)題，書末有習(xí)題解答與提示?！蹲顑?yōu)化方法》還專辟一章，列舉了用新版本的MATLAB軟件包及LINDO/LINGO優(yōu)化軟件包來計算的實例。本教材在闡述基本概念與基本理論時，力求清晰、透徹，在適當(dāng)?shù)胤脚渲昧艘恍┧伎碱}，以促使讀者深入思考，加深對內(nèi)容的理解.在文字敘述方面力求語言淺顯、簡易明了、深入淺出，以便于學(xué)生學(xué)習(xí)。內(nèi)容概況如下：第1章線性規(guī)劃主要內(nèi)容包括：1.1線性規(guī)劃問題的基本概念；1.2單純形法；1.3線性規(guī)劃的對偶理論；1.4運輸問題；1.5線性目標(biāo)規(guī)劃；1.6線性規(guī)劃應(yīng)用實例。第2章整數(shù)規(guī)劃主要內(nèi)容包括：2.1整數(shù)規(guī)劃問題的數(shù)學(xué)模型；2.2分枝定界法；2.3割平面法；2.40.1型整數(shù)規(guī)劃；2.5指派問題與匈牙利解法。第3章非線性規(guī)劃的基本概念與基本原理主要內(nèi)容包括：3.1非線性規(guī)劃的數(shù)學(xué)模型；3.2無約束問題的最優(yōu)性條件；3.3凸函數(shù)與凸規(guī)劃；3.4解非線性規(guī)劃的基本思路；3.5一維搜索。第4章無約束問題的最優(yōu)化方法主要內(nèi)容包括：4.1變量輪換法；4.2最速下降法；4.3牛頓法；4.4共軛梯度法；4.5變尺度法簡介。第5章約束問題的最優(yōu)化方法主要內(nèi)容包括：5.1約束極值問題的最優(yōu)性條件；5.2可行方向法；5.3近似規(guī)劃法；5.4制約函數(shù)法；5.5二次規(guī)劃。第6章動態(tài)規(guī)劃主要內(nèi)容包括：6.1動態(tài)規(guī)劃問題實例；6.2動態(tài)規(guī)劃的基本概念；6.3最優(yōu)性定理與基本方程；6.4動態(tài)規(guī)劃的應(yīng)用舉例。第7章用優(yōu)化軟件計算實例主要內(nèi)容包括：7.1用MATLAB7.0優(yōu)化工具箱計算實例；7.2用LINDO/LINGO軟件計算實例。三、重點分析與心得體會《最優(yōu)化方法》[1]這本書，著重實際應(yīng)用又有一定理論深度的最優(yōu)化方法教材，內(nèi)容包括：線性規(guī)劃[1-5]、運輸問題[1-5]、整數(shù)規(guī)劃[1-5]、目標(biāo)規(guī)劃[1-5]、非線性規(guī)劃[1-5]（無約束最優(yōu)化與有約束最優(yōu)化），動態(tài)規(guī)劃[1-5]等最基本、應(yīng)用最廣最有代表性的最優(yōu)化方法。本人在此著重分析一下線性規(guī)劃應(yīng)用的相關(guān)問題。線性規(guī)劃，是自1947年丹齊格提出了求解線性規(guī)劃一般放法-單純性法以來，線性規(guī)劃在理論上趨向成熟，日臻完善。線性規(guī)劃輔助人們進行科學(xué)管理，是國際應(yīng)用數(shù)學(xué)經(jīng)濟管理計算機科學(xué)界所關(guān)注的重要研究領(lǐng)域。線性規(guī)劃主要研究有限資源的最佳分配問題，即如何對有限的資源進行最佳地調(diào)配和最有利地使用，以便于最充分發(fā)揮資源的效能來獲取最佳的經(jīng)濟效益。線性規(guī)劃運用數(shù)學(xué)語言描述*些經(jīng)濟活動的過程，形成數(shù)學(xué)模型，以一定的算法對模型進行計算，為制定最優(yōu)計劃方案提供依據(jù)。其解決問題的關(guān)鍵是建立符合實際情況的數(shù)學(xué)模型，即線性規(guī)劃模型。在各種經(jīng)濟活動中，常采用線性規(guī)劃模型進行科學(xué)定量分析，安排生產(chǎn)組織與計劃，實現(xiàn)人力物力資源的最優(yōu)配置，獲得最佳的經(jīng)濟效益。目前，線性規(guī)劃模型被廣泛應(yīng)用于經(jīng)濟管理交通運輸工農(nóng)業(yè)生產(chǎn)等領(lǐng)域。3.1線性規(guī)劃的數(shù)學(xué)模型[6-9]線性規(guī)劃問題是求線性目標(biāo)函數(shù)在線性約束條件下的最大值或最小值的問題。這類問題的數(shù)學(xué)表達式稱為線性規(guī)劃模型。線性規(guī)劃模型的一般形式包括決策變量、約束條件和目標(biāo)函數(shù)三部分。決策變量都是非負的，其值代表待解決問題的一個具體方案，形式如下：約束條件都是線性等式或線性不等式，它們反映了待解決問題對資源的客觀限制及對所要完成的任務(wù)的各類要求，形式如下：其中，為第個約束條件中對應(yīng)第個變量的約束條件系數(shù)，是第個約束條件的右邊常數(shù)，它表示必須滿足的*種要求。目標(biāo)函數(shù)是決策變量的線性函數(shù)，根據(jù)待解決問題的不同，可要求目標(biāo)函數(shù)Z實現(xiàn)最大值或最小值，形式如下：其中，是目標(biāo)函數(shù)系數(shù)或價值系數(shù)。3.2、線性規(guī)劃模型在*地區(qū)水庫調(diào)節(jié)水池中的應(yīng)用[10-11]（1）最優(yōu)化問題的提出*地區(qū)水源取自*水庫，水庫涵洞底標(biāo)高為，水輸送到調(diào)節(jié)水池距離為，調(diào)節(jié)水池最高水位(高),該段距離中要求輸水量；另一段，從調(diào)節(jié)水池輸水到*水廠的距離為，調(diào)節(jié)水池低水位標(biāo)高為，水廠水池標(biāo)高為，高差，要求輸水量可供鋪設(shè)的輸水管有四種不同直徑，它們的單位長度造價和水頭損失列于表中。問應(yīng)如何適當(dāng)選擇輸水管進行鋪設(shè),既能保證供水，又能使造價最低。表1輸水管道單位長度造價和水頭損失管徑單價(元/m)單位長度水頭損失(m/1000m)Q=174L/s時的水頭損失h/mQ=116L/s時的水頭損失h/m6001000.8730.419500742.1601.030400546.7603.1203003631.00013.800（2）線性規(guī)劃模型的建立對第一段水庫到調(diào)節(jié)水池建立線性規(guī)劃模型：①選取決策變量根據(jù)水庫的需要，選取管徑為的輸水營的鋪設(shè)長度作為決策變量，并且決策變量分別設(shè)為。②確定目標(biāo)函數(shù)水庫的目標(biāo)是既能保證供水，又能使造價最低，目標(biāo)函數(shù)如下：③確定約束條件約束條件是由水庫的特點和輸水管性能決定的，它反映了決策變量與水庫參數(shù)之間必須遵循的關(guān)系。如果在建立模型時忽略了重要的約束條件，則求得的解不可信；但如果過于細微，約束條件數(shù)目增加，計算時間也將增加；同時由于變量多，關(guān)系復(fù)雜，比較容易給出互為矛盾的約束條件，造成模型無解。供水保證約束：要求輸水量為時，該段總水頭損失不超過：非負約束：得到如下線性規(guī)劃模型為：同理可得到第二段水庫到調(diào)節(jié)水池建立線性規(guī)劃模型：3.3、線性規(guī)劃問題的分析與求解[10-11]（1）單純形法求解線性規(guī)劃問題使用單純形法求解線性規(guī)劃時，首先要化問題為標(biāo)準(zhǔn)形式所謂標(biāo)準(zhǔn)形式是指下列形式：當(dāng)實際模型非標(biāo)準(zhǔn)形式時，可以通過以下變換化為標(biāo)準(zhǔn)形式：①當(dāng)目標(biāo)函數(shù)為時，可令，而將其寫成為:求得最終解時，再求逆變換Z=-Z′即可。②當(dāng)s?t?中存在形式的約束條件時，可引進變量：便寫原條件成為：其中的稱為松弛變量，其作用是化不等式約束為等式約束。同理，若該約束不是用"≤”號連接，而是用"≥”連接，則可引進剩余變量：使原條件寫成：在將線性規(guī)劃模型化為標(biāo)準(zhǔn)形后，便可使用單純形法求解。所謂單純形法，是指1947年美國數(shù)學(xué)家喬治·丹捷格發(fā)明的一種求解線性規(guī)劃模型的一般性方法。該模型的標(biāo)準(zhǔn)形式為：得到線性規(guī)劃化為標(biāo)準(zhǔn)形后，用最快的方法確定一個初始基本可行解。求中非基本變量的檢驗數(shù)。若，則停止運算，（表示最優(yōu)解），否則繼續(xù)迭代。由確定進基，由確定出基，其中稱為主元素；利用初等變換將化為1，并利用將同列中其它元素化為0，得新解，直至求得最優(yōu)解為止?，F(xiàn)利用上述程序重新求解上例。為了方便明了，采用一種稱為單純形表的形式求解。為此，將問題的標(biāo)準(zhǔn)形式進一步表述為：求和，使?jié)M足方程組：且要求各個非負，的值達最小。然后，將上述方程組寫成如下表格形式：CB基*1*2*3*4*5Zb0*30.8732.166.763110100000*411110014700*5(100)70543600810+500+350000-10我們把這個表稱作初始單純形表，其特點是，從第三列起將約束方程組連同目標(biāo)函數(shù)一起按各變量位置寫出，它把目標(biāo)函數(shù)作為一個特殊的約束，實際上是各變量的檢驗數(shù)所在行。最左邊兩列則表明了目前解的基本變量及其相應(yīng)的價值系數(shù)，最右邊一列則給出了目前解的基本變量取值，右下角的數(shù)0給出這一解的目標(biāo)值，由于,均為正數(shù)，故目前解非最優(yōu)，按照上述步驟開始尋找另一個更好的解。令*1進基，然后以b列與*1所在列各正分量作比，求其最小值，得故*5出基而主元素為6。為明確，將主元素加上括號便清楚地看到主元素所在列對應(yīng)的進基，所在行對應(yīng)的變量出基。CB基*1*2*3*4*5Zb0*30-1/310-1/30300*40（1/3）01-2/3060500*1(1)2/3001/60135σj050/300-250/3-1-67500由這一表易見，目前解，目標(biāo)值為72500。由于，故仍非最優(yōu)解。令進基，重復(fù)以上步驟。經(jīng)過3次迭代后我們可以得到第一段總造價最低為79325.2元。同理我可以求出第二段總造價最低為276586元。3.4、MATLAB求解線性規(guī)劃問題[12-14]根據(jù)上一節(jié)，建立的線性規(guī)劃模型，我們可以利用MATLAB編程求解。MATLAB可以高效、方便地解決線性規(guī)劃問題。線性規(guī)劃是合理利用、調(diào)配資源的一種應(yīng)用數(shù)學(xué)的方法。它的基本思路就是在滿足一定的約束條件下，使預(yù)定的目標(biāo)達到最優(yōu)。它的研究內(nèi)容可歸納為兩個方面：一是系統(tǒng)的任務(wù)已定,如何合理籌劃，精細安排，用最少的資源去實現(xiàn)這個任務(wù)：二是資源的數(shù)量已定,如何利用、分配，使任務(wù)完成得最多。前者是求極小，后者是求極大。線性規(guī)劃是在滿足企業(yè)內(nèi)、外部的條件下，實現(xiàn)管理目標(biāo)和極值問題，就是要以盡少的資源輸入來實現(xiàn)更多的社會需要的產(chǎn)品的產(chǎn)出?，F(xiàn)在通過專門的數(shù)學(xué)MATLAB軟件，只要將模型中的目標(biāo)函數(shù)系數(shù)、約束條件系數(shù)、不等關(guān)系輸入計算機，就會很快算出結(jié)果。對第一段水庫調(diào)節(jié)水池的線性規(guī)劃模型編程如下：運行結(jié)果如下：對第二段水庫調(diào)節(jié)水池的線性規(guī)劃模型編程如下：運行結(jié)果如下：四、總結(jié)本文通過對資源分配問題的分析，建立其線性化的目標(biāo)函數(shù)，并運用線性規(guī)劃的經(jīng)典算法單純形法對其進行求解，經(jīng)分析演算，問題得到了很好的解決。通過本文，我們認識到線性規(guī)劃問題在解決社會生產(chǎn)中的最優(yōu)化問題的重要性，單純形方法作為解決線性規(guī)劃問題經(jīng)典方法，發(fā)揮著重要的作用。下面是本人通過學(xué)習(xí)以上知識所做總結(jié)。（1）單純形法總結(jié)本人覺得用單純形法解決線性規(guī)劃問題需要注意以下幾點：1）目標(biāo)函數(shù)極小化時解的最優(yōu)性判別當(dāng)所求的線性規(guī)劃問題的目標(biāo)函數(shù)求極小值時，只需以所有檢驗數(shù)σj≥0作為判別表中解是否最優(yōu)的標(biāo)志；2）退化與循環(huán)一個基可行解如果存在取0的基變量，則稱為是退化的基本可行解，相應(yīng)的基稱為退化基。3）在退化情況下，用單純形法進行迭代時，經(jīng)過若干次后又回到原來的可行基：如B1,B2,…,B1，此時目標(biāo)函數(shù)值并沒用改變，這樣的問題稱為退化帶來的循環(huán)問題。4）退化解出現(xiàn)的原因一般是模型中存在多余的約束，使多個基可行解對應(yīng)同一頂點。這樣，按最小比值來確定出基變量時，有時會存在兩個以上相同的最小比值，從而使下一個表的基可行解中出現(xiàn)一個或多個基變量等于0的退化解。當(dāng)存在退化解時，就有可能出現(xiàn)計算循環(huán)。5）在計算表格中填寫其它量的時候須細心認真，千萬不能算錯，否則可能就一步錯步步錯了。（2）MATLAB求解總結(jié)線性規(guī)劃為硬性約束,在一定的條件下存在最優(yōu)解，用MATLAB線性約束優(yōu)化函數(shù),能求出滿足所有約束條件的最優(yōu)解。但在求解具有相互矛盾的約束條件時會出現(xiàn)無解的情況。MATLAB編程效率和計算效率極高，逐漸成為國際性的計算標(biāo)準(zhǔn)，在各個領(lǐng)域得到廣泛應(yīng)用。使用MATLAB工具箱，只須編寫很簡單的幾行程序代碼，即可進行線性規(guī)劃的優(yōu)化設(shè)計，且結(jié)果可靠，計算精度高，避免了應(yīng)用其他語言程序過于復(fù)雜、調(diào)試困難等缺點,提高了計算效果。五、展望隨著人們對線性規(guī)劃理論認識的加深,以及對線性規(guī)劃方法的進一步了解和它在實際中應(yīng)用*圍的擴展,人們將會逐漸把線性規(guī)劃的方法應(yīng)用到越來越廣泛的適用領(lǐng)域.特別是最近幾年,人們用線性規(guī)劃的方法結(jié)合模