《运筹学试题》word版.doc

专业： 科类： 科班级： 级班姓名： 学号：装订线装订线专业： 科类： 科班级： 级班姓名： 学号：临沂师范学院数学本科阶段性测试运筹学试题（3）题号一二三四五六七八九十总分得分阅卷人一、 填空题（5=5分）1设（）在的一个邻域内二阶连续可微，那么为无约束最优化问题的一个最优解的二阶充分条件是。 椭球算法和内点算法的作为线性规划的一个求解算法，其算法复杂性是。 对于标准形线性规划问题，如果有有限的最优解，则必可在其取得。如果互为对偶的两个线性规划问题中一个有最优解，则另一个也有。如果两个互为对偶的线性规划问题各有一个可行解,且相应的目标函数值相同，则这两个可行解。二计算题（0分）1（）用图解法确定下面线性规划问题的最优解 （）单纯行法确定下面线性规划问题的最优解 （）出下面线性规划问题的对偶问题（）用对偶单纯行法确定下面线性规划问题的最优解三、证明题(25分)(10)设DRn 是非空凸集，是定义在D上的凸函数，是一个实数，则集合L=x D| 是一个凸集。(10)对任何线性规划问题,其对偶的对偶还是原问题。（）写出下面线性规划的条件临沂师范学院数学系阶段性测试(3)试题标准答案一、 填空题：（=）1、，2、，多项式时间算法，3、可行域的某个顶点，、最优解,且两者的最优目标函数值相等，、各是相应问题的最优解二、 计算题（）（，）D v=(1,3) 分如图给出了这一问题的可行域 F，它是由线段AB,BC,CD,DA围成的凸多边形(凸集)，A,B, C,D是这个凸集的4个顶点。随着同位线的向右移动，目标函数值逐渐减小，f=的同位线同可行域相交于可行域的顶点A.如果把f=的同位线向右作任何一点点的移动，尽管目标函数值会有所减小，但同可行域不再有任何交点。也就是说不存在任何使目标函数值小于的可行点，因此可行域的顶点A是上述线性规划问题的最优解，最优目标函数值为.由图我们还可以看出在顶点A为最优点，即有x1*=,x2*=4分 （叙述不标准者酌情扣分）（）解：首先，引入三个松驰变量，将其转化为标准形的线性规划问题 分取，为初始基变量得下面单纯形表基变量右端项分取为出基变量，为出基变量，以为旋转主元，得下表基变量右端项 分取为出基变量，为出基变量，以1为旋转主元，得下表基变量右端项0 8分取为出基变量，为出基变量，以为旋转主元，得下表基变量右端项0 至此，所有 ，当前的迭代点已是问题的一个最优解，得最优解为 ， ， ， ， ，相应的最优目标函数值为分（叙述不标准者酌情扣分）（）解：分（）解首先，将本题中的约束转化成型，再引入松驰变量得分取，为初始基变量得下面单纯形表基变量右端项分取为出基变量，为入基变量，以为旋转主元，得下表基变量右端项分取为出基变量，为入基变量，以为旋转主元，得下表基变量右端项分至此，右端项的所有分量都已非负，当前的迭代点已是问题的一个最优解，得最优解为，相应的最优目标函数值为分（叙述不标准者酌情扣分）三、 证明题(25)（）证明：设 L, 于是D, , .今设,分由于是凸函数，故分因此， 从而 L是凸集。分（）证明：因为任何形式的线性问题都可以转化为经典形式，在此我们只考虑经典形线性规划问题：易知，其对