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