单纯形法图解法及原理.ppt

1,例：公交线路人员优化问题 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下： 班 次 时 间 所需人数 1 6:00 -10:00 60 2 10:00-14:00 70 3 14:00-18:00 60 4 18:00-22:00 50 5 22:00- 2:00 20 6 2:00 - 6:00 30 设司机和乘务人员分别在各时间区段一开始时上班，并连续工作八小时，问该公交线路至少配备多少名司机和乘务人员。 列出此问题的线性规划模型。,P46:Ex9,2,决策变量：Xi为第i班开始上班的人数 i=1,6 目标函数：Min Z= X1+X2+X3+X4+X5+X6 约束条件： X6 + X1 = 60 X1 + X2 = 70 X2 + X3 = 60 X3 + X4 = 50 X4 + X5 = 20 X5 + X6 = 30 Xi=0,1=1,6,3,线性规划模型隐含的假设： 比例性： 决策变量变化引起目标的改变量与决策变量改变量成正比。 可加性： 每个决策变量对目标和约束的影响独立于其它变量。 连续性： 每个决策变量取连续值。 确定性： 线性规划中的参数aij , bi , ci为确定值。,4,第二节 单纯形法原理,-图解法,图解法：是用画图的方式求解线性规划的一种方法。 只能用于求解两个变量的LP问题,5,1）作出可行域 2）作出一条目标函数的等值线 3）平行移动目标函数的等值线，求出最优解,图解法基本步骤：,6,例1.数学模型 max Z=50x1+30x2 s.t. 4x1+3x2 120 2x1+x2 50 x1,x2 0,7,x2,50,40,30,20,10,10,20,30,40,x1,4x1+3x2 120,由 4x1+3x2 120 x1 0 x2 0 围成的区域,8,x2,50,40,30,20,10,10,20,30,40,x1,2x1+x2 50,4x1+3x2 120,可行域,同时满足： 4x1+3x2 120 2x1+x2 50 x1 0 x2 0 的区域可行域,9,x2,50,40,30,20,10,10,20,30,40,x1,可行域,O（0，0）,Q1（25，0）,Q2（15，20）,Q3（0，40）,可行域是由约束条件围成的区域，该区域内的每一点都是可行解，它的全体组成问题的解集合。 该问题的可行域是由O，Q1，Q2，Q3作为顶点的凸多边形,10,x2,50,40,30,20,10,10,20,30,40,x1,可行域,目标函数是以Z作为参数的一组平行线 x2 = Z/30-（5/3）x1,11,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当Z值不断增加时，该直线 x2 = Z/30-（5/3）x1 沿着其法线方向向右上方移动。,12,x2,50,40,30,20,10,10,20,30,40,x1,可行域,当该直线移到Q2点时，Z（目标函数）值达到最大： Max Z=50*15+30*20=1350 此时最优解=（15，20）,Q2（15，20）,有唯一最优解,13,例2 解线性规划,有唯一最优解,14,对于线性规划问题，我们定义： 可行解：满足全部约束条件的决策向量 XRn。 可行域：全部可行解构成的集合。（它是 n 维欧 氏空间Rn 中的点集，而且是一个“凸 多面体”) 最优解：使目标函数达到最优值（最大值或最小 值，并且有界）的可行解。 无界解：若求极大化则目标函数在可行域中无上 界；若求极小化则目标函数在可行域中 无下界。,15,有无穷多最优解,例3 解线性规划,Z=0,Z=-2,16,例4 解线性规划,有无界解,17,例5： MaxZ=3X1-2X2 X1 + X2 =8 X1,X2 =0,无可行解,18,结论： 1、线性规划问题的可行域为凸集 2、若有最优解一定可以在其可行域的顶点上得到,线性规划问题解的几种情况： 1、有唯一最优解 2、有无穷多最优解 3、无可行解 4、无最优解,19,第三节 单纯形法 -原理,单纯形法：单纯形法是求解线性规划的主要算法，1947年由美国斯坦福大学教授丹捷格（G.B.Danzig）提出。尽管在其后的几十年中，又有一些算法问世，但单纯形法以其简单实用的特色始终保持着绝对 的“市场”占有率。,20,定义1：基(基阵) 由A中一个子矩阵B是可逆矩阵，则方阵B称为LP问题的一个基。,线性规划问题解的概念,21,22,AX=b的求解,A=(BN) X=(XB XN )T XB XN,(BN) = b,BXB +NXN=b BXB =b-NXN XB = B-1 b - B-1N XN,23,24,B=(P3 P4 P5)=I 可逆 基 N=(P1 P2),例1：,25,令X1 = X2 =0, X3=30, X4=60, X5=24,26,令X4=X5=0 X=(12, 12, -6, 0, 0)T,Z=40X1 +50X2 =4012-(1/3 X4 -1/3 X5) +5012- 1/2 X5 = 1080+(- 40/3 X4 -35/3 X5 ),基本解，但不可行,27,求出基变量是X1 , X3 , X4的基本解，是不是可行解？,28,29,X=(1, 0, 3/2, 3/2)T 是,30,定义1：凸集D是n维欧氏空间的一个集合 X(1), X(2)D,若任一个满足 X= X(1)+(1-) X(2) (0 1) 有XD,线性规划问题的几何意义(例2),31,X(1) , X(2) , ,X(k) 是n维欧氏空间中的k个点，若有一组数 1 , 2 , , k 满足 0 i 1 (i=1, ,k),定义2,有点 x= 1 X(1) + + k X(k) 则称点X为 X(1) , X(2) , ,X(k) 的凸组合。,凸组合,32,凸集D, 点 XD，若找不到两个不同的点X(1) , X(2) D 使得 X= X(1) +(1- ) X(2) (0 1) 则称X为 D的顶点。,定义3,顶点,33,定理1：LP问题的可行解域一定是凸集。,引理1：线性规划问题的可行解X为基可 行解的充分必要条件是：X的非 零分量(=0)所对应的系数矩阵 A的列向量是线性无关。,？,34,定理2：线性规划问题的基可