运筹学试卷1~4

运筹学试卷(1)

一、回答下面问题(每小题3分)

1.在单纯形法计算中,如果不按最小比值规则确定换基变量,则在下一个解中一定会出现 。

2. 原问题无界时，其对偶问题 ，反之，当对偶问题无可行解时，原问题 。 3．已知y0为线性规划的对偶问题的最优解，若y0>0，说明在最优生产计划中对应的资源 。

4．已知y0为线性规划的对偶问题的最优解，若y0=0，说明在最优生产计划中对应的资源 。

5．已知线形规划问题的原问题有无穷多最优解，则其对偶问题的最优解一定是 。 6．m个产地n个销地的产销平衡运输问题的模型其决策变量的个数是 个；基变量的个数是 个；决策变量的系数列向量的特点是 。

7．用位势法求解运输问题，位势的含义是 ；行位势与列位势中有一个的取值是任意的，这是因为 。

8.用割平面法求解整数规划，割平面割去了 ；但未割去 。 9．按教材中的符号写出最大流问题的数学模型 。 10．什么是截集，何谓最小截集？

二、（10分）下表是用单纯形法计算到某一步的表格，已知该线性规划的目标函数值为z=14

表1

cj x3 x1 σj （1） 求a—g的值；（8分）

（2） 表中给出的解是否为最优解。（2分）

三、（每小题6分共12分）车间为全厂生产一种零件，其生产准备费是100元，存贮费是0.05元／天·个，需求量为每天30个，而且要保证供应。

1 设车间生产所需零件的时间很短（即看成瞬时供应）；2 设车间生产零件的生产率是

x1 2 a c d b x2 0 e -1 x3 1 0 f x4 1/5 1 g 50个／天。

要求在（1）（2）条件下的最优生产批量Q*，生产间隔期t*和每天的总费用C*。

四、（18分） 某公司下属甲、乙两个厂，有A原料360斤，B原料640斤。甲厂用A、B两种原料生产

x1,x2两种产品，乙厂也用A、B两种原料生产x3,x4两种产品。每种单位产品所消耗各种原料的数量及产值、分配等如下

工厂 产品 A 原料 B 产值（百元） 10 4 3 330 4 3 4 310 甲 分配原料 x1 x2 8 160 x3 x4 5 200 乙 分配原料 1． 求各厂最优生产计划；（12分）

2． 问公司能否制定新的资源分配方案使产值更高？（6分）

五、（10分）已知有六个村庄，相互间道路的距离如图所示，已知各村庄的小学生数为：A村50人，B村40人，C村40人，D村60人，E村50人，F村90人。现六村决定合建一所小学，问小学应建在哪村，才能使学生上学所走的总路程最短？

A

2 B 6 8 D 4 1 6 7 1 F

C 3 E 3

六、（8分）A、B、C、D、E、F分别代表陆地和岛屿，1、2、3??14表示桥梁及其编号。若河两岸分别敌对的双方部队占领，问至少应切几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的，试用图论方法进行分析。（提示：以陆地为点，桥梁为弧，两点之间的桥梁数为弧的容量。）

七、（12分） 设有三个化肥厂供应四个地区的农用化肥。各化肥的年产量，各地区的需求量，化肥的运价如下表所示，请写出产销平衡运输表。

A1 A2 A3 B1 16 12 19 B2 13 14 21 B3 22 18 23 B4 16 15 ? 产量 50 60 50 最低要求 最高要求 30 45 70 70 0 30 10 不限 运筹学试卷（2）

一、填空（15×2分）

1、在线性规划问题的约束方程AX=b,X≥0中，对于选定的基B，令非基变量XN=0，得到的解X= ；若 ，则称此基本解为基本可行解；若 ，则称此基本可行解为退化的解；若 ，则此基可行解为最优解。

2、用对偶单纯形法求解线性规划问题时，根据b r 确定xr为出基变量；根据最小比值法则θ= ，确定x k为进基变量。

3、在单纯形法的相邻两次迭代中，迭代前的可行基B和迭代后的可行基B的逆矩阵存在关系：B-1 = Erk B-1其中Erk= 。

4、已知y*为某线形规划问题的对偶问题的最优解，若y*>0，说明在最优化生产计划中对应的资源 。

5、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有 个；其中决策变量xij所对应的列向量pij= .。

6、对于Max 型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：

XB b x1 x2 x3 x4 x2 3/4 0 1 7/4 -11/4

则对应的割平面方程为 。

7、用匈牙利法解分配问题时，当 则找到了分配问题的最优解；称此时独立零元素对应的效益矩阵为 。 8、将网络D=（V，A，C）的顶点集合V分割成两个非空集合V1和V1，使VS∈V1，Vt∈V1，则弧集 成为分割VS和Vt的截集；称 为截集的容量。 二、问答题（2×5分）

1．材写出目标规划的一般模型；

2．试叙动态规划的最优性原理。

三、已知某线性规划问题的目标函数为max=5x1+3x2,约束形式为“≤”。设x3,x4为松弛变量，用单纯形法计算是某一步的表格如下所示： （15分

Cj 5 3 0 0 ??CB 0 5 -Z XB x3 x1 b -10 x1 x2 x3 x4 c 0 1 1/5 d e 0 1 b -1 f g （1） 求a~g的值；

（2） 表中给出的解是否为最优解，并求出最优解。

四、已知某线性规划问题，其初始及最优单纯形表如下：（15分）

Cj CB 0 0 0 XB x3 x4 x5 σj b 12 9 8 1 2 0 0 0 X1 x2 x3 x4 x5 2 2 1 0 0 3 0 0 1 1 0 2 0 0 1 1 2 0 0 0 最优解表 Cj CB 1 0 2 XB x1 x4 x2 σj (1)求出对偶问题的最优解;

(2)求C1的变化范围,使最优基不变;

(3)如果b1由12变为16,求最优解.

五、种机器可以在高低两种不同的负荷下生产,高负荷生产时,产品的年产量g与投资的机器数量x的关系为:g(x)=8x,这时机器的年完好率a=0.7;在低负荷下生产时产品的年产量h和投入的机器数量y的关系为:h(x)=5y,这时机器的年完好率b=0.7。假定开始生产时的完好机器数量s1=1000台，试制定一个5年计划，确定每年投入高、低两种负荷下生产的完好机器数

B 2 3 4 1 2 0 0 0 x1 x2 x3 x4 x5 1 0 1/2 0 -1/2 0 0 -3/2 1 3/2 0 1 0 0 1/2 0 0 -1/2 0 -1/2 量，使5年内产品的总产品量最大，并且5年末完好的机器数量是500台。 （1） 写出阶段变量、状态变量、决策变量；（6分）

（2） 写出第k阶段的决策集合与状态转移方程；（9分）

（3） 写出递推方程，并规范化求解。（选作10分）

五、 如图所示是某地区交通运输示意图，s是起点t终点，弧旁数字为cij(fij)。（15分）

（1）写出此交通运输规划的线性规划数学模型；

（2）用标号法求出从s到t最大流及其流量；

（3）写出该网络的最小割集。

运筹学试卷(3)

一、填空(11×3分)

1、在线性规划问题的约束方程AX=b,X≥0中，对于选定的基B，令非基变量XN=0，得到的解X= ；若 ，则称此基本解为基本可行解；若 ，则称此基本可行解为退化的解。

2、用单纯形法求解线性规划问题的迭代步骤中，根据σK= 确定xk为进基变量；根据最小比值法则?= ，确定xr为出基变量。 3、平衡运输问题（m个产地，n个销地）的基可行解中基变量共有 个。 4、对于Max型整数规划问题，若其松弛问题的最优单纯形表中有一行数据为：

XB x2 b 3/4 x1 0 x 1 x 7/4 x -11/4 则对应的割平面方程为 。 5、用匈牙利法解分配问题时，当 则找到了分

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