12单纯形法图解法及原理.pptVIP

X(1) , X(2) , … ,X(k) 是n维欧氏空间中的k个点，若有一组数 μ1 , μ2 , … , μk 满足 0 ? μi ?1 (i=1,… ,k) 凸集D, 点 X?D，若找不到两个不同的点X(1) , X(2) ?D 使得 X=? X(1) +(1- ? ) X(2) (0? 1) 则称X为 D的顶点。 定义2 ? μ i =1 k i=1 有点 x= μ1 X(1) + … + μk X(k) 则称点X为 X(1) , X(2) , … ,X(k) 的凸组合。 凸组合 定义3 顶点 * * 例：公交线路人员优化问题 某昼夜服务的公交线路每天各时间区段内所需司机和乘务人员数如下： 班 次 时 间 所需人数 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 决策变量：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 线性规划模型隐含的假设： 比例性： 决策变量变化引起目标的改变量与决策变量改变量成正比。 可加性： 每个决策变量对目标和约束的影响独立于其它变量。 连续性： 每个决策变量取连续值。 确定性： 线性规划中的参数aij , bi , ci为确定值。 第二节 单纯形法原理 ----图解法 图解法：是用画图的方式求解线性规划的一种方法。 只能用于求解两个变量的LP问题 1）作出可行域 2）作出一条目标函数的等值线 3）平行移动目标函数的等值线，求出最优解 图解法基本步骤： 例1.数学模型 max Z=50x1+30x2 s.t. 4x1+3x2 ? 120 2x1+x2 ? 50 x1,x2 ? 0 x2 50 40 30 20 10 10 20 30 40 x1 4x1+3x2 ? 120 由 4x1+3x2 ? 120 x1 ? 0 x2 ? 0 围成的区域 x2 50 40 30 20 10 10 20 30 40 x1 2x1+x2 ? 50 4x1+3x2 ? 120 可行域 同时满足： 2x1+x2 ? 50 4x1+3x2 ? 120 x1 ? 0 x2 ? 0 的区域——可行域 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作为顶点的凸多边形 x2 50 40 30 20 10 10 20 30 40 x1 可行域 目标函数是以Z作为参数的一组平行线 x2 = Z/30-（5/3）x1 x2 50 40 30 20 10 10 20 30 40 x1 可行域 当Z值不断增加时，该直线 x2 = Z/30-（5/3）x1 沿着其法线方向向右上方移动。 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） 有唯一最优解 例2 解线性规划 有唯一最优解 对于线性规划问题，我们定义： 可行解：满足全部约束条件的决策向量 X?Rn。 可行域：全部可行解构成的集合。（它是 n 维欧 氏空间Rn 中的点集，而且是一个“凸