運籌學總復習(嘉興2課時)

運籌學總復習(嘉興2課時)運籌學總復習(嘉興2課時)運籌學總復習(嘉興2課時)xxx公司運籌學總復習(嘉興2課時)文件編號：文件日期：修訂次數(shù)：第1.0次更改批準審核制定方案設(shè)計，管理制度基本要求一、將線性規(guī)劃化為標準型和寫出相應(yīng)的對偶規(guī)劃；二、用圖解法求解具有兩個決策變量的線性規(guī)劃問題；三、用單純形方法；四、整數(shù)規(guī)劃與分枝定界法，0-1規(guī)劃與隱枚舉法，指派問題六、求解產(chǎn)銷平衡的運輸問題和產(chǎn)銷不平衡的運輸問題；七、動態(tài)規(guī)劃與求解.問題一、化標準型⑴標準型的概念：①目標函數(shù)為極大化；②資源常數(shù)；③約束條件關(guān)系為等式；④決策變量。例：將下面的線性規(guī)劃化為標準型無非負限制解 二、圖解法例用圖解法求解線性規(guī)劃問題極大化解：最優(yōu)解三、單純形方法對于具有兩個以上決策變量的線性規(guī)劃問題，采用單純形方法進行求解。具體過程是：⑴建立單純形表，在單純形表中，務(wù)必使基變量的價值系數(shù)為零，則檢驗數(shù)行是價值系數(shù)行的相反數(shù)；⑵若檢驗數(shù)則當前解為最優(yōu)解（當前解是基變量取相應(yīng)的資源常數(shù)，非基變量取為零）；若存在檢驗數(shù)，則要進行相應(yīng)的換基，即：迭代；⑶①進基：進基變量：②出基：出基變量為第行所對應(yīng)的基變量，由下面的關(guān)系確定③以主元進行迭代，目標：主元化為1，該列的其余元化為零。⑷再一次判定當前解是否為最優(yōu)解。建立對偶規(guī)劃的要點⑴原規(guī)劃是極大化，則對偶規(guī)劃是極小化；⑵原規(guī)劃的價值系數(shù)是對偶規(guī)劃中的資源常數(shù)；⑶原規(guī)劃與對偶規(guī)劃的約束條件系數(shù)矩陣為矩陣的轉(zhuǎn)置關(guān)系；⑷原規(guī)劃中的第個決策變量非正，則對偶規(guī)劃中的第個約束條件取反向不等式；⑸原規(guī)劃中的第個決策變量無非負限制，則對偶規(guī)劃中的第個約束條件為等式.例求下面問題的對偶規(guī)劃極大化無非負限制。解極小化對偶單純形法基本要求：檢驗數(shù)；資源常數(shù)存在負值。解法：列出對偶單純形表；將基變量在目標函數(shù)中系數(shù)化為零，檢驗數(shù)為新目標函數(shù)中系數(shù)的相反數(shù)；判斷，若，則當前解為最優(yōu)解；若中存在負項，則進行迭代，確定出基和進基變量； 出基：記為第r行對應(yīng)的變量； 進基：，為進基變量； 以為主元進行迭代。目標：將主元化為1，該列的其余元化為0。例：用單純性方法求解下面線性規(guī)劃問題：解由單純形方法得即,原問題的最優(yōu)解為例用分枝定界法求解整數(shù)規(guī)劃用隱枚舉法求解0-1規(guī)劃解增加過濾條件：，則原規(guī)劃改為解向量條件1條件2條件3條件4函數(shù)值FFFTTTT5TTTFTFTFTTTT7TTTT9所以，最優(yōu)方案為，最優(yōu)值為.指派問題的求解：1.的指派問題的最小值解的求解方法：⑴用行縮減和列縮減在每行和每列至少產(chǎn)生一個零；⑵用劃線法判定是否有個獨立的零；⑶如果有個獨立的零，則可以求出最小值解；⑷若沒有個獨立的零，重新進行調(diào)整，以求出個獨立的零。2.的指派問題的最小值解的求解方法：設(shè)置虛擬變量，其價值系數(shù)取為零。3.指派問題中的最大值求解。例：求下面指派問題的最小值解：解：故最優(yōu)解為：，最優(yōu)解值為。例：求下面指派問題的最小值及最大值解：例：求下面指派問題的最大值解：運輸問題（產(chǎn)銷平衡）的求解方法：表上作業(yè)法1.用最小元素法求初始解；2.用位勢法求出當前解所對應(yīng)的位勢：若為基變量，則行位勢和列位勢滿足關(guān)系3.用位勢法計算非基變量的影響系數(shù)：若為非基變量，則影響系數(shù)與行位勢和列位勢滿足關(guān)系4.最優(yōu)解的判定：若影響系數(shù)則當前解為最優(yōu)解；否則通過解的調(diào)整求出最優(yōu)解；5.解的調(diào)整：⑴記：⑵令為所對應(yīng)的非基變量，以為當前變量，構(gòu)造閉回路；⑶在閉回路上確定最大調(diào)整量；⑷求出新解6.重新判定當前解是否為最優(yōu)解。產(chǎn)銷不平衡的運輸問題的求解方法：設(shè)置虛擬產(chǎn)地或銷地以達到產(chǎn)銷平衡.例求下面運輸問題的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656則：，最小值為-6，非基變量為，閉回路，最大調(diào)整量為1，得新解：，重新計算位勢及影響系數(shù)，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656，最小值為-5，非基變量為，閉回路，最大調(diào)整為2，得新解：重新計算位勢及影響系數(shù)，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此時，，故當前解為最優(yōu)解。最優(yōu)解值為：。產(chǎn)銷不平衡的運輸問題：對產(chǎn)銷不平衡的運輸問題，求解的基本方法是設(shè)置虛擬變量，其單位運輸成本為0，從中求出最優(yōu)解。例：求下面運輸問題的最小運費解：12345121134072103590537812072346419例:求解運輸問題12341327650275236032545254MMMM1060402025145例：最短路問題：求下面從到的最短線路和最短距離：解：；所以：所以：,。例：設(shè)有某種肥料共6個單位，準備給4塊糧田用，其每塊糧田施肥數(shù)量與增產(chǎn)糧食的關(guān)系如下表所示。試求對每塊田施多少單位重量的肥料，才能使總的糧食增產(chǎn)最多。施肥糧田123412528245473676548774510680612885解：表1，對兩塊田的施肥：0123456收益田1田2120+00+252501242+020+250+454511360+042+2520+450+576721475+060+2542+4520+570+658722585+075+2560+4542+5720+650+7010532690+085+2575+4560+5742+6520+700+7312042表2，對三塊田的施肥：0123456收益123125+00+1825010245+025+180+3945110367+045+1825+390+6167210487+067+1845+3925+610+78872205105+087+1867+39