凌晨: 第五章L.P.单纯形法 L.P.问题中变量个数多于2时,图解法失效 即使是计算机求解,首先也要有有效算法,然 后才可能利用程序去实现它 单形法,是LP.问题算法之基础。本质上,它 是代数方法,可以用线性代数的理论证明方法 的合法性,清楚地说明算法背后的“为什么” 。由于课时限制我们不准备这么做,将把有限 的精力和时间浅尝辄止:了解算法本身的使用 ,并不证明“为什么
Ling Xueling L.P. 问题中变量个数多于 2 时，图解法失效 即使是计算机求解，首先也要有有效算法，然 后才可能利用程序去实现它 单形法，是 L.P. 问题算法之基础。本质上，它 是代数方法，可以用线性代数的理论证明方法 的合法性，清楚地说明算法背后的“为什么” 。由于课时限制我们不准备这么做，将把有限 的精力和时间浅尝辄止：了解算法本身的使用 ，并不证明“为什么” 。 第五章 L.P. 单纯形法 凌晨: 凌晨:
凌晨: 节单形法的代数说明 例子 假设HT公司正在计划下周两种计算机产品的生产 台式机/台:利润:50装配工时:3占地:8 便携机台/:利润:40装配工时:5占地:5 资源限制: 下周最大可用工时:150 便携式显示器目前只有:20pcs 仓储可用面积:300平方英尺 若以最大化利润为目标,如何安排生产?
Ling Xueling 一、例子 假设 HT 公司正在计划下周两种计算机产品的生产 台式机/台：利润：50 装配工时：3 占地：8 便携机台/：利润：40 装配工时：5 占地：5 资源限制： 下周最大可用工时：150 便携式显示器目前只有：20 pcs 仓储可用面积：300 平方英尺 若以最大化利润为目标，如何安排生产？ 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法的代数说明 二、模型及其标准形 设:x1一计划的台式机数量x2一计划的便携机数量 max 50x, +40x 3x1+5x2≤150时约束 2≤20 便携机显示器约束 8x1+5x2≤300仓储面积约束 1,X2≥0 非负约束 为了获得标准形,分别为约束式引入松弛变量:s
Ling Xueling 二、模型及其标准形 设：x1 －计划的台式机数量 x2 － 计划的便携机数量 max 50x1 + 40x2 s.t. 3x1 + 5x2 150 工时约束 x2 20 便携机显示器约束 8x1 + 5x2 300 仓储面积约束 x1，x2 0 非负约束 为了获得标准形，分别为约束式引入松弛变量：s i。 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法的代数说明 二、模型及其标准形 max50x1+40x2+0s1+0s2+0s3(5.1) 3x1+5x,+s =150 52) 20 8x1+5X2 300 即为模型之标准形。除非负约束之外,(5,2)-(54)刚好构 成一个5个变量、3个方程的线性方程组
Ling Xueling 二、模型及其标准形 max 50x1 + 40x2 + 0s1 + 0s2 + 0s3 (5.1) s.t. 3x1 + 5x2 + s1 = 150 (5.2) x2 + s2 = 20 (5.3) 8x1 + 5x2 + s3 = 300 (5.4) x1，x2，s1，s2，s3 0 即为模型之标准形。除非负约束之外，(5.2) －(5.4) 刚好构 成一个 5个变量、3 个方程的线性方程组。 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法的代数说明 从代数观点思考标准形一一解题思路 1、将(52)-(54)线性方程组表示为增广阵:(AB),则 其一般解法是通过初等变换(保证既化简又同解) (AB)→ B其中B含自由变量 可能有无穷多个解 2、因为不满足非负要求的线性方程组的解是非可行解,即 使得到也要去除并重新求解(换基) 3、从满足非负约束的线性方程组的解中找出(迭代方法) 使得目标函数取值最好的解,即为最优解
Ling Xueling 三、从代数观点思考标准形－－解题思路 1、将 (5.2) －(5.4) 线性方程组表示为增广阵：( A B )，则 其一般解法是通过初等变换（保证既化简又同解）: 其中 B’ 含自由变量 可能有无穷多个解 2、因为不满足非负要求的线性方程组的解是非可行解，即 使得到也要去除并重新求解（换基） 3、从满足非负约束的线性方程组的解中找出（迭代方法） 使得目标函数取值最好的解，即为最优解。 第一节 单形法的代数说明 凌晨: 凌晨: → ' 1 .... 1 1 (AB) B