管理运筹学习题3解答

1、文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持.管理运筹学习题 3及参考答案1、某公司从三个产地 A1, A2, A3将物品运往三个销地 B1, B2, B3,产量平衡表和单位 运价表如表1所示。问如何调运，使得总运输费用最小？表1产销平衡表和单位运价表肖地Bj产地A1B1B2B3产量（件）35710A261530A24320需求量（件）201020要求：（1）请建立该问题的线性规划模型，然后再化为标准问题。（2）用表上作业法求解：用最小元素法确定初始方案；用位势法验证初始方案是否最优？如果非最优，请用闭回路法调整，直至求出最优方案。解：（1） 设第i个产地（i=1,2,3）到第

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

3、33=-1<0，所以初始方案并非最优方案，需进一步调整， 法二：用闭回路法求检验数b 12=5-0+0-1=4 ; b 13=7-0+0-5=2 ；b 21=6-3+0-0=3 ; b 32=4-2+3-0+0-1=4 基变量 X33的闭回路）；b 33=3-2+3-0+0-5=-1；b 34=0-2+3-0=1 因为min（ b 33）=b 33=-1<0,所以初始方案并非最优方案，需进一步调整， 第三步：求0值，调整方案。过程如下：以X33作为进基变量。调整量0=min（10,20,20）=10,按照上图所示进行调整，选择X14作为出基变量。方案调整后为方案二，如下：用位势法可

4、求出方案二非基变量检验数：X33为进基变量。（注：图中画出了非X33为进基变量。产地销地一销地二销地三销地四Ui产地一X1134527X1400产地二36X221X235X2400产地三X31244-1310-13150'''-'-'-地 产地销地一销地二销地三销地四Ui产地一X1135537100产地二26X221X235X2401产地三X31254X33320-1304-1因为所有非基变量检验数b j都大于零，所以方案二就是唯一最优方案。第四步：决策结论：产地一向销地一调拨物资10吨，产地二分别向销地二、销地三调拨物资各10吨，产地二过剩生产的物资为

5、10吨；产地三分别向销地一、销地三调拨物资10吨、10吨。最小总运费=10X 3+10X 1+10X 5+10 X 2+10X 3=140 （百元）。2、求下列线性规划问题的对偶问题：解：根据原模型很容易判断X1是自由变量，而 X2> 0。方法一：按对称形式变换（1）原模型可变换为如下模型：（2）按对称形式变换关系可写出它的对偶问题，模型如下： 令 y1k1k2, y2k3, y3kq,yyk5,y5 k6,壮k?, y?kg,将上一步得到的模型整理为： 方法二：根据原问题和对偶问题的对应关系直接变换（1 ）将原模型作如下变换：即：（实际上和方法一得（2 ）根据上述问题和对偶问题的对应关

6、系，直接写出其对偶问题， 到的结果是一样的）min w16yi 2讨25y3 2y4 lOys 5*252y2yiy1 3y2 s.t.3为自由变量y 24y18ye y72y32y3yi2,4,6 O;yj j 3,5,703文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持.Z代表三种产品的利润总和（单位：千元） 。3、有下列线性规划问题， 下表是单纯形法求解的最优表： 请回答下列问题：（1）如果每吨产品C的利润提高到6 （千元），那么各产品最优产量计划是否改变？如果要 改变，求出改进的最优产量安排？（2）如果每吨产品 A的利润提高到4 （千元），那么各产品最优产量计划是否改变？

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

8、2 312 0 2各产品最优产量计划要改变。以X3为进基变量，在最优表基础上继续迭代，直至求出新2 3600CBXIB'1 b X1X2X3X4X50 i的最优产量方案。计算过程如下：文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持.7文档来源为：从网络收集整理.word版本可编辑.欢迎下载支持.236000 iCBXB bX1X2X3X4X52X1110-14-1一3X22012-111b j =Gj -Z j002-5-12X1211/207/2-1/26X3101/21-1/21/2b j =Gj -Z j100-10-4-2.所有非基变量检验数bj<0(j=2

9、,4,5),即：A B、C的产量调整为2吨、0吨、(2) X1为基变量，若所有非基变量检验数得到唯一最优解X =(2,0,1,0,0)1吨，利润总和上升到T,max z=1010 (千元)。jGjCbB Pj(10 0) G1 1G1由2变为G, 54G, 3 G, 304，4-4,3，所以最优产量431000 icbXB'bX1X2X3X4X54X110-14-1一3X22012-112b j =Gj -Z j00-1-1314X131113030X52012-112bj=Gj-Zj120-1-3-120即3/4 < GK 3 (千元/吨)时，原最优解不变。计划要变化。在原最优

10、表基础上继续迭代，直至求出新的最优产量方案。计算过程如下:j<0(j=2,3,4),3吨、0吨、所有非基变量检验数b 即：A B、C的产量调整为1*T得到唯一最优解 X=(3,0,0,0,2) ,max z=12 0吨，利润总和上升到12 (千元)。卄 14(3 )若 B 1b1劳动力约束增加力加量=-b 4=-(-5)=5b 0,即7 b 3 (吨)时，上述最优基不变。311个单位时总利润的增加量就是劳动力资源的影子价格, (千元)。或者： b, 2 -3,3,显然总利润增原问题最优基不变。总利润增加量 CbB 1bCbB 1b8 5(千元)。(注:gbB'1就是最优表上松弛变

11、量检验数的相反数)(4)设生产产品D为X4单位，Q4 G4GBBpt新产品D不值得生产。(5)新的设备台时约束条件：Xi不成立。所以原问题最优表对应的产量最优方案需要改进。由最优表第一行约束条件得到：x1 1 x3 4x4 x5 ；由最优表第二行约束条件得到：x2 2 2x3 x4 x5将上述两个表达式带入设备台时约束条件，并添加松弛变量X6,整理得到：2X3 2x4 X5 x 1。将其添加到原问题最优表上，用对偶单纯形法继续迭代求解, 求解过程和结果如下：2X2X34。代X*=(1,2,0,0,0)T入此条件，可知该条件2 31000cbXbB bX1 IX2X3X4X5X62X1110-1

12、4-103X22012-1100X6-100-2-2-11b j=Cj-Z j00-3-5-100 j1.52.512X1211160-13X21010-3010X5100221-1b j=Cj-Z j70 10-1-30-1(1 )minP1d1P2d2P3d1 P45d33d4(2)minP1d1P2d2P3 w1 d3w2d4 P4d1Pl、P2和P3的区域是线段CEBD 方程：Xi+2x2=6(W1,W2为权重比例且都大于零) 解：如图1所示：依次满足目标C(0,3)、令 t=5d3-+3d4- 当 xk 2 时，t= 5d3-=5(4-x1+2x2)=5(10-2x1) - min

13、t=30,此时对应 x1=2,x2=2 当 2<X1< 5 时， 3(2-X2)=-4+17x2 X1=2,X2=2 当 5<X1< 6 时，E(2,2)、B(5,1/2) 、D (6,0)。t=5d3-+3d4-=5(4-x1 +2x2)+min t=30,此时对应t=3d4-=3(2-X2)- min t=9/2,此时对应 X1=5,x2=1/2。综上所述，满意解为 X1=5,X2=1/2。可见， 交换目标等级，满意解发生了变化，由(132,5/4) 7 (5,1/2)。本小题也可以用单纯形法求解，学生可自行运算，这里略去。(2)用图解法。令 a=w1/w2, t=

14、 ad3-+d4-(a>0)由(1)分析知道：满足目标P1、P2的区域为 X1+2x2=k(6 < k w 9),它与所有非基变量检验数bj<0(j=3,4,6),得到唯一最优解 X=(2,1,0,0,1)',max z=7即：A B、C的产量调整为2吨、1吨、0吨，利润总和下降到 7 (千元)。4、(选做题)已知目标规划问题用单纯形法求解时，得到如下最优表。分析目标函数分别变为、两种情况时解的变化。 可绘制图进行分析或者列单纯形表进行分析。Cj700P1P40P25P303P300cbXb-1B bX1X2d1-d1+d2-d2+d3-d3+d4-d4+0X113/

15、210001/2-1/2-1/2-1/200P4d1 +300-111-1000033P3d4-3/40000-1/41/41/4-1/41-1-0X25/401001/4-1/4-1/4000-rCj-Zj11-13/411 -1/417/43/43直线 X2=2、X1-2x2=4 分别交于 C(k-4,2) 、D(2+k/2,k/4-1) 两点。当 X1W k-4 时，t= ad3'=a(4-x1+2x2)= a(4-k+4x2)当 k=9, X2=2, X1=5 时,min t1=3a; 当 k-4 w X1< 2+k/2 时，t= ad3'+d4'= a(

16、4-x 什2x2)+(2-X2)=(4-k)a+2+(4a-1)X2若 a> 1/4 时 k=9, X2=54, x1=13/2 时,min 12=3/4;若 0<a<1Z4 时 k=9, X2=2, X1=5 时,min t2=3a<34当 k>X1> 2+k/2 时，t= d4-=2-x2 当 x2=k/4-1=9/4-1=5/4, x1=13/2 时,min t3=34。综上所述:当 W1/w2= a>1/4 时,min(min 11,min t2,min t3)=34=min t2=min t3,此时满意解为 X1=13/2, X2=54; 当

17、 0<a= W1/w2<1/4 时，min 11=3a=min t2<min t3=34，此时满意解为 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=54。 用单纯形法作灵敏度分析，如下：公司计划生产A、B两种产品，须分别经过甲、乙、问： （1）如何安排生产计划，使得公司的产值和利润 不须求解该模型）？（2）若公司认为利润比产值更产品、序甲乙丙产品单价单件利润工时A、212.25010B220.8708加工能力/小时12010090O解：设XI、X2分别

18、为A、B两种产品的产量，则有多目标线性规划模型（1 ）分别就两个不同的目标求解线性规划，用单纯形法或图解法（这里略去，请大家自行计可见，当：当 Wi/W2> 1/4 时，满意解为 X1=132, X2=54;当 0< W1/W2W 1/4 时,满意解为 xi=5, X2=2。 5、（选做题：华中科技大学考研试题） 丙三道工序，其有关数据如下表所示。尽可能的高（要求建立目标规划模型， 重要，则应如何决策？（说明思路）CjT00P1P40P2W1P30W2P300CBXB-1B bX1x2d1-d1+d2-d2+d3-d3+d4-d4+0X113/210001/2-1/2-1/2-1/200P4d1 +300-111-100003w2P3d4-3/40000-1/41/41/4-1/41-1-0X25/401001/4-1/4-1/4000-P11-1W2/41W1- W2/4W2/4W2C.-z- j zjP211-W2/4rP3P40X1510001-100-22P4d1+300-111-10000w1P3d3-30000-111-14-40X22010000001-1P11W11W1W2-4w4w1P21-1-W1rCj-ZjP31P