1、優化模型優化模型 ( (規劃問題規劃問題) ) 舒舒 興興 明明QQ: 117562750QQ: 117562750TelTel:難題清清楚楚地寫出來，便已解決了一半。把難題清清楚楚地寫出來，便已解決了一半。 -古德林法則古德林法則推薦參考書推薦參考書胡運權.運籌學教程.清華大學出版社.1998韓伯棠.管理運籌學.高等教育出版社.2010謝金星等.優化建模與Lindo/Lingo軟件.清華大學出版社.2005譚永基等.經濟管理數學模型案例教程.高教出版社.2013譚永基.數學模型.復旦大學出版社.2005姜啟源.數學模型.高等教育出版社.20

2、10但靜.數學建模與數學實驗.高等教育出版社.2003姜啟源等.大學數學實驗.清華大學出版社.2004美Joe Zhu著.數據包絡分析.科學出版社.2016謝中華.Matlab統計分析與應用：40個案例分析.北航出版社.2010規劃問題及其模型規劃問題及其模型 在工程技術、經濟管理、科學研究等領域中，決策在工程技術、經濟管理、科學研究等領域中，決策者要求在滿足一系列條件要求下，求材料最省、重量最者要求在滿足一系列條件要求下，求材料最省、重量最輕、成本最低、時間最短、路程最短、利潤最大、誤差輕、成本最低、時間最短、路程最短、利潤最大、誤差最小、產量最大等等，都稱為最小、產量最大等等，都稱為優化問

3、題優化問題。習慣上，上述。習慣上，上述的最省、最輕、最低、最短、最大等統稱的最省、最輕、最低、最短、最大等統稱最優最優。 對于給定的優化問題，決策者根據問題的背景知識對于給定的優化問題，決策者根據問題的背景知識或試驗數據，將問題進一步簡化，用或試驗數據，將問題進一步簡化，用一系列數學符號一系列數學符號( (變變量量) )來代替問題所涉及的各種已知或未知要素，用這些符來代替問題所涉及的各種已知或未知要素，用這些符號的函數等式或者不等式來反映客觀條件或約束，并用號的函數等式或者不等式來反映客觀條件或約束，并用這些符號的函數來反映決策者的訴求這些符號的函數來反映決策者的訴求（欲望或目標欲望或目標），

4、），這樣的約束和訴求就構成了相應問題的這樣的約束和訴求就構成了相應問題的規劃模型規劃模型。一、兩個案例 案例1 （生產決策問題） （一個線性規劃模型） 案例2 （路燈照度問題） （一個非線性規劃問題） 通過兩個案例，學習規劃模型的建立必要步驟以及書寫的規范格式。 某某工廠在計劃期內要安排工廠在計劃期內要安排I I、II II兩種產品生產。生產兩種產品生產。生產單位產品所需的設備臺時、單位產品所需的設備臺時、A A，B B兩種原材料的消耗、兩種原材料的消耗、資源的限制以及單件產品利潤如表資源的限制以及單件產品利潤如表1-11-1所示所示表表1-11-1 問工廠應分別生產多少單位產品問工廠應分別生

5、產多少單位產品I I和產品和產品II II，才能獲，才能獲利最多？利最多？I III II資源限制資源限制設設 備備原原 料料 A A原原 料料 B B1 11 1300 300 臺時臺時2 21 1400 kg400 kg0 01 1250 kg250 kg利潤（元）利潤（元）5050100100案例案例1 1 生產決策問題生產決策問題（一個簡單的線性規劃問題（一個簡單的線性規劃問題）【問題分析問題分析 】 （1 1）這是一個生產決策問題，決策者的）這是一個生產決策問題，決策者的目標是生產利潤最大（目標是生產利潤最大（2 2）與利潤有關的是產品）與利潤有關的是產品的銷售量的銷售量與與售價（或

6、單位利潤）售價（或單位利潤） ；（；（3 3）生產產品就要）生產產品就要消耗消耗資源資源（這與產量有關），（這與產量有關），而各種資源又受到客觀限制。而各種資源又受到客觀限制。經驗經驗：收入與：收入與銷售量有關，而資源的消耗量與產品的產銷售量有關，而資源的消耗量與產品的產量有關。量有關。【問題假設問題假設】 （1 1）產品）產品I I的產量等于銷售量；的產量等于銷售量； （2 2）產品）產品II II的產量等于銷售量。的產量等于銷售量。【符號設置符號設置】x x1 1 產品產品I I的一個周期的產量（單位：件）；的一個周期的產量（單位：件）；x x2 2 產品產品II II的一個周期的產量（單

7、位：件）；的一個周期的產量（單位：件）；z z 工廠一個周期內的總利潤（單位：元）。工廠一個周期內的總利潤（單位：元）。（其中，其中，x x1 1, x, x2 2 稱為稱為決策變量決策變量）I III II資源限制資源限制設設 備備原原 料料 A A原原 料料 B B1 11 1300 300 臺時臺時2 21 1400 kg400 kg0 01 1250 kg250 kg利潤（元）利潤（元）5050100100【建立模型建立模型】工廠一個生產周期的總工廠一個生產周期的總利潤利潤 2110050 xxzx x1 1x x2 2生產資料約束生產資料約束221212xxxxx（設備限時）（設備限

8、時）（原料（原料A A限量）限量）（原料（原料B B限量）限量）資源的實際消耗資源的實際消耗資源的擁有量資源的擁有量250400300限制限制I IIIII資源限制資源限制設設 備備原原 料料 A A原原 料料 B B1 11 1300 300 臺時臺時2 21 1400 kg400 kg0 01 1250 kg250 kg利潤（元）利潤（元）50100其它約束其它約束：因為因為x x1 1和和x x2 2都是產品的產量，所以，從數學意義上，有都是產品的產量，所以，從數學意義上，有0,21xx廠家的訴求廠家的訴求：一個周期內：一個周期內利潤利潤 z z 越大越好越大越好！(max z)(max

9、 z) 以上分析，將生產過程的未知要素（以上分析，將生產過程的未知要素（產品產量產品產量）用用x x1 1, x, x2 2表示，各種表示，各種客觀約束客觀約束都表達為都表達為x x1 1,x ,x2 2的函數不等式，的函數不等式，廠家的廠家的訴求訴求（利潤）也是（利潤）也是x x1 1,x ,x2 2的函數表達式，將這些數的函數表達式，將這些數學結構寫在一起，就是這個規劃問題的學結構寫在一起，就是這個規劃問題的數學模型數學模型：0,250,0042,003.10050max212212121xxxxxxxtsxxz 這個規劃模型，如果拋開這個問題的背景，就是這個規劃模型，如果拋開這個問題的背

10、景，就是求在五個約束條件下，一次函數求在五個約束條件下，一次函數z=50 xz=50 x1 1+100 x+100 x2 2的最大的最大值，這是一個純數學意義上的極大值問題。值，這是一個純數學意義上的極大值問題。【數學模型數學模型】0,250,0042,003.10050max212212121xxxxxxxtsxxz目標函數目標函數條件約束條件約束變量約束變量約束約束約束Subject to Subject to 受約束于，滿足于受約束于，滿足于 雖然有些問題的數學結構很難用數學式子來表達，雖然有些問題的數學結構很難用數學式子來表達，但習慣上我們稱但習慣上我們稱決策變量、約束條件、目標函數決

11、策變量、約束條件、目標函數為規劃為規劃問題的問題的三要素三要素。這個問題的目標和約束都是決策變量的。這個問題的目標和約束都是決策變量的一次表達式，稱為一次表達式，稱為線性規劃線性規劃。決策變量決策變量案例案例2 2 路燈照度路燈照度問題問題( (一個非線性規劃問題一個非線性規劃問題） 如圖如圖2-12-1所示，在所示，在一條一條s=20ms=20m寬的道路兩側，分別安寬的道路兩側，分別安裝了一只裝了一只2kw2kw和一只和一只3kw3kw的路燈，它們離地面的高度分的路燈，它們離地面的高度分別為別為h h1 1=5m=5m和和h h2 2=6m=6m。（。（1 1）在）在漆黑的夜晚，當兩只路漆黑

12、的夜晚，當兩只路燈開啟時，兩只路燈連線路面上最暗的點和最亮的點燈開啟時，兩只路燈連線路面上最暗的點和最亮的點在哪里在哪里？（？（2 2）如果）如果3kw3kw路燈的高度可以在路燈的高度可以在3m3m到到9m9m之間之間變化，如何求得路面上最暗和最亮的點的位置變化，如何求得路面上最暗和最亮的點的位置？（？（3 3）如果如果兩只路燈的高度均可以在兩只路燈的高度均可以在3m3m到到9m9m之間變化，結果之間變化，結果將如何將如何？圖圖2-12-1osxP1P2h1h2r1r212【問題分析問題分析】 經驗經驗： （物理學背景知識）物理學背景知識） 光源光源點點P P1 1在點在點x x處的照度（照亮

13、強度）處的照度（照亮強度）I I1 1，I I1 1與功率與功率P P1 1成正例，與距離成正例，與距離r r1 1的平方成反比，與照射角度的平方成反比，與照射角度 1 1的正弦的正弦成正比。即成正比。即21111rsinPkI其中，其中，k k為比例系數，同時也是平衡量綱（單位）的量。為比例系數，同時也是平衡量綱（單位）的量。圖圖2-1osxP1P2h1h2r1r212圖2-1osxP1P2h1h2r1r212【問題假設問題假設】（1）p1,p2都可以看成點光源；（2）p1,p2在x的照度可以疊加（求和）；【符號設置符號設置】（符號設置如有圖2-1所示）I : 某點處的照度（亮度）；I1：燈

14、P1在該點處的照度；I2：燈P2在該點處的照度；（3）光源只來至兩盞燈。 s : 街道寬； p1,p2:兩個光源的功率； h1,h2:兩盞燈的高度； r1,r2: 兩盞路燈到x的距離； x : 街道某點的坐標，介于0和s之間； 1, 2:光線的入射角。圖圖2-1osxP1P2h1h2r1r212兩只燈在點x處的照度為21III其中，2222221111rsinPkI ,rsinPkI變量之間的關系，111sinrh,sin222rh.)xs (hr ,hxr22222121【建立模型建立模型】問題問題(1)(1)：燈高度不變，求路面照度最弱最強的位置燈高度不變，求路面照度最弱最強的位置x x。

15、數學模型數學模型1 1;IImax(min)21I2222221111rsinPkI ,rsinPkI，111sinrh,sin222rh.)xs (hr ,hxr22222121s.x0s.t.也可以化簡為也可以化簡為)h)xs(Ph)hx(PhkI max(min)23222222321211sx0s.t.代入已知參數，模型簡化為代入已知參數，模型簡化為.20 x0. t . s)36)x20(18)25(x10kI(x)max(min)232232即即求一元函數求一元函數I(x)I(x)在在0 0，2020上的上的最大值與最小值最大值與最小值。問題問題(2)(2)：當當3kw3kw的燈的

16、高度在的燈的高度在3m3m到到9m9m之間變化時，路之間變化時，路面的最暗和最亮點。面的最暗和最亮點。數學模型數學模型2 2. 9h320,x0. t . s;)h)x20(h3)25(x10k)hI(x,max(min)22322222322 即求即求二元函數二元函數I(x,hI(x,h2 2) )在所在所給矩形閉區域上給矩形閉區域上的最大值與的最大值與最小值。最小值。問題問題(3)(3)：兩只燈的高度都在兩只燈的高度都在3m3m到到9m9m之間變化時，求路之間變化時，求路面的最暗和最亮點。面的最暗和最亮點。數學模型數學模型3 3. 9h3, 9h320,x0. t . s;)h)x20(h

17、3)h(x2hk)h,hI(x,max(min)2123222223212121即即求求三元函數三元函數I(x,hI(x,h1 1,h ,h2 2) )在所給條件下的上的最大值與最在所給條件下的上的最大值與最小值小值。 像像這種目標函數或者約束條件是決策變量的非一這種目標函數或者約束條件是決策變量的非一次（非線性）的規劃模型，稱為次（非線性）的規劃模型，稱為非線性規劃模型非線性規劃模型。二、規劃問題解的概念二、規劃問題解的概念 1 1、線性規劃解的概念、線性規劃解的概念 通過具體的例子，學習線性規劃問題的可行解、可行域、最優解等概念；通過圖解法了解線性規劃解的情況； 2 2、非線性規劃解的概念

18、、非線性規劃解的概念 通過具體的例子，學習非線性規劃的可行解、可行域、局部最優解、全局最優解等概念；通過例子了解非線性規劃求解的特點； 3 3、小結小結 對比線性規劃和非線性規劃的圖解法，總結兩種規劃解的不同點（局部和全局）和相同點（迭代法）。1 1、線性規劃解的概念、線性規劃解的概念1.1 1.1 線性規劃的可行解線性規劃的可行解0,250,0042,003.10050max212212121xxxxxxxtsxxz 若若x x1 1,x ,x2 2滿足條滿足條件件14,14,則稱向量則稱向量21xxx為線性規劃問題為線性規劃問題的的一個可行解一個可行解。1234例如例如20200,1002

19、00,25050,00)4()3()2()1(xxxx其中其中x x(1)(1),x ,x(2)(2)為可行解，而為可行解，而x x(3)(3),x ,x(4)(4)不是可行解。不是可行解。所有可行解構成的集合41,|2121滿足xxxxxD稱為該線性規劃的可行域可行域。 在例1中，若存在x*=x1*,x2*T,對D中任何x=x1,x2T，都有21*2*11005010050 xxxx稱x*為該線性規劃的最優解最優解（使目標函數最大或最小的可行解可行解）。1.2 1.2 線性規劃的可行域線性規劃的可行域1.3 1.3 線性規劃的最優解線性規劃的最優解1.4 1.4 可行解、可行域、最優解的幾何

20、意義可行解、可行域、最優解的幾何意義可以用圖解法求解兩個決策變量的線性規劃問題。可以用圖解法求解兩個決策變量的線性規劃問題。例例3 3 用圖解法求解如下線性規劃問題用圖解法求解如下線性規劃問題0, 5,2426,155 . .2max212121221xxxxxxxtsxxz解解 圖解法圖解法步驟步驟：（1 1）用x1，x2分別表示橫坐標和縱坐標，并根據x1,x2=0，繪制坐標系繪制坐標系；（2 2）圖示各個約束條件圖示各個約束條件所表達的基線及其變化方向；（3 3）由滿足所有條件的點（可行解可行解）構成的集合（區域）就是就是可行域可行域，（4 4）圖示目標函數圖示目標函數的基線，并由變量的變

21、化方向確定基線的平移方向，最后確定最優解最優解；x1x205x5x2 2=15=156x6x1 1+2x+2x2 2=24=24x x1 1+x+x2 2=5=5Q1Q2Q3Q4可行區域可行區域D Dx x2 2=z-2x=z-2x1 1使得目標函數最大使得目標函數最大的點的點Q Q2 2(3.5,1.5)(3.5,1.5)Q Q2 2對應的點就是線性規劃問題的對應的點就是線性規劃問題的唯一最優解唯一最優解：x x* *=x=x1 1* *=3.5,x=3.5,x2 2* *=1.5=1.5T T。 例例4 4 用圖解法觀察下述問題的最優解情況用圖解法觀察下述問題的最優解情況x x1 1x x

22、2 205x5x2 2=15=156x6x1 1+2x+2x2 2=24=24x x1 1+x+x2 2=5=5Q1Q2Q3Q4x x2 2+x+x1 1=0=0可以看出，可以看出，Q Q2 2Q Q3 3上的點上的點全是最優解。全是最優解。即問題有即問題有無窮多最優解無窮多最優解。0, 5,2426,155. .max212121221xxxxxxxtsxxz 例例5 5 判斷如下線性規劃的解情況判斷如下線性規劃的解情況X2=3x1x20 x2+x1=0可以看出，在可行域內，當可行解變化時，目標函數可以無限增大。即問題為無界解無界解。例例6 6 判斷如右線性規劃問題的解情況12121212m

23、 ax22. .226,0zxxxxs txxxx可以看出，該問題兩個約束矛盾，無可行解無可行解。.0 x,x,3x. t . s;xxzmax21221 綜上所述，對于線性規劃問題，其結果不外乎下面幾綜上所述，對于線性規劃問題，其結果不外乎下面幾種情況：種情況：（1 1）有最優解有最優解：唯一最優解或無窮多最優解，且最優：唯一最優解或無窮多最優解，且最優解一定在解一定在可行域某頂點可行域某頂點達到；達到；（2 2）無界解無界解；（3 3）無可行解無可行解。 在實際的線性規劃模型的計算中，如果遇到（在實際的線性規劃模型的計算中，如果遇到（2 2）情）情況，說明況，說明漏掉了重要的約束漏掉了重要

24、的約束；如果遇到（；如果遇到（3 3）情況，說）情況，說明問題明問題有有約束沖突約束沖突，檢查約束條件，一般采取如下策略：，檢查約束條件，一般采取如下策略：要么留下主要約束，去掉與之矛盾的次要的約束；要么要么留下主要約束，去掉與之矛盾的次要的約束；要么承認矛盾的合理性，采用多目標規劃承認矛盾的合理性，采用多目標規劃。 在建立規劃模型時，若目標函數如例在建立規劃模型時，若目標函數如例2 2中決策變量或中決策變量或者約束方程（不等式）中某些變量為非一次（不是線者約束方程（不等式）中某些變量為非一次（不是線性），則稱建立的數學模型為非線性規劃模型。性），則稱建立的數學模型為非線性規劃模型。552 2

25、、非線性規劃解的概念、非線性規劃解的概念0, 2, 42. .2),(min212122212122212121xxxxxxxxtsxxxxxxf模型模型55為非線性規劃的標準模型為非線性規劃的標準模型( (目標最小化，所有約目標最小化，所有約束都是大于等于束都是大于等于) )，很多優化，很多優化理論的推導和優化程序的編理論的推導和優化程序的編譯都是按照這種模式展開）。譯都是按照這種模式展開）。22212121),(minxxxxxxf66模型模型66稱為無約束優化。默認稱為無約束優化。默認Rxx21,0, 23, 32. .5432),(min2121212122212121xxxxxxts

26、xxxxxxxxf77模型模型77稱為稱為二次規劃二次規劃( (目標是決策變量的二次型，約目標是決策變量的二次型，約束都是決策變量的束都是決策變量的線性約束，它的很多性質跟線性規線性約束，它的很多性質跟線性規劃類似劃類似) )。2.1 2.1 可行集（可行域可行集（可行域）給定非線性規劃問題給定非線性規劃問題550, 2, 42. .2),(min212122212122212121xxxxxxxxtsxxxxxxf1010111112122.1.1 2.1.1 可行解可行解 若若x x1 1,x ,x2 2滿足條件滿足條件10,11,1210,11,12，則稱向量，則稱向量x=xx=x1 1

27、,x ,x2 2 T T為非為非線規劃線規劃55的可行解。的可行解。0, 2, 42. .2),(min212122212122212121xxxxxxxxtsxxxxxxf10101111121211,31,22,00)4()3()2()1(xxxx例如：例如：其中其中x x(1)(1),x ,x(4)(4)不是此問題的可行解，而不是此問題的可行解，而x x(2)(2),x ,x(3)(3)是規劃問題是規劃問題55的的可行解可行解。2.1.2 2.1.2 可行集（可行域可行集（可行域）121110,|2121，滿足xxxxxD稱為非線性規劃問題稱為非線性規劃問題55的可行集（域）。的可行集（

28、域）。例例8 8 利用圖解法，求解如下非線性規劃問題利用圖解法，求解如下非線性規劃問題0 x0 x05xx05xxx) 1x()2(x)x,f(xmin21212221222121【問題分析問題分析】 : :決策變量決策變量為為x=(xx=(x1 1,x ,x2 2) )T T。目標函數表示。目標函數表示決決策變量策變量=(x=(x1 1,x ,x2 2) )T T到點到點(2,1)(2,1)T T的距離的平方（體現為以的距離的平方（體現為以(2,1)(2,1)為圓心的為圓心的圓周半徑圓周半徑變化）變化）；第一個約束是一條第一個約束是一條拋物線拋物線（開口朝左（開口朝左,x ,x1 1為橫軸）

29、為橫軸）；0 x0 x05xx05xxx) 1x()2(x)x,f(xmin21212221222121第二個約束為第二個約束為一次不等式一次不等式；同時決策變量非負。；同時決策變量非負。2212221)25(42505xxxxx（注意等號）（注意等號）解解 以以x x1 1和和x x2 2分別為橫軸和縱軸，分別為橫軸和縱軸，建立直角坐標系建立直角坐標系，如，如圖圖2-22-2：（1 1）繪制約束曲線；）繪制約束曲線；（2 2）標出可行域：）標出可行域：x1x205xx21( (右上右上) )2.5221)25(425xx( (在拋物線上在拋物線上) )ABCD拋物線段拋物線段ABCDABCD

30、為可行域；為可行域；圖圖2-22-2x1x205xx21(右上右上)2.51222221R) 1x() 2(xABCD如圖如圖2-22-2（續）（續）（3 3）繪制目標函數曲線）繪制目標函數曲線 該該問題的目標是在問題的目標是在拋物線段拋物線段ABCDABCD上找上找一個點，使得這個點一個點，使得這個點到到(2,1)(2,1)T T的距離的平方的距離的平方最小（最小（距離本身也是距離本身也是最小最小）。這樣的點位）。這樣的點位于以于以(2,1)(2,1)T T為圓心的圓為圓心的圓周上。由圖示可知，周上。由圖示可知，點點D D到到(2,1)(2,1)T T的距離最的距離最小。即小。即D(4,1)

31、D(4,1)T T就是拋就是拋物線段物線段ABCDABCD上到點上到點(2,1)(2,1)T T距離平方最小的距離平方最小的點。點。2.2 2.2 非線性規劃的解的概念非線性規劃的解的概念2.2.1 2.2.1 局部極小（極大）點局部極小（極大）點 如右圖所示，點如右圖所示，點B(2.9104,4.3275)B(2.9104,4.3275)T T比附近的其比附近的其它點對應的目標函數值都小，它點對應的目標函數值都小，稱稱為為局部極小點局部極小點，對應的目，對應的目標值標值f(B)f(B)為為局部極小值局部極小值；點；點C(6.25,2.5)C(6.25,2.5)T T對應的目對應的目標函數值比

32、附近的其它目標函數值都大，稱為標函數值比附近的其它目標函數值都大，稱為局部極局部極大點大點，對應的目標函數，對應的目標函數f( C )f( C )稱為稱為局部極大值局部極大值。 因為拋物線段因為拋物線段ABCDABCD上，上，B B 左右的點到左右的點到(2,1)(2,1)T T的距離的距離都大于都大于B B到到(2,1)(2,1)T T的距離；的距離；C C左右的點到左右的點到(2,1)(2,1)T T的距離都小的距離都小于于C C到到(2,1)(2,1)T T的距離的距離。2.2.2 2.2.2 全局最小（最大）點全局最小（最大）點 如右圖所示，點如右圖所示，點D(4,1)D(4,1)T

33、T到到(2,1)(2,1)T T的距離小于拋物線的距離小于拋物線段段ABCDABCD上其它任何點到上其它任何點到(2,1)(2,1)T T的距離，稱點的距離，稱點D D為此為此規劃的規劃的全局最小值點全局最小值點，f(D)f(D)稱為稱為全局最小值全局最小值。點點A(0,5)A(0,5)T T到點到點(2,1)(2,1)T T的距離大于拋物線段的距離大于拋物線段ABCDABCD上任何點上任何點到到(2,1)(2,1)T T的距離，稱點的距離，稱點A A為全為全局最大值點局最大值點，f(A)f(A)稱為稱為全局全局最大值最大值。3.13.1、線性規劃求解的特點、線性規劃求解的特點例例3 3的圖解

34、法截圖的圖解法截圖3、線性規劃與非線性規劃最優解求解的根本區別線性規劃與非線性規劃最優解求解的根本區別例例4 圖解法截圖圖解法截圖線性規劃最優解的特點線性規劃最優解的特點：（1 1）線性規劃的可行域都是直）線性規劃的可行域都是直線段圍成的（凸）多邊形區域；線段圍成的（凸）多邊形區域；（2 2）只要線性規劃存在最優）只要線性規劃存在最優解（不管是唯一最優解還是解（不管是唯一最優解還是無窮多最優解），就一定會無窮多最優解），就一定會在邊界的在邊界的頂點處頂點處到達；到達；（3 3）尋找線性規劃最優解的原理：）尋找線性規劃最優解的原理：【單純形法單純形法】 步驟步驟1 1： 在在OQOQ1 1Q Q

35、2 2Q Q3 3Q Q4 4O O邊界上，任取一邊界上，任取一個頂點，比如個頂點，比如O O點，計算點，計算O O的目標函數值，比較的目標函數值，比較O O與相與相鄰的頂點鄰的頂點Q Q1 1和和Q Q4 4對應的的目標函數值，如果對應的的目標函數值，如果O O點的目標點的目標函數值最大（最大化目標），函數值最大（最大化目標），O O就是最優解；就是最優解；步驟步驟2 2：如果存在相鄰點對：如果存在相鄰點對應的目標函數值比應的目標函數值比O O點對應點對應的目標函數值大（比如的目標函數值大（比如Q Q1 1) )，用用Q Q1 1點代替剛才的點代替剛才的O O點，重點，重復步驟復步驟1 1，

36、直到某個點對應，直到某個點對應的目標函數值比相鄰的點對的目標函數值比相鄰的點對應的目標函數值都大。應的目標函數值都大。對線性規劃解的全局性：對線性規劃解的全局性： 對于線性規劃問題，得到的對于線性規劃問題，得到的任何一個最優解任何一個最優解都是都是全局最優解全局最優解。3.23.2、非線性規劃求解的特點、非線性規劃求解的特點例例8 8圖解法截圖圖解法截圖 非線性規劃求解原理和非線性規劃求解原理和線性規劃求解原理大致都線性規劃求解原理大致都用用迭代法迭代法。步驟步驟1 1：如右圖所示，在可：如右圖所示，在可行域行域ABCDABCD拋物線段上任取拋物線段上任取一個初始點一個初始點O O（有風險有風

37、險），），比如這個初始點選在比如這個初始點選在ABAB之之間的某點；間的某點；步驟步驟2 2：從：從O O點分別試著朝點分別試著朝A A和朝和朝B B方向走，比較哪個方方向走，比較哪個方向會讓目標函數減小（最小化目標，如果有多個方向，向會讓目標函數減小（最小化目標，如果有多個方向，就選取目標函數減小最快的方向），就準備朝那個方向就選取目標函數減小最快的方向），就準備朝那個方向邁出步伐；邁出步伐；步驟步驟3 3：確定了朝：確定了朝B B方向目標方向目標函數會減小，就朝函數會減小，就朝B B方向跨方向跨出最大一步，到達步伐的終出最大一步，到達步伐的終點點O O1 1；步驟步驟4 4：用：用O O1

38、 1替代替代O O點，重復點，重復步驟步驟1313，直到沒有方向可，直到沒有方向可走為止。走為止。非線性規劃迭代法計算的風險非線性規劃迭代法計算的風險：尋找最小（或最大）依：尋找最小（或最大）依賴于初始點。比如剛才的迭代初始值選在賴于初始點。比如剛才的迭代初始值選在ABAB之間，就會之間，就會將將B B點誤作為全局最小值點。規避這種風險的方法除了點誤作為全局最小值點。規避這種風險的方法除了從迭代方法上作改進從迭代方法上作改進 ，就是，就是多選幾個初始點多選幾個初始點計算，然后計算，然后比較每次計算的最優解，再選取你認為最合適的一個點比較每次計算的最優解，再選取你認為最合適的一個點為全局最優解為

39、全局最優解。（例如：。（例如：設設wifiwifi信號源在信號源在(2,1)(2,1)T T，你拿著，你拿著手機在手機在ABC DABC D段上找離信號源最近的點）段上找離信號源最近的點）三、按照決策變量要求識別規劃模型三、按照決策變量要求識別規劃模型 1 1、整數規劃模型、整數規劃模型 部分決策變量要求取整數，這個要求人能識別，智能機器能識別，同時要求軟件能識別； 2 2、0-10-1規劃規劃 對于“是”與“非”的選擇問題，多用0-1變量來實現，同樣要求人、機器、軟件都能識別； 3 3、通過案例、通過案例學習，了解不同變量之間的交叉約束的線性約束表達。 1 1、整數規劃模型整數規劃模型例例9

40、 9 貨物托運貨物托運問題（一般整數規劃）問題（一般整數規劃） 某某公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨公司擬用集裝箱托運甲、乙兩種貨物，這兩種貨物每件的體積、重量，可獲利潤以及托運限制如表物每件的體積、重量，可獲利潤以及托運限制如表1-21-2貨物貨物每件體積每件體積/ /英英尺尺3 3每件重量每件重量/100kg/100kg每件利潤每件利潤/ /百元百元甲甲1951954 42 2乙乙27327340403 3托運限制托運限制13651365140140表表1-21-2 且且甲種貨物最多托運甲種貨物最多托運4 4件，問兩種貨物各托運多少件，問兩種貨物各托運多少件，可獲利最大。件，可獲

41、利最大。【問題假設問題假設】（1 1）甲乙兩種貨物不可分割，即按整數計件；）甲乙兩種貨物不可分割，即按整數計件；（2 2）甲乙兩貨物的體積可以直接）甲乙兩貨物的體積可以直接相加（軟體積）。比如水的相加（軟體積）。比如水的體積，就是所占空間的體積（軟體積）；碎石的體積就比所體積，就是所占空間的體積（軟體積）；碎石的體積就比所占空間的體積小（硬體積）。占空間的體積小（硬體積）。【符號設置符號設置】x x1 1 甲貨物裝運的件數；甲貨物裝運的件數；x x2 2 乙貨物裝運的件數；乙貨物裝運的件數；z z 一次運輸的利潤（單位：百元）一次運輸的利潤（單位：百元）【建立模型建立模型】根據問題描述，則總利

42、潤為根據問題描述，則總利潤為;x32xz21【問題分析問題分析】（此問題已高度簡化，（此問題已高度簡化， 問題分析問題分析 略去）略去）運輸體積約束運輸體積約束;1365327195x21x運輸重量約束運輸重量約束;140 x40 x421貨物要求約束貨物要求約束;4x1貨物分割要求貨物分割要求x x1 1,x ,x2 2要求取整數；要求取整數；非負約束非負約束.0 x,x21【數學模型數學模型】2132maxxxz, 0 x,x, 4x,140 x40 x4,1365x273x195. t . s2112121x x1 1,x ,x2 2取取整（或整（或x x1 1,x ,x2 2Z Z）線

43、性規劃線性規劃整整數數線線性性規規劃劃 這種這種要求所有決策變量的線性規劃就稱為要求所有決策變量的線性規劃就稱為線性整線性整數規劃數規劃；要求部分變量取整的稱為；要求部分變量取整的稱為混合線性整數規劃。混合線性整數規劃。例例10 投資場所的投資場所的選擇（一般選擇（一般0-1規劃）規劃） 某某公司計劃在市區的東、南、西、北四個區建立銷公司計劃在市區的東、南、西、北四個區建立銷售門面。擬議中有售門面。擬議中有1010個位置個位置A Ai i( (i i=1,2,10)=1,2,10)可供選擇，考可供選擇，考慮到各個地區居民消費水平以及居民的居住密度，慮到各個地區居民消費水平以及居民的居住密度，規

44、定：規定： 在在東區東區A A1 1,A,A2 2,A,A3 3三個點中至少選擇兩個；三個點中至少選擇兩個； 在在西區西區A A4 4,A,A5 5兩個點中至少選擇一個；兩個點中至少選擇一個； 在在南區南區A A6 6,A,A7 7兩個點中至少選擇一個；兩個點中至少選擇一個； 在在北區北區A A8 8,A,A9 9,A,A1010三個點中至少選擇三個點中至少選擇2 2個。個。 A Ai i各個點的設備投資以及每年可獲利潤由于地點各個點的設備投資以及每年可獲利潤由于地點不同都不一樣，預測情況如下表不同都不一樣，預測情況如下表 A A1 1A A2 2A A3 3A A4 4A A5 5A A6

45、6A A7 7A A8 8A A9 9A A1010投資額投資額1001001201201501508080707090908080140140160160180180利利 潤潤3636404050502222202030302525484858586161 另外，投資總額不能超過另外，投資總額不能超過720720萬元，問應該選擇哪幾萬元，問應該選擇哪幾家銷售點，可使得年利潤為最大？家銷售點，可使得年利潤為最大？【問題分析問題分析】 根據問題的敘述，每個點最多建立一個銷售網點，根據問題的敘述，每個點最多建立一個銷售網點，若設若設x xi i為第為第i i小區建立的銷售網點數小區建立的銷售網點數

46、，則，則10,.,2, 1, 10iZxxii0, 1xi在第在第i i個點建立銷售網點個點建立銷售網點在第在第i i個點不建銷售網點個點不建銷售網點i=1,2,10i=1,2,10這樣的這樣的0-10-1決策變量決策變量，有如下，有如下性質性質： 即即對每個點對每個點x xi i來說，來說，要么取要么取0 0，要么取，要么取1 1，這樣的變，這樣的變量就稱為量就稱為0-10-1變量，因此，變量也可以設成變量，因此，變量也可以設成（1 1）x xi i+x+xj j=1=1：x xi i和和x xj j有且只有一個取有且只有一個取1 1，另外一個取，另外一個取0 0；（2 2）x xi i+x

47、+xj j=1=1=1：x xi i和和x xj j至少一個取至少一個取1 1；（4 4）kxkxj j： 要么取要么取k k，要么取，要么取0 0；（5 5）x x1 1+x+x2 2+x xm m=p(p=m)=p(p=m)：m m個中恰好取個中恰好取p p個；個；（6 6）x x1 1+x+x2 2+ + +x xm m=p=p=p：m m個中至少取個中至少取p p個；個；（8 8）x xi i=x xj j：若第：若第j j個被選中，則第個被選中，則第i i個也被選中。個也被選中。思考思考：x xi i+x+xj j=x xk k表達的意思？表達的意思？【問題假設問題假設】（1 1）每

48、個點最多建立一個門面。）每個點最多建立一個門面。【符號設置符號設置】x xi i 點點A Ai i建立的門面數，建立的門面數，i=1,2,10i=1,2,10，其中，其中z z 表示年總利潤。表示年總利潤。10,.,2, 1, 10iZxxii根據問題敘述，總利潤為根據問題敘述，總利潤為;6158482530202250403610987654321xxxxxxxxxxz總投資額約束總投資額約束;720 x180 x160 x140 x80 x90 x70 x80 x150 x120 x10010987654321【建立模型建立模型】選擇約束選擇約束：; 2xxx321; 1xx54; 1xx

49、76; 2xxx1098東區東區A A1 1,A,A2 2,A,A3 3三個點至少選擇兩個三個點至少選擇兩個: :西區西區A A4 4,A,A5 5兩個點至少選擇一個：兩個點至少選擇一個：南區南區A A6 6,A,A7 7兩個點至少選擇一個：兩個點至少選擇一個：北區北區A A8 8,A,A9 9,A,A1010三個點至少選擇兩個：三個點至少選擇兩個：變量約束變量約束：.10,.,2, 1i,1 ,0 xi【數學模型數學模型】;x61x58x48x25x30 x20 x22x50 x40 x36zmax10987654321,720 x180 x160 x140 x80 x90 x70 x80

50、x150 x120 x10010987654321, 2xxx321, 1xx54, 1xx76, 2xxx1098.10,.,2, 1i,1 ,0 xis.t. 像像這種這種決策變量只取決策變量只取0 0和和1 1的線性規劃的線性規劃，稱為，稱為0-10-1線性規劃線性規劃，屬，屬于特殊的整數線性規劃，在實際問題中應用廣泛。于特殊的整數線性規劃，在實際問題中應用廣泛。軟件也能識別！軟件也能識別！例例11 11 固定成本固定成本問題問題( (變量交叉約束變量交叉約束） 高壓高壓容器公司制造小、中、大三種尺寸的金屬容容器公司制造小、中、大三種尺寸的金屬容器，所用資源為金屬板、勞動力和機器設備，制

51、造一器，所用資源為金屬板、勞動力和機器設備，制造一個容器的各種資源的數量如表個容器的各種資源的數量如表1-31-3所示所示表表1-31-3資資 源源小號容器小號容器中號容器中號容器 大號容器大號容器金屬板金屬板/t /t勞動力勞動力/ /（人（人/ /月）月）機器設備機器設備/ /（臺（臺/ /月）月）2 22 21 14 43 32 28 84 43 3 不不考慮固定費用，每種容器出售一只的利潤分別考慮固定費用，每種容器出售一只的利潤分別為為4 4萬元，萬元，5 5萬元，萬元，6 6萬元，可使用的金屬板有萬元，可使用的金屬板有500t500t，勞，勞動力有動力有300300人人/ /月，機器

52、有月，機器有100100臺臺/ /月。月。 此外此外，只要生產，不管每種容器的制造數量是多少，只要生產，不管每種容器的制造數量是多少，都要支付一筆固定的費用，小號為都要支付一筆固定的費用，小號為100100萬元，中號為萬元，中號為150150萬元，大號為萬元，大號為200200萬元。現在要制定一個月生產計劃，萬元。現在要制定一個月生產計劃，使得獲利為最大。使得獲利為最大。【問題分析問題分析】 此問題是一個生產決策問題，決策者需要決定三種此問題是一個生產決策問題，決策者需要決定三種型號的容器各生產多少件。不管哪種型號的容器，只要型號的容器各生產多少件。不管哪種型號的容器，只要產量在產量在1 1件

53、或件或1 1件以上，就需要鋪設生產線，其固定費用件以上，就需要鋪設生產線，其固定費用需要支出；若此型號的容器的產量為需要支出；若此型號的容器的產量為0 0，就不用鋪設生，就不用鋪設生產線，就不需要支出固定費用。產線，就不需要支出固定費用。【問題假設問題假設】（1 1）不管哪種容器，不可分割，即整數計件；）不管哪種容器，不可分割，即整數計件；（2 2）生產常識：如果某種容器不生產）生產常識：如果某種容器不生產( (產量為產量為0 0），則固），則固定費用不用支出；定費用不用支出；【符號設置符號設置】x x1 1,x ,x2 2,x ,x3 3 表示小、中、大三種容器的產量；表示小、中、大三種容器的產量；y y1 1 表示表示生產