暨南大學運籌學課件
OPERATIONS RESEARCH 運籌學Ⅰ
——怎樣把事情做到最好

郝英奇
第一章 緒論
1.1題解
Operations 漢語翻譯
工作、操作、行動、手術、運算
Operations Research
日本——運用學 港臺——作業(yè)研究
中國大陸——運籌學
Operational Research原來名稱，意為軍事行動研究——歷史淵源
緒論
1.2 運籌學的歷史
早期運籌思想：田忌賽馬
丁渭修宮
沈括運糧
Erlang 1917 排隊論
Harris 1920 存儲論
Levinson 1930 零售貿(mào)易
康脫洛維奇 1939 LP

緒論
1.2運籌學的歷史
軍事運籌學階段
德軍空襲 防空系統(tǒng) Blackett
運輸船編隊
空襲逃避
深水炸彈
轟炸機編隊
緒論
1.2運籌學的歷史
管理運籌學階段
戰(zhàn)后人員三分:軍隊、大學、企業(yè)
大學：課程、專業(yè)、碩士、博士
企業(yè)：美國鋼鐵聯(lián)合公司
英國國家煤炭局
運籌學在中國：50年代中期引入
華羅庚推廣 優(yōu)選法、統(tǒng)籌法
中國郵遞員問題、運輸問題

1.3學科性質(zhì)
應用學科
Morse&Kimball定義：運籌學是為決策機構(gòu)在對其控制的業(yè)務活動進行決策時提供的數(shù)量化為基礎的科學方法。
Churchman定義：運籌學是應用科學的方法、技術和工具，來處理一個系統(tǒng)運行中的問題，使系統(tǒng)控制得到最優(yōu)的解決方法。
中國定義：運籌學是應用分析、試驗、量化的方法，對經(jīng)濟管理系統(tǒng)中人力、物力、財力等資源進行統(tǒng)籌安排，為決策者提供有依據(jù)的最優(yōu)方案，以實現(xiàn)最有效的管理。
1.4定性與定量
例：店主進貨
兩者都是常用的決策方法
定性是基礎，定量是工具，定量為定性服務。
定性有主觀性也有有效性，定量有科學性也有局限性。管理科學的發(fā)展，定量越來越多。但定量不可替代定性。
1.5運籌學的模型
模型：真實事物的模仿，主要因素、相互關系、系統(tǒng)結(jié)構(gòu)。
形象模型：如地球儀、沙盤、風洞
模擬模型：建港口，模擬船只到達。學生模擬企業(yè)管理系統(tǒng)運行。
數(shù)學模型：用符號或數(shù)學工具描述現(xiàn)實系統(tǒng)。V=F（xi,yj,uk) G(xi,yj,uk)≥0
1.6運籌學的學科體系
規(guī)劃論：線性規(guī)劃、非線性規(guī)劃|、整數(shù)規(guī)劃、目標規(guī)劃、動態(tài)規(guī)劃
圖論與網(wǎng)絡
存儲論
排隊論
決策論
對策論
計算機仿真
1.7運籌學的工作步驟
確定問題
搜集數(shù)據(jù)建立模型
檢驗模型
求解模型
結(jié)果分析
結(jié)果實施
1.8運籌學與計算機
計算機為運籌學提供解題工具。
本書有現(xiàn)成的程序可以利用
要學會解題的思路與方法，建立模型很重要。
第二章 線性規(guī)劃與單純形法
2.1 LP(linear programming)的基本概念
LP是在有限資源的條件下，合理分配和利用資源，以期取得最佳的經(jīng)濟效益的優(yōu)化方法。
LP有一組有待決策的變量，
一個線性的目標函數(shù)，
一組線性的約束條件。
2.1.1 LP的數(shù)學模型 例題1—生產(chǎn)計劃問題
某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：
例題1建模
問題：如何安排生產(chǎn)計劃，使得獲利最多？
步驟：
1、確定決策變量：設生產(chǎn)A產(chǎn)品x1kg,B產(chǎn)品x2kg
2、確定目標函數(shù)：maxZ=70X1+120X2
3、確定約束條件：人力約束 9X1+4X2≤360
設備約束 4X1+5X2 ≤200
原材料約束3X1+10X2 ≤300
非負性約束X1≥0 X2≥0
例題2——配方問題
養(yǎng)海貍鼠 飼料中營養(yǎng)要求：VA每天至少700克，VB每天至少30克，VC每天剛好200克?，F(xiàn)有五種飼料，搭配使用，飼料成分如下表：
例題2建模
設抓取飼料I x1kg;飼料II x2kg;飼料III x3kg……
目標函數(shù)：最省錢 minZ=2x1+7x2+4x3+9x4+5x5
約束條件：3x2+2x2+x3+6x4+18x5 ≥700
營養(yǎng)要求： x1+0.5x2+0.2x3+2x4+0.5x5 ≥30
0.5x1+x2+0.2x3+2x4+0.8x5 =200
用量要求： x1 ≤50,x2 ≤60,x3 ≤50,x4 ≤70,x5 ≤40
非負性要求：x1 ≥0,x2 ≥0,x3 ≥0,x4 ≥0,x5 ≥0
例題3：人員安排問題
醫(yī)院護士24小時值班，每次值班8小時。不同時段需要的護士人數(shù)不等。據(jù)統(tǒng)計：

例題3建模
目標函數(shù)：min Z=x1+x2+x3+x4+x5+x6
約束條件： x1+x2 ≥70
x2+x3 ≥60
x3+x4 ≥ 50
x4+x5 ≥20
x5+x6 ≥30
非負性約束：xj ≥0,j=1,2,…6
歸納：線性規(guī)劃的一般模式
目標函數(shù)：max(min)Z=c1x1+c2x2+c3x3+…+cnxn
約束條件：a11x1+a12x2+a13x3+…+a1nxn ≤(= ≥)b1
a21x1+a22x2+a23x3+…+a2nxn ≤(= ≥)b2
… … … …
am1x1+am2x2+am3x3+…+amnxn ≤(= ≥)bn
非負性約束：x1 ≥0,x2 ≥0,…,xn ≥0
2.1.2線性規(guī)劃圖解法
由中學知識可知：y=ax+b是一條直線，同理：Z=70x1+120x2→x2=70/120x1-Z/120也是一條直線，以Z為參數(shù)的一族等值線。
9x1+4x2 ≤360 → x1 ≤360/9-4/9x2
是直線 x1=360/9-4/9x2 下方的半平面。所有半平面的交集稱之為可行域，可行域內(nèi)的任意一點，就是滿足所有約束條件的解，稱之為可行解。
例1圖示
.
概念
概念：
1、可行解：滿足所有約束條件的解。
2、可行域：即可行解的集合。所有約束條件的交集，也就是各半平面的公共部分。滿足所有約束條件的解的集合，稱為可行域。
3、基解：約束條件的交點稱為基解（直觀）
4、基可行解：基解當中的可行解。
5、凸集：集合內(nèi)任意兩點的連線上的點均屬于這個集合。如：實心球、三角形
結(jié)論
可行域是個凸集
可行域有有限個頂點
最優(yōu)值在可行域的頂點上達到
無窮多解的情形
無界解情形
無解情形
2.1.3線性規(guī)劃的標準型
代數(shù)式maxZ=c1x1+c2x2+…+cnxn
a11x1+a12x2+…+a1nxn=b1
a21x1+a22x2+…+a2nxn=b2
… … …
am1x1+am2x2+…+amnxn=bm
xj ≥0 j=1,2,…,n
線性規(guī)劃的標準型
和式：maxZ=∑cjxj
∑aijxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n

線性規(guī)劃的標準型
向量式：maxZ=CX
∑pjxj=bi i=1,2,…,m
xj ≥0 j=1,2,…,n
C=(c1,c2,c3,…,cn)
X=(X1,X2,X3,…,Xn) T
線性規(guī)劃的標準型
矩陣式： maxZ=CX AX=b X ≥0
其中： b=(b1,b2,…,bm)T
a11 a12 ….a1n
A= a21 a22 … a2n
… … …
am1 am2 …amn
標準型的特征
目標函數(shù)極大化
約束條件為等式
決策變量非負
非標準型轉(zhuǎn)化為標準型
目標函數(shù)極小化轉(zhuǎn)為極大化：
minZ=－max(－Z) ，一個數(shù)的極小化等價于其相反數(shù)的極大化。
不等式約束的轉(zhuǎn)化： ∑aijxj≤bi 加入松弛變量
∑aijxj≥bi 減去剩余變量
非正變量：即xk ≤0 則令x’k =－ xk
自由變量：即xk無約束，令xk= x’k－x”k
非標準型轉(zhuǎn)化舉例之一
maxZ=70X1+120X2 maxZ=70X1+120X2
9X1+4X2≤360 9X1+4X2+X3=360
4X1+5X2 ≤200 4X1+5X2 +x4=200
3X1+10X2 ≤300 3X1+10X2+x5 =300
X1≥0 X2≥0 Xj≥0 j=1,2,…,5
非標準型轉(zhuǎn)化舉例之二
minZ=x1+2x2-3x3 maxZ’=x’1－2x2+3(x’3－x”3)
x1+x2+x3 ≤9 －x’1+x2+x’3－ x”3 + x4=9
-x1-2x2+x3 ≥2 x’1－2x2+x’3 －x”3 - x5= 2
3x1+x2-3x3=5 － 3x’1+x2－3(x’3 － x”3 )=5
x1 ≤0 x2 ≥0 x3無約束 x’1 ≥ 0 x2 ≥0 x’3 ≥0
x”3 ≥0 x4≥0 x5≥0

2.1.4基可行解
基的概念：如前所述LP標準型
和式：maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n
矩陣式：maxZ=CX AX=b X ≥0
約束方程的系數(shù)矩陣A的秩為m，且m<n。設A=B+N ，B是A中mm階非奇異子矩陣，則稱B是LP的一個基，即：B是A中m個線性無關向量組。
基解的概念
不失一般性,設B是A的前m列,即B=(p1,p2,…,pm）,其相對應的變量XB=(x1,x2,…,xm)T,稱為基變量；其余變量XN=(Xm+1,…,Xn)T稱為非基變量。令所有非基變量等于零,則X=（x1,x2,…xm,0,…,0)T稱為基解 。
基可行解的概念
基可行解：基解可正可負，負則不可行（違背非負性約束條件），稱滿足所有約束條件的基解為基可行解。
退化的基可行解：若某個基變量取值為零，則稱之為退化的基可行解。
基解的數(shù)目：最多Cmn=n!/m!(n-m)!
例題6 基可行解說明
maxZ=70X1+120X2 P1 P2 P3 P4 P5
9X1+4X2+X3=360 9 4 1 0 0
4X1+5X2 +x4=200 A= 4 5 0 1 0
3X1+10X2+x5 =300 3 10 0 0 1
Xj≥0 j=1,2,…,5
這里m=3,n=5。 Cmn=10
例題6 基可行解說明
基（p3,p4,p5） ，令非基變量x1,x2=0，則基變量x3=360, x4=200, x5=300, 可行解
基（p2,p4,p5）,令非基變量x1=0,x3=0基變量x2=90,x4=－250,x5=－600. 非可行解
基（ p2,p3,p4 ），令非基變量x1,x5=0，則基變量x2=30, x3=240, x4=50,可行解（P21圖）
2.2單純形法
2.2.1初始基可行解的確定
從系數(shù)矩陣中找到一個可行基B，不妨設B由A的前m列組成，即B=(P1,P2,……Pm)。進行等價變換－－約束方程兩端分別左乘B－1 得
X1+ +a’1m+1xm+1+…+a’1nxn=b’1
x2+ +a’2m+1xm+1+…+a’2nxn=b’2
……………………………..
xm+a’mm+1xm+1+…+a’mnxn=b’m
令非基變量為0，得基可行解
X(0)=(b1’，b2’，……bm，0，……0）T z0=∑cibi’
2.2單純形法
2.2.2最優(yōu)性檢驗：LP經(jīng)過若干步迭代，成為如下形式：
X1+ +a’1m+1xm+1+…+a’1nxn=b’1 x1=b’1- ∑ a’1jxj
x2+ +a’2m+1xm+1+…+a’2nxn=b’2 x2=b’2- ∑a’2jxj
…………………………….. ……………..
xm+a’mm+1xm+1+…+a’mnxn=b’m xm=b’m- ∑a’mjxj
單純形法
一般性表示：xi=b’i- ∑a’ijxj i=1,2,…m 將xi代入目標函數(shù)得：Z= ∑ cjxj
= ∑ cixi+ ∑ cjxj
= ∑ci（ b’i- ∑a’ijxj ） + ∑ cjxj
= ∑cibi’+ ∑(cj- ∑ cia’ij)xj
令：σj= cj- ∑ cia’ij z0=∑cibi’ 則Z=z0+ ∑ σj xj
σj判別準則 ： σj ≤0 時,達到最優(yōu)解
單純形法
2.2.2基變換
若存在σj ≥ 0，則取 max{σj } = σK ，相應之非基變量XK若取非零，將使Z增加,故令XK 進基。令XK≠0 ，其余非基變量保持為零。 XK 原是非基變量，取零值， 若 XK ≠0 將迫使某個原基變量為零，當XK取值超過任意b’i / a’ik 時,將破壞非負性條件,于是令θ = min {b’i / a’ik a’ik >0 } =b’L/ a’Lk 。
這時原基變量XL=0，由基變量變成非基變量，
a’Lk處在變量轉(zhuǎn)換的交叉點上，稱之為樞軸元素
單純形法解題舉例
單純形表的格式：

2.2.3單純形法的計算步驟
找到初始可行基，建立單純形表
計算檢驗數(shù)，若所有σj ≤0 則得最優(yōu)解，結(jié)束。否則轉(zhuǎn)下步
若某σK ≥ 0而P’K ≤0 ，則最優(yōu)解無界，結(jié)束。否則轉(zhuǎn)下步
根據(jù)max {σj } = σK 原則確定XK 進基變量；根據(jù)θ規(guī)則 ：θ = min {b’i / a’ik a’ik >0} = b’L/ a’Lk 確定XL為出基變量
以a’Lk 為樞軸元素進行迭代，回到第二步
2.3單純形法的進一步探討
2.3.1極小化問題直接求解：檢驗數(shù)的判別由所有σj ≤0 即為最優(yōu)，變?yōu)樗?sigma;j ≥ 0則為最優(yōu)。
人工變量法之一：大M法 人工變量價值系數(shù)M例
人工變量法之二：構(gòu)造目標函數(shù)，分階段求解例
2.3.2無窮多最優(yōu)解情形：非基變量檢驗數(shù) σj= 0
2.3.3退化解的情形：有兩個以上 θ值相等
2.3.4單純形法的計算機求解
程序說明
應用舉例
例題1
例題2
2.5LP應用舉例之一
例13合理下料問題
料長7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？關鍵：設變量。

應用舉例之二
例14混合配方問題
A、B、C、D四種原料配制三種產(chǎn)品，三類約束：技術要求、原料限量、市場容量。已知產(chǎn)品價格和原料價格，求利潤最大的配方。關鍵：設變量。

應用舉例之三
例15.滾動投資問題
茲有100萬元閑錢，投資方向有四：



應用舉例之四
例16動態(tài)生產(chǎn)計劃問題
工廠做n個月的生產(chǎn)計劃，第j月需求量dj、正常生產(chǎn)能力aj、加班生產(chǎn)能力bj、正常生產(chǎn)成本cj、加班生產(chǎn)成本ej、庫存能力為I、庫存費用hj，設期初、期末庫存為零。求費用最小的生產(chǎn)計劃。
設第月正常生產(chǎn)xj件，加班生產(chǎn)件yj，存儲zj件。則：
本期生產(chǎn)+上期庫存-本期庫存=本期需求
第三章 對偶問題與靈敏度分析
要求：
了解LP對偶問題的實際背景
了解對偶問題的建立規(guī)則與基本性質(zhì)
掌握對偶最優(yōu)解的計算及其經(jīng)濟解釋
掌握LP的靈敏度分析
理解計算機輸出的影子價格與靈敏度分 析的內(nèi)容
3.1 對偶問題
3.1.1 對偶問題的提出
回顧例題1： 現(xiàn)在A、B兩產(chǎn)品銷路不暢，可以將所有資源出租或外賣，現(xiàn)在要談判，我們的價格底線是什么？

對偶模型
設每個工時收費Y1元，設備臺時費用Y2元，原材料附加費Y3元。
出租收入不低于生產(chǎn)收入：
9y1+4y2+3y3 ≥70
4y1+5y2+10y3 ≥120
目標：ω=360y1+200y2+300y3
出租收入越多越好？至少不低于某數(shù)
原問題與對偶問題之比較
原問題： 對偶問題：
maxZ=70X1+120X2 minω=360y1+200y2+300y3

9X1+4X2≤360 9y1+4y2+3y3 ≥70
4X1+5X2 ≤200 (3.1) 4y1+5y2+10y3 ≥120 (3.2)
3X1+10X2 ≤300 y1 ≥0, y2 ≥0, y3 ≥0
X1≥0 X2≥0
3.1.2對偶規(guī)則
原問題一般模型： 對偶問題一般模型：
maxZ=CX min ω=Yb
AX ≤b YA ≥C
X ≥0 Y ≥0
對偶規(guī)則
原問題有m個約束條件，對偶問題有m個變量
原問題有n個變量，對偶問題有n個約束條件
原問題的價值系數(shù)對應對偶問題的右端項
原問題的右端項對應對偶問題的價值系數(shù)
原問題的技術系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣
原問題的約束條件與對偶問題方向相反
原問題與對偶問題優(yōu)化方向相反
對偶規(guī)則
.
對偶規(guī)則簡捷記法
原問題標準則對偶問題標準
原問題不標準則對偶問題不標準
例題2 max ω=7y1+4y2-2y3
minZ=3x1+2x2-6x3+x5 2y1+ y2- y3 ≤3
2x1+x2-4x3+x4+3x5 ≥7 y1 +3y3 ≤2
x1+ 2x3 -x4 ≤ 4 -4y1+ 2y2 ≤-6
-x1+3x2 -x4+ x5 =-2 y1 -y2 -y3 ≥ 0
x1，x2，x3 ≥0; 3y1 +y3=1
x4 ≤ 0;x5無限制 y1 ≥ 0y2 ≤ 0y3 無約束

3.1.3對偶問題的基本性質(zhì)
對稱性：對偶問題的對偶問題是原問題
弱對偶性：極大化原問題的任一可行解的目標函數(shù)值，不大于其對偶問題任意可行解的目標函數(shù)值 (鞍型圖)
無界性：原問題無界，對偶問題無可行解
對偶定理：若一個問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標函數(shù)值相等。若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-1
3.1.4對偶最優(yōu)解的經(jīng)濟解釋—影子價格
Z= ω=CX=Yb Z/  b=(Yb)’=Y
Z=Yb= ∑yibi的意義：Y是檢驗數(shù)的反數(shù)。在Y確定的前提下，每增加一個單位的i種資源，對目標函數(shù)的貢獻。
結(jié)合例題1講解影子價格：y1=0:第一種資源過剩
y2=13.6：設備臺時最緊張，每增加一個臺時， 利潤增加13.6元。y3=5.2…
影子價格所含有的信息： 1、資源緊缺狀況
2、確定資源轉(zhuǎn)讓基價
參見：P40 3、取得緊缺資源的代價
3.2靈敏度分析
為什么進行靈敏度分析？
靈敏度分析的兩把尺子：
σj =Cj-CBB-1pj≤ 0；  xB= B-1b ≥0
3.2.1 價值系數(shù)的靈敏度分析
Cj變化到什么程度可以保持最優(yōu)基不變？用
（參看P96）
例題4： 87.5 ≤ C2 ≤ 233.33；36 ≤ C1 ≤ 96
靈敏度分析
右端項的靈敏度分析：
bi變化到什么程度可以保持最優(yōu)基不變？用尺度
xB= B-1b ≥0
例題5： 1 -3.12 1.16 360
B-1b= 0 0.4 -0.2 200 ≥0
0 -0.12 0.16 b3
b3的變化范圍：227.586 ≤ b3 ≤ 400
其它形式的靈敏度分析
新產(chǎn)品的分析：
在資源結(jié)構(gòu)沒有變化的條件下，是否生產(chǎn)這種新 產(chǎn)品，就看它的競爭力如何。
例題6：新增一種C產(chǎn)品，單位利潤110元，使用勞動力6工時，設備5臺時，原材料7公斤，問要否調(diào)整產(chǎn)品結(jié)構(gòu)？
先算檢驗數(shù)σj =Cj-CBB-1pj
σ6=C6-YP6=110-（0，13.6，5.2）（6，5，7）T = 110-104.4=5.6 大于零，有利可圖，將P6左乘B-1，加入到末表之中，繼續(xù)迭代，直到求得最優(yōu)解。
3.3用計算機進行靈敏度分析
例題7 參見P102
習題課：
P78——2.10
（1）唯一最優(yōu)解：H3 ≤ 0 ，H5≤ 0 ， H1 ≥0
（2）無窮多最優(yōu)解： H3=0， H1 ≥0， H5 0 ， H2>0
或 H5=0， H1 ≥0， H3  0， H4>0
（3）無界解： H5≥0， H4  0 ， H1 ≥0， H3 0
（4）退化最優(yōu)解： H1=0 ， H3 0 ， H5 0
（5）非最優(yōu)解，X1進基，X2出基：
H1 ≥0， H3>0 ， H2>0，
習題課：
P79——2.11
1、對 2、錯，可能有最優(yōu)解 3、對
4、對 5、錯 6、錯 7、錯在“可行”
8、對 9、錯
習題課：
P81——2.16
設白天電視廣告X1個，黃金時間電視廣告X2個，廣播廣告X3個，雜志廣告X4個
maxZ=40X1+90X2+50X3+2X4
8X1+15X2+6X3+3X4 ≤16
30X1+40X2+20X3+X4 ≥200
8X1+15X2 ≤10
X1 ≥3 X2 ≥2
X3 ≥5 X3 ≤10
X4 ≥5 X4 ≤10 X j≥0 j=1、2、3、4
習題課：
P81——2.17
設A產(chǎn)品生產(chǎn)X1單位，B產(chǎn)品生產(chǎn)X2單位，C產(chǎn)品銷毀X3單位
maxZ=5X1+10X2+3（2X2-X3）-1X3
2X1+3X2 ≤200
3X1+4X2 ≤240
2X2-X3 ≤10 X1、X2、X3 ≥0
習題課：
P107——3.2
1、對，根據(jù)若對偶性
2、對，同上
3、對，同上
4、對，因為影子價格是每增加一個單位的某種資源，對目標函數(shù)的貢獻程度
5、對，根據(jù)強對偶定理
習題課
P107——3.5 注：目標函數(shù)為最大化
1、這是線性規(guī)劃的逆運算
對偶問題最優(yōu)解 ：
Y1=4、Y2=2、Y3=0、Y4=4、Y5=0
習題課
P109——3.8
1、原問題的最優(yōu)解：X1=6，X5=10，其余為零;對偶問題最優(yōu)解：Y1=2,Y2=0
C1的變化范圍：以C1代入末表， C1 ≥1
右端項變化范圍： xB= B-1b ≥0
b1 ≥-6，b2≥-10

暨南大學運籌學課件