《运筹学试题》word版.doc

《《运筹学试题》word版.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、专业：科类：科　班级：　　级　　班　　姓名：　　　　学号：　　　　　　　　………………………………装………………………………订……………………………线…………………………………………………………装………………………………订……………………………线…………………………专业：科类：科　班级：　　级　　班　　姓名：　　　　学号：　　　　　　　　临沂师范学院数学本科阶段性测试《运筹学》试题（3）题号一二三四五六七八九十总分得分阅卷人一、填空题（３×5=１5分）1．设ｆ（ｘ）在ｘ＊的一个邻域内二阶连续可微，那么ｘ

2、＊为无约束最优化问题的一个最优解的二阶充分条件是＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。３．椭球算法和内点算法的作为线性规划的一个求解算法，其算法复杂性是＿＿＿＿＿＿＿＿＿＿。４．对于标准形线性规划问题，如果有有限的最优解，则必可在其＿＿＿＿＿＿＿＿＿＿＿＿＿＿取得。５．如果互为对偶的两个线性规划问题中一个有最优解，则另一个也有——————————————。６．如果两个互为对偶的线性规划问题各有一个可行解,且相应的目标函数值相同，则这两个可行解＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿＿。二．计算题

3、（６0分）1．（１０）用图解法确定下面线性规划问题的最优解２．（２０）单纯行法确定下面线性规划问题的最优解２．（１０）出下面线性规划问题的对偶问题４．（２０）用对偶单纯行法确定下面线性规划问题的最优解三、证明题(25分)１．(10)设D∈Rn是非空凸集，是定义在D上的凸函数，是一个实数，则集合L={x∈D

4、}是一个凸集。２．(10)对任何线性规划问题,其对偶的对偶还是原问题。３．（５）写出下面线性规划的ＫＫＴ条件．　　　　　　　　　　　　　临沂师范学院数学系阶段性测试(3)<<运筹学>>试题标准答案一、

5、填空题：（３×５=１５）1、，2、，多项式时间算法，3、可行域的某个顶点，４、最优解,且两者的最优目标函数值相等，５、各是相应问题的最优解二、计算题（６０）　　　　　　　　　　　　　　１．　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　Ａ（４／３，１４／３）　　　　　　　　　　　　　４Dv=(1,3)　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　

6、　　　　Ｂ　　　　　　　　　　　　　　Ｃ　　　　　　　　　　６．．．．．．．．．．．．．．．．．．．．．．．．．．．．．７分如图给出了这一问题的可行域F，它是由线段AB,BC,CD,DA围成的凸多边形(凸集)，A,B,C,D是这个凸集的4个顶点。随着同位线的向右移动，目标函数值逐渐减小，f=－４６／３的同位线同可行域相交于可行域的顶点A.如果把f=－４６／３的同位线向右作任何一点点的移动，尽管目标函数值会有所减小，但同可行域不再有任何交点。也就是说不存在任何使目标函数值小于－４６／３的可行点，因此可行域

7、的顶点A是上述线性规划问题的最优解，最优目标函数值为－４６／３.由图我们还可以看出在顶点A为最优点，即有x1*=４／３,x2*=１4／３．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１０分（叙述不标准者酌情扣分）２．（２０）解：首先，引入三个松驰变量，，将其转化为标准形的线性规划问题．．．．．．．．．．．．．．．．．．．．．．．．．４分取，，为初始基变量得下面单纯形表基变量　　　　　　　　　　　　　　右端项－ｆ－２　　　－３　　　　０　　　　０　　　　

8、０　０－１　　　１　　　　　１　　　　０　　　　０－２　　　１　　　　　０　　　　１　　　　０　４　　　　１　　　　　０　　　　０　　　　１　　　３２１６　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．８分取为出基变量，为出基变量，以－２为旋转主元，得下表基变量　　　　　　　　　　　　　　右端项－ｆ－８　　　０　　　　０　　　　　３　　　０　６１　　　０　　　　　１　　　－１　　　　０－２　　　１　　　　　０　　　　１　　　　０　　　　１２６　　　０　　　　　

9、０　　　－１　　　　１１４　　　　　　　　　　　　　　　　．．．．．．．．．．．．．．．．．．．．．．．．．．．．．．１２分取为出基变量，为出基变量，以1为旋转主元，得下表基变量　　　　　　　　　　　　　　右端项－ｆ0　　　０　　　　　8　　　－５　　　　０　１４１　　　０　　　　　１　　　－１　　　　００　　　１　　　　　２　　　－１　　　　０　０　　　０　　　　－６　　　　５　　　　１　　　１４８　　　　　　　　　　　　　　　　　．．．