重庆交通大学2010年运筹学真题

天津师范大学考试试卷Array 2011—2012学年第二学期期末考试试卷（A 卷）科目：运筹学学院：管理学院专业：信管、物流一、基本计算题:（每小题15分，本大题共60分）1. 某公司目前正在制造两种产品，产品Ⅰ和产品Ⅱ，现在产品Ⅰ和产品Ⅱ每天的产量分别为30个和120个。

公司负责制造的副总经理希望了解是否可以通过改变这两种产品的数量来提高公司的利润？公司制造每个产品所需的加工工时和各个车间的加工能力（每天加工（1）怎样安排生产，才能使利润最大。

（2）在1、2、3、4四个车间中那些车间的能力还有剩余，剩余多少？（3）1、2、3、4四个车间能力的影子价格各位多少？（4）当产品Ⅰ的单位利润不变，产品Ⅱ的单位利润在什么范围内变化时，此最优解不变？当产品Ⅱ的单位利润不变时，产品Ⅰ的单位利润在什么范围内变化时，此最优解不变。

（5）当产品Ⅰ的单位利润从500元降为450元，而产品Ⅱ的单位利润从400元增加为430元，原来的最优解产品组合是否还是最优产品组合？如有变化，新的最优产品组合是什么？2. 雨水啤酒厂(Rainwater Brewery)生产雨水牌啤酒,并用桶把啤酒储存在仓库中。

啤酒厂的销售商一旦有需求,啤酒厂就为其提供啤酒。

雨水啤酒每天的需求量为1500桶,啤酒厂每天可生产2000桶这种啤酒。

生产一批雨水啤酒的设备调整成本为6500美元。

雨水啤酒一旦被酿好,就以每桶每年50美元的成本储存在冷冻仓库中。

（一年按360天计）求a.成本最小的生产批量。

b.一年生产多少个批次？c.循环期。

d.一个生产批次要多长时间。

e.最大库存量。

f.总的年成本。

g.再订购点。

3. 亚特兰大的桃树机场服务轻型飞机，它有一条跑道和一个空中交通控制员控制飞机的降落。

一架飞机的降落和清理跑到需要12分钟。

机场每小时到达4架飞机。

a.确定等待降落飞机的平均数。

b.确定一架飞机降落前的平均等待时间。

c.一旦飞机通知机场它就在附近并且想降落，计算清理跑道平均所花费的时间？d.FAA有一条规定是一名空中交通控制员平均最多能在一个小时内的45分钟使飞机着陆。

《运筹学》试题样卷（一）一、判断题（共计10分，每小题1分，对的打√，错的打X ）1. 无孤立点的图一定是连通图。

2. 对于线性规划的原问题和其对偶问题，若其中一个有最优解， 另一个也一定有最优解。

3. 如果一个线性规划问题有可行解，那么它必有最优解。

4．对偶问题的对偶问题一定是原问题。

5．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0>j σ对应的变量都可以被选作换入变量。

6．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。

7. 度为0的点称为悬挂点。

8. 表上作业法实质上就是求解运输问题的单纯形法。

9. 一个图G 是树的充分必要条件是边数最少的无孤立点的图。

二、建立下面问题的线性规划模型（8分）某农场有100公顷土地及15000元资金可用于发展生产。

农场劳动力情况为秋冬季3500人日；春夏季4000人日。

如劳动力本身用不了时可外出打工，春秋季收入为25元 / 人日，秋冬季收入为20元 / 人日。

该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。

种作物时不需要专门投资，而饲养每头奶牛需投资800元，每只鸡投资3元。

养奶牛时每头需拨出1.5公顷土地种饲料，并占用人工秋冬季为100人日，春夏季为50人日，年净收入900元 / 每头奶牛。

养鸡时不占用土地，需人工为每只鸡秋冬季0.6人日，春夏季为0.3人日，年净收入2元 / 每只鸡。

农场现有鸡舍允许最多养1500只鸡，牛栏允许最多养200头。

三种作物每年需要的人工及收入情况如下表所示：试决定该农场的经营方案，使年净收入为最大。

三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为(1)写出原线性规划问题；（4分） (2)写出原问题的对偶问题；（3分）(3)直接由上表写出对偶问题的最优解。

（1分） 四、用单纯形法解下列线性规划问题（16分）3212max x x x Z +-=s. t. 3 x 1 + x 2 + x 3 ≤ 60 x 1- x 2 +2 x 3 ≤ 10 x 1+ x 2- x 3 ≤ 20 x 1, x 2 , x 3 ≥0五、求解下面运输问题。

2010级运筹学试题B天津师范大学考试试卷Array 2011—2012学年第二学期期末考试试卷（B 卷）科目：运筹学学院：管理学院专业：信管、物流一、基本计算题:（每小题15分，本大题共60分）1. 前进电器厂生产A、B、C三种产品的有关资料如下表所示。

问：(1)在资源限量及市场容量允许的条件下，如何安排生产获利最多？(2)说明A、B、C三种产品的市场容量的影子价格以及材料、台时的影子价格的含义，并对其进行灵敏度分析。

(3)如要开拓市场应当首先开拓哪种产品的市场？(4)如果要增加资源，则应在多大程度上增加机器台时数和材料数量？(5)单位产品利润分别在什么范围内变化时，原生产计划不变。

2. 大西洋钢铁公司(Atlantic Steel Company)的采购部经理必须制订一个煤炭采购策略以运作12个炼钢炉,每个炼钢炉每天精确地需要5吨煤来运作。

公司每年运作360天。

采购部经理已经确定单位订购成本为80美元,持有成本为库存持有商品平均价值的20%。

采购部经理已签订了一份公司在未来一年内可以以每吨12美元的价格采购煤的合同。

a.求每次订购煤的最优订购批量;b.求最优订货策略下的库存相关总成本(不包括煤的成本);c.如果接收订购的煤所需的提前期为5天,则下订单时煤的现有库存量应为多少?3. 第一城市的第一美国银行（First American Bank of Rapid City）有一个室外取款机，它服务一个银行客户平均花费4分钟。

每小时有12个客户到达服务窗口。

银行的运营主管正在分析添加第2 台窗口的可能性，每年花费20000美元。

假定到达的车辆平均分到两个服务窗口。

业务主管估计在客户等待时间上减少1分钟那么银行每年的收入将增加2000美元。

请计算应该安装第2个服务窗口吗？4. 简和吉姆.史密斯将在星期五晚上7：00举行一个聚会，他们的两个孩子杰瑞和朱迪将帮助他们准备此次聚会。

史密斯夫妇将都在下午4：00从工作单位和学校回到家。

《运筹学》试题及答案（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个非基变量6.下例错误的说法是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二、判断题（你认为下列命题是否正确，对正确的打“√”；错误的打“×”。

《运筹学》课程试卷A适用专业: 考试日期：考试时间：120分钟考试形式：闭卷试卷总分：100分一、填空题（每小题2分，共20分）：1.若基本可行解中的非零变量的个数小于m，即基变量出现零值时，则此基本可行解称为。

2.运输问题的数学模型和一般数学模型比较，具有的特点是。

3.用矩阵表示线形规划的数学模型，可推算出其解的表达式X B= ；f=.4.处理人工变量的方法有和。

5. 线性规则的数学模型中，基本解的个数最多为个。

6.若原规划问题的变量xj≤0，则对偶问题的约束条件为；变量xj为自由变量，对偶问题的约束条件为。

7.遗憾准则的基本思想是，所选最优方案是。

8.在网络分析中，总开工车项最早可能开始时间t e(1)= ，其余事项的最早可能开始时间t e(j)= 。

9. 确定下图中A2B2空格的闭合回路为。

10.动态规划的基本方程可表述为。

二、计算（80分）1．由下列单纯形表继续迭代,并确定其最优解，其目标函数是Maxf=7X1+12X2 （10分）2．根据表中的作业明细表绘制网络图（10分）3、4台拖拉机中分别完成四块土地耕作任务，每台拖拉机完成每块耕作任务的耗油量列于下表，试用匈牙利法求一个最省油的分配方案。

（10分）4、应用动态规划求解下列的线性模型。

（20分） 24232221X X X X MinZ +++=s.t : X 1+X 2+X 3+X 4≥10 Xi ≥0, i=1,2,3,4,5、现有一饭店转租，价格为20万，有经验的老张想把它租下，如租下需聘请一厨师，如聘王师傅年薪5万，手艺成功率是50%，并且不成功不需要年薪，如聘李师傅年薪7万，手艺成功率是70%，并且不成功也需要年薪，饭店经营额与单地的天气有很大的关系，如天晴，不除去聘请工资及饭店的租金，盈利额为50万，如下雨，盈利额为5万，当地天晴的概率是0.7，下雨的概率是0.3，试用决策树决策老张是否租此饭店，如租下应聘请哪个师傅，期望值是多少？（15分）6．线形规划问题（15分） 3212max x x x z +-=⎪⎩⎪⎨⎧≥≤+-≤++0,,42632121321x x x x x x x x用单纯形法求得最终单纯形表如下表所示 试说明分别发生下列变化时，新的最优解是什么(1)目标函数变为32132m ax x x x z ++=(2)约束条件右端项由 ⎥⎦⎤⎢⎣⎡46 变为⎥⎦⎤⎢⎣⎡43《运筹学》课程试卷A 答案一、填空（20分，每小题2分）： 1.退化的基本可行解2. （1）目标值为求最大值；（2）bj 值≥0；（3）aij=1（4）xij 在约束方程中无变量交叉在一个方程中。

北京交通大学远程与继续教育学院2010-2011学年第一学期网络教育期末试卷年级 2010级专业层次专升本成绩运筹学课程（ B卷）(请考生注意:本试卷共有六道大题)一、判断题(在下列各题中，你认为题中描述的内容为正确者，在题尾括号内写“√”，错误者写“×”。

每小题3分，共15分)1. 对偶问题的目标函数总是与原问题目标函数相等。

( )2. 原问题与对偶问题是一一对应的。

( )3. 运输问题的可行解中基变量的个数一定遵循m＋n－1的规则。

( )4. 指派问题的解中基变量的个数为m＋n。

( )5. 网络最短路径是指从网络起点至终点的一条权和最小的路线。

( )二、填空题（每个空2分，共20分）：1. 滑动平均预测法又分为（简单平均预测法）和（加权平均预测法）。

2．建立库存模型主要是为了探讨（库存数量）与（库存费用）之间的关系。

3.企业的盈亏主要取决于企业产品的（销售收入）和产品的（成本费用）。

4、线性规划的解有（）、（）、（）和无可行解四种。

5、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明（）。

三、选择题（每小题3分，共15分）：1．一个允许缺货的EOQ模型的费用CⅠ，和一个不允许缺货的EOQ模型的费用CⅡ，在具有相同存贮费、订购费的情况下（）A．CⅠ≥CⅡ B．CⅠ> CⅡ C．CⅠ< CⅡ D．CⅠ≤CⅡ2. 若某一运输问题有m个产地，n个销售地；则任意m+n-1个变量只要满足（），就可以作为基本可行解。

A.满足产销平衡B.非负条件C.在产销平衡表中构成闭回路D.满足产销平衡、非负条件，且在产销平衡表中不能构成闭回路3. 以结点9为始点的活动共有4个，它们的最迟开始时间各为：LS9，11=10天；LS9，13=6天；LS9，15=8天，LS9，17=9天。

则结点9的最迟开始时间LS9为（）天。

A.10B.6C.8D.94. 关于网络图中关键路线说法不正确的是( )。

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

一、判断题（共计 分，每小题 分，对的打√，错的打 ） 无孤立点的图一定是连通图。

对于线性规划的原问题和其对偶问题，若其中一个有最优解，另一个也一定有最优解。

如果一个线性规划问题有可行解，那么它必有最优解。

．对偶问题的对偶问题一定是原问题。

．用单纯形法求解标准形式（求最小值）的线性规划问题时，与0>j σ对应的变量都可以被选作换入变量。

．若线性规划的原问题有无穷多个最优解时，其对偶问题也有无穷 多个最优解。

度为 的点称为悬挂点。

表上作业法实质上就是求解运输问题的单纯形法。

一个图 是树的充分必要条件是边数最少的无孤立点的图。

二、建立下面问题的线性规划模型（ 分）某农场有 公顷土地及 元资金可用于发展生产。

农场劳动力情况为秋冬季 人日；春夏季 人日。

如劳动力本身用不了时可外出打工，春秋季收入为 元 人日，秋冬季收入为 元 人日。

该农场种植三种作物：大豆、玉米、小麦，并饲养奶牛和鸡。

种作物时不需要专门投资，而饲养每头奶牛需投资 元，每只鸡投资 元。

养奶牛时每头需拨出 公顷土地种饲料，并占用人工秋冬季为 人日，春夏季为 人日，年净收入 元 每头奶牛。

养鸡时不占用土地，需人工为每只鸡秋冬季 人日，春夏季为 人日，年净收入 元 每只鸡。

农场现有鸡舍允许最多养 只鸡，牛栏允许最多养 头。

三种作物每年需要的人工及收入情况如下表所示：试决定该农场的经营方案，使年净收入为最大。

三、已知下表为求解某目标函数为极大化线性规划问题的最终单纯形表，表中54,x x 为松弛变量，问题的约束为 形式（共 分）写出原线性规划问题；（ 分） 写出原问题的对偶问题；（ 分）直接由上表写出对偶问题的最优解。

（ 分）四、用单纯形法解下列线性规划问题（ 分）3212max x x x Z +-=五、求解下面运输问题。

（ 分）某公司从三个产地 、 、 将物品运往四个销地 、 、 、 ，各产地的产量、各销地的销量和各产地运往各销地每件物品的运费如表所示： 问：应如何调运，可使得总运输费最小六、灵敏度分析（共 分）线性规划的最优单纯形表如下：在何范围内变化，最优计划不变？ 分在什么范围内变化，最优基不变？ 分七、试建立一个动态规划模型。

一、填空题：（每空格2分，共16分）1、线性规划的解有唯一最优解、无穷多最优解、 无界解 和无可行解四种。

2、在求运费最少的调度运输问题中，如果某一非基变量的检验数为4，则说明 如果在该空格中增加一个运量运费将增加4 。

3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错 错4、如果某一整数规划： MaxZ=X 1+X 2 X 1+9/14X 2≤51/14 -2X 1+X 2≤1/3 X 1,X 2≥0且均为整数所对应的线性规划（松弛问题）的最优解为X 1=3/2，X 2=10/3，MaxZ=6/29，我们现在要对X 1进行分枝，应该分为 X1≤1 和 X1≥2 。

5、在用逆向解法求动态规划时，f k (s k )的含义是： 从第k 个阶段到第n 个阶段的最优解 。

6. 假设某线性规划的可行解的集合为D ，而其所对应的整数规划的可行解集合为B ，那么D和B 的关系为 D 包含 B7. 已知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条问：（1）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛---1003/20.3/1312 (2)对偶问题的最优解： Y ＝（5，0，23，0，0）T8. 线性规划问题如果有无穷多最优解，则单纯形计算表的终表中必然有___某一个非基变量的检验数为0______；9. 极大化的线性规划问题为无界解时，则对偶问题_无解_________；10. 若整数规划的松驰问题的最优解不符合整数要求，假设X i =b i 不符合整数要求，INT （b i ）是不超过b i 的最大整数，则构造两个约束条件：Xi ≥INT （b i ）＋1 和 Xi ≤INT （b i ） ，分别将其并入上述松驰问题中，形成两个分支，即两个后继问题。

11. 知下表是制订生产计划问题的一张LP 最优单纯形表（极大化问题，约束条问：(1)对偶问题的最优解： Y ＝(4,0,9,0,0,0)T （2）写出B -1=⎪⎪⎪⎭⎫ ⎝⎛611401102二、计算题（60分）1、 已知线性规划（20分） MaxZ=3X 1+4X 2 1+X 2≤5 2X 1+4X 2≤12 3X 1+2X 2≤81,X 2≥02） 若C 2从4变成5，最优解是否会发生改变，为什么3） 若b 2的量从12上升到15，最优解是否会发生变化，为什么4） 如果增加一种产品X 6，其P 6=(2,3,1)T ，C 6=4该产品是否应该投产为什么 解：1)对偶问题为Minw=5y1+12y2+8y3 y1+2y2+3y3≥3y1+4y2+2y3≥4 y1,y2≥02)当C 2从4变成5时， σ4=-9/8 σ5=-1/4由于非基变量的检验数仍然都是小于0的，所以最优解不变。