2012--2013运筹学期末考试试题及答案

一、填空题问题1 用大M法求解Max型线性规划时，人工变量在目标中的系数均为-M ，若最优解的基变量中含有人工变量,则原问题无可行解。

问题2 线性规划原问题中的变量个数与其对偶问题中的约束条件个数相等。

因此，当原问题增加一个变量时,对偶问题就增加一个约束条件，从而对偶可行域将可能变小(小还是大）。

问题3 若某种资源的影子价格为零，则表明该种资源不应该（应该或不应该）被买进;又当资源的影子价格不为零时，说明该种资源消耗完毕（完毕or 剩余）问题4 用表上作业法求解m个产地n个销地的平衡运输问题，其方案表上数字格的个数为m+n-1 个；若已计算出某空格的检验数为—3,若从该空格出发进行调整，设调整量为2，则调整后可使总运费下降 6 。

问题5 下表中给出某线性规划问题计算过程中的一个单纯形表,约束条件为≤，目标函数为maxZ=28ⅹ4+ⅹ5 +2ⅹ6,表中ⅹ1，ⅹ2，ⅹ3为松弛变量，表中解的目标函数值Z=14.其中，a= 7 ，b= -6 ,c= 0 ，d= 1 ，e= 0 ，f= 1/3 ，g= 0 ；表中所给出的解是（是否）为最优解，如为最优解，解的情况是无穷多最优解（唯一最优解、无穷多最优解、无界解、无可行解)。

二、判断题问题一某线性规划模型具有可行解,则该线性规划问题的对偶模型也有可行解。

错问题二在线性规划的图解法中，基可行解一定可以在顶点得到。

对问题三如果线性规划的对偶问题无可行解,则原问题也一定无可行解。

错问题四运输问题解的情况有四种：无可行解;无界解;唯一最优解；无穷多最优解。

错问题五运输问题的所有结构约束条件都是等式约束。

对三、计算题（10分）已知线性规划问题minZ=8ⅹ1+6ⅹ2+3ⅹ3+6ⅹ4ⅹ1+2ⅹ2 +ⅹ4≥33ⅹ1+ⅹ2+ⅹ3+ⅹ4≥6ⅹ3+ⅹ4≥2ⅹ1 +ⅹ3 ≥2ⅹ1，ⅹ2,ⅹ3,ⅹ4≥0（1）写出原问题的对偶问题。

(2）已知原问题的解为(1，1，2，0），根据对偶理论直接求解对偶问题的最优解;解：（1)略(2）（2，2,1，0）四、应用题（30分）某建材厂生产四种型号的特用构件：Ⅰ型-、Ⅱ型、Ⅲ型、Ⅳ型。

楚大2012---2013上学期经济信息管理及计算机应用系《运筹学》期末考试试题及答案班级： 学号一、单项选择题：1、在下面的数学模型中，属于线性规划模型的为（ A ）。

⎪⎩⎪⎨⎧≥-≥-+=0Y ,X 1Y X 2.t .s Y X 3S min .B ⎪⎩⎪⎨⎧≥≤+=0Y ,X 3XY .t .s Y X 4S max .A ⎪⎩⎪⎨⎧≥≤-+=0Y ,X 2Y X .t .s Y X S max .C 22⎪⎩⎪⎨⎧≥≥+=0Y ,X 3Y X .t .s XY 2S min .D 2、线性规划问题若有最优解，则一定可以在可行域的 （ A ）上达到。

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

A.两个B.零个C.无穷多个D.有限多个5、线性规划具有唯一最优解是指（ B ）A ．最优表中存在常数项为零B ．最优表中非基变量检验数全部非零C ．最优表中存在非基变量的检验数为零D ．可行解集合有界6、设线性规划的约束条件为⎪⎩⎪⎨⎧≥=++=++0,,422341421321x x x x x x x x 则基本可行解为（ C ）。

A ．(0, 0, 4, 3)B ． (3, 4, 0, 0)C ．(2, 0, 1, 0)D ． (3, 0, 4, 0)7、若运输问题已求得最优解，此时所求出的检验数一定是全部（ D ）A 、小于或等于零B ．大于零C ．小于零D ．大于或等于零8、对于m 个发点、n 个收点的运输问题，叙述错误的是( D )A ．该问题的系数矩阵有m ×n 列B ．该问题的系数矩阵有m+n 行C ．该问题的系数矩阵的秩必为m+n-1D ．该问题的最优解必唯一9、关于动态规划问题的下列命题中错误的是（ A ）A 、动态规划分阶段顺序不同，则结果不同B 、状态对决策有影响C 、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D 、动态规划的求解过程都可以用列表形式实现10、若P 为网络G 的一条流量增广链，则P 中所有正向弧都为G 的（ D ）A．对边B．饱和边C．邻边D．不饱和边一、判断题。

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

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

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

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

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

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

度为 的点称为悬挂点。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

运筹学试卷及参考答案运筹学试卷一、选择题（每小题2分，共20分）1、下列哪个不是线性规划的标准形式？（） A. min z = 3x1 + 2x2B. max z = -4x1 - 3x2C. s.t. 2x1 - x2 <= 1D. s.t. x1 + x2 >= 0答案：C2、以下哪个是最小生成树的Prim算法？（） A. 按照权值从小到大的顺序选择顶点 B. 按照权值从大到小的顺序选择顶点 C. 按照距离从小到大的顺序选择顶点 D. 按照距离从大到小的顺序选择顶点答案：B3、下列哪个不是网络流模型的典型应用？（） A. 道路交通流量优化 B. 人员部署 C. 最短路径问题 D. 生产计划答案：C4、下列哪个是最小化问题中常用的动态规划解法？（） A. 自顶向下的递推求解 B. 自底向上的递推求解 C. 分治算法 D. 回溯法答案：A5、下列哪个是最大流问题的 Ford-Fulkerson 算法？（） A. 增广路径的寻找采用深度优先搜索 B. 增广路径的寻找采用广度优先搜索 C. 初始流采用最大边的二分法求解 D. 初始流采用最小边的二分法求解答案：B二、简答题（每小题10分，共40分）1、请简述运筹学在现实生活中的应用。

答案：运筹学在现实生活中的应用非常广泛。

例如，线性规划可以用于生产计划、货物运输和资源配置等问题；网络流模型可以用于解决道路交通流量优化、人员部署和生产计划等问题；动态规划可以用于解决最短路径、货物存储和序列安排等问题；图论模型可以用于解决最大流、最短路径和最小生成树等问题。

此外，运筹学还可以用于医疗资源管理、金融风险管理、军事战略规划等领域。

总之，运筹学的理论和方法可以帮助人们更好地解决实际生活中的问题，提高决策的效率和准确性。

2、请简述单纯形法求解线性规划的过程。

答案：单纯形法是一种求解线性规划问题的常用方法。

它通过不断迭代和修改可行解，最终找到最优解。

具体步骤如下： (1) 将线性规划问题转化为标准形式； (2) 根据标准形式构造初始可行基，通常选取一个非基变量，使其取值为零，其余非基变量的取值均为零； (3) 根据目标函数的系数，计算出目标函数值； (4) 通过比较目标函数值和已选取的非基变量的取值，选取最优的非基变量进行迭代； (5) 在迭代过程中，不断修正基变量和非基变量的取值，直到找到最优解或确定无解为止。

《运筹学》试题参考答案一、填空题（每空2分，共10分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为 可行解 。

2、在线性规划问题中，图解法适合用于处理 变量 为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点，化为供求平衡的标准形式 。

4、在图论中，称 无圈的 连通图为树。

5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。

二、（每小题5分，共10分）用图解法求解下列线性规划问题： 1）max z = 6x 1+4x 2⎪⎪⎩⎪⎪⎨⎧≥≤≤+≤+0781022122121x x x x x x x ， 解：此题在“《运筹学》复习参考资料.doc ”中已有，不再重复。

2）min z =－3x 1+2x 2⎪⎪⎪⎩⎪⎪⎪⎨⎧≥≤-≤-≤+-≤+0,137210422422121212121x x x x x x x x x x 解：⑴ ⑵ ⑶ ⑷ ⑸ ⑹、⑺⑴⑵ ⑶ ⑷ ⑸、⑹可行解域为abcda ，最优解为b 点。

由方程组⎩⎨⎧==+02242221x x x 解出x 1=11，x 2=0∴X *=⎪⎪⎭⎫ ⎝⎛21x x =（11，0）T ∴min z =－3×11+2×0=－33三、（15分）某厂生产甲、乙两种产品，这两种产品均需要A 、B 、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：A B C 甲 9 4 3 70 乙 4 6 10 1203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5分）2）用单纯形法求该问题的最优解。

（10分） 解：1）建立线性规划数学模型：设甲、乙产品的生产数量应为x 1、x 2，则x 1、x 2≥0，设z 是产品售后的总利润，则max z =70x 1+120x 2s.t.⎪⎪⎩⎪⎪⎨⎧≥≤+≤+≤+0300103200643604921212121x x x x x x x x ， 2）用单纯形法求最优解：加入松弛变量x 3，x 4，x 5，得到等效的标准模型：max z =70x 1+120x 2+0 x 3+0 x 4+0 x 5s.t.⎪⎪⎩⎪⎪⎨⎧=≥=++=++=++5,...,2,1,03001032006436049521421321j x x x x x x x x x x j 列表计算如下：∴X *=（11，11，11，0，0）T∴max z =70×11100+120×11300=1143000四、（10分）用大M 法或对偶单纯形法求解如下线性规划模型：min z =5x 1＋2x 2＋4x 3⎪⎩⎪⎨⎧≥≥++≥++0,,10536423321321321x x x x x x x x x解：用大M 法，先化为等效的标准模型：max z / =－5x 1－2x 2－4x 3 s.t.⎪⎩⎪⎨⎧=≥=-++=-++5,...,2,1,010********214321j y x x x x x x x x j增加人工变量x 6、x 7，得到：max z / =－5x 1－2x 2－4x 3－M x 6－M x 7 s.t⎪⎩⎪⎨⎧=≥=+-++=+-++7,...,2,1,010*********2164321j x x x x x x x x x x x j大M 法单纯形表求解过程如下：∴x *=（32，2，0，0，0）T最优目标函数值min z =－max z / =－（－322）=322五、（15分）给定下列运输问题：（表中数据为产地A i 到销地B j 的单位运费）1）用最小费用法求初始运输方案，并写出相应的总运费；（5分） 2）用1）得到的基本可行解，继续迭代求该问题的最优解。

《运筹学》课程考试试卷试题(含答案)一、选择题（每题5分，共25分）1. 运筹学的核心思想是（）A. 最优化B. 系统分析C. 预测D. 决策答案：A2. 在线性规划中，约束条件可以用（）表示。

A. 等式B. 不等式C. 方程组D. 矩阵答案：B3. 以下哪个不是运筹学的基本模型？（）A. 线性规划B. 整数规划C. 非线性规划D. 随机规划答案：D4. 在目标规划中，以下哪个术语描述的是决策变量的偏离程度？（）A. 目标函数B. 约束条件C. 偏差变量D. 权重系数答案：C5. 在动态规划中，以下哪个概念描述的是在决策过程中，某一阶段的最优决策对后续阶段的影响？（）A. 最优子结构B. 无后效性C. 最优性原理D. 阶段性答案：B二、填空题（每题5分，共25分）1. 运筹学是一门研究在复杂系统中的______、______和______的科学。

答案：决策、优化、实施2. 在线性规划中，若目标函数为最大化，则其标准形式为______。

答案：max z = c^T x3. 在非线性规划中，若目标函数和约束条件均为凸函数，则该规划问题为______。

答案：凸规划4. 在目标规划中，若决策变量x_i的权重系数为w_i，则目标函数可以表示为______。

答案：min Σ(w_i d_i^+ + w_i d_i^-)5. 在动态规划中，若状态变量为s_n，决策变量为u_n，则状态转移方程可以表示为______。

答案：s_{n+1} = f(s_n, u_n)三、判断题（每题5分，共25分）1. 线性规划问题的最优解一定在可行域的顶点处取得。

（）答案：正确2. 在整数规划中，若决策变量为整数，则目标函数和约束条件也必须为整数。

（）答案：错误3. 目标规划中的偏差变量可以是负数。

（）答案：正确4. 在动态规划中，最优策略具有最优子结构。

（）答案：正确5. 在非线性规划中，若目标函数为凸函数，则约束条件也必须为凸函数。

2012年9月份考试运筹学第一次作业一、单项选择题（本大题共100分，共40小题，每小题2. 5分）1.•个无（）、但允许多重边的图称为多重图。

A.边B.孤C.环D.路2.运筹学是一门（）。

A.决策科学B.数学科学C.应用科学D.逻辑科学3.基可行解对应的基，称为（）。

A.最优基B.可行基C.最优可行基D.极值基4.运筹学用（）来描述问题。

A.拓补语言B.计算机语言C.机器语言D 数学语言5.隐枚墓最是省去若干目标函数不占优势的（）的一种检验过程。

A.基本可行解B.最优解C.基本解D.可行解6.对偶问题与原问题研究出自（）目的。

A.不同B.相似C.相反D.同一7.资源价格大于影子价格时，应该（）该资源。

A.头入B.卖出C.保持现状D 借贷出8.敏房性分析假定（）不变，分析参数的波动对最优解有什么影响。

A.可行基B.基本基C.非可行基D.最优基9.从系统工程或管理信息预测决辅助系统的角度来看，管理科学与（）就其功能而言是等同或近似的。

A 纬汁学B：计算机辅助科学C,运筹学D.人工智能科学10.闭回路的特点不包括（）。

A.每个顶点都是直角B.每行或每列有且仅有两个顶点C.每个顶点的连线都是水平的或是垂直的D.起点终点可以不同11.运输问题分布m*n矩阵表的横向约束为（）。

A.供给约束B.需求约束C.以上两者都有可能C.超额约束12.动态规划综合了（）和“最优化原理”。

A.一次决策方法B.二次决策方法C.系统决策方法D.分级决策方法13.线性规划问题不包括（）。

A.资源优化配置B.复杂系统结构性调整C,混沌系统分析D,宏、微观经济系统优化14.运输问题分布m*n矩阵表的纵向约束为（）。

A.供给约束B.需求约束C.以上两者都有可D.超额约束15.路的第一个点和最后一个点相同，称为（）oA.通路B,环路C.回路D,连通路16.对偶问题与原问题研究的是（）对象。

A.2种B.不同的C.1种D.相似的17.运输问题的求解方法不包括（）。

《运筹学》期末考试试卷A-答案一、选择题（每题5分，共25分）1. 运筹学是一门研究在复杂系统中进行决策的科学，以下哪个选项不属于运筹学的研究内容？A. 优化问题B. 随机过程C. 系统建模D. 心理咨询答案：D2. 在线性规划中，若一个线性规划问题的可行域是空集，则该问题称为：A. 无界问题B. 无解问题C. 无可行解问题D. 有解问题答案：C3. 线性规划问题中，目标函数和约束条件均为线性函数的是：A. 线性规划B. 非线性规划C. 动态规划D. 随机规划答案：A4. 在整数规划中，若决策变量只能取整数值，则该问题称为：A. 线性规划B. 整数规划C. 非线性规划D. 动态规划答案：B5. 在排队论中，以下哪个因素对服务效率影响最大？A. 服务速率B. 到达率C. 排队长度D. 服务时间答案：A二、填空题（每题5分，共25分）1. 运筹学的基本方法是________、________和________。

答案：模型化、最优化、计算机模拟2. 线性规划的标准形式包括________、________和________。

答案：目标函数、约束条件、非负约束3. 在非线性规划中，目标函数和约束条件至少有一个是________函数。

答案：非线性4. 动态规划适用于解决________决策问题。

答案：多阶段5. 排队论中的基本参数包括________、________和________。

答案：到达率、服务率、服务台数量三、简答题（每题10分，共30分）1. 请简要介绍线性规划的基本概念。

答案：线性规划是运筹学的一个基本分支，主要研究在一定的线性约束条件下，如何求解目标函数的最大值或最小值问题。

线性规划问题通常包括目标函数、约束条件和非负约束。

目标函数是决策者要优化的目标，约束条件是决策者需要满足的条件，非负约束要求决策变量取非负值。

2. 请简要阐述整数规划的特点。

答案：整数规划是线性规划的一种特殊情况，要求决策变量取整数值。

《运筹学》试题参考答案 一、填空题�每空2分�共10分� 1、在线性规划问题中�称满足所有约束条件方程和非负限制的解为 可行解 。

2、在线性规划问题中�图解法适合用于处理 变量 为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是 设立虚供地或虚需求点�化为供求平衡的标准形式 。

4、在图论中�称 无圈的 连通图为树。

5、运输问题中求初始基本可行解的方法通常有 最小费用法 、 西北角法 两种方法。

二、�每小题5分�共10分�用图解法求解下列线性规划问题� 1�m a x z = 6x 1+4x 2�������������0781022122121x x x x x x x � 解�此题在“《运筹学》复习参考资料.d o c ”中已有�不再重复。

2�m i n z =�3x 1+2x 2 �������������������0,137210422422121212121x x x x x x x x x x解�⑴⑵⑶ ⑷ ⑸⑹、⑺⑴⑵⑶ ⑷ ⑸、⑹可行解域为a b c d a �最优解为b 点。

由方程组������02242221xx x 解出x 1=11�x 2=0 ∴X *=��������21x x =�11�0�T∴m i n z =�3×11+2×0=�33三、�15分�某厂生产甲、乙两种产品�这两种产品均需要A 、B 、C 三种资源�每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示�ABC甲 9 4 3 70 乙 4 6 10 120 360 200 3002�用单纯形法求该问题的最优解。

�10分� 解�1�建立线性规划数学模型� 设甲、乙产品的生产数量应为x 1、x 2�则x 1、x 2≥0�设z 是产品售后的总利润�则 ma x z =70x 1+120x 2 s.t . ��������������0300103200643604921212121x x x x x x x x � 2�用单纯形法求最优解� 加入松弛变量x 3�x 4�x 5�得到等效的标准模型� ma x z =70x 1+120x 2+0 x 3+0 x 4+0 x 5 s.t . ������������������5,...,2,1,03001032006436049521421321j x x x x x x xx x x j 列表计算如下�CB XB b70 120 0θL x1 x2 x3 x4 x5 0x 3 360 94190 0 x 4 200 4 6 0 1 0 100/3 0 x 5 300 3 �10� 0 0 1 300 0 0 0 0 70 120↑ 0 0 0 0 x3 240 39/5 0 1 0 - 2/5 400/13 0 x4 20 �11/5� 0 0 1 - 3/5 100/11 120 x 2 30 3/10 1 0 0 1/10 10036 120 0 0 12 34↑ 0 0 0 �12 0 x3 1860/11 0 0 1 �39/11 19/11 70 x 1 100/11 1 0 0 5/11 - 3/11 120 x 2 300/11 0 1 0 - 3/22 2/11114300070 120 0 170/11 30/11 0 0-170/11 �30/11 ∴X *=�11100�11300�111860�0�0�T ∴m a x z =70×11100+120×11300=1143000四、�10分�用大M 法或对偶单纯形法求解如下线性规划模型� mi n z =5x 1�2x 2�4x 3 ������������0,,10536423321321321x x x x x x x x x解�用大M 法�先化为等效的标准模型� ma x z / =�5x 1�2x 2�4x 3 s.t . ���������������5,...,2,1,01053642353214321j y x x x xx x x x j 增加人工变量x 6、x 7�得到� ma x z / =�5x 1�2x 2�4x 3�M x 6�M x 7 s.t �����������������7,...,2,1,0105364237532164321j x x x x x x x x x x x j 大M 法单纯形表求解过程如下�C B X B b�5�2�400�M�MθLx1x2x3x4x5x6x7�M x64�3�12�10104/3�M x7106350�1015/3�9M�4M�7M M M�M�M9M�5↑4M�27M�4�M�M00�5x14/311/32/3�1/301/30——�M x72011�2��1�211�5-M�5/3-M�10/3-2M+5/3M2M�5/3-M0M�1/3M�2/32M�5/3↑�M�3M+5/30�5x15/311/25/60�1/601/610/3 0x410�1/2�1/21�1/2�11/22�5�5/2�25/605/60�5/601/2↑1/60�5/6�M�M+5/6�5�2x12/3101/3�11/31�1/3 x220112�1�21�322�5�2�11/311/3�1�1/3 00�1/3�1�1/3�M+1�M+1/3∴x*=�32�2�0�0�0�T最优目标函数值m i n z=�m a x z/=���322�=322五、�15分�给定下列运输问题��表中数据为产地A i到销地B j的单位运费�B1 B2 B3 B4 si A 1 A 2 A 3 1 2 3 4 8 7 6 5 9 10 11 9 10 80 15 dj 8 22 12 181�用最小费用法求初始运输方案�并写出相应的总运费��5分� 2�用1�得到的基本可行解�继续迭代求该问题的最优解。

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

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

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

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

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

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

度为 的点称为悬挂点。

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

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

某农场有 公顷土地及 元资金可用于发展生产。

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

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

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

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

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

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

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

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

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

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

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

-------------《运筹学》试题参考答案一、填空题（每空 2 分，共 10 分）1、在线性规划问题中，称满足所有约束条件方程和非负限制的解为可行解。

2、在线性规划问题中，图解法适合用于处理变量为两个的线性规划问题。

3、求解不平衡的运输问题的基本思想是设立虚供地或虚需求点，化为供求平衡的标准形式。

4、在图论中，称无圈的连通图为树。

5、运输问题中求初始基本可行解的方法通常有最小费用法、西北角法两种方法。

二、（每小题 5 分，共 10 分）用图解法求解下列线性规划问题：1）max z = 6x1+4x2⑴2x1x2 10 ⑵x1x28 ⑶x27 ⑷x1，x20 ⑸、⑹《运筹学》复习参考资料解：此题在“.doc”中已有，不再重复。

2）min z =－3x1+2x2⑴2x14x222 ⑵x14x210 ⑶2x1x27 ⑷x1 3x2 1 ⑸x1 , x20 ⑹、⑺解：--------------------------可行解域为 abcda，最优解为 b 点。

2 x1 4x222由方程组解出 x1=11，x2=0x20∴X* = x1 =（11，0）T x2∴min z =－3×11+2×0=－33三、（15 分）某厂生产甲、乙两种产品，这两种产品均需要 A 、B、C 三种资源，每种产品的资源消耗量及单位产品销售后所能获得的利润值以及这三种资源的储备如下表所示：A B C甲94370乙4610 1203602003001）建立使得该厂能获得最大利润的生产计划的线性规划模型；（5 分）--------------------------2）用单纯形法求该问题的最优解。

（10 分）解： 1）建立线性规划数学模型：设甲、乙产品的生产数量应为x1、x2，则 x1、x2≥0，设 z 是产品售后的总利润，则max z =70x1+120x2s.t.9 x1 4 x23604 x1 6 x22003 x110 x2300x1， x202）用单纯形法求最优解：加入松弛变量 x3，x4，x5，得到等效的标准模型：max z =70x1+120x2+0 x3+0 x4+0 x5s.t.9 x14x2x33604 x16x2x42003 x110x2x5300x j0, j1,2,...,5列表计算如下：--------------------------70120000θ LC B X B bx 1x2x3x4x5 0x3 3609410090 0x420046010100/3 0x5 3003（10）001300000070120↑000 0x3 24039/5 010- 2/5 400/13 0x4 20（11/5 ）001- 3/5 100/11 120x2303/10 1 001/1010036120001234↑000－12 0x3 1860/11001－39/11 19/1170 x1100/111005/11- 3/11120x2300/11010- 3/22 2/1143000701200170/11 30/1111000-170/11 －30/11∴X*=（ 100 ， 300 ， 1860，0，0）T11 11 11∴max z =70×100 +120×300 = 4300011 11 11四、（10 分）用大M法或对偶单纯形法求解如下线性规划模型：min z =5x1＋2x2＋4x33x1x22x3 46x13x25x310x1 , x2 , x30--------------------------解：用大 M 法，先化为等效的标准模型：max z/ =－5x1－2x2－4x3s.t.3x1x22x3 x4 46x13x25x3x5 10y j0, j 1,2,...,5增加人工变量 x6、x7，得到：max z/ =－5x1－2x2－4x3－M x6－M x7 s.t3x1x22x3 x4x6 46x13x25x3x5x7 10x j0, j 1,2,...,7大 M 法单纯形表求解过程如下：--------------------------C B X B －M x6 －M x7－5 x1－M x7－5 x10x4－5 x1－2 x2b－ 5－2 － 400－M－Mx1x2x3x4x5x6x7θ L 4（3）12－1 010 4/3106350－ 1 0 15/3 －9M－ 4M－7MM M－M－M↑4M－2 7M－4－M －M 00 9M－54/311/3 2/3－ 1/301/30 ——2011（2）－1 － 2 1 1－ 5-M－5/3 -M－10/3 -2 M +5/3M 2M － 5/3- M0M－1/3 M－2/3 2M －5/3 ↑－M － 3M +5/30 5/311/2 5/60－1/6 01/610/3 10（1/2 ）1/21－1/2 － 11/22－ 5－ 5/2 － 25/605/6 0－5/601/2 ↑1/60－5/6 － M－M +5/6 2/3101/3－1 1/3 1－1/320112－ 1 － 2 1－ 22－ 5－2 － 11/311/3 － 1－1/3300－1/3 －1 －1/3 －M +1－ M +1/3 2∴x* =（3，2，0，0，0）T最优目标函数值min z =－max z/ =－（－22）= 223 3--------------------------五、（15 分）给定下列运输问题：（表中数据为产地 A i 到销地 Bj 的单位运费）B1 B2 B3 B4 siA 1 1 2 3 4 10A 2 8 7 6 5 80A 3 9 10 11 9 15d j8 22 12 181）用最小费用法求初始运输方案，并写出相应的总运费；（5 分）2）用 1）得到的基本可行解，继续迭代求该问题的最优解。

期末运筹学试题及答案根据你的要求，以下是一份关于期末运筹学试题及答案的文章：期末运筹学试题及答案一、线性规划1. 问题描述：某工厂生产两种产品，产品 A 和产品 B。

生产一个单位的产品 A 需要花费 2 个单位的时间和 3 个单位的原材料，而生产一个单位的产品 B 需要花费 4 个单位的时间和 1 个单位的原材料。

工厂每天有 200 个单位的时间和 150 个单位的原材料可用。

产品 A 的利润为 5 单位，产品 B 的利润为 3 单位。

问如何安排生产，以使利润最大化？2. 解答：设生产产品 A 的数量为 x，生产产品 B 的数量为 y。

由于每天可用的时间和原材料有限，因此有以下限制条件：2x + 4y ≤ 200 （时间限制）3x + y ≤ 150 （原材料限制）而利润最大化的目标可以表示为：Maximize 5x + 3y综上所述，我们可以得到如下线性规划模型：Maximize 5x + 3ysubject to2x + 4y ≤ 2003x + y ≤ 150x ≥ 0, y ≥ 0二、网络模型1. 问题描述：有一座城市，城市中有多个交叉路口，每个交叉路口之间都有道路相连，形成了一个网络结构。

现在需要确定从一个起点到达终点的最短路径。

请使用迪杰斯特拉算法解决该问题。

2. 解答：迪杰斯特拉算法（Dijkstra Algorithm）是解决单源最短路径问题的常用算法。

以下是算法的步骤：1）初始化：将起点的距离设为0，其它节点的距离设为无穷大。

2）从起点开始，选择与起点相邻的节点中距离最小的节点作为当前节点。

3）计算当前节点的邻节点的距离，并更新最短距离。

4）重复第2步和第3步，直到所有节点都被访问过。

5）得到最短路径。

根据以上算法，我们可以计算出从起点到达终点的最短路径。

三、整数规划1. 问题描述：某公司生产四种产品，分别为产品 A、B、C 和 D。

每种产品对应的单位利润分别为 10、15、8 和 12。

《运筹学》期末考试试题及参考答案《运筹学》期末考试试题及参考答案一、填空题1、运筹学是一门新兴的_________学科，它运用_________方法，研究有关_________的一切可能答案。

2、运筹学包括的内容有_______、、、_______、和。

3、对于一个线性规划问题，如果其目标函数的最优解在某个整数约束条件的约束范围内，那么该最优解是一个_______。

二、选择题1、下列哪一项不是运筹学的研究对象？( ) A. 背包问题 B. 生产组织问题 C. 信号传输问题 D. 原子核物理学2、以下哪一个不是运筹学问题的基本特征？( ) A. 唯一性 B. 现实性 C. 有解性 D. 确定性三、解答题1、请简述运筹学在日常生活中的应用实例，并就其中一个进行详细说明。

2、某企业生产三种产品，每种产品都可以选择用手工或机器生产。

假设生产每件产品手工需要的劳动时间为3小时，机器生产为2小时，卖价均为50元。

此外，手工生产每件产品的材料消耗为10元，机器生产为6元。

已知每个工人每天工作时间为24小时，可生产10件产品，每件产品的毛利润为50元。

请用运筹学方法确定手工或机器生产的数量，以达到最大利润。

参考答案：一、填空题1、交叉学科；数学；合理利用有限资源，获得最大效益2、线性规划、整数规划、动态规划、图论与网络、排队论、对策论3、整点最优解二、选择题1、D 2. A三、解答题1、运筹学在日常生活中的应用非常广泛。

例如，在背包问题中，如何在有限容量的背包中选择最有价值的物品；在生产组织问题中，如何合理安排生产计划，以最小化生产成本或最大化生产效率；在信号传输问题中，如何设计最优的信号传输路径，以确保信号的稳定传输。

以下以背包问题为例进行详细说明。

在背包问题中，给定一组物品，每个物品都有自己的重量和价值。

现在需要从中选择若干物品放入背包中，使得背包的容量恰好被填满，同时物品的总价值最大。

这是一个典型的0-1背包问题，属于运筹学的研究范畴。

运筹学期末试题及答案一、选择题1. 运筹学是通过分析和决策来实现最佳利益的学科。

以下哪个选项最准确地描述了运筹学的定义？A. 运筹学是一门研究如何安排和管理物流的学科。

B. 运筹学是一门研究如何制定合理的销售策略的学科。

C. 运筹学是一门研究如何决策和规划资源的学科。

D. 运筹学是一门研究如何提高生产效率的学科。

答案：C2. 线性规划是一种常用于解决最优化问题的数学方法。

以下哪个选项最准确地解释了线性规划问题？A. 线性规划是一种通过建立线性方程组来寻找最小值或最大值的方法。

B. 线性规划是一种通过建立非线性方程组来寻找最小值或最大值的方法。

C. 线性规划是一种通过建立线性方程组来寻找全局最优解的方法。

D. 线性规划是一种通过建立非线性方程组来寻找局部最优解的方法。

答案：C3. 整数规划是一种特殊的线性规划问题，其中决策变量必须是整数。

以下哪个选项最准确地描述了整数规划的特点？A. 整数规划只适用于小规模问题，无法处理大规模问题。

B. 整数规划可以保证找到问题的最优整数解。

C. 整数规划只能用于决策变量为0或1的二进制问题。

D. 整数规划在求解过程中需要考虑所有可能的整数解。

答案：B4. 单纯形法是一种用于解决线性规划问题的常用算法。

以下哪个选项最准确地描述了单纯形法的特点？A. 单纯形法只能用于求解可行解存在且有限的线性规划问题。

B. 单纯形法可以保证找到线性规划问题的最优解。

C. 单纯形法在求解过程中需要考虑所有可能的解空间。

D. 单纯形法只适用于二维线性规划问题，无法处理高维问题。

答案：B5. 敏感性分析是一种用于评估线性规划模型解的稳定性和可靠性的方法。

以下哪个选项最准确地解释了敏感性分析？A. 敏感性分析是一种通过调整决策变量的值来优化线性规划模型的方法。

B. 敏感性分析是一种通过改变约束条件的值来评估线性规划模型的可行性的方法。

C. 敏感性分析是一种通过改变目标函数系数的值来评估线性规划模型解的稳定性的方法。

运筹学期末试卷及答案一、判断题（21分）1、可行解是基本可行解的充要条件是它的正分量所对应的A 中列向量线性无关（）；2、如果一个LP 问题有最优解，则它的对偶问题也有最优解，且它们的最优解相等（）；3、若线性规划问题有最优解，则一定有唯一的最优解（）；4、若一个原始线性规划问题无界，则它的对偶问题也无界（）；5、设1:R R f n →在点n x R ∈*处的Hesse 矩阵)(2*?x f 存在，若0)(2=?*x f ，并且)(2*?x f 正定，则*x 是（UMP ）的严格局部最优解（）；6、若1:R R f n →是S 上的凸函数，任意实数0≥α则f α是S 上的凸函数（）；7、设n R S ?是非空开凸集，1:R R f n →二阶连续可导，则f 是S 上的严格凸函数的充要条件是f 的Hesse 矩阵)(2x f ?在 S 上是正定的（）.二、1.将下面的线性规划问题化成标准形（7分）2，写出下面线性规划的对偶规划（7分）321654max x x x z ++=32134min x x x z ++=≥≥-+≤++=++.约,0,9522082510x 432.231321321321束无x x x x x x x x x x x t s≥≥≥+-=++≤-+.变为,0,016342532.231321321321量自由x x x x x x x x x x x x t s三、证明题（10分）设1:R R f n →在点n x R ∈*处可微.若*x 是（UMP ）的局部最优解，则0)(=?*x f .四、用对偶单纯形法求解下列线性规划问题（10分）32152415min x x x z ++==≥≥++≥+3,2,1,012526.32132j x x x x x x t s j五、把线性规划问题（18分）321x 2min x x Z -+-= ??≥≤+-≤++0,,426x .32121321x x x x x x x t s 记为（P ）求（1）用单纯形算法解（p ）；（2） 2c 由1变为)3(-；（3）b由4346变为六、用分枝定界法解下述ILP 问题（10分）21max x x z +=≥≥-≤+且为整数,0,2452.212121x x x x x x t s七、求以下无约束非线性规划问题的最优解（8分）746),(min 2211222121+-+-+=x x x x x x x x f 八、验证下列非线性规划为凸规划（9分）11394)(min 2112221++++=x x x x x x f ≤++-+=≤++=7422)(0975)(.22122212211x x x x x x g x x x g t s一、判断题（20分）1. V ;2. X;3. X;4. X;5. X ；6. V ；7. X 。

楚大2012---2013上学期经济信息经管及计算机应用系《运筹学》期末考试试卷及答案班级： 学号一、单项选择题：1、在下面的数学模型中，属于线性规划模型的为（ A ）。

⎪⎩⎪⎨⎧≥-≥-+=0Y ,X 1Y X 2.t .s Y X 3S min .B ⎪⎩⎪⎨⎧≥≤+=0Y ,X 3XY .t .s Y X 4S max .A ⎪⎩⎪⎨⎧≥≤-+=0Y ,X 2Y X .t .s Y X S max .C 22⎪⎩⎪⎨⎧≥≥+=0Y ,X 3Y X .t .s XY 2S min .D 2、线性规划问题若有最优解，则一定可以在可行域的 （A ）上达到。

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

A.两个B.零个C.无穷多个D.有限多个5、线性规划具有唯一最优解是指（ B ）A ．最优表中存在常数项为零B ．最优表中非基变量检验数全部非零C ．最优表中存在非基变量的检验数为零D ．可行解集合有界6、设线性规划的约束条件为⎪⎩⎪⎨⎧≥=++=++0,,422341421321x x x x x x x x 则基本可行解为（ C ）。

A ．(0, 0, 4, 3)B ． (3, 4, 0, 0)C ．(2, 0, 1, 0)D ． (3, 0, 4, 0)7、若运输问题已求得最优解，此时所求出的检验数一定是全部（ D ）A 、小于或等于零B ．大于零C ．小于零D ．大于或等于零8、对于m 个发点、n 个收点的运输问题，叙述错误的是( D )A ．该问题的系数矩阵有m ×n 列B ．该问题的系数矩阵有m+n 行C ．该问题的系数矩阵的秩必为m+n-1D ．该问题的最优解必唯一9、关于动态规划问题的下列命题中错误的是（ A ）A 、动态规划分阶段顺序不同，则结果不同B 、状态对决策有影响C 、动态规划中，定义状态时应保证在各个阶段中所做决策的相对独立性D 、动态规划的求解过程都可以用列表形式实现10、若P 为网络G 的一条流量增广链，则P 中所有正向弧都为G 的（ D ）A ．对边B ．饱和边C ．邻边D ．不饱和边一、判断题。

2012-2013 学年第 1 学期《运筹学》考试题答案要求 :第一题必做（ 50 分），二三四题任选两题（每题各25 分）。

一、考虑下面线性规划问题minz 4x1x23x1x23（）14 x13x26（）2s.t.2x23（）x13x1, x20（1）用图解法求解该问题；（2）写出该问题的标准形式；（3）求出该问题的松弛变量和剩余变量的值；（4）用单纯形法求解。

【解答】(1)图中阴影部分为此线性规划问题的可行域 ,目标函数z 4 x1x2,即 x24x1z 是斜率为 4 的一族平行直线 ,由线性规划的性质知 ,其最值在可行域的顶点取得 ,将直线z4x1 x2沿其法线方向逐渐向上平移,直至A点,A 点的坐标为 ( 3,6),所以 min z 43618 55555此线性规划问题有唯一解x13， x26。

55(2)给等式（ 2）左端添加剩余变量x3，给等式（3）左端添加松弛变量x4，则得到该问题的标准型为：maxz 4 x1x20x30x43x1x23,（）14x1 3x2x3 6 ,（）2s.t.2 x2x43,（）x13 x1 , x2 , x3 , x40（3）在上面标准型中令x13， x26，得到剩余变量 x3=0，松弛变量 x4=0。

55（4）先在上面标准型中约束条件(1)、（ 2）中分别加入人工变量x5, x6，得到如下数学模型，maxz4x1x20x30x4Mx 5 Mx63x1x2x53,（）14x13x2x3x6 6 ,（）2s.t.2x2x43,（）x13x1 , x2 , x3 , x4 , x5 , x60由此列出单纯形表逐步迭代，用大M 法求解计算结果如下表所示。

C j－4－100－ M－ Mx jC B X B x1x2x3x4x5x6b i － M x5【3】1001031－M x643－ 100163/20x412010033 r j7M－4 4M－1－ M000－ 9M － 4x111/3001/3013－ M x60【5/3】－ 10－ 4/3126/50x405/301－ 1/3026/5 r j(-z)0(5M+1)/3－ M0(－7M+4)/30－ 4-2M － 4x1101/503/5－ 1/53/51/3－ 1x201－ 3/50－ 4/53/56/5－0x400【 1】11100 r j(-z)001/50－ M+8/5－ M-1/5－18/5－ 4x1100－ 1/52/503/5－ 1x20103/5－ 1/506/50x300111－ 10r j(-z)000－1/5－ M+7/5－ M－18/5表中所有检验数 r j0,根据最优解定理，问题存在唯一的最优解36T ，目标函X (, ,0,0,0,0)55数的最优值 maxz43618 。