运筹学-练习题.doc

《运筹学-练习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、案例1，原始问题：某公司现有三条生产线，由于原有产品出现销售量下降的情况，管理部门决定调整公司的产品线，停产不赢利的产品以释放产能来生产两种新产品。其中，生产甲产品要占用生产线1和生产线3的部分产能，产品乙需要占用生产线2和3的部分产能。管理部门需要考虑下列问题：1、公司是否应该生产这两种产品？2、若生产，则两种产品的数量如何确定？数据：运筹小组与管理部门研究后去顶，两种产品的数量如何确定以使产品的总利润最大？因此，需要如下的信息：1、每条生产线的可得生产能力是多少？2、生产每一单位产品需要每条生产线多少生产能力？3、每种产品的单位利润是多少？生产部门和财务部门经过分析，提出如下数据：生

2、产线产品甲产品乙生产线每周可用时间一104二0212三3218单位产品利润35模型：1、要做出什么决策？（决策变量）2、做出的决策会有哪些条件限制？（约束条件）3、这些决策的全部评价标准是什么？（目标函数）maxz=3x1+5x2st.x1<=42x2<=123x1+2x2<=18x1,x2>=0决策：x1=2,x2=6,z=3600生产时间信息：按模型所确定的生产方案需要生产线2和3的所有时间，只有生产线1有2小时的剩余。1、用单纯形表求解以下线性规划问题（1）maxz=x1-2x2+x3s.t.x1+x2+x3≤1282x1+x2-x3≤6-x1+3x2≤9x1,x2,x3≥0解：标

3、准化，将目标函数转变成极小化，引进松弛变量x4,x5,x6³0,得到：minz’=-x1+2x2-x3s.t.x1+x2+x3+x4=122x1+x2-x3+x5=6-x1+3x2+x6=9x1,x2,x3,x4,x5,x6≥0列出初始单纯形表z’x1x2x3x4x5x6RHSz’11-210000x4011[1]1001212/1x5021-10106--x60-1300019--选取x3为进基变量，确定x4为离基变量z’x1x2x3x4x5x6RHSz’10-30-100-12x301111001212/1x50[3]201101818/3x60-1300019--得到最优解（x1,

4、x2,x3,x4,x5,x6）=（0,0,12,0,18,9），minz’=-12，maxz=12由于其中非基变量x1在目标函数中的系数为0，x1进基，x5离基，可以得到另一最优解：z’x1x2x3x4x5x6RHSz’10-30-100-12x3001/312/3-1/306x1012/301/31/306x60011/301/31/3115新的最优解为（x1,x2,x3,x4,x5,x6）=（6,0,6,0,0,15），minz’=-12，maxz=12原问题最优解的全体为：，（0≤l≤1），都有maxz=128（2）maxz=x1+3x2+4x3s.t.3x1+2x2≤13x2+3

5、x3≤172x1+x2+x3=13x1,x2,x3≥0解：将目标函数转化成极小化，引进松弛变量x4，x5，x6≥0，得到minz’=-x1-3x2-4x3s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3=13x1,x2,x3,x4,x5,≥0引进人工变量x6³0，构造辅助问题：minz’’=x6s.t.3x1+2x2+x4=13x2+3x3+x5=172x1+x2+x3+x6=13x1,x2,x3,x4,x5,x6≥0列出辅助问题的系数矩阵表：z’’x1x2x3x4x5x6RHSz’’100000-10x4032010013x5001301017x602110

6、0113消去基变量x6在目标函数中的系数，并开始单纯形叠代：z’’x1x2x3x4x5x6RHSz’’121100013x40[3]201001313/3x5001301017--x602110011313/28x1进基，x4离基，z’’x1x2x3x4x5x6RHSz’’10-1/31-2/30013/3x1012/301/30013/3--x500130101717/3x600-1/3[1]-2/30113/313/3x3进基，x6离基，z’’x1x2x3x4x5x6RHSz’’100000-10x1012/301/30013/3x500202104x300-1/3[1]-2/301

7、13/3辅助问题已经获得最优解，且minz’’=0，因而可以转入第二阶段，其系数矩阵表为：z’x1x2x3x4x5RHSz’1134000x1012/301/3013/3x50020214x300-1/31-2/3013/3消去基变量x1，x3在目标函数中的系数：z’x1x2x3x4x5RHSz’1011/307/30-65/3x1012/301/3013/313/2x500[2]02144/2x300-1/31-2/3013/3-