临沂师范学院《运筹学试题》.doc

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