線性規(guī)劃與非線性規(guī)劃

1、運(yùn)籌學(xué)線性規(guī)劃與非線性規(guī)劃線性規(guī)劃與非線性規(guī)劃是運(yùn)籌學(xué)的一個(gè)分支.運(yùn)籌學(xué)研究什么呢?運(yùn)籌學(xué)是研究“如何做出正確決策或選擇，以達(dá)到最好結(jié)果”的一門數(shù)學(xué)學(xué)科.有一句成語形象地說明了運(yùn)籌學(xué)的特點(diǎn)：運(yùn)籌帷幄，決勝千里.數(shù)學(xué)因?qū)嶋H的需要而產(chǎn)生，數(shù)學(xué)的很多重大發(fā)現(xiàn)也因?qū)嶋H的需要而出現(xiàn).數(shù)學(xué)建模競賽既因?qū)嶋H的重要需要而在世界范圍內(nèi)(在我國近十幾年)各大學(xué)蓬勃開展.沒有受到條條框框制約、富有聰明才智的大學(xué)生們，在每次競賽中都能對(duì)實(shí)際中的一些重要問題與難題給出富有新鮮創(chuàng)意的解決辦法，往往因此產(chǎn)生重大的社會(huì)效益和經(jīng)濟(jì)效益.建模競賽就是知識(shí)的“強(qiáng)行軍”.競賽會(huì)極大地激發(fā)學(xué)生們的創(chuàng)造性思維，是對(duì)學(xué)生們思考能力和動(dòng)手能

2、力的考驗(yàn).競賽能讓學(xué)生們切身感受到學(xué)習(xí)各科知識(shí)的必要性、重要性，成為學(xué)生們認(rèn)真學(xué)習(xí)的推動(dòng)力.數(shù)學(xué)建模會(huì)涉及數(shù)學(xué)的眾多學(xué)科：微分方程，運(yùn)籌學(xué)，概率統(tǒng)計(jì)，圖論，層次分析，變分法，要求建模者有較高的數(shù)學(xué)素養(yǎng)，有綜合應(yīng)用已學(xué)到的數(shù)學(xué)方法和思維對(duì)問題進(jìn)行分析、抽象及簡化的能力.數(shù)學(xué)建模既是建立實(shí)際問題的數(shù)學(xué)模型.一、最優(yōu)化模型數(shù)學(xué)建模的目的是使決策人的“利益”最大化，因此而建立的數(shù)學(xué)模型即所謂的最優(yōu)化模型.決策人在作決策時(shí)要有“科學(xué)觀”，為實(shí)現(xiàn)目標(biāo)(“利益”最大化)應(yīng)進(jìn)行“科學(xué)決策”.最優(yōu)化模型正是為實(shí)現(xiàn)科學(xué)決策而建立的數(shù)學(xué)模型，是科學(xué)決策的科學(xué)體現(xiàn).科學(xué)決策的目的是要對(duì)為實(shí)現(xiàn)目標(biāo)而提出的設(shè)計(jì)和操作最佳

3、化，最終實(shí)現(xiàn)決策人的“利益”最大化.一個(gè)最優(yōu)化模型包括決策變量、目標(biāo)函數(shù)和約束條件，它將“說明”決策變量在滿足約束條件的前提下應(yīng)使目標(biāo)函數(shù)值最優(yōu)化(最大或最小).決策變量是指影響并決定目標(biāo)實(shí)現(xiàn)的變量，其變化范圍一般是可控制的.目標(biāo)函數(shù)是指根據(jù)決策變量建立的目標(biāo)的函數(shù)表達(dá)式.約束條件是指決策變量所受的限制(用等式、不等式的函數(shù)方程表示).人們建立最優(yōu)化模型的目的是，希望通過科學(xué)的計(jì)算方法(稱為最優(yōu)化方法)找出使目標(biāo)函數(shù)值最優(yōu)(最大或最小)的決策變量的值(稱為最優(yōu)決策).實(shí)際問題的7步建模過程：第1步：表述問題.說明目標(biāo)及各種因素.第2步：分析數(shù)據(jù)或采集(或收集)并分析數(shù)據(jù).第3步：建立數(shù)學(xué)模型.

4、第4步：對(duì)模型求解.即尋找最優(yōu)決策.第5步：檢驗(yàn)、評(píng)價(jià)模型.如果與實(shí)際情況(或?qū)嶋H數(shù)據(jù))吻合，則轉(zhuǎn)到第7步，否則轉(zhuǎn)到第6步.第6步：修改或矯正模型，并返回到第1步、第2步或第3步.第7步：模型應(yīng)用，提出合理化建議.最優(yōu)化數(shù)學(xué)模型的一般形式為 (1.1)其中，是決策變量；是目標(biāo)函數(shù)；和是約束條件，前者稱為等式約束，后者稱為不等式約束.不帶約束條件的(1)式是無約束問題的模型.由滿足所有約束條件的決策向量組成的集合稱為可行域，通常記為.求解(1)是指，尋找使為目標(biāo)函數(shù)f在可行域上的最小值(或最大值).稱為最優(yōu)解，稱為最優(yōu)值.最優(yōu)解有嚴(yán)格與非嚴(yán)格和全局與局部之分.優(yōu)化模型的最優(yōu)解是指全局最優(yōu)解. 嚴(yán)

5、格極小點(diǎn) 嚴(yán)格極小點(diǎn)局部 全局 非嚴(yán)格極小點(diǎn) 非嚴(yán)格極小點(diǎn)圖1 一維函數(shù)的最優(yōu)解圖示這里指出：最優(yōu)化方法解出的多是優(yōu)化模型的局部最優(yōu)解.由于最優(yōu)化方法多為迭代法，所以取不同的初始點(diǎn)一般會(huì)得到一個(gè)或多個(gè)局部最優(yōu)解，然后再從這些局部最優(yōu)解中找出“全局”最優(yōu)解.二、線性規(guī)劃(LP) 線性規(guī)劃在銀行、教育、林業(yè)、石油、運(yùn)輸?shù)雀鞣N行業(yè)以及科學(xué)的各個(gè)領(lǐng)域中有著廣泛的應(yīng)用.1. 線性規(guī)劃模型 目標(biāo)函數(shù)、約束函數(shù)均為線性函數(shù)的最優(yōu)化模型既是所謂的線性規(guī)劃模型.(1)標(biāo)準(zhǔn)形式 (2.1)這里，約束是對(duì)決策變量的主要約束，稱為主約束，而約束(稱為非負(fù)變量)是對(duì)決策變量的符號(hào)約束；是主約束的右端常數(shù)項(xiàng)(通常不妨設(shè)為

6、非負(fù)數(shù))；稱為價(jià)值系數(shù).(2.1)式可以寫成如下矩陣形式 (2.2)其中，.決策向量，主約束右端常數(shù)向量，價(jià)值向量.(2)一般形式 (2.3)這里，約束、和是主約束，而約束和任意是符號(hào)約束，其中稱為自由變量.一般形式可以(通過如下辦法)轉(zhuǎn)化為標(biāo)準(zhǔn)形式.(i)將不等式約束轉(zhuǎn)化為等式約束引入剩余變量，將不等式約束改寫為，. (2.4)引入松弛變量，將不等式約束改寫為，. (2.5)(ii)去除自由變量去掉自由變量有兩種辦法：用非負(fù)變量的差表示自由變量設(shè)， (2.6)其中，代入到目標(biāo)函數(shù)和其它約束中便可去掉.取一個(gè)包含的等式約束(如果有的話)，比如：，由此解出， (2.7)代入到目標(biāo)函數(shù)和其它約束函

7、數(shù)中便可去掉.第一種方法將增加變量的數(shù)目，導(dǎo)致問題的維數(shù)增大.第二種方法正好相反.用(2.4)、(2.5)兩式替換(2.3)式中相應(yīng)的不等式約束，將(2.6)式或(2.7)式代入目標(biāo)函數(shù)和其它約束函數(shù)中，去掉目標(biāo)函數(shù)與主約束中的所有自由變量，最后將、和加入(2.3)式的符號(hào)約束中，(2.3)式就此轉(zhuǎn)化為標(biāo)準(zhǔn)形式的線性規(guī)劃， 一般形式與其標(biāo)準(zhǔn)形式問題的求解等價(jià)，因?yàn)檫@兩個(gè)問題的可行解一一對(duì)應(yīng)，目標(biāo)函數(shù)值對(duì)應(yīng)相等.所以如果這兩個(gè)問題之一有最優(yōu)解，那么另一個(gè)也必有最優(yōu)解，且最優(yōu)值相等.2. 線性規(guī)劃的特點(diǎn)(1)線性規(guī)劃的可行域是凸集：凸多邊形、凸多面體或空集.凸集非凸集凸多邊形 凸多面體(2)目標(biāo)函

8、數(shù)的等值面(或等值線)是平行的(超)平面(或直線).(3)如果線性規(guī)劃有最優(yōu)解，那么可行域的某個(gè)頂點(diǎn)必是最優(yōu)解.(4)求解線性規(guī)劃將出現(xiàn)下列4種情況之一.情況1：有唯一(最優(yōu))解.情況2：有無窮多(最優(yōu))解.情況3：解無界.情況4：無解.有唯一解 有無窮多解 有無界解 無解3. 一般線性規(guī)劃的解法線性規(guī)劃的解法有Dantzig單純形法，大M法，對(duì)偶單純形法，Karmarkar法，列生成法，目標(biāo)規(guī)劃，分解算法等.軟件中多為Dantzig單純形法.參考書目高等教育出版社,1989刁在筠 鄭漢鼑等. 運(yùn)籌學(xué).北京：高等教育出版社,2001 4. 特殊的線性規(guī)劃當(dāng)所有決策變量都取整數(shù)時(shí)，稱為整數(shù)規(guī)劃(

9、IP).當(dāng)所有決策變量只取0或1時(shí)，稱為0-1規(guī)劃.當(dāng)只有部分決策變量取整數(shù)時(shí)，稱為混合整數(shù)規(guī)劃(混合IP).解整數(shù)規(guī)劃的方法主要有窮舉法(對(duì)決策變量過多的問題不適用)、分枝定界法和割平面法.分枝定界法比較常用.解小規(guī)模0-1規(guī)劃的常用方法隱枚舉法.分枝定界法也適用于求解混合整數(shù)規(guī)劃.參考書目：刁在筠 鄭漢鼑等. 運(yùn)籌學(xué).北京：高等教育出版社,2001 5. 特殊的線性規(guī)劃問題及其解法(1)運(yùn)輸問題運(yùn)輸問題用“運(yùn)輸”單純形法求解.(2)轉(zhuǎn)運(yùn)問題轉(zhuǎn)運(yùn)問題可以化為運(yùn)輸問題，所以也用“運(yùn)輸”單純形法求解.(3)指派問題指派問題是特殊的0-1規(guī)劃，常用匈牙利法求解.線性規(guī)劃的算法可在Matlab“優(yōu)化

10、”工具箱中尋找.6. 線性規(guī)劃建模實(shí)例在一個(gè)線性規(guī)劃模型中，(1)決策變量應(yīng)當(dāng)完全描述要做出的決策.(2)決策者都希望由決策變量表示的目標(biāo)函數(shù)最大化(通常為收入或利潤)或最小化(通常為成本).目標(biāo)函數(shù)中的系數(shù)反映的是決策變量對(duì)目標(biāo)函數(shù)的單位貢獻(xiàn).(3)主約束條件中決策變量的系數(shù)稱為“技術(shù)”系數(shù)，這是因?yàn)榧夹g(shù)系數(shù)經(jīng)常影響用于“生產(chǎn)”不同“產(chǎn)品”的技術(shù).右端項(xiàng)常表示可用資源的數(shù)量.示例1 一家汽車公司生產(chǎn)轎車和卡車.每輛車都必須經(jīng)過車身裝配車間和噴漆車間處理. 車身裝配車間如果只裝配轎車，每天可裝配50輛；如果只裝配卡車，每天可裝配50輛.噴漆車間如果只噴轎車，每天可噴60輛；如果只噴卡車，每天可

11、噴40輛. 每輛轎車的利潤是1600元，每輛卡車的利潤是2400元.公司的生產(chǎn)計(jì)劃部門須制定一天的產(chǎn)量計(jì)劃以使公司的利潤最大化.建模過程：公司追求的目標(biāo)是其利潤的最大化，生產(chǎn)計(jì)劃部門為此要決定每一種車型的產(chǎn)量，所以定義兩個(gè)決策變量：每天生產(chǎn)的轎車數(shù)量，每天生產(chǎn)的卡車數(shù)量.公司每天的利潤為，因此該公司追求利潤最大化即為.按題意，決策變量須滿足以下3個(gè)條件(如果把每天的時(shí)間設(shè)為1，那么每天的工作時(shí)間應(yīng)該小于等于1.)： (1)裝配車間每天處理一輛轎車和一輛卡車的時(shí)間均為，所以處理輛轎車和輛卡車的時(shí)間應(yīng)滿足.(2)噴漆車間每天處理一輛轎車的時(shí)間為，處理一輛卡車的時(shí)間為，所以處理輛轎車和輛卡車的時(shí)間應(yīng)

12、滿足.(3)非負(fù)限制為負(fù)整數(shù),.該汽車公司追求利潤最大化的數(shù)學(xué)模型為如下線性規(guī)劃示例2(飲食問題) 有一個(gè)美國人的飲食方案要求他吃的所有食物都來自四個(gè)“基本食物組”之一(巧克力蛋糕、冰淇淋、蘇打水和干酪蛋糕).目前他可以消費(fèi)的食物有下列4種：胡桃巧克力糖、巧克力冰淇淋、可口可樂和菠蘿干酪蛋糕.一塊胡桃巧克力糖的價(jià)格為50美分，一勺巧克力冰淇淋的價(jià)格為20美分，一瓶可口可樂的價(jià)格為30美分，一塊菠蘿干酪蛋糕的價(jià)格為80美分.自己每天的營養(yǎng)要求，那他應(yīng)該怎樣做.表1 食物的營養(yǎng)價(jià)值數(shù)據(jù)食物類型卡路里巧克力(盎司)糖(盎司)脂肪(盎司)胡桃巧克力糖(1塊)400322巧克力冰淇淋(1勺)200224

13、可口可樂(1瓶)150041菠蘿干酪蛋糕(1塊)500045建模過程：這個(gè)美國人追求的目標(biāo)是使飲食的費(fèi)用最少.因此這個(gè)美國人必須做出決策：對(duì)于每種食物，每天應(yīng)當(dāng)吃多少.因此，需要定義下列決策變量：每天吃的胡桃巧克力糖的數(shù)量(單位：塊)，每天吃的巧克力冰淇淋的數(shù)量(單位：勺)，每天喝的可口可樂的數(shù)量(單位：瓶)，每天吃的菠蘿干酪蛋糕的數(shù)量(單位：塊).他追求的目標(biāo)是使飲食的費(fèi)用最少，因此目標(biāo)函數(shù)為.決策變量必須滿足以下4個(gè)條件：(1) 每天攝取的卡路里至少必須達(dá)到500卡路里.即.(2)每天攝取的巧克力至少必須達(dá)到6盎司.即.(3)每天攝取的糖至少必須達(dá)到10盎司.即.(4)每天攝取的脂肪至少必

14、須達(dá)到8盎司.即.以及非負(fù)限制.該美國人飲食費(fèi)用最少的數(shù)學(xué)模型為這個(gè)問題的最優(yōu)解是，表示每天最少花90美分便可得到符合飲食要求的750卡路里、6盎司巧克力、10盎司糖和13盎司脂肪. 列出更現(xiàn)實(shí)的食物和營養(yǎng)需求的飲食問題是計(jì)算機(jī)解決的最早的LP之一.整數(shù)規(guī)劃已用于計(jì)劃每周或每月的公共飲食業(yè)菜單.菜單計(jì)劃模型包含反映可口性和多樣性要求的約束條件.示例3 某服務(wù)部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人，周五至少需要80人，周六和周日至少需要90人.規(guī)定應(yīng)聘者需連續(xù)工作5天.試確定聘用方案：使在滿足需要的條件下聘用的總?cè)藬?shù)最少.建模過程：該服務(wù)部門追求的目標(biāo)是一周中聘用的總?cè)藬?shù)

15、最少.該服務(wù)部門因此必須做出決策：每天聘用多少人.為此，定義以下決策決量：分別表示周一至周日聘用的人數(shù).因此目標(biāo)函數(shù)為.決策變量必須滿足以下7個(gè)條件：周一工作的雇員應(yīng)是周四到周一聘用的，按照需要至少有50人，即.類似地，有人數(shù)應(yīng)該是整數(shù)，所以決策變量須是非負(fù)的整數(shù)變量，即 為非負(fù)整數(shù)，.該服務(wù)部門聘用總?cè)藬?shù)最少的數(shù)學(xué)模型是如下的整數(shù)規(guī)劃模型：示例4(工作調(diào)度問題)表1 郵局的需要工作日 需要的專職員工數(shù)量 工作日 需要專職員工的數(shù)量1=星期一 172=星期二 133=星期三 154=星期四 195=星期五 146=星期六 167=星期日 11首先來看一個(gè)不正確的模型.有許多學(xué)生定義決策變量為第

16、天上班員工的數(shù)量(第1天=星期一，第2天=星期二，依次類推),然后推出郵局專職員工的數(shù)量=(星期一上班員工的數(shù)量+星期二上班員工的數(shù)量+星期日上班員工的數(shù)量)/5，于是得到如下目標(biāo)函數(shù).添加約束條件(第天需要的員工數(shù)量)和符號(hào)限制條件后，得到如下不正確的線性規(guī)劃模型：為非負(fù)整數(shù),.這里目標(biāo)函數(shù)是專職員工的數(shù)量的5倍，問題是約束條件不能反映員工連續(xù)工作五天然后休息兩天的事實(shí).建模過程：這個(gè)郵局追求的目標(biāo)是聘用盡可能少的專職員工.正確表述這個(gè)問題的關(guān)鍵是，定義的決策變量不應(yīng)該是每天有多少人上班，而是一周中每天有多少人開始上班.定義決策變量：=第天開始上班員工的數(shù)量.例如，是星期一開始上班員工的數(shù)量

17、(這些人從星期一工作到星期五).那么郵局(專職員工的數(shù)量)=(星期一開始上班員工的數(shù)量)+(星期二開始上班員工的數(shù)量)+(星期日開始上班員工的數(shù)量).由于每個(gè)員工都只在一周的某一天開始上班，所以這個(gè)表達(dá)式不會(huì)重復(fù)計(jì)算員工.因此，追求聘用盡可能少的專職員工的目標(biāo)函數(shù)為決策變量滿足以下約束條件：在星期一上班員工的數(shù)量不少于17人：；在星期二上班員工的數(shù)量不少于13人：；在星期三上班員工的數(shù)量不少于15人：；在星期四上班員工的數(shù)量不少于19人：；在星期五上班員工的數(shù)量不少于14人：；在星期六上班員工的數(shù)量不少于16人：；在星期日上班員工的數(shù)量不少于11人：.及符號(hào)限制條件：為非負(fù)整數(shù),.郵局追求聘用

18、盡可能少的專職員工的調(diào)度方案數(shù)學(xué)模型為 ,為非負(fù)整數(shù),.這個(gè)模型的一個(gè)最優(yōu)解為，最優(yōu)值. 該模型存在另外一個(gè)問題：只有在周一、周二開始上班的員工才能在周末休息，而在其它時(shí)間開始上班的員工永遠(yuǎn)不會(huì)有在公休日與家人團(tuán)聚的機(jī)會(huì).顯然這不公平合理.從該模型的解出發(fā)，我們可以設(shè)計(jì)出如下公平合理的以23周為一個(gè)輪轉(zhuǎn)周期的員工調(diào)度方案：·第1-4周：在星期一開始上班·第5-8周：在星期二開始上班·第9-10周：在星期三開始上班·第11-16周：在星期四開始上班·第17-20周：在星期六開始上班·第21-23周：在星期日開始上班員工1將遵守這個(gè)調(diào)度方

19、案23周，員工2從第2周開始遵守這個(gè)調(diào)度方案23周(在星期一開始上班的時(shí)間為3周，在星期二開始上班的時(shí)間為4周，在星期日開始上班的時(shí)間為3周，在星期一開始上班的時(shí)間為1周).以這樣的方式繼續(xù)下去，就可以為每個(gè)員工制定一個(gè)23周調(diào)度方案.例如，員工13的調(diào)度方案如下：·第1-4周：在星期四開始上班·第5-8周：在星期六開始上班·第9-11周：在星期日開始上班·第12-15周：在星期一開始上班·第16-19周：在星期二開始上班·第20-21周：在星期三開始上班·第22-23周：在星期四開始上班本示例提醒我們，所建立的模型一定要考

20、慮合理性，符合實(shí)際.而本示例更符合實(shí)際的考慮是員工還有年休假.在郵局這個(gè)示例中，如果郵局可以同時(shí)使用專職員工和兼職員工來滿足每天的需要，且在每一周，專職員工必須連續(xù)工作5天，每天工作8小時(shí)；兼職員工必須連續(xù)工作5天，每天工作4小時(shí). 專職員工的工資是每小時(shí)15美元，而兼職員工的工資只有每小時(shí)10美元(沒有附加福利).工會(huì)把每周的兼職勞動(dòng)限制在25%，表述一個(gè)LP，使這個(gè)郵局每周的勞動(dòng)力成本最少.比示例5的單階段工作調(diào)度模型更復(fù)雜的是多階段工作調(diào)度模型.類似的還有多階段庫存模型、多階段財(cái)務(wù)管理(投資)模型等.示例5(指派問題) 某班準(zhǔn)備從5名游泳隊(duì)員中選4人，組隊(duì)參加學(xué)校的m混合泳接力比賽.5名

21、隊(duì)員4種泳姿的百米平均成績?nèi)绫?所示，問應(yīng)該怎樣選拔接力隊(duì)成員?表1 5名隊(duì)員4種泳姿的百米平均成績(秒)數(shù)據(jù)隊(duì)員甲乙丙丁戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4建模過程：該班追求的目標(biāo)是接力隊(duì)的成績最好.該班因此要做出決策：從5名隊(duì)員中選出4人，每人一種泳姿，且4人的泳姿各不相同(容易想到的一個(gè)辦法是窮舉法，組成接力隊(duì)的方案共有5!=120種.).設(shè)分別代表甲、乙、丙、丁和戊隊(duì)員，分別代表蝶泳、仰泳、蛙泳和自由泳泳姿，表示隊(duì)員的第種泳姿的百米平均成績.定義決策決量：若選擇隊(duì)員參

22、加泳姿的比賽()，則，否則.該班追求的目標(biāo)是接力隊(duì)的成績最好(只要對(duì)每一方案的成績作比較，即可找出最優(yōu)方案，但顯然這不是解決問題的好辦法.隨著問題規(guī)模的變大，窮舉法的計(jì)算量將是無法接受的).當(dāng)隊(duì)員入選泳姿時(shí)，表示他的成績，否則，因此目標(biāo)函數(shù)為.決策變量必須滿足以下3個(gè)條件：(1) 每人最多只能入選4種泳姿之一，即，.(2)每種泳姿必須有1人而且只能有1人入選，即，.(3)取值受限或，.該班追求接力隊(duì)成績最好的數(shù)學(xué)模型為0-1規(guī)劃：三、非線性規(guī)劃(NLP)非線性規(guī)劃廣泛存在于科學(xué)與工程領(lǐng)域.1.非線性規(guī)劃模型目標(biāo)函數(shù)、約束函數(shù)中至少有一個(gè)非線性函數(shù)的最優(yōu)化模型既是所謂的非線性規(guī)劃模型.其中函數(shù)中

23、至少有一個(gè)為非線性函數(shù).非線性規(guī)劃有無約束問題與有約束問題之分.2.非線性規(guī)劃的特點(diǎn)非線性規(guī)劃的可行域及最優(yōu)解的情況遠(yuǎn)比線性規(guī)劃的可行域及最優(yōu)解復(fù)雜的多：可能有最優(yōu)解，也可能沒有最優(yōu)解；約束問題的最優(yōu)解可能在可行域的內(nèi)部，也可能在可行域的邊界上.一些常用概念：等值面(線)函數(shù)值相等的決策變量曲面(曲線).上升/下降方向至少在局部范圍內(nèi)，函數(shù)值升的方向/函數(shù)值降的方向.梯度多元函數(shù)的“一階導(dǎo)數(shù)”，由函數(shù)的偏導(dǎo)數(shù)組成的向量. 當(dāng)梯度連續(xù)時(shí)，若，則必垂直于過點(diǎn)的等值面；梯度的方向是函數(shù)在點(diǎn)具有最大變化率的方向.方向?qū)?shù)函數(shù)在某方向上的變化率(下式中是方向上的單位向量).若，即，則方向是在點(diǎn)處的上升方

24、向；若，即，則方向是在點(diǎn)處的下降方向.海賽矩陣多元函數(shù)的“二階導(dǎo)數(shù)”，由函數(shù)的二階偏導(dǎo)數(shù)組成的矩陣.空間中由點(diǎn)和方向所確定的直線方程為.圖2 直線的幾何圖示3.非線性規(guī)劃的解法(1)非線性規(guī)劃基本解法基本解法的迭代格式一般為, k = 0,1,.稱為初始點(diǎn)，為處的搜索方向，為步長因子，滿足，且仍在可行域內(nèi).判斷是否為最優(yōu)解.若是，則輸出和；否則，繼續(xù)迭代.由基本解法解出的一般是局部最優(yōu)解.的確定方法直線搜索(一維優(yōu)化問題的數(shù)值迭代方法)，.直線搜索方法有“精確的”對(duì)分法、黃金分割法、拋物線插值法和不精確的直線搜索技術(shù).的確定方法各種優(yōu)化方法求解無約束問題的基本方法按確定方法的不同，有使用導(dǎo)數(shù)的

25、最速下降法、Newton法、阻尼-Newton法、共軛梯度法、逆Newton法(DFP法、BFGS法)等，有不使用導(dǎo)數(shù)的單純形替換法、步長加速法、Power法等，以及最小二乘法.最速下降法, k = 0,1,.特點(diǎn)：簡單，存儲(chǔ)量小，鋸齒現(xiàn)象.線性收斂.Newton法：, k = 0,1,.特點(diǎn)：對(duì)目標(biāo)函數(shù)的要求高，計(jì)算量、存儲(chǔ)量大.二階收斂.阻尼-Newton法：, k = 0,1,.特點(diǎn)：比Newton法相對(duì)有效的方法，計(jì)算量、存儲(chǔ)量大.F-R共軛梯度法：, k = 0,1,，其中.特點(diǎn)：存儲(chǔ)量小.是二次收斂算法.超線性收斂.DFP法：, k = 0,1,，其中.特點(diǎn)：是二次收斂算法.是擬N

26、ewton法.超線性收斂.單純形替換法、步長加速法、Power法等適用于目標(biāo)函數(shù)的導(dǎo)數(shù)不存在或?qū)?shù)過于復(fù)雜的情形.最小二乘法是求解最小二乘問題的特定解法.求解約束問題的基本方法有Z-容許方向法、梯度投影法、外點(diǎn)法(外部罰函數(shù)法)、內(nèi)點(diǎn)法(內(nèi)部罰函數(shù)法)、乘子法、線性化法、簡約梯度法等.Z-容許方向法：利用線性規(guī)劃得到搜索方向，然后再通過受限的直線搜索確定步長因子.梯度投影法：利用對(duì)梯度投影的方式得到搜索方向，然后再通過受限的直線搜索確定步長因子.外點(diǎn)法、內(nèi)點(diǎn)法、乘子法：通過求解一系列的無約束問題解約束問題.而這一系列無約束問題的目標(biāo)函數(shù)則是根據(jù)目標(biāo)函數(shù)及約束函數(shù)，通過“懲罰”方式產(chǎn)生. (2)

27、非線性規(guī)劃智能算法遺傳算法、蟻群算法、粒子群算法、禁忌搜索算法.非線性規(guī)劃的算法可在Matlab“優(yōu)化”工具箱中尋找.參考書目 現(xiàn)代應(yīng)用數(shù)學(xué)手冊(cè)編委會(huì).現(xiàn)代應(yīng)用數(shù)學(xué)手冊(cè)運(yùn)籌學(xué)與最優(yōu)化理論卷.北京：清華大學(xué)出版社,19984. 特殊的非線性規(guī)劃問題及其解法(1)二次規(guī)劃(QPP)Wolfe法.(2)數(shù)據(jù)擬合問題(最小二乘問題)最小二乘法5. 非線性規(guī)劃建模實(shí)例示例1 某公司有6個(gè)建筑工地要開工，每個(gè)工地的位置(用平面坐標(biāo)表示，距離單位：km)及水泥日用量(單位：(噸)由表1給出.目前有兩個(gè)臨時(shí)料場位于和，日儲(chǔ)量各有20.請(qǐng)回答以下兩個(gè)問題：(1)假設(shè)從料場到工地之間均有直線道路相連，試制定每天從

28、A、B兩料場分別向各工地運(yùn)送水泥的供應(yīng)計(jì)劃，使總的噸公里數(shù)最小.(2)為進(jìn)一步減少噸公里數(shù)，打算舍棄目前的兩個(gè)臨時(shí)料場，修建兩個(gè)新料場，日儲(chǔ)量仍各為20，問建在何處最佳，可以節(jié)省多少噸公里數(shù).表1 工地的位置及水泥日用量的數(shù)據(jù)料場1234561.258.750.55.7537.251.250.754.7556.57.753547611建模過程：公司追求的目標(biāo)是每天從A、B兩料場分別向各工地運(yùn)送水泥總的噸公里數(shù)最小.為表述該問題，設(shè)工地的位置與水泥日用量分別為和()，料場位置及其日儲(chǔ)量分別為和().定義決策變量(,)：料場向工地的運(yùn)送量(,)，在問題(2)中，新建料場位置也是決策變量.公司追求總的噸公里數(shù)最小的目標(biāo)函數(shù)為.決策變量(,)必須滿足以下約束條件：(i)滿足各工地的水泥日用量.(ii)各料場的運(yùn)送量不能超過日儲(chǔ)量.(iii)符號(hào)限制條件, ,.(1)公司追求總的噸公里數(shù)最小的數(shù)學(xué)模型是如下線性規(guī)劃模型;, ,.這個(gè)模型的解，即料場A、B向6個(gè)工地運(yùn)送水泥的計(jì)劃為工地1 工地2 工地3 工地4 工地5 工地6料場A料場B3 5 0 7 0 10 0 4 0 6 1