線(xiàn)性規(guī)劃的單純形算法與線(xiàn)性代數(shù)的分塊初等變換的教學(xué)結(jié)合2

1、線(xiàn)性規(guī)劃的單純形算法和線(xiàn)性代數(shù)的分塊初等變換的教學(xué)結(jié)合福建師范大學(xué)數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院鄭開(kāi)杰大綱 教學(xué)困惑 教學(xué)結(jié)合 其他一、教學(xué)困惑1. 線(xiàn)性代數(shù)的應(yīng)用實(shí)例的教學(xué)困惑（1）教師角度： 教師的教學(xué)往往是“以不變應(yīng)萬(wàn)變”，不同專(zhuān)業(yè)的學(xué)生講一樣的應(yīng)用實(shí)例 為講線(xiàn)性代數(shù)的應(yīng)用“造”實(shí)例 受制于課時(shí)，不敢完整地講甚至不敢講應(yīng)用實(shí)例（2）學(xué)生不買(mǎi)帳 老師講的實(shí)例不真、不完整、與專(zhuān)業(yè)無(wú)關(guān)且無(wú)法實(shí)現(xiàn) 不考試【解】設(shè)x1、x2分別為甲、乙產(chǎn)品的產(chǎn)量，數(shù)學(xué)模型為： 產(chǎn)品 資源 甲 乙現(xiàn)有資源材料A2140材料B11.530利潤(rùn)（元/件） 300400生產(chǎn)計(jì)劃問(wèn)題2010：把吃出來(lái)的病吃回去 令人佩服的騙子 張悟

2、本52012-11-24 福建省*次會(huì)議2010：“曲美”減肥膠囊 （鹽酸西布曲明膠囊） - 抑制食欲 2011：把吃出來(lái)的肉吃回去 -減肥瘋子 XXX科學(xué)食譜能否減肥？62012-11-24 福建省*次會(huì)議合成后合成前72012-11-24 福建省*次會(huì)議 5 一、教學(xué)困惑2. 線(xiàn)性規(guī)劃的單純形算法的教學(xué)困惑 現(xiàn)有大部分運(yùn)籌學(xué)課程要求完整地講授單純形算法，但實(shí)際上，應(yīng)用工作者無(wú)需了解太深 為講單純形算法，需復(fù)習(xí)相關(guān)線(xiàn)性代數(shù)的內(nèi)容，占課時(shí) 單純形算法的迭代過(guò)程多采用表格形式，工作量極其大一、教學(xué)困惑3. 解決途徑：將單純形算法融入到線(xiàn)性代數(shù)中 省運(yùn)籌學(xué)至少6課時(shí)，且僅需至多增加兩個(gè)線(xiàn)性代數(shù)的課

3、時(shí) 適用的學(xué)生面廣 無(wú)需教授數(shù)學(xué)軟件，Excel即可簡(jiǎn)便實(shí)現(xiàn)二、分塊初等行變換觀點(diǎn)看單純形算法矩陣形式標(biāo)準(zhǔn)型max cTx | Ax=b, x 0 其中，R (Amn) = m1. 線(xiàn)性規(guī)劃概念2. 最優(yōu)解的判定僅為敘述算法方便，不妨設(shè)A =（Bmm，N）且 r(A) = r(B) = mAx = bBxB+NxN = bxB = B-1b-B-1NxN基變量、檢驗(yàn)數(shù)、基本解、基本可行解；基本解成為最大值解當(dāng)且僅當(dāng)（1）x0（2）自由變量的檢驗(yàn)數(shù)非正二、分塊初等行變換觀點(diǎn)看單純形算法3. 單純形算法檢驗(yàn)數(shù)的自動(dòng)計(jì)算xBxNBxBBNbcBcNxBxNbxBEB-1NB-1b檢驗(yàn)數(shù)0cN T -

4、 cBTB1N標(biāo)準(zhǔn)型：max cTx | Ax=b, x 0 原始單純形法的思路：step1：找一個(gè)自由變量等于零的非負(fù)解（初始基本可行解）step2：不斷改善該基本可行解，啟發(fā)式的認(rèn)為：（1）為使目標(biāo)函數(shù)上升最快，進(jìn)基變量應(yīng)選擇檢驗(yàn)數(shù)最大的，（2）出基變量的選擇應(yīng)使解可行基本可行解唯一取決于自由變量的選擇，故改善解的過(guò)程本質(zhì)上是：“不斷地調(diào)整自由變量組” 或“選擇進(jìn)基變量和離基變量”二、分塊初等行變換觀點(diǎn)看單純形算法4. 算例： 用單純形法求最優(yōu)解 【解】step1：化為標(biāo)準(zhǔn)型step2：求初始基本可行解X(1)=(0,0,40,30)T 故最優(yōu)解為（x1，x2）=（15，10）step3：?jiǎn)渭冃蔚▎渭冃芜^(guò)程簡(jiǎn)化寫(xiě)法）進(jìn)基列出基行bi /ai2，ai20i(a)XBx1x2x3x4bx3211040 x413/20130j30040000(b)x3x2j(c)x1x210j基變量120002/302/3204/31-2/340100/30-800/330103/4-1/21501-1/2 11000-25-250將3/2化為12015step3：?jiǎn)渭冃蔚▎渭冃伪砀駥?xiě)法）二、分塊初等行變換觀點(diǎn)看單純形算法5. Excel實(shí)現(xiàn)三、層次分析法與最大特征值Step1：建立遞階層次結(jié)構(gòu)模型Step2：構(gòu)造各個(gè)層次的判斷矩陣