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

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

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

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

4、建立數(shù)學(xué)模型.第4步：對模型求解.即尋找最優(yōu)決策.第5步：檢驗、評價模型.如果與實際情況（或?qū)嶋H數(shù)據(jù)）吻合，則轉(zhuǎn)到第7步，否則轉(zhuǎn) 到第6步.第6步：修改或矯正模型，并返回到第1步、第2步或第3步.第7步：模型應(yīng)用，提出合理化建議.最優(yōu)化數(shù)學(xué)模型的一般形式為maxz = f （x，x，,x ）; TOC o 1-5 h z 12n（或 min）（1.1）s.t. g （x，x，x ） = 0，i = 1，p，i 1 2ng （x，x，,x ） 0，i = p +1，,m.i12n其中，x j （ j = 1,n）是決策變量；乙=f （氣,%，,七）是目標函數(shù)；g （x，X，x ） = 0（，=

5、1，p）和 g （x，x，x ） 0（i = p +1，m）是約束條件，i 12 ni 12 n前者稱為等式約束，后者稱為不等式約束.不帶約束條件的（1）式是無約束問題的模型.由滿足所有約束條件的決策向量x =（氣,x2，.，xn）T組成的集合稱為可行域，通常記 為D.求解（1）是指，尋找x * = （x*, x*，.，x*）T G D使z = f （x*, x；，,x*）為目標函數(shù)f在可行 域D上的最小值（或最大值）.x*稱為最優(yōu)解，f （x*,x：,x*）稱為最優(yōu)值.最優(yōu)解有嚴格與非嚴格和全局與局部之分.優(yōu)化模型的最優(yōu)解是指全局最優(yōu)解.嚴格極小點一嚴格極小點全局一非嚴格極小點一非嚴格極小點

6、圖1 一維函數(shù)的最優(yōu)解圖示這里指出：最優(yōu)化方法解出的多是優(yōu)化模型的局部最優(yōu)解.由于最優(yōu)化方法多為迭代法， 所以取不同的初始點一般會得到一個或多個局部最優(yōu)解，然后再從這些局部最優(yōu)解中找出 “全局”最優(yōu)解.二、線性規(guī)劃（LP）線性規(guī)劃在銀行、教育、林業(yè)、石油、運輸?shù)雀鞣N行業(yè)以及科學(xué)的各個領(lǐng)域中有著 廣泛的應(yīng)用.線性規(guī)劃模型目標函數(shù)、約束函數(shù)均為線性函數(shù)的最優(yōu)化模型既是所謂的線性規(guī)劃模型（1）標準形式min z = cx + c x + c x ;（或 max）1 12 2n ni = 1,，m,（2.1）st. a x + a x + a x = b,i1 1 i 2 2in n ix 0, j

7、= 1,.,n.這里，約束a x + a x + a x = b (i = 1,m)是對決策變量的主要約束，稱為主約束 i1 1 i 2 2in n i而約束x, 0( j = 1,n) (x,(j = 1,n)稱為非負變量)是對決策變量的符號約束； 七(i = 1,m)是主約束的右端常數(shù)項(通常不妨設(shè)為非負數(shù))；值系數(shù).c j (j = L,n)稱為價(2)式可以寫成如下矩陣形式,min z = ctx;(或 max)s.t. Ax = b,_x 0.(2.2)其中，a11a12.a1nc1ba21.a22:.a2n:_,c =c:2_,x=x:2_,b =b:2Ia m1am2.amn)n

8、 j n b, 0, j = 1,q,x,任意,j = q +1,n.i = 1,p,i = p +1,，u,i = u +1,，m,(2.3)這里，約a x + a x + a xi1 1i 2 2in na x + a x +i1 1i 2 2in ni(j = q +1,n)是符號約束，其中xj (j = q +1,n)稱為自由變量.一般形式可以(通過如下辦法)轉(zhuǎn)化為標準形式.=b (i = L，p)i(i = p +1,u) + a x 0(j = 1,q)一一一 ja x + a x + a xi1 1 i 2 2in n、和和七任意(i)將不等式約束轉(zhuǎn)化為等式約束引入剩余變量*0將

9、不等式約束a x + a x + a x b改寫為i1 1 i 2 2in n ia x + a x + a x s = b , i = p +1,，u .i1 1i 2 2in n i i(2.4)引入松弛變量匕0將不等式約束a x + a x + a x 0，x- 0，代入到目標函數(shù)和其它約束中便可去掉x取一個包含x的等式約束(如果有的話)，比如：ja x ；F a x ；F a x = b，i1 1ij jin n i由此解出baa(2.7)x = H x ，, , in x ，j aa 1 a n代入到目標函數(shù)和其它約束函數(shù)中便可去掉.第一種方法將增加變量的數(shù)目，導(dǎo)致問題的維數(shù)增大.第

10、二種方法正好相反.用(2.4)、(2.5)兩式替換(2.3)式中相應(yīng)的不等式約束，將(2.7)式代入目標函數(shù)和其它 約束函數(shù)中，去掉目標函數(shù)與主約束中的所有自由變量，最后將s 0(i = p +1,.,u)、ie 0(i = u +1,.,m)和 x+ 0,x- 0( j = q +1,n)加入(2.3)式的符號約束中，(2.3)ij j式就此轉(zhuǎn)化為標準形式的線性規(guī)劃min z = cx + + c x + c (x + x + ) + + c (x + x+);(或max)1 1q qq;1 q;1q;1n n nst. a x + a x + a (x ; x ; )+ a (x ; x

11、;) = b, i = 1,p,i1 1iq qiq;1 q;1q;1in n n ia x ; + a x ; a (x ; x ; ) ; ; a (x ; x ;) s b, i = p ;1,u,i1 1iq qiq;1q;1q;1innniia x + a x ; a (x ; x ; )+ a (x ; x +) ; e 0, j = 1,q; x ; 0, x- 0, j = q ;1,n;s 0,i = p ;1,，u;e 0,i = u ;1,m.一般形式與其標準形式問題的求解等價，因為這兩個問題的可行解一一對應(yīng)，目標函數(shù) 值對應(yīng)相等.所以如果這兩個問題之一有最優(yōu)解，那么另一

12、個也必有最優(yōu)解，且最優(yōu)值相等.線性規(guī)劃的特點線性規(guī)劃的可行域是凸集：凸多邊形、凸多面體或空集.凸集非凸集凸多邊形凸多面體（2）目標函數(shù)的等值面（或等值線）是平行的（超）平面（或直線）.如果線性規(guī)劃有最優(yōu)解，那么可行域的某個頂點必是最優(yōu)解求解線性規(guī)劃將出現(xiàn)下列4種情況之一.情況1：有唯一（最優(yōu)）解.情況2：有無窮多（最優(yōu)）解.情況3：解無界.情況4：無解.有唯一解 有無窮多解 有無界解 無解線性規(guī)劃的解法線性規(guī)劃的解法有Dantzig單純形法，大M法，對偶單純形法，Karmarkar法，列生成 法，目標規(guī)劃，分解算法等.軟件中多為Dantzig單純形法.參考書目：薛嘉慶.線性規(guī)劃.北京：高等教育

13、出版社,1989刁在筠 鄭漢鼐等.運籌學(xué).北京：高等教育出版社,2001特殊的線性規(guī)劃當所有決策變量都取整數(shù)時，稱為整數(shù)規(guī)劃（IP）.當所有決策變量只取0或1時，稱為0-1規(guī)劃.當只有部分決策變量取整數(shù)時，稱為混合整數(shù)規(guī)劃（混合IP）.解整數(shù)規(guī)劃的方法主要有窮舉法（對決策變量過多的問題不適用）、分枝定界法和割平面 法.分枝定界法比較常用.解小規(guī)模0-1規(guī)劃的常用方法一一隱枚舉法.分枝定界法也適用于求解混合整數(shù)規(guī)劃.參考書目：刁在筠鄭漢鼐等.運籌學(xué).北京：高等教育出版社,2001胡運權(quán).運籌學(xué)基礎(chǔ)及應(yīng)用.北京：高等教育出版社,2004特殊的線性規(guī)劃問題及其解法（1）運輸問題運輸問題用“運輸”單純

14、形法求解.（2 ）轉(zhuǎn)運問題轉(zhuǎn)運問題可以化為運輸問題，所以也用“運輸”單純形法求解（3 ）指派問題指派問題是特殊的0-1規(guī)劃，常用匈牙利法求解.線性規(guī)劃的算法可在Mat lab “優(yōu)化”工具箱中尋找.線性規(guī)劃建模實例在一個線性規(guī)劃模型中，決策變量應(yīng)當完全描述要做出的決策.決策者都希望由決策變量表示的目標函數(shù)最大化(通常為收入或利潤)或最小化(通 常為成本).目標函數(shù)中的系數(shù)反映的是決策變量對目標函數(shù)的單位貢獻.主約束條件中決策變量的系數(shù)稱為“技術(shù)”系數(shù)，這是因為技術(shù)系數(shù)經(jīng)常影響用于 “生產(chǎn)，不同“產(chǎn)品，的技術(shù).右端項常表示可用資源的數(shù)量.示例1 一家汽車公司生產(chǎn)轎車和卡車.每輛車都必須經(jīng)過車身裝

15、配車間和噴漆車間處 理.車身裝配車間如果只裝配轎車，每天可裝配50輛；如果只裝配卡車，每天可裝配50 輛.噴漆車間如果只噴轎車，每天可噴60輛；如果只噴卡車，每天可噴40輛.每輛轎車的 利潤是1600元，每輛卡車的利潤是2400元公司的生產(chǎn)計劃部門須制定一天的產(chǎn)量計劃以 使公司的利潤最大化.建模過程：公司追求的目標是其利潤的最大化，生產(chǎn)計劃部門為此要決定每一種車型的 產(chǎn)量，所以定義兩個決策變量：氣=每天生產(chǎn)的轎車數(shù)量，=每天生產(chǎn)的卡車數(shù)量.公司每天的利潤為1600氣+ 2400%，因此該公司追求利潤最大化即為 max z = 1600 x + 2400 x .按題意，決策變量須滿足以下3個條件

16、(如果把每天的時間設(shè)為1，那么每天的工作時間應(yīng)該小于等于1.)：(1)裝配車間每天處理一輛轎車和一輛卡車的時間均為二，所以處理x輛轎車和x輛 5012卡車的時間應(yīng)滿足-1 x + x 150 1 50 2噴漆車間每天處理一輛轎車的時間為土1處理一輛卡車的時間為40,所以處理輛轎車和x2輛卡車的時間應(yīng)滿足1160 七 + 40 x2非負限制xj為負整數(shù)，j = 1,2 .該汽車公司追求利潤最大化的數(shù)學(xué)模型為如下線性規(guī)劃max z = 1600 x + 2400 x ；,1. 11 八 2s.t. x + x 1,50 1 50 211x + x 500.（2）每天攝取的巧克力至少必、須達到2 6

17、盎司.即43x + 2x 6.（3）每天攝取的糖至少必須達到10盎司.即22 x + 2 x + 4 x + 4 x 10.（4） 每天攝取的脂肪至少必須達到8盎司.即42 x + 4 x + X + 5 X 8.以及非負限制1234X. 0, j = 1,2,3,4.該美國人飲食費用最少的數(shù)學(xué)模型為max z = 50 x + 20 x + 30 x + 80 x ；s.t. 400 x + 200 x +150X + 500 x 500,12343x + 2x 6,2x + 2x + 4x + 4x 10,2x + 4x + x + 5x 8,x 0, i = 1,2,3,4.這個問題的最

18、優(yōu)解是氣=X4 = 0,X2 = 3,X3 = 1,z = 90，表示每天最少花90美分便可得到符 合飲食要求的750卡路里、6盎司巧克力、10盎司糖和13盎司脂肪.列出更現(xiàn)實的食物和營養(yǎng)需求的飲食問題是計算機解決的最早的LP之一.整數(shù)規(guī)劃已 用于計劃每周或每月的公共飲食業(yè)菜單.菜單計劃模型包含反映可口性和多樣性要求的約束 條件.示例3某服務(wù)部門一周中每天需要不同數(shù)目的雇員：周一到周四每天至少需要50人， 周五至少需要80人，周六和周日至少需要90人.規(guī)定應(yīng)聘者需連續(xù)工作5天.試確定聘用方 案：使在滿足需要的條件下聘用的總?cè)藬?shù)最少.建模過程：該服務(wù)部門追求的目標是一周中聘用的總?cè)藬?shù)最少.該服務(wù)

19、部門因此必須做 出決策：每天聘用多少人.為此，定義以下決策決量：X ,X，,X分別表示周一至周日聘用的人數(shù). TOC o 1-5 h z 127因此目標函數(shù)為z - X + X + X + X + X + X + X .1234567決策變量必須滿足以下7個條件：周一工作的雇員應(yīng)是周四到周一聘用的，按照需要至少有50人，即x + x + x + x + x 5014567類似地，有x + x + x + x + x 50,12567x + x + x + x + x 50,12367x + x + x + x + x 50,12347x + x + x + x + x 80,12345x +

20、x + x + x + x 90,23456x + x + x + x + x 90.34567人數(shù)應(yīng)該是整數(shù)，所以決策變量須是非負的整數(shù)變量，即X,為非負整數(shù)，i = 1,2,7 .該服務(wù)部門聘用總?cè)藬?shù)最少的數(shù)學(xué)模型是如下的整數(shù)規(guī)劃模型：min z = X + X + X + X + X + X + x ；1234567s.t. X + X + X + X + X 50,14567x + x + x + x + x 50,12567x + x + x + x + x 50,12367x + x + x + x + x 50,12347x + x + x + x + x 80,12345x +

21、 x + x + x + x 90,23456x + x + x + x + x 90, 34567 X,為非負整數(shù),i = 1,2,.,7.示例4（工作調(diào)度問題）在每周的不同工作日，一個郵局需要不同數(shù)量的專職員工.表1 給出了每天需要的專職員工的數(shù)量.工會章程規(guī)定：每個專職員工每周必須連續(xù)工作五天， 然后休息兩天.這個郵局希望通過只使用專職員工來滿足每天的需要，那么這個郵局至少要 聘用多少專職員工.表1郵局的需要工作日需要的專職員工數(shù)量工作日需要專職員工的數(shù)量1=星期一175=星期五142=星期二136=星期六163=星期三157=星期日114二星期四19首先來看一個不正確的模型.有許多學(xué)生

22、定義決策變量X,為第i天上班員工的數(shù)量（第1 天=星期一，第2天=星期二，依次類推），然后推出郵局專職員工的數(shù)量=（星期一上班員工的 數(shù)量+星期二上班員工的數(shù)量+星期日上班員工的數(shù)量）/5，于是得到如下目標函數(shù)z = X + X + X + X + X + X + X .1234567添加約束條件X, （第i天需要的員工數(shù)量）和符號限制條件X, 0（i = 1,2,7）后，得到如 下不正確的線性規(guī)劃模型：min z = x + x + x + x + x + x + x ; HYPERLINK l bookmark66 o Current Document s.t. x 17,1x 13,2x

23、 15,3x 19,4x 14,12345675x 16,6x 11, x,為非負整數(shù)，=1,2,7 .這里目標函數(shù)是專職員工的數(shù)量的5倍，問題是約束條件不能反映員工連續(xù)工作五天然后休 息兩天的事實.建模過程：這個郵局追求的目標是聘用盡可能少的專職員工.正確表述這個問題的關(guān)鍵 是，定義的決策變量不應(yīng)該是每天有多少人上班，而是一周中每天有多少人開始上班.定義 決策變量：x,二第，天開始上班員工的數(shù)量.例如，x是星期一開始上班員工的數(shù)量（這些人從星期一工作到星期五）.那么郵局（專職員 工的數(shù)量）=（星期一開始上班員工的數(shù)量）+ （星期二開始上班員工的數(shù)量）+（星期日開始 上班員工的數(shù)量）.由于每個

24、員工都只在一周的某一天開始上班，所以這個表達式不會重復(fù)計 算員工.因此，追求聘用盡可能少的專職員工的目標函數(shù)為z = x + x + x + x + x + x + x ; TOC o 1-5 h z 1234567決策變量滿足以下約束條件：在星期一上班員工的數(shù)量不少于17人：x + x + x + x + x 17 ；14567在星期二上班員工的數(shù)量不少于13人：x + x + x + x + x 13 ；1 2 567在星期三上班員工的數(shù)量不少于15人：x + x + x + x + x 15 ；1 2 367在星期四上班員工的數(shù)量不少于19人：x + x + x + x + x 19 ；

25、12347在星期五上班員工的數(shù)量不少于14人：x + x + x + x + x 14 ； 12345 在星期六上班員工的數(shù)量不少于16人：x + x + x + x + x 16 ； 23456在星期日上班員工的數(shù)量不少于11人：x + x + x + x + x 11.34567及符號限制條件：x,為非負整數(shù)，, = 1,2,7 .郵局追求聘用盡可能少的專職員工的調(diào)度方案數(shù)學(xué)模型為min z = x + x + x + x + x + x + x ;1234567+ x + x + x + x 17,s.t. x1x1 + x2x1 + x2 + x3x + x + x + x123456

26、7+ x + x + x 13,+ x + x 15 ,+ x 19, 14.x + x + x + x + x12345x + x + x + x + x23456x + x + x + x + x3456716,11=3，最優(yōu)值z = 23.x,為非負整數(shù)，, = 1,2,7 .這個模型的一個最優(yōu)解為x = 4, x = 4, x = 2, x = 6, x = 0, x = 4, x1234567該模型存在另外一個問題：只有在周一、周二開始上班的員工才能在周末休息，而在其 它時間開始上班的員工永遠不會有在公休日與家人團聚的機會.顯然這不公平合理.從該模型的解出發(fā)，我們可以設(shè)計出如下公平合

27、理的以23周為一個輪轉(zhuǎn)周期的員工調(diào) 度方案：第1-4周：在星期一開始上班第5-8周：在星期二開始上班第9-10周：在星期三開始上班第11-16周：在星期四開始上班第17-20周：在星期六開始上班第21-23周：在星期日開始上班員工1將遵守這個調(diào)度方案23周，員工2從第2周開始遵守這個調(diào)度方案23周（在星期一 開始上班的時間為3周，在星期二開始上班的時間為4周，在星期日開始上班的時間為 3周，在星期一開始上班的時間為1周）.以這樣的方式繼續(xù)下去，就可以為每個員工制定一 個23周調(diào)度方案.例如，員工13的調(diào)度方案如下：第1-4周：在星期四開始上班第5-8周：在星期六開始上班第9-11周：在星期日開

28、始上班第12-15周：在星期一開始上班第16-19周：在星期二開始上班第20-21周：在星期三開始上班第22-23周：在星期四開始上班本示例提醒我們，所建立的模型一定要考慮合理性，符合實際.而本示例更符合實際的 考慮是員工還有年休假.在郵局這個示例中，如果郵局可以同時使用專職員工和兼職員工來滿足每天的需要，且 在每一周，專職員工必須連續(xù)工作5天，每天工作8小時；兼職員工必須連續(xù)工作5天，每 天工作4小時.專職員工的工資是每小時15美元，而兼職員工的工資只有每小時10美元（沒 有附加福利）.工會把每周的兼職勞動限制在25%，表述一個LP，使這個郵局每周的勞動力成 本最少.比示例5的單階段工作調(diào)度

29、模型更復(fù)雜的是多階段工作調(diào)度模型.類似的還有多階段庫存模型、多階段財務(wù)管理（投資）模型等.示例5（指派問題）某班準備從5名游泳隊員中選4人，組隊參加學(xué)校的4 x 100 m混合 泳接力比賽.5名隊員4種泳姿的百米平均成績?nèi)绫?所示，問應(yīng)該怎樣選拔接力隊成員？表1 5名隊員4種泳姿的百米平均成績（秒）數(shù)據(jù)隊員甲乙丙丁戊蝶泳66.857.2787067.4仰泳75.66667.874.271蛙泳8766.484.669.683.8自由泳58.65359.457.262.4建模過程：該班追求的目標是接力隊的成績最好.該班因此要做出決策：從5名隊員中 選出4人，每人一種泳姿，且4人的泳姿各不相同（容易

30、想到的一個辦法是窮舉法，組成接 力隊的方案共有5!=120種.）.設(shè)i = 1,2,3,4,5分別代表甲、乙、丙、丁和戊隊員，j = 1,2,3,4分別代表蝶泳、仰泳、 蛙泳和自由泳泳姿，%表示隊員i的第j種泳姿的百米平均成績.定義決策決量、：若選擇隊員i參加泳姿j的比賽（i = 1,2,3,4,5, j = 1,2,3,4），則 X = 1，否則氣=0.該班追求的目標是接力隊的成績最好(只要對每一方案的成績作比較，即可找出最優(yōu)方 案，但顯然這不是解決問題的好辦法.隨著問題規(guī)模的變大，窮舉法的計算量將是無法接受 的).當隊員，入選泳姿j時，C X表示他的成績，否則C X = 0，因此目標函數(shù)為

31、 ij ijj jz = 24E5 c x .j=1 i=1 決策變量必須滿足以下3個條件：每人最多只能入選4種泳姿之一，即4 x 1， i = 1,2,3,4,5 .ij j=1每種泳姿必須有1人而且只能有1人入選，即5 x = 1， j = 1,2,3,4.i=1(3 )取值受限x= 0 或 1, i = 1,2,3,4,5, j = 1,2,3,4. 該班追求接力隊成績最好的數(shù)學(xué)模型為0-1規(guī)劃：min z = 區(qū) cx ;ij ijj=1 i=1s.t. X 0, i = p +1,.,m.其中函數(shù)f,g,(i = 1,p),g,(i = p +1,m)中至少有一個為非線性函數(shù).非線性

32、規(guī)劃有無約束問題與有約束問題之分.非線性規(guī)劃的特點非線性規(guī)劃的可行域及最優(yōu)解的情況遠比線性規(guī)劃的可行域及最優(yōu)解復(fù)雜的多:可能有 最優(yōu)解，也可能沒有最優(yōu)解；約束問題的最優(yōu)解可能在可行域的內(nèi)部，也可能在可行域的邊 界上.一些常用概念：等值面(線)一一函數(shù)值相等的決策變量曲面(曲線)f (元)=C.上升/下降方向一一至少在局部范圍內(nèi)，函數(shù)值升的方向/函數(shù)值降的方向 f 0 + tp) f 0), t E (0,8)/f 0 + tp) f (無),t E (0,8).梯度一一多元函數(shù)的“一階導(dǎo)數(shù)”，由函數(shù)的偏導(dǎo)數(shù)組成的向量1_2 /若Vf (x)。0，則Vf (x)必垂直于f (無)過點無的等值面；

33、梯Vf (x)4空，綁，乎T.oxoxox當梯度Vf (x )連續(xù)時，度Vf (x)的方向是函數(shù)f (x)在點x具有最大變化率的方向.方向?qū)?shù)函數(shù)在某方向上的變化率(下式中e是p方向上的單位向量)of (x)f(x + te) - f (x)-=lim -op-0+罕) = Vf (x )re.op若號)0，即Vf (x0p0 ,則p方向是f (x)在點x0處的上升方向；若 of(x) 0，即Vf (xp V 0，則p方向是f (x)在點x處的下降方向.op00V 2 f (x )=海賽矩陣一一多元函數(shù)的“二階導(dǎo)數(shù)”，由函數(shù)的二階偏導(dǎo)數(shù)組成的矩陣ox ox I，匕空間中由點x0和方向p所確定的

34、直線方程為x = x + tp,t e Ri.0圖2直線的幾何圖示非線性規(guī)劃的解法(1)非線性規(guī)劃基本解法基本解法的迭代格式一般為x i = x + tp , k = 0,1，稱x為初始點，p為x處的搜索方向，t為步長因子，滿足f (x +1 p ) pCx = dWolfe 法.參考書目：趙鳳治.約束最優(yōu)化方法.北京：科學(xué)出版社,1991(2)數(shù)據(jù)擬合問題(最小二乘問題)最小二乘法非線性規(guī)劃建模實例示例1某公司有6個建筑工地要開工，每個工地的位置(用平面坐標(a,b)表示，距離 單位：km)及水泥日用量d (單位：t (噸)由表1給出.目前有兩個臨時料場位于A(5,1)和 B(2,7)，日儲

35、量各有201 .請回答以下兩個問題：假設(shè)從料場到工地之間均有直線道路相連，試制定每天從A、B兩料場分別向各工地 運送水泥的供應(yīng)計劃，使總的噸公里數(shù)最小.為進一步減少噸公里數(shù)，打算舍棄目前的兩個臨時料場，修建兩個新料場，日儲量 仍各為201，問建在何處最佳，可以節(jié)省多少噸公里數(shù).表1工地的位置(a, b)及水泥日用量d的數(shù)據(jù)料場123456a1.258.750.55.7537.25b1.250.754.7556.57.75d3547611建模過程：公司追求的目標是每天從A、B兩料場分別向各工地運送水泥總的噸公里數(shù) 最小.為表述該問題，設(shè)工地的位置與水泥日用量分別為(氣,b)和七(i = 1,2,

36、6),料場位 置及其日儲量分別為3 , J )和e (j = 1,2).定義決策變量w (i: 1,2, j = 1,2):料 j j jij場j向工地，的運送量(i = 1,2,6, j = 1,2 )，在問題(2)中，新建料場位置(七,七)也是決 策變量.公司追求總的噸公里數(shù)最小的目標函數(shù)為f =空j =1 i=1WjV(x- a)2 + (y. b)2 .決策變量w (i = 1,2,6, j = 1,2)必須滿足以下約束條件:滿足各工地的水泥日用量 w = d , i = 1,2, .,6.j=1各料場的運送量不能超過日儲量 w. 0 , i = 1,2,.,6, j = 1,2.(1)公司追求總的噸公里數(shù)最小的數(shù)學(xué)模型是如下線性規(guī)劃模型w .v(2 - a )2 + (7 - b )2 ；i = 1min f = w. J(5-a.)2 + (1 -b) + i = 1s.t. w = d , i = 1,2, ,6 ,j=1w. 0 , i = 1,2,.,6, j = 1,2.這個模型的解，即料場A、B向6個工地運送水泥的計劃為wii工地1工地2工地3工地4工地5