管理运筹学习题3解答

文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 1文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 《管理运筹学》习题3及参考答案 1、某公司从三个产地A1，A2， A3将物品运往三个销地B1，B2，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）第一步：用最小元素法确定初始方案（方案不唯一，增补的零元素不能位于同行或同列）。

方法二：伏格尔法（最接近最优解） 方法三：西北角法（初始解离最优解较远） 第二步：求非基变量检验数，验证初始方案（最小元素法求得的初始方案）是否为最优方案。 法一：用位势法求检验数。 求解见下表所示： 销地 产地 销地一 销地二 销地三 销地四 Ui

产地一 x11 3 4 5 2 7 x14 0 0 产地二 3 6 x22 1 x23 5 x24 0 0 产地三 x31 2 4 4 -1 3 1 0 -1 Vj 3 1 5 0 因为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作为进基变量。调整量θ＝min(10,20,20)=10，按照上图所示进行调整，选择x14

作为出基变量。

方案调整后为方案二，如下： 用位势法可求出方案二非基变量检验数： 销地 产地 销地一 销地二 销地三 销地四 Ui

产地一 x11 3 5 5 3 7 1 0 0 产地二 2 6 x22 1 x23 5 x24 0 1 产地三 x31 2 5 4 x33 3 2 0 -1 Vj 3 0 4 -1 因为所有非基变量检验数σij都大于零，所以方案二就是唯一最优方案。 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 2文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 第四步： 决策结论：产地一向销地一调拨物资10吨，产地二分别向销地二、销地三调拨物资各10吨，产地二过剩生产的物资为10吨；产地三分别向销地一、销地三调拨物资10吨、10吨。最小总运费＝10×3+10×1+10×5+10×2+10×3=140（百元）。 2、求下列线性规划问题的对偶问题： 解：根据原模型很容易判断x1是自由变量，而x2≥0。 方法一：按对称形式变换 （1）原模型可变换为如下模型： （2）按对称形式变换关系可写出它的对偶问题，模型如下： (3)令112233445566778,,,,,,ykkykykykykykyk，将上一步得到的模型整理为： 方法二：根据原问题和对偶问题的对应关系直接变换 （1）将原模型作如下变换： （2）根据上述问题和对偶问题的对应关系，直接写出其对偶问题，即：（实际上和方法一得到的结果是一样的）

12345672345126712312311min 16252105252337325..322848 y2,4,60;y3,5,70jj

wyyyyyyyyyyyyyyyyyystyyyyyjj













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，∵3331623202BccP ∴各产品最优产量计划要改变。以x3为进基变量，在最优表基础上继续迭代，直至求出新的最优产量方案。计算过程如下： 2 3 6 0 0 θi CB XB B-1b x1 x2 x3 x4 x5

为自由变量； 文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 3文档来源为:从网络收集整理.word版本可编辑.欢迎下载支持. 2 3 6 0 0 θi CB XB B-1b x1 x2 x3 x4 x5

2 3 x1 x2 1 2 1 0 0 1 -1 [2] 4 -1 -1 1 － 1

σj=cj-zj 0 0 2 -5 -1 2 6 x1 x3 2 1 1 0 1/2 1/2 0 1 7/2 -1/2 -1/2 1/2

σj=cj-zj 10 0 -1 0 -4 -2 ∵所有非基变量检验数σj<0(j=2,4,5), ∴得到唯一最优解X*=(2,0,1,0,0)T,max z=10 即：A、B、C的产量调整为2吨、0吨、1吨，利润总和上升到10（千元）。 （2）x1为基变量，若所有非基变量检验数

11111141(100)354330211jjBjccBPcccc









即3/4≤c1≤3（千元/吨）时，原最优解不变。但c1由2变为4，344[,3]，所以最优产量计划要变化。在原最优表基础上继续迭代，直至求出新的最优产量方案。计算过程如下： 4 3 1 0 0 θi CB XB B-1b x1 x2 x3 x4 x5

4 3 x1 x2 1 2 1 0 0 1 -1 2 4 -1 -1 [1] － 2

σj=cj-zj 0 0 -1 -13 1 4 0 x1 x5 3 2 1 0 1 [1] 1 2 3 -1 0 1 3 2

σj=cj-zj 12 0 -1 -3 -12 0 ∵所有非基变量检验数σj<0(j=2,3,4), ∴得到唯一最优解X*=(3,0,0,0,2)T,max z=12 即：A、B、C的产量调整为3吨、0吨、0吨，利润总和上升到12（千元）。

（3）若11314410,3113bBbb即（吨）时，上述最优基不变。 劳动力约束增加1个单位时总利润的增加量就是劳动力资源的影子价格，显然总利润增加量＝-σ4=-(-5)=5（千元）。或者：∵3142[,3]b，∴原问题最优基不变。总利润增加

量1125185()3BBcBbcBb千元。（注：cBB-1就是最优表上松弛变量检验数的相反数） （4）设生产产品D为x'4单位，'14441351301BccBP







Q

∴新产品D 不值得生产。 （5）新的设备台时约束条件：12324xxx。代X*=(1,2,0,0,0)T入此条件，可知该条件不成立。所以原问题最优表对应的产量最优方案需要改进。 由最优表第一行约束条件得到：134514xxxx； 由最优表第二行约束条件得到：234522xxxx 将上述两个表达式带入设备台时约束条件，并添加松弛变量x6，整理得到：

3456221xxxx。将其添加到原问题最优表上，用对偶单纯形法继续迭代求解，

求解过程和结果如下： 2 3 1 0 0 0