《管理运筹学》习题3及参考答案 1、某公司从三个产地A1A2， A3将物品运往三个销地B1B2，B3产量平衡表和单位运价表如表1所示。问如何调运使得总运输费用最小？ 表1 产销平衡表和单位运价表 销地Bj 产地Ai B1 B2 B3 产量（件） A1 3 5 7 10 A2 6 1 5 30 A3 2 4 3 20 需求量（件） 20 10 20 要求：（1）请建立该问题的线性规划模型然后再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用位势法验证初始方案是否最优如果非最优，请用闭回路法调整直至求出最优方案。 解： （1）设第i個产地（i=1,2,3）到第j个销地（j=1,2,3）的该种商品的数量为xij吨则可以建立以下模型： （2）因为总产量60（＝10+30+20）大于总需求量50（＝20+10+20），所以本问题不是標准运输问题增加一个虚拟销地，它的单位运价c14＝c24＝c34需求量为60-50=10。 （3）第一步：用最小元素法确定初始方案（方案不唯一增补的零元素不能位于同行或同列）。 方法二：伏格尔法（最接近最优解） 方法三：西北角法（初始解离最优解较远） 因为min(σ33)＝σ33=-1<0所以初始方案并非最优方案，需进一步调整x33为进基变量。 第三步：求θ值，调整方案。 过程如下： 以X33作为进基变量调整量θ＝min(10,20,20)=10，按照上图所示进行调整选择x14 作为出基变量。 方案调整后为方案二如下： 用位势法可求出方案二非基变量检验数： 销地 产地 销地一 销地二 销地三 销地四 Ui 产地┅ 决策结论：产地一向销地一调拨物资10吨，产地二分别向销地二、销地三调拨物资各10吨产地二过剩生产的物资为10吨；产地三分别向销地┅、销地三调拨物资10吨、10吨。最小总运费＝10×3+10×1+10×5+10×2+10×3=140（百元） 2、求下列线性规划问题的对偶问题： 解：根据原模型很容易判断x1是自由變量，而x20 方法一：按对称形式变换 （1）原模型可变换为如下模型： （2）按对称形式变换关系可写出它的对偶问题，模型如下： (3)令将上┅步得到的模型整理为： 方法二：根据原问题和对偶问题的对应关系直接变换 （1）将原模型作如下变换： （2）根据上述问题和对偶问题的對应关系，直接写出其对偶问题即：（实际上和方法一得到的结果是一样的） 3、有下列线性规划问题，Z代表三种产品的利润总和（单位：千元） 下表是单纯形法求解的最优表： 请回答下列问题： （1）如果每吨产品C的利润提高到6（千元），那么各产品最优产量计划是否改變如果要改变，求出改进的最优产量安排 （2）如果每吨产品A的利润提高到4（千元），那么各产品最优产量计划是否改变如果要改变，求出改进的最优产量安排 （3）当劳动力约束由1变为2，总利润将增加多少求出劳动力数量在什么范围内变动，上述表格的最优基不变 （4）有一种新产品，它的单位利润是3千元／吨生产一吨新产品需投入全部劳动工时及耗费一吨原材料。它是否值得生产如果生产它，那么上述最优表对应的最优方案如何改进 （5）比如现在需要考虑设备的生产能力限制，设台时消耗不能超过4个单位而三种产品的单位台时消耗分别为1、2、1个单位，那上