凌晨: 第五章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
凌晨: 节单形法的代数说明 四、基解( basic solution) 1、定义:在m个方程、n个变量之线性方程组中 若令n-m个变量为0,然后求出的线性方程 组解称为基解,其中被令成0的变量称为非基 变量,没有被令成0的变量称为基变量 2、上例中,m=3,n=5,令(实际上可以任选2 个):X2 0,s1=0,代入方程组易得 X1=50,x2=0,S1=0,S2=20, 100 即为LP问题一个基解,不过,非可行解
Ling Xueling 四、基解（basic solution） 1、定义：在 m 个方程、n 个变量之线性方程组中 若令 n－m 个变量为 0，然后求出的线性方程 组解称为基解，其中被令成 0 的变量称为非基 变量，没有被令成 0 的变量称为基变量 2、上例中，m = 3，n = 5，令（实际上可以任选 2 个）：x2 = 0，s1 = 0，代入方程组易得： x1 = 50，x2 = 0，s1 = 0，s2 = 20，s3 = －100 即为 L.P. 问题一个基解，不过，非可行解！ 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法的代数说明 五、基可行解 1、定义:满足非负要求的基解称为基可行解 很明显,我们要的是基可行解,是最优的基可行解 2、上例中,若令x1=0,x2=0,则可得基解: X1=0,X2=0,s1=150,S2=20,S3=300 正是一个基可行解!称之为初始基可行解 3、基可行解的几何解释 作出本LP问题的可行区域,可见: 0 0正是可 行域的端点(1)!这不是偶然的,我们有一般的结论
Ling Xueling 五、基可行解 1、定义：满足非负要求的基解称为基可行解 很明显，我们要的是基可行解，是最优的基可行解 2、上例中，若令 x1 = 0，x2 = 0，则可得基解： x1 = 0，x2 = 0，s1 = 150，s2 = 20，s3 = 300 正是一个基可行解！称之为初始基可行解 3、基可行解的几何解释 作出本 L.P. 问题的可行区域，可见： x1 = 0，x2 = 0 正是可 行域的端点（1）！这不是偶然的，我们有一般的结论。 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 五、基可行解 4、可行域及其初始基可行解的图形表示 (3) 端点(1)即为初始基可行解
Ling Xueling 五、基可行解 4、可行域及其初始基可行解的图形表示： 端点（1）即为初始基可行解。 第二节 单形法用于最简单例子 凌晨: 凌晨: (1) (2) (3) (4) (5)
凌晨: 节单形法的代数说明 五、基可行解 5、定理 LP.问题中,约束线性方程组的基可行解就是其可行域的 端点,反之亦然 6、定理 P问题最优解必是基可行解中的一个 7、单形法的迭代 从任意一个初始基可行解出发(只要令n-m个变量为零即 可),在不断改善目标函数前提下,设法将其变化(迭代 )成另一个基可行解,直至求出最优的
Ling Xueling 五、基可行解 5、定理一 L.P. 问题中，约束线性方程组的基可行解就是其可行域的 端点，反之亦然 6、定理二 L.P. 问题最优解必是基可行解中的一个 7、单形法的迭代 从任意一个初始基可行解出发（只要令 n-m 个变量为零即 可），在不断改善目标函数前提下，设法将其变化（迭代 ）成另一个基可行解，直至求出最优的。 第一节 单形法的代数说明 凌晨: 凌晨:
凌晨: 节单形法用于最简单例子 LP.的表格形式 表格形式的意义 将LP.模型化成表格形式,可为单形法迅速提供一个初始基 可行解!然后才开始迭代过程 2、例子 max50x1+40x2+0s1+0s2+0s3(5.1) 3x1+5X2+s 150 (5.2) 20 8x 300 (5.4) ≥0 注意上例中,基变量s的系数阵是一个单位阵
Ling Xueling 一、L.P. 的表格形式 1、表格形式的意义 将 L.P. 模型化成表格形式，可为单形法迅速提供一个初始基 可行解！然后才开始迭代过程 2、例子 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 注意上例中，基变量 si 的系数阵是一个单位阵。 第二节 单形法用于最简单例子 凌晨: 凌晨: