運(yùn)籌學(xué)復(fù)習(xí)參考資料-在線瀏覽
2025-06-04 12:13本頁(yè)面
【正文】 下：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)。由方程組 解出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)。 ⑴max z = 70x1+30x2 ⑵. ⑸、⑹ ⑷ ⑶可行解域?yàn)閛abcd0，最優(yōu)解為b點(diǎn)。確定最優(yōu)解及目標(biāo)函數(shù)值。㈡圖解法：圖解法采用直角坐標(biāo)求解：x1——橫軸；x2——豎軸。第一部分 線性規(guī)劃問題的求解——重要算法：圖解法、單純形迭代、大M法單純形迭代、對(duì)偶問題、表上作業(yè)法（找初始可行解：西北角法，最小元素法；最優(yōu)性檢驗(yàn)：閉回路法，位勢(shì)法；）、目標(biāo)規(guī)劃：圖解法、整數(shù)規(guī)劃：分支定界法（次重點(diǎn)），匈牙利法（重點(diǎn)）、第二部分 動(dòng)態(tài)規(guī)劃問題的求解——重要算法：圖上標(biāo)號(hào)法第三部分 網(wǎng)絡(luò)分析問題的求解——重要算法：破圈法、TP標(biāo)號(hào)法、尋求網(wǎng)絡(luò)最大流的標(biāo)號(hào)法 第一部分 線性規(guī)劃問題的求解一、兩個(gè)變量的線性規(guī)劃問題的圖解法：㈠概念準(zhǔn)備：定義：滿足所有約束條件的解為可行解；可行解的全體稱為可行（解）域。定義：達(dá)到目標(biāo)的可行解為最優(yōu)解。將約束條件（取等號(hào)）用直線繪出；確定可行解域；繪出目標(biāo)函數(shù)的圖形（等值線），確定它向最優(yōu)解的移動(dòng)方向；注：求極大值沿價(jià)值系數(shù)向量的正向移動(dòng)；求極小值沿價(jià)值系數(shù)向量的反向移動(dòng)。㈢參考例題：（只要求下面這些有唯一最優(yōu)解的類型）例1：某廠生產(chǎn)甲、乙兩種產(chǎn)品，這兩種產(chǎn)品均需在A、B、C三種不同的設(shè)備上加工，每種產(chǎn)品在不同設(shè)備上加工所需的工時(shí)不同，這些產(chǎn)品銷售后所能獲得利潤(rùn)以及這三種加工設(shè)備因各種條件限制所能使用的有效加工總時(shí)數(shù)如下表所示：品產(chǎn)耗消備設(shè) A B C利潤(rùn)（萬(wàn)元）甲乙3 5 99 5 37030有效總工時(shí)540 450 720——問：該廠應(yīng)如何組織生產(chǎn)，即生產(chǎn)多少甲、乙產(chǎn)品使得該廠的總利潤(rùn)為最大？（此題也可用“單純形法”或化“對(duì)偶問題”用大M法求解）解：設(shè)xx2為生產(chǎn)甲、乙產(chǎn)品的數(shù)量。由方程組 解出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=4，x2=∴X*==（4，）T∴min z =－34+=－11 二、標(biāo)準(zhǔn)型線性規(guī)劃問題的單純形解法：㈠一般思路：用簡(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)解。注②：由max{σj}確定所對(duì)應(yīng)的行的變量為“入基變量”；由θL=確定所對(duì)應(yīng)的行的變量為“出基變量”，行、列交叉處為主元素，迭代時(shí)要求將主元素變?yōu)?，此列其余元素變?yōu)?。我們?cè)谇懊鏄?biāo)準(zhǔn)型中是規(guī)定目標(biāo)函數(shù)求極大值。可作如下處理：由目標(biāo)函數(shù)min z=變成等價(jià)的目標(biāo)函數(shù)max（－z）=令－z=z/，∴min z=－max z/等式約束——大M法：通過加人工變量的方法，構(gòu)造人造基，從而產(chǎn)生初始可行基。（課本P29）類型一：目標(biāo)函數(shù)仍為max z，約束條件組≤與＝。例2：用單純形法求解min z =4x1+3x2.解：減去松弛變量x3，x4，并化為等效的標(biāo)準(zhǔn)模型：max z/ =－4x1－3x2.增加人工變量xx6，得到：max z/ =－4x1－3x2－Mx5－Mx6單純形表求解過程如下：CBXBb－400－M－MθLx1x2x3x4x5x6－Mx5162（4）－101016/4=4－Mx612320－10112/2=6－5M－6MMM－M－M5M－46M－3↑－M－M00－3x241/21－1/401/404/1/2=8－Mx64
教學(xué)教案相關(guān)推薦
鄂ICP備17016276號(hào)-1