运筹学复习资料.doc

1、分别用图解法和单纯形法求解下面的线性规划问题Max z=2x1+x2s.t 3x1+5x215 6x1+2x224 X1,x20解：1）图解法：由上图可知，B点为最优点，最优解为（15/4,3/4），最优值为z=33/42）单纯形法： 将上述线性规划问题化为标准形：Max z=2x1+x2s.t 3x1+5x2+x3=5 6x1+2x2+x4=24 X1,x2,x3,x40 利用单纯形法运算得到表一至表三： 由表三可知，线性规划问题的最优解为X*=(15/4,3/4,0,0)T目标函数的最优值为max z=33/42已知线性规划问题Max z=x1+2x2+3x3+4x4s.T x1+2x2+2x3+3x4 20 2x1+x2+3x3+2x420 x1 ,x2 ,x3 , x4 , 0其对偶问题的最优解为W=(1.2,0.2)T，试根据对偶理论求出原问题的最优解解，该原问题的对偶问题为：min Y=20w1+20w2s.T w1+2w2 1 (1) w1+2w21 x1=0 2w1+w2 2 (2) 2w1+w22 x2=0 2w1+3w2 3 (3) 2w1+3w2=3 3w1+2w2 4 (4) 3w1+2w2=4 w1,w2 0将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到X1=x2=0又w1,w20，由松驰性质得到原问题约束条件应取等号即w10 2x3+3x4=20w2 0 3x3+2x4=20， 解方程组，得x3=x4=4所以原问题的最优解为：X=(0,0,4,4)T3已知线性规划问题Max z=2x1+x2+5x3+6x4s.T 2x1 + x3+ x4 8 2x1+2x2+x3+2x412 x1 ,x2 ,x3 , x4 , 0其对偶问题的最优解为w=(4,1)T，试根据对偶理论求出原问题的最优解解，该原问题的对偶问题为：min Y=8w1+12w2s.T 2w1+2w2 2 (1) 2w1+2w22 x1=0 2w2 1 (2) 2w21 x2=0 w1+ w2 5 (3) w1+w2=5 w1+2w2 6 (4) w1+2w2=6 w1,w2 0将对偶问题的最优解代入，得到(1),(2)为严格不等式，故由互补松驰性质得到X1=x2=0又w1,w20，由松驰性质得到原问题约束条件应取等号即W10 x3+x4=8W20 x3+2x4=12，解方程组，得x3=x4=4所以原问题的最优解为X=(0,0,4,4)T4 A工厂计划生产甲、乙两种产品。每千克产品的销售价格和能源消耗量、以及能源资源见表3-26，怎样安排生产计划才能使A工厂获益最大？ 解：x1：产品甲的计划生产量；x2：产品乙的计划生产量，则有如下线性规划问题： max z=7x1 + 12x2 (总销售收入) s.t. 9x1 + 4x2 360 (煤资源限制) 4x1 + 5x2 200 (电资源限制) 3x1 + 10x2 300 (油资源限制) x1 0，x2 0 (非负条件)用单纯形法求解得：x1=20，x2=24。 原问题的最优解为X(20,24)T,对应的对偶价格，也就是影子价格为(0,1.36,0.52)5 已知企业关于获利的线性规划问题如下所示：Max z=-5x1+5x2+13x3s.T -x1+x2+3x3 20 12x1+4x2+10x390 x1 ,x2 ,x3 0(1)试确定获得最大利润的产品计划。(2)产品B的利润（即x2)在什么范围内变化时，上述的最优生产计划不变。(3)如果设计一种新产品D，单位劳动力（即第一种资源）消耗为2单位，材料（第二种资源）消耗为3单位，每件可获利12元，问该产品是否值得生产？(1)将原问题引入松驰变量化为标准，通过两步迭代得到最优单纯形表： 即最优生产计划为：即最优生产计划为：x1=0,x2=20,x3=0 ,最优值为max z=100（2） 假设B产品的变化量为C表三-551300XbbbX1X2X3X4X55X220-113100X510160-2-410c-2-50解得：-2/3 C 0故产品B在13/3 C 5时，最优生产计划为不变（3）由最优表可知，第一种资源的影子价格为5，第二种资源的影子价格为0，因此D产品的生产成本为：生产成本：52031012即生产成本小于12，企业有利图，值得生产。6.P114 页。4.3题解：设生产A、B、C三种产品的数量分别为x1,x2,x3，依题意得：Max z=3x1+x2+4x3s.t 6x1+3x2+5x345 3x1+4x2+5x330x1,x2,x30 利用单纯形法求解得表一至表三： 表二31400 xbbX1X2X3X4X5 X4153-101-1 X563/54/5101/53/5-11/500-4/5表三31400XBbx1x2x3x4x5X151-1/301/3-1/3X33011-1/52/50-20-1/5-3/5由表三可知，所有的检验数均小于等于0，所以表三为最优表，最优解为X=(5,0,3)T (2)设A产品的变化范围为C，利用灵敏度分析得表四：表四31400XBbx1X2x3x4x5X151-1/301/3-1/3X33011-1/52/50c/3-20-c/3-1/5c/3-3/5要使表四为最优表须：c/3-20 -c/3-1/50 c/3-3/50解不等式得：-3/5c9/5 所以产品A的最优变化范围为12/5,24/5 (3)由表三可知两种资源的影子价格分别为：1/5,3/5 增加新产品的成本为：1/5*8+2*3/5=14/5 9/7方向开拓，当t9/7时，首先遇到40,故此时，x4应进基，利用最小比原则可得x3应为出基-下面再向t5方向开拓，当t5时，首先遇到40,故此时，x4应进基，利用最小比原则可得x3应为出基故当9/7t5时，最优解为：X=(4,3,0,6,0)T 最优值z=27+5tt9/7t 5要使表二为最优表，须有：9/2-7t/2 0-5/2+t/2 0下面再向t5方向开拓，当t5时，首先遇到40,故此时，x4应进基，利用最小比原则可得x3应为出基综上所述：故当t5时，最优解为：X=(4,0,0,12,6)T 最优值z=12+8tt5t -3/2要使表三为最优表，须有：5-t 0-3-2t 013某地有10个村庄，它们之间的交通道路如下图所示，图中边旁权为道路长度(单位：百米)，现在要沿道架设电线，实现村村通电话工程，问应如何架设电线才能使总长度最短？解：本题实质是最小树问题，利用避圈法可求得最短路线，如下图粗线所示：最优架设路线如上图粗线所示，架设电线最短长度为18(百米)。 附判断定理3.1 （对称性定理）对偶问题的对偶问题是原问题根据对称性定理，在任一对偶问题中，可以把其中的任何一个称为原问题，而把另一个称为其对偶问题定义4.1：如果线性规划问题存在一组基本可行解，其中至少有一分量为零时，则称该问题为退化的。 Max()松驰变量的检验数的相反数为对偶问题的最优解Min() 松驰变