发布时间 : 星期日 文章运筹学更新完毕开始阅读f18033cf89eb172ded63b7b6
运筹学试卷(1)
一、回答下面问题(每小题3分)
1.在单纯形法计算中,如果不按最小比值规则确定换基变量,则在下一个解中一定会出现 。 2. 原问题无界时，其对偶问题 ，反之，当对偶问题无可行解时，原问题 。
3．已知y0为线性规划的对偶问题的最优解，若y0>0，说明在最优生产计划中对应的资源 。
4．已知y为线性规划的对偶问题的最优解，若y=0，说明在最优生产计划中对应的资源 。
5．已知线形规划问题的原问题有无穷多最优解，则其对偶问题的最优解一定是 。
6．m个产地n个销地的产销平衡运输问题的模型其决策变量的个数是 个；基变量的个数是 个；决策变量的系数列向量的特点是 。
7．用位势法求解运输问题，位势的含义是 ；行位势与列位势中有一个的取值是任意的，这是因为 。
8.用割平面法求解整数规划，割平面割去了 ；但未割去 。
9．按教材中的符号写出最大流问题的数学模型 。 10．什么是截集，何谓最小截集？ 二、（10分）
下表是用单纯形法计算到某一步的表格，已知该线性规划的目标函数值为z=14 表1
cj x3 x1 σj 2 a x1 c d b x2 0 e -1 x3 1 0 f x4 1/5 1 g 0
0
（1） 求a—g的值；（8分）
（2） 表中给出的解是否为最优解。（2分） 三、（每小题6分共12分）
车间为全厂生产一种零件，其生产准备费是100元，存贮费是0.05元／天·个，需求量为每天30个，而且要保证供应。
（1） 设车间生产所需零件的时间很短（即看成瞬时供应）； （2） 设车间生产零件的生产率是50个／天。
要求在（1）（2）条件下的最优生产批量Q*，生产间隔期t*和每天的总费用C*。 四、（18分）
某公司下属甲、乙两个厂，有A原料360斤，B原料640斤。甲厂用A、B两种原料生产x1,x2两种产品，乙厂也用A、B两种原料生产x3,x4两种产品。每种单位产品所消耗各种原料的数量及产值、分配等如下
工厂 产品 原料 A B 产值（百元） 甲 分配原料 x1 x2 8 4 6 10 4 3 160 330 x3 x4 5 8 10 4 3 4 200 310 乙 分配原料 1． 求各厂最优生产计划；（12分）
2． 问公司能否制定新的资源分配方案使产值更高？（6分） 五、（10分）
已知有六个村庄，相互间道路的距离如图所示，已知各村庄的小学生数为：A村50人，B村40人，C村40人，D村60人，E村50人，F村90人。现六村决定合建一所小学，问小学应建在哪村，才能使学生上学所走的总路程最短？
六、（8分）
A
2 B 6 8 D 4 1 6 F
7 1 C 3 3 E
A、B、C、D、E、F分别代表陆地和岛屿，1、2、3??14表示桥梁及其编号。若河两岸分别敌对的双方部队占领，问至少应切几座桥梁（具体指出编号）才能达到阻止对方部队过河的目的，试用图论方法进行分析。（提示：以陆地为点，桥梁为弧，两点之间的桥梁数为弧的容量。） 七、（12分）
设有三个化肥厂供应四个地区的农用化肥。各化肥的年产量，各地区的需求量，化肥的运价如下表所示，请写出产销平衡运输表。
A1 B1 16 B2 13 B3 22 B4 16 产量 50 A2 A3 最低要求 最高要求 12 19 30 45 14 21 70 70 18 23 0 30 15 ? 10 不限 60 50 运筹学试卷（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 CB 0 5 -Z （1） （1） 求a~g的值； （2） （2） 表中给出的解是否为最优解，并求出最优解。 四、四、已知某线性规划问题，其初始及最优单纯形表如下：（15分）
Cj CB 0 0 0 XB x3 x4 x5 σj 最优解表 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年计划，确定每年投入高、低两种负荷下生产的完好机器数量，使5年内产品的总产品量最大，并且5年末完好的机器数量是500台。 （1） （1） 写出阶段变量、状态变量、决策变量；（6分）
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 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 XB x3 x1 b -10 b -1 f g 5 3 0 0 x1 x2 x3 x4 c 0 1 1/5 d e 0 1