1、1第 1 章預備知識 1.1 基本概念與術語1.1.1 數學規劃問題舉例例 1 食譜（配食）問題假設市場上有 n 種不同的食物，第 j 種食物每個單位的銷售價為q（j=1,2,，n）。人體在正常生命活動過程中需要m 種基本的營養成分。為了保證人體的健康，一個人每天至少需要攝入第 i 種營養成分b（i=1,2,，m）個單位。第 j 種食物的每個單位包含第 i 種營養成分aij個單位。食譜（配食）問題就是要求在滿足人體基本營養需求的前提下，尋找最經濟的配食方案 （食譜）。建立食譜的數學模型引入決策變量 為：食譜中第 i 種食物的單位數量nmin exi生ns.t. aijXj:-bi,i = 1,

2、2, , mj呂Xj0,j =1,2, ,n例 2 選址與運輸問題假設某大型建筑公司有 m 個項目在不同的地點同時開工建設.記工地的位置分別為p-（ai,bi）, i=1,2, m.第 i 個工地對某種建筑材料的日用量是已知的（比如水泥的日用量 （單位：t ）為Di）.該公司準備分別在T=（為，yj和T2=（X2, y2）兩個地點建造臨時料場，并且保證臨時料場對材料的日儲量（單位：t）分別為M1和M2.如何為該公司確定臨時料場的位置，并且制訂每天的材料供應計劃，使建筑材料的總體 運輸負擔最小？建立選址與運輸問題的數學模型引入決策變量：位置變量（Xk, yk）,從臨時料場向各工地運送的材料數量Z

3、ki(k =1,2; i =1,2,m).2 m- Zki,.(Xk-ajk F ms.t.二Zki三Mk, k =1,2i2o(yk-bi)min2Zki=Di, i =1,2, ,mk丄2Zki 0,(Xk,yk) R , k=1,2,i =1,2, ,m例 3 生產計劃問題某企業向客戶提供一種機器，第 1 季度末需要交貨 G 臺，第 2 季度末需要交貨C2臺，第 3 季度末需要交貨c3臺.該企業最大生產能力是每季度生產 b 臺.若用 x 表示該企業在某季度生產的機器臺數，則生產費用(單位：元)可以用函數f (x) fx - a2x來描述.企業需為每臺機器在每個季度多支付p 元的存儲費.假

4、設在第一個季度開始時無存貨，不允許缺貨如何制訂生產計劃，確定在每個季度應該生產多少臺機器，才能既履行交貨合同，又使企業總體費用最少？建立生產計劃的數學模型決策變量：用(i =1,2,3)表示企業在第 i 個季度生產的機器數量.合同規定的總數量：x1x2X3 =C| C2C3每個季度生產數量要求：每個季度生產數量Xj不大于最大生產能力 b，不少于該季度末的交貨量Cj與該季度初的庫存量Ij之差第 j 個季度初庫存量：Ij=v(xi- ci), j =1,2,3(I1=0)變量隱含要求：Xj_0(j =1,2,3)，并且取整數.企業總費用：所有季度生產與存儲費用之和33F(x)f (x)xpIii=

5、1i=23_min F (x)=佝(3 i) p)Xia2X) p(2& C2)iM33S.t. 二Xj八Cjj T j mX1-C1x1x2- G c20Xj-b,Xj Z, j =1,2,3(Z 表示所有整數的集合)1.1.2 數學規劃問題的模型與分類形成一個最優化問題的數學模型3首先需要辨識目標，確定優化標準，即待研究系統的性能定量描述，如成本、數量、利潤、時間、能量等；其次用合適的決策變量描述系統的特征量，并將目標表示成決策變量的函數(目標函數，objective function)；此外需確定變量所受的范圍限制，由若干個函數的等式或者不等式來定義(約束函數，constraint fu

6、nctions ).最優化問題指在決策變量所受限制范圍內，對相關的目標函數進行極小化或者極大化minf(x)xWRns.t.gi(x) _0, i Ihj(x) =0, j E滿足約束條件的點稱為可行點(feasible poi nt)，所有可行點的集合稱為可行域(feasible region)，記為 S.-當S = Rn，無約束優化問題；否則，約束優化問題.-f ,gi和hi都是線性函數，為線性規劃(linear programming , LP);否則為非線性規劃(nonlinear programming, NLP ).-所有變量取整數，稱為整數規劃(integer programmi

7、ng);允許一部分變量取整數，另 一部分變量取實數，為混合整數規劃(mixed integer programming, MIP ).-從一個連通無限集合 (可行域)中尋找最優解，稱為連續優化(continuous optimization) 問題；從一個有限的集合或者離散的集合中尋找最優解，稱為組合優化(combinatorialoptimization)，或者離散優化(discrete optimization ).存在多個目標，即目標函數f (x)取一個向量值函數，稱多目標規劃(multi-objectiveprogramming)，或多目標優化.最優化問題中出現的參數是完全確定的，稱為

8、確定型優化(deterministic optimization )問題；否則稱為非確定型優化(uncertain optimization)問題，包括了隨機規劃(stochasticprogramming )、模糊規戈V (fuzzy programming ) 等特殊情形.1.1.3 最優解的概念定義：設f(x)為目標函數，S為可行域，x S,若對每個S，成立f(x)_f(l), 則稱x為f (x)在S上的全局極小點。定義：設f (x)為目標函數，S為可行域，若存在S的；0鄰域N& =x|xI，使得對每個Sc N(x)成立f (x)蘭f &),則稱x為f (x)在S上的局部極小點。全局極小

9、點也是局部極小點，而局部極小點不一定是全局極小點 大多數的優化算法通常只是尋找局部最優解4對于某些特殊情形，如凸規劃，局部極小點也是全局極小點5 1.2 多元函數分析1.2.1 梯度及 Hesse 矩陣函數f(x)在 x 處的梯度為 n 維列向量:W(x)=迪，葩,拼(XX1；x2f (x)在 x 處的 Hesse 矩陣為n n矩陣2f (x):-：xn-f(x)Ff(x)Ff(x)1cX1cX2cxxnd f (X)2f(x)d f(x)v2f (x)=做&JaCX2CX2I-Ff (X)Ff(x)Ff(x)IcXsX1CXnCX?FXnXn _二次函數fgxUX +cn 階對稱矩陣，b 是

10、n 維列向量，c 是常數.梯度：帝f(x)=Ax+bHesse 矩陣：2V f(x)=A對向量值函數h(x)= (h1(x),h2(x)；i，hm(X)T，函數Pa2f(x/l-X；：Xj的 Jacobi 矩陣為A 是每個分量h (x)為 n 元實值函數nx：n昂i(x)旳(x)(x)cx2欣n昂2(X)引2(x)chz(x)acx2欣na引m(x)Chm(x)Chm(x)Xicx2CXn_ 旨(x)該矩陣稱為 h 在 x 的導數，記作h(x)或 Ih(x)T,其中 h(x) =、hi(x),i h2(x),hm(x)sin XiCOSX2例向量值函數f (x) = f(X|, x2)=XiC

11、OSX22XX2e22為+xjx2f (x)在任一點(X4,X2)的 Jacobi 矩陣,即導數為mxn6cosx1-sin x2|f(x) =Nf (x)T =2e2e2E4xi+x2Xi1.2.2 多元函數的 Taylor 展式假設f (x)在開集 S 上連續可微，給定點XS,貝yf 在點 X 的一階 Taylor 展開式為f (x)二f (x)、f(X)T(XX)0( XX )o(|xx|)當|XX|T0時,關于|x -X是高階無窮小量.假設f (X)在開集 S 上二次連續可微，則 f 在點X S的二階 Taylor 展開式為f(x)= f(x)if(X)T(xX)*(xX)Ti2f(X

12、)(xX)0(xx2)1.2.3 方向導與最速下降方向f (X)在點X處沿方向 d 的變化率用方向導數表示.f (X)在x處沿方向 d 的方向導數Df(x;d)定義為極限Df(x;d)=limf(x d)f(x)0 對于可微函數，方向導數等于梯度與方向的內積，即Df (x;d)f (x)Tdf (x)在點X處下降最快的方向，稱為最速下降方向，它是f(X)在點X處的負梯度方向f(x) 1.3 凸分析初步1.3.1 凸集的定義、舉例( (常見凸集) )及性質定義：設 S 為 n 維歐氏空間Rn中一個集合若對 S 中任意兩點，聯結它們的線段仍屬 于 S;換言之，對 S 中任意兩點x，x及每個實數0,

13、1，都有X(1 - )x(2)S則稱 S 為凸集.0( X_X )當X _x0時,關于X-x是高階無窮小量.7常見凸集：1集合H二x | pTx為凸集.(p 為 n 維列向量，:-為實數) 集合 H 稱為Rn中的超平面，故超平面為凸集.2集合H -=x | pTx乞:為凸集.集合H一稱為半空間，故半空間為凸集.3集合L二x|x =x() d, -0為凸集.(d 是給定的非零向量 ,x)是定點)集合L稱為射線，故射線為凸集.證明：對任意兩點x，x(2)L及每一個0,1，必有x(1)=x(0)+X,dx(2)=x(0)+入2d以及X(1 -)X(2)= (x(0)d) (1 - )(x(0)2d)

14、=x(0)W(1 - ；)2d由于匚対* (1 -2_ 0，因此有血+(1丸)x亡L凸集的性質：設s和5為Rn中的兩個凸集，一：是實數，則(1)昨=Px|xS為凸集；(2)35 為凸集；(3)S!S2=x(1)- X|x s，x(2)S2為凸集;(4)3 S2=x(1)_x(2)| X亡S，x叫SJ為凸集.凸錐和多面集定義：設有集合C Rn，若對 C 中每一點 X,當取任何非負數時，都有XC,則 稱 C 為錐.又若C 為凸集，則稱 C 為凸錐.例向量集:(1), :(2),(k)的所有非負線性組合構成的集合(h)8|入3 0,i=1,2，,k為凸錐.定義 有限個半空間的交x I Ax乞b稱為多

15、面集.9例：集合S=x|xi 2x2乞4, Xi- X2乞1,Xi_ 0 必_ 0為多面集若 b=0,則多面集x| Ax乞0也是凸錐，稱為多面錐.極點和極方向定義：設 S 為非空凸集，S，若 x 不能表示成 S 中兩個不同點的凸組合；換言之, 若假設a丄a、(2)(1)(2)_ gX = X (1 -)x,x ,x S必推得x = x=x(2)，則稱x是凸集S的極點.(b)定義：設 S 為非空凸集，d 為非零向量，如果對 S 中的每一個 x,都有射線x d | _0 S,則稱向量 d 為 S 的方向.又設d和d(2)是 S 的兩個方向，若對任何正數，有d(1)- d，則稱d和d是 兩個不同的方

16、向.若 S 的方向 d 不能表示成該集合的兩個不同方向的正的線性組合，則稱 d 為 S 的極方向.(a)10注意:有界集不存在方向，因而也不存在極方向.對于無界集才有方向的概念.11多面集的一個重要性質一一表示定理：設S =x| Ax =b,x _0為非空多面集，則有:d,d(l).I(3)xwS的充要條件是：x= EkjX(j)+4jd，乞打=1，丸j啟0, j=1,2,，k,j 4j 4j 4Jj-0,j =1,2, ,l.1.3.2 凸集分離定理及其應用（擇一定理）凸集的另一個重要性質一一分離定理.集合的分離：指對于兩個集合S和S2，存在一個超平面 H，使 S 在 H 的一邊，S2在 H

17、 的另一邊.如果超平面的方程為pTX=，那么對位于 H 某一邊的點 X,必有pTX工二，而對位 于 H 另一邊的點 X,必有pTX _ :-.定義：設s和S是兩個非空集合，H =x| pTx=a為超平面如對每個xE s,有pTX ：-：，對每個X S，有pTX _ （或情形恰好相反），則稱H 分離集合 S|和S2.定理（凸集分離定理）：設S和S2是兩個非空凸集，S, S,-一，則存在超平面 H,使得S H”叫x|pTx_：,S2H）x|pTx.凸集分離定理的另一種表述方法：設3 和是兩個非空凸集，S,，則存在非零向量 p，使inf pTx| x SJ _ suppTx I x S2凸集分離定理

18、在最優化理論中很有用。著名的應用是所謂的擇一定理。擇一定理（the theorem of the alternative）指對于兩個相關的線性系統（等式或不等式組）I 和 II 來說，或者系統 I 有解，或者系統 II 有解，但兩者不可能同時有解擇一定理有多種不同的形式：Farkas 定理，Gordan 定理，Motzkin 定理等.定理（Farkas 定理）:設 A 為m n矩陣，c 為 n 維向量，則線性系統（I）Ax _ 0,cTx 0（I） 極點集非空， 且存在有限個極點(k),x()（2）極方向集合為空集的充要條件是S 有界若 S 無界，則存在有限個極方向12有解，當且僅當(II)A

19、Ty=c,y_0無解定理(Gordan 定理):設 A 為m n矩陣,那么Ax 0的充要條件是不存在非零向量y - 0,使ATy= 01.3.3 凸函數的定義、性質及判別方法定義：設 S 為非空凸集，f 是定義在 S 上的實函數如果對任意的X，x.S及每個數(0,1),都有f(x(1一)x上f(x)(1一)f(x)則稱 f 為 S 上的凸函數.如果對任意互不相同X,x(2)S及每一個數(0,1),都有f(X(1 -)x):：f (x)(1 -)f(x(2),則稱 f 為 S 上的嚴格凸函數.如果-f 為 S 上的凸函數，則稱 f 為 S 上的凹函數.凸函數的幾何解釋：連接函數曲線上任意兩點的弦

20、不在曲線的下方.凸函數的一些性質：1f 是定義在凸集 S 上的凸函數，實數_0,則，f 也是定義在 S 上的凸函數.2f1和f2是定義在凸集 S 上的凸函數，貝y f f2也是定義在 S 上的凸函數.k3f1, f2/, fk是定義在凸集 S 上的凸函數，實數 鼻鼻,，-。，則Vifi也是定im義在 S 上的凸函數.4S 是非空凸集，f 是定義在 S 上的凸函數，是一個實數，則水平集S廣x|x S, f (x)豈:是凸集.5S 是非空凸集，f 是定義在 S 上的凸函數，貝 y f 在 S 上局部極小點是全局極小點，且 極小點的集合為凸集.證明：設X是 f 在 S 上的局部極小點，即存在x的；.

21、0的鄰域N (x)，使得對每一點/I./W(b)13x S N(x)， 成立f (x) f (x).假設x不是全局極小點，則存在? S，使f(x):：f (x)由于 S 是凸集，因此對每一 個數0,1,有(1 -S由于x與:?是不同的兩點，可取(0,1),又由于 f 是S 上的凸函數，因此有f(?(1- 鼻)f (x)(1 -，)f &):f(x) ( ) f(x)= f(x)當取得充分小時，可使?(1一S N (x)這與x為局部極小點矛盾.故x是 f 在 S 上的全局極小點.由以上證明可知，f 在 S 上的極小值也是它在 S 上的最小值設極小值為，則極小點的集合可以寫作丨.二x|x S, f

22、(x)乞:根據性質，為凸集.凸函數判別的一階條件定理：設 S 是非空開凸集，f (x)是定義在 S 上的可微函數，則f (x)為凸函數的充要 條件是對任意兩點x,x S，都有f(X)_f(X)(X)T(xX(1)而f (x)為嚴格凸函數的充要條件是對任意的互不相同的X,x(2廠S，成立f(X)f(X)lf(X)T(X(2)-X)推論：設 S 是Rn中的凸集，S,f(x)是定義在Rn上的凸函數，且在點x可微，則 對任意的x S,有f(x)_ f(X)i f(X)T(x-X)凸函數判別的二階條件定理：設 S 是Rn中非空開凸集，f(x)是定義在 S 上的二次可微函數，則f(x)為凸函 數的充要條件是在每一點X- S處 Hesse 矩陣半正定.Hesse 矩陣半正定，即對于任意的x，S和x，Rn,有14xVf (X)x_O定理：設 S 是Rn中非空開凸集，f (x)是定義在 S 上的二次可微函數，如