§10.2.2标准形式 计算方法 傅孝胡 例10.3 第十华量优化 方滋 将下列线性规划问题化为标准形式 地1址姓到的问面 1地之线性规划同整的 几同盘义 min z=x1-4x2+x3, 的进甲件 地丰性丝代此到面 -2x1-x2+2x3≥7， 的一城业装 地士无有表非过性我 3x1+2x2-x3≤2， s.t. x1+2x2-3=-1, x1≤0，x2≥0，x3无约束. 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.2 标准形式 . 例 10.3 . . 将下列线性规划问题化为标准形式 min z = x1 − 4x2 + x3, s. t. −2x1 − x2 + 2x3 > 7, 3x1 + 2x2 − x3 6 2, x1 + 2x2 − x3 = −1, x1 6 0, x2 > 0, x3无约束. 傅孝明 计算方法
§10.2.3基本定理 计算方法 对于标准形式的线性规划问题，引入有关基的几个概念。 博孝明 定义10.2 第十华是优化 方注 设A=(a)mxm为等式约束条件(3a)的系数矩阵，其中m<n, 的L城生套面 rank(4)=m.若B是A的一个m×m满秩子矩阵，则称B是线性 地位装性城划问整的 几有型义 规划问题的一组基.不失一般性，可设 地上非性这 地主县鞋此业 a11 Q12 1m 一线孝生 山无表业班到 B= : (P1,P2,·,Pnm)为 其中B中的每一个列向量P称为基向量，与基向量P对于的变量 ,称为基变量，线性规划问题中除基变量以外的变量称为非基变 量 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.3 基本定理 对于标准形式的线性规划问题, 引入有关基的几个概念. . 定义 10.2 . . 设 A = (aij)m×n 为等式约束条件(3a)的系数矩阵, 其中 m < n, rank(A) = m. 若 B 是 A 的一个 m × m 满秩子矩阵, 则称 B 是线性 规划问题的一组基. 不失一般性, 可设 B = a11 a12 · · · a1m . . . . . . · · · . . . am1 am2 · · · amm = ( p1 , p2 , · · · , pm ) , 其中 B 中的每一个列向量 pj 称为基向量, 与基向量 pj 对于的变量 xj 称为基变量. 线性规划问题中除基变量以外的变量称为非基变 量. 傅孝明 计算方法
§10.2.3基本定理 计算方法 傅孝胡 定义10.3 第十华量优化 在等式约束条件(3a)中，若令所有非基变量 方法 xm+1=xm+2=…=xn=0,又因det(B)卡0，知由m个约束 的1址姓到问面 1的之线性规则同整图 方程可解出m个基变量的唯一解xB=(1,2,,xm)T.将 几风盘义 进单件法 这个解加上非基变量取0的值，有 地丰性丝代此到面 地一地堂 x=(1,2,…,xm,0,…,0)T,称x为线性规划问题的基解 地上无有非址性我 注意，在线性规划问题求解过程中，基是可以变化的，此时基 向量，基变量，基解等也随之变化 容易看出，在基解中变量取非零值的个数不大于方程个数m, 故基解的总数不超过() 000 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.3 基本定理 . 定义 10.3 . . 在等式约束条件(3a)中, 若令所有非基变量 xm+1 = xm+2 = · · · = xn = 0, 又因 det(B) ̸= 0, 知由 m 个约束 方程可解出 m 个基变量的唯一解 xB = (x1, x2, · · · , xm) T . 将 这个解加上非基变量取 0 的值, 有 x = (x1, x2, · · · , xm, 0, · · · , 0)T , 称 x 为线性规划问题的基解. 注意, 在线性规划问题求解过程中, 基是可以变化的, 此时基 向量, 基变量, 基解等也随之变化. 容易看出, 在基解中变量取非零值的个数不大于方程个数 m, 故基解的总数不超过 ( n m ) . 傅孝明 计算方法
§10.2.3基本定理 计算方法 博季雨 第十华量优化 方注 定义10.4 的L城生套面 地位装性城划问整的 满足非负约束条件(3b)的基解称为基可行解。 几有型义 地上排性多 地里耳性比业 定义10.5 与基可行解对应的基称为可行基： 4口，，1三，升200 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.3 基本定理 . 定义 10.4 . .满足非负约束条件(3b)的基解称为基可行解. . 定义 10.5 . .与基可行解对应的基称为可行基. 傅孝明 计算方法
§10.2.3基本定理 计算方法 傅孝胡 定义10.6 第十华量优化 方法 设C是n维欧式空间的一个点集，若对任意的x1,x2∈C,均 的1址姓到问面 有 1的之线性规则同整图 几风盘义 Xx1+(1-入)x2∈C,入∈[0,1， 的进甲件 地丰性丝代此到面 即x1与x2连线上的所有点也都在C中，则称C是凸集. 的一城业装 地上无有非址性我 从直观上看，凸集没有凹入部分，其内部没有空洞.实心圆， 实心球体，实心立方体等都是凸集，而圆环就不是凸集 任何两个凸集的交集是凸集， 傅孝明 计算方法
计算方法 傅孝明 第十章最优化 方法 §10.1 线性规划问题 §10.2 线性规划问题的 几何意义 §10.3 单纯形法 §10.4 非线性优化问题 §10.5 一维搜索 §10.6 无约束非线性优 化 . . . . . . §10.2.3 基本定理 . 定义 10.6 . . 设 C 是 n 维欧式空间的一个点集, 若对任意的 x1, x2 ∈ C, 均 有 λx1 + (1 − λ)x2 ∈ C, ∀λ ∈ [0, 1], 即 x1 与 x2 连线上的所有点也都在 C 中, 则称 C 是凸集. 从直观上看, 凸集没有凹入部分, 其内部没有空洞. 实心圆, 实心球体, 实心立方体等都是凸集, 而圆环就不是凸集. 任何两个凸集的交集是凸集. 傅孝明 计算方法