第一讲规划问题的基本概念

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 表示表示生产