运筹学-线性规划-PPT课件.ppt

1、 线性规划n3.1 LP的基本概念n3.2线性规划问题的图解法n3.3 单纯形表上作业法n3.4 大M法和两阶段法n3.5单纯形法的进一步探讨n3.6 计算机求解n3.7 习题课第3章 线性规划n线性规划的发展线性规划的发展n1939年，前苏联数学家康托洛维奇用线性模型研究提高组织和生产效率问题 1947年，Dantzig提出求解线性规划的单纯形法 1950-1956年，主要研究线性规划的对偶理论 1958年，发表整数规划的割平面法n1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。n1979年，Khachiyan，1984年，Karmarkaa

2、研究成功线性规划的多项式算法。3.1 LP(linear programming)的基本概念LP是在有限资源的条件下，合理分配和利用资源，以期取得最佳的经济效益的优化方法。LP有一组有待决策的变量，一个线性的目标函数，一组线性的约束条件。线性规划研究的主要问题线性规划研究的主要问题n一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。n另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。n 实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max 或 min）。例1.1 某厂生产两种产品，下表给出

3、了单位产品所需资源及单位产品利润 问：应如何安排生产计划，才能使 总利润最大？例题1生产计划问题解：解：1.决策变量：设产品I、II的产量分 别为 x1、x22.目标函数：设总运费为z，则有：max z=2 x1+3 x23.约束条件：x1+2x2 8 4x1 16 4x2 12 x1，x203.1.1 LP的数学模型例题2 某厂生产三种药物，这些药物可以从四种不同的原料中提取。下表给出了单位原料可提取的药物量（配方问题）要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。解：解：1.决策变量：设四种原料的使用 量分别为：x1、x2、x3、x

4、42.目标函数：设总成本为z，则有：min z=5 x1+6 x2+7 x3+8 x43.约束条件：x1+2x2+x3+x4 160 2x1 +4 x3+2 x4 200 3x1 x2+x3+2 x4 180 x1、x2、x3、x40 药物原料ABC单位成本（元吨）甲1235乙2016丙1417丁1228例题3：人员安排问题n医院护士24小时值班，每次值班8小时。不同时段需要的护士人数不等。据统计：序号时段最少人数安排人数1061060X12101470X23141860X34182250X45220220X56020630 x6例题3建模n目标函数：min Z=x1+x2+x3+x4+x5+

5、x6n约束条件：x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x6+x1 60非负性约束：xj 0,j=1,2,6例题4合理下料问题n料长7.4米，截成2.9、2.1、1.5米各200根。如何截取余料最少？关键：设变量。方案料型 1 2 3 4 5 6 7 8 2.9米 2.1米 1.5米 1 2 0 1 0 1 0 0 0 0 2 2 1 1 3 0 3 1 2 0 3 1 0 4 合计 残料 7.4 7.3 7.2 7.1 6.6 6.5 6.3 6.0 0 0.1 0.2 0.3 0.8 0.9 1.1 1.4例题4建模设：xj为采用第 j种方

6、案的根数（j=1，2，8），z 为总残料量则：min z=0.1x2+0.2x3+0.3x4+0.8x5+0.9x6+1.1x7+1.4x8 x1+2 x2+x4+x6 2002x3+2 x4+x5+x6+3x7 2003x1+x2+2x3+3 x5+x6+4 x8 200 xj 0 j=1,2,8船只种类船只数拖 轮30A型驳船34B型驳船52航线号合同货运量12002400航线号船队类型编队形式货运成本（千元队）货运量（千吨）拖轮A型驳船B型驳船1112362521436202322472404142720问：应如何编队，才能既完成合同任务，又使总货运成本为最小？例题5 某航运局现有船只种

7、类、数量以及计划期内各条航线的货运量、货运成本如下表所示：例题5建模设：xj为第 j 号类型船队的队数（j=1，2，3，4），z 为总货运成本则：min z=36x1+36x2+72x3+27x4 x1+x2+2x3+x4 302x1 +2x3 34 4x2+4x3+4x4 5225x1+20 x2 200 40 x3+20 x4 400 xj 0 j=1,2,3,4用单纯形法可求得：x1=8，x2=0，x3=7，x4=6 最优值：z=954即：四种船队类型的队数分别是 8、0、7、6，此时可使总货运成本为最小，为954千元。线性规划模型特点线性规划模型特点1 都用一组决策变量X=(x1,x2

8、,xn)T表示某一方案；满足以上三个条件的数学模型称为线性规划满足以上三个条件的数学模型称为线性规划2 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等 式来表示。3.23.2线性规划问题的名词和图解法线性规划问题的名词和图解法max z=x1+3x2 s.t.x1+x26 -x1+2x28 x1,x20123456xz=0z=3z=6z=9z=12z=15.3013456约束条件（1）约束条件（2）C-1-8-2-3-4-5-6-7x214 将最优解代入目标函数，求出最优值。1 在直角平面坐标系中画出所有的约

9、束等式，并找出所有约束条件的公共部 分，称为可行域，可行域中的点称为可行解。2 标出目标函数值增加的方向。3 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向 平行移动，找与可行域最后相交的点，该点就是最优解。图解法解题步骤图解法解题步骤O123123xx21ABCDx3=0 x4=0 x2=0 x1=0可行域可行域(可行解全体可行解全体)基本可行解基本可行解(可行域顶点、极点可行域顶点、极点)基本解基本解令非基变量 x10，x2 0则得：X (0,0,3,1)T基本解则：基变量为x2、x3，非基变量为x1、x4令非基变量 x10，x4 0则得：X (0,1,5,0)T基本解

10、不是基本可行解基本可行解例例 讨论下述约束方程的解 x1 2x2 x3 3 2x1 x2 x4 1解解系数矩阵为：10120121A则：基变量为x3、x4，非基变量为x1、x23）X (1/2,1/2,3/2,1/2)T不是基本解可行解不是基本可行解3.2.2 3.2.2 线性规划的基本名词线性规划的基本名词1 可行解（feasible solution）：满足线性规划约束条件的解称为可行解。2可行域：可行解的集合3 最优解（optimal solution）：使线性规划目标函数达到最优的可行解。4 基本解（basic solution）：以线性规划约束等式的系数矩阵A中任意m行m 列组成的m

11、m满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（basic variable），其余变量称为非基变量，令非基变量为零，可求得基变 量的值，这样求出的解称为基本解。5基本可行解（basic feasible solution）：满足非负约束的基本解称为基本可行解。若约束等式中有n个变量，m个约束，则基本解的个数mnC基础解、基础可行解max z=x1+3x2Ds.t.x1+x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1,x2,x3,x40 x1=0 E O x2=0 AOABCDE基变量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基变量x1 x

12、2x2 x3x3 x4x1 x4x1 x3x2 x4xj0-x4x1基础可行解是是是是否否1 可行解与最优解：最优解一定是可行解，但可行解不一定是最优解。线性规划解之间的关系线性规划解之间的关系基本解不一定是可行解，可行解也不一定是基本解。2 可行解与基本解：3 可行解与基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4 基本解与基本可行解：5 最优解与基本解：最优解不一定是基本解，基本解也不一定是最优解。问题：最优解与基本可行解？非可行解可行解基本可行解基本解几何概念代数概念约束直线满足一个等式约束的解约束半平面满足一个不等式约

13、束的解约束半平面的交集：凸多边形满足一组不等式约束的解约束直线的交点基础解可行域的极点基础可行解目标函数等值线：一组平行线 目标函数值等于一个常数的解线性规划解的性质线性规划解的性质定理定理1 线性规划的可行域 R 是一个凸集，且有有限个顶点。定理定理2 X是线性规划可行域 R 顶点的充要条件是 X 线性规划的基本可行解。定理定理3 若线性规划有最优解，则必有基本最优解。定理定理4 若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线 上也达到最优。线性规划问题的可行域是一个凸集。线性规划的每一个基本可行解对应凸集的每一个顶点。若线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优。

14、若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。最优解一定是基本可行解，但基本可行解不一定是最优解。解的形态 (d)可行域无界可行域无界 (e)可行域无界可行域无界 (f)可行域为空集可行域为空集 多个最优解多个最优解 目标函数无界目标函数无界 无可行解无可行解 (a)可行域有界可行域有界 (b)可行域有界可行域有界 (c)可行域无界可行域无界 唯一最优解唯一最优解 多个最优解多个最优解 唯一最优解唯一最优解结论n可行域是个凸集n可行域有有限个顶点n最优值在可行域的顶点上达到n唯一最优解的情形n无穷多解的情形n无界解情形n无解情形线性规划的一般模式1.决策变量：X=(x1,x2,.,

15、xn)T2.目标函数：max(min)z=c1 x1+c2 x2+.+cnxn3.约束条件：a11x1+a12 x2+.+a1n xn(=)b1 a21x1+a22 x2+.+a2n xn(=)b2 am1x1+am2 x2+.+amn xn(=)bm x1,x2,xn0线性规划的标准形式1.决策变量：X=(x1,x2,.,xn)T2.目标函数：max z=c1 x1+c2 x2+.+cnxn3.约束条件：a11x1+a12 x2+.+a1n xn=b1 a21x1+a22 x2+.+a2n xn=b2 am1x1+am2 x2+.+amn xn=bm x1,x2,xn0线性规划的标准形式线性

16、规划的标准形式其中：),2,1(0),2,1(max(min)11njxmibxaxczjnjijijnjjj求和形式求和形式矩阵形式矩阵形式0 max(min)XbAXCXznxxxX21决策变量决策变量常数项常数项nbbbb21系数矩阵系数矩阵nmijmnmmnnaaaaaaaaaaA212222111211价值系数价值系数ncccC21其中：标准型的特征n目标函数极大化n约束条件为等式n决策变量非负n约束方程右侧常数全部非负正规型的特征n标准型n每一个约束方程均有基变量非标准型转化为正规型n目标函数极小化转为极大化：minZ=max(Z)，一个数的极小化等价于其相反数的极大化。n不等式约

17、束的转化：aijxjbi 加入松弛变量 aijxjbi 减去剩余变量n非正变量：即xk 0 则令xk=xk 自由变量：即xk无约束，令xk=xkx”k非标准型转化举例之一之一maxZ=70X1+120X2 maxZ=70X1+120X2 9X1+4X2360 9X1+4X2+X3=360 4X1+5X2 200 4X1+5X2+x4=200 3X1+10X2 300 3X1+10X2+x5=300 X10 X20 Xj0 j=1,2,5非标准型转化举例之二之二minZ=x1+2x2-3x3 maxZ=x12x2+3(x3x”3)x1+x2+x3 9 x1+x2+x3 x”3+x4=9-x1-2

18、x2+x3 2 x12x2+x3 x”3-x5=2 3x1+x2-3x3=5 3x1+x23(x3 x”3)=5 x1 0 x2 0 x3无约束 x1 0 x2 0 x3 0 x”3 0 x40 x50 正规化1.目测：松驰变量2.构造：人工变量（举例）大M法例解Min Z=-3X1+X2+X3 Max Z=3X1-X2-X3 MX6-MX7 s.t.X1-2X2+X3 11 s.t.X1-2X2+X3 +X4 =11 -4X1+X2+2X3 3 -4X1+X2+2X3 -X5+X6 =3 2X1-X3=-1 -2X1+X3 +X7=1 X10,X20,X30 Xj 0 j=1,2,7求解一般

19、线性规划问题策略求解一般线性规划问题策略寻找初始基本可行解寻找初始基本可行解给出基本可行解为最优解的判别准则给出基本可行解为最优解的判别准则给出从目前基本可行解转移到新基本给出从目前基本可行解转移到新基本 可行解的方法可行解的方法求解流程求解流程 确定初始确定初始基本可行解基本可行解最优解？最优解？否否转移到新转移到新的基本可行解的基本可行解给出最优解给出最优解是是 3.3 单纯形表上作业法单纯形表的格式：CjC1 C2 Cn i CBXBbx1 x2 .xn C1 C2 Cmx1x2xmb1b2bma11 a12 a1na21 a22 a2n am1 am2 amn 1 2 m -z *1

20、2 n 例解：（表图）max z=x1+3x2Ds.t.x1+x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1,x2,x3,x40 x1=0 E O x2=0 AOABCDE基变量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基变量x1 x2x2 x3x3 x4x1 x4x1 x3x2 x4xj0-x4x1基础可行解是是是是否否 Cj1 3 0 0CBXBbX1 X2 X3 X4j 0 0 X3X468 1 1 1 0 -1 2 0 1 6/18/2-z0 1 3 0 0 0 3X3X224 3/2 0 1 -1/2 -1/2 1 0 1/24/3-z

21、-12 5/2 0 0 -3/213X1X24/314/3 1 0 2/3 -1/3 0 1 1/3 1/3-z-46/3 0 0 -5/3 -2/3O点C点B点基础解、基础可行解max z=x1+3x2Ds.t.x1+x2+x3=6 B-x1+2x2 +x4=8 x4=0 C x3=0 x1,x2,x3,x40 x1=0 E O x2=0 AOABCDE基变量x3 x4x1 x4x1 x2x2 x3x2 x4x1 x3非基变量x1 x2x2 x3x3 x4x1 x4x1 x3x2 x4xj0-x4x1基础可行解是是是是否否步骤n用正规型表示问题，确定初始基可行解n填入初始单纯形表n求相对利润

22、系数。如果全部非正，则停止n选择旋入变量n用最小比值法确定旋出变量n旋转运算计算表格数据和相对利润系数。返回第三步3.4 大M法和两阶段法n例解Min Z=-3X1+X2+X3 Max Z=3X1-X2-X3 MX6-MX7 s.t.X1-2X2+X3 11 s.t.X1-2X2+X3 +X4 =11 -4X1+X2+2X3 3 -4X1+X2+2X3 -X5+X6 =3 2X1-X3=-1 -2X1+X3 +X7=1 X10,X20,X30 Xj 0 j=1,2,7 Cj3 -1 -1 0 0 -M -MCBXBbX1 X2 X3 X4 X5 X6 X7j 0 -M -MX4X6X71131

23、 1 -2 1 1 0 0 0-4 1 2 0 -1 1 0 -2 0 1 0 0 0 1-z0 3 -1 -1 0 0 -M -M 0 -M -MX4X6X7113 1 1 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 1113/21-z4M3-6M M-1 3M-1 0 -M 0 00-M-1X4X6X31011 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2-2 0 1 0 0 0 1-1-zM+1 1 M-1 0 0 -M 0 3M初始单纯形表大M法miijijjacc1B Cj3 -1 -1 0 0 -M -MCBXBbX1 X2 X

24、3 X4 X5 X6 X7j 0 0 0X4X2X312113 0 0 1 -2 2 -50 1 0 0 -1 1 -2-2 0 1 0 0 0 14-z2 1 0 0 0 -1 1-M -1-M -3 1 1X1X2X341 91 0 0 1/3 -2/3 2/3 -5/30 1 0 0 -1 1 -2 0 0 1 2/3 -4/3 4/3 -7/3-z-20 0 0 -1/3 -1/3 1/3-M 2/3-M 大M法 Cj0 0 0 0 0 -1 -1CBXBbX1 X2 X3 X4 X5 X6 X7j 0 -1 -1X4X6X71131 1 -2 1 1 0 0 0-4 1 2 0 -1

25、 1 0 -2 0 1 0 0 0 1-W0 0 0 0 0 0 -1 -1 0 -1 -1X4X6X7113 1 1 -2 1 1 0 0 0-4 1 2 0 -1 1 0-2 0 1 0 0 0 1113/21-W4-6 1 3 0 -1 0 00-10X4X6X31011 3 -2 0 1 0 0 -1 0 1 0 0 -1 1 -2-2 0 1 0 0 0 0-1-W1 0 1 0 0 -1 0 3初始单纯形表两阶段法第一阶段 Cj0 0 0 0 0 -M -MCBXBbX1 X2 X3 X4 X5 X6 X7j 0 0 0X4X2X312113 0 0 1 -2 2 -50 1 0

26、0 -1 1 -2-2 0 1 0 0 0 1-W0 0 0 0 0 0 -1 -1两阶段法第一阶段 Cj3 -1 -1 0 0CBXBbX1 X2 X3 X4 X5j 0 -1 -1X4X2X312113 0 0 1 -20 1 0 0 -1-2 0 1 0 04-z21 0 0 0 -1 3 -1 -1X1X2X341 91 0 0 1/3 -2/30 1 0 0 -10 0 1 2/3 -4/3-z-20 0 0 -1/3 -1/3两阶段法第二阶段miijijjacc1B3.5单纯形法的进一步探讨n极小化问题直接求解：检验数的判别由所有j 0 即为最优，变为所有j 0则为最优。n无穷多最

27、优解情形：非基变量检验数 j=0 (在最终单纯形表中)n退化解的情形：有两个以上 值相等n无界解n无解 Cj3 2 0 0 0CBXBbX1 X2 X3 X4 X5j 0 0 3X3X4X1753 0 1 1 0 1 0 5 0 1 3 1 1 0 0 171-z-9 0 5 0 0 3 0 2 3X3X2X161 4 0 0 1 1/5 8/5 0 1 0 1/5 -3/5 1 0 0 1/5 2/515/4-10-z-14 0 0 0 -1 0023X5X2X115/413/45/2 0 0 5/8 -1/8 1 0 1 3/8 1/8 0 1 0 -1/4 1/4 0 626/3-z-1

28、4 0 0 0 -1 0无穷多个最优解 Cj0 0 0 2 0 1.5CBXBbX1 X2 X3 X4 X5 X6j 0 0 0X1X2X3243 1 0 0 1 -1 0 0 1 0 2 0 1 0 0 1 1 1 1 223-z0 0 0 0 2 0 1.5 2 0 0X4X2X320 1 1 0 0 1 -1 0 -2 1 0 0 2 1-1 0 1 0 2 1-01.5-z-4-2 0 0 0 2 1.5200X4X5X2201 0 0.5 0 1 0 0.5-1 0.5 0 0 1 0.5 0 -1 1 0 0 040-z-4 0 -1 0 0 0 0.5退化解 Cj2 3 0 0C

29、BXBbX1 X2 X3 X4j 0 0 X3X424 1 1 1 0 -3 1 0 1-4-z0 2 3 0 0 0 3X3X264-2 0 1 1-3 1 0 1-z-12 11 0 0 -3无界解 Cj2 1 0 0 -MCBXBbX1 X2 X3 X4 X5j 0 -M X3X526 1 1 1 0 0 2 2 0 -1 1 23-z6M 2+2M 1+2M 0 -M 0 2 -MX1X522 1 1 1 0 0 0 0 -2 -1 1-z2M-4 0 -1 -2-2M -M 0无解3.6 计算机求解n数据准备填入计算结果分析n基变量选择n旋入变量选择n相对利润系数或者比值相同的处理

30、Cj无人工变量CBXBbX1 X2 X3 X4 X5 X6j X3X4X623 4 1 0 0 1 5 0 1 1 0 3 0 0 4 1-z 0 0 3 03.7 习题课例题112312应如何限制6个未知常量，才能使下列的命题之一成立？n当前解是最优的，但存在多个最优解。n当前解不可行（指出哪个变量）。n约束条件之一不成立。n当前解是退化的基本可行解（哪个变量引起退化？）n当前解是唯一最优解。n当前解可行，但可用X1换出X6改进目标函数，在旋转运算后，目标函数的总变化是多少？12312习题课例题2n下面每一张表都对应一个最大值问题的迭代结果。从下面诸条中选出一条或几条，它们可以简要说明每张表

31、的结果，然后回答括号中的问题。nA.可能继续改进目标函数值（哪个变量进基？哪个变量出基？目标函数的增量是多少？）nB.原问题不可行。（为什么？）nC.解是退化的。（哪个变量退化？）nD.表中表示的解不是基本可行解。nE.已获得唯一最优解。nF.存在多个最优解，只求其中一个最优解。（求多个最优解。）nG.原问题的最优解无界（哪个变量引起这种情况？）（注：M是很大的正数）应用举例之一 n例7混合配方问题A、B、C、D四种原料配制三种产品，三类约束：技术要求、原料限量、市场容量。已知产品价格和原料价格，求利润最大的配方。关键：设变量应用举例之二n例8滚动投资问题有100万元资金，投资方向有四：第四年第一年第二年第三年A项目110%B项目135%C项目125%D项目104%第五年各年投资什么项目，使第五年末资本总额为最大？应用举例之三n例9动态生产计划问题 工厂做n个月的生产计划，第j月需求量dj、正常生产能力aj、加班生产能力bj、正常生产成本cj、加班生产成本ej、库存能力为I、库存费用hj，设期初、期末库存为零。求费用最小的生产计划。设第月正常生产xj件，加班生产件yj，存储zj件。则：本期生产+上期库存-本期库存=本期需求