2017东北大学852运筹学真题(回忆版)

目录Chapter 2 Linear programming (2)Solution： (4)Chapter 3 Simplex (6)Solution: (7)Chapter 4 Sensitivity Analysis and duality (11)Solution： (14)Chapter 5 Network (18)Solution: (20)Chapter 6 Integer Programming (23)Solution: (25)Chapter 7 Nonlinear Programming (28)Solution: (28)Chapter 8 Decision making under uncertainty (29)Solution: (31)Chapter 9 Game theory (34)Solution： (36)Chapter 10 Markov chains (39)Solution: (41)Chapter 11 Deterministic dynamic programming (43)Solution: (43)Expanded Projects (44)Chapter 2 Linear programming1. A firm manufactures chicken feed by mixing three different ingredients. Eachingredien t contains three key nutrients protein, fat and vitamin. The amount of each nutrient contained in 1 kilogram of the three basic ingredients is summarized in the following table:Ingredient Protein(grams)F at(grams)Vitamin(units)12511235245101603327190The costs per kilogram of Ingredients 1, 2, and 3 are $0.55, $0.42 and $0.38, respectively. Each kilogram of the feed must contain at least 35 grams of protein, a minimum of 8 grams of fat and a maximum of 10 grams of fat and at least 200 units of vitamin s. Formulate a linear programming model for finding the feed mix that has the minimum cost per kilogram.2.For a supermarket, the following clerks are required:Days Min. number of clerksMon 20T ue16Wed13Th u16F ri19Sat14Sun12Each clerk works 5 consecutive days per week and may start working on Monday, Wednesday or Friday.The objective is to find the smallest number of clerks required to comply with the above requirements. Formulate the problem as a linear programming model.3.Consider the following LP problem:12121212126841634243412,0MaxZ x x Subject tox x x x x x x x =++≤+≤-≤≥ (a) Sketch the feasible region.(b) Find two alternative optimal extreme (corner) points.(c) Find an infinite set of optimal solutions.4. A power plant has three thermal generators. The generators’ generation costsare $36/MW, $30/MW, and $25/MW, respectively. The output limitation for the generators is shown in the table. Some moment, the power demand for thisplant is 360MW, please set up an LP optimization model and find out the optimal output for each generator (with lowest operation cost).5. Use the Graphical Solution to find the optimal solutions to the following LP:12121212max 4.. 36 20 ,0z x x s t x x x x x x =-++≤-+≤≥Solution ：1. Let x 1 = the amoun t of Ingredien t 1 mixed in 1 kilogram of thechicken feedx 2 = the amoun t of Ingredien t 2 mixed in 1 kilogram of the chicken feedx 3 = the amoun t of Ingredien t 3 mixed in 1 kilogram of the chicken feedThe LP model is:1231231231231231231230.550.420.382545323511107811107102351601902001,,0Min Z x x x Subject tox x x x x x x x x x x x x x x x x x =++++≥++≥++≤++≥++=≥2.Let x1 = number of clerks start working on Mondayx2 =number of clerks start working on Wednesday x3 =number of clerks start working on Friday The LP model is:12313131212123232312320161316191412,,0Min Z x x x Subject tox x x x x x x x x x x x x x x x x x =+++≥+≥+≥+≥++≥+≥+≥≥3. (a)(b) The t w o alternativ e optimal extreme points are (4, 3) and (6,3/2 ). (c) The infinite set of optimal solutions: {λ(4, 3) + (1 − λ)(6,3/2) : 0 ≤ λ ≤ 14. Model:123123111123max 363025.. 360 5020050150 50150 ,,0z x x x s t x x x x x x x x x =++++=≤≤≤≤≤≤≥Solution:x 1=60(MW); x 2=150(MW); x 3=150(MW)5. According to the figure, the solution is: x 1=0; x 2=0Chapter 3 Simplex1. Show that if ties are broken in favor of lower-numbered rows, then cyclingoccurs when the simplex method is used to solve the following LP: 123123412341234369920/32/3099210(1,2,3,4)i Max Z x x x Subject tox x x x x x x x x x x x x i =-+-+--≤+--≤--++≤≥= 2. Use the simplex algorithm to find two optimal solutions to the following LP:123123123123max 53.. 36 53615 ,,0z x x x s t x x x x x x x x x =++++≤++≤≥3. Use the Big M method to find the optimal solution to the following LP:1212121212max 5.. 26 4 25 ,0z x x s t x x x x x x x x =-+=+≤+≤≥4. Use the simplex algorithm to find two optimal solutions to the following LP .123123123123max 53.. 3653615 ,,0z x x x s t x x x x x x x x x =++++≤++≤≥5. For a linear programming problem:1212121234241232850(1,2)i Max Z x x Subject tox x x x x x x i =++≤+≤+≤≥= Find the optimal solution using the simplex algorithm.Solution:1.Here are the pivots:BV={S1,S2,S3}.BV={X2,S2,S3}.We now enter X3 into the basis in Row 2.BV={X2,X3,S3}.We now enter X4 into the basis in Row 1.BV={X4,X3,S3}.X1 now enters basis in Row 2.BV={X4,X1,S3}.We now choose to enter S1 in Row 1.BV={S1,X1,S3}.S2 would now enter basis in Row 2. This will bring us back to the initial tableau, so cycling has occurred. 2. Standard form:1231231123212312max 53.. 36 53615 ,,,,0z x x x s t x x x s x x x s x x x s s =+++++=+++=≥Tableau:So: z=15; x 1=3 ; x 2=0;x 3=03. Standard form:12121211221212max 5.. 26 4 25 ,,,0z x x s t x x x x s x x s x x s s =-+=++=++=≥=>12112112112212121max 5.. 26 4 25 ,,,,0z x x a M s t x x a x x s x x s x x s s a =--++=++=++=≥ Tableau: => => So, the solution is z=15, x 1=3, x 2=04. Standard form:1231231123212312max 53.. 36 53615 ,,,,0z x x x s t x x x s x x x s x x x s s =+++++=+++=≥So, the solution is z=15,x 1=0,x 2=5 or z=15,x 1=3,x 2=0 5. Optimal solution:Chapter 4 Sensitivity Analysis and duality1. Consider the following linear program (LP):1212232420(1,2)i Max Z x x Subject tox x x x i =++≤≤≥=(a). De termin e the shadow price for b 2, the right-hand side of the constrai n t x 2 ≤ b 2. (b). De t e rmin e th e allowable r ange to s tay optimal for c 1, the co e ffic i e n t of x 1 in theob jec tiv e function Z = c 1x 1 + 3x 2.(c). De termin e the allowable range to stay feasible for b 1, th e right-hand side of theconstrai n t 2x 1 + x 2 ≤ b 1.2. There is a LP model as following,1212121234524123280(1,2)i Max Z x x Subject tox x x x x x x i =++≤+≤+≤≥= The optimal simplex tableau is1） Give the dual problem of the primal problem.2） If C2 increases from 4 to 5, will the optimal solution change? Why? 3） If b2 changes from 12 to 15, will the optimal solution change? Why? 3. There is a LP model as following12312312312236222333280(1,2)j Min Z x x x Subject tox x x x x x x x x j =++++≥-++≤-+≤≥= 1) give its dual problem.2) Use the graphical solution to solve the dual problem.4. You have a constraint that limits the amount of labor available to 40 hours perweek. If your shadow price is $10/hour for the labor constraint, and the market price for the labor is $11/hour. Should you pay to obtain additional labor? 5. Consider the following LP model of a production plan of tables and chairs:Max 3T + 2C (profit) Subject to the constraints:2T + C ≤100 (carpentry hrs) T + C ≤80 (painting hrs)T ≤ 40T, C ≥ 0 (non-negativity)1) Draw the feasible region. 2) Find the optimal solution.3)Does the optimal solution change if the profit contribution for tables changed from $3 to $4 per table?4) What if painting hours available changed from 80 to 100?6. For a linear programming problem:11221212121234524123280(1,2)i Max Z c x c x x x Subject tox x x x x x x i =+=++≤+≤+≤≥=Suppose C2 rising from 4 to 5, if the optimal solution will change? Explain the reason. 7. For a linear programming problem:112212121221234524123280(1,2)i Max Z c x c x x x Subject tox x x x b x x x i =+=++≤+≤=+≤≥=Suppose b2 rising from 12 to 15, if the optimal solution will change? Explain thereason.8. For a linear programming problem:112212121221234524123280(1,2)i Max Z c x c x x x Subject tox x x x b x x x i =+=++≤+≤=+≤≥=Calculate the shadow price of all of the three constraints. 9.1) Use the simplex algorithm to find the optimal solution to the model below(10 points)1212125231250(1,2)i Max Z x x Subject tox x x x x i =++≤+≤≥=2) For which objective function coefficient value ranges of x 1 and x 2 does thesolution remain optimal? (10 points) 3) Find the dual of the model; (5 points)4) Find the shadow prices of constraints. (5 points)5) If x1 and x2 are all integers, using the branch-and-bound to solve it.( 15points)10. A factory is going to produce Products I, II and III by using raw materials A and B.1) Please arrange production plan to make the profit maximization. (15) 2) Write the dual problem of the primal problem. (5)3) If one more kg of raw material A is available, how much the total profit will be increased? (5) 4) If the profit of product II changes from 1 to 2，will the optimal solution change? (5)Solution ：1.(a) T h e shadow pr ic e for b 2 is 2.5. Replace th e constrai n t x 2 ≤ 2 by the constrain t x 2 ≤ 3.The new optimal solution is (x 1, x 2) = (0.5, 3) with Z = 9.5. Thus, a unit increas e in b 2 leads t o a 2.5 unit increase in Z .(b) The all o wabl e range to s tay optimal i s 0 ≤ c 1 ≤ 6. The ob j e ctiv e fun c t ion Z =c 1x 1 + 3x 2 is p arall e l to th e c on s tr ain t boundary equation 2x 1 + x 2 = 4 when c 1 = 6. The ob j e ctiv e function Z = c 1x 1 + 3x 2 is parallel to t he c on s tr ain t boundary equation x 2 = 2 wh e n c 1 = 0.(c) T h e allowable range to stay feasible is 2 ≤ b 1 < ∞. The righ t -h and sideb 1 can b e decreased un t il thec on s tr ain t boundary e qu ation 2x 1 + x 2 = 4 intersects th e solution (x 1, x 2) = (0, 2). This occurs when b 1 = 2. T h e right-hand side b 1 can b e in c r e ase d w i thou t i nte r s ec t ing a s olu tion .2.1) the dual problem:123123123125128..233424,0Min w y y y S ty y y y y y y y =++++≥++≥≥2) when C2 changes from 4 to 5, the optimal basic variable will not change, because the coefficient of the nonbasic variable remain positive.3) when b2 changes from 12 to 15, the optimal basic variable will not change. 3.1） the dual problem of the primal problem is ：121212121223..222336,0Max w y y S ty y y y y y y y =--≤+≤+≤≥ 2） using the graphical solution, the optimal solution of the dual problem is: w= 19/5, y1=8/5, y2=-1/5.4. No. If you obtain one additional labor, you should pay $11. But by the shadowprice, you can only earn $10. So we should not pay to obtain additional labor. 5.2) The optimal solution is T=20, C=60 and the maximum profit is 180.3) If the profit contribution for tables changed from $3 to $4 per table, therewill be two optimal solutions, says T=20, C=60 and T=40, C=20, and the maximum profit is 200.4) Because painting hrs is a constraint condition for T=20, C=60, so theoptimal solution will change. The new optimal solution is T=0, C=100, and the maximum profit is 200.6. Parameter is calculated below:1212311211[,,][,][0,4,3][0,0]11104202311/81/403/81/401/41/2111240320001001BV NBV s j BV NBVBV s x x NBV s s C C B B a a a N c c B N c --====⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦--⎡⎤⎢⎥=-⎢⎥⎢⎥-⎣⎦⎡⎤⎡⎤⎡⎤⎢⎥⎢⎥⎢⎥===⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎢⎥⎣⎦⎣⎦⎣⎦⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦=-If c2 rising from 4 to 5, then ，and >0，so the optimal solution will not change.7. If b2 rising from 12 to 15, every element of =[9/8,29/8,1/4] is large thenzero,so the optimal solution will not change. 8. Shadow price is calculated by 。

运筹学A卷）一、单项选择题（从下列各题四个备选答案中选出一个正确答案，答案选错或未选者，该题不得分。

每小题1分，共10分）1．线性规划具有唯一最优解是指A．最优表中存在常数项为零B．最优表中非基变量检验数全部非零C．最优表中存在非基变量的检验数为零D．可行解集合有界2．设线性规划的约束条件为则基本可行解为A．(0, 0, 4, 3) B．(3, 4, 0, 0)C．(2, 0, 1, 0) D．(3, 0, 4, 0)3．则A．无可行解B．有唯一最优解mednC．有多重最优解D．有无界解4．互为对偶的两个线性规划, 对任意可行解X 和Y，存在关系A．Z > W B．Z = WC．Z≥W D．Z≤W5．有6 个产地4个销地的平衡运输问题模型具有特征A．有10个变量24个约束B．有24个变量10个约束C．有24个变量9个约束D．有9个基变量10个非基变量A．标准型的目标函数是求最大值B．标准型的目标函数是求最小值C．标准型的常数项非正D．标准型的变量一定要非负7. m+n－1个变量构成一组基变量的充要条件是A．m+n－1个变量恰好构成一个闭回路B．m+n－1个变量不包含任何闭回路C．m+n－1个变量中部分变量构成一个闭回路D．m+n－1个变量对应的系数列向量线性相关8．互为对偶的两个线性规划问题的解存在关系A．原问题无可行解，对偶问题也无可行解B．对偶问题有可行解，原问题可能无可行解C．若最优解存在，则最优解相同D．一个问题无可行解，则另一个问题具有无界解9.有m个产地n个销地的平衡运输问题模型具有特征A．有mn个变量m+n个约束…m+n-1个基变量B．有m+n个变量mn个约束C．有mn个变量m+n－1约束D．有m+n－1个基变量，mn－m－n－1个非基变量10．要求不超过第一目标值、恰好完成第二目标值，目标函数是A．)(m in22211+-+++=ddpdpZB．)(m in22211+-+-+=ddpdpZC．)(m in22211+---+=ddpdpZD．)(m in22211+--++=ddpdpZ二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”。

2012年东北大学管理运筹学考研试题（回忆版）
一简答40分
1线性规划单纯形法的依据是什么?15分
2.什么是效用函数?10分
3.效用函数具有什么性质?15分
二证明30分
给了一道求最大的线性规划（两个变量，三个约束，都是〈约束，x1，2>=0）
1写出该问题的对偶问题10分
2.运用对偶理论证明该线性规划问题和其对偶问题均有最优解20分
三80分
1. 一道5x5的指派问题很简单
2.一道3x4的产销平衡运输问题（直接用伏格尔法就能给出最优解，相当简单）
3.对策∶甲乙各有三枚硬币1角5角10角（1元），加以分别出一个硬币，不让对方知道，如果两人的硬币和为奇数则甲赢得乙所出的硬币，如果和为偶数，则甲输掉自己所出的硬币。

建立该对策模型，并求解，判断该游戏对甲乙是否公平?。

《运筹学》试卷一一、（15分）用图解法求解下列线性规划问题二、（20分）下表为某求极大值线性规划问题的初始单纯形表及迭代后的表，、为松弛变量，试求表中到的值及各变量下标到的值。

-1311611 -2 002 -111/21/214 07三、（15分）用图解法求解矩阵对策，其中四、（20分）（1）某项工程由8个工序组成，各工序之间的关系为工序 a b c d e f g h —— a a b,c b,c,d b,c,d e 紧前工序试画出该工程的网络图。

（2）试计算下面工程网络图中各事项发生的最早、最迟时间及关键线路（箭线下的数字是完成该工序的所需时间，单位：天）五、（15分）已知线性规划问题其对偶问题最优解为，试根据对偶理论求原问题的最优解。

六、（15分）用动态规划法求解下面问题：七、（30分）已知线性规划问题用单纯形法求得最优单纯形表如下，试分析在下列各种条件单独变化的情况下，最优解将如何变化。

2-11 02311311111610-3-1-2（1）目标函数变为；（2）约束条件右端项由变为；（3）增加一个新的约束：八、（20分）某地区有A、B、C三个化肥厂向甲、乙、丙、丁四个销地供应同一种化肥，已知产地产量、销地需求量和各产地运往不同销地单位运价如下表，试用最小元素法确定初始调运方案，并调整求最优运输方案销地甲乙丙丁产量产地A 4 12 4 11 16B 2 10 3 9 10C 8 5 11 6 22 需求量8 14 12 14 48《运筹学》试卷二一、（20分）已知线性规划问题：（a）写出其对偶问题；（b）用图解法求对偶问题的解；（c）利用（b）的结果及对偶性质求原问题的解。

二、（20分）已知运输表如下：销地B1B2B3B4供应量产地A1 3 2 7 6 50A2 7 5 2 3 60A3 2 5 4 5 25需求量60 40 20 15（1）用最小元素法确定初始调运方案；（2）确定最优运输方案及最低运费。

2016年东北大学852运筹学考研真题（回忆版）
一、简答题
1．影子价格与市场价格的区别，影子价格的意义。

2．对偶单纯形法的步骤。

3．表上作业法的步骤。

4．什么是隐枚举法，骤枝定界法和割平面法是隐枚举法吗？
5．确定型，风险型，不确定型决策的共同点和不同点。

二、计算题
1．单纯形法解线性规划，还有灵敏度分析，忘了几小问了（应该是5到6个），最后一问是如果加上整数条件，写出割平面的方程
2．用对偶问题的性质确定原问题Z≤1，这个以前真题好像考过
3．建模，n个车间生产m种产品，每个车间的生产工时和每种产品的最大销量都有限制，给出了每种产品的价格，最后好像是只要两个车间，三种产品（m和n我不记得具体
是几了，反正不超过5）
4．甲有两个红球一个白球，随便藏起一个，甲可以声称自己手里有两个红球或者一红一白，如果甲声称的正确而乙同意，则甲得10分，如果甲有两红球声称一白一红而乙同意，则甲得20分，如果甲有一红一白声称两红球而乙同意，则甲扣20分。

如果乙提出异议，则上面的得分情况反过来而且加倍
（1）求出甲和乙的纯策略
（2）求出甲的赢得矩阵
5．动态规划，要求解，5年的期限，高负荷生产和低负荷生产带来的效益不同，对机器的损坏也不同，这个题书上有例题
（有些地方数字可能记不清了）。

2017年东北大学工商管理学院851经济学考研真题（回忆版）一、名词解释（每题3分，共30分）1．供求定理2．需求收入弹性3．边际技术替代率4．阿罗不可能性定理5．洛伦兹曲线6．生产函数7．无差异曲线8．纳什均衡9．投资乘数10．流动偏好陷阱二、选择题（每题2分，共30分）单选加多选，考察概念问题，比较简单。

三、简答题（每题5分，共25分）1．影响供给的因素。

2．完全竞争的条件。

3．古诺模型的前提。

4．用收入法和支出法分别核算GDP。

5．通货膨胀的经济效应有哪些？四、论述题（每题15分，共45分）1．垄断竞争条件并举例说明。

2．IS-LM交点是否为充分就业的国民收入？3．推导LAC曲线。

五、计算题（每题10分，共20分）计算题在高鸿业教材课后习题上有类似的题目。

1．考点：均衡收入，投资乘数，政府购买乘数，税收乘数，转移支付乘数，均衡乘数。

2．考点：TP L，AP L，MP L。

2017年东北大学工商管理学院851经济学考研真题（回忆版）及详解一、名词解释（每题3分，共30分）1．供求定理答：供求定理是指任何一种商品价格的调整都会使该商品的供给和需求达到平衡。

在其他条件不变的情况下，需求变动分别引起均衡价格和均衡数量的同方向变动；供给变动引起均衡价格的反方向的变动，引起均衡数量的同方向的变动。

具体情况如下：①如果供给不变需求增加使需求曲线向右上方移动，均衡价格上升，均衡数量增加；需求减少使需求曲线向左下方移动，均衡价格下降，均衡数量减少。

②如果需求不变供给增加使供给曲线向右下方移动，均衡价格下降，均衡数量增加；供给减少使供给曲线向左上方移动，均衡价格上升，均衡数量减少。

2．需求收入弹性答：需求收入弹性表示在一定时期内消费者对某种商品的需求量的变动对于消费者收入量变动的反应程度。

或者说，表示在一定时期内当消费者的收入变化百分之一时所引起的商品需求量变化的百分比。

如果用e M表示需求收入弹性系数，用M和ΔM分别表示收入和收入的变动量，Q和ΔQ表示需求量和需求量的变动量，则需求收入弹性公式为：e M＝（ΔQ/ΔM）·（M/Q）。

2006年东北大学运筹学考研真题（运筹学部分）2007年东北大学运筹学考研真题（运筹学部分）2008年东北大学运筹学考研真题（运筹学部分）2009年东北大学运筹学考研真题（运筹学部分）2010年东北大学运筹学考研真题（运筹学部分）2011年东北大学运筹学考研真题（运筹学部分）2012年东北大学848运筹学考研真题2013年东北大学852运筹学考研真题一、简答题（8道，每个5分）1．动态规划的原理，方法2．表上作业法的实质步骤3．对偶问题的优缺点4．大M法的依据5．分支定界法的原理6．线性规划模型的要素（反正就是决策变量约束条件目标函数这三个）7．双人对策什么时候有最优纯策略（这个记不清了，有两个简答都是有关对策的，压根没背过）8．混合策略有解的条件（估计就是书上那章的小定理，就一两句话就考简答，一个五分）二、计算题（6道）1．第一题：对偶问题（1）写出对偶问题（2）用对偶性质给出对偶问题最优解（3）解释对偶问题经济意义2．第二题：指派问题（这道题跟13年的一样，鬼知道有几个答案，N个指派方案，我只写了一个）3．第三题：线性规划问题（1）求B-1一个检验数；（2）略（3）当参数＝3时最优解4．运输问题（产大于销）5．生产计划问题（动态规划那章的，只建模不求解）6．对策问题，给一个矩阵（1）判断有没有最优策略（2）求解（但是有说个用什么东西，不记得了，没听过，我就用的常规解法，求两个不等式组）只想说今年的题真的很坑。

感觉今年的题真的有点偏了，比往年真心难，往年真题也没感觉这么变态。

一、简答题（5道）1．全情报价值法概念和意义2．静态规划动态规划的区别，动态规划基本思想3．矩阵对策有解的条件，解的性质4．效用的涵义，什么情况下用最大效用值？5．闭回路法确定最优解的思想二、计算题（6道）1．效率矩阵的线性规划解法2．运输建模3．动态规划的设备更新4．分支定界法5．灵敏度分析6．运输求解一、简答题1．影子价格与市场价格的区别，影子价格的意义。