管理运筹学习题3解答.doc

管理运筹学习题3及参考答案1、某公司从三个产地A1，A2， A3将物品运往三个销地B1，B2，B3，产量平衡表和单位运价表如表1所示。问如何调运，使得总运输费用最小？表1 产销平衡表和单位运价表 销地Bj产地AiB1B2B3产量（件）A135710A261530A324320需求量（件）201020要求：（1）请建立该问题的线性规划模型，然后再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。解：（1）设第i个产地（i=1,2,3）到第j个销地（j=1,2,3）的该种商品的数量为xij吨，则可以建立以下模型： （2）因为总产量60（10+30+20）大于总需求量50（20+10+20），所以本问题不是标准运输问题。增加一个虚拟销地，它的单位运价c14c24c34，需求量为60-50=10。（3）第一步：用最小元素法确定初始方案（方案不唯一，增补的零元素不能位于同行或同列）。 方法二：伏格尔法（最接近最优解） 方法三：西北角法（初始解离最优解较远） 第二步：求非基变量检验数，验证初始方案（最小元素法求得的初始方案）是否为最优方案。法一：用位势法求检验数。求解见下表所示： 销地产地销地一销地二销地三销地四Ui产地一x1134527x1400产地二36x221x235x2400产地三x31244-1310-1Vj3150 因为min(33)33=-10，所以初始方案并非最优方案，需进一步调整，x33为进基变量。法二：用闭回路法求检验数12=5-0+0-1=4；13=7-0+0-5=2；21=6-3+0-0=3；32=4-2+3-0+0-1=4（注：图中画出了非基变量x33的闭回路）；33=3-2+3-0+0-5=-1；34=0-2+3-0=1因为min(33)33=-10，所以初始方案并非最优方案，需进一步调整，x33为进基变量。第三步：求值，调整方案。过程如下： 以X33作为进基变量。调整量min(10,20,20)=10，按照上图所示进行调整，选择x14作为出基变量。方案调整后为方案二，如下： 用位势法可求出方案二非基变量检验数：销地产地销地一销地二销地三销地四Ui产地一x1135537100产地二26x221x235x2401产地三x31254x33320-1Vj304-1因为所有非基变量检验数ij都大于零，所以方案二就是唯一最优方案。第四步：决策结论：产地一向销地一调拨物资10吨，产地二分别向销地二、销地三调拨物资各10吨，产地二过剩生产的物资为10吨；产地三分别向销地一、销地三调拨物资10吨、10吨。最小总运费103+101+105+102+103=140（百元）。2、求下列线性规划问题的对偶问题： 解：根据原模型很容易判断x1是自由变量，而x20。方法一：按对称形式变换（1）原模型可变换为如下模型：（2）按对称形式变换关系可写出它的对偶问题，模型如下：(3)令，将上一步得到的模型整理为：方法二：根据原问题和对偶问题的对应关系直接变换（1）将原模型作如下变换：（2）根据上述问题和对偶问题的对应关系，直接写出其对偶问题，即：（实际上和方法一得到的结果是一样的）为自由变量；3、有下列线性规划问题，Z代表三种产品的利润总和（单位：千元）。下表是单纯形法求解的最优表：请回答下列问题：（1）如果每吨产品C的利润提高到6（千元），那么各产品最优产量计划是否改变？如果要改变，求出改进的最优产量安排？（2）如果每吨产品A的利润提高到4（千元），那么各产品最优产量计划是否改变？如果要改变，求出改进的最优产量安排？（3）当劳动力约束由1变为2，总利润将增加多少？求出劳动力数量在什么范围内变动，上述表格的最优基不变？（4）有一种新产品D，它的单位利润是3千元吨，生产一吨新产品D需投入全部劳动工时及耗费一吨原材料。它是否值得生产？如果生产它，那么上述最优表对应的最优方案如何改进？（5）比如现在需要考虑设备的生产能力限制，设台时消耗不能超过4个单位，而三种产品的单位台时消耗分别为1、2、1个单位，那上述最优表对应的产量最优方案需要改进吗？如果需要，求出改进的产量最优方案。解：（1）x3为非基变量，c3由1变为6，各产品最优产量计划要改变。以x3为进基变量，在最优表基础上继续迭代，直至求出新的最优产量方案。计算过程如下：23600iCBXBB-1bx1x2x3x4x523x1x2121001-124-1-111j=cj-zj002-5-126x1x321101/21/2017/2-1/2-1/21/2j=cj-zj100-10-4-2所有非基变量检验数j0(j=2,4,5), 得到唯一最优解X*=(2,0,1,0,0)T,max z=10即：A、B、C的产量调整为2吨、0吨、1吨，利润总和上升到10（千元）。（2）x1为基变量，若所有非基变量检验数即3/4c13（千元/吨）时，原最优解不变。但c1由2变为4，所以最优产量计划要变化。在原最优表基础上继续迭代，直至求出新的最优产量方案。计算过程如下：43100iCBXBB-1bx1x2x3x4x543x1x2121001-124-1-112j=cj-zj00-1-13140x1x5321011123-10132j=cj-zj120-1-3-120所有非基变量检验数j0(j=2,3,4), 得到唯一最优解X*=(3,0,0,0,2)T,max z=12即：A、B、C的产量调整为3吨、0吨、0吨，利润总和上升到12（千元）。（3）若（吨）时，上述最优基不变。 劳动力约束增加1个单位时总利润的增加量就是劳动力资源的影子价格，显然总利润增加量-4=-(-5)=5（千元）。或者：，原问题最优基不变。总利润增加量。（注：cBB-1就是最优表上松弛变量检验数的相反数）（4）设生产产品D为x4单位，新产品D 不值得生产。（5）新的设备台时约束条件：。代X*=(1,2,0,0,0)T入此条件，可知该条件不成立。所以原问题最优表对应的产量最优方案需要改进。由最优表第一行约束条件得到：；由最优表第二行约束条件得到： 将上述两个表达式带入设备台时约束条件，并添加松弛变量x6，整理得到：。将其添加到原问题最优表上，用对偶单纯形法继续迭代求解，求解过程和结果如下：231000CBXBB-1bx1x2x3x4x5x6230x1x2x612-1100010-12-24-1-2-11-1001j=cj-zj00-3-5-10j1.52.51230x1x2x52111001101026-32001-11-1j=cj-zj700-1-30-1所有非基变量检验数j0(j=3,4,6), 得到唯一最优解X*=(2,1,0,0,1)T,max z=7即：A、B、C的产量调整为2吨、1吨、0吨，利润总和下降到7（千元）。4、（选做题）已知目标规划问题 用单纯形法求解时，得到如下最优表。分析目标函数分别变为、两种情况时解的变化。可绘制图进行分析或者列单纯形表进行分析。Cj00P1P40P25P303P30CBXBB-1bx1x2d1-d1+d2-d2+d3-d3+d4-d4+0P43P30x1 d1+d4-x213/233/45/4100000010-10001001/21-1/41/4-1/2-11/4-1/4-1/201/4-1/4-1/20-1/40001000-103-jcj-zjP1P2P3P411-13/411-1/417/43/43（1）（2）（w1,w2为权重比例且都大于零）解：如图1所示：依次满足目标P1、P2和P3的区域是线段CEBD。方程：x1+2x2=6E D C d-4 d+4 d-1 d+1 d-2 d+2 B A 54321 0 1 2 3 4 5 6 7 8 9 10 d+3 d-3 x1 x2 C(0,3)、E(2,2)、B(5,1/2)、D(6,0)。令t=5d3-+3d4-当x12时，t=5d3-=5(4-x1+2x2)=5(10-2x1)min t=30,此时对应x1=2,x2=2当2x15时，t=5d3-+3d4-=5(4-x1+2x2)+3(2-x2)=-4+17x2 min t=30,此时对应x1=2,x2=2当50)x2 由（1）分析知道：满足目标P1、P2x1 d-3 d+3 0 1 2 3 4 5 6 7 8 9 10 54321 A d+2 d-2 d+1 d-1 d+4 d-4 的区域为x1+2x2=k(6k9),它与B D C 直线x2=2、x1-2x2=4分别交于C(k-4,2)、D(2+k/2,k/4-1)两点。当x1k-4时，t= ad3-=a(4-x1+2x2)=a(4-k+4x2) 当k=9, x2=2, x1=5时,min t1=3a;当k-4x12+k/2时，t= ad3-+d4-=a(4-x1+2x2)+(2-x2)=(4-k)a+2+(4a-1)x2若a1/4时k=9, x2=5/4, x1=13/2时,min t2=3/4;若0a1/4时k=9, x2=2, x1=5时,min t2=3a1/4时,min(min t1,min t2,min t3)=3/4=min t2=min t3,此时满意解为x1=13/2, x2=5/4;当0a= w1/w21/4时, min t1=3a=min t2min t3=3/4,此时满意解为x1=5, x2=2。当a= w1/w2=1/4时, min t1=min t2=min t3=3/4,此时满意解为x1=5, x2=2和x1=13/2, x2=5/4。用单纯形法作灵敏度分析，如下：Cj00P1P40P2w1P30w2P30CBXBB-1bx1x2d1-d1+d2-d2+d3-d3+d4-d4+0P4w2P30x1 d1+d4-x213/233/45/4100000010-10001001/21-1/41/4-1/2-11/4-1/4-1/201/4-1/4-1/20-1/40001000-103-jcj-zjP1P2P3P411-1w2/411- w2/4w1- w2/4w2/4w20P4w1P30x1 d1+d3-x25332100000010-100010011-10-1-110001000-10-204120-4-1jcj-zjP1P2P3P411w1-11- w11w1w2-4w14w1可见，当：当w1/w21/4时,满意解为x1=13/2, x2=5/4;当0 w1/w21/4时,满意解为x1=5, x2=2。5、（选做题：华中科技大学考研试题）公司计划生产A、B两种产品，须分别经过甲、乙、丙三道工序，其有关数据如下表所示。问：（1）如何安排生产计划，使得公司的产值和利润尽可能的高（要求建立目标规划模型，不须求解该模型）？（2）若公司认为利润比产值更重要，则应如何决策？（说明思路）。耗用工时 工 序产品甲乙丙产品单价单件利润AB22122.20.85070108加工能力/小时12010090解：设x1、x2分别为A、B两种产品的产量，则有多目标线性规划模型（1）分别