暨南大學(xué)運(yùn)籌學(xué)課件
OPERATIONS RESEARCH 運(yùn)籌學(xué)Ⅰ
——怎樣把事情做到最好

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

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

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

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

線性規(guī)劃的標(biāo)準(zhǔn)型
向量式：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ī)劃的標(biāo)準(zhǔn)型
矩陣式： maxZ=CX AX=b X ≥0
其中： b=(b1,b2,…,bm)T
a11 a12 ….a1n
A= a21 a22 … a2n
… … …
am1 am2 …amn
標(biāo)準(zhǔn)型的特征
目標(biāo)函數(shù)極大化
約束條件為等式
決策變量非負(fù)
非標(biāo)準(zhǔn)型轉(zhuǎn)化為標(biāo)準(zhǔn)型
目標(biāo)函數(shù)極小化轉(zhuǎn)為極大化：
minZ=－max(－Z) ，一個(gè)數(shù)的極小化等價(jià)于其相反數(shù)的極大化。
不等式約束的轉(zhuǎn)化： ∑aijxj≤bi 加入松弛變量
∑aijxj≥bi 減去剩余變量
非正變量：即xk ≤0 則令x’k =－ xk
自由變量：即xk無約束，令xk= x’k－x”k
非標(biāo)準(zhǔn)型轉(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
非標(biāo)準(zhǔn)型轉(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標(biāo)準(zhǔn)型
和式：maxZ= ∑cjxj ∑aijxj=bi xj ≥0 j=1,2,…,n
矩陣式：maxZ=CX AX=b X ≥0
約束方程的系數(shù)矩陣A的秩為m，且m<n。設(shè)A=B+N ，B是A中mm階非奇異子矩陣，則稱B是LP的一個(gè)基，即：B是A中m個(gè)線性無關(guān)向量組。
基解的概念
不失一般性,設(shè)B是A的前m列,即B=(p1,p2,…,pm）,其相對應(yīng)的變量XB=(x1,x2,…,xm)T,稱為基變量；其余變量XN=(Xm+1,…,Xn)T稱為非基變量。令所有非基變量等于零,則X=（x1,x2,…xm,0,…,0)T稱為基解 。
基可行解的概念
基可行解：基解可正可負(fù)，負(fù)則不可行（違背非負(fù)性約束條件），稱滿足所有約束條件的基解為基可行解。
退化的基可行解：若某個(gè)基變量取值為零，則稱之為退化的基可行解。
基解的數(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ù)矩陣中找到一個(gè)可行基B，不妨設(shè)B由A的前m列組成，即B=(P1,P2,……Pm)。進(jìn)行等價(jià)變換－－約束方程兩端分別左乘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)性檢驗(yàn)：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代入目標(biāo)函數(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判別準(zhǔn)則 ： σj ≤0 時(shí),達(dá)到最優(yōu)解
單純形法
2.2.2基變換
若存在σj ≥ 0，則取 max{σj } = σK ，相應(yīng)之非基變量XK若取非零，將使Z增加,故令XK 進(jìn)基。令XK≠0 ，其余非基變量保持為零。 XK 原是非基變量，取零值， 若 XK ≠0 將迫使某個(gè)原基變量為零，當(dāng)XK取值超過任意b’i / a’ik 時(shí),將破壞非負(fù)性條件,于是令θ = min {b’i / a’ik a’ik >0 } =b’L/ a’Lk 。
這時(shí)原基變量XL=0，由基變量變成非基變量，
a’Lk處在變量轉(zhuǎn)換的交叉點(diǎn)上，稱之為樞軸元素
單純形法解題舉例
單純形表的格式：

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

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

應(yīng)用舉例之三
例15.滾動(dòng)投資問題
茲有100萬元閑錢，投資方向有四：



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

對偶模型
設(shè)每個(gè)工時(shí)收費(fèi)Y1元，設(shè)備臺(tái)時(shí)費(fèi)用Y2元，原材料附加費(fèi)Y3元。
出租收入不低于生產(chǎn)收入：
9y1+4y2+3y3 ≥70
4y1+5y2+10y3 ≥120
目標(biāo)：ω=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個(gè)約束條件，對偶問題有m個(gè)變量
原問題有n個(gè)變量，對偶問題有n個(gè)約束條件
原問題的價(jià)值系數(shù)對應(yīng)對偶問題的右端項(xiàng)
原問題的右端項(xiàng)對應(yīng)對偶問題的價(jià)值系數(shù)
原問題的技術(shù)系數(shù)矩陣轉(zhuǎn)置后為對偶問題系數(shù)矩陣
原問題的約束條件與對偶問題方向相反
原問題與對偶問題優(yōu)化方向相反
對偶規(guī)則
.
對偶規(guī)則簡捷記法
原問題標(biāo)準(zhǔn)則對偶問題標(biāo)準(zhǔn)
原問題不標(biāo)準(zhǔn)則對偶問題不標(biāo)準(zhǔn)
例題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ì)
對稱性：對偶問題的對偶問題是原問題
弱對偶性：極大化原問題的任一可行解的目標(biāo)函數(shù)值，不大于其對偶問題任意可行解的目標(biāo)函數(shù)值 (鞍型圖)
無界性：原問題無界，對偶問題無可行解
對偶定理：若一個(gè)問題有最優(yōu)解，則另一問題也有最優(yōu)解，且目標(biāo)函數(shù)值相等。若原問題最優(yōu)基為B，則其對偶問題最優(yōu)解Y*=CBB-1
3.1.4對偶最優(yōu)解的經(jīng)濟(jì)解釋—影子價(jià)格
Z= ω=CX=Yb Z/  b=(Yb)’=Y
Z=Yb= ∑yibi的意義：Y是檢驗(yàn)數(shù)的反數(shù)。在Y確定的前提下，每增加一個(gè)單位的i種資源，對目標(biāo)函數(shù)的貢獻(xiàn)。
結(jié)合例題1講解影子價(jià)格：y1=0:第一種資源過剩
y2=13.6：設(shè)備臺(tái)時(shí)最緊張，每增加一個(gè)臺(tái)時(shí)， 利潤增加13.6元。y3=5.2…
影子價(jià)格所含有的信息： 1、資源緊缺狀況
2、確定資源轉(zhuǎn)讓基價(jià)
參見：P40 3、取得緊缺資源的代價(jià)
3.2靈敏度分析
為什么進(jìn)行靈敏度分析？
靈敏度分析的兩把尺子：
σj =Cj-CBB-1pj≤ 0；  xB= B-1b ≥0
3.2.1 價(jià)值系數(shù)的靈敏度分析
Cj變化到什么程度可以保持最優(yōu)基不變？用
（參看P96）
例題4： 87.5 ≤ C2 ≤ 233.33；36 ≤ C1 ≤ 96
靈敏度分析
右端項(xiàng)的靈敏度分析：
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元，使用勞動(dòng)力6工時(shí)，設(shè)備5臺(tái)時(shí)，原材料7公斤，問要否調(diào)整產(chǎn)品結(jié)構(gòu)？
先算檢驗(yàn)數(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用計(jì)算機(jī)進(jìn)行靈敏度分析
例題7 參見P102
習(xí)題課：
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進(jìn)基，X2出基：
H1 ≥0， H3>0 ， H2>0，
習(xí)題課：
P79——2.11
1、對 2、錯(cuò)，可能有最優(yōu)解 3、對
4、對 5、錯(cuò) 6、錯(cuò) 7、錯(cuò)在“可行”
8、對 9、錯(cuò)
習(xí)題課：
P81——2.16
設(shè)白天電視廣告X1個(gè)，黃金時(shí)間電視廣告X2個(gè)，廣播廣告X3個(gè)，雜志廣告X4個(gè)
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
習(xí)題課：
P81——2.17
設(shè)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
習(xí)題課：
P107——3.2
1、對，根據(jù)若對偶性
2、對，同上
3、對，同上
4、對，因?yàn)橛白觾r(jià)格是每增加一個(gè)單位的某種資源，對目標(biāo)函數(shù)的貢獻(xiàn)程度
5、對，根據(jù)強(qiáng)對偶定理
習(xí)題課
P107——3.5 注：目標(biāo)函數(shù)為最大化
1、這是線性規(guī)劃的逆運(yùn)算
對偶問題最優(yōu)解 ：
Y1=4、Y2=2、Y3=0、Y4=4、Y5=0
習(xí)題課
P109——3.8
1、原問題的最優(yōu)解：X1=6，X5=10，其余為零;對偶問題最優(yōu)解：Y1=2,Y2=0
C1的變化范圍：以C1代入末表， C1 ≥1
右端項(xiàng)變化范圍： xB= B-1b ≥0
b1 ≥-6，b2≥-10

暨南大學(xué)運(yùn)籌學(xué)課件