運籌學復習參考資料(已修改)
2025-04-29 12:13 本頁面
【正文】 第一部分 線性規(guī)劃問題的求解——重要算法：圖解法、單純形迭代、大M法單純形迭代、對偶問題、表上作業(yè)法（找初始可行解：西北角法，最小元素法；最優(yōu)性檢驗：閉回路法，位勢法；）、目標規(guī)劃：圖解法、整數規(guī)劃：分支定界法（次重點），匈牙利法（重點）、第二部分 動態(tài)規(guī)劃問題的求解——重要算法：圖上標號法第三部分 網絡分析問題的求解——重要算法：破圈法、TP標號法、尋求網絡最大流的標號法 第一部分 線性規(guī)劃問題的求解一、兩個變量的線性規(guī)劃問題的圖解法：㈠概念準備：定義：滿足所有約束條件的解為可行解；可行解的全體稱為可行（解）域。定義：達到目標的可行解為最優(yōu)解。㈡圖解法：圖解法采用直角坐標求解：x1——橫軸；x2——豎軸。將約束條件（取等號）用直線繪出；確定可行解域；繪出目標函數的圖形（等值線），確定它向最優(yōu)解的移動方向；注：求極大值沿價值系數向量的正向移動；求極小值沿價值系數向量的反向移動。確定最優(yōu)解及目標函數值。㈢參考例題：（只要求下面這些有唯一最優(yōu)解的類型）例1：某廠生產甲、乙兩種產品，這兩種產品均需在A、B、C三種不同的設備上加工，每種產品在不同設備上加工所需的工時不同，這些產品銷售后所能獲得利潤以及這三種加工設備因各種條件限制所能使用的有效加工總時數如下表所示：品產耗消備設 A B C利潤（萬元）甲乙3 5 99 5 37030有效總工時540 450 720——問：該廠應如何組織生產，即生產多少甲、乙產品使得該廠的總利潤為最大？（此題也可用“單純形法”或化“對偶問題”用大M法求解）解：設xx2為生產甲、乙產品的數量。 ⑴max z = 70x1+30x2 ⑵. ⑸、⑹ ⑷ ⑶可行解域為oabcd0，最優(yōu)解為b點。由方程組 解出x1=75，x2=15∴X*==（75，15）T∴max z =Z*= 7075+3015=5700例2：用圖解法求解 ⑴max z = 6x1+4x2 ⑵. ⑸、⑹ ⑷ ⑶可行解域為oabcd0，最優(yōu)解為b點。由方程組 解出x1=2，x2=6∴X*==（2，6）T∴max z = 62+46=36例3：用圖解法求解 ⑴min z =－3x1+x2. ⑵ ⑶ ⑷ ⑸ ⑹、⑺解：可行解域為bcdefb，最優(yōu)解為b點。由方程組 解出x1=4，x2=∴X*==（4，）T∴min z =－34+=－11 二、標準型線性規(guī)劃問題的單純形解法：㈠一般思路：用簡單易行的方法獲得初始基本可行解；對上述解進行檢驗，檢驗其是否為最優(yōu)解，若是，停止迭代，否則轉入3；根據θL規(guī)則確定改進解的方向；根據可能改進的方向進行迭代得到新的解；根據檢驗規(guī)則對新解進行檢驗，若是最優(yōu)解，則停止迭代，否則轉入3，直至最優(yōu)解。㈡具體做法（可化歸標準型的情況）：設已知max z = c1x1+ c2x2+…+ xn.對第i個方程加入松弛變量xn+i，i =1，2，…，m，得到列表計算，格式、算法如下：CBXBbc1c2…+mθLx1x2…xn+m+1xn+1b1a11a12…a1 n+mc n+2xn+2b2a21a22…a2 n+m.........…………+mxn+mbnam1am2…am n+mz1z2…zn+mσ1σ2…σn+m注①： zj =+1 a1j+ +2 a2j +…+ +m amj=，（j=1，2，…，n+m）σj =cj－zj ,當σj ≤0時，當前解最優(yōu)。注②：由max{σj}確定所對應的行的變量為“入基變量”；由θL=確定所對應的行的變量為“出基變量”，行、列交叉處為主元素，迭代時要求將主元素變?yōu)?，此列其余元素變?yōu)?。例1：用單純形法求解（本題即是本資料P2“圖解法”例1的單純形解法；也可化“對偶問題”求解）max z =70x1+30x2.解：加入松弛變量x3，x4，x5，得到等效的標準模型：max z =70x1+30x2+0 x3+0 x4+0 x5.列表計算如下：CBXBb7030000θLx1x2x3x4x50x354039100540/3 =1800x445055010450/5 =900x5720（9）3001720/9 =800000070↑300000x33000810 1/3300/8 =0x4500（10/3）01 5/950/10/3 =
教學教案相關推薦
鄂ICP備17016276號-1