最全的运筹学复习题及答案
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 3．线性规划模型不包括下列_ D要素。 A．目标函数 B．约束条件 C．决策变量 D．状态变量 4．线性规划模型中增加一个约束条件，可行域的范围一般将_B_。 A．增大 B．缩小 C．不变 D．不定 5．若针对实际问题建立的线性规划模型的解是无界的，不可能的原因是B__。 A．出现矛盾的条件 B．缺乏必要的条件 C．有多余的条件 D．有相同的条件 6．在下列线性规划问题的基本解中，属于基可行解的是 D A．(一1，0，O)T B．(1，0，3，0)T C．(一4，0，0，3)T D．(0，一1，0，5)T 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 4．若线性规划问题的可行域是无界的，则该问题可能ABCD A．无有限最优解B．有有限最优解C．有唯一最优解D．有无穷多个最优解E．有有限多个最优解 5．判断下列数学模型，哪些为线性规划模型(模型中a．b．c为常数；θ为可取 某一常数值的参变量，x，Y为变量) ACDE 6．下列模型中，属于线性规划问题的标准形式的是ACD 7．下列说法错误的有_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 4 6—10 8 10一14 10 14—18 7 18—22 12 22—2 4 每个工作人员连续工作八小时，且在时段开始时上班，问如何安排，使得既满足以上要求，又使上班人数最少? 第三章 线性规划的基本方法 一、填空题 1．线性规划的代数解法主要利用了代数消去法的原理，实现基可行解的转换，寻找最优解。 2．标准形线性规划典式的目标函数的矩阵形式是_ maxZ=CBB－1b+(CN－CBB－ 1 N)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．线性规划问题C 2．在单纯形迭代中，出基变量在紧接着的下一次迭代中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 A．BPK B．BTPK C．PKB D．B-1PK 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(1)，X(2)是用单纯形法求得的某一线性规划问题的最优解，则说明ACDE。 A．此问题有无穷多最优解 B．该问题是退化问题 C．此问题的全部最优解可表示为λX(1)+(1一λ)X(2)，其中0≤λ≤1 D．X(1)，X(2)是两个基可行解E．X(1)，X(2)的基变量个数相同 4．某线性规划问题，含有n个变量，m个约束方程，(m 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、单纯形法解题的基本思路？ 可行域的一个基本可行解开始，转移到另一个 基本可行解，并且使目标函数值逐步得到改善，直到最后球场最优解或判定原问题无解。 五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的 每一步相当于图解法可行域中的哪一个顶点。 六、用单纯形法求解下列线性规划问题： 七、用大M法求解下列线性规划问题。并指出问题的解属于哪一类。 八、下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为maxZ=5x1+3x2，约束形式为“≤”，X3，X4为松驰变量．表中解代入目标函数后得Z=10 Xl X2 X3 X4 —10 b -1 f g X3 2 C O 1 1／5 Xl A d e 0 1 (1)求表中a～g的值 (2)表中给出的解是否为最优解? （1）a=2 b=0 c=0 d=1 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。 对偶问题的解B．市场上的稀缺情况 C．影子价格D．资源的购销决策E．资源 的市场价格 7．在下列线性规划问题中，CE采用求其对偶问题的方法，单纯形迭代的步骤一 般会减少。 四、名词、简答题 1、对偶可行基：凡满足条件δ=C-CBB-1A≤0的基B称为对偶可行基。 2、.对称的对偶问题：设原始线性规划问题为maxZ=CX s.t AX≤b X ≥0 称线性规划问题minW=Yb s.t YA≥C Y≥0 为其对偶问题。又称它们为一对对称的对偶问题。 3、影子价格：对偶变量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)T，试根据对偶理论，直接求出对偶问题的最优解。 W* = 16 第五章 线性规划的灵敏度分析 一、填空题 1、灵敏度分析研究的是线性规划模型的原始、最优解数据变化对产生的影响。 2、在线性规划的灵敏度分析中，我们主要用到的性质是_可行性，正则性。 3．在灵敏度分析中，某个非基变量的目标系数的改变，将引起该非基变量自身的检验数的变化。 4．如果某基变量的目标系数的变化范围超过其灵敏度分析容许的变化范围，则此基变量应出基。 5．约束常数b；的变化，不会引起解的正则性的变化。 6．在某线性规划问题中，已知某资源的影子价格为Y1，相应的约束常数b1，在灵敏度容许变动范围内发生Δb1的变化，则新的最优解对应的最优目标函数值 是Z*+yi△b (设原最优目标函数值为Z﹡) 7．若某约束常数bi的变化超过其容许变动范围，为求得新的最优解，需在原最优单纯形表的基础上运用对偶单纯形法求解。 8．已知线性规划问题，最优基为B，目标系数为CB，若新增变量xt，目标系数 －1 为ct，系数列向量为Pt，则当Ct≤CBBPt时，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 Ⅱ 设备 1 2 8台时 原材料A 4 0 16kg 原材料B 0 4 12kg 该工厂每生产一件产品I可获利2百元，每生产一件产品Ⅱ可获利3百元。 (1)单纯形迭代的初始表及最终表分别如下表I、Ⅱ所示： x1 x2 x3 x4 x5 xB 0 2 3 O 0 -Z 0 X3 8 1 2 1 O X4 16 0 X5 12 4 0 0 1 0 0 4 0 0 1 14 0 0 -3/2 -1/8 0 Xl 4 1 0 0 1/4 X5 4 0 X2 2 0 0 -2 1/2 1 0 1 1/2 -1/8 0 说明使工厂获利最多的产品混合生产方案。 (2)如该厂从别处抽出4台时的设备用于生产I、Ⅱ，求这时该厂生产产品I、Ⅱ的最优方案。 (3)确定原最优解不变条件下，产品Ⅱ的单位利润可变范围。 (4)该厂预备引进一种新产品Ⅲ，已知生产每件产品Ⅲ，需消耗原材料A、B分别为6kg，3kg使用设备2台时，可获利5百元，问该厂是否应生产该产品及生产多少? (1)使工厂获利最多的产品混合生产方案：生产I产品4件，生产II产品2件，设备台时与原材料A全部用完，原材料B剩余4kg，此时，获利14百元。 (2)X*=(4，3,2，0，o)Tz*=17 (3)0≤C2≤4 (4)应生产产品Ⅲ，产量为2。 五、给出线性规划问题 用单纯形表求解得单纯形表如下，试分析下列各种条件变化下最优解(基)的变化： xl x2 x3 x4 x5 -8 0 0 -3 -5 -1 xl 1 1 0 -1 4 x2 2 -1 0 1 2 -1 1 (1)分别确定目标函数中变量X1和X2的系数C1，c2在什么范围内变动时最优解不变； (2)目标函数中变量X3的系数变为6； (3)增添新的约束X1+2x2+x3≤4 -Z xB 解：(1)3/4≤C1≤3 2≤C2≤8 (2)X*=(2，0，1，0，0，T 0)Z*=10 (3)X*=(2，1，0，0，1，0)T Z*=7 (4)X*=(0，2，0，0，0，1/3)T Z*=25/3 第六章 物资调运规划运输问题 一、填空题 1．物资调运问题中，有m个供应地，Al，A2…，Am，Aj的供应量为ai(i=1，2…，m)，n个需求地B1，B2，…Bn，B的需求量为bj(j=1，2，…，n)，则供需平 衡条件为 ai=bi i1mnj12．物资调运方案的最优性判别准则是：当全部检验数非负时，当前的方案一定是最优方案。 3．可以作为表上作业法的初始调运方案的填有数字的方格数应为m+n－1个(设问题中含有m个供应地和n个需求地) 4．若调运方案中的某一空格的检验数为1，则在该空格的闭回路上调整单位运置而使运费增加1。 5．调运方案的调整是要在检验数出现负值的点为顶点所对应的闭回路内进行运量的调整。 6．按照表上作业法给出的初始调运方案，从每一空格出发可以找到且仅能找到_1条闭回路 7．在运输问题中，单位运价为Cij位势分别用ui，Vj表示，则在基变量处有cij Cij=ui+Vj 。 nm8、供大于求的、供不应求的不平衡运输问题，分别是指_＞abi的运输问imni1j1题、ai_＜bi的运输问题。 i1j110．在表上作业法所得到的调运方案中，从某空格出发的闭回路的转角点所对应的变量必为基变量。 11．在某运输问题的调运方案中，点(2，2)的检验数为负值，(调运方案为表所示)则相应的调整量应为300_。 I Ⅱ Ⅲ Ⅳ A 300 100 300 B 400 C 600 300 12.若某运输问题初始方案的检验数中只有一个负值：－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 B2 B3 B4 B5 B6 产量 30 Al 20 10 50 A2 30 20 75 A3 10 10 50 5 A4 20 20 销量 20 40 30 10 50 25 (b) (c) Bl B2 B3 B4 B5 B6 产量 Bl B2 B3 B4 产量 Al 30 30 Al 6 5 11 A2 20 30 50 A2 5 4 2 11 A3 10 30 10 25 75 A3 5 3 8 A4 20 20 销量 5 9 9 7 销量 20 40 30 10 50 25 (a)可作为初始方案； (b)中填有数字的方格数少于9(产地数+销地数－1)，不能作为初始方案； (c)中存在以非零元素为顶点的闭回路，不能作为初始方案 四、已知某运输问题的产销平衡表。单位运价表及给出的一个调运方案分别见表(a)和(b)，判断给出的调运方案是否为最优?如是说明理由；如否。也说明理由。 表(a)产销平衡表及某一调运方案 单位运价表 销 地 B l B2 B3 B4 B5 B6 产量 产地 30 20 50 l A2 A3 A4 30 10 40 60 10 40 10 20 11 31 销量 30 50 20 40 30 11 五、给出如下运输问题 运价 销 B1 B2 B3 B4 产量 产 Al A2 A3 销量 5 3 10 4 90 1 6 9 6 40 20 10 5 7 70 30 50 80 40 200 (1)应用最小元素法求其初始方案；(2)应用位势法求初始方案的检验数，并检验该方案是否为最优方案 六、用表上作业法求给出的运输问题的最优解 甲 乙 丙 丁 产量 1 10 6 7 12 4 2 16 0 5 9 9 3 5 4 10 10 4 销量 5 2 4 6 甲 乙 丙 丁 产量 1 1 2 1 4 2 3 6 9 3 4 4 销量 5 2 4 6 在最优调运方案下的运输费用最小为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．若在对某整数规划问题的松驰问题进行求解时，得到最优单纯形表中，由61X。所在行得X则以X－X31+1／7x3+2／7x5=13／7，1行为源行的割平面方程为_277－X5≤0_。 78．在用割平面法求解整数规划问题时，要求全部变量必须都为整数。 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中至少选择两个； 试建立这个问题的整数规划模型 八、有四项工作要甲、乙、丙、丁四个人去完成．每项工作只允许一人去完成。每个人只完成其中一项工作，已知每个人完成各项工作的时间如下表。问应指派每个人完成哪项工作，使总的消耗时间最少? 工作 I 人 Ⅱ Ⅲ Ⅳ 甲 15 18 2l 24 乙 19 23 22 18 丙 6 7 16 19 丁 19 21 23 17 第八章 图与网络分析 一、填空题 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排队系统：是单服务台系统，其顾客到达服从参数为λ的泊松分布，服务时间属一般分布。 随机排队模型：称服务员个数为随机变量的排队系统为随机排队服务系统，相应的模型为随机排队模型。 一、（10分）某咨询公司，受厂商委托，对新上市的一种新产品进行消费者反映的调查。该公司采用了挨户调查的方法，委托他们调查的厂商以及该公司的市场研究专家对该调查提出下列几点要求： （1）必须调查2000户人家； （2）在晚上调查的户数和白天调查的户数相等； （3）至少应调查700户有孩子的家庭； （4）至少应调查450户无孩子的家庭。 每会见一户家庭，进行调查所需费用为 家庭 有孩子 无孩子 白天会见 25元 20元 晚上会见 30元 24元 问为使总调查费用最少，应调查各类家庭的户数是多少？（只建立模型） 二、（10分） 某公司受委托，准备把120万元投资两种基金A和B，其中A基金的每单位投资额为50元，年回报率为10%，B基金的每单位投资额为100元，年回报率为4%。委托人要求在每年的年回报金额至少达到6万元的基础上要求投资风险最小。据测定每单位A基金的投资风险指数为8，每单位B基金的投资风险指数为3，投资风险指数越大表明投资风险越大。委托人要求在B基金中的投资额不少于30万元。为了使总的投资风险最小，该公司应该在基金A和基金B中各投资多少单位？这时每年的回报金额是多少？ 为求该解问题，设 可以建立下面的线性规划模型 使用《管理运筹学》软件，求得计算机解如下图所示， 最 优 解 目 标 函 数 值 = 62000.000 变 量 值 相差值 x1 4000.000 0.000 x2 10000.000 0.000 3 约 束 松驰/剩余变量 对偶价格 1 0.000 0.057 2 0.000 -2.167 3 7000.000 0.000 目 标 系 数 范 围 变 量 下 限 当 前 值 上 限 x1 3.750 8.000 无上限 x2 无下限 3.000 6.400 常 数 项 范 围 变 量 下 限 当 前 值 上 限 1 780000.000 1200000.000 1500000.000 2 48000.000 60000.000 102000.000 3 无下限 3000.000 10000.000 根据图回答问题： a.最优解是什么，最小风险是多少？ b.投资的年收入是多少？ c.每个约束条件的对偶价格是多少？ d.当每单位基金A的风险指数从8降为6，而每单位基金B的风险指数从3上升为5时，用百分之一百法则能否断定，其最优解变或不变？为什么？ e.对图中的右边值范围的上、下限给予具体解释，并阐述如何使用这些信息。 三、（10分） 某造船厂根据合同从当年起连续三年末各提供五条规格型号相同的大型客货轮。已知该厂这三年内生产大型客货轮的能力及每艘客货轮的成本如下表所示。 已知加班生产时，每艘客货轮成本比正常高出10%，又知造出来的客货轮如当年不交货，每艘每积压一年所造成的积压损失为60万元。在签合同时，该厂已积压了两艘未交货的客货轮，而该厂希望在第三年末完成合同后还能储存一艘备用。问该厂应如何安排每年客货轮生产量，使在满足上述各项要求的情况下，总的生产费用为最少？建立上述运输问题模型。 正常生产时间内 年度 可完成的客货轮数 可完成的客货轮数 1 2 3 四、（10分） 某畜产品公司计划在市区的东、西、南、北四区建立销售门市部，拟议中有10个位置 Ai (i＝1，2，3，…，10)可供选择，考虑到各地区居民的消费水平及居民居住密集度，规定： 在东区由A1，A2，A3三个点中至少选择两个； 在西区由A4，A5两个点中至少选一个； 在南区由A6，A7两个点中至少选一个； 在北区由A8，A9，A10三个点中至多选两个。 3 4 2 3 2 3 （万元） 600 700 650 加班生产时间内 正常生产时每艘成本 Ai各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况见下表（单位：万元）所示。 A1 A2 A3 A4 90 17 A5 80 15 A6 100 25 A7 90 20 A8 A9 A10 投资额 110 130 160 利润 31 35 45 150 170 190 43 53 56 但投资总额不能超过820万元，问应选择哪几个销售点，可使年利润为最大?建立上述问题的整数规划模型。 五、（10分） 某公司拟将某种设备4台，分配给所属的甲、乙、丙三个工厂。各工厂获得此设备后，预测可创造的利润如下表所示， 问这4台设备应如何分配给这3个工厂，使得所创造的总利润为最大？用动态规划求解。 六、（10分） 请确定a、b、c、d 各题的存储模型，确定各输入数据，不需计算： a、某公司生产一种电子设备，该设备所需的一个部件由自己的分厂提供，分厂对这种部件的生产能力为6000/件，分厂每次的生产准备费为250元。公司的这种电子设备的年需求为2000台/年。装配允许滞后，滞后的费用为每台成本 的40%。该部件每件成本为500元，年存贮为成本的20%。求：公司生产关于这种部件费用最小的生产批量。 b、某单位每年需要一种备件5000个，这种备件可以从市场直接购买到。设该备件的单价为16元/个，年存贮费为单价的25%。一个备件缺货一年的缺货费为单价的10%。若每组织采购一次的费用为120元。试确定一个使采购存贮费用之和为最小的采购批量。 c、一条生产线如果全部用于某型号产品时，其年生产能力为600000台。据预测对该型号产品的年需求量为250000台，并在全年内需求基本保持平衡，因此该生产线将用于多品种的轮番生产。已知在生产线上更换一种产品时，需准备结束费1350元。该产品每台成本为45元，年存贮费用为产品成本的24%，不允许发生供应短缺。求使费用最小的该产品的生产批量。 d、某企业的产品中有一外购件，年需求量为60000件，单价为35元。该外购件可在市场立即采购到，并设不允许缺货。已知每组织一次采购需720元，每件每年的存贮费为该件单价的20%。试求经济订货批量及每年最小的存贮加上采购的总费用。 某公司在今后四个月内需租用仓库堆放物资。已知各个月所需的仓库面积数字如下所示： 月份 所需仓库面积 15 （百平方米） 仓库的租借费用，当租借期限越长时，享受的折扣优惠越大，具体数字如下： 10 20 12 1 2 3 4 合同租借期限 合同期限内每百平方米 1个月 二800 2个月 4500 3个月 6000 4个月 7300 仓库面积的租借费用 租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。因此该厂可根据需要在任何一个月初办理租借合同，且每次办理，可签一份，也可同时签定若干份租用面积和租借期不同的合同。请建立求解出一个所付租借费为最小的租借方案的线性规划模型。 设xij表示i时会见的j种家庭的人数 目标函数：（2分） minZ=25x11+30x21+20x12+24x22 约束：（8分） x11+x21+x12+x22=2000 x11+ x12=x21+ x22 x11+x21≥700 x12+x22≥450 xij≥0（i,j=1,2） 第二题（10分） 标准答案： a. 最优解：x1=4000；x2=10000；最小风险：62000（2分） b. 年收入：6000元（2分） c. 第一个约束条件对偶价格：0.057；第二个约束条件对偶价格：-2.167；第三个约束条件对偶价格：0（2分） d. 不能判定（2分） e. 当右边值总投资额取值在780000—1500000之间时，不改变约束条件1的对偶价格；当右边值回报额取值在48000—102000之间时，不改变约束条件2的对偶价格；当右边值B的投资额小于10000时，不改变约束条件3的对偶价格。（2分） 第三题（10分） 标准答案： M为一足够大的数 第四题（10分） 标准答案： 设 目标函数：（2分） maxZ=31x1+35x2+45x3+17x4+15x5+25x6+20x7+43x8+53x9+56x10 约束条件：（8分） 110x1+130x2+160x3+90x4+80x5+100x6+90x7+150x8+170x9+190x10≤820 x1+x2+x3≥2 x4+x5≥1 x6+x7≥1 x8+x9+x10≤2 xi为0-1变量（i=1,2,…,10） 第五题（10分） 标准答案： 阶段3(3分) xi Si 0 1 2 3 0 0 5 7 12 0 1 2 3 r 0 1 2 3 4 f(xi) X* 5 7 12 4 13 13 4 阶段2(3分) xi Si 0 1 2 0 0 6 11 0 1 1,2 12+0 12+5 12+0 18 1,2 16 2 0 1 r 2 3 4 f(xi) X* 0+5 6+0 0+7 *6+5 *11+0 3 0+12 6+7 *11+5 4 0+13 *6+12 *11+7 阶段1(3分) xi Si 4 0+1*4+18+110+120 1 0 1 r 2 3 4 f(xi) X* 8 6 1 6 3 分配给甲厂1台；分配给乙厂2台；分配给丙厂1台；总利润：20(1分) 第六题（10分） 标准答案： a. 允许缺货的经济生产批量模型：D=2000台/年；d=2000台/年；p=6000台/年；C1=100元/年；C2=200元/年；C3=250元/年(3分) b. 允许缺货的经济订购批量模型：D=5000个/年；C1=4元/年； C2=1.6元/次；C3=120元/年(3分) c. 经济生产批量模型：D=250000台/年；p=600000台/年；d=250000台/年；C1=10.8元/年； C3=1350元/次(2分) d. 经济订购批量模型：D=60000件/年；C1=7元/年； C3=720元/次(2分) 第十题（10分） 标准答案： 设xij为第i月初办理的期限为j月的合同规定的仓库面积 目标函数：（2分） minZ=2800(x11+x21+x31+x41)+4500((x12+x22+x32) +6000(x13+x23) +7300x14 约束条件：（8分） x11+x12+x13+x14≥15 x12+x13+x14+x21+x22+x23≥10 x13+x14+x21+x22+x23+x31+x32≥20 x14+x23+x32+x41≥12 一、 某公司制造三种产品A、B、C，需要两种资源（劳动力和原材料），现 要确定总利润最大的生产计划，列出下述线性规划(35分) maxz3x1＋x2＋5x3（劳动力）6x1＋3x2＋5x345 （原材料）3x1＋4x2＋5x330x，x，x0123求：（1）线性规划问题的最优解； 首先将问题标准化： maxz3x1＋x2＋5x36x1＋3x2＋5x3x445 3x1＋4x2＋5x3x530x，x，x,x,x012345cj CB 0 0 0 5 x4 x3 XB x4 x5 b 45 30 15 6 3 x1 6 3 3 3 3/5 3 4 1 -1 4/5 1 x2 5 x3 5 【5】 5 0 1 0 x4 1 0 0 1 0 0 x5 0 1 0 -1 1/5 i 9 6 0 -3 0 0 -1 最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,6,15,0)T，最优目标值z*=30 （2）求对偶问题的数学模型及其最优解； minw45y130y26y13y233y4y1 125y15y25y10,y20y1*=0,y2*=1 (3) 最优解不变的情况下，求产品A的利润允许变化范围； 最优解不变的情况下，c10,c13 （4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？ 有利 单位材料的影子价格是1元，10元钱购进15单位的材料的单位价格为2/3元，低于影子价格。同时，在保持最优基不变的情况下 30b215 购进15吨的原材料，最优基不变。该材料的影子价格仍为1元。 （5）当可利用的资源增加到60单位时，求最优解。 b'B1b114515 1060125cj CB 0 5 0 5 x5 x3 XB x4 x3 b -15 12 15 9 3 x1 3 3/5 0 -3 6/5 1 x2 -1 4/5 -3 1 3/5 5 x3 0 1 0 0 1 0 x4 1 0 0 -1 1/5 0 x5 【-1】 1/5 -1 1 0 -3 -2 0 -1 0 最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,9,0,15)T，最优目标值z*=45 （6）当产品B的原材料消耗减少为2个单位时，是否影响当前的最优解，为什么？ x2在最有表是非基变量，该产品的原材料消耗只影响x2的检验数。 P2'B1P21131 1202552c2CBB1P2'1105215所以最优解不变20 （7）增加约束条件2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？ 增加的约束条件，相当于增加了一个约束方程 2x1x23x3x620 cj CB 0 5 0 0 5 0 x4 x3 x6 XB x4 x3 x6 b 15 6 20 15 6 2 2 x1 3 3/5 2 0 3 3/5 4/5 4 x2 -1 4/5 1 -3 -1 4/5 -7/5 1 x3 0 1 3 0 0 1 0 0 x4 1 0 0 0 1 0 0 0 x5 -1 1/5 0 -1 -1 1/5 -3/5 0 x6 0 0 1 0 0 0 1 0 0 -3 0 0 -1 对原问题的最优解无影响，对对偶问题的最优解也无影响。 二、 某钻井队要从8个可供选择的井位中确定4个钻井探油，使总的钻探费 用最省。若8个井位的代号是s1、s2、…、s8，相应的钻探费用为c1、c2、…、c8，并且井位满足下列条件限制：（10分） i. 或选择s1和s7，或选择s8； ii. s6和s7中选一个； iii. s2和s5不能同时选； iv. 选择了s1的话就不能选择s4； v. 选择了s2的话必须选择s3 试用：整数规划方法建模。 1当选择si令：xi0当不选择simaxzc1x1c2x2c3x3c4x4c5x5c6x6c7x7c8x8 x1x7x81xx176x2x51x1x41x2x30xi0或1 四、A、B两个煤矿负责供应甲、乙、丙三个城市煤炭。已知A、B两矿年产量、三个城市的需求量以及从两煤矿至各城市煤炭运价如下表。由于供不应求，经协商，甲城市必要时可少供应0－30万吨，乙城市需求须全部满足，丙城市需求不少于270万吨。试求：将甲、乙两矿煤炭全部分配出去，满足上述条件又使总运费最低的调运方案。（15分） 产 甲 乙 丙 产量 销 A 15 18 22 400 B 21 25 16 450 销量（T） 320 250 350 解：(1)依题意得产销平衡表如下： 产 甲’ 甲’’ 乙 丙’ 丙’’ 产量 销 A 15 15 18 22 22 400 B 21 21 25 16 16 450 C M 0 M M 0 70 销量（T） 290 30 250 270 80 (2)做初始的调运方案（伏格尔法） 产 甲’ 甲’’ 乙 丙’ 丙’’ 产销 量 A B 150 15 21 15 21 250 18 25 22 16 22 16 400 450 C 140 30 M 0 M 270 10 M 270 丙’ 70 80 0 70 U -6 0 -16 销量（T） 290 30 250 （3）用位势法进行检验 产 甲’ 甲’’ 乙 销 A 1 15 18 0 5 0 0 B 2 21 25 1 0 0 1 C M 0 M V M-5 21 -5 21 M-8 24 丙’’ 22 16 22 12 12 16 0 16 0 M 0 0 16 (4) 做闭回路调整 调整后为： 产 甲’ 甲’’ 乙 销 A 1 15 18 155 250 0 B 2 21 25 1 140 C M 0 M 销量（T） 290 （5）进行进一步检验 产 甲’ 甲’’ 销 A 1 15 0 5 0 30 30 250 丙’ 22 16 丙’’ 22 16 产量 400 450 270 40 M 270 40 80 0 70 乙 0 18 丙’ 丙’’ 22 U -6 22 12 12 B 0 21 21 1 0 25 0 16 16 0 -16 C 5 M M 0 M 0 M-5 0 M-8 M 0 V 21 16 24 16 16 (6) 调整后的方案为最优方案 最低费用＝150×15＋250×18＋140×21＋270×16＋40×16＋30×0＋40×0＝14650 五、分配甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最少的指派方案。（15分） A B C D E 甲 25 29 31 42 37 乙 39 38 26 20 33 丙 34 27 28 40 32 丁 24 42 36 23 45 解：假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。 得效率矩阵为： ABCDE甲25293142373938262033乙 丙3427284032丁2442362345戊2427262032各行减最小值，各列减最小值：得 ABCDE甲0451771918508乙 丙7013丁1191217戊4757变换得 ABCDE甲045乙18174丙70丁1811戊364707 1416618进一步 ABCDE甲0011831813003乙丙1100180丁0147012戊32002最有指派方案 ABCDE 甲01000 00010乙 丙00001丁10000戊00100 甲——B，乙——C,D，丙——E，丁——A 最低费用＝29＋26＋20＋32＋24＝131 六、某公司打算将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所分配的投资有关。各工厂在获得不同的投资额时所能增加的利润如下 表所示，问应如何分配资金，使公司总的利润为最大（15分） 利润 投0 1千万 2千3千万 资 万 工厂 1 0 2.5 4 10 2 0 3 5 8.5 3 0 2 6 9 解：K为阶段变量，k=1,2,3 Sk:第k阶段所剩的资金数 Xk：第k阶段分配给第k个工厂的资金数 gk（xk）：将xk分配给第k个工厂的效益 状态转移方程：Sk+1= Sk-xk 递推关系： {gk(xk)fk1(skxk)}kn1,,1 fk(sk)0maxxksk fn(sn)maxgn(xn)xnsn 第三阶段，k=3 X3=s3 f3(s3)maxg3(x3) x3s3x3 s3 0 1 g3(x3) 2 3 f3(s3) x*3 0 1 2 3 0 2 6 9 0 2 6 9 0 1 2 3 第二阶段： s3=s2-x2， 0s23， 0x2s2 f2(s2)max{g2(x2)f3(s2x2)} 0x2s2x2 s2 f2(s2)max{g2(x2)f3(s2x2)} 0x2s2f2(s2) 0 2 6 9 x*2 0 1 0 0,1 0 0 1 2 3 0+0 0+2 0+6 0+9 1 3+0 3+2 3+6 2 5+0 5+2 3 8.5+0 第三阶段 S1=3 S2=s1-x1, 0x1s1 x1 f1(s1)max{g1(x1)f1(s1x1)} 0x1s1s1 0 1 2 3 3 0+9 2.5+6 4+3 10+0 f1(s1) 10 x*1 3 最优分配方案为，x1*=3,x2*=0,x3*=0 最佳获益值：10千万。 第二章 线性规划问题的基本概念 3、本章典型例题分析 例：某工厂要安排生产甲、乙两种产品，已知生产单位产品所需的设备台时及A、B两种原村料的消耗如表所示。该工厂生产一单位产品甲可获利2元， 生产一单位产品乙可获利3元，问应如果安排生产，使其获利最多？ 设备 原材料A 原材料B 甲 1 4 0 乙 2 0 4 每日提供资源 8（台时） 16（Kg） 12（Kg） 解：①确定决策变量：设X1 、X2 为产品甲、乙的生产数量； ②明确目标函数：获利最大，即求2X1+3X2的最大值； ③所满足的约束条件： 设备限制：X1+2X2≤8 原材料A限制：4X1≤16 原材料B限制：4X2≤12 基本要求：X1 ，X2≥0 用max代替最大值，S.t.代替约束条件，则此问题的数学模型为： maxZ2x13x2 St x12x28 4x116 4x212 x1,x20 型。 2、本章重点难点分析 建立初始单纯形表格，并用单纯形方法求解线性规划数学模型。 3、本章典型例题分析 例： maxZ20x115x2 用单纯形法求解 St 2x13x2600 2x1x2400 x1,x20 解：先化为标准形式：maxZ20x115x2 St 2x13x2x3600 2x1x2x4400 xj0(j1,2,3,4) 把标准形的系数列成一个表 基 S X1 X2 X3 S 1 -20 -15 0 X3 0 2 3 1 X4 0 2 1 0 第一次迭代：调入x1,调出x4 基 S X1 X2 X3 S 1 0 -5 0 X3 0 0 2 1 X1 0 1 1/2 0 第二次迭代：调入x2,调出x3 基 S X1 X2 X3 X4 0 0 1 X4 10 -1 1/2 X4 解 0 600 400 解 4000 200 200 解 S X2 X1 1 0 0 0 0 1 0 1 0 5/2 1/2 -1/4 15/2 -1/2 3/4 4500 100 150 Zmax 4、本章作业 见本章练习题 3、本章典型例题分析 x1150x21004500 例：写出下列线性规划问题的对偶问题 maxZ3x1x24x36x13x25x325 St3x14x25x320x0(j1,2,3)j 解：其对偶问题为： minW25y120y26y13y233y4y1 12St5y15y24y1,y204、本章作业 见本章练习题 第五章 运输模型 1、本章学习要求 （1）应熟悉的内容 运输问题的数学模型。 （2）应掌握的内容 根据实际问题能写出运输问题的数学模型。 （3）应熟练掌握的内容 确定初始方案的方法：最小元素法、元素差额法。 2、本章重点难点分析 先确定初始方案，然后进行检验是否是最优解，如果不是最优解，则进行调整改进，最终得到最优解。。 3、本章典型例题分析 例：用最小元素法求解（表上作业法） （单位：吨） 销地 产地 1 2 3 销量 1 2 3 4 5 产量 200 200 250 250 300 300 350 200 550 100 100 200 600 400 500 1500 （单位：元） 销地 产地 1 2 3 4 5 1 2 3 2 4 2 1 2 1 3 1 1 1 3 3 2 1 4 ⑤ ③ ④ ① ② ⑥ ∴运输费用为：1×250+1×350+1×300+1×100+2×200+3×200+4×100=2400(元）。 4、本章作业 见本章练习题 第六章 网络分析 例：用破圈法求一个最小生成树 V2 1 V1 10 V6 V1 V1 V3 V2 V3 1 3 7 7 3 43 V2 7 V4 V1 3 4 3V2 7 V4 5 83 5 8 4 V5 V6 4 V5 V2 V3 1 V2 V3 371 37 4 V23 7 V1 3 V2 7 V4 3 5V4 3 V6 4 V5 V6 4 V5 V2 V3 V2 V3 1 1 37 7 3 3 V2V1 3 V2 7 4 V7 V4 3 3 V6 V5 V6 V5 ∴总权数为：3+3+3+1+2+7=19 4、本章作业 3、本章典型例题分析 例： 自然状态 概率 收益值 行动方案 S1（大批量生产) S2（中批量生产） S3（小批量生产） 决策 N1(需求量大) N2(需求量小) E（Si） P(N1)=0.3 P(N2)=0.7 30 20 10 -6 -2 5 N1(需求量大) P(N1)=0.3 4.8 4.6 6.5 △30 △-6 大批量生产 S1 N2(需求量小) P(N2)=0.7 N1(需求量大) P(N1)=0.3 中批量生产 △20 S2 N2(需求量小) P(N2)=0.7 △-2 E（S1）=0.3×30+0.7×(-6)=4.8 E（S2）=0.3×20+0.7×(-2)=4.6 小批量生产 S3 N1(需求量大) P(N1)=0.3 △10 N2(需求量小) P(N2)=0.7 △5 E（S3）=0.3×10+0.7×5=6.5 ∴选定方案S3 二、计算题 1、试建立下列问题的数学模型 （1）某农场要新买一批拖拉机以完成每年三季的工作量：春种330公顷，夏管130公顷，秋收470公顷。可供选择的拖拉机型号、单台投资额及工作能力如下表所示。 拖拉机 型号 资 （元） A B C D 5000 4500 4400 5200 单台投单台工作能力（公顷） 春种 30 29 32 31 夏管 17 14 16 18 秋收 41 43 42 44 问配购哪几种拖拉机各几台，才能完成上述每年工作量且使总投资最少？ （2）甲、乙两煤矿供给A、B、C三个城市的用煤。各矿产量和各市需求量如下表所示 煤矿 甲 乙 日产量（吨） 200 250 城市 A B C 需求量（吨） 100 150 200 各矿与各市之间的运输价格如下表示 城市 煤矿 甲 乙 A 90 80 运价（元/吨） B 70 65 C 100 80 问：应如何调运，才能既满足城市用煤需求，又使运输的总费用为最少？ 2、将下述线性规划问题化成标准型 （1） minZx12x23x3 x12x2x35 s.t. 2x13x2x36x1x2x32x10,x30 （2） minZx12x23x3 s.t. 2x1x2x393x1x22x343x12x23x36x10,x20,x3取值无约束 3、图解法求解下列线性规划问题： （1） minZ6x14x2 s.t. 3x14x215 2x1x21x10,x20, （2） maxZ3x12x2 s.t. 2x12x24 x1x21x10,x20,（3） maxZ3x19x2 x13x222s.t. x1x24 x262x15x20x10,x20, 第三章 练习题 一、思考题 1、试述单纯形法的计算步骤，如何在单纯形表上去判别问题是具有唯一最优解、元穷多最优解、无界解或无可行解。 2、如果线性规划的标准型式变换为求目标函数的极小化min Z，则用单纯形法计算时如何判别问题已得到最优解。 二、单纯形法求解下列线性规划问题 1、 maxZ2x1x2 s.t. 6x12x224 3x15x215x10,x20,2、 minZ2x13x2 2x12x212 4x116s.t. x12x28 4x212x10,x20, 第四章 练习题 一、思考题 1、 试从经济上解释对偶问题及对偶变量的含义。 2、 根据原问题同对偶问题之间的对应关系，分别找出两个问题变量之间、解以及检验数之间的对应关系。 二、写出下列线性规划问题的对偶问题： （1） maxZ2x1x23x3x4 s.t. x1x2x3x452x1x23x34x1x3x41x1,x30,x2,x4无约束 （2） minZ2x12x24x3 s.t. 2x13x25x323x1x27x33x14x26x35x20,x30 第五章 练习题 一、思考题 1、试述运输问题数学模型的特征，为什么模型的（m+n）个约束中最多只有（m+n－1）个是独立的。 2、试述用最小元素法确定运输问题的初始基可行解的基本思路和基本步骤。 3、试述用闭回路法计算检验数的原理和经济意义，如何从任一空格出发去寻找一条闭回路。 二、求解下列产销平衡运输问题的最优调运方案和最小总运费 （单位：吨） 1 销地 产地 B1 B2 B3 B4 产量 A1 A2 A3 销量1 40 45 55 60 55 70 75 200 运费表 （单位：元） 销地 产地 A1 A2 A3 2 B1 B2 B3 B4 3 5 9 6 3 7 2 6 7 6 4 8 销地 运价 产地 A1 A2 A3 4 3 5 8 5 4 7 4 9 5 3 6 7 3 6 16 14 B1 B2 B3 B4 产量 销量1 4 4 3 3 （单位：吨） （单位：元） 第六章 练习题 一、思考题 1、通常用G＝（V，E）来表示一个图，试述符号V，E及这个表达式的涵义。 2、图论中的图同一般的工程图、几何图的主要区别是什么，试举例说明。 3、最大流的问题是一个特殊的线性规划问题，试具体说明这个问题中的变量、目标函数和约束条件各是什么？ 二、计算 1、如图，S，A，B，C，D，E，T代表村镇，它们间连线表明各村镇间现有道路交通情况，连线旁数字代表道路的长度。现在要求沿中道路架设电线，使上述村镇全部通上电，应如何架设使总的线路长度为最短。 2 A 2 7 D B 3 5 E 1 5 7 T C 5 1 2、求图中V1到V7的最短路S V1 第七章 练习题 一、思考题 4 V2 V3 1 2 5 V4 5 V6 8 V7 4 4 V5 1 6 1、简述决策的分类、决策的过程和程序、构成决策模型的各要素，并举例说明。 2、简述确定型决策、风险型决策和不确定型决策之间的区别。不确定型决策能否设法转化为风险型决策？若能转化，对决策的准确性有什么影响？ 3、对比分析不确定型决策中的悲观主义决策原则、乐观主义决策原则、等可能性原则，最小最大原则之间的区别与联系，并指出采用不同原则时决策者所面临的环境和心理条件。 二、应用题 1、某公司拟定扩大再生产的三种方案。未来市场需求状态为：无需求（E1）、低需求（E2）、中需求（E3）和高需求（E4），每个方案在四种自然状态下的损失如下表所示（单位：万元） 自然状态 损失 方案 S1 S2 S3 130 40 95 65 5 50 -70 -45 -60 -160 -100 -120 E1 E2 E3 E4 试分别依据以下决策准则选择扩大再生产的方案。 （1） （2） （3） （4） 悲观准则； 乐观准则； 等可能性准则； 后悔值准则。 2、某公司有5万元多余资金、如果用于某项产品开发估计成功率为96%，成功时一年可获利12%，但一旦失败，有丧失全部资金的危险。如把资金存放到银行，则可稳得年利6%。为获得更多情报，该公司可求助于咨询服务，但咨询费用为500元，但咨询意见只是提供决策参考。据过去咨询公司类似200例 咨询意见实施结果，统计结果如表（单位：次） 实施结果 咨询意见 可以投资 不宜投资 合 计 154 38 192 2 6 8 156 44 200 投资成功 投资失败 合计 试用决策树法分析：该公司是否值得求助于咨询服务？ 参考答案 第二章 1、(1)设购置A,B,C,D型号的拖拉机分别为x1, x2,x3,x4,台，相应的数学模型为： minZ5000x14500x24400x35200x4 30x129x232x331x4330s.t. 17x114x216x318x413041x143x242x344x4470x1,x2,x3,x40(且为整数) (2)设甲矿分别供应给A，B，C城市x11, x12, x13,吨煤乙矿分别供应给A，B， C城市x21, x22, x23,吨煤相应的数学模型为 minZ90x1170x12100x1380x2165x2280x23 x11x12x13200x21x22x23250s.t. x11x21100x12x22150x13x23200xij0(i1,2;j1,2,3) 2x23x3 2、(1) maxZx12x2s.t. 2x2x3x45x12x23x2x3x562x13x2x2x3x62x1x2xi0(i1,4,5,6)''x2,x2'',x30 2x23x33x30x40x5 (2) maxZx1s.t. x3x492x1x2x32x3x543x1x22x33x363x12x23x3,x3,x2,x4,x50x1,x3 2、 (1)唯一最优解Z3,x11/2,x20 (2)无可行解 (3)无穷多最优解，Z66 第三章 1、(1)x115333,x2,x30,x40,Z 444 (2)x14,x22,x30,x40,x50,x64,Z14, 第四章 1、 min5y14y2y3 2、 max2y13y25y3 y12y2y32s.t. y1y21 s.t. 2y13y2y323y1y24y325y17y26y34y10,y20 y13y2y33 y1y31y10,y2无约束,y30第五章 1 销地 运量 B1 B2 B3 B4 产量 产地 A1 A2 A3 销量 40 40 45 45 15 40 55 25 35 60 55 70 75 200 最小总运费为945 2 销地 产地 A1 A2 A3 最小总运费59 B1 B2 B3 B4 B5 4 4 0 3 3 0 2 第六章 1、 2 A 2 T D B 3 1 5 S C 1 2. 最短路为(V1, V2, V3, V6, V7,) E 管理运筹学复习 （1）某工厂在计划期内要安排Ⅰ,Ⅱ两种产品的生产.生产单位产品所需的设备台时及A,B两种原材料的消耗以及资源的限制如下表所示: Ⅰ Ⅱ 资源限制 设备 1 1 300台时 原料A 2 1 400kg 原料B 0 1 250kg 工厂每生产一单位产品Ⅰ可获利50元，每生产一单位产品Ⅱ可获利100元，问工厂应分别生产多少单位产品Ⅰ和产品Ⅱ才能使获利最多？ 解： max z=50X1+100X2 ； 满足约束条件： X1+X2≤300， 2X1+X2≤400， X2≤250， X1≥0,X2≥0。 （2）：某锅炉制造厂，要制造一种新型锅炉10台，需要原材料为∮63.5×4mm的锅炉钢管，每台锅炉需要不同长度的锅炉钢管数量如下表所示： 规格/mm 需要数量/根 规格/mm 需要数量/根 2640 8 1770 42 1651 35 1440 1 库存的原材料的长度只有5500mm一种规格，问如何下料，才能使总的用料根数最少？需要多少根原材料？ 解：为了用最少的原材料得到10 台锅炉，需要混合使用14 种下料方案 1 2 3 4 5 6 7 8 9 10 11 12 13 14 262 1 1 1 0 0 0 0 0 0 0 0 0 0 40 17 0 1 0 0 3 2 2 1 1 1 0 0 0 0 70 16 0 0 1 0 0 1 0 2 1 0 3 2 1 0 51 14 0 0 0 1 0 0 1 0 1 2 0 1 2 3 40 合5244424053514950484649474543计 80 10 91 80 10 91 80 72 61 50 53 42 31 20 剩2210121419305242638554759611余 0 90 09 20 0 9 0 8 9 0 7 8 9 80 设按14 种方案下料的原材料的根数分别为X1,X2,X3,X4,X5,X6 ,X7,X8,X9,X10,X11,X12,X13,X14, 可列出下面的数学模型： min f＝X1+X2+X3+X4+X5+X6+X7+X8+X9+X10+X11+X12+X13+X14 满足约束条件： 2X1＋X2＋X3＋X4 ≥ 80 X2＋3X5＋2X6＋2X7＋X8＋X9＋X10 ≥420 X3＋X6＋2X8＋X9＋3X11＋X12＋X13 ≥ 350 X4＋X7＋X9＋2X10＋X12＋2X13＋3X14 ≥ 10 X1，X2，X3，X4，X5，X6，X7，X8，X9，X10，X11，X12，X13，X14≥ 0 （3）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示： 产量/件 B1 B2 B3 A1 6 4 6 200 A2 6 5 5 300 销量/件 150 150 200 应如何调运，使得总运输费最小？ 解： 此运输问题的线性规划的模型如下 min f =6X11+4X12+6X13+6X21+5X22+5X23 约束条件 ： X11+X12+X13=200 X21+X22+X23=300 X11+X21=150 X12+X22=150 X13+X23=200 Xij≥0(i=1,2;j=1,2,3) (4) 某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示： 产量/件 B1 B2 B3 A1 6 4 6 300 A2 6 5 5 300 销量/件 150 150 200 500 600 应如何组织运输，使得总运输费为最小？ 解：这是一个产大于销的运输问题，建立一个假想销地B4，得到产销平衡如下表： 产量/件 B1 B2 B3 B4 A1 6 4 6 0 300 A2 6 5 5 0 300 销量/件 150 150 200 100 600 600 （5）某公司从两个产地A1、A2将物品运往三个销地B1、B2、B3，各产地的产量、各销地的销量和各产地运往各销地的每件物品的运输单价如下表所示： 产量/件 B1 B2 B3 A1 6 4 6 200 A2 6 5 5 300 销量/件 250 200 200 650 500 解：这是一个销大于产的运输问题，建立一个假想销地A3，得到产销平衡如下表： 产量/件 B1 B2 B3 A1 6 4 6 200 A2 6 5 5 300 150 650 650 （6）某公司在三个地方有三个分厂，生产同一种产品，其产量分别为300箱、400箱、500箱。需要供应四个地方的销售，这四地的产品需求分别为400箱、250箱、350箱、200箱。三个分厂到四个销地的单位运价如下表所示： 甲 乙 丙 丁 1分厂 21 17 23 25 A3 销量/件 0 250 0 200 0 200 2分厂 10 15 30 19 3分厂 23 21 20 22 ① 应如何安排运输方案,使得总运费为最小? ② 如果2分厂的产量从400箱提高到了600箱,那么应如何安排运输方案,使得总运费为最小? ③ 如果销地甲的需求从400箱提高到550箱,而其他情况都同①,那该如何安排运输方案,使得运费为最小? 解:①此运输问题的线性规划的模型如下 minf=21X11+17X12+23X13+25X14+10X21+15X22+30X23+19 X24+23X31+21X32+20X33+22X34 约束条件 ： X11+X12+X13 +X14=300 X21+X22+X23+X24=400 X31+X32+X33+X34=500 X11+X21+X31=400 X12+X22+X32=250 X13+X23+X33=350 X14+X24+X34=200 Xij≥0(i=1,2,3;j=1,2,3,4) ②解：这是一个产大于销的运输问题，建立一个假想销地戊，得到产销平衡如下表： 甲 乙 丙 丁 戊 产量/箱 1分厂 21 17 23 25 0 300 2分厂 （400）600 10 15 30 19 0 3分厂 销量/箱 23 400 21 250 20 350 22 200 0 200 500 1400 1400 ③解：这是一个销大于产的运输问题，建立一个假想销地4分厂，得到产销平衡如下表： 甲 乙 丙 丁 产量/箱 1分厂 21 17 23 25 300 2分厂 10 15 30 19 400 3分厂 4分厂 销量/箱 23 0 550 21 0 250 20 0 350 22 0 200 500 150 1350 1350 （7）整数规划的图解法 某公司拟用集装箱托运甲、乙两种货物，这两种货物每件的体积、重量、可获利润以及托运所受限制如下表所示： 每件体积/立方英每件重量/百千克 每件利润/百元 尺 甲 195 4 2 乙 273 40 3 托运限制 1365 140 甲种货物至多托运4件，问两种货物各托运多少件，可使获得利润最大？ 解：设X1,X2分别为甲、乙两种货物托运的件数，其数学模型如下所示： max z=2X1+3X2 约束条件： 195X1+273X2 ≤1365， 4X1+40X2 ≤140， X1 ≤4， X1, X2≥0， X1, X2 为整数。 （8）指派问题 有四个工人，要分别指派他们完成四项不同的工作，每人做各项工作所消耗的时间如下表所示：问应如何指派工作，才能使总的消耗时间为最少？ A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 解：引入0—1变量Xij ，并令 1，当指派第i人去完成第j项工作时； Xij = 0，当不指派第i人去完成第j项工作时； 此整数规划的数学模型为： min z=15X11+18X12+21X13+24X14+19X21+23X22+22X23+ 18 X24+26X31+17X32+16X33+19X34 +19X41+21X42+23X43+17X44 约束条件： X11+X12+X13 +X14=1（甲只能干一项工作） X21+X22+X23+X24=1（乙只能干一项工作） X31+X32+X33+X34=1（丙只能干一项工作） X41+X42+X43+X44=1（丁只能干一项工作） X11+X21+X31+X41=1（A工作只能一个人干） X12+X22+X32+X42=1（B工作只能一个人干） X13+X23+X33+X43=1（C工作只能一个人干） X14+X24+X34+X44=1（D工作只能一个人干） Xij为0—1变量，(i=1,2,3，4;j=1,2,3,4) (9)有优先权的目标规划的图解法 一位投资商有一笔资金准备购买股票，资金总额为90000元，目前可选的股票有 货物 A、B两种（可以同时投资于两种股票），其价格以及年收益率和风险系数 如下表所示： 股票 价格/元 年收益/（元/年） 风险系数 A 20 3 0.5 B 50 4 0.2 从表可知： 股票A的收益率为（3/20）×100%=15%,股票B的收益率为（4/50）×100%=8%, A的收益率比B大，但同时A的风险也比B大，这符合高风险高收益的规律。 试求一种投资方案，使得一年的总投资风险不高于700，且投资收益不低于10000元。 解：设X1、X2 分别表示投资商所购买的股票A和股票B的数量。 1.针对优先权最高的目标建立线性规划 X1 建立线性规划模型如下： 4000 min d1+ 20X1+50X2 ≦90000 约束条件：20X1+50X2 ≦90000 3000 2000 0.5X1+0.2X2-d1++d1- =700 3X1+4X2-d2++d2- =10000 1000 X1 , X2 , d1+ , d2-≧0 X2 0 1000 2000 3000 4000 5000 2.针对优先权次高的目标建立线性规划 X1 建立线性规划模型如下： 4000 min d2- 0.5X1+0.2X2 =700 约束条件： 20X1+50X2 ≦90000 3000 0.5X1+0.2X2-d1++d1- =700 2000 20X1+50X2 ≦90000 3X1+4X2-d2++d2- =10000 d1+=0 1000 X1 ， X2 ，d1+ ，d1- ，d2+，d2- ≧0 0 1000 2000 3000 4000 5000 3.目标规划模型的标准化 对于两个不同优先权的目标单独建立线性规划进行求解，为方便，把他们用一个模型来表达： min P1(d1+)+P2(d2-) 约束条件： 20X1+50X2 ≦90000 ， 0.5X1+0.2X2-d1++d1- =700， 3X1+4X2-d2++d2- =10000， X1 ， X2 ，d1+ ，d1- ，d2+，d2- ≧0。 （10）某工厂试对产品A、B进行生产，市场需求并不是很稳定，因此对每种产品分别预测了在销售良好和销售较差时的预期利润，这两种产品都经过甲、乙两台设备加工，已知产品A和B分别在甲和乙设备上的单位加工时间，甲、乙设备的可用加工时间以及预期利润如表所示，要求首先是保证在销售较差时，预期利 润不少于5千元，其次是要求销售良好时，预期销售利润尽量达到1万元。试建立目标规划模型。 A B 可用时间 甲 4 3 45 乙 2 5 30 销售良好时的预期利润（元/8 6 100 件） 销售较差时的预期利润（元/5 5 50 件） 解：设工厂生产 A 产品 X1 件，生产 B 产品X2件。按照生产要求，建立如下目标规划模型: min P1(d1+)+P2(d2-) 约束条件： 4X1+3X2 ≦45 ， 2X1+5X2 ≦30 5X1+5X2-d1++d1- =50， 8X1+6X2-d2++d2- =100， X1 ， X2 ，di+ ，di- ≧0.i=1,2 (11)动态规划 石油输送管道铺设最优方案的选择问题：如图所示，其中A为出发点，E为目的地，B、C、D分别为三个必须建立油泵加压站的地区，其中的B1、B2、B3;C1、C2、C3;D1、D2分别为可供选择的各站站点。图中的线段表示管道可铺设的位置，线段旁的数字为铺设管线所需要的费用，问如何铺设管道才使总费用最小？ 6 2 3 B 1 3 C 1 D1 5 5 3 3 E A 5 B 2 2 C 2 7 4 4 4 4 D2 4 1 5 4 B 3 5 C 3 解： 第四阶段：D1—E 3；D2—E 4； 第三阶段：C1—D1—E 5；C2—D2—E 8；C3—D1—E 8；C3—D2—E 8； 第二阶段：B1—C1—D1—E 11；B1—C2—D2—E 11；B2—C1—D1—E 8； B3—C1—D1—E 9 ；B3—C2—D2—E 9； 第一阶段：A—B1—C1—D1—E 14；A—B1—C2—D2—E 14； A—B2—C1—D1—E 13；A—B3—C1—D1—E 13； A—B3—C2—D2—E 13； 最优解：A―B2―C1―D1―E；A―B3―C1―D1―E；A―B3―C2―D2―E 最优值：13 （12）最小生成树问题 某大学准备对其所属的7个学院办公室计算机联网，这个网络的可能联通的途径如图所示，图中V1，……，V7表示7个学院办公室，图中的边为可能联网的途径，边上的所赋权数为这条路线的长度，单位为百米。请设计一个网络能联通7个学院办公室，并使总的线路长度为最短。 V2 3 V1 10 V6 3 3 4 V7 5 8 4 V5 2 1 V3 7 V1 V4 3 3 V2 3 4 V7 5 8 V5 2 1 V3 7 V4 G V6 4 G1 解：①在G中找到一个圈（V1，V7，V6，V1）,并知在此圈上边[V1，V6]的权 数10为最大，在G中去掉边[V1，V6]得图G1 ，如上图所示 V2 3 V1 1 V6 3 3 4 4 V7 5 V5 2 1 V3 7 V1 V4 1 3 V6 4 V5 3 V2 3 4 V7 2 1 V3 7 V4 G2 G3 ②在G1中找到一个圈（V3，V4，V5，V7，V3），去掉其中权数最大的边 [V4，V5]， 得图G2 ，如上图所示 ③在G2中找到一个圈（V2，V3，V5，V7，V2），去掉其中权数最大的边 [V5，V7]，得图G3 ，如上图所示 V2 3 V1 1 V6 3 3 V5 4 V7 2 1 V3 7 V1 V4 1 3 V6 V5 3 V2 3 V7 2 1 V3 7 V4 G4 G5 ④在G3中找到一个圈（V3，V5，V6，V7，V3），去掉其中权数最大的边 [V5，V6]，得图G4 ，如上图所示 ⑤在G4中找到一个圈（V2，V3， V7，V2），去掉其中权数最大的边 [V3，V7]，得图G5 ，如上图所示 ⑥在G5中已找不到任何一个圈了，可知G5即为图G的最小生成树。 这个最小生成树的所有边的总权数为3+3+3+1+2+7=19 (13)某一个配送中心要给一个快餐店送快餐原料，应按照什么路线送货才能使送货时间最短。下图给出了配送中心到快餐店的交通图，图中V1，……，V7表示7个地名，其中V1表示配送中心，V7表示快餐店，点之间的联线表示两地之间的道路，边所赋的权数表示开车送原料通过这段道路所需要的时间（单位：分钟） （18,3） （4,1） V2 （0,S） 4V1 （配送中心） 18162V4 7856V5 （24,3） V6 （25,4） 612V7 （27,5） （快餐店） （16,2） V3 解：①给起始点V1标号为（0，S） ②I={V1},J={ V2，V3，V4，V5，V6 ,V7} ，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={[ V1，V2]，[ V1，V3]}，并有 S12=L1+C12=0+4=4 ； S13=L1+C13=0+18=18 min (S12,S13)= S12 =4 给边[ V1，V2]中的未标号的点V2 标以（4，1），表示从V1 到V2 的距离为4，并且在V1到V2的最短路径上V2的前面的点为V1. ③这时I={V1 ，V2},J={V3，V4，V5，V6 ,V7}，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={[ V1，V3]，[ V2，V3]，[ V2，V4]}，并有 S23=L2+C23=4+12=16 ；S24=L2+C24=4+16=20 ；min (S23,S24 , S13)= S23 =16 给边[ V2，V3]中的未标号的点V3 标以（16，2） ④这时I={V1 ，V2 ，V3},J={V4，V5，V6 ,V7}，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={[ V2，V4]，[ V3，V4]，[ V3，V5]}，并有 S34=L3+C34=16+2=18 ； S35=L3+C35=16+6=22 ； S24=L2+C24=4+16=20 min (S34,S35,S24)= S34 =18 给边[ V3，V4]中的未标号的点V4 标以（18，3） ⑤这时I={V1 ，V2 ，V3 ，V4},J={V5，V6 ,V7}，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={ [ V4，V6]，[ V4，V5]，[ V3，V5]}，并有 S46=L4+C46=18+7=25 ； S45=L4+C45=18+8=26 ；min (S46,S45 ,S35)= S35 =24 给边[ V3，V5]中的未标号的点V5 标以（24，3） ⑥这时I={V1 ，V2 ，V3 ，V4 ，V5 },J={ V6 ，V7}，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={[ V5，V7]，[ V4，V6] }，并有 S57=L5+C57=22+5=27 ；min (S57,S46)= S46 =25 给边[ V4，V6]中的未标号的点V6 标以（25，4） ⑦这时I={V1 ，V2 ，V3 ，V4 ，V5 ，V6 },J={ V7}，边的集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}={[ V5，V7]，[ V6，V7] }，并有 S67=L6+C67=25+6=31 ；min (S57,S67)= S57 =27 给边[ V5，V7]中的未标号的点V7 标以（27，5） ⑧此时I={V1 ，V2 ，V3 ，V4 ，V5 ，V6 ，V7},J=空集，边集合{[Vi，Vj] ︳Vi，Vj两点中一点属于I,而另一点属于J}=空集，计算结束。 ⑨得到最短路。从V7 的标号可知从V1 到V7 的最短时间为27分钟。 即：配送路线为： V1 →V2 →V3 →V5 →V7 （14）最小生成树问题 某电力公司要沿道路为8个居民点架设输电网络，连接8个居民点的道路图如图所示，其中V1，……，V8表示8个居民点，图中的边表示可架设输电网络的道路，边上的赋权数为这条道路的长度，单位为公里，请设计一个输电网络，联通这8个居民点，并使总的输电线路长度为最短 。 V2 4 V1 2 V3 G V4 2 4 6 V5 7 5 V8 2 3 2 5 V6 3 V7 ①在图中找到一个圈（V1，V2，V5，V3）,并知在此圈上边[V1，V2]和 [V3，V5]的权数4为最大，在图中去掉边[V1，V2] ； ②在图中找到一个圈（V3，V4，V8 ，V5 ，V3, V1），去掉其中权数最大的边 [V4，V8]； ③在图中找到一个圈（V3，V4， V5，V3），去掉其中权数最大的边 [V4，V5]； ④在图中找到一个圈（V5，V2，V6，V7 ，V5），去掉其中权数最大的边 [V2，V6]； ⑤在图中找到一个圈（V5，V7， V8，V5），去掉其中权数最大的边 [V5，V8]。 ⑥在图中已找不到任何一个圈了，可知此即为图G的最小生成树。 这个最小生成树的所有边的总权数为2+2+4+2+3+3+2=18 （15）最大流问题 某地区的公路网如图所示，图中V1，……，V6为地点，边为公路，边上所赋的 权数为该段公路的流量（单位为千辆/小时），请求出V1 到V6 的最大流量。 V2 8 4 6 5 6 10 6 5 V5 12 V4 V1 6 V6 V3 解：第一次迭代： 选择路为V1 →V3 →V6 。弧（V3 ，V6）的顺流流量为5，决定了pf=5，改进的网络流量图如图所示： V2 0 6 8 4 0 6 10 5 5 0 6 5 0 0 0 5 0 0 V5 12 0 5→ V4 V1 6 0 5 0 V6 →5 第一次迭代 后的总流量 V3 第二次迭代： 选择路为V1 →V2 →V5 →V6 。弧（V1 ，V2）的顺流流量为6，决定了pf=6，改进的网络流量图如图所示： V2 6 0 6 0 6 5 5 6 0 第二次迭代 后的总流量 0 0 0 8 4 5 2 0 0 6 V5 12 6 0 6 5 0 6 11→ V4 V1 V6 →11 第三次迭代：选择路为V1→V4 →V6 。弧（V1 ，V4）的顺流流量为6， 决定了pf=6，改进的网络流量图如图所示： V2 6 0 6 5 5 6 4 0 0 6 0 0 0 5 2 0 6 V3 V5 6 6 17→ V4 V1 6 0 5 0 6 V617 → 第三次迭代 后的总流量 V3 第四次迭代：选择路为V1→V3→V4 →V2→V5→V6 。弧（V2 ，V5）的顺流流量 为2，决定了pf=2，改进的网络流量图如图所示： V2 6 0 2 0 2 4 0 5 3 5 7 4 6 0 6 2 0 2 5 0 5 第四次迭代 后的总流量 0 6 8 0 V5 6 4 6 8 6 V4 19→ V1 V6 19→ V3 第五次迭代：选择路为V1→V3→V4→V5→V6 。弧（V1 ，V3）的顺流流量为3， 决定了pf=3，改进的网络流量图如图所示： V2 6 0 2 2 0 3 0 7 11 4 1 6 5 2 0 5 2 0 8 3 0 V5 4 1 8 0 5 第五次迭代 后的总流量 6 11 V4 22→ V1 V6 22→ V3 在通过第五次迭代后在图中已找不到从发点到收点的一条路上的每一条弧顺流容量都大于零，运算停止。我们已得到此网络的从 V1到V6的最大流量，最大流量为22，也就是公路的最大流量为每小时通过22千辆车。 (16) 最小费用最大流问题 请求下面网路图中的最小费用最大流,图中弧(Vi , Vj)的赋权（Cij , bij），其中Cij为从Vi 到Vj 的流量，bij 为Vi 到Vj 的单位流量的费用。 V2 （5，3） （2，4） V4 （2，4） V1 （4，1） （1，1） （1，2） （1，2） V6 （5，2） V3 （3，3） V5 （17）一台机器、n个零件的排序问题 某车间只有一台高精度的磨床，常常出现很多零件同时要求这台磨床加工的情况，现有六个零件同时要求加工，这六个零件加工所需要的时间如表所示： 零件 加工时间/小时 零件 加工时间/小时 1 1.8 4 0.9 2 2.0 5 1.3 3 0.5 6 1.5 我们应该按照什么样的加工顺序来加工这六个零件，才能使得这六个零件在车间里停留的平均时间为最少？ 解：对于一台机器n个零件的排序问题，我们按照加工时间从少到多排出加工零件的顺序就能使各个零件的平均停留时间为最少。 零件 加工时间/小时 停留时间 零件 加工时间/小时 停留时间 3 0.5 0.5 6 1.5 4.2 4 0.9 1.4 1 1.8 6.0 5 1.3 2.7 2 2.0 8 （18）两台机器、n个零件 某工厂根据合同定做一些零件，这些零件要求先在车床上车削，然后再在磨床上加工，每台机器上各零件加工时间如表所示： 零件 车床 磨床 零件 车床 磨床 1 1.5 0.5 4 1.25 2.5 2 2.0 0.25 5 0.75 1.25 3 1.0 1.75 应该如何安排这五个零件的先后加工顺序才能使完成这五个零件的总的加工时间为最少？ 解：我们应该一方面把在车床上加工时间越短的零件，越早加工，减少磨床等待的时间，另一方面把在磨床上加工时间越短的零件，越晚加工，也就是说把在磨床上加工时间越长的零件，越早加工，以便充分利用前面的时间，这样我们得到了使完成全部零件加工任务所需总时间最少的零件排序方法。 车床 5 3 4 1 2 磨床 5 3 4 1 2 等待时间 （19）在一台车床上要加工7个零件，下表列出它们的加工时间，请确定其加工顺序，以使各零件在车间里停留的平均时间最短。 零件 1 2 3 4 5 6 7 Pi 10 11 2 8 14 6 5 解：各零件的平均停留时间为： 6P15P24P33P42P5P6 6由此公式可知，要让停留的平均时间最短，应该让让加工时间越少的零件排在越前面，加工时间越多的零件排在后面。 所以，此题的加工顺序为：3，7，6，4，1，2，5 (20) 有7个零件，先要在钻床上钻孔，然后在磨床上加工，下表列出了各个零件的加工时间，确定各零件加工顺序，以使总加工时间最短。 零件 1 2 3 4 5 6 7 钻床 6.7 2.3 5.1 2.3 9.9 4.7 9.1 磨床 4.9 3.4 8.2 1.2 6.3 3.4 7.4 解：此题为两台机器，n 个零件模型，这种模型加工思路为：钻床上加工时 间越短的零件越早加工，同时把在磨床上加工时间越短的零件越晚加工。 根据以上思路，则加工顺序为：2，3，7，5，1，6，4。 （21）根据下表绘制计划网络图 V2 a V6 b V4 f h d V1 c V3 解： e j V7 i V5 g V3 c d V4 f a V1 b V2 e V6 g V5 (22)对21题，通过调查与研究对完成每个活动的时间作了3种统计，如表所示，请求出每个活动的最早开始时间，最晚开始时间，最早完成时间，最晚完成时间；找出关键工序；找出关键路线；并求出完成此工程项目所需平均时间；如果要求我们以98%的概率来保证工作如期完成，我们应该在多少天以前就开始这项工作。 活动（工序） 乐观时间/天 最可能时间/天 悲观时间/天 a 1.5 2 3 b 3 4 6 c 3.5 5 6 d 3 4 5.5 e 2.5 3 4 f 1 2 4 g 2 4 5 解：显然这三种完成活动所需时间都具有一定概率，根据经验，我们可以假定这些时间的概率分布近似服从β分布，这样我们可用如下公式计算出完成活动所 a4mbba2 ) 需的平均时间：T= 以及方差：δ2 =(66活动 T（平均时间） δ2 （方差） 活动 T（平均时间） δ2 （方差） a 2.08 0.07 e 3.08 0.07 b 4.17 0.26 f 2.17 0.26 c 4.92 0.18 g 3.83 0.26 d 4.08 0.18 工序安排： 工序 最早开始时最迟开始时最早完成时最迟完成时间 时差 是否关键工间 间 间 序 a 0 0 2.08 2.08 2.08 √ b 0 0 4.17 4.17 0 c 4.17 5 9.08 9.92 0.83 √ d 4.17 4.17 8.25 8.25 0 e 4.17 5.17 7.25 8.25 1 f 9.08 9.92 11.25 12.08 0.83 √ g 8.25 8.25 12.08 12.08 0 本问题关键路径是：B--D—G；本工程完成时间是：12.08 这个正态分布的均值 E (T ) =12.08 其方差为： σ 2 ＝σb2 +σd2 +σg 2 =0.70 则σ ＝0.84 当以98％的概率来保证工作如期完成时，即：φ(u ) = 0.98，所以u=2.05 T—12.08此时提前开始工作的时间Ｔ满足：=2.05 0.84所以Ｔ＝13.8 ≈ 14 （23）矩阵对策的最优纯策略 甲乙乒乓球队进行团体对抗赛，每对由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛。比赛共赛三局，规定每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。甲队的策略集为S1={α1，α2，α3}，乙队的策略集为S1={β1，β2，β3}，根据以往比赛得分资料，可得甲队的赢得矩阵为A，如下： A= 1 1 1 1 -1 -3 3 -1 3 试问这次比赛各队应采用哪种阵容上场最为稳妥。 解：甲队的α1，α2，α3 三种策略可能带来的最少赢得，即矩阵A中每行的最小元素分别为： 1，-3，-1， 在这些最少赢得中最好的结果是1，即甲队应采取策略α1 ，无论对手采用什么策略，甲队至少得1分。而对乙队来说，策略β1，β2，β3 可能带来的最少赢得，即矩阵A中每列的最大因素（因为两人零和策甲队得分越多，就使得乙队得分越少），分别为： 3，1，3， 其中乙队最好的结果为甲队得1分，这时乙队采取β2 策略，不管甲队采用什么策略甲队的得分不会超过1分（即乙队的失分不会超过1）。这样可知甲队应采用α1 策略，乙队应采取β2 策略。把这种最优策略α1 和β2 分别称为局中人甲队、乙队的最优纯策略。这种最优纯策略只有当赢得矩阵A=（aij）中等式 max min aij = min max aij i j j i 成立时，局中人才有最优纯策略，并把（α1 ，β2）称为对策G在纯策略下的解，又称（α1 ，β2）为对策G的鞍点。 （24）矩阵对策的混合策略 A= 5 9 8 6 解：首先设甲使用α1 的概率为X1’，使用α2 的概率为X2’，并设在最坏的情况下（即乙出对其最有利的策略情况下），甲的赢得的平均值等于V。这样我们建立以下的数学关系： 1.甲使用α1 的概率X1’和使用α2 的概率X2’的和为1，并知概率值具有非负性，即X1’+ X2’=1，且有X1’≧0，X2’≧0. 2.当乙使用β1 策略时，甲的平均赢得为：5X1’+ 8X2’，此平均赢得应大于等于V，即5X1’+ 8X2’≧V 3.当乙使用β2 策略时，甲的平均赢得为：9X1’+ 6X2’，此平均赢得应大于等于V，即9X1’+ 6X2’≧V 第二步，我们来考虑V的值，V的值与赢得矩阵A的各因素的值是有关的，如果A的各元素的值都大于零，即不管甲采用什么策略，乙采用什么策略，甲的赢得都是正的。这时的V值即在乙出对其最有利的策略时甲的平均赢得也显然是正的。因为A的所有元素都取正值，所以可知V﹥0. Xi'第三步，作变量替换，令Xi =(i=1，2) V考虑到V﹥0，这样把以上5个数量关系式变为： 1X1+ X2 =，X1≧0，X2≧0， V5X1+ 8X2 ≧1 9X1+ 6X2 ≧1 1对甲来说，他希望V值越大越好，也就是希望的值越小越好，最后，我们就 V建立起求甲的最优混合策略的线性规划的模型如下： min X1+ X2 约束条件： 5X1+ 8X2 ≧1 9X1+ 6X2 ≧1 X1≧0，X2≧0 同样求出乙最优混合策略，设y1’, y2’分别为乙出策略β1，β2 的概率，V为甲出对其最有利的策略的情况下，乙的损失的平均值。 同样我们可以得到： y1’+ y2’=1, 5y1+ 9y2 ≦V 8y1+ 6y2 ≦V y1’≧0，y2’≧0. yi'同样作变量替换，令yi =(i=1，2) V1得关系式： y1+ y2 = V5y1+ 9y2 ≦1 8y1+ 6y2 ≦1 y1≧0，y2≧0. 1乙希望损失越少越好，即V越小越好而越大越好，这样我们也建立了求乙的 V最优混合策略的线性规划的模型如下： max y1+ y2 约束条件： 5y1+ 9y2 ≦1 8y1+ 6y2 ≦1 y1≧0，y2≧0. (25)完全信息动态对策 某行业中只有一个垄断企业A，有一个潜在进入者企业B，B可以选择进入或不进入该行业这两种行动，而A当B进入时，可以选择默认或者报复两种行动，如果B进入后A企业报复，将造成两败俱伤的结果，但如果A默认B进入，必然对A的收益造成损失，如果B不进入，则B无收益而A不受损，把此关系用图表示如下：（求最后的策略） 默许 B 进入 A 报复 不进入 50，100 —20，0 0，200 0，200 假设B进入，A只能选择默许，因为可以得到100的收益，而报复后只得到0.假设A选择报复，B只能选择不进入，因为进入损失更大。因此，（B选择不进入，A选择报复）和（B选择进入，A选择默许）都是纳什均衡解，都能达到均衡。 但在实际中，（B选择不进入，A选择报复）这种情况是不可能出现的。因为B知道他如果进入，A只能默许，所以只有（B选择进入，A选择默许）会发生。或者说A选择报复行动是不可置信的威胁。对策论的术语中，称（B选择进入，A选择默许）为精炼纳什均衡。 当然如果A下定决心一定要报复B，即使自己暂时损失，这时威胁就变成了可置信的，B就会选择不进入，（B选择不进入，A选择报复）就成为精炼纳什均衡。 （26）设有参加对策的局中人A和B，A的损益矩阵如下，求最优纯策略和对策值。 β1 β2 β3 α1α2 α3 -500 -100 700 100 0 200 500 -200 -700 解:矩阵α1，α2，α3中每行的最小元素分别为： -500，0，-700，（最大） 矩阵β1，β2，β3中每列的最大因素分别为： 500，0，700，（最小） 因为 max min aij = min max aij = 0 i j j i 所以最优纯策略为 (α 2 , β 2 ) ,对策值为0 （27）已知面对四种自然状态的三种备选行动方案的公司收益如下表所示： 方案 自然N1 N2 N3 N4 状态 ﹣6 S1 15 8 0 S2 4 14 8 3 S3 1 4 10 12 假定不知道各种自然状态出现的概率请分别用以下五种方法求最优行动方案： ①最大最小准则 min [α（S1，Nj）]=min{15，8，0，﹣6}=﹣6 1≦j≦3 min [α（S2，Nj）]=min{4，14，8，3}=3 1≦j≦3 min [α（S3，Nj）]=min{1，4，10，12}=1 1≦j≦3 再从这些最小收益中选取一个最大值3，即 max{min [α（Si，Nj）]}=max{﹣6，3，1}=3. 在此准则下，方案S2 为最优。 ②最大最大准则 max [α（S1，Nj）]=max{15，8，0，﹣6}=15 1≦j≦3 max [α（S2，Nj）]=max{4，14，8，3}=14 1≦j≦3 max [α（S3，Nj）]=max{1，4，10，12}=12 1≦j≦3 最后得到 max{max [α（Si，Nj）]}=max{15，14，12}=15 在此准则下，方案S1 为最优。 ③等可能性准则 E(S1)=0.25×15+0.25×8+0+0.25×(﹣6)=4.25 E(S2)=0.25×4+0.25×14+0.25×8+0.25×3=7.25 E(S3)=0.25×1+0.25×4+0.25×10+0.25×12=6.75 其中E(S2)最大，根据等可能性准则方案S2 为最优。 ④乐观系数准则（取α=0.6） CVi=α·max [α（Si，Nj）]+(1－α)·min [α（Si，Nj）] CV1=0.6×15+0.6×8+0+0.6×(﹣6)=10.2 CV2=0.6×4+0.6×14+0.6×8+0.6×3=17.4 CV3 =0.6×1+0.6×4+0.6×10+0.6×12=16.2 即得max [CVi]=17.4 ，故方案S2 为最优方案。 1≦j≦3 ⑤后悔值准则 N1 N2 N3 N4 Max a′ij 1≤ j ≤ 4 S1 0 6 10 18 18 11（min） S2 11 0 2 9 S3 14 10 0 0 14 min max a′ij=min{18，11，14}=11，故在后悔值准则下取方案S2。 i j （28）下表是过去12个月的某种产品的销售量的数据： 月 销售量 月 销售量 1 105 7 140 2 135 8 135 3 115 9 100 4 100 10 85 5 95 11 100 6 120 12 105 1.分别取n=3和n=4用移动平均法对第13月的销售量进行预测，并进行比较。 2.分别用α=0.3和α=0.5的指数平滑法对第13月的销售量进行预测，并进行比较。 解:①移动平均法：移动平均数=∑（最近n个数据值）/n 85100105n=3 时，第 13 个月的销售量为：≈96.7 385100105100n＝4 时，第 13 个月的销售量为：≈97.5 4②指数平滑法：Ft+1=α·yt+(1-α)Ft Ft+1 为t+1时期的时间序列的预测值； yt 为第t时间的时间序列的实际值； Ft 为第t时间的时间序列的预测值； α 为平滑系数（0≦α≦1） 月份 销售量 α ＝0.3 时的预测α ＝0.5 时的预测值 值 1 105 2 135 105 105 3 115 114 120 4 100 114.3 117.5 5 95 110.01 108.75 6 120 105.507 101.875 7 140 109.8549 110.9375 8 135 118.8984 125.4688 9 100 123.7289 130.2344 10 85 116.6102 115.1172 11 100 107.1272 100.0586 12 105 104.989 100.0293 13 104.9923 102.5146 一、 考虑下列线性规划（20分） MaxZ=2X1+3X2 2X1+ 2X2+X3=12 X1+2X2 +X4=8 4X1 +X5=16 4X2 +X6=12 Xj≥0（j=1,2,…6） 其最优单纯形表如下： 基变量 X1 X2 X3 X4 X5 X6 X3 0 0 0 1 -1 -1/4 0 X1 4 1 0 0 0 1/4 0 X6 4 0 0 0 -2 1/2 1 X2 2 0 1 0 1/2 -1/8 0 σj 0 0 0 -3/2 -1/8 0 1）当C2=5时，求新的最优解 2）当b3=4时，求新的最优解 3）当增加一个约束条件2X1+X2≤12，问最优解是否发生变化，如果发生变化求新解？ 解当C2=5时 σ4=－5/2 σ5=1/8＞0所以最优解发生变化 基变量 X1 X2 X3 X4 X5 X6 0 X3 0 0 0 1 -1 -1/4 0 2 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 5 X2 2 0 1 0 1/2 -1/8 0 σj 0 0 0 -5/2 1/8 0 0 X3 2 0 0 1 －2 0 1/2 2 X1 2 1 0 0 1 0 -1/2 0 X5 8 0 0 0 -4 1 2 5 X2 3 0 1 0 0 0 1/4 σj 0 0 0 -2 0 -1/4 最优解为X1=2，X2=3,Z＝19 2）当b3=4时 基变量 X1 X2 X3 X4 X5 X6 0 X3 3 0 0 1 -1 -1/4 0 2 X1 1 1 0 0 0 1/4 0 0 X6 -3 0 0 0 -2 1/2 1 3 X2 5/2 0 1 0 1/2 -1/8 0 σj 0 0 0 -3/2 -1/8 0 0 X3 9/2 0 0 1 0 -1/2 1 2 X1 1 1 0 0 0 1/4 0 0 X4 3/2 0 0 0 1 -1/4 -1/2 3 X2 7/4 0 1 0 0 0 1/4 σj 0 0 0 0 -1/2 -3/4 此时最优解为X1=1，X2=7/4,Z＝29/4 3)增加一个约束条件 基变量 X1 X2 X3 X4 X5 X6 X7 X3 0 0 0 1 -1 -1/4 0 0 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 0 X2 2 0 1 0 1/2 -1/8 0 0 X7 12 2 1 0 0 0 0 1 σj 0 0 0 -3/2 -1/8 0 0 X3 0 0 0 1 -1 -1/4 0 0 X1 4 1 0 0 0 1/4 0 0 X6 4 0 0 0 -2 1/2 1 0 X2 2 0 1 0 1/2 -1/8 0 0 X7 2 0 0 0 －1/2 －3/8 0 1 σj 0 0 0 -3/2 -1/8 0 0 由于X7＝2大于0，所以最优解不变 二、给出线性规划问题（20分） MinZ=2X1+3X2+ 5X3+ 6X4 X1+ 2X2+3X3+ X4≥2 -2X1+X2- X3 +3X4≤-3 Xj≥0（j=1,…4） 1）写出其对偶问题 2）用图解法求解对偶问题 3）利用2）的结果及根据对偶问题性质写出原问题的最小值 解： 对偶问题为 Maxw =2y1-3y2 y1-2y2≤2 2y1+y2≤3 3y1-y2≤5 y1+3y2≤6 y1≥0,y2≤0 2)根据图解法得对偶问题最优解为Y＝(8/5,-1/5) W=19/5 3)原问题和对偶问题如果都有最优解，则他们的最优解目标函数值相等，所以原问题的最小值＝19/5 三、某公司从三个产地A1，A2，A3将物品运往四个销售地B1，B2，B3，B4， 各产地的产量、各销售地的销量和各产地运往各销售地每件物品的运费如表，问如何调运，使总运费最小（20分） 解：初始解为 A1 A2 A3 销量/t B1 80 80 B2 70 70 B3 70 20 90 B4 30 80 110 产量/t 100 100 150 计算检验数 A1 A2 A3 销量/t B1 －1 0 11 80 B2 4 2 0 70 B3 0 0 －2 90 B4 0 7 0 110 产量/t 100 100 150 由于X11和X33的检验数小 A1 A2 A3 销量/t B1 8 5 17 80 B2 14 8 7 70 B3 17 13 12 90 B4 12 15 9 110 产量/t 100 100 150 于0，所以不是 最优解，调整得 A1 A2 A3 销量/t B1 80 80 B2 70 70 B3 20 70 90 B4 100 10 110 产量/t 100 100 150 重新计算检验数 A1 1 4 2 0 A2 0 0 0 5 A3 13 0 0 0 销量/t 80 70 90 110 由于所有的检验数都大于等于0，所以得到最优解。 四、有4个工人，要指派他们分别完成4项工作，每人做各项工作所消耗的时间如下表：(20分) 工作 A B C D 工人 甲 7 9 17 14 乙 6 7 14 6 丙 4 8 7 15 丁 6 9 12 8 问指派哪个人去完成哪项工作，可使总的消耗时间为最小？ B1 B2 B3 B4 产量/t 100 100 150 解： 最优解为 X= 0 1 0 0 0 0 0 1 0 0 1 0 1 0 0 0 总消耗时间为28 五、建模题（20分） 1、某厂根据订货合同在今后3个季度多某个产品的需求如表，设每组织一次生产的生产费用为3千元，每件产品的生产成本为1千元，每一件产品储存一个季度的费用为0.2千元，且第一季度开始和第三季度末绝没有库存，生产能力不超过5件，问在上述条件下如何安排各季度的生产与库存，使总成本最低？ （只需建模，写出阶段、状态变量含义、决策变量含义、状态转移方程、指标函数、最优函数） 季度 需求量Dk 1 3 2 3 3 2 解，设阶段K＝1，2，3 状态变量Sk表示为第k 个季度初的库存量 决策变量Uk表示在第k个季度的生产量 Sk+1=Sk+Uk-Dk 阶段指标Vk＝3+Uk+0.2Sk 递推公式fk=opt{vk+fk+1(sk+1)} 2、某钻井队要从以下10个可供选择的井位中确定5个钻井探油，使总的钻探费用为最小，若10个井位的代号为s1,s2,…s10，相应的钻探费用位c1,c2,…c10，，并且选择上要满足下列限制条件： 1）选择了s3或s4，就不能选s5，反过来也一样 2）在s5，s6，s7，s8中最多只能选两个 试建立这个问题的模型 解： 设Xi= 0 表示该不选择点钻井 1 表示选择该点钻井 Maxz =c1X1+c2X2+…+c10X10 X1+X2+…+X10=5 X3+X5≤1 X4+X5≤1 X5+X6+X7+X8≤2 Xi=0 or 1 因篇幅问题不能全部显示，请点此查看更多更全内容