§10.2.1图解法 计算方法 博孝明 第十华量优化 方注 的L城性套代 地位装性城划问整的 几有型义 地生排性这 地里耳性比业则 一性字生 山无表业班到 Figure:图解法 口母t42型专月QC 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.1 图解法 P1 P2 P3 P4 v 0 1 2 3 4 5 x 1 2 3 4 5 y Figure: 图解法 傅孝明 计算方法
§10.2.1图解法 计算方法 不难看出，此问题的最优解是唯一.但是，对于一般的线性规划问题 博孝明 来说，还可能出现下列的情况： 第十华量优化 (1)无穷多最优解.若将目标函数换成z=x1+3x2,则目标函数 方选 的直线族与约束条件(1c)平行，此时线段P3P4上所有的点都 运1址性到的问面 1地之线性规划同整的 是最优解，即有无穷多最优解。 几月丝义 (2)无界解.若将约束条件(1a)-(1c)换成4x1≤18，则可行域是无 的进甲件 地丰性丝代此到面 穷区域，即变量x2的取值可无限增大，此时目标函数值也可无 地一城堂 地上无有非址性秋 限增大，即最优解无界 (3)无解，或无可行解.若将约束条件(1a)换成4x1+2x2≥24，则 不存在满足所有约束条件的公共区域，可行域是空集，即无解。 当求解结果出现无界解或无解情况时，一般来说是线性规划问题的 数学模型有错误，前者缺乏必要的约束条件，后者存在矛盾的约束 条件，需重新建模， 000 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.1 图解法 不难看出, 此问题的最优解是唯一. 但是, 对于一般的线性规划问题 来说, 还可能出现下列的情况: (1) 无穷多最优解. 若将目标函数换成 z = x1 + 3x2, 则目标函数 的直线族与约束条件(1c)平行, 此时线段 P3P4 上所有的点都 是最优解, 即有无穷多最优解. (2) 无界解. 若将约束条件(1a)-(1c)换成 4x1 6 18, 则可行域是无 穷区域, 即变量 x2 的取值可无限增大, 此时目标函数值也可无 限增大, 即最优解无界. (3) 无解, 或无可行解. 若将约束条件(1a)换成 4x1 + 2x2 > 24, 则 不存在满足所有约束条件的公共区域, 可行域是空集, 即无解. 当求解结果出现无界解或无解情况时, 一般来说是线性规划问题的 数学模型有错误, 前者缺乏必要的约束条件, 后者存在矛盾的约束 条件, 需重新建模. 傅孝明 计算方法
§10.2.1图解法 计算方法 博孝明 图解法仅能用于求解具有两个变量的线性规划问题，但是它 第十华量优化 为求解一般线性规划问题提供了一些启示： 方注 的L城生套面 (1)若线性规划问题的可行域存在，则可行域是凸集 地位装性城划问整的 (2)若线性规划问题的最优解存在，则最优解或最优解之一 几有型义 地生排性这 (有无穷多解时)是可行域的某个顶点 地里耳性比业则 一线字类 单纯形法的基本思路：先找出可行域的任一顶点，计算在该顶 点处的目标函数值，检查周围相邻顶点的目标函数值是否比 这个值大，如果是否，则它就是最优解的点或最优解的点之 一：否则，转到比这个点的目标函数值更大的另一顶点.重复 上述过程，直至找到使目标函数值达到最大的顶点为止 00 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.1 图解法 图解法仅能用于求解具有两个变量的线性规划问题, 但是它 为求解一般线性规划问题提供了一些启示: (1) 若线性规划问题的可行域存在, 则可行域是凸集. (2) 若线性规划问题的最优解存在, 则最优解或最优解之一 (有无穷多解时) 是可行域的某个顶点. 单纯形法的基本思路: 先找出可行域的任一顶点, 计算在该顶 点处的目标函数值, 检查周围相邻顶点的目标函数值是否比 这个值大, 如果是否, 则它就是最优解的点或最优解的点之 一; 否则, 转到比这个点的目标函数值更大的另一顶点. 重复 上述过程, 直至找到使目标函数值达到最大的顶点为止. 傅孝明 计算方法
§10.2.2标准形式 计算方法 因目标函数和约束条件内容和形式上的差别，线性规划问题 博孝明 的表示形式是多种多样的.因此，为便于后续方法的描述，有 第十华量优化 方法 必要规定线性规划问题的标准形式： 的1址姓到问面 1地之线性规划同整的 几风盘义 max (2) 地丰性丝代此到面 拉一地建 地士无有表非过性我 ary=b,i=1,2,…m, (3a) ,j=1,2,…n (3b) 在标准形式中，目标函数为求极大值，约束条件全为等式，约 束条件右端常数项b全为非负值，变量x均取非负值， 000 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.2 标准形式 因目标函数和约束条件内容和形式上的差别, 线性规划问题 的表示形式是多种多样的. 因此, 为便于后续方法的描述, 有 必要规定线性规划问题的标准形式: max z = ∑n i=1 cixi , (2) s. t. ∑n j=1 aijxj = bi , i = 1, 2, · · · m, (3a) xj > 0, j = 1, 2, · · · n. (3b) 在标准形式中, 目标函数为求极大值, 约束条件全为等式, 约 束条件右端常数项 bi 全为非负值, 变量 xj 均取非负值. 傅孝明 计算方法
§10.2.2标准形式 计算方法 对于不符合标准形式的线性规划问题，可通过下列变换进行转化 博孝明 (1)若目标函数为求极小值，即min:= 》c,可令=-，则原问题可化为 第十华量优化 方注 max:=(一∑）这就与标准形式中的目标函数一致了： 的L城生套面 地位装性城划问整的 (2) 若约束条件是不等式，有两种情况：一种是约束方程为“≤”不等式，可在不等 几有型义 式的左端加入一个非负变量：另一种是约束方程为“≥”不等式，可在不等式的 地生排性法 地里耳性比业想 左端减去一个非负变量，新加入的变量称为松她变量，则可将不等式约束化为 山-紫 等式约束 (3)若约束条件的右端项b<0,可将等式两端乘以”一1”，则等式右端项必大于 零： (4)若约束条件≤0，可令+1=一k,则化为约束条件x+1≥0： (5)若存在取值无约束的变量x,可令x=从+1一+2，则化为约束条件 +1:xk+2≥0 不难证明，任何形式的线性规划问题都可以化为标准形式 口母t12型 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.2 标准形式 对于不符合标准形式的线性规划问题, 可通过下列变换进行转化: (1) 若目标函数为求极小值, 即 min z = ∑n i=1 cixi, 可令 ˜z = −z, 则原问题可化为 max˜z = ( − ∑n i=1 cixi ) , 这就与标准形式中的目标函数一致了; (2) 若约束条件是不等式, 有两种情况: 一种是约束方程为 “6” 不等式, 可在不等 式的左端加入一个非负变量; 另一种是约束方程为 “>” 不等式, 可在不等式的 左端减去一个非负变量, 新加入的变量称为松弛变量, 则可将不等式约束化为 等式约束. (3) 若约束条件的右端项 bi < 0, 可将等式两端乘以”−1”, 则等式右端项必大于 零; (4) 若约束条件 xk 6 0, 可令 xk+1 = −xk , 则化为约束条件 xk+1 > 0; (5) 若存在取值无约束的变量 xk , 可令 xk = xk+1 − xk+2, 则化为约束条件 xk+1, xk+2 > 0. 不难证明, 任何形式的线性规划问题都可以化为标准形式. 傅孝明 计算方法