第1-6节

null运筹学（下）运筹学（下）运筹学的研究内容运筹学的研究内容null1. 数学规划论： （1）线性规划（linear programming）：线性规划问题的建模相对简单，有通用算法和计算机软件，是运筹学应用最广泛的一个分支； （2）整数规划（integer programming）：如线性规划中的决策变量要求为整数，这类模型的研究构成整数规划分支； null（3）目标规划（goal programming）：解决多目标决策问题。 （4）非线性规划（nonlinear programming）：如线性规划中的目标 函数 excel方差函数excelsd函数已知函数     2 f x m x mx m      2 1 4 2拉格朗日函数pdf函数公式下载 或约束条件不全是线性的，这类模型的研究构成非线性规划分支； （5）动态规划（dynamic programming）：研究多阶段决策过程最优化的运筹学分支。null 2. 图论（graph theory） 图论——研究由节点和边所组成图形的数学理论和方法。 3. 网络分析（network analysis） 网络分析——研究具体网络对象（如铁路网、电力网、通信网）。图论是网络分析的基础。 null4. 排队论（queuing theory）：研究生产和生活中存在的有形和无形的排队和拥挤现象。 5. 存储论（inventory theory）：研究最优存储策略的理论和方法。null6. 对策论（game theory）：研究对抗局势问题。系统中参与对抗的各方成为局中人，他们各自按照有利于自己的方式活动，但又无法精确预测其他局中人的行为。对策论为局中人提供一套定量化和程序化的选择策略的理论和方法。 null7. 决策论（decision theory）：随着科学技术的发展，要求科学决策取代经验决策。决策论就是研究科学地决策方法。形成问题、提出 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 、效果度量、综合评价，一直到最优方案的选取。 null8. 启发式智能优化方法 方法不追求严格最优，具有启发式思路，并借助来自生物学、物理学和其他学科的思想来解决问题。 ——遗传算法（GA） ——模拟退伙算法（SA） ——神经网络（NN） ——模糊逻辑（FL） ——进化计算（EC） ——禁忌算法（TS）运筹学应用的工具运筹学应用的工具null主要是数学和电子计算机。参 考 书 目参 考 书 目null运筹学，《运筹学》教材编写组编，清华大学出版社 运筹学教程，胡运权主编，清华大学出版社 现代优化计算方法，邢文训、谢金星编著，清华大学出版社 非数值并行算法——模拟退火算法，康立山等著，科学出版社 非数值并行算法——遗传算法，康立山等著，科学出版社 遗传算法的数学基础，张文修等编著，西安交通大学出版社 进化计算，王正志等著，国防科技大学出版社第一章 无约束非线性规划问题 第一章 无约束非线性规划问题 在生产管理和经营活动中经常提出以下两类问题： 1.如何利用有限的人力、物力、财力等资源安排生产，使产值最大或利润最高。 2.对给定的任务，如何统筹安排，以便用最少的人力、物力、财力等资源消耗去完成任务。在生产管理和经营活动中经常提出以下两类问题： 1.如何利用有限的人力、物力、财力等资源安排生产，使产值最大或利润最高。 2.对给定的任务，如何统筹安排，以便用最少的人力、物力、财力等资源消耗去完成任务。对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究，构成了运筹学的一个重要分支——数学规划论。 对于这种从生产的计划与组织中提出的达到最大收益或最小支付为目的的问题研究，构成了运筹学的一个重要分支——数学规划论。 数学规划论 数学规划论 线性规划 (Linear Programming, LP) 非线性规划 (Nonlinear Programming, NLP) 自1974年丹捷格（G.B. Dantzig）提出线性规划问题的求解方法——单纯形法之后，使得线性规划在理论上趋向成熟，并在管理决策、经济计划、交通运输业、最优化 设计 领导形象设计圆作业设计ao工艺污水处理厂设计附属工程施工组织设计清扫机器人结构设计 等领域发挥了重要作用。 线性规划已成为现代科学管理的重要手段之一。自1974年丹捷格（G.B. Dantzig）提出线性规划问题的求解方法——单纯形法之后，使得线性规划在理论上趋向成熟，并在管理决策、经济计划、交通运输业、最优化设计等领域发挥了重要作用。 线性规划已成为现代科学管理的重要手段之一。在科学管理和其他领域，对一些实际问题所建立的数学模型其目标函数和约束条件都是自变量的一次函数，即可以归结为线性规划问题。在科学管理和其他领域，对一些实际问题所建立的数学模型其目标函数和约束条件都是自变量的一次函数，即可以归结为线性规划问题。null线性规划问题的特征 线性规划属于一类优化问题，它们的共同特征为： 每个问题都用一组决策变量（x1,x2,…,xn）表示某一方案。这组决策变量的值代表一个具体方案，这些变量一般取值都是非负的。null存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示。 都有一个要求表达的目标，它可用决策变量的线性函数来表示（称为目标函数），按问题的不同，要求目标函数实现最大化或最小化。 null线性规划问题的数学模型 满足以上三个条件的数学模型称为线性规划的数学模型： 目标函数 max(min) z=c1x1 + c2x2 +…+ cnxn 约束条件 a11x1 + a12x2 +…+ a1nxn ≤ (=,≥) b1 a21x1 + a22x2 +…+ a2nxn ≤ (=,≥) b2 ………… am1x1 + am2x2 +…+ amnxn ≤ (=,≥) bm x1, x2, …, xn ≥ 0nullmax z = 2x1 + 3x2是线性规划max z = 2x1 + 3x2不是线性规划不是线性规划但很多实际问题所建立的数学模型其目标函数和约束条件都很难表达为自变量的线性函数。 即目标函数和约束条件中含有非线性函数，称这种数学规划问题为非线性规划问题。但很多实际问题所建立的数学模型其目标函数和约束条件都很难表达为自变量的线性函数。 即目标函数和约束条件中含有非线性函数，称这种数学规划问题为非线性规划问题。非线性规划是 20 世纪 50 年代开始形成的一门新兴学科。 1951年H.W.库恩和A.W.塔克发表的关于最优性条件(后来称为库恩－塔克条件)的论文是非线性规划正式诞生的一个重要标志。非线性规划是 20 世纪 50 年代开始形成的一门新兴学科。 1951年H.W.库恩和A.W.塔克发表的关于最优性条件(后来称为库恩－塔克条件)的论文是非线性规划正式诞生的一个重要标志。50 年代末到 60 年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。 非线性规划问题在近几十年来得到了长驱发展，在管理科学、系统控制、最优设计等许多领域得到越来越广泛的应用。50 年代末到 60 年代末出现了许多解非线性规划问题的有效的算法，70年代又得到进一步的发展。 非线性规划问题在近几十年来得到了长驱发展，在管理科学、系统控制、最优设计等许多领域得到越来越广泛的应用。由于非线性规划问题中，其目标函数或约束条件含有非线性函数，故求解非线性规划问题要比求解线性规划问题困难得多。由于非线性规划问题中，其目标函数或约束条件含有非线性函数，故求解非线性规划问题要比求解线性规划问题困难得多。非线性规划问题非线性规划问题线性规划问题单纯形法等通用方法没有适用于各种问题的一般算法第一节 基本概念 第二节 非线性规划的图解法 第三节 极值问题 第四节 凸函数和凹函数 第五节 凸规划 第六节 跌代算法 第七节 一维搜索 第八节 无约束非线性规划问题的解法——梯度法 第九节 无约束非线性规划问题的解法——共轭梯度法 第十节 无约束非线性规划问题的解法——牛顿法 第十一节 无约束非线性规划问题的解法——变尺度法第一节 基本概念 第二节 非线性规划的图解法 第三节 极值问题 第四节 凸函数和凹函数 第五节 凸规划 第六节 跌代算法 第七节 一维搜索 第八节 无约束非线性规划问题的解法——梯度法 第九节 无约束非线性规划问题的解法——共轭梯度法 第十节 无约束非线性规划问题的解法——牛顿法 第十一节 无约束非线性规划问题的解法——变尺度法第一节 基本概念第一节 基本概念null一、问题的提出 例1 某工厂生产I、II两种产品。已知生产一件产品 I 所需原材料为 0.5 吨，生产一件产品 II 所需原材料为（2+0.25x2）吨。工厂共有800吨原材料。 又知道，每生产一件产品 I 可获得 30 元，每生产一件产品 II 可获得 450 元，问应如何制定生产计划才能够使得盈利做大？null解：生产计划就是要确定生产产品 I 和 II 各多少件。 故问题的决策变量为需要生产产品I的数量、生产产品II的数量。 设需要生产产品I的数量：x1 设需要生产产品II的数量：x2null对生产计划（即产品 I 和 II 的生产数量）造成影响的制约因素有一个，为： 原材料数限制： 0.5 x1 + ( 2 + 0.25 x2) x2 ≤ 800问题的目标是使得创造的利润达到最大，用 z 表示所创造的利润值，则可表示为： max z = 30 x1 + 450 x2 null综上所述，建立问题的数学模型为： 目标函数： max z = 30 x1 + 450 x2约束条件：null二、非线性规划问题的特征 每个问题都用一组决策变量（x1,x2,…,xn）表示某一方案。这组决策变量的值代表一个具体方案。 存在一定的约束条件，这些约束条件可以用一组等式或不等式来表示（不一定是线性的）。null都有一个要求表达的目标，它可用决策变量的函数来表示（称为目标函数，不一定是线性的），按问题的不同，要求目标函数实现最大化或最小化。 null三、非线性规划问题的数学模型 目标函数 等式约束条件不等式约束条件null故非线性规划模型也可表述为如下形式：因等式约束可表示为不等式情况：第二节 非线性规划的图解法第二节 非线性规划的图解法null对于两个变量的非线性规划问题可以用图解法来求解。步骤如下： 在直角坐标系中画出由所有约束条件所组成的公共取值范围。null2. 画出目标函数在直角坐标系中所代表的曲线，并变动，直到要离开图中可行域（公共取值范围）为止，停止变动。 定义：位于同一条目标函数所代表的曲线上的点具有相同的目标函数值，因而称它为“等值线”。null3.求出目标函数曲线同可行域相交的边界点坐标值。 该边界值即为问题的最优解，并代入目标函数，求出问题的最优解。 注意：线性规划问题的最优解一定可以在其可行域的顶点上达到；非线性规划问题的最优解则可能在其可行域中的任意一点达到。null例：null解：（1）绘制公共取值范围： x1 + x2 - 6 = 0：直线 x1+ x2 - 6 = 0x1x26x1 + x2=66null（2）绘制等值线，并变动。Qx1x26x1 + x2=6622(x1-2)2+(x2-2)2 =znull（3）求出交点坐标 Q（3,3）。（4）最优解为：x1=3，x2=3。 最优值为：z = 2null例：null解：（1）绘制公共取值范围： x1 + x2 - 6 = 0：直线 x1+ x2 - 6 = 0的左下方。x1x26x1 + x2=66null（2）绘制等值线，并变动。x1x26x1 + x2=6622(x1-2)2+(x2-2)2 =zQnull（3）求出交点坐标 Q（2,2）。（4）最优解为：x1=2，x2=2。 最优值为：z = 0null例：null解：（1）绘制公共取值范围：x1x2x1 - x2+2≥02-21null（2）绘制等值线，并变动。x1x2x1 - x2+2≥02-212(0.58,1.34)Qnull（3）求出交点坐标 Q（0.58,1.34）。（4）最优解为：x1=0.58，x2=1.34。 最优值为：f(X*) = 3.8第三节 极值问题第三节 极值问题null线性规划的目标函数为线性函数，可行域为凸集，因而求出的最优解就是整个可行域的全局最优解。 非线性规划则不然，当非线性规划的目标函数是非线性函数时，求出的某个解虽然是一部分可行域上的极值点，但却并不一定是整个可行域上的全局最优解。null目标函数为线性函数目标函数为非线性函数局部最优就是全局最优局部最优点不是全局最优点null设 f(X) 为定义在 n 维欧氏空间 En 的某一区域 R 上的 n 元实数，其中 X=(x1 , x2 ,… , xn)T。对于 X*∈R，如果存在某个 ε >0，使所有与 X*的距离小于 ε 的X ∈ R （即X ∈ R且‖X-X*‖< ε ）均满足不等式 f(X) ≥ f(X*)，则称 X* 为 f(X) 在 R 上的局部极小点（或相对极小点），f(X)为局部极小值。一、局部极值nullX*Xn 维实数空间上的区域 R‖X-X*‖< ε如果 f(X) ≥ f(X*)称 X* 为 f(X) 在 R 上的局部极小点（或相对极小点）null设 f(X) 为定义在 n 维欧氏空间 En 的某一区域 R 上的 n 元实数，其中 X=(x1 , x2 ,… , xn)T。对于 X*∈R，如果存在某个 ε >0，使所有与 X*的距离小于 ε 的X ∈ R （即X ∈ R且‖X-X*‖< ε ）均满足不等式 f(X) > f(X*)，则称 X* 为 f(X) 在 R 上的严格局部极小点（或严格相对极小点），f(X)为严格局部极小值。nullX*Xn 维实数空间上的区域 R‖X-X*‖< ε如果 f(X) > f(X*)称 X* 为 f(X) 在 R 上的严格局部极小点（或严格相对极小点）null设 f(X) 为定义在 n 维欧氏空间 En 的某一区域 R 上的 n 元实数，其中 X=(x1 , x2 ,… , xn)T。对于 X*∈R，对于所有 X ∈ R 均满足不等式 f(X) ≥ f(X*)，则称 X* 为 f(X) 在 R 上的全局极小点，f(X)为全局极小值。二、全局极值nullX*Xn 维实数空间上的区域 R如果 f(X) ≥ f(X*)称 X* 为 f(X) 在 R 上的全局极小点null设 f(X) 为定义在 n 维欧氏空间 En 的某一区域 R 上的 n 元实数，其中 X=(x1 , x2 ,… , xn)T。对于 X*∈R，对于所有 X ∈ R 均满足不等式 f(X) > f(X*)，则称 X* 为 f(X) 在 R 上的严格全局极小点，f(X)为严格全局极小值。nullX*Xn 维实数空间上的区域 R如果 f(X) > f(X*)称 X* 为 f(X) 在 R 上的严格全局极小点null三、极值点存在的条件 1. 极值点存在的必要条件 R 是 n 维欧氏空间 En 上的某一开集，f(X) 在 R 上有一阶连续偏导数，且在点 X*∈R 取得局部极值，则必有或nullX*∈R 为极值点▽f(X*)=0必要条件f(X) 在 X* 处的梯度null已知 X*=(X1,X2)=(2,2)为函数的极小值点。null称为 f(X) 在点 X’ 处的梯度。▽f(X’) 的方向为 f(X) 的等值面（等值线）在点 X’ 处的法线方向，沿这个方向函数值增加最快。nullx1x2(2,2)处的法线方向。c梯度计算 f(X)=(x1-2)2+(x2-2)2 在点处的梯度的方向为等值线(x1-2)2+(x2-2)2 =c 在点nullf(X) 在极值点 X* 处的梯度为f(X) 在处梯度f(X) 在处梯度故不是极值点。null2. 极值点存在的充分条件 R 是 n 维欧氏空间 En 上的某一开集，f(X) 在 R 上有二阶连续偏导数，存在点 X*∈R ，若▽f(X*)=0，且对于任何非零向量 Z ∈En 有则 X* 为 f(X) 的严格局部极小点。null此处 H(X*) 为 f(X) 在点 X*处的海赛（Hesse）矩阵：nullX* 为 极小值点▽f(X*)=0且充分条件f(X) 的海赛矩阵 H(X) 在 X* 处正定null证明 X*=(X1,X2)=(2,2)为函数的极小值点。null因为海赛矩阵在 X* 处正定，故根据充分条件可知，X*=(2,2)为极值点。null1. 二次型的二次齐次多项式 称为 n 元二次型，简称二次型。 四、二次型的相关知识 null2. 二次型的矩阵表示二次型可写成 当 i≠j 时，aij=aji=xi xj项系数的一半；aii是xi2 项的系数。null将二次型写成矩阵形式。null3. 正定二次型 设二次型 f(x1,x2,…,xn)=xTAx， 如果对任意的 x=[ x1,x2,…,xn]T≠0，恒有 f = xTAx＞0，则称 f 为正定二次型，称对称矩阵 A是正定的。 f = xTAx≥0，则称 f 为半正定二次型，称对称矩阵 A是半正定的。 f = xTAx＜0，则称 f 为负定二次型，称对称矩阵 A是负定的。 f = xTAx≤0，则称 f 为半负定二次型，称对称矩阵 A是半负定的。null4. 正定二次型的判断对称矩阵 A 为正定的充分必要条件是：A 的各阶主子式都为正。 对称矩阵 A 为半正定的充分必要条件是：A 的各阶主子式都为正和0。 对称阵 A 为负定的充分必要条件是：A 的奇数阶主子式为负 而偶数阶主子式为正。 对称阵 A 为半负定的充分必要条件是：A 的奇数阶主子式为负和0 而偶数阶主子式为正和0。 null判断将二次型的正定性。A 为正定矩阵，对应的二次型 f 为正定二次型。 第四节 凸函数和凹函数第四节 凸函数和凹函数null一、凸集的定义 凸集、凸函数、凸函数极值的性质是研究非线性规划问题所不可缺少的内容。设 K 是 n 维欧氏空间的一个点集，若存在任意两点 X(1)∈K，X(2)∈K 的连线上的一切点：null则称 K 为凸集。注：X(1)X(2)Xα1 -αnull实心圆、实心球体、实心立方体等都是凸集。 凸集没有凹入部分，其内部没有空间。 两个凸集的交集是凸集。null二、凸函数的定义 设 f(X) 为定义在 n 维欧氏空间 En 中某个凸集 R 上的函数，若对于任何实数 α （ 0<α<1 ）以及 R 中的任意两点 X(1) 和 X(2) ，恒有：称 f(X) 为定义在 R 上的凸函数。null设 f(X) 为定义在 n 维欧氏空间 En 中某个凸集 R 上的函数，若对于任何实数 α （ 0<α<1 ）以及 R 中的任意两点 X(1) 和 X(2) ，恒有：称 f(X) 为定义在 R 上的严格凸函数。nullxf(x)x(1)x(2)α x(1) +(1-α )x(2)凸函数null凸函数的定义说明：凸函数上，两点间的线性插值不低于这个函数的值。xf(x)x(1)x(2)凸函数null三、凹函数的定义 设 f(X) 为定义在 n 维欧氏空间 En 中某个凸集 R 上的函数，若对于任何实数 α （ 0<α<1 ）以及 R 中的任意两点 X(1) 和 X(2) ，恒有：称 f(X) 为定义在 R 上的凹函数。null设 f(X) 为定义在 n 维欧氏空间 En 中某个凸集 R 上的函数，若对于任何实数 α （ 0<α<1 ）以及 R 中的任意两点 X(1) 和 X(2) ，恒有：称 f(X) 为定义在 R 上的严格凹函数。nullxf(x)x(1)x(2)α x(1) +(1-α )x(2)凹函数null凹函数的定义说明：凹函数上，两点间的线性插值不高于这个函数的值。xf(x)x(1)x(2)凸函数nullxf(x)x(1)x(2)非凸非凹函数null四、凸函数的性质 性质1 设 f(X) 为定义在凸集 R 上的凸函数，则对任意实数 β ≥0，函数 β f(X) 也是定义在 R 上的凸函数。 性质2 设 f1(X) 和 f2(X) 为定义在凸集 R 上的两个凸函数，则其和 f(X) = f1(X) + f2(X) 仍为定义在 R 上的凸函数。null推论 有限个凸函数的非负线性组合 β1 f1(X)+ β2 f2(X) +…+ βm fm(X)， βi ≥0 仍为凸函数。null五、凹函数的性质 性质1 设 f(X) 为凹函数，则对任意实数 β ≥0，函数 β f(X) 也是凹函数。 性质2 设 f1(X) 和 f2(X) 为两个凹函数，则其和 f(X) = f1(X) + f2(X) 仍为凹函数。 推论 有限个凹函数的非负线性组合 β1 f1(X)+ β2 f2(X) +…+ βm fm(X)， βi ≥0 仍为凹函数。null例：证明 为凹函数。证明：先证明 为凹函数。利用定义，任意指定两点 a1 和 a2，证明下式成立即可。上式显然成立。null同理可证明 也为凹函数。由性质2 可知 f(X) 为凹函数。证毕。null六、函数凸性的判断 1. 判定定理 1 定义。 2. 判定定理 2（一阶条件） 设 R 为 n 维欧氏空间 En 上的凸集，f(X)在 R 上具有一阶连续偏导数，则 f(X) 为 R 上的凸函数的充要条件是：对任意两个不同点 X(1) ∈R 和X(2) ∈R，恒有null证明： ① 必要性f(X) 为凸函数设 f(X) 为 R 上的凸函数，则对任何 α （0< α < 1）有nullnullnull② 充分性f(X) 为凸函数设 X(1) ∈R 和X(2) ∈R因为 X(1) ∈R 和 X ∈R，则有则 X(1) 和 X(2) 连线上的点 X ∈ R ，因为 X(2) ∈R 和 X ∈R，则有null{{}}+nullf(X) 为凸函数null一阶条件：凸函数上，函数的值高于基于某点导数的线性近似。xf(x)X(1)凸函数X基于X(1)null3. 判定定理 2的引申（一阶条件） 设 R 为 n 维欧氏空间 En 上的凸集，f(X)在 R 上具有一阶连续偏导数，则 f(X) 为 R 上的凹函数的充要条件是：对任意两个不同点 X(1) ∈R 和X(2) ∈R，恒有null例：证明 为凹函数。证明：任选取 X(1) = (a1,b1)，X(2)=(a2,b2)即证明null上式显然成立，证毕。null4. 判定定理 3（二阶条件） 设 R 为 n 维欧氏空间 En 上的凸集，f(X)在 R 上具有二阶连续偏导数，则 f(X) 为 R 上的凸函数的充要条件是：f(X) 的海赛矩阵 H(X) 在 R 上处处半正定。null5. 判定定理 3的引申（二阶条件） 设 R 为 n 维欧氏空间 En 上的凸集，f(X)在 R 上具有二阶连续偏导数，则 f(X) 为 R 上的凹函数的充要条件是：f(X) 的海赛矩阵 H(X) 在 R 上处处半负定。null例：证明 为凹函数。证明：写出 f(X)的海赛矩阵如下海赛矩阵处处负定，故 f(X) 为严格凹函数。null凸函数凹函数严格凸函数严格凹函数一阶条件null凸函数凹函数严格凸函数严格凹函数f(X) 的海赛矩阵 H(X) 在 R 上处处半负定f(X) 的海赛矩阵 H(X) 在 R 上处处负定f(X) 的海赛矩阵 H(X) 在 R 上处处半正定f(X) 的海赛矩阵 H(X) 在 R 上处处正定二阶条件null六、凸函数的极值 一般函数：局部极值 ≠ 全局极值。 凸函数：局部极值 = 全局极值 1. 定理 1 设 f(X) 为定义在凸集 R 上的凸函数，则它的任一极小点就是它在 R 上全局极小点，而且它的极小点形成了一个凸集。null证明：X* 是 R 中的局部极小点，Y 是 R 中的任一点。对于充分小的 λ，存在：f((1- λ)X*+ λY)≥f(X*)X*RY因为 f(X) 是凸函数，故 (1- λ)f(X*)+ λf(Y) ≥ f((1- λ)X*+ λY)null(1- λ)f(X*)+ λf(Y)≥f(X*)f(Y)≥f(X*)f((1- λ)X*+ λY)≥f(X*)(1- λ)f(X*)+ λf(Y) ≥ f((1- λ)X*+ λY)即 X* 也是 R 中的全局极小点，证毕。null2. 定理 2 设 f(X) 是定义在凸集 R 上的可微凸函数，若存在点X* ∈R 有 ▽f(X)(X-X*)≥0 则 X* 是 f(X) 在 R 上的全局极小点。null证明：因为 f(X) 是凸函数，由一阶条件可知 f(X) ≥f(X*)+▽f(X*)(X-X*) 又因为 ▽f(X*)(X-X*)≥0 故： f(X)≥f(X*) ，即 X* 为全局极小点。第五节 凸规划第五节 凸规划null满足所有约束约束的解称为可行解。 所有可行解得集合称为可行域。 某个可行解使目标函数最小，称它为最优解。或null称这样的非线性规划为凸规划。凸函数凹函数凸规划是一类比较简单又具有重要意义的非线性规划。null凸规划的特点： 凸规划的可行域为凸集。 凸规划的局部最优解就是全局最优解。 如凸规划的目标函数为严格凸函数，其最优解唯一。 线性函数即可视为凸函数，又可视为凹函数，故线性规划也属于凸规划。null例：试分析下列非线性规划。解：利用二阶条件来判断 f(X) 和 g2(x) 是否为凸函数，g1(x)为线性函数。null海赛矩阵处处正定，故 f(X) 为严格凸函数。f(X) 的海赛矩阵为：g2(X) 的海赛矩阵为：海赛矩阵半负定，故 f(X) 为凹函数（非严格凹函数）。nullx1x2x1 - x2+2≥02-212(0.58,1.34)Q最优值为：f(X*) = 3.8根据凸规划的定义可知该非线性规划为凸规划。 因为该问题只有两个变量，故可用图解法求解。null作业 1 判断下列非线性规划是否为凸规划。null海赛矩阵处处正定，故 f(X) 为严格凸函数。解：f(X) 的海赛矩阵为：g1(X) 的海赛矩阵为：g1(X)的海赛矩阵半正定，故 g1(X) 为凸函数（非严格凸函数），故问题不是一个凸规划。g2(X) 的海赛矩阵为：null作业 2 判断下列非线性规划是否为凸规划。null解：模型变为标准形式。f(X) 的海赛矩阵为：f(X) 为凸函数。nullg1(X) 的海赛矩阵为：g2(X)的海赛矩阵半正定，故 g2(X) 为凸函数（非严格凸函数），故问题不是一个凸规划。g2(X) 的海赛矩阵为：第六节 跌代算法第六节 跌代算法null无约束可微函数 f(X) 的最优解求解方法： 令该函数 f(X)的梯度=0，求出驻点。 利用充分条件（该函数 f(X) 的海赛矩阵在驻点处正定）进行判断。 该方法的问题： 对于 n 元函数 f(X)，▽f(X)=0往往是一个非线性方程组，从而无法求出驻点。 如函数 f(X) 不可微，不能使用上述方法。null给定一个初始估计 X(0)。 按某种算法找到比 X(0) 更好的解 X(1)。 按某种算法找到比 X(1) 更好的解 X(2)。 如此循环…。 若这个问题有最优解，经过多次跌代，X(k)将无限接近该最优解，其接近程度视跌代次数而定，即一、跌代法的思路null设拟建工厂有 n 个配送中心、仓库或原材料供应点。已知： (xi, yi)：各配送中心、仓库或原材料供应点的坐标，其中 i =1,2,…,n。 hi：工厂到 i 处（配送中心、仓库或原材料供应点）的每单位货物单位距离所需的运输费用，又称运输费率。 wi：工厂与 i 处间的物流量。 现在欲求此工厂的位置(x, y)，使从工厂到各处的总运输费用为最小。 null设 di 为工厂到 i 处的直线运输距离，ci 为工厂到 i处的运输费用，H 为工厂到各处的总运输费用。 null但从目标函数形式可以看出，目标函数为关于 x 和y 的连续函数，又无任何约束，其极值点必然位于驻点，可考虑求该函数的驻点的方法，求出问题的最优解。该问题的目标函数为关于 x 和 y 的二元非线性函数，无约束条件，属于无约束非线性规划问题。问题：null根据函数求极值的原理，对 H 分别关于 x 和 y 求偏导，令偏导数为 0，可得： null因为 hi、wi 和 xi 均为已知数，只须用它们将 x 表示出来即可。 因为 hi、wi 和 xi 均为已知数，只须用它们将 y 表示出来即可。 null造成无法直接写出 x 和 y 表达式的根本原因在于di 为未知变量，其中含有 x 和 y。如果 di 为已知数的话，则 x 和 y 的表达式很容易写出。nullnull令 为已知数，则利用上述公式可求得：又因为将 x1 和 y1 代入可得出新的 di ：null 为已知数，利用公式可求得：又因为将 x2 和 y2 代入可得出新的 di ：null（1）（2）（3）null算法步骤 （1）给出厂址的初始位置(xk, yk)； （2）利用式（3）计算出总运输费用Hk； （3）将(xk, yk)代入式（2），计算dik； （4）将 dik 代入式（1），计算出改进位置(xk+1, yk+1)； （5）将(xk+1, yk+1)代入式（3）计算出Hk+1； （6）将Hk+1和Hk进行比较： 如果Hk+1