第十一章：非劣解的解法.pptVIP

主要内容 K-T条件 加权法 约束法 K-T条件 纯量优化问题的K-T条件 非线性规划 纯量优化问题的K-T条件 假设条件 （1）设x*满足约束条件，如果梯度向量对于x*在下标集上（起作用约束）是线性独立的，则称x*是正则点（对x*起作用的约束条件的梯度是线性独立的） 纯量优化问题的K-T条件 K-T条件 纯量优化问题的K-T条件 它是最优解x*的一个必要条件，但不一定充分。 如果f(x)是凹函数，可行空间X是凸域，则K-T条件也是充分条件 向量优化问题的K-T条件 向量优化问题存在非劣解的必要条件 向量优化问题的K-T条件 加权法 加权法 加权法：通过对目标函数的加权，直接利用K-T条件推出非劣解 加权法 K-T条件 加权法 可知 加权的纯量优化问题的最优解和原来的向量优化问题的非劣解有相同的K-T必要条件 可以证明：只有当权wk都严格为正时，才能保证加权的纯量问题的最优解是原来的向量优化问题的非劣解 加权法 如果有一个或多个wk=0，则纯量优化问题找到的最优解有可能不是唯一的，在这些最优解中，有的解可能是原来的向量优化问题的劣解（见后面例题） 加权法 加权法的解释 例：一所高校（见陈廷《决策分析》P158） y1是招生人数，y2是研究生和本科生的比 例，两个目标在学校的人力、物力受限制 的条件下，相互矛盾。学校的意图是选择 一方案是两个目标同时达到极大。 加权法 期中Y是由约束条件所规定的目标空间的 可行域。 如果认为研究生和本科生的比例每增加1%，等价于招生人数增加w个，则原问题可化为 加权法 可用非线性规划和线性规划的一般方法求解上面的纯量优化问题，这个解将是宣布w的人的最佳调和解 加权法 把轨线作为无差异曲线，在可行域内移动 上图中C点即为决策人的最佳调和解 W称为置换率 两个属性之间标定一个符合决策人愿望的置换w，等价于决策人的偏好用一个斜率为-1/w的无差异曲线去表示 加权法 一般情况下，置换率将随属性的值而变，无差异曲线不是一根直线 看一下w变化时的一些情况 加权法 所有目标加权 上式可化为 加权法 一般情况下的加权问题 加权法 权为负值情况的解释（陈廷，P161） （1）两个负权：变成极小化问题 （2）一个为负：无差异直线的斜率为正 约束为线性的情况 可能产生许多最优解 加权法 一般步骤 加权法常用于逼近非劣解，但不是一种准 确找出所有非劣解的有效方法 （1）令w1=(1,0,…,0),…wn=(0,0,…,1)找出非劣集的端点 （2）设定权重的步长，从0到上限 加权法 加权法 几个权为0的解释 约束法 约束法 可以由非劣解的K-T条件直接导出 在前面的加权法的例子中，假设研究生和本科生的比例不得小于某个百分比e，问题是，当这个比例不小于某一个百分比时，学校能招生多少学生？ 约束法 约束法 改变e的值，再找到y1的一个新的极大点，它对应一个新的非劣解，由此可找到一集非劣解 约束法 一般情况 约束法 K-T条件 大家证明（5分钟） 第十一章 产生非劣解的方法 C y2 y1 C y2 y1 D E B y2 y1 A y2 y1 y2 y1 A