运筹学考试2007年秋季学期里仁.doc

《运筹学考试2007年秋季学期里仁.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、运筹学考试（2007年秋季学期里仁）1、消费者购买某一时期需要的营养物（如大米、猪肉、牛奶等），希望获得其中的营养成分（如：蛋白质、脂肪、维生素等）。设市面上现有这3种营养物，其分别含有各种营养成分数量，以及各营养物价格和根据医生建议消费者这段时间至少需要的各种营养成分的数量（单位都略去）见下表。营养物营养成分甲乙丙至少需要的营养成分数量A462080B11265C10370D21735450价格252045问：消费者怎么购买营养物，才能既获得必要的营养成分，而花钱最少？只建立模型，不用计算。解：设购买甲、乙、丙三种营养物的数量分别为则根据题意可得如下

2、线性规划模型：2、线性规划问题用单纯形法求解得最终单纯形表如下表所示。x1x2x3x4x5x1611110X51003111cj-zj0-3-1-20试说明分别发生如下变化时，新的最优解是什么？（1）目标函数变为；（2）约束条件右端项由变为；（3）增添一个新的约束。解：（1）cj→23100θiCBxBbx1x2x3x4x52x161111020x5100[3]1110cj-zj01-1-202x18/3102/32/3-1/323X210/3011/31/31/30cj-zj00-4/3-7/3-1/3因为所有的检验数均小于等于零。故最优解为（2）因

3、为。所以cj→2-1100θiCBxBbx1x2x3x4x52x13111100x5703111cj-zj0-3-1-20因为所有的检验数均小于等于零，故最优解为（3）由于，所以原问题的最优解不是该问题的最优解。在约束条件左右两端同时乘以“-1”，并加上松弛变量，得到cj→2-11000θiCBxBbx1x2x3x4x5x62x161111000x5100311100x6-210-2001cj-zj0-3-1-2002x161111000x5100311100x6-80-1[-3]-101cj-zj0-3-1-2002x110/312/302/301/

4、30x522/308/302/311/31x38/301/311/30-1/3cj-zj0-8/30-5/30-1/3因为所有的检验数均小于等于零，故最优解为产地销地产地3、已知运输问题的产销平衡表与单位运价表如下表所示。销地甲乙丙丁产量A327650B752360C254525销量60402015试用表上作业法求出最优解。解：本问题是产销平衡问题。根据最小元素法，初始可行解为：甲乙丙丁产量A104050B25201560C2525销量60402015135采用位势法，可得检验数如下表所示（为了区别，检验数用“括号里的数字”表示）甲乙丙丁产量UiA10

5、（0）40（0）（9）（7）500B25(0)（-1）20(0)15(0)604C25(0)（4）（7）（7）25-1销量60402015135Vj32-2-1因为（B，乙）的检验数为-1，所以该初始可行解非最优解。从空格（B，乙）出发的闭回路为（B，乙）——（B，甲）——（A，甲）——（A，乙）——（B，乙）。该闭回路的偶数顶点位于格（B，甲）和（A，乙），由于所以可得如下可行解甲乙丙丁产量UiA35（0）15（0）（8）（6）500B(1)25（0）20(0)15(0)603C25(0)（4）（6）（6）25-1销量60402015135Vj32-

6、10由于所有空格的检验数均大于零。所以得到唯一最优解。4、用匈牙利法求解下列的指派问题，已知效率矩阵如下：。√√√解：→由于得到了5个独立零元素，故可得最优指派方案。本题的最优解为：。这样可使目标函数最小，为3+2+4+3+9=21。5、已知线性规划问题（1）写出其对偶问题；（2）用图解法求对偶问题的解；（3）利用（2）的结果及对偶性质求原问题解。解：（1）原线性规划问题可化为：其对偶问题为：（2）用图解法解得（3）由互补松弛性定理知道，又由解之，可得原问题最优解