《运筹学考试解答》由会员分享，可在线阅读，更多相关《运筹学考试解答（4页珍藏版）》请在金锄头文库上搜索。
1、1运筹学考运筹学考试试（ （2007 年秋季学期年秋季学期 里仁）里仁）1、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等） ，希望获得其中的营养成分（如：蛋白 质、脂肪、维生素等） 。设市面上现有这 3 种营养物，其分别含有各种营养成分数量，以及各营养物价格 和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为321xxx和、则根据题意
2、可得如下线性规划模型：0,45035721703652802064. .452025min32132131321321321xxxxxxxxxxxxxxtsxxxz2、线性规划问题0,4262max32121321321xxxxxxxxxxxZ用单纯形法求解得最终单纯形表如下表所示。x1x2x3x4x5x1611110X51003111cj-zj0-3-1-20试说明分别发生如下变化时，新的最优解是什么？（1）目标函数变为；32132maxxxxZ（2）约束条件右端项由变为； 46 43（3）增添一个新的约束。2231xx解：（1）cj23100CBxBbx1x2x3x4x5i营养物 营养成分
3、22x161111020x510031110cj-zj01-1-202x18/3102/32/3-1/323X210/3011/31/31/30cj-zj00-4/3-7/3-1/3因为所有的检验数均小于等于零。故最优解为)0 , 0 , 0 , 3/10, 3/8(*X（2）因为。所以 03,11011bB 331bBcj2-1100CBxBbx1x2x3x4x5i2x13111100x5703111cj-zj0-3-1-20因为所有的检验数均小于等于零，故最优解为)7 , 0 , 0 , 0 , 3(*X（3）由于，26026231xx所以原问题的最优解不是该问题的最优解。在约束条件左右两
4、端同时乘以“-1”，并加上松弛变量，2231xx6x得到22631xxxcj2-11000CBxBbx1x2x3x4x5x6i2x161111000x5100311100x6-210-2001cj-zj0-3-1-2002x161111000x5100311100x6-80-1-3-101cj-zj0-3-1-2002x110/312/302/301/30x522/308/302/311/31x38/301/311/30-1/3cj-zj0-8/30-5/30-1/3因为所有的检验数均小于等于零，故最优解为)3/22, 0 , 3/8 , 0 , 3/10(*X3、已知运输问题的产销平衡表与单
5、位运价表如下表所示。销地甲乙丙丁产量A327650B752360产 地销 地产地3C254525销量60402015试用表上作业法求出最优解。 解：本问题是产销平衡问题。根据最小元素法，初始可行解为：甲乙丙丁产量A104050B25201560C2525销量 60402015135采用位势法，可得检验数如下表所示（为了区别，检验数用“括号里的数字”表示）甲乙丙丁产量UiA10（0）40（0） （9）（7）500B25(0)（-1）20(0)15(0)604C25(0)（4）（7）（7）25-1销量 60402015135Vj32-2-1因为（B，乙）的检验数为-1，所以该初始可行解非最优解。
6、从空格（B，乙）出发的闭回路为（B，乙）（B，甲）（A，甲）（A，乙）（B，乙）。该闭回路的偶数顶点位于格（B，甲）和（A，乙），由于25)40,25min(所以可得如下可行解甲乙丙丁产量UiA35（0）15（0） （8）（6）500B (1)25（0）20(0)15(0)603C25(0)（4）（6）（6）25-1销量 60402015135Vj32-10由于所有空格的检验数均大于零。所以得到唯一最优解。4、用匈牙利法求解下列的指派问题，已知效率矩阵如下：。1096109532485724679278310283解： 3202220005240034603507040109610953248
7、57246792783102831000020205242032401307240由于得到了 5 个独立零元素，故可得最优指派方案。本题的最优解为： 4。这样可使目标函数最小，为 3+2+4+3+9=21。0000101000000100010010000*X5、已知线性规划问题4, 3 , 2, 10332232 . .6532min432143214321jxxxxxxxxx tsxxxxzj（1）写出其对偶问题； （2）用图解法求对偶问题的解； （3）利用（2）的结果及对偶性质求原问题解。 解：（1）原线性规划问题可化为：4 , 3 , 2 , 10332232. .6532min432143214321jxxxxxxxxxtsxxxxzj其对偶问题为：0,63533222. .32max212121212121yyyyyyyyyytsyyw（2）用图解法解得 )51,58(),(21*yyY519*w（3）由互补松弛性定理知道，0, 613421xyyQ又由 32232519532x,321321321*xxxxxxxxwz可得：解之，可得原问题最优解。)0 ,51, 0 ,57(*X
