临沂师范学院运筹学试题试题二

………………………………装………………………………订……………………………线…………………………………………………………装………………………………订……………………………线…………………………临沂师范学院数学本科阶段性测试《运筹学》试题（2）一、填空题（３×５=１５分）１．对于集合nRD和)(xf，若满足对任意的Dyx,和]1,0[有,)1(Dyx),()1()())1((yfxfyxf则称Ｄ为＿＿＿＿＿，ｆ（ｘ）为＿＿＿＿＿＿．２．设ｆ（ｘ）在ｘ＊的一个邻域内二阶连续可微，那么ｘ＊为无约束最优化问题的一个最优解的二阶必要条件是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿．３．标准形线性规划的可行点}0,|{xbAxxFx是Ｆ的顶点的充分必要条件是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿．４．单纯行法作为线性规划的一个求解算法，其算法复杂性＿＿＿＿＿＿＿＿＿＿．５．对于标准形线性规划问题，如果有有限的最优解，则＿＿＿＿＿＿＿＿＿＿＿＿＿＿取得。二．计算题（６0分）1．（１０）用图解法确定下面线性规划问题的最优解0,026213..2min212212121xxxxxxxtsxx２．（２０）单纯行法确定下面线性规划问题的最优解0,,93124..3min3213232132131xxxxxxxxxxxtsxx题号一二三四五六七八九十总分得分阅卷人专业：科类：科班级：级班姓名：学号：专业：科类：科班级：级班姓名：学号：３．（１０）出下面线性规划问题的对偶问题0,030351546324624..347min3132321321321xxxxxxxxxxtsxxx４．（２０）用对偶单纯行法确定下面线性规划问题的最优解0,0,010252..423min3213221321xxxxxxxtsxxx三、证明题（２５分）1．(1０)凸规划问题的一个局部最优解一定是它的全局最优解．２．（１０）对任何线性规划问题,其对偶的对偶还是原问题。３．（５）叙述强对偶定理．临沂师范学院数学系阶段性测试(2)运筹学试题标准答案一、填空题：（３×５=１５）1、凸集，凸函数，2、nTRssxfsxf,0)(,0)(*2*，3、ｘ是一个基本可行解，4、不是多项式时间算法５、必可在其可行域的某个顶点二、计算题（６０）１．３Ｅ２ＤＣ４．．．．．．．．．．．．．．．．．．．．．．．．．．．．．6分如图给出了这一问题的可行域F，它是由线段AB,BC,CD,DA围成的凸多边形(凸集)，A,B,C,D是这个凸集的４个顶点。随着同位线的向左移动，目标函数值逐渐减小，f=－３的同位线同可行域相交于可行域的顶点A.如果把f=-３的同位线向左作任何一点点的移动，尽管目标函数值会有所减小，但同可行域不再有任何交点。也就是说不存在任何使目标函数值小于-３的可行点，因此可行域的顶点A是上述线性规划问题的最优解，最优目标函数值为Ａ（１，２）ＢＣＤｘ1-2x2=z(-1,2)-３.由图我们还可以看出在顶点A为最优点，即有x1*=1,x2*=２.．．．．．．．．．．．．．．．１０分（叙述不标准者酌情扣分）２．（２０）解：首先，引入三个松驰变量和人工变量4x，5x，6x，7x将其转化为标准形的线性规划问题7,...,2,1,093124..32min7326532143217621ixxxxxxxxxxxxxtsMxMxxxi．．．．．．．．．．．．．．．．．．．．．．．．．４分取4x，6x，7x为初始基变量得下面单纯形表基变量1x2x3x4x5x6x7x右端项－ｆ２M+3－4M－1０Ｍ００4x6x7x１１１１０００－２１－１０－１１００３１０００１４１９．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．８分取6x为出基变量，2x为入基变量，以１为旋转主元，得下表基变量1x2x3x4x5x6x7x右端项－ｆ－６M+3０－４Ｍ－１０－３Ｍ４Ｍ０4x2x7x３０２１１－１０－２１－１０－１１０６０４０３－３１３１６．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１２分取7x为出基变量，1x为入基变量，以６为旋转主元，得下表基变量1x2x3x4x5x6x7x右端项－ｆ００－３０－23Ｍ＋23Ｍ－214x2x1x０００１－2121－21０１31０００31１０32０21－2161０３１．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１６分取1x为出基变量，3x为入基变量，以６为旋转主元，得下表基变量1x2x3x4x5x6x7x右端项－ｆ23０００43Ｍ－43Ｍ＋414x2x3x０００１－2121－21－21１００－41414123０１０43－4341０2523至此，所有44,0Njcj，当前的迭代点已是问题的一个最优解，得最优解为1x＝０，2x＝25，3x＝23，4x＝０，5x＝０．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．２０分（叙述不标准者酌情扣分）３．（１０）解：0,033464562734..301524max2132132121321yyyyyyyyyytsyyy．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１０分４．（２０）解．首先，将本题中的约束转化成型，再引入松驰变量得5,...,1,010252..423min532421321ixxxxxxxtsxxxi．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．４分取4x，5x为初始基变量得下面单纯形表基变量1x2x3x4x5x右端项－ｆ３２４０００4x5x－２１０１００－２１０１－５－１０．．．．．．．．．．．．．．．．．．．．．．．．．．８分取5x为出基变量，2x为出基变量，以－２为旋转主元，得下表基变量1x2x3x4x5x右端项－ｆ３０５０１－１０4x2x－２０21１21０１－21０－21－１０５．．．．．．．．．．．．．．．．．．．．．．．．１２分取4x为出基变量，1x为出基变量，以－２为旋转主元，得下表基变量1x2x3x4x5x右端项－ｆ００５4323１43－251x2x１０－41－21－41０１－21０－21５５．．．．．．．．．．．．．．．．．．．．．．１６分至此，右端项的所有分量都已非负，当前的迭代点已是问题的一个最优解，得最优解为1x＝５，2x＝５，3x＝０，相应的最优目标函数值为２５．．．．．．．．．．．．．．．．．．．２０分（叙述不标准者酌情扣分）三、证明题(25)１．（１０）证明：设*x是凸规划问题的一个局部最优解，但不是它的全局最优解，则存在另一个可行点，设为y满足)()(*xfyf．．．．．．．．．．．．．．．．．．．．．．．．．．．２分有可行集的凸性，对于任意的)1,0(，点yx)1(*都是可行点．．．．．．．．．５分又根据目标函数的凸性有),()()1()()()1()())1((*****xfxfxfyfxfyxf．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．８分这表明在*x的任意小的邻域内都存在函数值小于)(*xf的可行点，这与*x是凸规划问题的一个局部最优解相矛盾，因此，函数值小于)(*xf的可行点不存在，*x一定是凸规划问题的一个全局最优解．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１０分２．（１０）证明：因为任何形式的线性问题都可以转化为经典形式，在此我们只考虑经典形线性规划问题：0..)(minxbAxtsxcxfT易知，其对偶问题为：0..)(maxycyAtsybyzTT．．．．．．．．．．．．．．．．．．．．．．．５分将对偶形式转化为经典形式：0..)(minycyAtsybygTT它的对偶为0..maxxbAxtsxcT经整理即得原线性规划问题．．．．．．．．．．．．．．．．．．．．．．．１０分３（５）强对偶定理：如果互为对偶的两个线性规划问题中一个有最优解，则另一个也有最优解,且两者的最优目标函数值相等。．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．５分