線性規(guī)劃法在救援物資調(diào)運問題中的應(yīng)用1

《運籌學教程》綜合設(shè)計項目名稱：線性規(guī)劃法在救援物資調(diào)運問題中的應(yīng)用2011年122011年12月19日組長：學號：——姓名：—成員：學號：—姓名：_學號：姓名：學號：姓名：開課學期：2011至2012學年第一學期指導(dǎo)教師：完成時間:成線性規(guī)劃法在救援物資調(diào)運問題中的應(yīng)用【摘要】最近幾年，我國物流產(chǎn)業(yè)快速發(fā)展，形成了物流熱，在物流作業(yè)管理中，有著大量的規(guī)劃問題，物資的合理調(diào)運就是其中一個比較重要的問題。本文通過建立線性規(guī)劃模型，利用線性規(guī)劃法，用Excel求出了物資調(diào)運問題的最優(yōu)解，得到了一個最佳的物資調(diào)運方案。分析的過程中，我們要確定出合適調(diào)運方案，使運輸總費用最小，即將“費用最小化”作為調(diào)運最終目標。在具體的求解過程中，借助運籌學相關(guān)知識將此問題轉(zhuǎn)化為線性規(guī)劃模型的最優(yōu)解求解問題，并建立線性規(guī)劃模型、運用Excel軟件得出最優(yōu)化解?！娟P(guān)鍵詞】：線性規(guī)劃法；Excel；調(diào)運，運輸總費用，最優(yōu)解一、問題提出由于近幾年來地殼運動劇烈，各種自然災(zāi)害頻頻發(fā)生，其中各地的地震災(zāi)害尤其嚴重。汶川地震發(fā)生后，為了盡可能的減小國家和人民的損失，各級政府對災(zāi)區(qū)進行物資救助。為了解決大規(guī)模物資調(diào)運的實際問題（通常要處理的實際問題都是大規(guī)模的物資調(diào)運問題）以及物流管理中的類似問題，我們必須先建立這類問題的數(shù)學模型，而后選擇合適的計算方法并利用計算機工具求解。這種數(shù)學模型稱為規(guī)劃問題，規(guī)劃問題中涉及的線性函數(shù)關(guān)系，我們就稱為線性規(guī)劃問題。本文將在物資調(diào)運中的實際問題建立數(shù)學模型，用Excel求出物資調(diào)用的最優(yōu)方案。我們首先應(yīng)確立線性規(guī)劃的模型和其應(yīng)用以及Excel的作用。一、線性規(guī)劃問題及其數(shù)學模型線性規(guī)劃的模型決定于它的定義，線性規(guī)劃的定義是：求一組變量的值，在滿足一組約束條件下，求得目標函數(shù)的最優(yōu)解。根據(jù)這個定義，就可以確定線性規(guī)劃模型的基本結(jié)構(gòu)。（1）變量又叫未知數(shù)，它是實際系統(tǒng)的未知因素，也是決策系統(tǒng)中的可控因素，一般稱為決策變量。（2）目標函數(shù)將實際系統(tǒng)的目標，用數(shù)學形式表現(xiàn)出來，就稱為目標函數(shù)，線性規(guī)劃的目標函數(shù)是求系統(tǒng)目標的數(shù)值，即極大值，如產(chǎn)值極大值、利潤極大值或者極小值，如成本極小值、費用極小值、損耗極小值等等。（3）約束條件是指實現(xiàn)系統(tǒng)目標的限制因素。它涉及到企業(yè)內(nèi)部條件和外部環(huán)境的各個方面，如原材料供應(yīng)、設(shè)備能力、計劃指標、產(chǎn)品質(zhì)量要求和市場銷售狀態(tài)等等，這些因素都對模型的變量起約束作用，故稱其為約束條件。約束條件的數(shù)學表示形式為三種，艮吃、=、〔線性規(guī)劃的變量應(yīng)為正值，因為變量在實際問題中所代表的均為實物，所以不能為負。在經(jīng)濟管理中，線性規(guī)劃使用較多的是下述幾個方面的問題：（1）投資問題一確定有限投資額的最優(yōu)分配，使得收益最大或者見效快。（2）計劃安排問題一確定生產(chǎn)的品種和數(shù)量，使得產(chǎn)值或利潤最大，如資源配制問題。任務(wù)分配問題一分配不同的工作給各個對象(勞動力或機床)，使產(chǎn)量最多、效率最高，如生產(chǎn)安排問題。下料問題一如何下料，使得邊角料損失最小。運輸問題一在物資調(diào)運過程中，確定最經(jīng)濟的調(diào)運方案。庫存問題一如何確定最佳庫存量，做到即保證生產(chǎn)又節(jié)約資金等等。應(yīng)用線性規(guī)劃建立數(shù)學模型的三步驟：明確問題，確定問題，列出約束條件。收集資料，建立模型。模型求解(最優(yōu)解)，進行優(yōu)化后分析。其中，最困難的是建立模型，而建立模型的關(guān)鍵是明確問題、確定目標，在建立模型過程中花時間、花精力最大的是收集資料。本題我們選取了運輸問題來建立模型。二、Excel的簡介：Excel是分析和求解線性規(guī)劃問題的良好工具，它不僅可以很方便地將線性規(guī)劃模型所有參數(shù)錄入電子表格，而且可以利用規(guī)劃求解工具迅速找到模型的最優(yōu)解。更重要的是，在利用Excel電子表格求解模型時，改變?nèi)魏螀?shù)都能立刻反映到模型的解，不需要重新應(yīng)用求解工具和重新錄入數(shù)據(jù)，即使重新求解也只需按回車鍵即可完成。當然，Excel不但可以處理線性規(guī)劃問題，還可以處理整數(shù)規(guī)劃和運輸問題等經(jīng)典的線性規(guī)劃問題，極大滿足了人們學習運籌學和在實踐中解決線性規(guī)劃問題的需要。二、物資調(diào)運問題針對物資調(diào)運，我們想到了關(guān)于在自然災(zāi)害發(fā)生時，我們向受災(zāi)點調(diào)運受災(zāi)物資的情形。但運輸物資，需保證物資的完備性，必須滿足受災(zāi)點的需要。并且更主要的也要考慮運輸?shù)目傎M用最低，從而節(jié)約成本。針對這些現(xiàn)象，我們找了一個案例用來分析物資調(diào)運問題。以下就是我們所收集的資料和數(shù)據(jù)：現(xiàn)有三家企業(yè)捐獻物資調(diào)運到四個受災(zāi)點。企業(yè)A，B，C捐贈物資量分別為110噸、70噸、100噸；四個受災(zāi)點I，Il，III，W，需求量分別為60噸、70噸、50噸、70噸。企業(yè)A往受災(zāi)點I，II，III，W每噸的運價分別為l0元、15元、20元、25元；企業(yè)B到受災(zāi)點I，II，III，W每噸的運價分別為2O元、10元、l5元、15元：企業(yè)C到受災(zāi)點I，II，III，W每噸的運價分別為25元、30元、20元、25元。如何確定調(diào)運方案，才能使運輸總費用最小。在這個題目中我們所了解的約束條件主要有三個：一是企業(yè)捐贈物資量的限制，總數(shù)是280噸，而其中A企業(yè)捐贈110噸，B企業(yè)捐贈70噸，C企業(yè)捐贈100噸，我們在計算各受災(zāi)點需求量的時候絕對不能超過這個量；二是各受災(zāi)點需求量的限制，受災(zāi)點收到的物資不得小于它們的需求量，也就是說各受災(zāi)點需求量是下限；三是調(diào)運物資的數(shù)量的限制，企業(yè)運輸?shù)绞転?zāi)點的物資數(shù)量必須大于等于零。在這些約束條件的限制下，我們經(jīng)過計算，得出運輸總費用為3800元，并且各受災(zāi)點所需的物資量達到滿足。下面我們就把該問題規(guī)范為一個線性規(guī)劃問題，用相關(guān)Excel求解。首先我們需要的是目標函數(shù)，毫無疑問，這里肯定是以運輸費用最小化作為目標。費用是用各點的運價乘以它們的需求量，再匯總求和，計算出最小值。其主要的項目和數(shù)據(jù)如下表：運輸費用數(shù)據(jù)表\受災(zāi)點企業(yè)'IIIIIIW供應(yīng)量A10152025110B2010151570C25302025100需求量60705070首先，設(shè)運輸總費用為W，我們要求運輸總費用最小，現(xiàn)在我們可以得到目標函數(shù)了，即目標函數(shù)為：MinW=10x+15x+20x+25x+20x+10x+15x+15x+25x+30x+20x+25x111213142122232431323334得到目標函數(shù)之后我們需要把約束條件列出才能求解，那現(xiàn)在我們依據(jù)前文的描述可以知道，約束條件共有三各方面，分別是企業(yè)捐贈物資量的限制，各受災(zāi)點需求量的限制，調(diào)運物資的數(shù)量的限制。其中孔表示從企業(yè)i調(diào)運到受災(zāi)點j物資的數(shù)量，minW表示運輸費用最少?？紤]約束條件如上表所述的供應(yīng)量和銷地的需求量要滿足運輸平衡條件，以及各變量取非負數(shù)，就是限制條件。首先是供應(yīng)量方面，即四個受災(zāi)點的物資需求量不能超過三個企業(yè)的供應(yīng)量。所以有x+x+xx<=110，x+x+xx<=70，x+x+xx<=100；111213+14212223+24313233+34然后是需求量方面，三企業(yè)分別運輸?shù)剿膫€受災(zāi)點的物資的總和不能少于受災(zāi)點的需求量，否則就不能得到滿足。所以有x+x+x>=60，x+x+x>=70，x+x+x>=50，112131122232132333x+x+x>=70；最后是調(diào)運物資的數(shù)量方面，即分別運輸?shù)礁魇転?zāi)點的物資要大于等于142434零。所以有Xij^0(i=1,2,3;j=1,2,3,4)經(jīng)過上面的描述，我們經(jīng)過整理之后可得如下約束條件：rx+x+xx<=110111213+14x+x+xx<=70212223+24x+x+xx<=100313233+34x+x+x>=60112131xi2+x22+x32>=70x+x+x>=50x+x+x>=70142434孔日0(1=1,2,3門二1,2,3,4)最后，我們將目標函數(shù)和約束條件寫在一起，就得到了物資調(diào)運問題的數(shù)學模型，即線性規(guī)劃問題：MinW=10x+15x+20x+25x+20x+10x+15x+15x+25x+30x+20x+25xTOC\o"1-5"\h\z111213142122232431323334rx+x+x<=110111213x21+x22+x23<=70x31+x32+x33<=100x+x+x>=60112131x12+x22+x32>=70x+x+x>=50x+x+x>=70142434IXjjN0(i=1,2,3;j=1,2,3,4)三、用Excel實現(xiàn)結(jié)果卜面我們根據(jù)建立出來的數(shù)據(jù)模型用Excel來計算出結(jié)果。具體過程如下：(1)根據(jù)題目把表中的數(shù)據(jù)以及所有約束條件及數(shù)據(jù)輸入Excel中，如圖所示:對每一步進行求解，求解過程如下：11|A]二11)|12|B=suid(B12:E12)CB_=suid(B11:B13)C||=SUIo(Cll:C13)|=suid(E11:E13)(2)分別建立單位運價表和調(diào)運量表:從調(diào)運量表工廠IIIIIIIV605000B020050I-100502060705070(3)通過規(guī)劃求解參數(shù)來求出問題最優(yōu)解:j=S1-UTl(B13:E13)|=BH=suid(D11^D13)決策變量運輸問題規(guī)劃求解參數(shù)設(shè)置:由上述計算結(jié)果可知，、二60,X12=50,X13=0X2「0,X/20,X23=0,X=0,X=0,X=50,313233該線性規(guī)劃的最優(yōu)解為:X14=0X24=50X34=20由此求出最優(yōu)值為：minW=3800。即運輸總費用的最小值為3800元。并且每個受災(zāi)點都達到了它們的需求量。四、總結(jié)以上是一個供大于求的運輸問題的示例，運用以上示例即可求得一個最佳的物資調(diào)運方案。對于平衡問題，只需在填寫規(guī)劃求解參數(shù)中添加約束條件時稍做改動即可求解，或者將其轉(zhuǎn)化為平衡問題后建立相應(yīng)的線性規(guī)劃模型，再用以上方法求解亦可。通過這個物資運輸問題的求解，我們學到了如何去靈活運用線性規(guī)劃方法來求得運輸問題的最優(yōu)解，知道怎么根據(jù)問題來分步建立數(shù)學模型，同時也掌握了用Excel求解的方法，使我們更深的認識了運籌學的魅力，也明白了線性規(guī)劃問題在實際生活應(yīng)用中求最優(yōu)化問題時起到了很大的作用。這次的運籌學大作業(yè)，我們小組合力完成，分工協(xié)作，相互討論，分工尋找案例，分析數(shù)據(jù)，繪制表格，列出數(shù)據(jù)模型，并運用Excel求解，這讓我們明白小組合作的重要性，每個成員都盡心盡力，做好自己應(yīng)該做的工作，但同時我們也意識到這次我們尋找的案例