運籌學(xué)OperationalResearch緒論1、運籌學(xué)的發(fā)展歷史（OperationalResearch）名稱由來：“夫運籌帷幄之中，決勝千里之外”Lanchester戰(zhàn)斗方程(1914)Erlang(1917)的排隊論公式(源于電話通信問題)；存儲論(1920)的最優(yōu)批量公式第二次世界大戰(zhàn)英國雷達布防高射炮火力的問題，武器庫設(shè)置問題等防空作戰(zhàn)系統(tǒng)運行研究（1938,7）——“operationalresearch”蘇聯(lián)學(xué)者康托洛維奇對列寧格勒膠合板廠的計劃任務(wù)建立線性規(guī)劃模型（1939）；美國數(shù)學(xué)家G.B.Dantzig,求解線性規(guī)劃問題的單純形法（1947）；60年代華羅庚“優(yōu)選法、統(tǒng)籌法”，國防科技的計劃評審技術(shù);計算機→運籌學(xué)的發(fā)展→實際問題的最優(yōu)與滿意解。

美國：研究用科學(xué)方法來決定在資源不充分情況下如何最好地設(shè)計人——機系統(tǒng)并使之最好地運行。２、運籌學(xué)的定義：德國：從事決策模型的數(shù)學(xué)解法的一門科學(xué)。英國：運用科學(xué)方法解決工業(yè)、商業(yè)、政府部門、國防部門中有關(guān)人力、機器、物資、金錢等大型系統(tǒng)的指揮管理方面出現(xiàn)的問題，其目的是幫助管理者科學(xué)地決策其策略和行動。３、運籌學(xué)的內(nèi)容和分支規(guī)劃論：線性規(guī)劃、非線性規(guī)劃、整數(shù)規(guī)劃、動態(tài)規(guī)劃、多目標規(guī)劃等決策論：決策的原則、決策的方法等對策論——齊王賽馬，矩陣對策排隊論庫存理論（存貯論）圖與網(wǎng)絡(luò)分析４、運籌學(xué)的本質(zhì)以定量的模型化方法來描述和解決問題５、基本過程分析和表達問題（可控變量及有關(guān)參數(shù)、目標、可能的約束）；建立模型——數(shù)學(xué)模型,圖論模型,網(wǎng)絡(luò)模型等；求解模型，即尋找方案；檢驗(對解的最優(yōu)性進行檢驗)；方案的分析、評價；存儲空間分配，不同排隊規(guī)則對磁盤工作性能的影響；計算機網(wǎng)絡(luò)分組交換、操作系統(tǒng)中的作業(yè)調(diào)度，排隊論；滿足某組需求的文件查找次序，整數(shù)規(guī)劃；管理信息系統(tǒng)，決策支持系統(tǒng)。規(guī)劃論、決策論、對策論等。６、運籌學(xué)應(yīng)用——計算機與信息系統(tǒng)7、主要參考書

運籌學(xué)基礎(chǔ)及應(yīng)用（第四版）,胡運權(quán)主編,哈爾濱工業(yè)大學(xué)出版社運籌學(xué)（第三版）,《運籌學(xué)》教材編寫組編，清華大學(xué)出版社

課件公用郵箱用戶名 yunchouxue_bjut@密碼 yunchouxue簡介+線性規(guī)劃3)單純形法(3)對偶問題和靈敏度分析(6)運輸問題(3)目標規(guī)劃(3)整數(shù)規(guī)劃(6)非線性規(guī)劃(6)動態(tài)規(guī)劃(6)排隊論(6)對策論和單目標決策論(3)8、內(nèi)容安排(54-3-3-3=45課時)省略內(nèi)容：1圖與網(wǎng)絡(luò)分析2存儲論3多目標決策論4啟發(fā)式方法第一章線性規(guī)劃（LinearProgramming）教學(xué)目的：本章重點引入線性規(guī)劃問題的模型、幾何性質(zhì)、單純形解法和線性規(guī)劃的對偶定理。應(yīng)理解和掌握線性規(guī)劃的幾何性質(zhì)和求解原理，能針對實際問題，建立相應(yīng)的線性規(guī)劃模型。重點：線性規(guī)劃問題的求解方法、解的基本性質(zhì)以及對偶原理。難點：線性規(guī)劃的單純形法求解思想、矩陣表述、對偶理論以及靈敏度分析

問題1：某工廠計劃生產(chǎn)甲、乙兩種產(chǎn)品。所需的設(shè)備臺時及A、B兩種原材料消耗，詳見下表該工廠每生產(chǎn)一件甲產(chǎn)品可獲利2元，每生產(chǎn)一件乙產(chǎn)品可獲利3元，問如何安排生產(chǎn)計劃，可使利潤最大？§1線性規(guī)劃問題及其數(shù)學(xué)模型解：設(shè)x1，x2分別為甲、乙產(chǎn)品的數(shù)量，則有約束條件x1+2x2≤8

4x1≤16

4x2≤12

x1≥0，x2≥0，稱x1，x2為決策變量目標函數(shù)maxz=2x1+3x2(圖解法)問題2：運輸問題的運價、產(chǎn)量、銷量如下表，如何安排調(diào)運，運費最小？

銷地產(chǎn)地

運價

123產(chǎn)量A

B

2132

24

50

30

銷量401525解：設(shè)x1j為從產(chǎn)地A運往銷地j的物資數(shù)量(j=1,2,3),x2j為從產(chǎn)地B運往銷地j的物資數(shù)量(j=1,2,3), 則有，目標函數(shù)：

minz=2x11+x12+3x13+2x21+2x22+4x23

約束條件:x11+x12+x13≤

50x21+x22+x23≤

30x11+x21≤

40x12+x22 ≤

15x13+x23≤

25xij≥0i=1,2；j=1,2,3總結(jié)：線性規(guī)劃三要素：決策變量、目標函數(shù)、約束條件線性規(guī)劃的特點:

目標線性、約束條件為線性不等式或等式一般情況下，其值均是正的定義：線性規(guī)劃（LP）的一般模型為

目標函數(shù)：max(min)z=c1x1+c2x2+…+cnxn

約束條件：a11x1+a12x2+…+a1nxn=（≤、≥）b1

a21x1+a22x2+…+a2nxn=（≤、≥）b2

…

…

…

am1x1+am2x2+…+amnxn=（≤、≥）bm

x1≥0，x2≥0，…，xn≥0其中：

C—價值向量

A—系數(shù)矩陣

X－決策變量向量

b—資源向量其它表示形式：

形式：max(min)Z=cjxj

s.t.aijxj,=,bi，i=1,2,…,m

xj0，j=1,2,…,n

向量形式:max(min)Z=CXs.t.Pjxj,=,b

xj0，j=1,2,…,n

矩陣形式:max(min)Z=CXs.t.AX,=,bX0線性規(guī)劃問題模型的標準型：分量形式：線性規(guī)劃（LP）的標準型：目標函數(shù)：maxz=c1x1+c2x2+…+cnxn

約束條件：a11x1+a12x2+…+a1nxn=b1s.t.a21x1+a22x2+…+a2nxn=b2

…

…

…am1x1+am2x2+…+amnxn=bm

x1≥0，x2≥0，…，xn≥0

且bi≥0，若bi<0，則乘(-1)注:有些書中以min型目標函數(shù)為標準型∑(和)形式：目標函數(shù)maxz=∑cjxj

約束條件s.t.∑aijxj=bi，

i=1,…,mxj≥0，j=1,…,n向量形式:

目標函數(shù)maxz=∑cjxj

約束條件s.t.∑Pjxj=b

xj≥0，j=1,…,n矩陣形式:

目標函數(shù)maxz=CX

約束條件s.t.AX=b

X≥0任意線性規(guī)劃模型轉(zhuǎn)化為標準型的方法：1、目標最小化情況：minZ=max(―Z)=maxZ2、約束條件為不等式：“≥”：引進非負松弛變量xk≥0,不等式左端減去松弛變量,目標函數(shù)中xk對應(yīng)的系數(shù)取為零。

“≤”：引進非負剩余變量（也叫松弛變量）xl≥0,不等式左端加上松弛變量,目標函數(shù)中xl對應(yīng)的系數(shù)取為零。3、決策變量xk是自由變量(無非負限制)，或xj有上下界限制都可以引進新的變量，轉(zhuǎn)化為變量≥0形式。例如xk是自由變量，引進xl≥0,xm≥0,新變量，令xk=xl-xm，對應(yīng)的目標系數(shù)仍為ck

。4、當(dāng)bi小于零的時候，在等式兩邊同時乘以-1即可。“小加、大減、一變二”解：引進變量x3≥0、x4≥0，將自由變量換為x2=x3-x4

引進松弛變量x5≥0,松弛變量x6≥0得:maxZ’=-x1-2x3+2x4+0x5+0x6

2x1+3x3-3x4+x5=6s.t.x1+x3-x4-x6=4

x1-x3+x4=3

xj≥0,j=1,3,4,5,6例如：將下列線性規(guī)劃問題化成標準型

minZ=x1+2x2

2x1+3x2≤6s.t.x1+x2≥4

x1-x2=3

x1≥0§2.1圖解法

圖解法不是解線性規(guī)劃的主要方法,只是用于說明線性規(guī)劃解的性質(zhì)和特點。只能解兩個變量問題。

（用圖解法求解,線性規(guī)劃不需要化成標準型）圖解法的步驟：

1、約束區(qū)域的確定

2、目標函數(shù)等值線

3、平移目標函數(shù)等值線求最優(yōu)值§2線性規(guī)劃圖解法例1：maxz=2x1+3x2

s.t.x1+2x2≤84x1≤16x1,x2≥0有唯一解x1x2可行域(4,2)z=14目標函數(shù)等值線畫圖步驟：1、約束區(qū)域的確定2、目標函數(shù)等值線3、平移目標函數(shù)等值線求最優(yōu)值有無窮多解線段Q1Q2上的任意點都是最優(yōu)解x2x1x1+2x2=84x2=123x1=12例2maxz=2x1+4x2

s.t.x1+2x2≤84x2≤123x1≤12x1,x2≥0Q1Q2約束條件圍不成區(qū)域(又稱矛盾方程)無可行解例3：x1x2maxz=4x1+3x2

-3x1+2x2≤6

s.t.-x1+3x2≥18

x1,x2

≥0無有限最優(yōu)解(無界解)x1x2例4：-3x1+2x2=6

圖解法得出線性規(guī)劃問題解的幾種情況解的幾種情況約束條件圖形特點方程特點唯一解一般圍成有限區(qū)域,最優(yōu)值只在一個頂點達到無窮多解在圍成的區(qū)域邊界上,至少在兩個頂點處達到最優(yōu)值目標和某一約束方程成比例無可行解(無解)圍不成區(qū)域有矛盾方程無界解(無解)圍成無界區(qū)域,且無有限最優(yōu)值缺少一必要條件的方程列向量x=(x1，x2，…，xm）T為m維列向量。xRm線性相關(guān)一組向量v1,…,vn,如果有一組不全為零的系數(shù)α1,…,αn,使得:α1v1+…+αnvn=0，則稱v1,…,vn是線性相關(guān)的.線性無關(guān)一組向量v1,…,vn,如果對于任何數(shù)α1,…,αn,若要滿足:α1v1+…+αnvn=0,則必有系數(shù)α1=…=αn=0,(全為零)則稱v1,…,vn線性無關(guān)(線性獨立).矩陣A的秩設(shè)A為一個m×n階矩陣(m<n)若矩陣中最大線性無關(guān)列向量個數(shù)為k,則稱矩陣A的秩數(shù)為k,記為秩(A)=k.復(fù)習(xí)線性代數(shù)內(nèi)容:設(shè)線性規(guī)劃的標準形式：

maxz=Σcjxj(1)s.t.Σaijxj=bii=1,2,…,m(2)xj≥0j=1,2,…,n(3)可行域：由約束條件(2)、(3)所圍成的區(qū)域；可行解：滿足(2)、(3)條件的解X=(x1，x2，…，xn)T為可行解；基：設(shè)A是約束條件方程組的m×n維系數(shù)矩陣,其秩為m，B是A中m×m階非奇異子矩陣，則稱B為線性規(guī)劃問題的一個基。設(shè)§2.2線性規(guī)劃問題解的概念B=

=(p1,p2,…,pm)

a11a12…a1m

a21a22…a2m

…

…

…

am1am2…amm

基向量、非基向量、基變量、非基變量：稱pj(j=1,2,…,m）為基向量，其余稱為非基向量；與基向量pj(j=1,2,…,m）對應(yīng)的xj稱為基變量，其全體寫成XB=（x1，x2，…，xm）T；否則稱為非基變量，其全體經(jīng)常寫成XN。基解：對給定基B,設(shè)XB是對應(yīng)于這個基的基變量

XB=(x1，x2，…，xm)T；

令非基變量xm+1=xm+2=…=xn=0，由（2）式得出的解X=（x1，x2，…，xm，0，…，0）T

稱為基解。基可行解:所有決策變量滿足非負條件(xj≥0)的基解,稱作基可行解。可行基：基可行解所對應(yīng)的基底稱為可行基。基解的數(shù)目最多為Cnm個。基可行解的數(shù)目一般小于基解的數(shù)目;基解中非零分量的個數(shù)小于m個時，基解稱為退化解。以后在不聲明的情況下，均假設(shè)不出現(xiàn)退化情況。可行解基解基可行解非可行解解的關(guān)系：

凸集:（直觀）圖形中連接任意兩點的線段全部都在圖形區(qū)域內(nèi),稱此圖形是凸的。嚴格數(shù)學(xué)定義:設(shè)Ω為一n維歐氏空間的點集,若任意兩點x1,x2∈Ω,有x=λx1+(1-λ)x2∈Ω，其中λ∈[0，1]，則稱Ω為凸集。§2.3線性規(guī)劃問題的幾何意義?x1?x2?x1?x2凸組合：設(shè)x(1),x(2),…,x(k)是n維空間中的k個點,若存在μ1,μ2,…,μk(0≤μi≤1i=1,2,…k且Σμi=1)使x=μ1x(1)+μ2x(2)+…+μkx(k)成立,則稱x為

x(1),x(2),…,x(k)

的凸組合。特別，平面上的兩點x(1),x(2),連線上任一點x的坐標為x=αx(1)+(1-α)x(2)0≤α≤1.頂點：設(shè)K為凸集,x∈K并且x不能用K內(nèi)不同的兩點x(1),x(2)(x≠x(1),x≠x(2))的凸組合表示,則稱x為頂點.

定理1:線性規(guī)劃問題若存在可行域,則其必是凸集，亦即

D={X∣AX=b,xj≥0}={X∣,xj≥0}是凸集。凸集性質(zhì):設(shè)x(1)≠x(2)為D內(nèi)任取兩點，則Ax(1)=b,Ax(2)=b,x(1)≥0,x(2)≥0,令x為線段x(1),x(2)上任一點,即有x=μx(1)+(1-μ)x(2)(0≤μ≤1)則Ax=A[μx(1)+(1-μ)x(2)](0≤μ≤1)=μAx(1)+Ax(2)-μAx(2)=μb+b–μb=b

又因為x(1)

≥0,x(2)≥0,0≤μ≤1

所以x≥0即x∈D證畢證明：線性規(guī)劃

maxz=CXs.t.AX=bX≥0

引理1.線性規(guī)劃問題的可行解X為基可行解的充分必要條件是X的正分量所對應(yīng)的系數(shù)列向量是線性獨立的.證明:

必要性：已知X為線性規(guī)劃的基可行解，要證X的正分量所對應(yīng)的系數(shù)列向量線性獨立。因為X還是可行解，所以其非零分量全為正；又因為X為基本解，由定義，其非零分量所對應(yīng)的系數(shù)列向量線性獨立。充分性：已知可行解X的正分量所對應(yīng)的系數(shù)列向量線性獨立，欲證X是線性規(guī)劃的基可行解。

X正分量對應(yīng)的系數(shù)向量P1,P2,…,Pk線性獨立,則必有k≤m；當(dāng)k=m時，它們恰構(gòu)成一個基，從而X=（x1，x2,…,xk，0…0）為相應(yīng)的基可行解。k<m時，則一定可以從其余的系數(shù)列向量中取出m-k個與P1,P2,…,Pk構(gòu)成最大的線性獨立向量組，其對應(yīng)的解恰為X，所以根據(jù)定義它是基可行解。

定理2：X是線性規(guī)劃問題的基可行解的充要條件是它對應(yīng)于可行域D的頂點。（線性規(guī)劃問題的基可行解X對應(yīng)于可行域D的頂點。）證明：不失一般性，假設(shè)基可行解X的前m個分量為正。故

充分性（頂點基可行解，用反證法）：由引理1，若X不是基可行解，則其正分量所對應(yīng)的系數(shù)列向量P1,P2,…,Pm線性相關(guān),即存在一組不全為零的數(shù)αi,i=1,2,…,m（1）令X(1)=[(x1-μα1),(x2-μα2),…,(xm-μαm),0,…,0]X(2)=[(x1+μα1),(x2+μα2),…,(xm+μαm),0,…,0]當(dāng)μ充分小時,可保證xi±μαi≥0i=1,2,…,m,即X(1),X(2)是可行解。由X(1),X(2)

可以得到X=,即X是X(1),X(2)連線的中心。所以X不是可行域D的頂點.使得

α1P1+α2P2+…+αmPm=0