數(shù)學(xué)規(guī)劃ch4線

1、第四章 運籌與優(yōu)化模型 4.1 線性規(guī)劃模型 4.2 非線性規(guī)劃模型 4.3 動態(tài)規(guī)劃模型 4.4 變分法模型 4.5 層次分析法模型1 數(shù)學(xué)規(guī)劃2規(guī)劃模型（1）效益最大化或費用最小化（2）各種條件約束3 數(shù)學(xué)規(guī)劃許多實際問題都可以歸結(jié)為以下形式的 數(shù)學(xué)模型：44.1 線性規(guī)劃模型5 例1 某機床廠生產(chǎn)甲、乙兩種機床，每臺銷售后的利潤分別為4000 元與3000 元。生產(chǎn)甲機床需用A、B 機器加工，加工時間分別為每臺2 小時和1 小時；生產(chǎn)乙機床需用A、B、C 三種機器加工，加工時間為每臺各一小時。若每天可用于加工的機器時數(shù)分別為A 機器10 小時、B 機器8 小時和C 機器7 小時，問該廠每

2、天應(yīng)生產(chǎn)甲、乙機床各幾臺，才能使總利潤最大？線性規(guī)劃引例6 設(shè)該廠生產(chǎn) 臺甲機床和 臺乙機床時總利潤最大，則 應(yīng)滿足 （目標(biāo)函數(shù)） (約束條件)數(shù)學(xué)模型：7線性規(guī)劃(linear Programming)模型目標(biāo)函數(shù)約束條件決策變量8 1、有關(guān)線性規(guī)劃問題的幾個例子 2、線性規(guī)劃問題的標(biāo)準(zhǔn)形式 3、關(guān)于整數(shù)規(guī)劃 4、應(yīng)用本節(jié)內(nèi)容91.線性規(guī)劃問題的幾個例子 某化工廠生產(chǎn)A1，A2，A3，A4四種化工產(chǎn)品，每種產(chǎn)品生產(chǎn)1噸消耗的工時、能源和獲得的利潤如下表：產(chǎn)品A1A2A3A4工時(h)10025038075能源(噸標(biāo)準(zhǔn)煤)0.20.30.50.1利潤(萬元)2581 已知該廠明年的工時限額為1

3、8480h，能耗限額為100t標(biāo)準(zhǔn)煤，欲使該廠明年的總利潤最高，請確定各種產(chǎn)品的生產(chǎn)數(shù)量。10模型產(chǎn)品A1A2A3A4生產(chǎn)數(shù)量x 1x 2x 3x 4假設(shè)：工時限制供煤限制11例 某商品有m 個產(chǎn)地、n 個銷地，各產(chǎn)地的產(chǎn)量分別為 各銷地的需求量分別為 。若該商品由i 產(chǎn)地運到 j 銷地的單位運價為 ，問應(yīng)該如何調(diào)運才能使總運費最??？運輸問題(產(chǎn)銷平衡)12解：引入變量 ，其取值為由i 產(chǎn)地運往 j 銷地的該商品數(shù)量，數(shù)學(xué)模型為13運輸問題(產(chǎn)銷不平衡)上例中，若產(chǎn)大于銷，即 時, 運輸模型可寫為 14河流污染與凈化問題 某河流邊有兩個化工廠, 流經(jīng)第一個化工廠的河水流量是每天500萬立方米,

4、 在兩個工廠之間有一條流量為每天200萬立方米的支流. 兩個化工廠每天排放工業(yè)污水分別為2萬與1.4萬立方米, 從第一個化工廠排出的污水流到第二個化工廠之前, 有20可自然凈化. 根據(jù)環(huán)保部門的要求,河流中工業(yè)污水的含量應(yīng)不大于0.2 . 因此兩個化工廠都必須各自處理凈化一部分污水,已知他們治污成本分別為0.1元和0.08元每立方米。問在滿足環(huán)保要求的條件下，兩廠各需要處理多少污水，可使兩廠總的處理污水費用最少。15分析: (1) 假設(shè)第一、二廠每天各自處理x1和x2萬立方米的污水; (2) 根據(jù)環(huán)保部門的要求，應(yīng)有 同時應(yīng)有 16 (3) 記 f 為兩廠治污的總費用,則有從而該問題的數(shù)學(xué)模型

5、為172. 線性規(guī)劃問題的標(biāo)準(zhǔn)形式若寫成向量和矩陣形式, 則有 18求解方法：（1）單純形法 （2）軟件求解:Lindo， matlab，Lingo等 其中 注: 任何線性規(guī)劃模型都可以化為標(biāo)準(zhǔn)形式. 19實例 將以下LP問題化為標(biāo)準(zhǔn)型:20解 令得標(biāo)準(zhǔn)型為松弛變量剩余變量21線性規(guī)劃的Matlab 標(biāo)準(zhǔn)形式其中c 和x 為n 維列向量， A 、Aeq 為適當(dāng)維數(shù)的矩陣， b 、beq 為適當(dāng)維數(shù)的列向量。22Matlabx,fval=linprog(c,A,b,Aeq,beq,LB,UB,X0,OPTIONS)fval 返回目標(biāo)函數(shù)的值，LB 和UB 分別是變量x 的下界和上界， x0 是x

6、 的初始值，OPTIONS 是控制參數(shù)。23Matlab（i）編寫M 文件c=2; 3; -5;a=-2,5,-1;1,3,1; b=-10;12;aeq=1,1,1;beq=7;x=linprog(-c,a,b,aeq,beq,zeros(3,1)value=c*x （ii）將M文件存盤，并命名為example1.m。 （iii）在Matlab指令窗運行example1即可得所求結(jié)果。x = 6.4286 0.5714 0.0000value = 14.5714求最大值24 編寫Matlab程序如下：c=2;3;1;a=1,4,2;3,2,0;b=8;6;x,y=linprog(c,-a,-

7、b,zeros(3,1)25LP問題的圖解法(僅適用二維問題)實例 用圖解法求解以下LP問題:26解:最優(yōu)解為(4,4/3)最優(yōu)目標(biāo)值為44/3273.整數(shù)規(guī)劃(Integer Linear Programming)模型28 有一個徒步旅行者，其可攜帶物品重量的限度為a 公斤，設(shè)有n 種物品可供他選擇裝入包中。已知每種物品的重量及價值（元），問此人應(yīng)如何選擇攜帶的物品（各幾件），使所帶物品價值最大？物品 1 2 j n重量（公斤/件） a1 a2 aj an每件價值 c1 c2 cj cn 這就是背包問題。類似的還有工廠里的下料問題、運輸中的貨物裝載問題、人造衛(wèi)星內(nèi)的物品裝載問題等。背包問題2

8、9設(shè)xj 為第j 種物品的裝件數(shù)（非負(fù)整數(shù)）則問題的數(shù)學(xué)模型如下：30LP問題的Lindo輸入范例ST2) 3) 4) END31ST2) 3) 4) ENDGIN2 (!表示前兩個變量為一般整數(shù))ILP問題的Lindo輸入范例之一32ST2) 3) 4) ENDGIN(X1);GIN(X2);ILP問題的Lingo輸入范例33例：運輸問題(產(chǎn)銷不平衡) 設(shè)有三個化肥廠供應(yīng)四個地區(qū)的農(nóng)用化肥. 各化肥廠產(chǎn)量(單位：萬噸), 各地區(qū)年需求量(單位：萬噸)及從各化肥廠到各地區(qū)的單位運價(單位：萬元/萬噸)如表所示，試建立使總運費最省的化肥調(diào)撥方案.表4.1.434 地 區(qū)化 肥 廠 I I II

9、III IV IV產(chǎn) 量ABCD 16 16 13 22 17 17 14 14 13 19 15 15 19 19 20 23 M M M 0 M 0 M 050605050需求 30 20 70 30 10 50 210模型的建立與求解 設(shè) 表示第i個化肥廠運到各地區(qū)的滿足最低需求部分， 表示第i個化肥廠運到各地區(qū)的滿足最高需求的部分，則調(diào)運方案數(shù)學(xué)模型為35例：綜合運輸問題的0-1規(guī)劃模型 設(shè)某種物質(zhì)有 m 個產(chǎn)地 第 i 個產(chǎn)地的產(chǎn)量為 該物資將銷往 n 個銷地 第 j 個銷地的銷量為 且有 已知從各個產(chǎn)地運往各銷地需經(jīng)過 p 個中間編組站 轉(zhuǎn)運, 若啟用第 k 個編組站，不管轉(zhuǎn)運量多

10、少，均發(fā)生固定費用 且第 k 個中間編組站轉(zhuǎn)運的最大容量限制為 用 和 分別表示從 到 和從 到 的單位物質(zhì)的運輸費用，試建立使總運費為最小的該種物資的調(diào)運方案的數(shù)學(xué)模型。 36 分析 從產(chǎn)地到中轉(zhuǎn)站和從中轉(zhuǎn)站到銷地，均為運輸問題，關(guān)鍵是各中轉(zhuǎn)站是否啟用，用哪幾個。對于中轉(zhuǎn)站而言，具有用與不用兩種狀態(tài)，故可以考慮引入0-1變量來處理。 模型建立和求解 設(shè) 表示從產(chǎn)地 運至中轉(zhuǎn)站 的物資的數(shù)量， 表示從中轉(zhuǎn)站運至銷地 的物資數(shù)量，記37 周一 18人 周二 15人 周三 12人 周四 16人 周五 19人 周六 14人 周日 12人例 某百貨商場每周內(nèi)至少需要售貨員人數(shù)如下：規(guī)定每個員工每周連續(xù)

11、工作五天，休息兩天。求總員工數(shù)最少的排班方案。38ILP問題的圖解法(僅適用二維問題)實例 用圖解法求解以下ILP問題:39解:對應(yīng)LP問題最優(yōu)解為(4,4/3),不是ILP問題的可行解ILP問題的最優(yōu)解為X*=(4,1),最優(yōu)目標(biāo)值為 z*=14,可行域頂點可以是非可行解40投資的效益和風(fēng)險(1998年全國大學(xué)生數(shù)學(xué)建模競賽A題)41原題還有一組 n=25的數(shù)據(jù)，現(xiàn)略去。42問題分析優(yōu)化問題決策每種資產(chǎn)的投資額（投資組合）目標(biāo)凈收益最大整體風(fēng)險最小 在一定風(fēng)險下收益最大的決策 在一定收益下風(fēng)險最小的決策 收益和風(fēng)險按一定比例組合最優(yōu)的決策一組解(如在一系列風(fēng)險值下收益最大的決策)二者矛盾 冒

12、險型投資者從中選擇高風(fēng)險下收益最大的決策 保守型投資者則可從低風(fēng)險下的決策中選取43模型建立用數(shù)學(xué)符號和式子表述決策變量、構(gòu)造目標(biāo)函數(shù)、確定約束條件。xi對Si(i=0,1,n)的投資, x0表示存入銀行.目標(biāo)函數(shù) 總收益投資Si的收益減去交易費，對i求和 總體風(fēng)險投資Si的風(fēng)險，對i求最大值對Si的投資xi加交易費ci(xi)，對i求和，不超過給定資金M.決策變量約束條件440uixicipiui1）投資Si的交易費、凈收益、風(fēng)險、資金表達式交易費凈收益(收益率ri)風(fēng)險資金(風(fēng)險損失率qi)452）投資方案、總收益、總體風(fēng)險、資金表達式投資方案總收益總體風(fēng)險資金3）兩目標(biāo)（總收益、總體風(fēng)險

13、）優(yōu)化模型464）單目標(biāo)優(yōu)化模型47模型簡化交易費ui很小M很大資金約束設(shè)M=1投資Si的比例48設(shè)M=1線性規(guī)劃模型LP1模型M1的簡化M149模型M2的簡化M2極大極小規(guī)劃模型線性規(guī)劃模型LP2引入人工變量 xn+150模型M3的簡化M3線性規(guī)劃模型LP3模型求解LP1,LP2,LP3都很容易用MATLAB, MATHEMATICA或其它數(shù)學(xué)軟件求解51線性規(guī)劃模型LP152模型一的求解535455LP1的結(jié)果風(fēng)險水平取k=02.5%, 得投資比例y0y456LP1的結(jié)果57LP3的結(jié)果與LP1相同58實例 某廠生產(chǎn)A,B, C三種產(chǎn)品,每種產(chǎn)品的單位利潤分別為12,18和15,資源消耗和

14、資源總數(shù)量如下表,求總利潤最大的生產(chǎn)方案. A B C 限制 原料1/單位產(chǎn)品 6 9 5 200 原料2/單位產(chǎn)品 12 16 17 360 人工/單位產(chǎn)品 25 20 12 78059解:設(shè)生產(chǎn)A,B,C分別為x1,x2,x3個單位,數(shù)學(xué)模型為:60整數(shù)規(guī)劃的計算方法分枝定界法主要思路 1.分枝 把全部可行解空間反復(fù)地分割為越來越小的子集； 2.定界對每個子集內(nèi)的解集計算一個目標(biāo)下界（對于最小值問題）； 3.剪枝在每次分枝后，凡是界限超出已知可行解集目標(biāo)值的那些子集不再進一步分枝，這樣，許多子集可不予考慮61 設(shè)有最大化的整數(shù)規(guī)劃問題A ，與它相應(yīng)的線性規(guī)劃為問題B ，從解問題B 開始，若

15、其最優(yōu)解不符合A 的整數(shù)條件，那么B 的最優(yōu)目標(biāo)函數(shù)必是A 的最優(yōu)目標(biāo)函數(shù)z* 的上界，記作 ；而A 的任意可行解的目標(biāo)函數(shù)值將是z* 的一個下界 。分枝定界法就是將B 的可行域分成子區(qū)域的方法。逐步減小 和增大 ，最終求到z*.62 例 求解下述整數(shù)規(guī)劃解 （i）先不考慮整數(shù)限制，即解相應(yīng)的線性規(guī)劃B ，得最優(yōu)解為：此時 取 63（ii）因為 當(dāng)前均為非整數(shù)，故不滿足整數(shù)要求，任選一個進行分枝。設(shè)選 進行分枝，把可行集分成2 個子集：這兩個子集的規(guī)劃及求解如下：問題B1 問題B264（iii）對問題 再進行分枝得問題 和 ,它們的最優(yōu)解為再定界： 340 z* 349，并將 剪枝。（iv）對

16、問題 再進行分枝得問題 和 ，它們的最優(yōu)解為將 于是可以斷定原問題的最優(yōu)解為：65例 某?；@球隊準(zhǔn)備從以下隊員中選拔3名為正式隊員，并使平均身高盡可能高，這6名預(yù)備隊員情況如下表所示。預(yù)備隊員 號碼 身高 位置 大張 1 193 中鋒 大李 2 191 中鋒 小王 3 187 前衛(wèi) 小趙 4 186 前衛(wèi) 小田 5 180 后衛(wèi) 小周 6 185 后衛(wèi)66 隊員的挑選要滿足下列條件：至少補充一名后衛(wèi)(5、6)隊員；大李(2號)或小田(5號)中間只能入選一名；最多補充一名中鋒(1、2)；若大李(2)或小趙(4)入選，小周(6)就不能入選。 試建立此問題的數(shù)學(xué)模型。解:則該問題的數(shù)學(xué)模型為:67上

17、述形式的數(shù)學(xué)規(guī)劃模型稱為(0-1)規(guī)劃 隊員的挑選要滿足下列條件：至少補充一名后衛(wèi)(5、6)隊員；大李(2號)或小田(5號)中間只能入選一名；最多補充一名中鋒(1、2)；若大李(2)或小趙(4)入選，小周(6)就不能入選。 試建立此問題的數(shù)學(xué)模型。68 0-1規(guī)劃 一個公司有22億元資金用來投資，現(xiàn)有6個項目可供選擇，各項目所需投資金額和預(yù)計年收益如下表所示：項目123456投資526468收益0.50.40.60.50.91 應(yīng)選擇哪幾個項目投資收益最大？69指派問題 0-1規(guī)劃問題：70 上述指派問題的可行解可以用一個矩陣表示，其每行每列均有且只有一個元素為1，其余元素均為0。 問題中的變

18、量只能取0 或1，從而是一個0-1 規(guī)劃問題。一般的0-1 規(guī)劃問題求解極為困難。但指派問題并不難解，其約束方程組的系數(shù)矩陣十分特殊（被稱為全單位模矩陣，其各階非零子式均為 1），其非負(fù)可行解的分量只能取0 或1，故約束 或 可改寫為 而不改變其解。此時，指派問題被轉(zhuǎn)化為一個特殊的運輸問題，其中m = n ， 。71指派問題的計算機解法7273解指派問題的匈牙利算法74五、網(wǎng)絡(luò)問題問題： 右圖是一公路交通圖，弧上數(shù)字為路程，求汽車從（1）到（7）最短路。75模型：76問題變形最大流問題上圖77問題變形最小費用流問題上圖78六、問題應(yīng)用鋼管下料問題：某鋼管零售商從鋼管廠進貨，將鋼管按顧客 的要求

19、切割后售出，從鋼管廠進貨時得到的 原料鋼管都是19m。（1）現(xiàn)有一客戶需要50根4m、20根6m和15根8m 的鋼管，應(yīng)如何下料最省。79問題(1)分析： 首先，應(yīng)當(dāng)確定哪些切割模式是可行的。所謂一個切割模式，是指按照客戶需要在原料鋼管上安排切割的一種組合。顯然，可行的切割模式是很多的。 其次，應(yīng)當(dāng)確定哪些切割模式是合理的。通常假設(shè)一個合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸。例如，將19m 長的鋼管切割成3 根4m的鋼管是可行的，但余料為7m，可以進一步將7m 的余料切割成4m 鋼管（余料為3m），或者將7m 的余料切割成6m 鋼管（余料為1m）。在這種合理性假設(shè)下，切割

20、模式一共有7 種，如表3 所示。80問題（1）解答鋼管下料合理切割模式：問題：按何種切割模式，切割多少根原鋼管，最為節(jié)省。節(jié)?。?1）余料最少 2）原鋼管總數(shù)最少81模型設(shè)x i表示照第i種模式切割原材料鋼管的根數(shù)總余料最小 原鋼管條數(shù)最少82求解 運用Lingo軟件對上述整數(shù)規(guī)劃問題分別求解. 對第一個目標(biāo)模型，求得:按照模式2 切割12 根原料鋼管，按照模式5 切割15 根原料鋼管，共27 根，總余料量為27m。但4m 長的鋼管比要求多切割了1 根，6m 長的鋼管比要求多切割了7 根。顯然，在總余料量最小的目標(biāo)下，最優(yōu)解將是使用余料盡可能小的切割方式（模式2 和模式5 的余料為1m），這會

21、導(dǎo)致切割原料鋼管的總根數(shù)較多。83 對第二個目標(biāo)模型，求得: 按照模式2 切割15 根原料鋼管，按模式5 切割5 根，按模式7 切割5 根，共25 根，可算出總余料量為35m。但各長度的鋼管數(shù)恰好全部滿足要求，沒有多切割。與上面得到的結(jié)果比較，總余料量增加了8m，但是所用的原料鋼管的總根數(shù)減少了2根。在余料沒有什么用途的情況下，通常選擇總根數(shù)最少為目標(biāo)。84（2）零售商如果采用的不同切割模式太多，將會導(dǎo)致生產(chǎn)過程的復(fù)雜化，從而增加生產(chǎn)和管理成本，所以該零售商規(guī)定只能采用3種不同的切割模式。此外，該客戶除需要（1） 中的三種鋼管外，還需要10根5m的鋼管，應(yīng)如何下料最省。85問題（2）解答問題分

22、析： 按照問題（1）的思路，可以通過枚舉法首先確定哪些切割模式是可行的。但由于需要的鋼管規(guī)格增加到4 種，所以枚舉法的工作量較大。 一合理的切割模式的余料不應(yīng)該大于或等于客戶需要的鋼管的最小尺寸，故本題中合理的切割模式的余量不能大于3m。這里，僅選擇總根數(shù)最少為目標(biāo)進行求解。86模型建立設(shè)x i表示照第i種模式切割原材料鋼管的根數(shù)（i=1,2,3）r ji分別表示在第i種切割模式下一根原鋼管生產(chǎn)第j種(j=1,2,3,4 分別對應(yīng)長度是4,5,6,8米的鋼管)鋼管數(shù)量(滿足4米鋼管數(shù)需求)(滿足5米鋼管數(shù)需求)(滿足6米鋼管數(shù)需求)(滿足8米鋼管數(shù)需求)(第i種模式所得鋼管 總長度, i=1,

23、2,3)87七、應(yīng)用（AMCM-88B） 將七種不同規(guī)格的包裝箱裝到兩輛鐵路平板車上，各包裝箱寬、高均相等，但厚度t(厘米)與重量w(公斤)不同。每平板車有10.2米長的地方用來裝包裝箱，載重40噸。由于貨運限制，對c5、c6、c7類包裝箱總數(shù)有限定：總厚度不超過302.7(厘米)。試把箱子裝到平板車并使空間浪費最小。88八、應(yīng)用（AMCM-89B） 機場通常按“先來先走”的原則來分配飛機跑道，即當(dāng)飛機準(zhǔn)備好離開登機口時，駕駛員電告地面控制中心，加入等候跑道的隊伍。假設(shè)控制中心可以從快速聯(lián)機數(shù)據(jù)庫中得到每架飛機如下信息： 1、預(yù)定離開登機口的時間 2、實際離開登機口的時間 3、機上乘客人數(shù) 4、預(yù)定在下一站轉(zhuǎn)機的人數(shù)和時間 5、到達下一站的預(yù)定時間。 又設(shè)飛機共有七種型號，載客量從100人起以50人遞增，載客最多達400人。 試開發(fā)和分析一種能使乘客和航空公司雙方滿意的數(shù)學(xué)