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