最全的运筹学复习题及答案 - 图文

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

A．m个 B．n个 C．Cnm D．Cmn个 2．下列图形中阴影部分构成的集合是凸集的是 A

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

A．基可行解的非零分量的个数不大于mB．基本解的个数不会超过Cmn个C．该问题不会出现退化现象D．基可行解的个数不超过基本解的个数E．该问题的基是一个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

则ABD 。A．该问题的典式不超过CNM个B．基可行解中的基变量的个数为m个C．该问题一定存在可行解D．该问题的基至多有CNM=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、单纯形法解题的基本思路？ 可行域的一个基本可行解开始，转移到另一个

基本可行解，并且使目标函数值逐步得到改善，直到最后球场最优解或判定原问题无解。

五、分别用图解法和单纯形法求解下列线性规划问题．并对照指出单纯形迭代的

每一步相当于图解法可行域中的哪一个顶点。

六、用单纯形法求解下列线性规划问题：

七、用大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。

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分) maxz?3x1＋x2＋5x3（劳动力）?6x1＋3x2＋5x3?45 ?（原材料）?3x1＋4x2＋5x3?30?x，x，x?0?123求：（1）线性规划问题的最优解； 首先将问题标准化：

maxz?3x1＋x2＋5x3?6x1＋3x2＋5x3?x4?45 ??3x1＋4x2＋5x3?x5?30?x，x，x,x,x?0?12345cj 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）求对偶问题的数学模型及其最优解； minw?45y1?30y2?6y1?3y2?3?3y?4y?1 ?12??5y1?5y2?5??y1?0,y2?0y1*=0,y2*=1

(3) 最优解不变的情况下，求产品A的利润允许变化范围； 最优解不变的情况下，?c1?0,c1?3

（4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？ 有利

单位材料的影子价格是1元，10元钱购进15单位的材料的单位价格为2/3元，低于影子价格。同时，在保持最优基不变的情况下

?30?b2?15

购进15吨的原材料，最优基不变。该材料的影子价格仍为1元。

（5）当可利用的资源增加到60单位时，求最优解。

b'?B?1b?1?1??45???15?

1????????060??12?????5??cj 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'?B?1P2?1?1??3??1?

1??????2???02?5???????5???2?c2?CBB?1P2'?1??1??05??2???1???5?所以最优解不变?2?0

（7）增加约束条件2x1+x2+3x3≤20，对原最优解有何影响，对对偶解有何影响？

增加的约束条件，相当于增加了一个约束方程

2x1?x2?3x3?x6?20

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令：xi???0当不选择simaxz?c1x1?c2x2?c3x3?c4x4?c5x5?c6x6?c7x7?c8x8

?x1?x7?x8?1?x?x?17?6??x2?x5?1??x1?x4?1?x2?x3?0???xi?0或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甲?2529314237??3938262033乙???

丙?3427284032???丁?2442362345?戊??2427262032??各行减最小值，各列减最小值：得

ABCDE甲?045177??1918508乙???

丙?70?13????丁?11912?17?戊??475?7??变换得

ABCDE甲?045乙??18174丙?70??丁??1811戊??3647?07?? 14????16??6??18进一步

ABCDE甲?001183??1813003乙???丙?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)?fk?1(sk?xk)}k?n?1,?,1 ?fk(sk)?0max?xk?sk? ?fn(sn)?maxgn(xn)?xn?sn ?第三阶段，k=3 X3=s3

f3(s3)?maxg3(x3)

x3?s3x3 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， 0?s2?3， 0?x2?s2

f2(s2)?max{g2(x2)?f3(s2?x2)}

0?x2?s2x2 s2 f2(s2)?max{g2(x2)?f3(s2?x2)} 0?x2?s2f2(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, 0?x1?s1 x1 f1(s1)?max{g1(x1)?f1(s1?x1)} 0?x1?s1s1 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.代替约束条件，则此问题的数学模型为： maxZ?2x1?3x2 S?t? x1?2x2?8

4x1?16

4x2?12 x1,x2?0 型。

2、本章重点难点分析

建立初始单纯形表格，并用单纯形方法求解线性规划数学模型。 3、本章典型例题分析

例： maxZ?20x1?15x2 用单纯形法求解 S?t? 2x1?3x2?600

2x1?x2?400

x1,x2?0

解：先化为标准形式：maxZ?20x1?15x2 S?t? 2x1?3x2?x3?600

2x1?x2?x4?400

xj?0(j?1,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

解

本文来源：https://www.bwwdw.com/article/hypr.html