【正文】 . a11 x1 + a12 x2 + … + a1n xn ≤ b1 a21 x1 + a22 x2 + … + a2n xn ≤ b2 …… …… am1 x1 + am2 x2 + … + amn xn ≤ bm x1 ， x2 ， … ， xn ≥ 0? 加入松弛變量： Max z = c1 x1 + c2 x2 + … + c n xn . a11 x1 + a12 x2 + … + a1n xn + xn+1 = b1 a21 x1 + a22 x2 + … + a2n xn + xn+2 = b2 …… …… am1 x1 + am2 x2 + … + amn xn+ xn+m = bm x1 ， x2 ， … ， xn ， xn+1 ， … ， xn+m ≥ 017顯然， xj = 0 j = 1, … , n 。每一節(jié)或一章學(xué)完后，必須學(xué)會(huì)用精煉的語(yǔ)言來(lái)該書(shū)所學(xué)內(nèi)容。一般每一本運(yùn)籌學(xué)教材都有自己的特點(diǎn)，但是基本原理、概念都是一致的。運(yùn)籌學(xué)北京理工大學(xué)管理與經(jīng)濟(jì)學(xué)院吳祈宗教授1 緒 論 線 性 規(guī) 劃 運(yùn) 輸 問(wèn) 題 動(dòng) 態(tài) 規(guī) 劃 圖與網(wǎng)絡(luò)分析 排 隊(duì) 論 教學(xué)日歷運(yùn) 籌 學(xué) —— 目錄說(shuō) 明 本教學(xué)課件是與教材緊密配合使用的，教材為：《運(yùn)籌學(xué)》 楊民助編著西安交通大學(xué)出版社， 2023年 6月參考書(shū)：《運(yùn)籌學(xué)》 清華大學(xué)出版社或其他的《運(yùn)籌學(xué)》方面本科教材的相關(guān)內(nèi)容下面所標(biāo)注的頁(yè)號(hào)，均為本課程教材的頁(yè)號(hào)。? 自學(xué)時(shí)要掌握三個(gè)重要環(huán)節(jié)： 認(rèn)真閱讀教材和參考資料，以指定教材為主，同時(shí)參考其他有關(guān)書(shū)籍。 要學(xué)會(huì)做學(xué)習(xí)小結(jié)。要通過(guò)讀懂教材內(nèi)容以及大量練習(xí)來(lái)掌握。 充分大正數(shù) M 。23 線 性 規(guī) 劃 （續(xù) ）例題 例：（ LP） Max z = 5 x1 + 2 x2 + 3 x3 x4 . x1 + 2 x2 + 3 x3 = 15 2 x1 + x2 + 5 x3 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 ≥ 0? 大 M法問(wèn)題（ LP M） Max z = 5 x1 + 2 x2 + 3 x3 x4 M x5 M x6 . x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 0? 兩階段法 ：第一階段問(wèn)題（ LP 1） Max z = x5 x6 . x1 + 2 x2 + 3 x3 + x5 = 15 2 x1 + x2 + 5 x3 + x6 = 20 x1 + 2 x2 + 4 x3 + x4 = 26 x1 , x2 , x3 , x4 , x5 , x6 ≥ 024 線 性 規(guī) 劃 （續(xù) ）大 M法例?大 M法 （ LP M）? 得到最優(yōu)解： (25/3， 10/3， 0， 11)T 最優(yōu)目標(biāo)值： 112/325 線 性 規(guī) 劃 （續(xù) ）兩階段法例?第一階段 （ LP 1）? 得到原問(wèn)題的基本可行解： (0， 15/7， 25/7， 52/7)T 26 線 性 規(guī) 劃 （續(xù) ）兩階段法例?第二階段 把基本可行解填入表中? 得到原問(wèn)題的最優(yōu)解： (25/3， 10/3， 0， 11)T ?最優(yōu)目標(biāo)值： 112/327 線 性 規(guī) 劃 （續(xù) ） 矩陣描述 —— 此段為選讀，有困難者可不看。數(shù)據(jù)如下表。 利潤(rùn) = [（銷售單價(jià) 原料單價(jià)） * 產(chǎn)品件數(shù) ]之和 （每臺(tái)時(shí)的設(shè)備費(fèi)用 *設(shè)備實(shí)際使用的總臺(tái)時(shí)數(shù)）之和。這樣我們建立數(shù)學(xué)模型時(shí)，要考慮： 對(duì)于甲： x11， x12， x13； 對(duì)于乙： x21， x22， x23； 對(duì)于丙： x31， x32， x33； 對(duì)于原料 1： x11， x21， x31； 對(duì)于原料 2： x12， x22， x32； 對(duì)于原料 3： x13， x23， x33； 目標(biāo)函數(shù)： 利潤(rùn)最大，利潤(rùn) = 收入 原料支出 約束條件： 規(guī)格要求 4 個(gè)； 供應(yīng)量限制 3 個(gè)。定理 22 （最優(yōu)性準(zhǔn)則定理）若 x, y 分別為（ LP）和（ DP）的可行解，且 cT x = bT y ，那么 x, y分別為（ LP）和（ DP）的最優(yōu)解。線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）462. 2 對(duì)偶單純形法? 對(duì)偶單純形法在什么情況下使用 ： 應(yīng)用前提：有一個(gè)基，其對(duì)應(yīng)的基本解滿足 ① 單純形表的檢驗(yàn)數(shù)行全部非正（對(duì)偶可行）； ② 變量取值可有負(fù)數(shù)（非可行解）。 Max{?j / asj ? asj 0 } ≤ ?cs ≤ Min{?j / asj ? asj 0 } 例 : Max Z = 2x1 + 3x2 + 0x3 + 0x4+ 0x5 . x1 + 2x2+ x3 = 8 4x1 + x4 =16 4x2 +x5 = 12 x1 , x2 , x3 , x4 , x5 ≥ 0 線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）55例、下表為最優(yōu)單純形表，考慮基變量系數(shù) c2 發(fā)生變化從表中看到 σ j = Cj （ C1 * a1j + C5 * a5j + （ C2 +ΔC 2 ） * a2j ） j = 4可得到 3 ≤ ΔC 2 ≤ 1 時(shí)，原最優(yōu)解不變。計(jì)算得到線性規(guī)劃問(wèn)題的進(jìn)一步研究（ ）用單純形法進(jìn)一步求解，可得： x* = ( 1,0,0,0,2 )T f* = 59? 增加一個(gè)約束 增加約束一個(gè)之后，應(yīng)把最優(yōu)解帶入新的約束，若滿足則最優(yōu)解不變，否則填入最優(yōu)單純形表作為新的一行，引入1個(gè)新的非負(fù)變量（原約束若是小于等于形式可引入非負(fù)松弛變量，否則引入非負(fù)人工變量），并通過(guò)矩陣行變換把對(duì)應(yīng)基變量的元素變?yōu)?0，進(jìn)一步用單純形法或?qū)ε紗渭冃畏ㄇ蠼狻? * 運(yùn)輸問(wèn)題的 m + n 1 個(gè)變量構(gòu)成基變量的充分必要條件是不含閉回路。若某行（列）的產(chǎn)量（銷量）已滿足，則把該行（列）的其他格劃去。 j = 1, … , n運(yùn) 輸 問(wèn) 題（ ） 72? 前例，位勢(shì)法求檢驗(yàn)數(shù)： step 1 從任意基變量對(duì)應(yīng)的 cij 開(kāi)始，任取 ui 或 vj ，然后利用公式 cij = ui + vj 依次找出 m + n 個(gè) ui , vj ； 從 c14 = 10 開(kāi)始 step 2 計(jì)算非基變量的檢驗(yàn)數(shù) ?ij = cij ui vj ； 填入圓圈內(nèi)運(yùn) 輸 問(wèn) 題（ ） 73主元變換：（ 1）選負(fù)檢驗(yàn)數(shù)中最小者 ?rk，那么 xrk 為主元，作為進(jìn)基變量； （上頁(yè)圖中 x24 ）（ 2）以為 xrk 起點(diǎn)找一條閉回路，除 xrk 外其余頂點(diǎn)必須為基變量格； （上頁(yè)圖中 藍(lán)色回路）（ 3）為閉回路的每一個(gè)頂點(diǎn)標(biāo)號(hào)， xrk 為 1，沿一個(gè)方向依次給各頂點(diǎn)標(biāo)號(hào)；（ 4）求 ?=min{xij?xij對(duì)應(yīng)閉回路上的偶數(shù)標(biāo)號(hào)格 }= xpq那么確定 xpq為出基變量， ?為調(diào)整量；（ 5）對(duì)閉回路的各奇標(biāo)號(hào)頂點(diǎn) xij + ?，對(duì)各偶標(biāo)號(hào)頂點(diǎn) xij ?，特別 xpq ? = 0，變?yōu)榉腔兞?；運(yùn) 輸 問(wèn) 題（ ） 重復(fù) 3步，直到所有檢驗(yàn)數(shù)均非負(fù)，得到最優(yōu)解。假設(shè)效果相同，有關(guān)數(shù)據(jù)如下表。運(yùn) 輸 問(wèn) 題（例題）82解： 設(shè) xij為第 i 季度生產(chǎn)的第 j 季度交貨的柴油機(jī)數(shù)目，那末應(yīng)滿足：交貨： x11 = 10 生產(chǎn)： x11 + x12 + x13 + x14 ≤ 25 x12 + x22 = 15 x22 + x23 + x24 ≤ 35 x13 + x23 + x33 = 25 x33 + x34 ≤ 30 x14 + x24 + x34 + x44 = 20 x44 ≤ 10 把第 i 季度生產(chǎn)的柴油機(jī)數(shù)目看作第 i 個(gè)生產(chǎn)廠的產(chǎn)量；把第 j 季度交貨的柴油機(jī)數(shù)目看作第 j 個(gè)銷售點(diǎn)的銷量；成本加儲(chǔ)存、維護(hù)等費(fèi)用看作運(yùn)費(fèi)。續(xù)下頁(yè) 產(chǎn)銷平衡與運(yùn)價(jià)表：運(yùn) 輸 問(wèn) 題（例題）85 **習(xí)題： p 124 習(xí)題 3 33， 34運(yùn) 輸 問(wèn) 題（例題）返回目錄864. 1 動(dòng)態(tài)規(guī)劃概念與模型? 多階段決策過(guò)程特點(diǎn)要點(diǎn)：階段，狀態(tài)，決策，狀態(tài)轉(zhuǎn)移方程， k后部子過(guò)程動(dòng) 態(tài) 規(guī) 劃 () 87? 動(dòng)態(tài)規(guī)劃模型 n opt R( u1, … , u n ) = ? rk ( xk , uk ) k=1 . xk+1 = Tk ( xk , uk ) xk ? Xk ； uk ? Uk k = 1,…,n ?： 表示對(duì) n階段效應(yīng)進(jìn)行綜合（常用 ? 或 ? ）； opt ：最優(yōu)化（ Max 或 Min） R( u1, … , u n )：目標(biāo)函數(shù)（最優(yōu)值函數(shù)） xk+1 = Tk ( xk , uk ) ：狀態(tài)轉(zhuǎn)移方程 Xk ：狀態(tài)可能集合 Uk：決策允許集合動(dòng) 態(tài) 規(guī) 劃 () 88? 建模過(guò)程