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

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

1、《管理运筹学》习题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）的该种商品的数量为xi

2、j吨，则可以建立以下模型：（2）因为总产量60（＝10+30+20）大于总需求量50（＝20+10+20），所以本问题不是标准运输问题。增加一个虚拟销地，它的单位运价c14＝c24＝c34，需求量为60-50=10。（3）第一步：用最小元素法确定初始方案（方案不唯一，增补的零元素不能位于同行或同列）。方法二：伏格尔法（最接近最优解）方法三：西北角法（初始解离最优解较远）第二步：求非基变量检验数，验证初始方案（最小元素法求得的初始方案）是否为最优方案。法一：用位势法求检验数。求解见下表所示：销地产地销地一销地二销地三销地四Ui产地一x1134527x1400产地二36x22

3、1x235x2400产地三x31244-1310-1Vj3150因为min(σ33)＝σ33=-1<0，所以初始方案并非最优方案，需进一步调整，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=-1<0，所以初始方案并非最优方案，需进一步调整，x33为进基变量。第三步：求θ值，调整方案。过程如下：以X33作为进基变量。调整量θ＝m

4、in(10,20,20)=10，按照上图所示进行调整，选择x14作为出基变量。方案调整后为方案二，如下：用位势法可求出方案二非基变量检验数：销地产地销地一销地二销地三销地四Ui产地一x1135537100产地二26x221x235x2401产地三x31254x33320-1Vj304-1因为所有非基变量检验数σij都大于零，所以方案二就是唯一最优方案。第四步：决策结论：产地一向销地一调拨物资10吨，产地二分别向销地二、销地三调拨物资各10吨，产地二过剩生产的物资为10吨；产地三分别向销地一、销地三调拨物资10吨、10吨。最小总运费＝10×3+10×1+10×5+10×2+

5、10×3=140（百元）。2、求下列线性规划问题的对偶问题：解：根据原模型很容易判断x1是自由变量，而x2≥0。方法一：按对称形式变换（1）原模型可变换为如下模型：（2）按对称形式变换关系可写出它的对偶问题，模型如下：(3)令，将上一步得到的模型整理为：方法二：根据原问题和对偶问题的对应关系直接变换（1）将原模型作如下变换：（2）根据上述问题和对偶问题的对应关系，直接写出其对偶问题，即：（实际上和方法一得到的结果是一样的）为自由变量；3、有下列线性规划问题，Z代表三种产品的利润总和（单位：千元）。下表是单纯形法求解的最优表：请回答下列问题：（1）如果每吨产品C的利润提高到

6、6（千元），那么各产品最优产量计划是否改变？如果要改变，求出改进的最优产量安排？（2）如果每吨产品A的利润提高到4（千元），那么各产品最优产量计划是否改变？如果要改变，求出改进的最优产量安排？（3）当劳动力约束由1变为2，总利润将增加多少？求出劳动力数量在什么范围内变动，上述表格的最优基不变？（4）有一种新产品D，它的单位利润是3千元／吨，生产一吨新产品D需投入全部劳动工时及耗费一吨原材料。它是否值得生产？如果生产它，那么上述最优表对应的最优方案如何改进？（5）比如现在需要考虑设备的生产能力限制，设台时消耗不能超过4个单位，而三种产品的单位台时消耗分别为1、2、1个单位，

7、那上述最优表对应的产量最优方案需要改进吗？如果需要，求出改进的产量最优方案。解：（1）x3为非基变量，c3由1变为6，∵∴各产品最优产量计划要改变。以x3为进基变量，在最优表基础上继续迭代，直至求出新的最优产量方案。计算过程如下：23600θiCBXBB-1bx1x2x3x4x523x1x2121001-1[2]4-1-11－1σj=cj-zj002-5-126x1x321101/21/2017/2-1/2-1/21/2σj=cj-zj100-10-4-2∵所有非基变量检验数σj<0(j=2,4,5),∴得到唯一最优解X*=(