运筹学期末试卷及答案

《运筹学期末试卷及答案》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

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

2、问题化成标准形（7分）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）在约束条件中

4、加入松弛变量得s.t它的初始表（2分）（5分）此时检验数向量故最优解为其最优值为。（6分）(2)（8分）（10分）此时检验数向量故最优解为其最优值为。（12分）(3)原问题的最优解为所对应的可行基B==,,故（16分）从而新问题对应的单纯形表为由于，故最优解为其最优值为。（18分）六、解：用图解法解求ILP问题的松弛问题的最优解为,最优值为。（2分）它的最优解不符合整数的要求,可任选一个变量,如选择进行分枝.由于（4分）引进两个约束生成两个子问题s.t和s.t（6分）ILP问题的松弛LP问题的最优解,最优值。的松弛LP问题的最优解,最优值。（8

5、分）由于,故ILP问题的最优解,最优值。（10分）七、解：目标函数的梯度向量为，（2分）令，求得的驻点。（4分）的Hesse矩阵为，的一、二阶顺序主子式分别为，（6分）对为正定矩阵，因而是上的凸函数。故为它的整体最优解。（8分）八、解：的Hesse矩阵为，（2分）的一、二阶顺序主子式本别为，，因而为正定矩阵，是严格凸函数.（4分）而=，它也是一个正定矩阵，因而也是严格凸函数，（7分）其它的不等是约束为线性的。由定理知，该非线性规划是一个凸规划。（9分）