運(yùn)籌學(xué)課件-緒論

Optimization最優(yōu)化OperationalResearch運(yùn)籌學(xué)(包含更廣泛的內(nèi)容)內(nèi)容：1.線性規(guī)劃

2.

整數(shù)規(guī)劃

3.目標(biāo)規(guī)劃

4.非線性規(guī)劃

參考書《數(shù)學(xué)規(guī)劃》黃紅選，韓繼業(yè)編著《運(yùn)籌學(xué)》＜運(yùn)籌學(xué)＞教材編寫組編著作業(yè)要求與答疑安排請使用作業(yè)紙，寫清名字與學(xué)號。每周二上午交作業(yè)(理科樓27#)。助教：郭佳(guojia199011@163.com)通過郵箱(mlu@)答疑總成績=平時(shí)成績（15%）+期末考試成績（90%）聯(lián)系電話：62794756一、運(yùn)籌學(xué)（OR）發(fā)展簡介運(yùn)籌學(xué)在國外英國稱為OperationalResearch美國稱為OperationsResearch起源于二戰(zhàn)期間的軍事問題，如雷達(dá)的設(shè)置、運(yùn)輸船隊(duì)的護(hù)航艦隊(duì)的規(guī)模、反潛作戰(zhàn)中深水炸彈的深度、飛機(jī)出擊隊(duì)型、軍事物資的存儲等。二戰(zhàn)以后運(yùn)籌學(xué)應(yīng)用于經(jīng)濟(jì)管理領(lǐng)域1948年英國首先成立運(yùn)籌學(xué)會(huì)(ORS)

；1952年美國成立運(yùn)籌學(xué)會(huì)(ORSA)和管理學(xué)會(huì)(TIMS),(1994年合并為運(yùn)籌與管理學(xué)會(huì)，即INFORMS)。1952年，Morse和Kimball出版《運(yùn)籌學(xué)方法》1959年：成立國際運(yùn)籌學(xué)聯(lián)合會(huì)(IFORS),每3年一次年會(huì)

運(yùn)籌學(xué)在國內(nèi)中國古代樸素的運(yùn)籌學(xué)思想:《孫子兵法》、田忌賽馬1950年代(錢學(xué)森、華羅庚、許國志等)——兩法推廣（優(yōu)選法、統(tǒng)籌法）1956年成立運(yùn)籌學(xué)小組1958年提出運(yùn)輸問題的圖上作業(yè)法1962年提出中國郵路問題1964年華羅庚推廣統(tǒng)籌方法我國于1982年加入國際運(yùn)籌學(xué)聯(lián)合會(huì)，并于1999年8月組織了第15屆大會(huì)運(yùn)籌學(xué)的發(fā)展及展望運(yùn)籌學(xué)取得全面的發(fā)展。表現(xiàn)在：1）數(shù)學(xué)理論得到加強(qiáng)；2）分支學(xué)科大量涌現(xiàn)；3）應(yīng)用領(lǐng)域不斷拓寬等。二、運(yùn)籌學(xué)的定義運(yùn)籌學(xué)是把科學(xué)方法應(yīng)用在指導(dǎo)人員、工商企業(yè)、政府和國防等方面解決發(fā)生的各種問題，其方法是發(fā)展一個(gè)科學(xué)的系統(tǒng)模式，并運(yùn)用這種模式預(yù)測、比較各種決策及其產(chǎn)生的后果，以幫助主管人員科學(xué)地決定工作方針和政策——英國運(yùn)籌學(xué)會(huì)運(yùn)籌學(xué)為決策機(jī)構(gòu)對所控制的業(yè)務(wù)活動(dòng)作決策時(shí)，提供以數(shù)量為基礎(chǔ)的科學(xué)方法——Morse和Kimball運(yùn)籌學(xué)是應(yīng)用分析、試驗(yàn)、量化的方法對經(jīng)濟(jì)管理系統(tǒng)中人力、物力、財(cái)力等資源進(jìn)行統(tǒng)籌安排，為決策者提供有根據(jù)的最優(yōu)方案，以實(shí)現(xiàn)最有效的管理——中國百科全書現(xiàn)代運(yùn)籌學(xué)涵蓋了一切領(lǐng)域的管理與優(yōu)化問題，稱為ManagementScience三、運(yùn)籌學(xué)的工作步驟明確問題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評價(jià)結(jié)果簡化？

滿意？YesNoNo明確問題建立模型設(shè)計(jì)算法整理數(shù)據(jù)求解模型評價(jià)結(jié)果運(yùn)籌學(xué)的主要特點(diǎn)：運(yùn)籌學(xué)研究和解決問題的基礎(chǔ)是最優(yōu)化技術(shù)，并強(qiáng)調(diào)系統(tǒng)整體最優(yōu)。運(yùn)籌學(xué)研究和解決問題的優(yōu)勢是應(yīng)用各學(xué)科交叉的方法，具有綜合性。5.運(yùn)籌學(xué)具有強(qiáng)烈的實(shí)踐性和應(yīng)用的廣泛性。4.運(yùn)籌學(xué)研究和解決問題的效果具有連續(xù)性。運(yùn)籌學(xué)研究和解決問題的方法具有顯著的系統(tǒng)分析特征，其各種方法的運(yùn)用，幾乎都需要建立數(shù)學(xué)模型和利用計(jì)算機(jī)進(jìn)行求解。生產(chǎn)計(jì)劃的編制問：企業(yè)應(yīng)如何安排生產(chǎn)，能使總收益最大？2、數(shù)學(xué)模型決策目標(biāo)：A、B、C產(chǎn)品各生產(chǎn)多少臺使企業(yè)總收益最大？

決策變量：設(shè)

目標(biāo)函數(shù)：

約束條件：非負(fù)條件：合理下料問題

現(xiàn)要用長7.4米的圓鋼截取長2.9米、2.1米和1.5米的材料各100根，應(yīng)如何下料，才能使用料最??？1、各種取料方式

2.9

2.1

1.5

0.92、數(shù)學(xué)模型(1)決策目標(biāo)：如何取料使所用原料最少

(2)決策變量：設(shè)第j

種下料方式所用的原料根數(shù)為xj(3)目標(biāo)函數(shù)：(4)約束條件：(5)非負(fù)條件：人力資源安排問題

某商場是個(gè)中型的百貨商場，現(xiàn)在需要對營業(yè)員的工作時(shí)間作出安排，營業(yè)員每周工作五天，休息兩天，并要求休息的兩天是連續(xù)的，問題歸結(jié)為：如何安排營業(yè)員的作息時(shí)間，既能滿足工作需要，又使配備的營業(yè)員人數(shù)最少？1、有關(guān)數(shù)據(jù)對營業(yè)員的需求進(jìn)行統(tǒng)計(jì)分析，營業(yè)員每天的需求人數(shù)如下表所示：2、模型

例（挑選球員問題）某籃球教練要從8名業(yè)余隊(duì)員中挑選3名隊(duì)員參加專業(yè)球隊(duì)，使平均身高達(dá)到最高。隊(duì)員的號碼、身高及所擅長的位置如下。要求：中鋒1人；后衛(wèi)1人；前鋒1人，但1號、3號與6號隊(duì)員中至少保留1人給業(yè)余隊(duì)。

號碼身高（米）

位置挑選變量

12345678

1.921.911.901.861.851.831.801.79

中鋒中鋒前鋒前鋒前鋒后衛(wèi)后衛(wèi)后衛(wèi)

x1

x2

x3

x4

x5

x6

x7

x8(連續(xù)投資問題)某投資公司擬制定今后5年的投資計(jì)劃，初步考慮下面的4個(gè)投資計(jì)劃項(xiàng)目。項(xiàng)目1：從第1年到第4年每年年初需要投資，于次年年末收回成本，并可獲利潤15%；項(xiàng)目2：第3年年初需要投資，到第5年年末可以收回成本，并獲得利潤25%，但為保證足夠的資金流動(dòng)，規(guī)定該項(xiàng)目的投資金額上限為不超過總金額的40%；項(xiàng)目3：第2年年初需要投資，到第5年年末可以收回成本，并獲利潤40%，但公司規(guī)定該項(xiàng)目的最大投資金額不超過總金額的30%；項(xiàng)目4：5年內(nèi)每年年初可以購買公債，于當(dāng)年年末可以歸還本金，并獲利息6%。公司現(xiàn)有投資金額100萬元，該公司如何制定這些項(xiàng)目每年的投資計(jì)劃，使公司到第5年年末能夠獲得最大利潤？例（運(yùn)輸問題）要把某種貨物從m個(gè)工廠運(yùn)到n個(gè)商店去，其中每個(gè)工廠的庫存量為a1,a2,…,am,各商店的需求量為b1,b2,…,bn,從工廠i到商店j的運(yùn)費(fèi)（每單位貨物）為cij,確定從工廠i到商店j的運(yùn)輸量xij(i=1,…,m,j=1,…,n),使在滿足供求的條件下，總的運(yùn)費(fèi)最小。例（選址問題）設(shè)有n個(gè)市場，第j個(gè)市場的位置為(aj,bj)，對某種貨物的需要量為qj,j=1,…,n,現(xiàn)計(jì)劃建立m個(gè)倉庫，第i個(gè)倉庫的容量為ci,i=1,…,m,試確定倉庫的位置，使各倉庫到各市場的運(yùn)輸量與路程乘積之和最?。猓涸O(shè)第i個(gè)倉庫的位置為(xi,yi)，運(yùn)輸量為wij.例（數(shù)據(jù)擬合問題）在實(shí)驗(yàn)數(shù)據(jù)處理或統(tǒng)計(jì)資料分析中常遇到如下問題：設(shè)兩個(gè)變量x和y，已知存在函數(shù)關(guān)系，但其解析表達(dá)式或者是未知的、或者雖然為已知的但過于復(fù)雜。設(shè)已取得一組數(shù)據(jù)，

(xi,yi),i=1,2,…,m根據(jù)這組數(shù)據(jù)導(dǎo)出函數(shù)y=f(x)的一個(gè)簡單而近似的解析表達(dá)式。取一個(gè)簡單的函數(shù)序列g(shù)0(x),g1(x),…,gn(x)總結(jié)

目標(biāo)函數(shù)用決策變量的線性（或非線性）函數(shù)來表示。按問題的不同，要求目標(biāo)函數(shù)實(shí)現(xiàn)最大化和最小化。最優(yōu)化問題的共同特征：

每一個(gè)問題都用一組決策變量（x1,x2,…,xn）表示某一方案，這組決策變量的值代表一個(gè)具體方案。

存在一定的約束條件，這些約束條件可以用一組線性（或非線性）等式或線性（或非線性）不等式來表示?；靖拍羁尚悬c(diǎn)（可行解）：在線性規(guī)劃和非線性規(guī)劃中，滿足約束條件的點(diǎn)．可行集或可行域S：全體可行點(diǎn)組成的集合．無約束問題：如果一個(gè)問題的可行集是整個(gè)空間．對于一個(gè)規(guī)劃問題，下面三種情況必占其一：(1)S＝Φ，則稱該問題無解或不可行；(2)S≠Φ，但目標(biāo)函數(shù)在S上無界，則稱該問題無界；(3)S≠Φ且目標(biāo)函數(shù)有有限的最優(yōu)解，則稱該問題有（有限的）最優(yōu)解．定義１：設(shè)f(x)為目標(biāo)函數(shù)，S為可行域，x0∈S，若對?x∈S,有f(x)≥f(x0),則x0稱為極小化問題minf(x)，x∈S的（全局）最優(yōu)解．定義２：設(shè)f(x)為目標(biāo)函數(shù)，S為可行域，若存在x0的ε鄰域

使得對?x∈S∩Nε(x0)，有f(x)≥f(x0),則x0稱為極小化問題minf(x)，x∈S的局部最優(yōu)解．預(yù)備知識線性相關(guān)與線性無關(guān)：范數(shù)集合

內(nèi)點(diǎn)：補(bǔ)集：開集：閉集：有界集：緊集：有界閉集稱為緊集．性質(zhì)：函數(shù)的展開梯度：Hesse矩陣：Taylor展開定理：二次型的正定性定義：定理：二次型的半正定性定義：定理：凸集(convexset)定義：設(shè)x,y為歐式空間En中相異的兩個(gè)點(diǎn)，則點(diǎn)集

P={λx+(1-λ)y|λ∈R}稱為通過x和y的直線。定義：設(shè)S?En,若對?x(1),x(2)∈S及?λ∈[0,1],都有

λx(1)+(1-λ)x(2)∈S則稱S為凸集。設(shè)x(1),x(2)，…,x(k)∈S,稱

λ1x(1)+λ2x(2)+…+λkx(k)(其中λ1+λ2+…+λk=1，λi≥0)為x(1),x(2),…,x(k)的凸組合.H={x|pTx＝a}－－－－－－超平面H-={x|pTx≤a}－－－－－－（閉）半空間L={x|x=x(0)+λd,λ≥0}－－－－射線凸集的性質(zhì)設(shè)S1和S２為En中的兩個(gè)凸集，β是實(shí)數(shù)，則(1)βS1

={βx|x∈S1}為凸集。(2)S1∩S2為凸集。(3)S1+S２={x(1)+x(2)|x(1)∈S1，x(2)∈

S2}為凸集。(4)S1-S２={x(1)-