運籌學(xué)教案(胡運權(quán)版)

3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹立愛崗精神【教學(xué)流程圖】{【教學(xué)方法】【教學(xué)內(nèi)容】（一）舉例引入5分鐘）定義：運籌學(xué)（OperationResearch）是運用系統(tǒng)化的方法，通過建力、財力等籌劃和管理方面的問題。2.能力目標(biāo)：掌握線性規(guī)劃建模的標(biāo)準(zhǔn)形式及將普通模型化為標(biāo)準(zhǔn)模型的3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹立愛崗精神【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】506222甲乙AxxBxxCxxij如果規(guī)劃問題的數(shù)學(xué)模型中，決策變量的取值是連續(xù)的整數(shù)、小策變量的線性等式或不等式，則稱這種規(guī)劃問題為線性規(guī)劃。jx'和x''，令x=x'-x''；jjjjji-x''2-x)-x4-x''-x''{{【教學(xué)流程圖】{【教學(xué)方法】【教學(xué)內(nèi)容】（一）舉例引入5分鐘）教師演示并總結(jié)如下：圖解法適用于兩個決策變量的線性規(guī)劃非滿足約束條件的不等號及該已知點的位置來判斷它所在的解xx2x基變量——利用矩陣的初等變換從約束條件的m×n(n>m)階系數(shù)矩【教學(xué)流程圖】{單【教學(xué)方法】【教學(xué)內(nèi)容】（二）舉例引入5分鐘）基變量——利用矩陣的初等變換從約束條件的m×n(n>m)階系數(shù)矩4、按最小比值原則，用常數(shù)列各數(shù)除以主元列相對應(yīng)的正商量對應(yīng)的常數(shù)列為最優(yōu)解，代入目標(biāo)函數(shù)得最優(yōu)目標(biāo)函數(shù)例1-62522j1034150j2jxxZλ52000012000000000000000xxx453代代x3x15Zjλjx3x1x2Zjλj41【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】（三）舉例引入5分鐘）{{j2xj146jj4x1M2初1271001Zλ0M5x4MM000xxxxZ j56321jjxxZλj6y21y3對s.t.{jyj12y3y4y5y6y7初y67λjy2←y←7λjy2y1λj21jy210300y400yyyj52j23jyyλTij212321【教學(xué)流程圖】性規(guī)劃的對偶問題的基本概念對偶問題與原問題{性規(guī)劃的對偶問題的基本概念對偶問題與原問題【教學(xué)方法】【教學(xué)內(nèi)容】（一）舉例引入對偶問題的基本概念5分鐘）第二章線性規(guī)劃的對偶理論與靈敏度分析506222現(xiàn)從另一角度提出問題：假定有某個公司想把美佳公司的資源收買過來，2第i個變量為“≥0”第i個變量為“≤0”第i個約束條件為“≥”第i個約束條件為“=”第i個變量為“≥0”第i個變量為“≤0”第i個約束條件為“≤”第i個約束條件為“=”例1-6和例1-8分別用單純形法和兩階段法可求得上述例題的原問題和其j3xjjyyx3x4x5y4決策變量基變量xx0000yyyyλj2253jT。jsjx4x5λjx116x20x3241x4100x5010b24xx11101x50313λj010x110401x20162λj00y3y4y5y1y2yy545,由上性質(zhì)，有【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】（二）舉例引入影子價格的基本概念5分鐘）第二章線性規(guī)劃的對偶理論與靈敏度分析Σii*i*i對偶單純形法與原問題單純形法【教學(xué)流程圖】性規(guī)劃的對偶問題的基本概念對偶問題與原問題{性規(guī)劃的對偶問題的基本概念對偶問題與原問題【教學(xué)方法】【教學(xué)內(nèi)容】（三）舉例引入對偶問題的基本概念5分鐘）ijij某個λ>0jijyyiiyy1y1y1yjy基變量0100001100003010001000j第一代y14y500001002決策變量100000000yyyyyλλyZZjjjj445523312代jj1y5Zλyyjjjjjλmin{ija'min{iija'jijj2.能力目標(biāo)：分析C的變化；分析b的變化；增加一個變量x的jjjjj3、增加一個變量x的分析。j2、增加一個變量x的分析。jjjj【教學(xué)流程圖】{{jj增加一個變量x的分析j【教學(xué)方法】【教學(xué)內(nèi)容】（四）舉例引入對偶問題的基本概念5分鐘）{X≥0解32101403303300=1=-------------------------------------------------------------------------------------------------------------------------------------=100010001120j345jjx30001x12100代x21010Zj210λj000xZλ基變量初決策變量000xCBXBCNXNBB1BNB1NbNNBjjj基變量代代x1x2λjx4x1x20202決策變量λ2j312λ代00000000001xxxxxλj45解14141一3223i080100,設(shè)最優(yōu)表中的常數(shù)列為b'，那么其增量為：080=2j決策變量基變量10x531j35124j01001051代代x2λxxx00000000000000xx0j【教學(xué)流程圖】{與運量【教學(xué)方法】【教學(xué)內(nèi)容】：（2、約束條件系數(shù)矩陣的每一列有兩個元素，這對應(yīng)于每一個元素3、對于產(chǎn)銷平衡運輸問題，所有約束條件都有是等式約束，各產(chǎn)2.能力目標(biāo)：掌握運輸問題的建模和表上作業(yè)求解法；掌握解的最優(yōu)性檢驗法中的閉回路法和位勢法的計算步驟。【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】（二）舉例引入運輸問題的基本概念5分鐘）1x96xAAAxxxxxxxxxBBBB4483x542233ijx11x11x11x11x11x11xxxxx11111xxxxx111ji？）空格閉回路指在一個封閉的直角回路的若干角點處，除最后得x所在空格的檢驗數(shù)λ。ijijijijij1ijijijijijijijlkijijlk運量，奇點處減調(diào)運量”的方法，重新安排空格閉回路上轉(zhuǎn)角點的調(diào)運量。ij器整后的方案仍為最優(yōu)，不過目標(biāo)函數(shù)值不會有所改善，稱之為多解。BB46×9×86×8AAABBB4483522334×98638AAABBBB4485362232.能力目標(biāo)：掌握運輸問題的建模和表上作業(yè)求解法；掌握解的最優(yōu)性檢驗法中的閉回路法和位勢法的計算步驟。【教學(xué)流程圖】{【教學(xué)方法】【教學(xué)內(nèi)容】：（A1A2A377500A10A20A33×5××3×7×BBBBB4444987753364023解方法：這是一個產(chǎn)地A和A的產(chǎn)量有上下限的運輸問題，先求出A的444A15A22A3123BBB44336623MA‘10A1MA2MA30A’324××5×42××73×3×02BBBB444753333336643574324××5×42×1A3×3×3A’3AABB3622C1DF×2×A085332C1DF×2×1A85332C0D12F×811A5333.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹立愛崗精神【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】-設(shè)d---g(x)不超過E；（為偽意味著要求g(x)與E無關(guān)，超過值越大越好，相當(dāng)于求相當(dāng)于求ming(x)。__d+__d+_ⅠⅡ21129++一一xx2B1FEd3G2OxC3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹立愛崗精神2.掌握目標(biāo)規(guī)劃的目標(biāo)規(guī)劃的單純形法與普通單純形求解方法的區(qū)【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】（一）復(fù)習(xí)舊課5分鐘）P3d0302100dd+2PP2xd+1P3d0302100dd+2PP2xd+1d320xBx3d1d2d3λjCjCBP2P3P1P2P3012118x3d1x26Pd33Pd33λP1λPj1j1P1PP253x3d-1x2x1λj111P1P213242P3x3d+3x2x1λj1P1121611121jjjjkjk1j1j2j1、化為標(biāo)準(zhǔn)型：取第一個約束中加上松弛變量x，取x、d、d、d為23.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹立愛崗精神【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】}-}-〈x-2x-d+1--d+--d+--d+--解目標(biāo)函數(shù)的變化僅影響原解的最優(yōu)性，即各變量的檢驗數(shù)。因此，應(yīng)當(dāng)先考察檢驗數(shù)的變化，然后再作適當(dāng)?shù)奶幚?。?—6000pp0pd-d+43x1d+1d-4x23234jBc-zjj00pB1．當(dāng)目標(biāo)函數(shù)變（i就是要了解交換第三和第四優(yōu)先級目標(biāo)對原解的影響。此時，單純形表變?yōu)楸?—7表4—70xd+1d-1ppXx0BBj2331422340000001110000101000000030000000000000000000000000000310pdxx4jj+CB0040jjb53234p311001p1d1cjXBx1d2d4x20x2000100000x100000002．當(dāng)目標(biāo)函數(shù)變（ii就是要了解第三優(yōu)先級中兩目標(biāo)權(quán)系數(shù)取值對原解的影響。1d30300W1-W2/403000W2001-W21100W2000000000100100000000000000000000000000004234110P241ppddddXxxxx000BB4jjj2422231.知識目標(biāo)：掌握整數(shù)規(guī)劃的概念、類型和作用及其求解方法概述；掌握3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹立愛崗精神《整數(shù)規(guī)劃：定義、類型、求解綜述和分支定界法》【教學(xué)流程圖】-------------------------------------------------------------------------------------------------------------------------------------【教學(xué)方法】【教學(xué)內(nèi)容】（二）舉例引入整數(shù)規(guī)劃5分鐘）第五章整數(shù)規(guī)劃第一節(jié)整數(shù)規(guī)劃的數(shù)學(xué)模型及解的特點第三節(jié)分支定界法對于最大化問題：Z=Z<Z*<Z=Z；對于最小化問題：Z=Z<Z*<Z=Z。jxx2x第一步：用圖解法求出原整數(shù)規(guī)劃問題的松馳問題的解。對x=4.81按11和x51進(jìn)行分支，得到原整數(shù)規(guī)劃問題的松馳問題的兩個子松馳問題如下。然后對原整數(shù)規(guī)兩個子問題由原問題的松馳問題分別加上分支的兩個約束條件組成，再用圖1j和1jxx2x45第二步：根據(jù)對節(jié)點分支的三種情況：剪支、停題進(jìn)行繼續(xù)分支。又分別得到兩個子問題。如此第三步：最后如果得到一個整數(shù)解，即為最優(yōu)整1120- j-------------------------------------------------------------------------------------------------------------------------------------11j2j11j- 2j-2j2j*-3.素質(zhì)目標(biāo)：培養(yǎng)學(xué)生良好的職業(yè)道德、樹立愛崗精神【教學(xué)流程圖】【教學(xué)方法】【教學(xué)內(nèi)容】（三）舉例引入整數(shù)規(guī)劃5分鐘）若X(0)不全為整數(shù)，則設(shè)法給松弛問題增加一個線性約束條件（叫割平面1整數(shù)向量，則計算結(jié)束，否則對P再增加一個割約束，形成問題P， ，例1用割平面法求解純整數(shù)規(guī)劃ILP：jx21j0000xx0xxxλ4234將上式左邊的非基變量的系數(shù)和右端常數(shù)寫4因x,x為整數(shù)，原整數(shù)規(guī)劃ILP約束條件中各系數(shù)和右端常數(shù)也為整4441-4j5決策變量基變量Cj1x11x2215j2jj00xxxλ000000010)=00000000xxx30例1有一項說明書要由漢語分別譯成英、日、德、俄四種文字，交由甲、乙、丙、丁14ij1{0ijij33 4ijijij344978902040502070315044405第二步試求最優(yōu)解，找出m個獨立零元素1、從第一行開始，遇到每行只有一個零元素就用括號括上，記作0）(,然后劃去其所在列的其他零元素，用○表示，遇到有兩個及其以上零元素的行先跳過去；2、進(jìn)行列檢驗，從第一列開始，給只有一個零元素的列中的那個零元素ij2○44○52○315444○5元素各減去θ,對畫直線的列中所有非零元素各加上θ,并保持原來零元素0206030503340403060305033404本例又從第二步開始： 45○3iiiiiiiiii二維背包iiΣiiiii②狀態(tài)變量s表示第第k階段開始時允許裝入前k種物品的總重量，有kkk-1kkks kas kakkkksf(s)=max{cx+f(sii4353i99s1s]1f(s)x*1440000000000000888853332150f(s)f(s)x1005x*2s3f(s)f(s)0x*386885557890055500644952）確定狀態(tài)變量及其取值范圍：原則是它能描需求量dk233440kkkkk+1個月的庫存量為第k個月可銷售k{{}k{}kkkkkkk5{}{{{{}