《高級運籌學》非線性規(guī)劃模型及基本概念

1、.高級運籌學北京物資學院研究生課程北京物資學院研究生課程信息學院信息學院 李珍萍李珍萍.Operations Research, Operational Reasearch直譯為直譯為“運用研究運用研究” 或或 “作業(yè)研究作業(yè)研究”許國志等根據(jù)史記中：許國志等根據(jù)史記中：“運籌于帷幄之中，決運籌于帷幄之中，決勝于千里之外勝于千里之外”將其翻譯成將其翻譯成“運籌學運籌學”運籌學是運用科學的數(shù)量方法運籌學是運用科學的數(shù)量方法主要是數(shù)學模主要是數(shù)學模型型研究對人力、物力進行合理籌劃和運用，研究對人力、物力進行合理籌劃和運用，尋找管理及決策最優(yōu)方案的綜合性學科。尋找管理及決策最優(yōu)方案的綜合性學科。.本

2、學期教學內(nèi)容本學期教學內(nèi)容 非線性規(guī)劃非線性規(guī)劃 第一章：非線性規(guī)劃模型及基本概念第一章：非線性規(guī)劃模型及基本概念 第二章：無約束非線性規(guī)劃第二章：無約束非線性規(guī)劃 第三章：約束非線性規(guī)劃第三章：約束非線性規(guī)劃 第四章：多目標規(guī)劃第四章：多目標規(guī)劃 現(xiàn)代優(yōu)化算法簡介現(xiàn)代優(yōu)化算法簡介 .非線性規(guī)劃非線性規(guī)劃教學參考書教學參考書1 1 施光燕、董加禮施光燕、董加禮, ,最優(yōu)化方法最優(yōu)化方法 高等教育出版社，高等教育出版社，20042004。2 2 施光燕、錢偉懿，龐麗萍，最優(yōu)化方法（第二版）高等施光燕、錢偉懿，龐麗萍，最優(yōu)化方法（第二版）高等 教育出版社，教育出版社，20072007。3 3 郭科

3、等郭科等 最優(yōu)化方法及應(yīng)用，高等教育出版社，最優(yōu)化方法及應(yīng)用，高等教育出版社， 2007 2007 。.非線性規(guī)劃模型非線性規(guī)劃模型及基本概念及基本概念信息學院信息學院 李珍萍李珍萍20152015年年9 9月月研究生研究生高級運籌學高級運籌學課件課件.本章內(nèi)容 一、非線性規(guī)劃的數(shù)學模型一、非線性規(guī)劃的數(shù)學模型 1. 1. 非線性規(guī)劃問題實例非線性規(guī)劃問題實例 2. 2. 非線性規(guī)劃問題的數(shù)學模型非線性規(guī)劃問題的數(shù)學模型 二、基本概念二、基本概念.例例1 把邊長為把邊長為a的正方形鐵板的四個角處剪去相等的正的正方形鐵板的四個角處剪去相等的正方形以制成方形無蓋水槽，問如何剪法使水槽的容積最方形以

4、制成方形無蓋水槽，問如何剪法使水槽的容積最大？大？解：設(shè)剪去的正方形邊長為解：設(shè)剪去的正方形邊長為x （ 0 x a/2) , 做成的無蓋水做成的無蓋水槽體積為：槽體積為：2( ) (2 )f xaxx該問題的數(shù)學模型為：求該問題的數(shù)學模型為：求x （ 0 x a/2)，使使 f (x) 達到達到最大，即：最大，即： 20/2max( )(2 )x af xaxx 1. 1. 非線性規(guī)劃問題實例非線性規(guī)劃問題實例一、非線性規(guī)劃的數(shù)學模型一、非線性規(guī)劃的數(shù)學模型.例例2 已知某規(guī)劃區(qū)內(nèi)有已知某規(guī)劃區(qū)內(nèi)有m個客戶，第個客戶，第i個客戶的位置坐標為個客戶的位置坐標為(ai,bi)，現(xiàn)要在該區(qū)域內(nèi)選定

5、一個位置建立配送中心為客戶供，現(xiàn)要在該區(qū)域內(nèi)選定一個位置建立配送中心為客戶供應(yīng)商品。問如何選定配送中心的位置，才能使配送中心到各應(yīng)商品。問如何選定配送中心的位置，才能使配送中心到各用戶的總距離最??？用戶的總距離最小？解：設(shè)配送中心的位置坐標為解：設(shè)配送中心的位置坐標為(x1,x2), 則則2212121min( ,)()()miiif x xxaxb.例例3 3 求表面積為常數(shù)求表面積為常數(shù)6a2 (a0), 體積最大的長方體體積。體積最大的長方體體積。解：設(shè)長方體的長、寬、高分別為解：設(shè)長方體的長、寬、高分別為x1,x2,x3. 則則1231232121323123max(,). .2()6

6、0,0,0f x xxx x xstx xx xx xaxxx.例例4 設(shè)有設(shè)有400萬元資金，要求萬元資金，要求4年內(nèi)使用完，若在一年內(nèi)使用年內(nèi)使用完，若在一年內(nèi)使用資金資金x萬元，則可得效益萬元，則可得效益 萬元（已使用的資金不能再次使萬元（已使用的資金不能再次使用，獲得的效益當年不能使用），當年不用的資金可存入銀用，獲得的效益當年不能使用），當年不用的資金可存入銀行，年利率為行，年利率為10%,試制定出資金使用規(guī)劃，使試制定出資金使用規(guī)劃，使4年的效益之年的效益之和最大和最大.x解：設(shè)解：設(shè)xi (i=1,2,3,4)分別表示第分別表示第i年所使用的資金數(shù)，則年所使用的資金數(shù)，則1234

7、1211311224112233max( )04000(400) 1.1. .0(400) 1.1 1.10(400) 1.1 1.1 1.1f xxxxxxxxxstxxxxxxxxxxxx.123411121122311223341234max( )4001.1440. . 1.211.11.14841.3311.211.211.11.1532.4,0f xxxxxxxxxstxxxxxxxxxxxxx x x x化簡得.SETS:N/1.4/:X;ENDSETSmax=sum(N(i):X(i)0.5);X(1)400;1.1*X(1)-(X(1)(1/2)+X(2)440;1.21*X

8、(1)-1.1*(X(1)(1/2)+1.1*X(2)-(X(2)(1/2)+X(3)484;1.331*X(1)-1.21*(X(1)(1/2)+1.21*X(2)-1.1*(X(2)(1/2)+1.1*X(3)-(X(3)(1/2)+X(4)532.4; Local optimal solution found. Extended solver steps: 5 Total solver iterations: 86 Variable Value Reduced Cost .例例5 5 某公司專門生產(chǎn)儲藏用的容器，訂貨合同要求該公某公司專門生產(chǎn)儲藏用的容器，訂貨合同要求該公司制造一種敞口的

9、長方體容器，容積為司制造一種敞口的長方體容器，容積為12 m12 m3 3 , ,該容器的該容器的底必須為正方形，容器總重量不超過底必須為正方形，容器總重量不超過68kg68kg，已知制作容，已知制作容器四壁的材料為每平方米器四壁的材料為每平方米1010元，重元，重3kg3kg；制作容器底的材；制作容器底的材料每平方米料每平方米2020元，重元，重2kg2kg。試問制造該容器所需的最小費。試問制造該容器所需的最小費用是多少？用是多少？解：設(shè)該容器的底邊長和高分別為解：設(shè)該容器的底邊長和高分別為x1 m, ,和和x2 m. .則則2121212211212min( )4020. .1221268

10、,0f xx xxstx xxx xx x.SETS:N/1.2/:X;ENDSETSmin=40*X(1)*X(2)+20*(X(2)2;(X(1)2*X(2)=12;2*(X(1)2+12*X(1)*X(2)68; Local optimal solution found. Extended solver steps: 5 Total solver iterations: 78 Variable Value Reduced Cost .例例6 有一底面為長方形的烤箱，長為有一底面為長方形的烤箱，長為L，寬為，寬為W。某公司要。某公司要為該烤箱制造一批蛋糕烤盤，要求蛋糕烤盤的底面積為為該烤箱

11、制造一批蛋糕烤盤，要求蛋糕烤盤的底面積為A, 底面形狀為矩形兩端加半圓（如下圖所示）。問如何設(shè)計烤底面形狀為矩形兩端加半圓（如下圖所示）。問如何設(shè)計烤盤尺寸才能使烤箱一次烤出的蛋糕數(shù)量達到最多？盤尺寸才能使烤箱一次烤出的蛋糕數(shù)量達到最多？.解：假設(shè)烤箱中的烤盤按行列整齊排放。解：假設(shè)烤箱中的烤盤按行列整齊排放。設(shè)烤箱中可放置的烤盤數(shù)量為設(shè)烤箱中可放置的烤盤數(shù)量為n行，行， m 列。每個烤盤所占最列。每個烤盤所占最大矩形的長、寬分別為大矩形的長、寬分別為x, y，烤盤兩端的半圓半徑為，烤盤兩端的半圓半徑為r。顯然顯然2r等于等于x,y的最小值。的最小值。22max42(1). . 22, ,0,

12、00,1fmnmxLnyWxyrrArkxk ys trxryr x ym nk 且且為為整整數(shù)數(shù)1,20,2rxkry .一般最優(yōu)化問題的數(shù)學模型一般最優(yōu)化問題的數(shù)學模型min( )(1). .( )0(1,2,., )(2)( )0(1,2,.,)(3)jinf xst h xjlg ximxR如果目標函數(shù)和約束條件都是線性函數(shù)，則稱為如果目標函數(shù)和約束條件都是線性函數(shù)，則稱為線性規(guī)劃線性規(guī)劃。否則稱為否則稱為非線性規(guī)劃非線性規(guī)劃。如果要求部分或全部變量為整數(shù)，則稱為如果要求部分或全部變量為整數(shù)，則稱為整數(shù)規(guī)劃整數(shù)規(guī)劃。2. 非線性規(guī)劃問題的數(shù)學模型非線性規(guī)劃問題的數(shù)學模型.無約束非線性規(guī)

13、劃問題無約束非線性規(guī)劃問題一般非線性規(guī)劃問題的數(shù)學模型一般非線性規(guī)劃問題的數(shù)學模型min( )(1). .( )0(1,2,., )(2)( )0(1,2,.,)(3)jinf xst h xjlg ximxRmin( )nx Rf x.二、基本概念二、基本概念1. 局部極小點局部極小點：現(xiàn)有多元函數(shù) f(x1,x2,xn), 若點 x 0 = (x10, x20, xn0)T 存在一鄰域(x0), 使對任意x (x0), 均有 f (x0) f(x), 則稱 x 0是 f(x) 的局部極小點。.2. 方向?qū)?shù)方向?qū)?shù) 定義定義: 設(shè)設(shè) 在點在點x0處可微，處可微，P是固定不變的是固定不變的非

14、零向量，非零向量，e是方向是方向P上的單位向量，則稱極限上的單位向量，則稱極限 為函數(shù)為函數(shù)f(x) 在點在點x 0處沿處沿P方向的方向?qū)?shù)，方向的方向?qū)?shù)，記作記作 1:RRfn0000()()()limtf xf xtef xPt0()f xP.3. 3. 下降方向下降方向.4. 梯度： 定義定義: : 以f(x) 的n個偏導數(shù)為分量的向量稱為f(x) 在x處的梯度，記為梯度也可以稱為函數(shù) f(x) 關(guān)于向量 x 的一階導數(shù).12( )( )( )( )Tnf xf xf xf xxxx.若0()0Tf xP則P是函數(shù)f(x)在點x0處的下降方向。0()0Tf xP則P是函數(shù)f(x)在點x

15、0處的上升方向。若5. 5. 梯度和方向?qū)?shù)的關(guān)系梯度和方向?qū)?shù)的關(guān)系00()()Tf xf xeP 其中e是方向P上的單位向量。.(1)梯度方向是函數(shù)值的最速上升方向；(2)函數(shù)在與其梯度正交的方向上變化率為零；(3)函數(shù)在與其梯度成銳角的方向上是上升的，而在與其梯度成鈍角的方向上是下降的；(4)梯度反方向是函數(shù)值的最速下降方向.例7：求函數(shù) f(x)=x12+x22+1在 (0，3)T 處的最速下降方向，并求沿最速下降方向移動一個單位后新的目標函數(shù)值。122( )2xf xx(0,3)0( )|6f x沿最速下降方向移動一個單位后的點為(0，2)T，新的目標函數(shù)值為 5.解：.定義: 若f

16、(x)二階可微，則以其二階偏導數(shù)為元素構(gòu)成的下列矩陣稱為f(x)的Hesse矩陣22221121222222122222212( )( )( )( )( )( )( )( )( )( )nnnnnf xf xf xxx xx xf xf xf xf xx xxx xf xf xf xx xx xx6. Hesse 6. Hesse 矩陣矩陣.例8 求下列函數(shù)的梯度及hesse矩陣23132221233241432)(xxxxxxxxxXf32112322213321342( )64642xx xxf xxxxxxx x212132123112222( )21242462xxxxf xxxxx.7. 泰勒展開式泰勒展開式設(shè)f(x)具有二階連續(xù)偏導數(shù)，則其中21()( )( )( )2TTf xPf xf xPPf x