《运筹学 2》课程试题(A卷)

运筹学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二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”。

g 10 02运筹学II 练习题1 试判定下述非线性规划是否为凸规划:(1)Min f X x/ x 22 8x ,2 x 2 02X i x 2 2 0X ! ,x 2 0 Min f Xc 22 22x-| x 2 x 3 x-|X 2 22X 1 X 245x 12 X 3 10X 1 , X 2 , X 3 0(2)(3) C max f (X) x , x 2St 2 2x ,x 2 < 1x 1f x 2 > 02 2Min f Xx 1 x 2 8”g 1 X x 1x 2 0 解(1)11 22g 2 Xx 1 x 2 2 0X 1 , X 2 0f X ,g 1 X ,g 2 X 的海赛矩阵的行列式:H x x-i2f X2f X2 0 0 22 0 X22g 2 XT~ X2g 2 XX 2 X 1g 2 2g 2 X X 1 X 2 2g 2 X2 Xg i X ,为凸函数, 知f X 为严格凸函数, g 2 X 为凹函数，所以不是一个凸规划问题。

(2) Min fg i X 2 X 1 5X 122%2 2 X 2 2 X22 X3g 12 X2g 2 X X 1,X 2,X 3 0X 310同上有 ，g i，g 2的海赛矩阵的行列式是凸函数，不是 g i min (X i 凸规划问题。

(3) f(X))说明 s.t g 1(X) g 2(X)g 3(X)f(X) g 2(X)2 X 1X 1 X 2》f （X ）是凸函数,> 0,H g 3（X）g 1（X ）、2试用斐波那契法求函数2f X X 3X 2g(X)0 2>0,g 2（X ） > g 3（X ）是凹函数。

因此,本模型是一个凸规划。

在区间［0 , 10］上的极小点，要求缩短后的区间长度不大于原区间长度的8%。

(1.5 )420216H X0 4Fn 1/ 12.5,n 6; a0 0,b0 10; t1 b0 F5(b0 a0) 3.846; F6 t1' a0F5(b0 a0)6.154;F6f(t1) 5.254;f(t1') 21.409;11f(t1) f(t1')「al 0;b1 6.154;t2' 3.846;t2 b1 F4(b1 a1) 2.308;F511 f(t2) 0.403;f (t2) f(t2') 5.254冷 a2 0; b2 3.846;t3' 2.308;t3 b2 F3(b2 a2) 1.538;F4* i f(t3) 0.248 f (t3') 0.403料 a3 0;b3 2.308;t4' 1.538; t4 b3F2(b3 a3) 0.769;F311 f(t4) 0.284 f (t4') 0.248^ a4 0.769;b4 2.308;t5 1.538;F1t5' a4 (b4 a4) 1.538F22t t 2在区间［1,3］上的近似极小点，要求缩短后的区向长度不大于原区间长的 8%。

学年度第一学期期末考试《运筹学》（八）卷专业班级姓名学号一、单选题（每题的备选答案中只有一个最佳答案，每题2分，共30分）I、运筹学的主要内容包括：（）A.线性规划B.非线性规划C.存贮论D.以上都是2、下面是运筹学的实践案例的是：（）A.丁谓修守B.田忌赛马C.二战间，英国雷达站与防空系统的协调配合D.以上都是3、规划论的内容不包括：（）A.线性规划B.非线性规划C.动态规划D.网络分析4、关于运筹学的原意，卜冽说法不正确的是：Λ.作业研究B.运作管理C.作战研究D.操作研究5,运筹学模型：A.在任何条件下均有效B.只有符合模型的简化条件时才有效C.可以解答管理部门提出的任何问题D.是定性决策的主要工具6、最早运用运筹学理论的是：Λ.二次世界大战期间，英国军事部门将运筹学运用到军事战略部署B.美国最早将运筹学运用到农业和人口规划问逸上C.二次世界大战后，英国政府将运筹学运用到政府制定计划D.50年代,运筹学运用到研究人口，能源,粮食，第三世界经济发展等问题上7、下列哪些不是运筹学的研究范用：A.库存控制B.动态规划C.排队论D.系统设计8、对运筹学模型的下列说法，正确的是：A.在任何条件下均有效B.只有符合模型的简化条件时才有效C.可以解答管理部门提出的任何问题D.是定性决策的主要工具9、线性规划具有多重最优解是指（）A.目标函数系数与某约束系数对应成比例B.最优表中存在非基变量的检验数为零C.可行解集合无界D.基变量全部大丁•零10.图解法通常用于求解有（）个变量的线性规划问题。

A.1B.2C.4D.5Ik以下不属于运筹学求解目标的是：A.最优解B.次优解C.满意解D.劣解12、线性规划问返的最优解（）为可行解。

A.一定B.不一定C.一定不D.无法判断13、将线性规划问感转化为标准形式时,下列说法不正确的是:A.如为求Z的最小值，需转化为求-Z的垠大值B.如约束条件为W,则要增加一个松驰变量C.如约束条件为2,则要减去一个剩余变量D.如约束条件为=,则要增加一个人工变易14、关于图解法，下列结论最正确的是：A.线性规划的可行域为凸集。

第七章决策论1. 某厂有一新产品，其面临的市场状况有三种情况，可供其选择的营销策略也是 三种，每一钟策略在每一种状态下的损益值如下表所示，要求分别用非确定型 决策的五种方法进行决策（使用折衷法时a = 0.6）。

悲观法：根据“小中取大”原则，应选取的经营策略为 乐观法：根据“大中取大”原则，应选取的经营策略为 折中法（a =0.6）:计算折中收益值如下：51 折中收益值=0.6x50+0.4x （-5）=28 52 折中收益值=0.6x30+0.4x0=18 S3 折中收益值=0.6x10+0.4x10=10 显然，应选取经营策略s1为决策方案。

平均法：计算平均收益如下：S3: 故选择策略s1,s2为决策方案。

'最小遗憾法：分三步 第一，定各种自然状态下的最大收益值，如方括号中所示;第二，确定每一方案在不同状态下的最小遗憾值， 并找出每一方案的最大 遗憾值如S1: x i = (50+10-5) /3=55/3 S2:X2=(30+25)/3=55/3(4)s3; s1X 3=(1O+1O)/3=1O(5)】(1) (2)圆括号中所示；第三，大中取小，进行决策。

故选取S1作为决策方案。

经营 策略市场状况Q1Q2 Q3 S1 0 (15)15S2 （20） 0 10 S3（40）152•如上题中三种状态的概率分别为：0.3,0.4, 0.3,试用期望值方法和决策树方法决策。

（1）用期望值方法决策：计算各经营策略下的期望收益值如下：CSi ） =£尸住 i ）XH 二1匸53-13〔S3) =2 FC^i)X3i = 10j-1故选取决策S 2时目标收益最大。

（2）用决策树方法，画决策树如下：尸（內）=0. 4 八十）=0- 317.531抉策19 /—f …—30of 尸®曲4 △圧佥八、尸(内)二0・3 灵0 ——— 1010 尸(内)二0・3 P(&1)二Q ・3 P (i j l e i ) 构造差（11）构造一般（12）构造好（l 3）无油（e 1） 0.6 0.3 0.1 贫油（e 2）0.30.4 0.3 富油（e 3）0.10.40.5假定勘探费用为1万元，试确定:3.某石油公司拟在某地钻井，可能的结果有三：无油 （e 1）,贫油（e 2）和富油（e3）, 估计可能的概率为：P （e 1）=0.5, P （e 2）=O .3, P （e 3）=0.2。

D、分支定界法在处理整数规划问题时，借用线性规划单纯形法的基本思想，在求相应的线性模型解的同时，逐步加入对各变量的整数要求限制，从而把原整数规划问题通过分支迭代求出最优解。

7、下列变量组是一个闭回路的有（）A、{x21,x11,x12,x32,x33,x23}B、{ x11,x12,x23,x34,x41,x13}C、{x21,x13,x34,x41,x12,x14}D、{ x12,x22,x32,x33,x23,x21}8、工序（i,j）的最早开工时间T ES（i,j）等于（）A、T E（i）B、max{ T Es（k）+ t ki }C、T L（i）D、min{ T L（j）- t ij }9、对于不确定型的决策，某人采用悲观主义准则进行决策，则应在收益表中（）A、大中取小B、大中取大C、小中取小D、小中取大10、以下哪项是决策结果的方法程序（）A、收集信息-确定目标-提出方案-方案优化-决策B、确定目标-收集信息-决策-提出方案-优化方案C、确定目标-收集信息-提出方案-方案优化-决策D、确定目标-提出方案-收集信息-方案优化-决策单项选择题答题表二、判断题，正确打√，错误打×, 并将修改建议简写在对应题号下的改错栏。

（20分，每题2分）1、线性规划问题的每一个基可行解对应可行域的一个顶点。

（√）2、图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

（√）3、线性规划模型中增加一个约束条件，可行区域的范围一般将缩小，减少一个约束条件，可行域的范围一般将扩大。

（√）4、紧前工序是前道工序，后序工序是紧后工序。

( )5、在折衷主义准则中，乐观系数α的确定与决策者对风险的偏好有关。

( )6、旅行售货员问题是遍历每一条边的问题。

( )7、按最小元素法给出的初始基可行解，从每一空格出发可以找出而且仅能找出唯一的闭回路。

（√）8、在目标规划模型中，正偏差变量应取正值，负偏差变量应取负值。

运筹学试题(代码：8054)一、填空题(本大题共8小题，每空2分，共20分)1．线性规划闯题中，如果在约束条件中出现等式约束，我们通常用增加___的方法来产生初始可行基。

2．线性规划模型有三种参数，其名称分别为价值系数、___和___。

3．原问题的第1个约束方程是“=”型，则对偶问题相应的变量是___变量。

4．求最小生成树问题，常用的方法有：避圈法和 ___。

5．排队模型M／M／2中的M，M，2分别表示到达时间为___分布，服务时间服从负指数分布和服务台数为2。

6．如果有两个以上的决策自然条件，但决策人无法估计各自然状态出现的概率，那么这种决策类型称为____型决策。

7．在风险型决策问题中，我们一般采用___来反映每个人对待风险的态度。

8．目标规划总是求目标函数的___信，且目标函数中没有线性规划中的价值系数，而是在各偏差变量前加上级别不同的____。

二、单项选择题(本大题共l0小题，每小题3分，共30分)在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。

多选无分。

9．使用人工变量法求解极大化线性规划问题时，当所有的检验数在基变量中仍含有非零的人工变量，表明该线性规划问题【】A．有唯一的最优解 B．有无穷多最优解C．为无界解 D．无可行解10．对偶单纯形法解最大化线性规划问题时，每次迭代要求单纯形表中【】A．b列元素不小于零 B．检验数都大于零C．检验数都不小于零 D．检验数都不大于零11．已知某个含10个结点的树图，其中9个结点的次为1，1，3，1，1，1，3，1，3，则另一个结点的次为【】A．3 B．2C．1 D．以上三种情况均有可能12．如果要使目标规划实际实现值不超过目标值。

则相应的偏离变量应满足【】13．在运输方案中出现退化现象，是指数字格的数目【】A．等于 m+n B．等于m+n-1C．小于m+n-1 D．大于m+n-114．关于矩阵对策，下列说法错误的是【】A．矩阵对策的解可以不是唯一的C．矩阵对策中，当局势达到均衡时，任何一方单方面改变自己的策略，都将意味着自己更少的赢得和更大的损失D．矩阵对策的对策值，相当于进行若干次对策后，局中人I的平均赢得或局中人Ⅱ的平均损失值【】A．2 8．—l C．—3 D．116．关于线性规划的原问题和对偶问题，下列说法正确的是【】A．若原问题为元界解，则对偶问题也为无界解B．若原问题无可行解，其对偶问题具有无界解或无可行解c．若原问题存在可行解，其对偶问题必存在可行解D．若原问题存在可行解，其对偶问题无可行解17．下列叙述不属于解决风险决策问题的基本原则的是【】A．最大可能原则 B．渴望水平原则C．最大最小原则 D．期望值最大原则18．下列说法正确的是【】A．线性规划问题的基本解对应可行域的顶点也必是该问题的可行解D．单纯形法解标准的线性规划问题时，按最小比值原则确定换出基变量是为了保证迭代计算后的解仍为基本可行解三、多项选择题(本大题共5小题，每小题2分，共l0分)在每小题列出的四个备选项中至少有两个是符合题目要求的，请将其代码填写在题后的括号内。

重庆邮电大学2011-2012学年二学期运筹学期末考试试卷(A卷)班级:___________学号:___________姓名:___________得分:___________题目部分，(卷面共有10题,100.0分,各大题标有题量和总分)一、计算解答(10小题,共100.0分)[1]用对偶单纯形法求解下列线性规划问题[2]写出下列线性规划的对偶问题[3]试用对偶理论讨论下列原问题与它们的对偶问题是否有最优解[4]考虑如下线性规划其最优单纯形表示于下表。

最优单纯形表(1) 由，求新的最优解。

(2) 由，求新的最优解。

(3) 由，是否影响最优解？若有影响，求新的最优解。

(4) 由，回答与(3)相同的问题。

(5)增加变量对最优解是否有影响？(6)增加一个约束条件，求新的最优解。

[5]已知某工厂计划生产三种产品，各产品需要在甲、乙、丙设备上加工。

有关数据如下表。

生产，，三种产品的有关数据试问：如何充分发挥设备能力，使工厂获利最大？(2)若为了增加产量，可借用别的工厂的设备甲，每月可借用60台时，租金1.8万元，问是否合算？(3)若别有2种新产品、，其中每件需用设备甲12台时，设备乙5台时、设备丙10台时，每件获利2.1千元；每件需用设备甲4台时，设备乙4台时、设备丙12台时，每件获利1.87千元。

如、、设备台时不增加，分别回答这2种新产品投产是否合算？(4)增加设备乙的台时是否可使企业总利润进一步增加？[6]写出下列问题的对偶规划[7]写出下列问题的对偶规划[8]某厂利用原料A、B生产甲、乙、丙三种产品，已知生产单位产品所需原料数、单件利润及有关数据如下表所示，分别回答下列问题：(1)建立线性规划模型，求该厂获利最大的生产计划。

(2)若产品乙、丙的单件利润不变，产品甲的利润在什么范围变化，上述最优解不变？(3)若有一种新产品丁，其原料消耗定额：A为3单位，B为2单位，单件利润为2.5单位。

问该种产品是否值得安排生产，并求新的最优计划。

运筹学试题二
一、用单纯形法求解下述线性规划问题（20分）
⎧⎨⎪⎪⎩
⎪⎪0
,824424m ax 2121212121≥≤-≤-≤+-+=x x x x x x x x x x z
二、设一线性规划问题为（25分）
234
700件，且在第二、三周能加班生产。

加班后，每周可增产200件产品，但成本每件增加5元。

产品如不能在本周交货，则每件每周存贮费是3元。

问如何安排生产计划，使总成本最小，要求建立运输问题数学模型求解。

（25分）
四、某高校拟开设文学、艺术、音乐、美术四个学术讲座。

每个讲座每周下午举行一次。

经调查知，每周星期一至星期五不能出席某一讲座的学生数如下表：（20分）
座的学生总数。

试题二答案
()0
1310232>=⎪⎪⎭⎫
⎝⎛-=r
6
*=Z
（3） 最优解不满足新增加的约束条件2231≥+-x x ∴最优解要发生改变 将约束条件改写为 22631-=+-x x x
加入最优表中继续迭代。

《运筹学》试题及答案19、简述线性规划模型主要参数（p11）（1）、价值系数：目标函数中决策变量前的系数为价值系数（2）、技术系数：约束条件中决策变量前的系数（3）、约束条件右边常数项15、简述线性规划解几种可能的结果（情形）（ppt第二章39或89页）（1）.有唯一最优解 (单纯形法中在求最大目标函数的问题时，对于某个基本可行解，所有δj≤0)（2）.无可行解，即可行域为空域，不存在满足约束条件的解，也就不存在最优解了。

（3）.无界解，即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小，一般来说，这说明模型有错，忽略了一些必要的约束条件（4）.无穷多个最优解，则线段上的所有点都代表了最优解（5）退化问题，基变量有时存在两个以上相同的最小比值，这样在下一次迭代中就有一个或几个基变量等于零，用图解法无退化解1、简述单纯形法的基本思路（p70）从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。

直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。

17、简述线性规划中添加人工变量的前提（p85）在系数矩阵中直接找不到初始可行解，进而通过添加人工变量的方法来构造初始可行基，得出初始基本可行解10、简述线性规划对偶问题的基本性质（p122）（1）对称性（2）弱对偶性（3）强对偶性（4）最优性（5）互补松弛型原函数与对偶问题的关系1）求目标函数最大值的线性规划问题中有n 个变量 m个约束条件，它的约束条件都是小于等于不等式。

而其对偶则是求目标函数为最小值的线性规划问题，有m个变量n个约束条件，其约束条件都为大于等于不等式。

2）原问题的目标函数中的价值系数为对偶问题中的约束条件的右边常数项，并且原问题的目标函数中的第i个价值系数就等于对偶问题中的第i个约束条件的右边常数项。

3）原问题的约束条件的右边常数项为对偶问题的目标函数中价值系数。

运筹学A卷）一、单项选择题（从下列各题四个备选答案中选岀一个正确答案, 分。

每小题1分，共10分）1 .线性规划具有唯一最优解是指A .最优表中存在常数项为零B •最优表中非基变量检验数全部非零C •最优表中存在非基变量的检验数为零D •可行解集合有界2 •设线性规划的约束条件为则基本可行解为3 min Z = 3工]+4勺，；f] + 工2 > 4,2工1+ 工2 - 2,心花一Q 则A •无可行解B .有唯一最优解 medn 答案选错或未选者，该题不得A . (0, 0, 4, 3) B. (3, 4, 0, 0) C • (2, 0,1,0) D • (3, 0, 4, 0)C .有多重最优解D .有无界解4 .互为对偶的两个线性规划任意可行解X和丫，存在关系C . Z >W5 .有6个产地4个销地的平衡运输问题模型具有特征A .有10个变量24个约束B .有24个变量10个约束C .有24个变量9个约束D .有9个基变量10个非基变量6.下例错误的说法是A.标准型的目标函数是求最大值B .标准型的目标函数是求最小值C .标准型的常数项非正D•标准型的变量一定要非负7. m+n — 1个变量构成一组基变量的充要条件是8 .互为对偶的两个线性规划问题的解存在关系A .原问题无可行解，对偶问题也无可行解B •对偶问题有可行解，原问题可能无可行解C .若最优解存在，则最优解相同D •一个问题无可行解，则另一个问题具有无界解9.有m 个产地n 个销地的平衡运输问题模型具有特征mn 个变量 m+n 个约束 …m+n-1 个基变量m+n — 1 个基变量，mn — m — n — 1 个非基变量10 •要求不超过第一目标值、恰好完成第二目标值，目标函数是m+n — 1 个变量恰好构成一个闭回路m+n — 1 个变量不包含任何闭回路m+n — 1 个变量中部分变量构成一个闭回路m+n — 1 个变量对应的系数列向量线性相关B •有 m+n 个变量 mn 个约束C •有 mn 个变量m+n — 1约束A •有D •有20.对偶问题有可行解，则原问题也有可行解 X15 分)12.凡基本解一定是可行解 X 同1914.可行解集非空时，则在极点上至少有一点达到最优值 15.互为对偶问题，或者同时都有最优解，或者同时都无最优解17.要求不超过目标值的目标函数是 二說+18.求最小值问题的目标函数值是各分枝函数值的下界19.基本解对应的基是可行基 X 当非负时为基本可行解，对应的基叫可行基min ZP i d iP 2 (d 2 d 2)minP 2(d 2d 2)min P i d iP 2(d 2 d 2)minP i d iP 2(d 2 d 2)二、判断题 （你认为下列命题是否正确，对正确的打；错误的打“X”。

运筹学期末考试题（a 卷）注意事项：1、答题前，考生务必将自己的姓名、班级填写在答题卡上。

2、答案用钢笔或圆珠笔写在答题卡上，答在试卷上不给分。

3、考试结束，将试卷和答题卡一并交回。

一、 单项选择题(每小题1分，共10分)1：在下面的数学模型中，属于线性规划模型的为（ ） ⎪⎩⎪⎨⎧≥≤+=0Y ,X 3XY .t .s Y X 4S max .A ⎪⎩⎪⎨⎧≥-≥-+=0Y ,X 1Y X 2.t .s Y X 3S min .B ⎪⎩⎪⎨⎧≥≤-+=0Y ,X 2Y X .t .s Y X S max .C 22 ⎪⎩⎪⎨⎧≥≥+=0Y ,X 3Y X .t .s XY2S min.D 2．线性规划问题若有最优解，则一定可以在可行域的 （ ）上达到。

A ．内点 B ．顶点 C ．外点 D ．几何点 3：在线性规划模型中，没有非负约束的变量称为 （ ）A ．多余变量B ．松弛变量 C.自由变量 D ．人工变量4：若线性规划问题的最优解同时在可行解域的两个顶点处达到，那么该线性规划问题最优解为（ ）A.两个B.零个C.无穷多个D.有限多个 5：原问题与对偶问题的最优（ ）相同。

A ．解B ．目标值C ． 解结构D ．解的分量个数 6：若原问题中i x 为自由变量，那么对偶问题中的第i 个约束一定为 （ ）A ．等式约束B ．“≤”型约束C ．“≥”约束D ．无法确定7：若运输问题已求得最优解，此时所求出的检验数一定是全部（ ） A ．小于或等于零 B ．大于零 C ．小于零 D ．大于或等于零 8：对于m 个发点、n 个收点的运输问题，叙述错误的是( ) A ．该问题的系数矩阵有m ×n 列 B ．该问题的系数矩阵有m+n 行 C ．该问题的系数矩阵的秩必为m+n-1 D ．该问题的最优解必唯一 9：关于动态规划问题的下列命题中错误的是（ ） A 、动态规划分阶段顺序不同，则结果不同 B 、状态对决策有影响C 、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D 、动态规划的求解过程都可以用列表形式实现10：若P 为网络G 的一条流量增广链，则P 中所有正向弧都为G 的（ ） A ．对边 B ．饱和边 C ．邻边 D ．不饱和边 二、 判断题（每小题1分，共10分）1：图解法和单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的。

广东海洋大学2011-2012学年第二学期《运筹学 2》课程试题（A卷）一、判断下列说法是否正确？正确的打“√”错误的打“×”。

（20分）1．线性规划问题如果有最优解，那么最优解是唯一的。

（）2．图中最短路的任何子路径都是最短路。

（）3．企业拥有是某种资源的影子价格高于其他市场价格，则企业应该直接出售该资源。

（）4．在图的某一路径中，如果同一条边不出现两次，则称此路径是简单路径。

（）5．在网络规划中某工序的总时差不依赖于它的紧后工序。

（）6．求解指派问题的匈牙利法不是多项式时间算法。

（）7．线性规划问题的原问题如果没有可行解则对偶问题有无界解。

（）8．一个有向连通图具有欧拉回路，当且仅当它的每个顶点的引入次数等于引出次数。

（）9．树的每一对顶点有唯一的一条基本路径（n≥2）。

（）10．博弈的三要素是指：（1）明确的规则。

（2）策略集中至少两个策略可以选择。

（3）赢得可以被描述。

（）二、 求解下面的线性规划问题（20分）min z = 5x 1 + 21x 3三、 A 、B 、C 、D 、E 无人分别完成G 1G 2G 3G 4各项工作所须的最短时间如下表。

问：如果每人完成一项工作，派哪四个人？如何安排才能使完成全部四项工作的总用时最少？请给出全部最优方案。

（20分）四、 1、计算下面网络规划图中的事项中的最早时间和最迟时间。

2、求出下面网络规划图中的关键路线，并用粗线标出。

3、求工序④⑩的单时差和总时差。

（15分）五、在W城的冰箱市场上，以往的市场份额有本市生产的A牌冰箱占有绝大部分。

本年初，一个全国知名的B牌冰箱进出W城的市场。

在这场竞争中假设双方考虑可采用的市场策略均为三种：广告、降价、完善售后服务，且双方用于营销的资金相同。

根据市场预测，A的市场占有率为：分）六、（背包问题）一个登山队员，需要携带的物品有：食品、氧气、冰镐、绳索、帐篷、照相器材、通信器材等。

每种物品的重量及重要性系数见下表。

《运筹学》(A)参考答案一、不定项选择题(每小题3分，共9分)1.线性规划的标准型有特点(B D )0A、右端项非零；B、目标求最大；C、有等式或不等式约束；D、变量均非负。

2.一个线性规划问题(P)与它的对偶问题(D)有关系(BCD)。

A、(P)无可行解则(D) 一定无可行解；B、(P)、(D)均有可行解则都有最优解；C、(P)的约束均为等式，则(D)的所有变量均无非负限制；D、若(D)是(P)的对偶问题，则(P)是(D)的对偶问题。

3.关于动态规划问题的下列命题中(B )是错误的。

A、动态规划阶段的顺序与求解过程无关；B、状态是由决策确定的；C、用逆序法求解动态规划问题的重要基础之一是最优性原理；D、列表法是求解某些离散变量动态规划问题的有效方法。

二、判断题(每小题2分，共10分)1.若某种资源的影子价格等于Q在其他条件不变的情况下，当该种资源增加5个单位时，相应的目标函数值将增大5k个单位。

(X)2.如果运输问题单位运价表的某一行(或某一列)元素分别加上一个常数久最优调运方案将不会发生变化。

(V)3.运输问题是一种特殊的线性规划模型，因而求解结果也可能出现下列四种情况之一：有唯一最优解，有无穷多最优解,无界解，无可行解。

(X )4.用割平面法求解纯整数规划问题时，要求包括松弛变量在内的全部变量必须取整数值。

（V ）5.如图中某点匕有若干个相邻点，与其距离最远的相邻点为耳，则边卩,刀必不包含在最小支撑树内。

（X）三（20分）、考虑下列线性规划：max z = 3xj + 5x2 + x34xj + 2X2+x3 < 14< X] + x2 + x3 < 4Xj > 0, j = 1,2,31（10分）、写出此线性规划的最优解、最优值、最优基B和它的逆沪；2（2分）、求线性规划的对偶问题的最优解；3（4分）、试求C2在什么范围内，此线性规划的最优解不变；4 （4分）、若^=14变为9,最优解及最优值是什么？解：1（10分）、写出此线性规划的最优解、最优值、最优基B和它的逆沪;标准形式：max z = 3xj + 5x2 + x34xj + 2*2 + X3 + 卩=14< X] + *2 + X3 + x5 = 4X j > 0, j = 1,2,3,4,5最优解 X' =（0,4,0,6,0）『 最优值r =20 ---------------- （1分） 最优基5 = P 2]---------------- （2分）0 1 "1 -2B~l= o ]---------------- （2 分）2（2分）、求线性规划的对偶问题的最优解； 对偶问题的最优解厂=（0,5）3（4分）、试求c?在什么范围内，此线性规划的最优解不变;（1分）（2分）要使得原最优解不变，则所有检验数非正，即 3 — c 2 W 0 <1-C 2 <0 ，解得c 2 >3--------------- （2 分）~C 2 - 04（4分）、若$=14变为9,最优解及最优值是什么？-2j9 1 4最优值r =20-四（10分）、下述线性规划问题：max z = 10“ + 24x 2 + 20x 3 + 2O.r 4 + 25x 5X] + x 2 + 2x, + 3X 4 + 5X 5 < 19 < 2x 1 + 4X 2 + 3x, + 2X 4 + x 5 < 57 ">（2分）（2分）0, j =l,2,---,5以几,力为对偶变量写出其对偶问题。

北京交通大学考试试题答案（A卷）——运筹学A一、单选题5分，每题1分。

二1．设甲、乙产品的产量分别为x1，x2件，线性规划模型为：max z=3x1+2x2s.t. 2x1+4x2≤1603x1+2x2≤180x1 , x2≥0标准型及单纯形计算如下：max z=3x1+2x2s.t. 2x1+4x2+x3=1603x1+2x2+x4=180x1 , x2, x3, x4≥60最优方案为甲生产50件，乙生产15件，或甲生产60件，乙生产0件，或上述两种方式的凸组合。

最大利润为180。

15分，模型5分，标准型与初始表5分，计算3分，结论2分。

2．影子价格分别为0和14分，各2分，计算错误扣1分。

3．产品丙的检验数为－1，不值得生产。

5分，公式2分，计算2分，结论1分。

4．原料B 的灵敏度范围0-240，最多应购买60千克。

6分，公式2分，计算3分，结论1分。

三、（15分）①正确列出运价表如右：7分 ②最小元素法方案3分 ③位势法求检验数4分 ④给出正确的调运方案1分四、（10分）分配甲、乙、丙三个人去完成A 、B 、C 、D 四项任务，每个人完成各项任务的时间如表所示。

其中任务D 必须完成，且每个人只能完成一项任务，每项任务只能由一个人完成。

试确定最优分配方案，使完成任务的总时间最少。

①正确列出效益表如右：5分 ②匈牙利法计算结果3分 ③给出正确的分配方案2分第五题定义状态：s1=x1+s2 s2=x2+s3 s3=x3 故 s1<=8（3分） k=3时f3(s3)=Max {4*x3} ，此时 0<=x3<=s3即x3=s3时f3(s3)=4＊s3（3分）k=2时f2(s2)=Max {3*x2+f3(s3)}= Max {3*x2+4*(s2-x2)} 0<=x2<=s2即x2=0时f2(s2)=4＊s2（3分）k=3时f1(s1)=Max {x1*x1+ f2(s2)}=Max{x1*x1-4*x1+4*s1} ，此时0<=x1<=s1 由于s1<=8，故x1=s1＝8时f1(s1)=64（3分）因此，x1=8, x2=0, x3=0时z取得最大值，最大值为64。

《运筹学》试卷一一、（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）确定最优运输方案及最低运费。

重庆邮电大学2011-2012学年二学期运筹学期末考试试卷(A卷)班级:___________学号:___________姓名:___________得分:___________题目部分，(卷面共有10题,100.0分,各大题标有题量和总分)一、计算解答(10小题,共100.0分)[1]用对偶单纯形法求解下列线性规划问题[2]写出下列线性规划的对偶问题[3]试用对偶理论讨论下列原问题与它们的对偶问题是否有最优解[4]考虑如下线性规划其最优单纯形表示于下表。

最优单纯形表124 10025(1)(2)(3)(4) (3)相同的问题。

(5)(6)[5]有关数据如下表。

生产，，三种产品的有关数据试问：如何充分发挥设备能力，使工厂获利最大？(2)若为了增加产量，可借用别的工厂的设备甲，每月可借用60台时，租金1.8万元，问是否合算？(3)若别有2种新产品、，其中每件需用设备甲12台时，设备乙5台时、设备丙10台时，每件获利2.1千元；每件需用设备甲4台时，设备乙4台时、设备丙12台时，每件获利1.87千元。

如、、设备台时不增加，分别回答这2种新产品投产是否合算？(4)增加设备乙的台时是否可使企业总利润进一步增加？[6]写出下列问题的对偶规划[7]写出下列问题的对偶规划[8]某厂利用原料A、B生产甲、乙、丙三种产品，已知生产单位产品所需原料数、单件利润及有关数据如下表所示，分别回答下列问题：(1)建立线性规划模型，求该厂获利最大的生产计划。

(2)若产品乙、丙的单件利润不变，产品甲的利润在什么范围变化，上述最优解不变？(3)若有一种新产品丁，其原料消耗定额：A为3单位，B为2单位，单件利润为2.5单位。

问该种产品是否值得安排生产，并求新的最优计划。

(4)若原材料A市场紧缺，除拥有量外一时无法购进，而原材料B如数量不足可去市场购买，单价为0.5，问该厂应否购买？以购进多少为宜？(5)由于某种原因该厂决定暂停甲产品的生产，试重新确定该厂的最优生产计划。

练习题（博弈论部分）：1、化简下面的矩阵对策问题：⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎣⎡=2504363432423622415332412A2、列出下列矩阵对策的线性规划表达式⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡------=334133313A3、用线性方程组解 “齐王赛马”的纳什均衡。

解：已知齐王的赢得矩阵为A =⎥⎥⎥⎥⎥⎥⎥⎥⎦⎤⎢⎢⎢⎢⎢⎢⎢⎢⎣⎡------3111111311111131111113111111311111134、已知对策400008060A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦的最优解为：)133,134,136(),134,133,136(**==Y X ，对策值1324*=V ，求以下矩阵对策的最优解和对策值⎥⎥⎥⎦⎤⎢⎢⎢⎣⎡=203820442020202032'A5、设矩阵对策的支付矩阵为：353432323A ⎡⎤⎢⎥=-⎢⎥⎢⎥⎣⎦，求其策略和策略的值。

6、求解下列矩阵对策的解：123312231A ⎡⎤⎢⎥=⎢⎥⎢⎥⎣⎦练习题（多属性决策部分）：试用加权和法分析应扩建那所学校？讨论权重的选择对决策的影响！2、拟选择一款洗衣机，其性能参数（在洗5Kg衣物的消耗）如下表，设各目标的重要性相同，采用折中法选择合适的洗衣机W=3、六方案四目标决策问题的决策矩阵如下表,各目标的属性值越大越好，{0.3,0.2,0.4,0.1}T请用ELECTRE法求解，折中法，加权法求解排队论练习：例1：在某单人理发馆，顾客到达为普阿松流，平均到达间隔为20分钟，理发时间服从负指数分布，平均时间为15分钟。

求：(1)顾客来理发不必等待的概率；(2)理发馆顾客平均数；(3)顾客在理发馆平均逗留时间；(4)如果顾客在店平均逗留时间超过1.25小时，则店主将考虑增加设备及人员。

问平均到达率提高多少时店主才能做这样考虑呢？例2：某机关接待室只有一位对外接待人员，每天工作10小时，来访人员和接待时间都是随机的。

运筹学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二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”。

安徽工程大学2009——2010学年第2学期( 运筹学Ⅱ)课程考试试卷（A ）卷 考试时间120分钟，满分100分要求：闭卷[√]，开卷[ ]；答题纸上答题[√]，卷面上答题[ ] (填入√)一、计算题(共计70分,写明解题过程). 1、（12分）线性规划问题123123123123123max 234 23325362 7 ,,0z x x x x x x x x x x x x x x x =++-+≤⎧⎪+-≤⎪⎨-++≤⎪⎪≥⎩ (1)写出其标准形式，(2)并利用单纯形法求解其最优解与最优值。

2、（12分）已知线性规划问题：1234124122341231234max 243 82 6.. 6 9,,, 0z x x x x x x x x x s t x x x x x x x x x x =+++++≤⎧⎪+≤⎪⎪++≤⎨⎪++≤⎪⎪≥⎩(1)写出对偶问题的形式；(2)原问题的最优解为(2,2,4,0)T X *=，利用互补松弛性求出对偶问题的解.3、（12分）现有线性规划问题12312312123max 26..24,,0z x x x x x x s t x x x x x =-+++≤⎧⎪-+≤⎨⎪≥⎩， 用单纯形法求最优解时，其最优单纯形表下表所示，（1）目标函数变为123max 23z x x x =++试求最优解； (2) 增添一个新的约束2231≥+-x x 试求最优解.5、（12分）某学校要从外地聘请5个英语教师给5个英语程度不同的班级上辅导课，劳动报酬每小时80元，各教师辅导各班级所需小时的预测值见下表。

试在总费用最少的条件下确定各个班级应由哪个教师上课，并算出总费用为多少？6、（10分）某公司有资金10万元，若投资于项目(1,2,3)i i =的投资额为i x 时，其收益分别为)(i i x g 。

其中)(11x g =41x ，)(22x g =92x ，)(33x g =223x ，问应如何分配资金额才能使总收益最大？二、建模题（每小题10分，共计20分，只建模不求解）1、某公司准备投资B 万元建民用住宅。