1、基本要求一、將線性規劃化為標準型和寫出相應的對偶規劃；二、用圖解法求解具有兩個決策變量的線性規劃問題；三、用單純形方法；四、整數規劃與分枝定界法，0-1規劃與隱枚舉法，指派問題六、求解產銷平衡的運輸問題和產銷不平衡的運輸問題；七、動態規劃與求解. 問題一、化標準型標準型的概念： 目標函數為極大化； 資源常數； 約束條件關系為等式； 決策變量。例： 將下面的線性規劃化為標準型 無非負限制解 二、圖解法 例 用圖解法求解線性規劃問題 極大化 解：最優解三、單純形方法 對于具有兩個以上決策變量的線性規劃問題，采用單純形方法進行求解。具體過程是： 建立單純形表，在單純形表中，務必使基變量的價值系數為零

2、，則檢驗數行是價值系數行的相反數； 若檢驗數則當前解為最優解（當前解是基變量取相應的資源常數，非基變量取為零）；若存在檢驗數，則要進行相應的換基，即：迭代； 進基：進基變量 ： 出基：出基變量為第行所對應的基變量，由下面的關系確定 以主元進行迭代，目標：主元化為1，該列的其余元化為零。 再一次判定當前解是否為最優解。 建立對偶規劃的要點 原規劃是極大化，則對偶規劃是極小化；原規劃的價值系數是對偶規劃中的資源常數； 原規劃與對偶規劃的約束條件系數矩陣為矩陣的轉置關系； 原規劃中的第個決策變量非正，則對偶規劃中的第個約束條件取反向不等式； 原規劃中的第個決策變量無非負限制，則對偶規劃中的第個約束條

3、件為等式. 例 求下面問題的對偶規劃極大化 無非負限制。 解 極小化 對偶單純形法 基本要求：檢驗數；資源常數存在負值。 解法：1 列出對偶單純形表；2 將基變量在目標函數中系數化為零，檢驗數為新目標函數中系數的相反數；3 判斷，若，則當前解為最優解； 若中存在負項，則進行迭代，確定出基和進基變量； 出基：記為第r行對應的變量； 進基：，為進基變量； 以為主元進行迭代。目標：將主元化為1，該列的其余元化為0。 例：用單純性方法求解下面線性規劃問題： 解 由單純形方法得即,原問題的最優解為例 用分枝定界法求解整數規劃用隱枚舉法求解0-1規劃解 增加過濾條件：，則原規劃改為解向量條件1條件2條件3

4、條件4函數值FFFTTTT5TTTFTFTFTTTT7TTTT9所以，最優方案為，最優值為.指派問題的求解：1.的指派問題的最小值解的求解方法：用行縮減和列縮減在每行和每列至少產生一個零；用劃線法判定是否有個獨立的零；如果有個獨立的零，則可以求出最小值解；若沒有個獨立的零，重新進行調整，以求出個獨立的零。2.的指派問題的最小值解的求解方法：設置虛擬變量，其價值系數取為零。3.指派問題中的最大值求解。例：求下面指派問題的最小值解： 解： 故最優解為：，最優解值為。例：求下面指派問題的最小值及最大值解：例：求下面指派問題的最大值解：運輸問題（產銷平衡）的求解方法：表上作業法1.用最小元素法求初始解

5、；2.用位勢法求出當前解所對應的位勢：若為基變量，則行位勢和列位勢滿足關系3.用位勢法計算非基變量的影響系數：若為非基變量，則影響系數與行位勢和列位勢滿足關系4.最優解的判定：若影響系數則當前解為最優解；否則通過解的調整求出最優解；5.解的調整：記：令為所對應的非基變量，以為當前變量，構造閉回路；在閉回路上確定最大調整量；求出新解6.重新判定當前解是否為最優解。產銷不平衡的運輸問題的求解方法：設置虛擬產地或銷地以達到產銷平衡.例 求下面運輸問題的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v1=2v2=9v3=3v4=101934u1=013

6、11310743u2=-121923431u3=-53741059633656則：，最小值為-6，非基變量為，閉回路，最大調整量為1，得新解：，重新計算位勢及影響系數，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656，最小值為-5，非基變量為，閉回路，最大調整為2，得新解：重新計算位勢及影響系數，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此時，故當前解為最優解。最優解值為：。產銷不平衡的運輸問題：對產銷不平衡

7、的運輸問題，求解的基本方法是設置虛擬變量，其單位運輸成本為0，從中求出最優解。例：求下面運輸問題的最小運費解：12345121134072103590537812072346419例: 求解運輸問題12341327650275236032545254MMMM1060402025145例：最短路問題：求下面從到的最短線路和最短距離：解：；所以：所以：,。例：設有某種肥料共6個單位，準備給4塊糧田用，其每塊糧田施肥數量與增產糧食的關系如下表所示。試求對每塊田施多少單位重量的肥料，才能使總的糧食增產最多。施 肥糧 田123412528245473676548774510680612885解：表1，對

8、兩塊田的施肥：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+3945+6125+780+901062126120+0