【正文】 運(yùn) 籌 學(xué) 江 兵 合肥工業(yè)大學(xué)管理學(xué)院 2 三、課堂教學(xué)內(nèi)容 章 次 內(nèi) 容 總學(xué)時(shí)數(shù) 緒論 1 一 線(xiàn)性規(guī)劃及單純形法 16 / 2 二 對(duì)偶理論與靈敏度分析 12 / 2 三 運(yùn)輸問(wèn)題 6 / 1 四 整數(shù)規(guī)劃 6 / 1 五 動(dòng)態(tài)規(guī)劃 5 / 1 六 動(dòng)態(tài)規(guī)劃應(yīng)用舉例 4 七 圖與網(wǎng)絡(luò)分析 10 / 1 八 網(wǎng)絡(luò)計(jì)劃 2 九 排隊(duì)論 10 總學(xué)時(shí)數(shù) 72 / 8 3 運(yùn)籌學(xué)的工作步驟 明確問(wèn)題 建立模型 設(shè)計(jì)算法 整理數(shù)據(jù) 求解模型 評(píng)價(jià)結(jié)果 簡(jiǎn)化？ Yes No No 明確問(wèn)題 建立模型 設(shè)計(jì)算法 整理數(shù)據(jù) 求解模型 評(píng)價(jià)結(jié)果 結(jié)束 Yes 滿(mǎn)意？ 4 數(shù)學(xué)規(guī)劃是管理科學(xué)中求最優(yōu)或最有效使用有限資源的方 式以達(dá)到既定目標(biāo)的一個(gè)領(lǐng)域，又稱(chēng)為最優(yōu)化。 有限的資源：從地下抽出的原油、傾倒垃圾和有害廢物的 場(chǎng)地、企業(yè)招聘的人員、餐館放座位的空間、一個(gè)人每天工 作活動(dòng)的時(shí)間，做某件事情需要花的錢(qián) …… 確定產(chǎn)品組合：多數(shù)企業(yè)可以生產(chǎn)多種產(chǎn)品，但不同產(chǎn)品所需的原材料和工時(shí)不同，類(lèi)似地，它們產(chǎn)生的利潤(rùn)也不同，管理者必須決定每種產(chǎn)品產(chǎn)量以使利潤(rùn)最大或以最小成本滿(mǎn)足需求。 選路與物流：許多零售公司在各地都有提供商店貨物的倉(cāng)庫(kù)，倉(cāng)庫(kù)可供的貨物數(shù)量和各商店所需的貨物數(shù)量是不同的，需要確定從倉(cāng)庫(kù)運(yùn)送到商店的貨物所需成本最低的方法。 5 線(xiàn)性規(guī)劃 (Linear Programming —— LP)是數(shù)學(xué)規(guī)劃的一個(gè)分支，是一種解決在線(xiàn)性約束條件下追求最大或最小的線(xiàn)性目標(biāo)函數(shù)的方法。一般可以表達(dá)成以下兩個(gè)問(wèn)題中的一個(gè)： 1. 當(dāng)資源給定時(shí)，要求完成的任務(wù)最多； 2. 當(dāng)任務(wù)給定時(shí)，要求為完成任務(wù)所消耗的資源最少。 數(shù)學(xué)規(guī)劃中的模型都是線(xiàn)性函數(shù)時(shí)，稱(chēng)線(xiàn)性規(guī)劃。 6 第一章 線(xiàn)性規(guī)劃及單純形法 第一節(jié) 線(xiàn)性規(guī)劃問(wèn)題及數(shù)學(xué)模型（ P8） I II 設(shè)備 原材料 A 原材料 B 單件利潤(rùn) 1 4 0 2 2 0 4 3 8臺(tái)時(shí) 16kg 12kg ??????????????0,12416482..32m a xIII2121212121xxxxxxtsxxZxx 的產(chǎn)量、分別為計(jì)劃期內(nèi)產(chǎn)品、設(shè)7 設(shè) X1﹑X 2為工廠 1﹑ 2的日處理量 Min Z=1000X1+800X2 X1 ≥ 1 (1) +X2 ≥ (2) X1 ≤ 2 (3) X2 ≤ (4) X1﹑X 2≥ 0 環(huán)保要求： (污水量 /河水量 )≤%， 河流自?xún)袅Γ?20% 500萬(wàn) m3 200萬(wàn) m3 m3， 800元 /萬(wàn) m3 o工廠 2 例 2（ P9） 2萬(wàn) m3 ， 1000元 /萬(wàn) m3 o工廠 1 8 LP問(wèn)題的共同特征： ?每一個(gè)問(wèn)題變量都用一組 決策變量 （ x1,x2,… ,xn）表示某一方案，這組決策變量的值代表一個(gè)具體方案，這些變量是非負(fù)的。 ? 存在一定的 約束條件 ，這些約束條件可以用一組線(xiàn)性等式或線(xiàn)性不等式來(lái)表示。 ?目標(biāo)函數(shù) 用決策變量的線(xiàn)性函數(shù)來(lái)表示。按問(wèn)題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化或最小化。 目標(biāo)： objective, goal, target 9 LP模型一般形式 目標(biāo)函數(shù) Max (Min) Z=C1X1+ C2X2 + ... +Cn Xn a11X1+ a12X2 + ... + a1n X n ≤(=,≥)b1 約束條件 a21X1+ a22X2 + ... + a2n X n ≤(=,≥)b2 ┆ ┆ am1X1+ am2X2 + ... + amn Xn ≤(=,≥) bm 非負(fù)條件 X1﹑ X2 ... Xn ≥(=, ≤)0 或無(wú)約束 10 4x1=16 4x2=12 x1+2x2=8 x1 x2 4 8 4 3 0 Q(4,2) Z=2x1+3x2 最優(yōu)生產(chǎn)計(jì)劃為：生產(chǎn) I產(chǎn)品 4件，生產(chǎn) II產(chǎn)品 2件。 三、兩變量線(xiàn)性規(guī)劃問(wèn)題的圖解法 1) 作出 LP問(wèn)題的可行域 2) 作出目標(biāo)函數(shù)的等值線(xiàn) 3) 移動(dòng)等值線(xiàn)到可行域邊界得到最優(yōu)點(diǎn) 圖解法步驟 （圖解法意義不大，但可直觀揭示有關(guān)概念） ??????????????0,12416482..32m a x21212121xxxxxxtsxxZ11 有 可行解 有 最優(yōu)解 唯一解 無(wú)窮多解 無(wú) 最優(yōu)解（可行域?yàn)闊o(wú)界） 無(wú) 可行解（無(wú)解） LP解的可能情況： 若 LP問(wèn)題有最優(yōu)解，則要么最優(yōu)解唯一，要么有無(wú)窮多最優(yōu)解。 12 0 4 8 12 x1 9 6 3 x2 ① ③ ② 可行域 Z=36 4, 6 多重解舉例 Max Z=3X1+4X2 X1 ≤8 ① 2X2 ≤12 ② 3X1+4X2≤36 ③ X1﹑ X2≥0 此線(xiàn)段上的點(diǎn) 均為最優(yōu)點(diǎn) 13 1 0 1 2 3 x1 2 1 x2 可行域 無(wú)界解舉例 Max Z=3X1+2X2 2X1+X2≤2 ① X13X2≤3 ② X1﹑ X2≥0 ① ② Z增大方向 14 0 2 4 6 8 x1 x2 無(wú)可行解舉例 ： Max Z=2X1+3X2 X1+2X2≤8 ① 4X1 ≤16 ② 4X2 ≤12 ③ 2X1+X2 ≥4 ④ X1﹑ X2≥0 ① ③ 6 4 2 0 ④ 無(wú)公共區(qū)域 (可行域 ) ② 15 四、 線(xiàn)性規(guī)劃問(wèn)題的標(biāo)準(zhǔn)型 16 線(xiàn)性規(guī)劃標(biāo)準(zhǔn)形矩陣描述 (A,C,b,X均為矩陣 )： X— 決策變量列向量。 b— 約束條件右端常數(shù)（資源）列向量。 C— 目標(biāo)函數(shù)價(jià)值系數(shù)行向量。 Amxn— 約束條件左端系數(shù)矩陣。 a11 a12 ... a1n a21 a22 ... a2n A= ┆ ┆ ┆ am1 am2 ... amn =[P1， P2 ... Pn] C = [c1 c2 ...] b1 x1 b2 x2 b= ┆ X= ┆ bm xn Max Z=CX | AX=b， X≥0 17 非標(biāo)準(zhǔn)形 LP問(wèn)題化為標(biāo)準(zhǔn)形： 1）若目標(biāo)函數(shù)為 MinZ，令 Z39。=Z， 則 MinZ等價(jià)于 MaxZ39。 2） 若為不等式約束： ? 若為 ≤ ，在方程左邊加一非負(fù)新變量，稱(chēng)松弛 （ Slack）變量 ? 若為 ≥ ，在方程左邊減一非負(fù)新變量，稱(chēng)剩余 （ Surpius）變量或松弛變量 四個(gè)特點(diǎn) ：極大化目標(biāo) ﹑ 等式約束 ﹑ 約束右端常數(shù)bi≥0﹑ 決策變量 Xj≥0 。 18 非標(biāo)準(zhǔn)形 LP問(wèn)題化為標(biāo)準(zhǔn)形 ： 3） 若 bi0, 方程兩邊同乘（ 1） 4） 若變量不滿(mǎn)足非負(fù)： ? 若 xK≤0 ，令 xK =xK39。, xK39?！? ，用此式替換模型中 xk ? 若 xK無(wú)約束，令 xK=xK39。xK39。39。, xK39。﹑x K39。39?！? ，用此式替換模型中 xk 19 例 1 ??????????????0,12416482..3221212121xxxxxxtsxxM axZ????????????????????????)5,1(01241648200032524132154321?jxxxxxxxxxxxxxM axZj可化為 例 4 Min Z = 1X1+2X23X3 X1+X2 +X3 ≤7 X1 X2 +X3 ≥2 3X1+X2+2X3=5 X1﹑ X2≥0﹑ X3無(wú)約束 Max Z39。 = X12X2+3（ X4X5） +0X60X7 X1+X2 +（ X4X5） +X6 =7 X1 X2 +（ X4X5） X7 =2 3X1+X2+ 2（ X4X5） =5 X1﹑ X2 ﹑ X4﹑ X5 ﹑ X6﹑ X7≥0 20 LP問(wèn)題解的概念 （可行解 ﹑ 基 ﹑ 基可行解 ﹑ 可行基） Max Z=2X1+3X2+4X3+7X4 2X1+3X2 X34X4 =8 X12X2+6X37X4 =3 X1﹑X 2 ﹑X 3﹑X 4≥0 24C?????????????????????????????????????????????????????? ????????????7641,7243,62137142,6112,2132654321BBBBBB及對(duì)應(yīng)解：個(gè)基共有 iBCA67461213224 ??????????????21 X1=(1,14/7,0