当前位置：问答库＞考研试题

一、简答题

1． 简述割平面法的基本思想。

【答案】这个方法的基础仍然是用解线性规划的方法去解整数规划问题，首先不考虑变量xi 是整数这一条件， 但增加线性约束条件（用几何术语，称为割平面）使得由原可行域中切割掉一部分，这部分只包含非整数解，但没有切割掉任何整数可行解。这个方法就是指出怎样找到适当的割平面（不见得一次就找到），使切割后最终得 到这样的可行域，它的一个有整数坐标的极点恰好是问题的最优解。

2． 简述求解整数规划分枝定界法的基本思想。

【答案】设有最大化的整数规划问题A ，与它对应的线性规划为问题B ，从解问题B 开始，若其最优解不符合A 的整数条件，那么B 的最优目标函数必是A 的最优目标函数z*的上界，记作; 而A 的任意可行解的目标函数值将是z*的一个下界子区域（称为分支）的方法，逐步减小和增大

; 。分支定界法就是将B 的可行域分成

:， 最终求到z*。

二、证明题

3． 假设线性规划问题为:

其中

，秩

运用单纯形算法求得的最优基可行解时，所有的非基变量检验数全都<0，试证明这时所得到的最优解必定 是线性规划问题（l ）的准最优解。

【答案】一般情况下，经过迭代后解变为

再将上式代入目标函数式，整理后得到

令于是

第 2 页，共 47 页

再令则

时，此时的解就为最优解。

这样当所有非基变量的检验数即4． 证明:r （x ）二x12+x22是严格凸函数。

【答案】首先求导为（2x l ，2x 2:）

求海塞矩阵

为正定矩阵，所以f （x ）为严格凸函数

5． 对于M/M/1/∞/∞模型，在先到先服务情况下，试证明:

顾客排队等待时间分布的概率密度是

，并根据该式求等待时间的期望值

。

，【答案】令N ’为在统计平衡下一个顾客到达时刻看到系统中已有的顾客数（不包括此顾客）

为在统计平衡 下顾客的等待时间，则

由a n 的定义，得

，于是有

由定理知，对任何一个输入为最简单流的单服务台或多服务台的等待制排队系统，

恒有

，所以，

到达者遇到系统中顾客数不少于1个顾客，是需要等待的充要条件，因此

①

因为当系统中有n （n ≥l ）个顾客时，其中只有一个顾客正在接受服务，而其余n-1个顾客在排队等待，所以，新到顾客必须在服务台轮空n 次后，才能接受服务。于是，服务台轮空次数m （t ）t的充要条件，因此

②

其次，因为服务时间服从负指数分布，故其输出流，即服务台轮空次数m （t ）是一最简单流，其参数为

因此

③

第 3 页，共 47 页

将③式代入②式，然后再将②式代入①式，得

，其中，

，有

所以，顾客在系统中的等待时间分布为

因为，

以正概率

取0值，而当t>0时，它又具有连续型随机变量的性质，其分布函

既不是连续型随机变量，又不是离散型随机变量。然而类似的密度函数为

数必在（0，+∞） 上连续。所以于连续型随机变量，可以定义

。

6． 设线性规划问题解。

【答案】其对偶问题为设

1

有最优解，B 为最优基，证明单纯形乘子CB 是对偶问题的最优

，

即可得

，由此得

，即是

是原问题的最优解，则其对应的基矩阵B

必存在，这时Y 是对偶问题的可行解，它使

由于原问题的最优解，使目标函数取值

对偶问题的最优解，因此单纯形乘子，是对偶问题的最优解。

三、计算题

7． 某厂对原料需求的概率如表所示。

表

第 4 页，共 47 页