运筹学期末试卷及答案.doc

1、一、判断题（21分）1、可行解是基本可行解的充要条件是它的正分量所对应的A中列向量线性无关（ ）；2、如果一个LP问题有最优解，则它的对偶问题也有最优解，且它们的最优解相等（ ）； 3、若线性规划问题有最优解，则一定有唯一的最优解（ ）；4、若一个原始线性规划问题无界，则它的对偶问题也无界（ ）；5、设在点处的Hesse矩阵存在，若，并且正定，则是（UMP）的严格局部最优解（ ）；6、若是S上的凸函数，任意实数则是S上的凸函数（ ）；7、设是非空开凸集，二阶连续可导，则是S上的严格凸函数的充要条件是的Hesse矩阵在 S上是正定的（ ）.二、1.将下面的线性规划问题化成标准形（7分） 2，写出

2、下面线性规划的对偶规划（7分） 三、证明题（10分）设在点处可微.若是（UMP）的局部最优解，则. 四、用对偶单纯形法求解下列线性规划问题（10分） 五、把线性规划问题（18分） 记为 （P）求（1） 用单纯形算法解（p）； （2） 由1变为； （3） b由六、用分枝定界法解下述ILP问题（10分）七、求以下无约束非线性规划问题的最优解（8分） 八、验证下列非线性规划为凸规划（9分） 一、判断题（20分）1. V ; 2. X; 3. X; 4. X; 5. X ； 6. V ； 7. X 。二、1.解：对自由变量代替;对第一个不等式约束添加松弛变量,对第二个不等式约束添加剩余变量,再用代替原

3、来的目标函数,便得到了标准形式的LP问题 （2分） （4分） s.t （8分）2解：这里根据定义，其对偶问题是 （2分） （4分） s.t （7分）三、证明题（10分）证：用反证法，若 ，现令，则有 （2分） （5分）由定理，必存在，使当时，有 成立 （8分）但这与假设矛盾.因此必有 （10分）四、 解：引进非负的剩余变量将不等式约束化为等式约束 将等式两端同乘以（-1），就直接得到原问题一个基本（不可行）解和对偶问题的一个可行解（检验数向量）其对应的单纯形标如下 （6分） （8分）此时，故原问题的最优解为，其最优值为。 （10分）五、解：（1）在约束条件中加入松弛变量得 s.t 它的初始表

4、（2分） （5分） 此时检验数向量故最优解为其最优值为。 （6分） (2) （8分） （10分）此时检验数向量故最优解为其最优值为。 （12分）(3) 原问题的最优解为所对应的可行基B=, , 故 （16分） 从而新问题对应的单纯形表为 由于，故最优解为其最优值为。 （18分）六、解：用图解法解求ILP问题的松弛问题的最优解为,最优值为。 （2分）它的最优解不符合整数的要求,可任选一个变量,如选择进行分枝.由于 （4分）引进两个约束生成两个子问题 s.t 和 s.t （6分）ILP问题的松弛LP问题的最优解,最优值。的松弛LP问题的最优解,最优值。 （8分）由于,故ILP问题的最优解,最优值。 （10分）七、解：目标函数的梯度向量为 ， （2分）令，求得的驻点。 （4分）的Hesse矩阵为，的一、二阶顺序主子式分别为 ， （6分） 对为正定矩阵，因而是上的凸函数。故为它的整体最优解。 （8分）八、解： 的Hesse矩阵为， （2分） 的一、二阶顺序主子式本别为 ， ， 因而为正定矩阵，是严格凸函数. （4分）而= ，它也是一个正定矩阵，因而也是严格凸函数， （7分） 其它的不等是约束为线性的。由定理知，该非线性规划是一个凸规划。 （9分）