运筹学复习：

《运筹学复习：》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、运筹学复习：有四项工作要甲、乙、丙、丁四个人去完成，每项工作只允许一个人去完成，每个人只完成其中一项工作。已知每个人完成各项工作的时间如下表所示，问应指派哪个人去完成哪项工作才能使总的消耗时间为最少？ 工作1工作2工作3工作4甲10131619乙14181713丙21121114丁14161812最优方案为：甲-工作1，乙-工作4，丙-工作3，丁-工作2例试将下面线性规划问题minz=-x1+2x2-3x3s.t.x1+x2+x3≤7x1-x2+x3≥2-3x1+x2+2x3=-5x1,x2≥0maxz’=x1-2x2+3x4-3x5s.t.x1+x2+x4-x5+x6

2、=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,

3、x2,x’3,x’’3,x4,x5,x6≥01.2线性规划的图解maxz=x1+3x2s.t.x1+x2≤6-x1+2x2≤8x1≥0,x2≥0可行域目标函数等值线最优解Z（4/3,14/3）=46/364-860x1x2最优解X=(15,10)最优值Z=85x1x2O1020304010203040(3,4)(15,10)原问题与对偶问题的对应关系对偶问题为求下述线性规划问题的对偶问题•minz=2x1+3x2-5x3+x4•x1+x2-3x3+x4≥5•2x1+2x3-x4≤4•x2+x3+x4=6•x1≤0,x2,x3≥0;x4无约束•设对应于三个约束条件的对偶变

4、量分别为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无约束