运筹学练习题分析

运筹学部分课后习题解答P47 1.1 用图解法求解线性规划问题a）12121212min z=23466 ..424,0x xx xs t x xx x++≥⎧⎪+≥⎨⎪≥⎩解：由图1可知，该问题的可行域为凸集MABCN，且可知线段BA上的点都为最优解，即该问题有无穷多最优解，这时的最优值为min 3z=23032⨯+⨯= P47 1.3 用图解法和单纯形法求解线性规划问题a）12121212max z=10x5x349 ..528,0x xs t x xx x++≤⎧⎪+≤⎨⎪≥⎩解：由图1可知，该问题的可行域为凸集OABCO，且可知B点为最优值点，即112122134935282xx xx x x=⎧+=⎧⎪⇒⎨⎨+==⎩⎪⎩，即最优解为*31,2Tx⎛⎫= ⎪⎝⎭这时的最优值为max335z=101522⨯+⨯=单纯形法： 原问题化成标准型为121231241234max z=10x 5x 349..528,,,0x x x s t x x x x x x x +++=⎧⎪++=⎨⎪≥⎩ j c →10 5B CB Xb 1x2x3x4x0 3x 9 3 4 1 0 04x8[5] 2 0 1 j j C Z -105 0 0 0 3x 21/5 0 [14/5] 1 -3/5 101x8/51 2/5 0 1/5 j j C Z -1 0 -2 5 2x 3/2 0 1 5/14 -3/14 101x11 0 -1/72/7j j C Z --5/14 -25/14所以有*max 33351,,1015222Tx z ⎛⎫==⨯+⨯= ⎪⎝⎭P78 2.4 已知线性规划问题：1234124122341231234max24382669,,,0z x x x x x x x x x x x x x x x x x x x =+++++≤⎧⎪+≤⎪⎪++≤⎨⎪++≤⎪≥⎪⎩求: (1) 写出其对偶问题；（2）已知原问题最优解为)0,4,2,2(*=X ，试根据对偶理论，直接求出对偶问题的最优解。

运筹学 试卷B 及参考答案（本题20分）一、考虑下面的线性规划问题：Min z=6X 1+4X 2约束条件： 2X 1+X 2 ≥13X 1+4X 2≥3 X 1 , X 2 ≥ 0(1) 用图解法求解,并指出此线型规划问题是具有惟一最优解、无穷多最优解、无界解或无可行解；(2) 写出此线性规划问题的标准形式； (3) 求出此线性规划问题的两个剩余变量的值； (4) 写出此问题的对偶问题。

解：（1）阴影部分所示ABC 即为此线性规划问题的可行域。

其中，A （0，1），B （1，3/4），C （1/5，3/5）。

显然，C （1/5，3/5）为该线性规划问题的最优解。

因此，该线性规划问题有唯一最优解，最优解为：121/5,3/5,*18/5x x z ===。

——8分。

说明：画图正确3分；求解正确3分；指出解的情况并写出最优解2分。

（2）标准形式为：121231241234min 6421343,,,0z x x x x x x x x x x x x =++-=⎧⎪+-=⎨⎪≥⎩ X 1 X 2 AB——4分 （3）两个剩余变量的值为：340x x =⎧⎨=⎩——3分（4）直接写出对偶问题如下：12121212max '323644,0z y y y y y y y y =++≤⎧⎪+≤⎨⎪≥⎩——5分（本题10分）二、前进电器厂生产A 、B 、C 三种产品，有关资料下表所示：学模型，不求解）解：设生产A 、B 、C 三种产品的数量分别为x 1，x 2和x 3，则有：——1分123123123123123max 810122.0 1.5 5.030002.0 1.5 1.21000200250100,,0z x x x x x x x x x x x x x x x =++++≤⎧⎪++≤⎪⎪≤⎪⎨≤⎪⎪≤⎪≥⎪⎩ ——14分，目标函数和每个约束条件2分（本题10分）三、某电子设备厂对一种元件的年需求为2000件，订货提前期为零，每次订货费为25元。

《运筹学基础》试题分析《运筹学基础》是全国高等教育自学考试计算机信息管理专业的专业基础课。

建设信息系统需要综合性的知识，信息管理专业的学生必须兼有企业管理、统计等经济管理方面的知识。

俗话说“试题就是最好的复习资料”。

下面结合2010年4月和7月高等教育自学考试运筹学试题，分析一下这门课的试题特点与应对方法。

一、题型及分值分布对试题题型的充分了解，可以帮助大家有针对性的进行复习。

本试题可分为四种题型：单项选择题（15分）、填空题（10分）、名称解释（15分）、计算题（60分）。

从试题分布来看，计算题为重中之重，所以在学习和复习时在计算题要多下功夫，下面针对2010年7月试题中关键知识点所在的章节，每章的题量、分值分布统计如下。

教材：《运筹学基础》，2002填空几乎每章都有，名词解释由于题量限制，只选取了五章的名词解释，计算题量大，且每章都有几个题型，占了60%的分值，所以在学习和复习时平均用力的同时，对计算题应该有所侧重。

二、试卷题型分析下面就2010年4月和7月的全国试题做一下分析。

1、单项选择题（本大题共15小题，每小题1分，共15分）单项选择题是对基础知识的考察，是掌握本章内容必须掌握的知识，是相对比较简单的一类题，在学习过程中要学会对比总结。

很多知识点是“知道了就会，不知道就不会”的题目，所以考生学习和复习时要全面系统。

例1：特尔斐法的预测过程因为要经过几轮信息反馈，进行预测的时间比较长，因而适用于(A )A.长期或中期预测B.中期或短期预测C.短期预测D.近期预测本题考察的是预测方法的使用范围，我们知道预测方法分定性预测和定量预测，定性预测主要讲了特尔斐法和专家座谈法，定性预测主要讲了时间预测法和回归分析法。

其中特尔斐法由于统一性、匿名性、反馈性的特点适用于中期或长期预测，专家座谈法预测程序比较紧凑，适用于短期预测；时间序列法准确性较差，适于短期预测。

这样由一个题进行举一反三，我们可以系统掌握更多的相关知识。

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

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

3、“如果线性规划的原问题存在可行解，则其对偶问题一定存在可行解”，这句话对还是错？ 错4、如果某一整数规划： MaxZ=X 1+X 2X 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的，所以最优解不变。

(一)线性规划建模与求解B.样题：活力公司准备在5小时内生产甲、乙两种产品。

甲、乙两种产品每生产1单位分别消耗2小时、1小时。

又根据市场需求信息，乙产品的产量应该至少是甲产品产量的3倍。

已知甲、乙两种产品每销售1单位的利润分别为3百元和1百元。

请问：在5小时内，甲、乙两种产品各生产多少单位，才能够使得总销售利润最大？要求：1、建立该问题的线性规划模型。

2、用图解法求出最优解和最大销售利润值，并写出解的判断依据。

如果不存在最优解，也请说明理由。

解：1、(1)设定决策变量：设甲、乙两种产品分别生产x 1、x 2单位。

(2)目标函数： max z=2 x 1+x 2(3)约束条件如下：12211225..3,0+≤⎧⎪≥⎨⎪≥⎩x x s t x x x x2、该问题中约束条件、目标函数、可行域和顶点见图1所示，其中可行域用阴影部分标记，不等式约束条件及变量约束要标出成立的方向，目标函数只须画出其中一条等值线，结论：本题解的情形是： 无穷多最优解 ，理由： 目标函数等值线z=2 x 1+x 2与约束条件2 x 1+x 2≤5的边界平行。

甲、乙两种产品的最优产量分别为 (5,0)或(1,3)单位；最大销售利润值等于 5 百元。

（二）图论问题的建模与求解样题A.正考样题（最短路问题的建模与求解，清华运筹学教材编写组第三版267-268页例13）某企业使用一台设备，每年年初，企业都要做出决定，如果继续使用旧的，要付维修费；若购买一台新设备，要付购买费。

但是变卖旧设备可以获得残值收入，连续使用1年、2年、3年、4年以上卖掉的设备残值分别为8万元、6万元、3万元和0万元。

试制定一个5年的更新计划，使总支出最少。

已知设备在各年的购买费与维修费如表2所示。

要求：（1）建立某种图论模型；（2）求出最少总支出金额。

解：（1）建立图论——最短路问题模型。

①设点V i 表示第i 年年初，虚设一个点V 6，表示第五年年底；②弧(V i , V j )表示第i 年初购进一台设备一直使用到第j 年初(即第i-1年年底)再卖掉并获得残值收入；③弧(V i , V j )上的权数表示第i 年初购进一台设备，一直使用到第j 年初所需支付的购买、维修及抵扣残值收入以后的全部费用（单位：万元）。

运筹学练习：一、判断（√）1、线性规划问题中，必须有一个要实现的目标。

（×）2、在基可行解中基变量一定为非零。

（√）3、如果一个线性规划问题有两个不同的最优解，则它有无穷多个最优解。

（√）4、在用单纯形法解线性规划问题时，任何一个人工变量都不应该在最优解的基变量组合中。

（×）5、如果一个线性规划问题有可行解，则它必有最优解。

（√）6、运输问题中，用闭回路法和用位势法算出的检验数是一样的。

（√）7、运输问题模型是一种特殊的线性规划模型，因而运输问题也可用单纯形法求解。

（×）8、运输问题的运价表的某一行的所有ij c 同乘以一个非零常数，其最优调运方案不变。

（√）9、运输表中给出初始基可行解后，从每一空格出发的闭回路是唯一的。

（×）10、不平衡运输问题不一定有最优解。

二、填空１、线性规划是试图合理地分配各种 资源 以最优地实现某个 目标 的规划方法。

２、标准线性规划问题的特点是：（1）要求目标函数 极大化 ，（2）约 束条件取 等式 ，（3）变量 为非负 。

３、在线性规划问题的图解法中，如果存在最优解，则这个最优解将处于 可行域的 顶点处 。

４、解总运费最小的运输问题时，确定最优解的条件是：所有非基变量的 检验数均不为 负 数。

５、解运输问题一般采用 表上作业 法，确定检验数的方法有 闭回路法和 用位势法 三、简答题1、试用图解法求解下述线性规划问题⎪⎩⎪⎨⎧≥≤+≤++=0,152315322110max 21212121x x x x x x x x z解：先在直角坐标系中作出可行域，再作目标函数的等值线，可以看出，当目标函数的等值线平移到两直线1523,15322121=+=+x x x x 的交点时，目标函数值最大。

即，最优解为：3,321==x x ，2、某商场对售货员的需求情况如下表所示，为保证售货人员充分休息，每周工作五天，休息两天，并要求休息的两天是连续的。

第1章导论【真题演练】1、（12年4月）借助于某些正规的计量方法而做出的决策，称为( A )A．定量决策 B．定性决策 C．混合性决策 D．满意决策2、（12年4月）利用直观材料，依靠个人经验的主观判断和分析能力，对未来的发展进行预测属于( c )A．经济预测 B．科技预测 C．定性预测 D．定量预测3、（11年7月）根据决策人员的主观经验或知识而制定的决策，称之为( B )A.定量决策B.定性决策C.混合性决策D.满意决策4、（12年4月）对于管理领域，运筹学也是对管理决策工作进行决策的___计量___方法。

5、（11年7月）运筹学应用多种分析方法，对各种可供选择的方案进行比较评价，为制定最优的管理决策提供___数量___上的依据。

6、（11年4月）作为运筹学应用者，接受管理部门的要求，收集和阐明数据，建立和试验_数学模型_，预言未来作业，然后制定方案，并推荐给经理部门。

7、（10年7月）运筹学把复杂的功能关系表示成_数学模型_，以便通过定量分析为决策提供数量依据。

8、（10年4月）在当今信息时代，运筹学和信息技术方法的分界线将会____消失____，并将脱离各自原来的领域，组合成更通用更广泛的管理科学的形式。

9、（09年7月）决策方法一般分为定性决策、定量决策、___混合型决策___三类。

10、（09年4月）运筹学是一门研究如何有效地组织和管理____人机系统____的科学。

11、（09年4月）名词解释：定性预测12、（11年7月）名词解释：定量预测【同步练习】1、运筹学研究和运用的模型，不只限于数学模型，还有用___符号___表示的模型和___抽象___的模型。

2、在某公司的预算模型中，__收益表__是显示公司效能的模型，___平衡表__是显示公司财务情况的模型。

3、运筹学工作者观察待决策问题所处的环境应包括___内部___环境和___外部___环境。

4、企业领导的主要职责是___作出决策___，首先确定问题，然后__制定目标___，确认约束条件和估价方案，最后选择___最优解___。

运筹学考研真题及答案运筹学考研真题及答案一、选择题1. 在线性规划中，若最优化问题的对偶问题有最优解，则原始问题也有最优解。

（正确）解析：线性规划理论中对偶定理：“若原始问题的对偶问题有可行解，且存在最优解，则原始问题也有最优解。

”2. 若在线性规划的单纯形法中，某一回路上的所有非基变量（非基变量为0）均为0，则这一问题无有限最优解。

（错误）解析：所有非基变量为0时，相应的基变量可以任意非负，问题有无穷多最优解。

3. 在线性规划中，若某元组在原始问题和对偶问题下都是可行解，则该元组是原始问题和对偶问题的最优解。

（错误）解析：若某元组在原始问题和对偶问题下都是可行解，则该元组满足原始问题的可行性和对偶问题的可行性，但并不一定是最优解。

4. 线性规划的最优性条件是原始问题的可行解和对偶问题的可行解所对应的目标函数值相等。

（正确）解析：线性规划理论中最优性条件：“若原始问题的可行解与对偶问题的可行解所对应的目标函数值相等，则解是原始问题和对偶问题的最优解。

”5. 线性规划的可行性要求约束条件为不等式约束。

（错误）解析：线性规划的可行性要求是所有约束条件都满足，包括等式约束和不等式约束。

二、填空题1. 与线性规划的相对论证法相对应的是（单纯形法）。

解析：线性规划的相对论证法和单纯形法是互为相对的两种求解方法。

2. 在线性规划中，若最优差异为0，则最优解是（非唯一）。

解析：最优差异为0意味着最优解是非唯一的，有多个最优解。

3. 线性规划的最优性条件是（对偶定理）与最优条件相对应。

解析：线性规划的最优性条件是对偶定理，而最优条件是原始问题的可行解和对偶问题可行解所对应的目标函数值相等。

4. 在线性规划中，若一个可行解在原始问题和对偶问题下都是最优解，则称为（互补性）条件。

解析：若一个可行解在原始问题和对偶问题下都是最优解，则满足互补性条件。

三、应用题1.某公司生产两种产品A和B，每个产品的制造工序及所需时间如下表，在一天内，公司有8小时的工时可用，每个工序只能由一名员工负责完成。

运筹学课后习题及答案运筹学是一门应用数学的学科，旨在通过数学模型和方法来解决实际问题。

在学习运筹学的过程中，课后习题是非常重要的一部分，它不仅可以帮助我们巩固所学的知识，还可以提升我们的解决问题的能力。

下面，我将为大家提供一些运筹学课后习题及答案，希望对大家的学习有所帮助。

1. 线性规划问题线性规划是运筹学中的一个重要分支，它旨在寻找线性目标函数下的最优解。

以下是一个线性规划问题的例子：Max Z = 3x + 4ySubject to:2x + 3y ≤ 10x + y ≥ 5x, y ≥ 0解答：首先，我们可以画出约束条件的图形，如下所示：```y^|5 | /| /| /| /|/+-----------------10 x```通过观察图形，我们可以发现最优解点是(3, 2)，此时目标函数取得最大值为Z = 3(3) + 4(2) = 17。

2. 整数规划问题整数规划是线性规划的一种扩展，它要求变量的取值必须是整数。

以下是一个整数规划问题的例子：Max Z = 2x + 3ySubject to:x + y ≤ 52x + y ≤ 8x, y ≥ 0x, y为整数解答：通过计算，我们可以得到以下整数解之一：x = 2, y = 3此时，目标函数取得最大值为Z = 2(2) + 3(3) = 13。

3. 网络流问题网络流问题是运筹学中的另一个重要分支，它研究的是在网络中物体的流动问题。

以下是一个网络流问题的例子：有一个有向图，其中有三个节点S、A、B和一个汇点T。

边的容量和费用如下所示：S -> A: 容量为2，费用为1S -> B: 容量为3，费用为2A -> T: 容量为1，费用为1B -> T: 容量为2，费用为3A -> B: 容量为1，费用为1解答：通过使用最小费用最大流算法，我们可以找到从源点S到汇点T的最小费用流量。

在该例中，最小费用为5，最大流量为3。

第一部分绪论第二部分线性规划与单纯形法1 判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同,但从几何上理解,两者是一致的；(b)线性规划模型中增加一个约束条件,可行域的范围一般将缩小,减少一个约束条件,可行域的范围一般将扩大；(c)线性规划问题的每一个基解对应可行域的一个顶点；(d)如线性规划问题存在可行域,则可行域一定包含坐标的原点；(e)对取值无约束的变量x i,通常令其中,在用单纯形法求得的最优解中有可能同时出现(f)用单纯形法求解标准型的线性规划问题时,与对应的变量都可以被选作换入变量；(g)单纯形法计算中,如不按最小比值原则选取换出变量,则在下一个解中至少有一个基变量的值为负；(h)单纯形法计算中,选取最大正检验数δk对应的变量x k作为换入变量,将使目标函数值得到最快的增长；(i)一旦一个人工变量在迭代中变为非基变量后,则该变量及相应列的数字可以从单纯形表中删除,而不影响计算结果；(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；(k)若x1,x2分别是某一线性规划问题的最优解,则也是该线性规划问题的最优解,其中λ1,λ2可以为任意正的实数；(1)线性规划用两阶段法求解时,第一阶段的目标函数通常写为X ai为人工变量),但也可写为,只要所有k i均为大于零的常数；(m)对一个有n个变量、m个约束的标准型的线性规划问题,其可行域的顶点恰好为个；(n)单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行解；(o)线性规划问题的可行解如为最优解,则该可行解一定是基可行解；(p)若线性规划问题具有可行解,且其可行域有界,则该线性规划问题最多具有有限个数的最优解；(q)线性规划可行域的某一顶点若其目标函数值优于相邻的所有顶点的目标函数值,则该顶点处的目标函数值达到最优；(r)将线性规划约束条件的“≤”号及“≥”号变换成“＝”号,将使问题的最优目标函数值得到改善；(s)线性规划目标函数中系数最大的变量在最优解中总是取正的值；(t)一个企业利用3种资源生产4种产品,建立线性规划模型求解得到的最优解中,最多只含有3种产品的组合；(u)若线性规划问题的可行域可以伸展到无限,则该问题一定具有无界解；(v)一个线性规划问题求解时的迭代工作量主要取决于变量数的多少,与约束条件的数量关系相对较小。