八线性规划八线性规划LinearProgramming.PDF

八八. 线性规划线性规划 (Linear(Linear Programming)Programming) 引引 言言 • 线性规划讨论的是最优化问题。 • 最优化理论所研究的对象是静态系统，即与时间无关 的系统，与前面各章所讨论的最优控制问题不同。 • 最优化理论和算法要解决的问题是最优化理论和算法要解决的问题是： 在可选的方案中哪个方案最优( 目标函数极值)；  怎样找出最优方案。怎样找出最优方案。 • 与最优控制理论相同，最优化理论也是泛函极值理论 发展的一个重要分支，20世纪40年代起逐渐形成单独 的学科。 • 最优化理论和算法内容非常丰富，主要包括：线性规 划划、整数规划整数规划、非线性规划非线性规划、几何规划几何规划、动态规划动态规划、 随机规划、网络决策等，而最基本的内容是线性规划 和非线性规划和非线性规划。。 8.1 凸集和凸函数 • 凸集和凸函数是线性规划和非线性规划( 以及整个最优化 问题中) 的非常重要的概念。 • 一般的最优化理论都建立在凸集和凸函数基础之上般的最优化理论都建立在凸集和凸函数基础之上。 • 本节内容作为基础知识不作深入介绍，供需要时参考。 88.22 线性规划线性规划的定义和标准形式的定义和标准形式 ((1)) 线性规划的定义 考虑最优化问题的数学模型一般表示为 min (or max) f (x) s.t. g (x) = B 其中，f (x)为目标函数，g (x)为约束函数；x ∈Rn, B为m维列向量， gg ((xx))为为mm维向量函数维向量函数，， 线性规划定义线性规划定义：：最优化问题数学模型中目标函数和约束函数都是最优化问题数学模型中目标函数和约束函数都是 变量x 的线性函数的，称之为线性规划问题。 线性规划是非线性规划的一种特殊形式，但在最优化理论与算法中 已成为非常重要的一个分支，在理论和算法上都很成熟，应用非常 广泛。广泛。 (2)(2) 线性规划线性规划标准形式标准形式 一般线性规划问题总可以表示为： n min c x ((8-2-1)) ii ii (or max) i 1 n s.t . a x b , j 1,2,3, , m (8-2-2) ji i j i 1 x ii 0, i 1,2,3, , n; bjj 0, jj 1,2,3, , m (8-2-3) 或用矩阵形式表示为： min Cx (8-2-1’) (or max) ss.tt . AAxx BB (8(8-22-22’)) x 0; B 0 (8-2-3’) 其中A 为m ╳n 维矩阵，C为n维行向量，B为m维列向量。 任何其他任何其他形式的线性规划问式的线性规划问题均均可转换成转换成以上标准上标准形式式。 例如，若有bj 0 可在相应等式两边乘（-1 ）（非负化）； x  0