數(shù)學(xué)規(guī)劃導(dǎo)論和預(yù)備知識(shí)

數(shù)學(xué)規(guī)劃導(dǎo)論和預(yù)備知識(shí)第1頁(yè)，共29頁(yè)，2023年，2月20日，星期六教材：黃紅選，韓繼業(yè)編著，數(shù)學(xué)規(guī)劃，清華大學(xué)出版社參考書目：1.陳寶林，最優(yōu)化理論與算法（第2版），清華大學(xué)出版社2.袁亞湘，最優(yōu)化理論與方法，科學(xué)出版社3.何堅(jiān)勇，最優(yōu)化方法，清華大學(xué)出版社4.OperationsResearch(MathematicalProgramming)(ThirdEdition),WAYNEL.WINSTON,清華大學(xué)出版社2第2頁(yè)，共29頁(yè)，2023年，2月20日，星期六平時(shí)成績(jī)（30%）+期末成績(jī)（70%）考試形式：開卷3第3頁(yè)，共29頁(yè)，2023年，2月20日，星期六主要內(nèi)容緒論和預(yù)備知識(shí)（第1章、第2章）線性規(guī)劃（第3章、第7章）一般線性規(guī)劃整數(shù)規(guī)劃非線性規(guī)劃（第4章、第5章）無約束非線性規(guī)劃約束非線性規(guī)劃4第4頁(yè)，共29頁(yè)，2023年，2月20日，星期六緒論和預(yù)備知識(shí)最優(yōu)化的發(fā)展史最優(yōu)化例子相關(guān)數(shù)學(xué)概念和理論第5頁(yè)，共29頁(yè)，2023年，2月20日，星期六什么是最優(yōu)化？–生產(chǎn)計(jì)劃安排中選擇怎樣的方案才能獲得最高的利潤(rùn)–有限的資源如何分配使得既能滿足各方面要求并獲得最好的經(jīng)濟(jì)效益–工程設(shè)計(jì)中如何選擇參數(shù)使得既能滿足要求又能降低成本–對(duì)抗賽時(shí)實(shí)施更有效的策略，田忌賽馬–等等第6頁(yè)，共29頁(yè)，2023年，2月20日，星期六需解決兩方面的問題：什么樣的方案最優(yōu)？如何找出最優(yōu)方案？數(shù)學(xué)規(guī)劃（最優(yōu)化）正是為解決這些問題提供理論基礎(chǔ)和求解方法。它是應(yīng)用廣泛、實(shí)用性很強(qiáng)的學(xué)科。第7頁(yè)，共29頁(yè)，2023年，2月20日，星期六數(shù)學(xué)規(guī)劃的發(fā)展史二戰(zhàn)之前，自然科學(xué)中的最優(yōu)化Fermat,1637;Newton,1670Euler,1755Lagrange,1797Cauchy，1847最速下降法Fermat,1637;

Newton,1670Euler,1755Lagrange,1797Cauchy，1847最速下降法第8頁(yè)，共29頁(yè)，2023年，2月20日，星期六二戰(zhàn)以后原蘇聯(lián)數(shù)學(xué)家康托洛維奇－下料問題和運(yùn)輸問題1939《生產(chǎn)組織與管理中的數(shù)學(xué)方法》1960《最佳資源利用的經(jīng)濟(jì)計(jì)算》1975諾貝爾經(jīng)濟(jì)學(xué)獎(jiǎng)美國(guó)Dantzig－線性規(guī)劃

1947單純型算法Kuhn和Tucker－非線性規(guī)劃

1950Kuhn-Tucker條件第9頁(yè)，共29頁(yè)，2023年，2月20日，星期六例1—運(yùn)輸問題第10頁(yè)，共29頁(yè)，2023年，2月20日，星期六目標(biāo)變量subjectto,受限制于，約束條件是第11頁(yè)，共29頁(yè)，2023年，2月20日，星期六例2—生產(chǎn)問題某廠生產(chǎn)兩種產(chǎn)品，需要三種資源，已知各產(chǎn)品的利潤(rùn)、各資源的限量和各產(chǎn)品的資源消耗系數(shù)如下表：產(chǎn)品A產(chǎn)品B資源限量勞動(dòng)力設(shè)備原材料9434510360200300利潤(rùn)元/kg70120問題：如何安排生產(chǎn)計(jì)劃，使得獲利最多？第12頁(yè)，共29頁(yè)，2023年，2月20日，星期六Model：第13頁(yè)，共29頁(yè)，2023年，2月20日，星期六例3（方程組的求解）解非線性方程組是相當(dāng)困難的一類問題，由于最優(yōu)化方法的發(fā)展，對(duì)解非線性方程組提供了一種有力的手段解非線性方程組在方程組有解的情況下，等價(jià)于求下列函數(shù)的極小值點(diǎn)：非線性最小二乘問題第14頁(yè)，共29頁(yè)，2023年，2月20日，星期六類似地，對(duì)于線性方程組Ax=b的求解也可轉(zhuǎn)化為一個(gè)最優(yōu)問題，即求解線性最小二乘問題第15頁(yè)，共29頁(yè)，2023年，2月20日，星期六一些成功的事例最優(yōu)化人員安排使美國(guó)航空公司每年節(jié)約2000萬(wàn)美元；優(yōu)化貨運(yùn)路線讓YellowFreight每年的節(jié)約超過1730萬(wàn)美元；ReynoldsMetal公司通過改進(jìn)卡車調(diào)度，提高了即時(shí)交付率，每年節(jié)約貨運(yùn)成本700萬(wàn)美元；GTE本地能力擴(kuò)張每年節(jié)約3000萬(wàn)美元。Proctor&Gamble(保潔公司)通過北美運(yùn)營(yíng)重構(gòu)，削減了20%的廠房，每年節(jié)約2億美元；DigitalEquipment通過優(yōu)化全球供應(yīng)鏈節(jié)約了3億美元；優(yōu)化水熱生成器安排讓南部公司每年節(jié)約1.4億美元；

第16頁(yè)，共29頁(yè)，2023年，2月20日，星期六數(shù)學(xué)規(guī)劃的分類根據(jù)問題的不同特點(diǎn)分類無約束極小化問題等式約束極小化問題不等式約束極小化問題一般約束極小化問題根據(jù)函數(shù)類型的分類線性規(guī)劃非線性規(guī)劃二次規(guī)劃整數(shù)規(guī)劃根據(jù)解法的分類解析方法直接方法約束最優(yōu)化問題

無約束最優(yōu)化問題第17頁(yè)，共29頁(yè)，2023年，2月20日，星期六最優(yōu)化術(shù)語(yǔ)：可行點(diǎn)（可行解）：在數(shù)學(xué)規(guī)劃中，滿足所有約束條件的點(diǎn)?？尚杏颍尚屑核锌尚悬c(diǎn)組成的集合。最優(yōu)解（全局極小點(diǎn)）:使得目標(biāo)函數(shù)取得最小值的可行解局部最優(yōu)解（局部極小點(diǎn)）任意全局極小點(diǎn)必為局部極小點(diǎn)，但反過來不成立。然而，對(duì)于凸規(guī)劃而言，局部極小點(diǎn)就是全局極小點(diǎn)。第18頁(yè)，共29頁(yè)，2023年，2月20日，星期六預(yù)備知識(shí)（多元函數(shù)分析）梯度Hesse矩陣Taylor公式極值的判別條件（必要條件、充分條件）方向?qū)?shù)第19頁(yè)，共29頁(yè)，2023年，2月20日，星期六梯度幾種特殊類型函數(shù)的梯度公式第20頁(yè)，共29頁(yè)，2023年，2月20日，星期六Hesse矩陣第21頁(yè)，共29頁(yè)，2023年，2月20日，星期六Taylor公式第22頁(yè)，共29頁(yè)，2023年，2月20日，星期六極值的判別條件一元函數(shù)：

設(shè)f(x)的定義域?yàn)閰^(qū)間D,x0為內(nèi)點(diǎn)，f(x)在點(diǎn)x0可微，若x0為極值點(diǎn)，則

必要條件：二元函數(shù)：

設(shè)f(x,y)的定義域?yàn)閰^(qū)域D,(x0,y0)為內(nèi)點(diǎn)，f(x,y)在點(diǎn)(x0,y0)可微，若(x0,y0)為極值點(diǎn)，則多元函數(shù)：第23頁(yè)，共29頁(yè)，2023年，2月20日，星期六充分條件一元函數(shù)：

設(shè)f(x)的定義域?yàn)閰^(qū)間D,x0為內(nèi)點(diǎn)，f(x)在點(diǎn)x0二次可微，

(1)若,則x0為極小點(diǎn)(2)若,則x0為極大點(diǎn)第24頁(yè)，共29頁(yè)，2023年，2月20日，星期六若

,則(x0,y0)是極值點(diǎn)。當(dāng)時(shí)，(x0,y0)是極小點(diǎn)。當(dāng)時(shí)，(x0,y0)是極大點(diǎn)。二元函數(shù)：

設(shè)f(x,y)的定義域?yàn)閰^(qū)域D,(x0,y0)為內(nèi)點(diǎn)，f(x,y)在點(diǎn)(x0,y0)二次可微，第25頁(yè)，共29頁(yè)，2023年，2月20日，星期六多元函數(shù)：(1)x0為D的一個(gè)內(nèi)點(diǎn)(2)f(x)在點(diǎn)x0二次可微(3)(4)

H(x0)>0（

H(x0)<0

）則x0是極小點(diǎn)(極大點(diǎn))。第26頁(yè)，共29頁(yè)，2023年，2月20日，星期六方向?qū)?shù)（偏導(dǎo)數(shù)導(dǎo)數(shù)）設(shè)有單位向量h=(h1,h2,...,hn)T,表示n維空間中的一個(gè)方向，則可微函數(shù)f(x)在點(diǎn)x沿h的方向?qū)?shù)為：1.函數(shù)沿各個(gè)方向的變化率2.從各個(gè)方向中求出f(x)變化最快的方向，亦即變化率最大的方向。第27頁(yè)，共29頁(yè)，2023年，2月20日，星期六對(duì)于方向?qū)?shù)，有以下結(jié)論：若，則h為f(x)在點(diǎn)x的上升方向；若，則h為f(x)在點(diǎn)x的下降方向；若，則對(duì)任何方向h，有若