单纯形法中右端项小于等于零，是否可以通过乘-1来解决？_运筹学吧_百度贴吧
&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&&签到排名：今日本吧第个签到，本吧因你更精彩，明天继续来努力！
本吧签到人数：0成为超级会员，使用一键签到本月漏签0次！成为超级会员，赠送8张补签卡连续签到：天&&累计签到：天超级会员单次开通12个月以上，赠送连续签到卡3张
关注：1,866贴子：
单纯形法中右端项小于等于零，是否可以通过乘-1来解决？收藏
做题时碰到这么一个题，计算过程检验数大于零但是右端项小于零，和平时做的不一样，也不能用对偶单纯形法解。然后我考虑到因为行列式是不变的，右端项小于零的那一行乘一个负数就大于零了，再换进去一个新的基变量，然后我这种做法被老师喷了。。。。。。但是得出的答案是完全正确的，于是求大神指教这样的问题该怎么解？看了几本教材（不多）好像都默认不存在计算过程中会有右端项小于等于零的情况。这算特例么？附题如下：maxz=2x1-x2+2x3st:x1+x2+x3&=6-2x1+x3&=22x2-x3&=0xj&=0单纯性法计算过程中出现b小于零的过程，该如何处理？
1楼 18:54&|
相关的贴子896318374相关的图贴
一般来说，右端项小于零的话，应该可以用对偶单纯形法做的，明天帮你看看哈
2楼 01:15&|来自
一般来说，右端项小于零的话，应该可以用对偶单纯形法做的，明天帮你看看哈
3楼 01:15&|来自
换决策变量
4楼 09:14&|来自
maxz= 2X1-X2+2X3 -Mx4-Mx5-Mx6st { X1+X2+X3+x4=6 -2X1 +X3 +x5=2 2X2-X3 +x6=0 X1、X2、X3,x4,x5,x6&=0}cj 2 -1 2 -M -M -MCB 基 b x1 x2 x3 x4 x5 x6 θ-M X4 6 1 [ 1 ] 1 1 0 0 6-M X5 2 -2 0 1 0 1 0 --M X6 0 0 2 -1 0 0 1 -cj-zj 2-M 3M-1 M+2 0 0 0 0
{大M法}-1 x2 6 1 1 1 1 0 0 -M x5 2 -2 0 1 0 1 0-M x6 -12 -2 0 -3 -2 0 1cj-zj 3-4M 0 3-2M 1-3M 0 0最优解：x*=(0,6,0,0,2,-12)因为cj-zj&0，计算停止且人工变量x5=2&0所以该问题为无界解。
收起回复5楼 10:20&|
登录百度帐号我的游戏推荐游戏
后查看最近玩过的游戏
内&&容:使用签名档&&
想了解更多关于 ”运筹学“的信息,请&或《运筹学》复习题及参考答案 运筹学》第一章 运筹学概念 一、填空题 1．运筹学的主要研究对象是各种有组织系统的管理问题，经营活动。 2．运筹学的核心主要是运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据。 3．模型是一件实际事物或现实情况的代表或抽象。 4 通常对问题中变量值的限制称为约束条件，它可以表示成一个等式或不等式的集合。 5．运筹学研究和解决问题的基础是最优化技术，并强调系统整体优化功能。运筹学研究和解决问题的效 果具有连续性。 6．运筹学用系统的观点研究功能之间的关系。 7．运筹学研究和解决问题的优势是应用各学科交叉的方法，具有典型综合应用特性。 8．运筹学的发展趋势是进一步依赖于_计算机的应用和发展。 9．运筹学解决问题时首先要观察待决策问题所处的环境。 10．用运筹学分析与解决问题，是一个科学决策的过程。 11.运筹学的主要目的在于求得一个合理运用人力、物力和财力的最佳方案。 12．运筹学中所使用的模型是数学模型。用运筹学解决问题的核心是建立数学模型，并对模型求解。 13 用运筹学解决问题时，要分析，定议待决策的问题。 14．运筹学的系统特征之一是用系统的观点研究功能关系。 15.数学模型中， “s·t”表示约束。 16．建立数学模型时，需要回答的问题有性能的客观量度，可控制因素，不可控因素。 17．运筹学的主要研究对象是各种有组织系统的管理问题及经营活动。 18. 1940 年 8 月，英国管理部门成立了一个跨学科的 11 人的运筹学小组，该小组简称为 OR。 二、单选题 1． 建立数学模型时，考虑可以由决策者控制的因素是（ A ） A．销售数量 B．销售价格 C．顾客的需求 D．竞争价格 2．我们可以通过（ C ）来验证模型最优解。 A．观察 B．应用 C．实验 D．调查 3．建立运筹学模型的过程不包括（ A ）阶段。 A．观察环境 B．数据分析 C．模型设计 D．模型实施 4.建立模型的一个基本理由是去揭晓那些重要的或有关的（ B ） A 数量 B 变量 C 约束条件 D 目标函数 5.模型中要求变量取值（ D ） A 可正 B 可负 C 非正 D 非负 6.运筹学研究和解决问题的效果具有（ A ） A 连续性 B 整体性 C 阶段性 D 再生性 7.运筹学运用数学方法分析与解决问题，以达到系统的最优目标。可以说这个过程是一个（C） A 解决问题过程 B 分析问题过程 C 科学决策过程 D 前期预策过程 8.从趋势上看，运筹学的进一步发展依赖于一些外部条件及手段，其中最主要的是（ C ） A 数理统计 B 概率论 C 计算机 D 管理科学 9.用运筹学解决问题时，要对问题进行（ B ） A 分析与考察 B 分析和定义 C 分析和判断 D 分析和实验 三、多选 1 模型中目标可能为（ ABCDE ） A 输入最少 B 输出最大 C 成本最小 D 收益最大 E 时间最短 2 运筹学的主要分支包括（ ABDE ） A 图论 B 线性规划 C 非线性规划 D 整数规划 E 目标规划 四、简答 1．运筹学的计划法包括的步骤。 答：观察、建立可选择的解、用实验选择最优解、确定实际问题 2．运筹学分析与解决问题一般要经过哪些步骤? 答： 一、观察待决策问题所处的环境 二、分析和 定义待决策的问题 三、拟订模型 四、选择输入数据 五、求解并验证解的合理性 六、实施最优解 3．运筹学的数学模型有哪些优缺点? 答：优点： ．通过模型可以为所要考虑的问题提供一个参考轮 （1） 廓，指出不能直接看出的结果。 （2） ．花节省时间和费用。 （3） ．模型使人们可以根据过去和现在的信息 进行预测，可用于教育训练，训练人们看到他们决策的结果，而不必作出实际的决策。 4） （ ．数学模型有 能力揭示一个问题的抽象概念，从而能更简明地揭示出问题的本质。 （5） ．数学模型便于利用计算机处理 一个模型的主要变量和因素，并易于了解一个变量对其他变量的影响。 模型的缺点 （1） ．数学模型的缺 点之一是模型可能过分简化，因而不能正确反映实际情况。 （2） ．模型受设计人员的水平的限制，模型无法超越设计人员对问题的理解。 （3） ．创造模型有时需要付出较高的代价。 4．运筹学的系统特征是什么? 答：运筹学的系统特征可以概括为以下四点： 一、用系统的观点研究 功能关系 二、应用各学科交叉的方法 三、采用计划方法 四、为进一步研究揭露新问题 5、线性规划数学模型具备哪几个要素？ 答： （1）.求一组决策变量 xi 或 xij 的值（i =1，2，…m j=1， 2…n）使目标函数达到极大或极小； （2）.表示约束条件的数学式都是线性等式或不等式； （3）.表示问题最 优化指标的目标函数都是决策变量的线性函数 第二章 线性规划的基本概念 一、填空题 1．线性规划问题是求一个线性目标函数_在一组线性约束条件下的极值问题。 2．图解法适用于含有两个变量的线性规划问题。 3．线性规划问题的可行解是指满足所有约束条件的解。 4．在线性规划问题的基本解中，所有的非基变量等于零。 5．在线性规划问题中，基可行解的非零分量所对应的列向量线性无关 6．若线性规划问题有最优解，则最优解一定可以在可行域的顶点（极点）达到。 7．线性规划问题有可行解，则必有基可行解。 8．如果线性规划问题存在目标函数为有限值的最优解，求解时只需在其基可行解_的集合中进行搜索即 可得到最优解。 9．满足非负条件的基本解称为基本可行解。 10．在将线性规划问题的一般形式转化为标准形式时，引入的松驰数量在目标函数中的系数为零。 11．将线性规划模型化成标准形式时，“≤”的约束条件要在不等式左_端加入松弛变量。 12．线性规划模型包括决策（可控）变量，约束条件，目标函数三个要素。 13．线性规划问题可分为目标函数求极大值和极小_值两类。 14．线性规划问题的标准形式中，约束条件取等式，目标函数求极大值，而所有变量必须非负。 15．线性规划问题的基可行解与可行域顶点的关系是顶点多于基可行解 16．在用图解法求解线性规划问题时，如果取得极值的等值线与可行域的一段边界重合，则这段边界上 的一切点都是最优解。 17．求解线性规划问题可能的结果有无解，有唯一最优解，有无穷多个最优解。 18.如果某个约束条件是“≤”情形，若化为标准形式，需要引入一松弛变量。 ′ 〞 ′ 19.如果某个变量 Xj 为自由变量，则应引进两个非负变量 Xj , Xj , 同时令 Xj＝Xj － Xj。 20.表达线性规划的简式中目标函数为 max(min)Z=∑cijxij。 21..(2.1 P5))线性规划一般表达式中，aij 表示该元素位置在 i 行 j 列。 二、单选题 1． 如果一个线性规划问题有 n 个变量，m 个约束方程(m&n)，系数矩阵的数为 m，则基可行解的个数最 为_C_。 m n A．m 个 B．n 个 C．Cn D．Cm 个 2．下列图形中阴影部分构成的集合是凸集的是 A3．线性规划模型不包括下列_ D 要素。 A．目标函数 B．约束条件 C．决策变量 D．状态变量 4．线性规划模型中增加一个约束条件，可行域的范围一般将_B_。 A．增大 B．缩小 C．不变 D．不定 5．若针对实际问题建立的线性规划模型的解是无界的，不可能的原因是 B__。 A．出现矛盾的条件 B．缺乏必要的条件 C．有多余的条件 D．有相同的条件 6．在下列线性规划问题的基本解中，属于基可行解的是 D T T T T A．(一 1，0，O) B．(1，0，3，0) C．(一 4，0，0，3) D．(0，一 1，0，5) 7．关于线性规划模型的可行域，下面_B_的叙述正确。 A．可行域内必有无穷多个点 B．可行域必有界 C．可行域内必然包括原点 D．可行域必是凸的 8．下列关于可行解，基本解，基可行解的说法错误的是_D__. A．可行解中包含基可行解 B．可行解与基本解之间无交集 C．线性规划问题有可行解必有基可行解 D．满足非负约束条件的基本解为基可行解 9.线性规划问题有可行解，则 A A 必有基可行解 B 必有唯一最优解 C 无基可行解 D 无唯一最优解 10.线性规划问题有可行解且凸多边形无界，这时 C A 没有无界解 B 没有可行解 C 有无界解 D 有有限最优解11.若目标函数为求 max，一个基可行解比另一个基可行解更好的标志是 A A 使 Z 更大 B 使 Z 更小 C 绝对值更大 D Z 绝对值更小 12.如果线性规划问题有可行解，那么该解必须满足 D A 所有约束条件 B 变量取值非负 C 所有等式要求 D 所有不等式要求 13.如果线性规划问题存在目标函数为有限值的最优解， 求解时只需在 D 集合中进行搜索即可得到最优解。 A 基 B 基本解 C 基可行解 D 可行域 14.线性规划问题是针对 D 求极值问题. A 约束 B 决策变量 C 秩 D 目标函数 15 如果第 K 个约束条件是“≤”情形，若化为标准形式，需要 B A 左边增加一个变量 B 右边增加一个变量 C 左边减去一个变量 D 右边减去一个变量 16.若某个 bk≤0, 化为标准形式时原不等式 D A 不变 B 左端乘负 1 C 右端乘负 1 D 两边乘负 1 17.为化为标准形式而引入的松弛变量在目标函数中的系数应为 A A 0 B 1 C 2 D 3 12.若线性规划问题没有可行解，可行解集是空集，则此问题 B A 没有无穷多最优解 B 没有最优解 C 有无界解 D 有无界解 三、多选题 1． 在线性规划问题的标准形式中，不可能存在的变量是 D . A．可控变量 B．松驰变量 c．剩余变量 D．人工变量 2．下列选项中符合线性规划模型标准形式要求的有 BCD A．目标函数求极小值 B．右端常数非负 C．变量非负 D．约束条件为等式 E．约束条件为“≤”的不等式 3．某线性规划问题，n 个变量，m 个约束方程，系数矩阵的秩为 m(m&n)则下列说法正确的是 ABDE。 m A． 基可行解的非零分量的个数不大于 mB． 基本解的个数不会超过 C n 个 C． 该问题不会出现退化现象 D． 基 可行解的个数不超过基本解的个数 E．该问题的基是一个 m×m 阶方阵 4．若线性规划问题的可行域是无界的，则该问题可能 ABCD A．无有限最优解 B．有有限最优解 C．有唯一最优解 D．有无穷多个最优解 E．有有限多个最优解 5．判断下列数学模型，哪些为线性规划模型(模型中 a．b．c 为常数；θ为可取某一常数值的参变量，x， Y 为变量) ACDE6．下列模型中，属于线性规划问题的标准形式的是 ACD7．下列说法错误的有_ABD_。 A． 基本解是大于零的解 B．极点与基解一一对应 C．线性规划问题的最优解是唯一的 D．满足约束条件的解就是线性规划的可行解 8.在线性规划的一般表达式中，变量 xij 为 ABE A 大于等于 0 B 小于等于 0 C 大于 0 D 小于 0 E 等于 0 9.在线性规划的一般表达式中，线性约束的表现有 CDE A ＜ B ＞ C ≤ D ≥ E = 10.若某线性规划问题有无界解，应满足的条件有 ADA Pk＜0 B 非基变量检验数为零 C 基变量中没有人工变量 Dδj＞O E 所有δj≤0 11.在线性规划问题中 a23 表示 AE A i =2 B i =3 C i =5 D j=2 E j=3 43.线性规划问题若有最优解，则最优解 AD A 定在其可行域顶点达到 B 只有一个 C 会有无穷多个 D 唯一或无穷多个 E 其值为 0 42.线性规划模型包括的要素有 CDE A．目标函数 B．约束条件 C．决策变量 D 状态变量 E 环境变量 四、名词 1 基：在线性规划问题中，约束方程组的系数矩阵 A 的任意一个 m×m 阶的非奇异子方阵 B，称为线性规 划问题的一个基。 2、线性规划问题：就是求一个线性目标函数在一组线性约束条件下的极值问题。 3 .可行解：在线性规划问题中，凡满足所有约束条件的解称为线性规划问题可行解 4、行域：线性规划问题的可行解集合。 5、本解：在线性约束方程组中，对于选定的基 B 令所有的非基变量等于零，得到的解，称为线性规划问 题的一个基本解。 6.、图解法：对于只有两个变量的线性规划问题，可以用在平面上作图的方法来求解，这种方法称为图解 法。 7、本可行解：在线性规划问题中，满足非负约束条件的基本解称为基本可行解。 8、模型是一件实际事物或实际情况的代表或抽象，它根据因果显示出行动与反映的关系和客观事物的内在 联系。 四、把下列线性规划问题化成标准形式：2、minZ=2x1-x2+2x3五、按各题要求。建立线性规划数学模型 1、某工厂生产 A、B、C 三种产品，每种产品的原材料消耗量、机械台时消耗量以及这些资源的限量，单位 产品的利润如下表所示：根据客户订货，三种产品的最低月需要量分别为 200，250 和 100 件，最大月销售量分别为 250，280 和 120 件。月销售分别为 250，280 和 120 件。 问如何安排生产计划，使总利润最大。2、某建筑工地有一批长度为 10 米的相同型号的钢筋，今要截成长度为 3 米的钢筋 90 根，长度为 4 米的钢 筋 60 根，问怎样下料，才能使所使用的原材料最省?1． 某运输公司在春运期间需要 24 小时昼夜加班工作，需要的人员数量如下表所示： 起运时间 2—6 6—10 10一14 14—18 18—22 22—2 最少? 服务员数 4 8 10 7 12 4每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数第三章线性规划的基本方法一、填空题 1．线性规划的代数解法主要利用了代数消去法的原理，实现基可行解的转换，寻找最优解。 － － 2．标准形线性规划典式的目标函数的矩阵形式是_ maxZ=CBB 1b+(CN－CBB 1N)XN 。 3．对于目标函数极大值型的线性规划问题，用单纯型法求解 时，当基变量检验数δj_≤_0 时，当前解为 最优解。 4．用大 M 法求目标函数为极大值的线性规划问题时，引入的人工变量在目标函数中的系数应为－M。 5．在单纯形迭代中，可以根据最终_表中人工变量不为零判断线性规划问题无解。 6．在线性规划典式中，所有基变量的目标系数为 0。 7．当线性规划问题的系数矩阵中不存在现成的可行基时，一般可以加入人工变量构造可行基。8．在单纯形迭代中，选出基变量时应遵循最小比值θ法则。 9．线性规划典式的特点是基为单位矩阵，基变量的目标函数系数为 0。 10．对于目标函数求极大值线性规划问题在非基变量的检验数全部δj≤O、问题无界时，问题无解时情况 下，单纯形迭代应停止。 11． 在单纯形迭代过程中， 若有某个δk&0 对应的非基变量 xk 的系数列向量 Pk_≤0_时， 则此问题是无界的。 12．在线性规划问题的典式中，基变量的系数列向量为单位列向量_ 13.对于求极小值而言，人工变量在目标函数中的系数应取-1 14.(单纯形法解基的形成来源共有三 种 15.在大 M 法中，M 表示充分大正数。 二、单选题 1．线性规划问题 C2．在单纯形迭代中，出基变量在紧接着的下一次迭代中 B 立即进入基底。 A．会 B．不会 C．有可能 D．不一定 3．在单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中 B。 A．不影响解的可行性 B．至少有一个基变量的值为负 C．找不到出基变量 D．找不到进基变量 4．用单纯形法求解极大化线性规划问题中，若某非基变量检验数为零，而其他非基变量检验数全部&0，则 说明本问题 B 。 A．有惟一最优解 B．有多重最优解 C．无界 D．无解 5．线性规划问题 maxZ=CX，AX=b，X≥0 中，选定基 B，变量 Xk 的系数列向量为 Pk，则在关于基 B 的典式中， Xk 的系数列向量为_ D T -1 A．BPK B．B PK C．PKB D．B PK 6．下列说法错误的是 B A． 图解法与单纯形法从几何理解上是一致的 B．在单纯形迭代中，进基变量可以任选 C．在单纯形迭代中，出基变量必须按最小比值法则选取 D．人工变量离开基底后，不会再进基 7.单纯形法当中，入基变量的确定应选择检验数 C A 绝对值最大 B 绝对值最小 C 正值最大 D 负值最小 8.在单纯形表的终表中，若若非基变量的检验数有 0，那么最优解 A A 不存在 B 唯一 C 无穷多 D 无穷大 9.若在单纯形法迭代中，有两个 Q 值相等，当分别取这两个不同的变量为入基变量时，获得的结果将是 C A 先优后劣 B 先劣后优 C 相同 D 会随目标函数而改变 10.若某个约束方程中含有系数列向量为单位向量的变量，则该约束方程不必再引入 C A 松弛变量 B 剩余变量 C 人工变量 D 自由变量 11.在线性规划问题的典式中，基变量的系数列向量为 D A 单位阵 B 非单位阵 C 单位行向量 D 单位列向量 12.在约束方程中引入人工变量的目的是 D A 体现变量的多样性 B 变不等式为等式 C 使目标函数为最优 D 形成一个单位阵 13.出基变量的含义是 D A 该变量取值不变 B 该变量取值增大 C 由 0 值上升为某值 D 由某值下降为 0 14.在我们所使用的教材中对单纯形目标函数的讨论都是针对 B 情况而言的。 A min B max C min + max D min ,max 任选 15.求目标函数为极大的线性规划问题时，若全部非基变量的检验数≤O，且基变量中有人工变量时该问题 有 B A 无界解 B 无可行解 C 唯一最优解 D 无穷多最优解 三、多选题 1． 对取值无约束的变量 xj。通常令 xj=xj’- x”j，其中 xj’≥0，xj”≥0，在用单纯形法求得的最优 解中，可能出现的是 ABC 2．线性规划问题 maxZ=x1+CX2 其中 4≤c≤6，一 1≤a≤3，10≤b≤12，则当_ BC 时，该问题的最优目标函数值分别达 到上界或下界。 A．c=6 a=-1 b=10 B．c=6 a=-1 b=12 C．c=4 a=3 b=12 D．c=4 a=3 b=12 E．c=6 a=3 b=123．设 X ，X 是用单纯形法求得的某一线性规划问题的最优解，则说明 ACDE。 (1) A．此问题有无穷多最优解 B．该问题是退化问题 C．此问题的全部最优解可表示为λX +(1 一 (2) (1) (2) (1) (2) λ)X ，其中 0≤λ≤1 D．X ，X 是两个基可行解 E．X ，X 的基变量个数相同 4．某线性规划问题，含有 n 个变量，m 个约束方程，(m&n)，系数矩阵的秩为 m，则 ABD 。A．该问题的 M 典式不超过 CN 个 B．基可行解中的基变量的个数为 m 个 C．该问题一定存在可行解 D．该问题的基至多有 M CN =1 个 E．该问题有 111 个基可行解 5．单纯形法中，在进行换基运算时，应 ACDE。A．先选取进基变量，再选取出基变量 B．先选出基变量， 再选进基变量 C．进基变量的系数列向量应化为单位向量 D．旋转变换时采用的矩阵的初等行变换 E．出基 变量的选取是根据最小比值法则 6．从一张单纯形表中可以看出的内容有 ABCE。A．一个基可行解 B．当前解是否为最优解 C．线性规划 问题是否出现退化 D．线性规划问题的最优解 E．线性规划问题是否无界 7.单纯形表迭代停止的条件为（ AB ） A 所有δj 均小于等于 0 B 所有δj 均小于等于 0 且有 aik≤0 C 所有 aik＞0 D 所有 bi≤0 8.下列解中可能成为最优解的有（ ABCDE ） A 基可行解 B 迭代一次的改进解 C 迭代两次的改进解 D 迭代三次的改进解 E 所有检验数均小于等于 0 且解中无人工变量 9、若某线性规划问题有无穷多最优解，应满足的条件有（ BCE ） A Pk＜Pk0 B 非基变量检验数为零 C 基变量中没有人工变量 Dδj＜O E 所有δj≤0 10.下列解中可能成为最优解的有（ ABCDE ） A 基可行解 B 迭代一次的改进解 C 迭代两次的改进解 D 迭代三次的改进解 E 所有检验数均小于等于 0 且解中无人工变量 四、名词、简答 1、人造初始可行基：当我们无法从一个标准的线性规划问题中找到一个 m 阶单位矩阵时，通常在约束方 程中引入人工变量，而在系数矩阵中凑成一个 m 阶单位矩阵，进而形成的一个初始可行基称为人造初始可 行基。 2、单纯形法解题的基本思路？ 可行域的一个基本可行解开始，转移到另一个基本可行解，并且使目标函 数值逐步得到改善，直到最后球场最优解或判定原问题无解。 五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的每一步相当于图解法可行 域中的哪一个顶点。(1)(2)六、用单纯形法求解下列线性规划问题：七、用大 M 法求解下列线性规划问题。并指出问题的解属于哪一类。八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 maxZ=5x1+3x2，约束形式为 “≤”，X3，X4 为松驰变量．表中解代入目标函数后得 Z=10 Xl —10 X3 Xl (1)求表中 a～g 的值 （1）a=2 b=0 c=0 d=1 2 a b C d X2 -1 O e X3 f 1 0 X4 g 1／5 1(2)表中给出的解是否为最优解? e=4/5 f=0 g=－5 （2） 表中给出的解为最优解 线性规划的对偶理论第四章一、填空题 1．线性规划问题具有对偶性，即对于任何一个求最大值的线性规划问题，都有一个求最小值/极小值的 线性规划问题与之对应，反之亦然。 2．在一对对偶问题中，原问题的约束条件的右端常数是对偶问题的目标函数系数。 3．如果原问题的某个变量无约束，则对偶问题中对应的约束条件应为等式_。 4．对偶问题的对偶问题是原问题_。 5．若原问题可行，但目标函数无界，则对偶问题不可行。 6．若某种资源的影子价格等于 k。在其他条件不变的情况下(假设原问题的最佳基不变)，当该种资源增 加 3 个单位时。相应的目标函数值将增加 3k 。 ﹡ － 7．线性规划问题的最优基为 B，基变量的目标系数为 CB，则其对偶问题的最优解 Y = CBB 1。 ﹡ ﹡ ﹡ ﹡ 8．若 X 和 Y 分别是线性规划的原问题和对偶问题的最优解，则有 CX = Y b。 9．若 X、Y 分别是线性规划的原问题和对偶问题的可行解，则有 CX≤Yb。 ﹡ ﹡ ﹡ 10．若 X 和 Y 分别是线性规划的原问题和对偶问题的最优解，则有 CX =Y*b。 11．设线性规划的原问题为 maxZ=CX，Ax≤b，X≥0，则其对偶问题为 min=Yb YA≥c Y≥0_。 12．影子价格实际上是与原问题各约束条件相联系的对偶变量的数量表现。 13．线性规划的原问题的约束条件系数矩阵为 A，则其对偶问题的约束条件系数矩阵为 AT 。 14．在对偶单纯形法迭代中，若某 bi&0，且所有的 aij≥0(j=1，2，…n)，则原问题_无解。 二、单选题 1． 线性规划原问题的目标函数为求极小值型， 若其某个变量小于等于 0， 则其对偶问题约束条件为 A 形式。 A．“≥” B． “≤” C，“&” D．“=” 2．设 X 、 Y 分别是标准形式的原问题与对偶问题的可行解,则 C 3．对偶单纯形法的迭代是从_ A_开始的。 。A．正则解 B．最优解 C．可行解 D．基本解 ﹡ 4．如果 z。是某标准型线性规划问题的最优目标函数值，则其对偶问题的最优目标函数值 w A。 ﹡ ﹡ ﹡ ﹡ ﹡ ﹡ ﹡ ﹡ A．W =Z B．W ≠Z C．W ≤Z D．W ≥Z 5．如果某种资源的影子价格大于其市场价格，则说明_ B A．该资源过剩 B．该资源稀缺 C．企业应尽快处理该资源 D．企业应充分利用该资源，开僻新的生产途径 三、多选题 1．在一对对偶问题中，可能存在的情况是 ABC。 A．一个问题有可行解，另一个问题无可行解 B．两个问题都有可行解 C．两个问题都无可行解 D．一个问题无界，另一个问题可行 2．下列说法错误的是 B 。 A．任何线性规划问题都有一个与之对应的对偶问题 B．对偶问题无可行解时，其原问题的目标函数无 界。C．若原问题为 maxZ=CX，AX≤b，X≥0，则对偶问题为 minW=Yb，YA≥C，Y≥0。D．若原问题有可行解， 但目标函数无界，其对偶问题无可行解。 3．如线性规划的原问题为求极大值型，则下列关于原问题与对偶问题的关系中正确的是 BCDE。 A 原问题的约束条件“≥”，对应的对偶变量“≥0” B 原问题的约束条件为“=”，对应的对偶变量 为自由变量 C．原问题的变量“≥0”，对应的对偶约束“≥” D．原问题的变量“≤O”对应的对偶约束 “≤”E．原问题的变量无符号限制，对应的对偶约束“=” 4．一对互为对偶的问题存在最优解，则在其最优点处有 BD A．若某个变量取值为 0，则对应的对偶约束为严格的不等式 B．若某个变量取值为正，则相应的对偶 约束必为等式 C．若某个约束为等式，则相应的对偶变取值为正 D．若某个约束为严格的不等式，则相应的 对偶变量取值为 0 E．若某个约束为等式，则相应的对偶变量取值为 0 5．下列有关对偶单纯形法的说法正确的是 ABCD。 A．在迭代过程中应先选出基变量，再选进基变量 B．当迭代中得到的解满足原始可行性条件时，即得 到最优解 C．初始单纯形表中填列的是一个正则解 D．初始解不需要满足可行性 E．初始解必须是可行的。 6．根据对偶理论，在求解线性规划的原问题时，可以得到以下结论 ACD。 A． 对偶问题的解 B．市场上的稀缺情况 C．影子价格 D．资源的购销决策 E．资源的市场价格 7 ． 在 下 列 线 性 规 划 问 题 中 ， CE 采 用 求 其 对 偶 问 题 的 方 法 ， 单 纯 形 迭 代 的 步 骤 一 般 会 减 少 。四、名词、简答题 1、对偶可行基：凡满足条件δ=C-CBB A≤0 的基 B 称为对偶可行基。 2、.对称的对偶问题：设原始线性规划问题为 maxZ=CX 称线性规划问题 minW=Yb s.t AX≤b X ≥0 s.t YA≥C Y≥0 为其对偶问题。又称它们为一对对称的对偶问题。-13、影子价格：对偶变量 Yi 表示与原问题的第 i 个约束条件相对应的资源的影子价格，在数量上表现为，当 该约束条件的右端常数增加一个单位时（假设原问题的最优解不变） ，原问题目标函数最优值增加的数量。 4．影子价格在经济管理中的作用。 （1）指出企业内部挖潜的方向； （2）为资源的购销决策提供依据； （3） 分析现有产品价格变动时资源紧缺情况的影响； （4）分析资源节约所带来的收益； （5）决定某项新产品是 否应投产。 5．线性规划对偶问题可以采用哪些方法求解？（1）用单纯形法解对偶问题； （2）由原问题的最优单纯形 表得到； （3）由原问题的最优解利用互补松弛定理求得； （4）由 Y*=CBB-1 求得，其中 B 为原问题的最优基 6、一对对偶问题可能出现的情形：1.原问题和对偶问题都有最优解，且二者相等；2.一个问题具有无界解， 则另一个问题具有无可行解；3.原问题和对偶问题都无可行解。 五、写出下列线性规划问题的对偶问题 1．minZ=2x1+2x2+4x3六、已知线性规划问题应用对偶理论证明该问题最优解的目标函数值不大于 25七、已知线性规划问题 maxZ=2x1+x2+5x3+6x4其对偶问题的最优解为 Yl =4，Y2 =1，试应用对偶问题的性质求原问题的最优解。﹡﹡七、用对偶单纯形法求解下列线性规划问题：八、已知线性规划问题(1) 写出其对偶问题 的最优解。(2)已知原问题最优解为 X﹡=(2，2，4，0) ，试根据对偶理论，直接求出对偶问题TW* 第五章 线性规划的灵敏度分析= 16一、填空题 1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。 2、在线性规划的灵敏度分析中，我们主要用到的性质是_可行性，正则性。 3．在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。 4．如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。 5．约束常数 b；的变化，不会引起解的正则性的变化。 6．在某线性规划问题中，已知某资源的影子价格为 Y1，相应的约束常数 b1，在灵敏度容许变动范围内发生 Δb1 的变化，则新的最优解对应的最优目标函数值是 Z*+yi△b (设原最优目标函数值为 Z﹡) 7．若某约束常数 bi 的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对 偶单纯形法求解。 8．已知线性规划问题，最优基为 B，目标系数为 CB，若新增变量 xt，目标系数为 ct，系数列向量为 Pt，则 － 当 Ct≤CBB 1Pt 时，xt 不能进入基底。 9．如果线性规划的原问题增加一个约束条件，相当于其对偶问题增加一个变量。 10、若某线性规划问题增加一个新的约束条件，在其最优单纯形表中将表现为增加一行，一列。 11．线性规划灵敏度分析应在最优单纯形表的基础上，分析系数变化对最优解产生的影响 12．在某生产规划问题的线性规划模型中，变量 xj 的目标系数 Cj 代表该变量所对应的产品的利润，则当某 一非基变量的目标系数发生增大变化时，其有可能进入基底。 二、单选题 1．若线性规划问题最优基中某个基变量的目标系数发生变化，则 C。 A．该基变量的检验数发生变化 B．其他基变量的检验数发生变化 C．所有非基变量的检验数发生变化 D．所有变量的检验数都发生变化 2．线性规划灵敏度分析的主要功能是分析线性规划参数变化对 D 的影响。 A．正则性 B．可行性 C．可行解 D．最优解 3．在线性规划的各项敏感性分析中，一定会引起最优目标函数值发生变化的是 B。 A．目标系数 cj 的变化 B．约束常数项 bi 变化 C．增加新的变量 D．增加新约束 4．在线性规划问题的各种灵敏度分析中，B_的变化不能引起最优解的正则性变化。A．目标系数 B．约束常数 C．技术系数 D．增加新的变量 E．增加新的约束条件 5．对于标准型的线性规划问题，下列说法错误的是 C A．在新增变量的灵敏度分析中，若新变量可以进入基底，则目标函数将会得到进一步改善。B．在增 加新约束条件的灵敏度分析中，新的最优目标函数值不可能增加。C．当某个约束常数 bk 增加时，目标函数 值一定增加。D．某基变量的目标系数增大，目标函数值将得到改善 6.灵敏度分析研究的是线性规划模型中最优解和 C 之间的变化和影响。 A 基 B 松弛变量 C 原始数据 D 条件系数 三、多选题 1．如果线性规划中的 cj、bi 同时发生变化，可能对原最优解产生的影响是_ ABCD. A．正则性不满足，可行性满足 B．正则性满足，可行性不满足 C．正则性与可行性都满足 D．正则性与 可行性都不满足 E．可行性和正则性中只可能有一个受影响 2．在灵敏度分析中，我们可以直接从最优单纯形表中获得的有效信息有 ABCE。 -1 A．最优基 B 的逆 B B．最优解与最优目标函数值 C．各变量的检验数 D．对偶问题的解 E．各列向量 3．线性规划问题的各项系数发生变化，下列不能引起最优解的可行性变化的是 ABC_。 A．非基变量的目标系数变化 B．基变量的目标系数变化 C．增加新的变量 D，增加新的约束条件 4．下列说法错误的是 ACD -1 A．若最优解的可行性满足 B b≥0，则最优解不发生变化 B．目标系数 cj 发生变化时，解的正则性将受 到影响 C．某个变量 xj 的目标系数 cj 发生变化，只会影响到该变量的检验数的变化 D．某个变量 xj 的目标 系数 cj 发生变化，会影响到所有变量的检验数发生变化。 四、名词、简答题 1.灵敏度分析：研究线性规划模型的原始数据变化对最优解产生的影响 2．线性规划问题灵敏度分析的意义。 （1）预先确定保持现有生产规划条件下，单位产品利润的可变范围； （2）当资源限制量发生变化时，确定新的生产方案； （3）确定某种新产品的投产在经济上是否有利； （4） 考察建模时忽略的约束对问题的影响程度； （5）当产品的设计工艺改变时，原最优方案是否需要调整。 四、某工厂在计划期内要安排生产 I、Ⅱ两种产品。已知生产单位产品所需的设备台时及 A、B 两种原料的 消耗如表所示： I 设备 原材料A 原材料B 1 4 0 Ⅱ 2 0 4 8台时 16kg 12kg该工厂每生产一件产品 I 可获利 2 百元，每生产一件产品Ⅱ可获利 3 百元。 (1)单纯形迭代的初始表及最终表分别如下表 I、Ⅱ所示： x1 xB X3 X4 X5-Zx2 3 2 0 4 0 0 0 1x3 O 1 0 0 -3/2 0 -2 1/2x4 0 O 1 0 -1/8 1/4 1/2 -1/8x5 0 0 0 1 0 0 1 0 (4)0 8 16 12 142 1 4 0 0 1 0 0Xl X5 X24 4 2说明使工厂获利最多的产品混合生产方案。 (2)如该厂从别处抽出 4 台时的设备用于生产 I、Ⅱ，求这 时该厂生产产品 I、Ⅱ的最优方案。 (3)确定原最优解不变条件下，产品Ⅱ的单位利润可变范围。 可获利 5 百元，问该厂是否应生产该产品及生产多少? (1)使工厂获利最多的产品混合生产方案：生产 I 产品 4 件，生产 II 产品 2 件，设备台时与原材料 A 全部用 完，原材料 B 剩余 4kg，此时，获利 14 百元。 生产产品Ⅲ，产量为 2。 (2)X*=(4，3,2，0，o)Tz*=17 (3)0≤C2≤4 (4)应 该厂预备引进一种新产品Ⅲ，已知生产每件产品Ⅲ，需消耗原材料 A、B 分别为 6kg，3kg 使用设备 2 台时，五、给出线性规划问题用单纯形表求解得单纯形表如下，试分析下列各种条件变化下最优解(基)的变化： xB xl x2 -8 1 2 xl 0 1 0 x2 0 0 1 x3 -3 -1 2 x4 -5 4 -1 x5 -1 -1 1-Z(1)分别确定目标函数中变量 X1 和 X2 的系数 C1，c2 在什么范围内变动时最优解不变； (2)目标函数中 变量 X3 的系数变为 6； (3)增添新的约束 X1+2x2+x3≤4 解：(1)3/4≤C1≤3 2≤C2≤8 (2)X*=(2，0，1，0，0，0)T Z*=10 T (3)X*=(2，1，0，0，1，0) Z*=7 (4)X*=(0，2，0，0，0，1/3)T Z*=25/3 第六章 物资调运规划运输问题 一、填空题 1． 物资调运问题中， m 个供应地， l， 2…， m， j 的供应量为 ai(i=1， 有 A A A A 2…， n 个需求地 B1， 2， n， m)， B …BmnB 的需求量为 bj(j=1，2，…，n)，则供需平衡条件为∑i =1ai =∑bj =1i2．物资调运方案的最优性判别准则是：当全部检验数非负时，当前的方案一定是最优方案。 3．可以作为表上作业法的初始调运方案的填有数字的方格数应为 m+n－1 个(设问题中含有 m 个供应地 和 n 个需求地) 4．若调运方案中的某一空格的检验数为 1，则在该空格的闭回路上调整单位运置而使运费增加 1。 5．调运方案的调整是要在检验数出现负值的点为顶点所对应的闭回路内进行运量的调整。 6．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到_1 条闭回路 7．在运输问题中，单位运价为 Cij 位势分别用 ui，Vj 表示，则在基变量处有 cij Cij=ui+Vj 。 m n n m 8、供大于求的、供不应求的不平衡运输问题，分别是指 ∑ a i _＞ ∑ bi 的运输问题、 ∑ a i _＜ ∑ bi 的运输 i =1 i =1 j =1 j =1 问题。 10．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。 11．在某运输问题的调运方案中，点(2，2)的检验数为负值，(调运方案为表所示)则相应的调整量应为 300_。 I A B C 600 300 Ⅱ Ⅲ 100 400 300 Ⅳ 30012.若某运输问题初始方案的检验数中只有一个负值： －2， 则这个－2 的含义是该检验数所在格单位调整量。 13.运输问题的初始方案中的基变量取值为正。 。 14 表上作业法中，每一次调整 1 个“入基变量” 15.在编制初始方案调运方案及调整中，如出现退化，则某一个或多个点处应填入数字 016 运输问题的模型中，含有的方程个数为 n+M 个。 17 表上作业法中，每一次调整，“出基变量”的个数为 1 个。 18 给出初始调运方案的方法共有三种。 19.运输问题中，每一行或列若有闭回路的顶点，则必有两个。 二、单选题 1、在运输问题中，可以作为表上作业法的初始基可行解的调运方案应满足的条件是 D。 A．含有 m+n—1 个基变量 B．基变量不构成闭回路 C．含有 m+n 一 1 个基变量且不构成闭回路 D．含有 m+n 一 1 个非零的基变量且不构成闭回 2．若运输问题的单位运价表的某一行元素分别加上一个常数 k，最优调运方案将 B。 A．发生变化 B．不发生变化 C．A、B 都有可能 3．在表上作业法求解运输问题中，非基变量的检验数 D。 A．大于 0B．小于 0C．等于 0D．以上三种都可能 4.运输问题的初始方案中，没有分配运量的格所对应的变量为 B A 基变量 B 非基变量 C 松弛变量 D 剩余变量 5.表上作业法的基本思想和步骤与单纯形法类似，那么基变量所在格为 C A 有单位运费格 B 无单位运费格 C 有分配数格 D 无分配数格 6.表上作业法中初始方案均为 A A 可行解 B 非可行解 C 待改进解 D 最优解 7.闭回路是一条封闭折线，每一条边都是 D A 水平 B 垂直 C 水平＋垂直 D 水平或垂直 8 当供应量大于需求量，欲化为平衡问题，可虚设一需求点，并令其相应运价为 D A 0 B 所有运价中最小值 C 所有运价中最大值 D 最大与最小运量之差 9.运输问题中分配运量的格所对应的变量为 A A 基变量 B 非基变量 C 松弛变量 D 剩余变量 10.所有物资调运问题，应用表上作业法最后均能找到一个 D A 可行解 B 非可行解 C 待改进解 D 最优解 11.一般讲，在给出的初始调运方案中，最接近最优解的是 C A 西北角法 B 最小元素法 C 差值法 D 位势法 12.在运输问题中，调整对象的确定应选择 C A 检验数为负 B 检验数为正 C 检验数为负且绝对值最大 D 检验数为负且绝对值最小 13.运输问题中，调运方案的调整应在检验数为 C 负值的点所在的闭回路内进行。 A 任意值 B 最大值 C 绝对值最大 D 绝对值最小 14.表上作业法的基本思想和步骤与单纯形法类似，因而初始调运方案的给出就相当于找到一个 C A 基 B 可行解 C 初始基本可行解 D 最优解 15 平衡运输问题即是指 m 个供应地的总供应量 D n 个需求地的总需求量。 A 大于 B 大于等于 C 小于 D 等于 三、多选题 1．运输问题的求解结果中可能出现的是 ABC _。 A、惟一最优解 B．无穷多最优解 C．退化解 D．无可行解 2．下列说法正确的是 ABD。 A．表上作业法也是从寻找初始基可行解开始的 B．当一个调运方案的检验数全部为正值时，当前方案 一定是最佳方案 C．最小元素法所求得的运输的运量是最小的 D．表上作业法中一张供需平衡表对应一个 基可行解 3．对于供过于求的不平衡运输问题，下列说法正确的是 ABC。 A．仍然可以应用表上作业法求解 B．在应用表上作业法之前，应将其转化为平衡的运输问题 C．可以虚 设一个需求地点，令其需求量为供应量与需求量之差。D．令虚设的需求地点与各供应地之间运价为 M(M 为 极大的正数) 4．下列关于运输问题模型特点的说法正确的是 ABD A． 约束方程矩阵具有稀疏结构 B． 基变量的个数是 m+n-1 个 C． 基变量中不能有零 D． 基 变量不构成闭回路 5.对于供过于求的不平衡运输问题，下列说法正确的是 ABC A．仍然可以应用表上作业法求解 B．在应用表上作业法之前，应将其转化为平衡的运输问题 C．可以虚设一个需求地点，令其需求量为供应量与需求量之差。 D．令虚设的需求地点与各供应地之间运价为 M(M 为极大的正数) E. 可以虚设一个库存，令其库存量为 0 三、判断表(a)(b)(c)中给出的调运方案能否作为表上作业法求解时的初始解，为什么? (a)Bl Al A2 A3 A4 销量 Bl Al A2 A3 A4 销量 20 20 30 10 40 30 30 B2 20 (b) B3 20B2 10 30B3B4B5B6产量 3020 10 10 50 5 2050 75 20 (c)40 B430 B5 3010 B650 产量 30 5025 Bl Al A2 A3 销量 5 5 4 5 9 3 9 B2 B3 6 B4 5 2 7 产量 11 11 810 20 10 5025 2575 20(a)可作为初始方案；(b)中填有数字的方格数少于 9(产地数+销地数－1)，不能作为初始方案；(c)中存在以非零元素为顶点的闭回路，不能作为初始方案 四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表(a)和(b)，判断给出的调 运方案是否为最优?如是说明理由；如否。也说明理由。 表(a)产销平衡表及某一调运方案 销地 产地l单位运价表Bl 30B2 20 30B3B4B5B6产量 50A2 A3 A4 销量 3010 10 40 10 20 11 1140 60 3150204030五、给出如下运输问题 运价 产 Al A2 A3 销量 5 1 20 30 3 6 10 50 10 9 5 80 4 6 7 40 90 40 70 200销B1B2B3B4产量(1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案六、用表上作业法求给出的运输问题的最优解 甲 1 2 3 销量 10 16 5 5 乙 6 0 4 2 丙 7 5 10 4 丁 12 9 10 6 产量 4 9 4甲 1 2 3 销量 4 5 1乙 2丙 1 3丁产量 469 4246在最优调运方案下的运输费用最小为 118。 七、名词 1、 平衡运输问题：m 个供应地的供应量等于 n 个需求地的总需求量，这样的运输问题称平衡运输问题。 2、不平衡运输问题：m 个供应地的供应量不等于 n 个需求地的总需求量，这样的运输问题称不平衡运输 问题。 第七章 整数规划 一、填空题 1． 用分枝定界法求极大化的整数规划问题时， 任何一个可行解的目标函数值是该问题目标函数值的下界。 2．在分枝定界法中，若选 Xr=4／3 进行分支，则构造的约束条件应为 X1≤1，X1≥2。 3．已知整数规划问题 P0，其相应的松驰问题记为 P0’，若问题 P0’无可行解，则问题 P。无可行解。 4．在 0 - 1 整数规划中变量的取值可能是_0 或 1。 5．对于一个有 n 项任务需要有 n 个人去完成的分配问题，其 解中取值为 1 的变量数为 n 个。 6．分枝定界法和割平面法的基础都是用_线性规划方法求解整数规划。 7．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由 X。所在行得 X1+1／7x3+2 6 1 2 ／7x5=13／7，则以 X1 行为源行的割平面方程为_ － X3－ X5≤0_。 7 7 7 8．在用割平面法求解整数规划问题时，要求全部变量必须都为整数。 9．用割平面法求解整数规划问题时，若某个约束条件中有不为整数的系数，则需在该约束两端扩大适 当倍数，将全部系数化为整数。 10．求解纯整数规划的方法是割平面法。求解混合整数规划的方法是分枝定界法_。 11．求解 0—1 整数规划的方法是隐枚举法。求解分配问题的专门方法是匈牙利法。 12．在应用匈牙利法求解分配问题时，最终求得的分配元应是独立零元素_。 13.分枝定界法一般每次分枝数量为 2 个. 二、单选题 1．整数规划问题中，变量的取值可能是 D。 A．整数 B．0 或 1C．大于零的非整数 D．以上三种都可能 2．在下列整数规划问题中，分枝定界法和割平面法都可以采用的是 A 。 A．纯整数规划 B．混合整数规划 C．0—1 规划 D．线性规划 3．下列方法中用于求解分配问题的是 D_。 A．单纯形表 B．分枝定界法 C．表上作业法 D．匈牙利法 三、多项选择 1．下列说明不正确的是 ABC。 A． 求解整数规划可以采用求解其相应的松驰问题， 然后对其非整数值的解四舍五入的方法得到整数解。 B． 用分枝定界法求解一个极大化的整数规划问题， 当得到多于一个可行解时， 通常任取其中一个作为下界。 C．用割平面法求解整数规划时，构造的割平面可能割去一些不属于最优解的整数解。D．用割平面法求解整数规划问题时，必须首先将原问题的非整数的约束系数及右端常数化为整数。 2．在求解整数规划问题时，可能出现的是 ABC。 A．唯一最优解 B．无可行解 C．多重最佳解 D．无穷多个最优解 3．关于分配问题的下列说法正确的是_ ABD。 A．分配问题是一个高度退化的运输问题 B．可以用表上作业法求解分配问题 C．从分配问题的效 益矩阵中逐行取其最小元素，可得到最优分配方案 D．匈牙利法所能求解的分配问题，要求规定一个人只 能完成一件工作，同时一件工作也只给一个人做。 4.整数规划类型包括（ CDE ） A 线性规划 B 非线性规划 C 纯整数规划 D 混合整数规划 E 0—1 规划 5.对于某一整数规划可能涉及到的解题内容为（ ABCDE ） A 求其松弛问题 B 在其松弛问题中增加一个约束方程 C 应用单形或图解法 D 割去部分 非整数解 E 多次切割 三、名词 1、纯整数规划：如果要求所有的决策变量都取整数，这样的问题成为纯整数规划问题。 2、0—1 规划问题：在线性规划问题中，如果要求所有的决策变量只能取 0 或 1，这样的问题称为 0—1 规 划。 3、混合整数规划：在线性规划问题中，如果要求部分决策变量取整数，则称该问题为混合整数规划。 四、用分枝定界法求解下列整数规划问题：(提示:可采用图解法) maxZ=40x1+90x2五、用割平面法求解六、下列整数规划问题说明能否用先求解相应的线性规划问题然后四舍五入的办法来求得该整数规划的一个可行解。 答：不考虑整数约束，求解相应线性规划得最优解为 x1=10/3，x2=x3=0，用四舍五人法时，令 x1=3， x2=x3=0，其中第 2 个约束无法满足，故不可行。 七、若某钻井队要从以下 10 个可供选择的井位中确定 5 个钻井探油。使总的钻探费用为最小。若 10 个井 位的代号为 S1,S2．…，S10 相应的钻探费用为 C1 ,C2 ,… C10，并且井位选择要满足下列限制条件： (1)在 s1，s2，S4 中至多只能选择两个； (2)在 S5，s6 中至少选择一个；(3)在 s3，s6，S7，S8 中至少选 择两个； 试建立这个问题的整数规划模型八、有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工 作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少? 工作 人 甲 乙 丙 丁 15 19 6 19 18 23 7 21 2l 22 16 23 24 18 19 17 I Ⅱ Ⅲ Ⅳ第八章 一、填空题图与网络分析1．图的最基本要素是点、点与点之间构成的边 2．在图论中，通常用点表示，用边或有向边表示研究对象，以及研究对象之间具有特定关系。 3．在图论中，通常用点表示研究对象，用边或有向边表示研究对象之间具有某种特定的关系。 4．在图论中，图是反映研究对象_之间_特定关系的一种工具。 5．任一树中的边数必定是它的点数减 1。 6．最小树问题就是在网络图中，找出若干条边，连接所有结点，而且连接的总长度最小。 7．最小树的算法关键是把最近的未接_结点连接到那些已接结点上去。 8．求最短路问题的计算方法是从 0≤fij≤cij 开始逐步推算的，在推算过程中需要不断标记平衡和最短路线。 二、单选题 1、关于图论中图的概念，以下叙述(B)正确。 A 图中的有向边表示研究对象，结点表示衔接关系。 B 图中的点表示研究对象，边表示点与点之间的关 系。C 图中任意两点之间必有边。 D 图的边数必定等于点数减 1。 2．关于树的概念，以下叙述(B)正确。 A 树中的点数等于边数减 1 B 连通无圈的图必定是树 C 含 n 个点的树是唯一的 D 任一树中， 去掉一条边仍为树。 3．一个连通图中的最小树(B)，其权(A)。 A 是唯一确定的 B 可能不唯一 C 可能不存在 D 一定有多个。 4．关于最大流量问题，以下叙述(D)正确。 A 一个容量网络的最大流是唯一确定的 B 达到最大流的方案是唯一的 C 当用标号法求最大流时，可能得 到不同的最大流方案 D 当最大流方案不唯一时，得到的最大流量亦可能不相同。 5．图论中的图，以下叙述(C)不正确。 A．图论中点表示研究对象，边或有向边表示研究对象之间的特定关系。B．图论中的图，用点与点的相 互位置，边的长短曲直来表示研究对象的相互关系。C．图论中的边表示研究对象，点表示研究对象之间的 特定关系。 D．图论中的图，可以改变点与点的相互位置。只要不改变点与点的连接关系。 6．关于最小树，以下叙述(B)正确。 A．最小树是一个网络中连通所有点而边数最少的图 B．最小树是一个网络中连通所有的点，而权数最少 的图 C．一个网络中的最大权边必不包含在其最小树内 D．一个网络的最小树一般是不唯一的。 7．关于可行流，以下叙述(A)不正确。 A． 可行流的流量大于零而小于容量限制条件 B． 在网络的任一中间点， 可行流满足流人量=流出量。 各 C． 条有向边上的流量均为零的流是一个可行流 D．可行流的流量小于容量限制条件而大于或等于零。 三、多选题 1．关于图论中图的概念，以下叙述(123)正确。 (1)图中的边可以是有向边，也可以是无向边 (2)图中的各条边上可以标注权。(3)结点数等于边数的 连通图必含圈(4)结点数等于边数的图必连通。 2．关于树的概念，以下叙述(123)正确。 1)树中的边数等于点数减 1(2)树中再添一条边后必含圈。(3)树中删去一条边后必不连通(4)树中两点 之间的通路可能不唯一。 3．从连通图中生成树，以下叙述(134)正确。 (1)任一连通图必有支撑树 (2)任一连通图生成的支撑树必唯一(3)在支撑树中再增加一条边后必含圈 (4)任一连通图生成的各个支撑树其边数必相同 4．在下图中，(abcd)不是根据(a)生成的支撑树。5．从赋权连通图中生成最小树，以下叙述(124)不正确。 (1)任一连通图生成的各个最小树，其总长度必相等(2)任一连通图生成的各个最小树，其边数必相等。 (3)任一连通图中具有最小权的边必包含在生成的最小树上。(4)最小树中可能包括连通图中的最大权边。 6．从起点到终点的最短路线，以下叙述(123)不正确。 1)从起点出发的最小权有向边必含在最短路线中。 (2)整个图中权最小的有向边必包含在最短路线中。 (3)整个图中权最大的有向边可能含在最短路线中 (4)从起点到终点的最短路线是唯一的。 7．关于带收发点的容量网络中从发点到收点的一条增广路，以下叙述( 123)不正确。 (1)增广路上的有向边的方向必须是从发点指向收点的(2)增广路上的有向边，必须都是不饱和边 (3) 增广路上不能有零流边(4)增广路上与发点到收点方向一致的有向边不能是饱和边， 相反方向的有向边不 能是零流边 8．关于树，以下叙述(ABCE)正确。 A．树是连通、无圈的图 B．任一树，添加一条边便含圈 C．任一树的边数等于点数减 1。D．任一树的点 数等于边数减 1E．任一树，去掉_条边便不连通。9．关于最短路，以下叙述(ACDE)不正确。 A 从起点出发到终点的最短路是唯一的。B．从起点出发到终点的最短路不一定是唯一的，但其最短路 线的长度是确定的。C．从起点出发的有向边中的最小权边，一定包含在起点到终点的最短路上 D．从起点 出发的有向边中的最大权边，一定不包含在起点到终点的最短路上。 E．整个网络的最大权边的一定不包 含在从起点到终点的最短路线上。 10．关于增广路，以下叙述(BC )正确。 A．增广路是一条从发点到收点的有向路，这条路上各条边的方向必一致。B．增广路是一条从发点到 收点的有向路， 这条路上各条边的方向可不一致。 增广路上与发点到收点方向一致的边必须是非饱和边， C． 方向相反的边必须是流量大于零的边。D．增广路上与发点到收点方向一致的边必须是流量小于容量的边， 方向相反的边必须是流量等于零的边。E．增广路上与发点到收点方向一致的边必须是流量为零的边，方向 相反的边必须是流量大于零的边。 四、名词解释 1、树:在图论中，具有连通和不含圈特点的图称为树。 2．权：在图中，边旁标注的数字称为权。 3．网络：在图论中，给边或有向边赋了权的图称为网络 4．最大流问题：最大流问题是指在网络图中，在单位时间内，从发点到收点的最大流量 5．最大流问题中流量：最大流问题中流量是指单位时间的发点的流出量或收点的流入量。 6．容量：最大流问题中，每条有向边单位时间的最大通过能力称为容量 7．饱合边：容量与流量相等的有向边称为饱合边。 8 零流边：流量为零的有向边称为零流边 9.生成树：若树 T 是无向图 G 的生成树，则称 T 是 G 的生成树。.。 10 根：有向图 G 中可以到达图中任一顶点的顶点 u 称为 G 的根。 11 枝：树中的边称为枝。 12.平行边：具有相同端点的边叫平行边。 13 根树：若有向图 G 有根 u，且它的基本图是一棵树，则称 G 为以 u 为根的根树。 四、计算题 1．下图是 6 个城市的交通图，为将部分道路改造成高速公路，使各个城市均能通达，又要使高速公路的 总长度最小，应如何做?最小的总长度是多少?2．对下面的两个连通图，试分别求出最小树。3、 第 1 题中的交通图，求城市 A 到 D 沿公路走的最短路的路长及路径。4．对下面两图，试分别求出从起点到终点的最短路线。5．分别求出下面两图中从发点到收点的最大流。每条有向边上的数字为该边的容量限制。6．下面网络中，点①，②是油井，点⑥是原油脱水处理厂，点③、④、⑤是泵站，各管道的每小时最 大通过能力(吨／小时)如有向边上的标注。求从油井①、②每小时能输送到脱水处理厂的最大流量。(提示：虚设一个发点 S，令有向边(S，1)，(S，2)的容量为∞)。名词 十一章 1、 需求：需求就是库存的输出。 2、 存贮费：一般是指每存贮单位物资单位时间所需花费的费用。 3、 缺货损失费：一般指由于中断供应影响生产造成的损失赔偿费。 4、 订货批量 Q：存贮系统根据需求，为补充某种物资的库存而向供货厂商一次订货或采购的数量。 5、 订货间隔期 T：两次订货的时间间隔可订货合同中规定的两次进货之间的时间间隔。6、 记账间隔期 R：指库存记账制度中的间隔记账制所规定的时间。 十二章 1、 预测：是决策的基础，它借助于经济学、概率论与数理统计、现代管理科学、系统论和计算机科学等 所提供的理论及方法，通过适当的模型技术，分析和预测研究对象的发展趋势。 十三章 1、 决策：凡是根据预定目标而采取某种行动方案所作出的选择或决定就称为决策。 2、 单纯选优决策：是指根据已掌握的数据，不需再加工计算，或仅进行方案指标值的简单计算，通过比 较便可以直接选出最优方案的决策方法。 3、 模型选 优决策：是在决策对象的客观状态完全确定的条件下，建立一定的符合实际经济状况的数学模 型，进而通过对模型的求解来选择最优方案的方法。 4、 非确定型决策：是一种在决策分析过程中，对决策方案付诸实施后可能遇到的客观状态，虽然能够进 行估计，但却无法确定每一种客观状态出现的概率的决策。 5、 风险型决策：是一种在分析过程中，对方案付诸实施后可能遇到的客观状态，不仅在决策分析时能够 加以估计，而且对每一种状态出现的概率大小也有所掌握。 6、 决策树：就是对一个决策问题画一张图，用更容易了解的形式来表示有关信息。 十四章 1、 排队论： 排队论所讨论的是一个系统对一群体提供某种服务时该群体占用此服务系统时所呈现的状态。 2、 排队规则：是描述顾客来到服务系统时，服务机构是否充许，顾客是否愿意排队，在排队等待情形下 服务的顺序。 3、 M/G/1 排队系统：是单服务台系统，其顾客到达服从参数为λ的泊松分布，服务时间属一般分布。 随机排队模型：称服务员个数为随机变量的排队系统为随机排队服务系统，相应的模型为随机排队模型。}