山东大学软件学院 2018-2019 学年度第二学期 最优化方法 试题 回忆版 一、简答题（30 分） 1. 线性规划问题中，什么是基本可行解 2. 什么是凸规划 3. 单纯形算法中，如果判定已经得到了最优解？如何判定问题无界？两阶段算法中， 如何判定问题无解？ 4. 分支定界法解整数规划最小化问题中，分枝的含义是什么？定界的含义是什么？剪 枝的含义是什么？ 5. 描述 0.618 法的基本流程 二、证明题（30 分） 1. f(x) 是凸函数 当且仅当fy ≥fx +f(x)(−) 2. 线性规划中，原始规划为最小化问题，证明≥ 3. ∇f(x)<0 ⟹ + <() 4. 最速下降法中的d+1=0 5. 共轭向量线性无关 三、计算题（40 分） 1. 用单纯形法解线性规划 （具体数值忘记了） 2. 用对偶单纯形法解线性规划 （具体数值忘记了） 3. 使用 K-T 条件解下列优化问题 min s.t. max s.t. 4. 写出罚函数 12+22 1≥0 1+2=1 −1+2 21−2=2 12+22<5