運(yùn)籌學(xué)簡(jiǎn)介及第一章

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

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

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

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

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

4x1≤16

4x2≤12

x1≥0，x2≥0，稱(chēng)x1，x2為決策變量目標(biāo)函數(shù)maxz=2x1+3x2(圖解法)問(wèn)題2：運(yùn)輸問(wèn)題的運(yùn)價(jià)、產(chǎn)量、銷(xiāo)量如下表，如何安排調(diào)運(yùn)，運(yùn)費(fèi)最?。?/p>

銷(xiāo)地產(chǎn)地

運(yùn)價(jià)

123產(chǎn)量A

B

2132

24

50

30

銷(xiāo)量401525解：設(shè)x1j為從產(chǎn)地A運(yùn)往銷(xiāo)地j的物資數(shù)量(j=1,2,3),x2j為從產(chǎn)地B運(yùn)往銷(xiāo)地j的物資數(shù)量(j=1,2,3), 則有，目標(biāo)函數(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ī)劃三要素：決策變量、目標(biāo)函數(shù)、約束條件線性規(guī)劃的特點(diǎn):

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

目標(biāo)函數(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—價(jià)值向量

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ī)劃問(wèn)題模型的標(biāo)準(zhǔn)型：分量形式：線性規(guī)劃（LP）的標(biāo)準(zhǔn)型：目標(biāo)函數(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)注:有些書(shū)中以min型目標(biāo)函數(shù)為標(biāo)準(zhǔn)型∑(和)形式：目標(biāo)函數(shù)maxz=∑cjxj

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

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

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

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

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

目標(biāo)函數(shù)maxz=CX

約束條件s.t.AX=b

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

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

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

引進(jìn)松弛變量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ī)劃問(wèn)題化成標(biāo)準(zhǔn)型

minZ=x1+2x2

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

x1-x2=3

x1≥0§2.1圖解法

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

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

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

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

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

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

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

-3x1+2x2≤6

s.t.-x1+3x2≥18

x1,x2

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

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

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

=(p1,p2,…,pm)

a11a12…a1m

a21a22…a2m

…

…

…

am1am2…amm

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

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

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

稱(chēng)為基解?；尚薪?所有決策變量滿(mǎn)足非負(fù)條件(xj≥0)的基解,稱(chēng)作基可行解?？尚谢夯尚薪馑鶎?duì)應(yīng)的基底稱(chēng)為可行基。基解的數(shù)目最多為Cnm個(gè)?；尚薪獾臄?shù)目一般小于基解的數(shù)目;基解中非零分量的個(gè)數(shù)小于m個(gè)時(shí)，基解稱(chēng)為退化解。以后在不聲明的情況下，均假設(shè)不出現(xiàn)退化情況。可行解基解基可行解非可行解解的關(guān)系：

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

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

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

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

D={X∣AX=b,xj≥0}={X∣,xj≥0}是凸集。凸集性質(zhì):設(shè)x(1)≠x(2)為D內(nèi)任取兩點(diǎn)，則Ax(1)=b,Ax(2)=b,x(1)≥0,x(2)≥0,令x為線段x(1),x(2)上任一點(diǎn),即有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

又因?yàn)閤(1)

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

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

maxz=CXs.t.AX=bX≥0

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

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

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

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

充分性（頂點(diǎn)基可行解，用反證法）：由引理1，若X不是基可行解，則其正分量所對(duì)應(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)μ充分小時(shí),可保證xi±μαi≥0i=1,2,…,m,即X(1),X(2)是可行解。由X(1),X(2)

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

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