运筹学复习：.doc

有四项工作要甲、乙、丙、丁四个人去完成,每项工作只允许一个人去完成,每个人只完成其中一项工作。已知每个人完成各项工作的时间如下表所示,问应指派哪个人去完成哪项工作才能使总的消耗时间为最少? 工作1工作2工作3工作4甲10131619乙14181713丙21121114丁14161812最优方案为:甲-工作1,乙-工作4,丙-工作3,丁-工作2例试将下面线性规划问题minz=-x1+2x2-+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0maxz’=x1-2x2+3x4-+x2+x4-x5+x6=7x1-x2+x4-x5-x7=23x1-x2-2x4+2x5=5x1,x2,x4,x5,x6,x7≥0解令x3=x4-x5其中x4、x5≥0;对第一个约束条件加上松弛变量x6;对第二个约束条件减去松弛变量x7;对第三个约束条件两边乘以“-1”;令z’=-z把求minz改为求maxz’例将下列数学模型转化为标准型maxz=4x1+5x2+2x3x1+x2≤45x1+x2+2x3≤80x1+x2-4x3≥-40x1,x2≥0,x3无约束maxz=4x1+5x2+2x’3+2x’’3x1+x2+x4=45x1+x2+2x3+x5=80-x1-x2+4x3+x6=40x1,x2,x’3,x’’3,x4,x5,x6≥=x1+3x2 +x2≤6-x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解Z(4/3,14/3)=46/364-860x1x2最优解X=(15,10)最优值Z=85x1x2O1020304010203040(3,4)(15,10)原问题与对偶问题的对应关系对偶问题为求下述线性规划问题的对偶问题minz=2x1+3x2-5x3+x4x1+x2-3x3+x4≥52x1 +2x3-x4≤4 x2+x3+x4=6x1≤0,x2,x3≥0;x4无约束设对应于三个约束条件的对偶变量分别为y1,y2,y3;由于目标函数是求极小值,由上表知其对偶问题为 maxz’=5y1+4y2+6y3 y1+2y2≥2 y1+y3≤3 -3y1+2y2+y3≤-5 y1-y2+y3=1 y1≥0,y2≤0,y3无约束