第二讲 非线性规划基本概念.ppt

1 第二讲非线性规划模型 一 非线性规划引例 例1路灯照度问题 在一条20m宽的道路两侧 分别安装了一只2kw和一只3kw的路灯 它们离地面的高度分别为5m和6m 在漆黑的夜晚 当两只路灯开启时 两只路灯连线路面上最暗的点和最亮的点在哪里 如果3kw路灯的高度可以在3m到9m之间变化 如何使得路面上最暗和最亮的点的位置 如果两只路灯的高度均可以在3m到9m之间变化 结果将如何 只是涉及非线性规划的案例以及其解的相关概念 不涉及具体算法 2 图2 1 o s x p1 p2 h1 h2 r1 r2 分析 如图2 1 p1 p2 表示两只灯的功率 离地面的高度为h1 h2 两只灯的距离为s 假设两只灯发出的光都可以看成点光源 预备知识 光源点p1在点x处的照度i1 i1与功率p1成正例 与距离r1的平方成反比 与照射角度 1的正弦成正比 即 其中 k为比例系数 同时也是平衡量纲 单位 的量 3 解 所有的变量设置如图2 1所示 两只灯在点x处的照度为 其中 变量之间的关系 这个公式只是适合点光源 如果不是点光源 比如竖着的日光灯 该怎么办 4 问题一 灯高度不变 求路面照度最弱最强的位置x 数学模型1 s t 也可以化简为 5 代入已知参数 模型简化为 即求一元函数i x 在 0 20 上的最大值与最小值 6 问题2 当3kw的灯的高度在3m到9m之间变化时 路面的最暗和最亮点 数学模型2 即求二元函数i x h2 在所给条件下的上的最大值与最小值 7 问题3 两只灯的高度都在3m到9m之间变化时 求路面的最暗和最亮点 数学模型3 即求三元函数i x h1 h2 在所给条件下的上的最大值与最小值 像这种目标函数或者约束条件是决策变量的非一次 非线性 的规划问题 称为非线性规划模型 8 二 非线性规划模型 在建立规划模型时 若目标函数中决策变量或者约束方程 不等式 中某些变量为非一次 不是线性 则称建立的数学模型为非线性规划模型 其数学模型一般为 若 1 非线性规划模型 1 9 2 非线性规划问题的解的相关概念 一般来说 非线性规划的求解 比线性规划的求解困难得多 线性规划有统一的单纯形求解方法 而非线性规划目前还没有统一的一般算法 1 1可行集 可行域 给定非线性规划问题 1 1 如果 1 中m 0 表示没有约束 称为无约束优化问题 否则就是一般意义上的非线性规划模型 10 若x满足 1 的约束条件 则称x为 1 的一个可行解 所有可行解的集合称为可行域 或可行集 记 1 2局部极小点 局部最优解 对于非线性规划 1 若存在 且对一切 满足 即x为x 附近的点 都有 则称x 为f x 在d上的局部极小点 局部最优解 11 当 时 若 则称x 为f x 在 d上的严格局部最优解 1 3全局最优解 全局极小值点 对于非线性规划 1 若存在 且对一切 都有 则称x 为f x 在d上的全局极小点 全局局最优解 注意 局部最优和全局最优实际就是高数中的极值与最值问题 12 x y f x 0 a b x1 x2 x3 x4 x5 x6 x1 x3 x5为f x 的局部极小值点 x2 x4 x6为f x 的局部极大值点 x4为全局最大值点 x3是全局最小值点 13 3 非线性规划的图解法 例2利用图解法 求解如下非线性规划问题 分析 决策变量为x x1 x2 t 目标函数表示决策变 x1 x2 t到点 2 1 t的距离的平方 体现为圆周半径变化 第一个约束是一条抛物线 开口朝左 x1为横轴 第二个约束为直线 同时决策变量非负 14 解以x1和x2分别为横轴和纵轴 建立直角坐标系 如图2 2 1 绘制约束曲线 2 标出可行域 图2 2 15 x1 x2 0 右上 2 5 在抛物线上 1 2 a b c d 16 3 绘制目标函数曲线 该问题的目标曲线是圆 以 2 1 t为圆心 半径 随着 x1 x2 t变化而变化 当半径达到最小 则目标函数也达到最小 让目标曲线随着目标意愿变化 本题的全局最优点是d 4 1 如图所示 另外 b 2 9104 4 3275 t是局部最小点 严格局部最优解 目标函数的最大点是a 0 5 c 2 5 2 5 点是局部最大点 17 4 1线性规划问题的最优解一定在可行域的边界的顶点处达到 任何一个最优解 就是全局最优解 4 2非线性规划的最优解可以在可行域内任何一点处达到 非线性规划求解出来的只是局部最优解 所以在针对非线性规划求解时 具体问题 有具体的搜索最优解的方法 一般注意 4 建立规划模型的注意点 1 尽可能给出靠近全局最优解附近的初始可行解 2 尽可能给出每个决策分量的比较准确的上下界 3 能够线性化的表达式 尽量线性化 4 尽量每个表达式连续可导 起码二阶 5 非线性规划每次求解结果不一定相同 18 4 3在建立规划模型时 尽量做到 1 尽量用线性代替非线性 2 尽量用连续函数 若遇到分段函数 尽可能连续化或者用特殊手段处理 3 尽量写成乘积而不是除法 4 尽量用实数变量 少用整数变量 5 尽量给出变量的准确上下界 有利于更快搜索到最优解 6 复杂的式子 尽量化简表达式 19 例3组合投资问题 假设某公司在下一个计划期内可用于投资的总资本为b万元 可供选择的投资项目为n个 分别记为1 2 n 已知对