临沂师范学院：运筹学考试考试二

1、:号号子 ：名姚姓 班班一级 :级議班科科：类毬科 ：业.盍专题号-一一-二二-三四五六七八九十总分得分阅卷人临沂师范学院数学本科阶段性测试运筹学试题(2)一、填空题(3X5 = 15分)1.对于集合DRn和f (x),若满足对任意的x, y D和 0,1有X(1-')yD,f(hx + (1 -扎)y) Ehf(x) +(1 h)f (y),则称D为,f (x)为.2 设f(x)在x*的一个邻域内二阶连续可微，那么x*为无约束最优化问题的一个最优解的二阶必要条件是.3.标准形线性规划的可行点 xF=x|Ax=b,xZO是F的顶点的充分必要条件是_4单纯行法作为线性规划的一个求解算法，

2、其算法复杂性.5.对于标准形线性规划问题，如果有有限的最优解， 则取得。二. 计算题(6 0分)1. (1 0)用图解法确定下面线性规划问题的最优解min 捲一2x2s.t.3x1 -x2 _12x1 x2 巴 6x2乞2捲 _ 0,X2 _ 02. (20)单纯行法确定下面线性规划问题的最优解min3x1 - x3s.t.X1 X2 X3 - 4- 2x1 x2 x3 亠 13x2 x3 = 9X1, X2, X3 - 03. ( 10)出下面线性规划问题的对偶问题min7x1 4x? - 3x3st. -4x1 2x2 - 6x3 _ 24-3xr - 6x2 -4x3 _ 155x2 3

3、x3 = 30x1 _ 0, x3 _ 04. (2 0)用对偶单纯行法确定下面线性规划问题的最优解min3x1 2x2 4x3s.t.2x1 -x2 _52x2 - X3 10X1 _ 0, X2 _ 0, X3 _ 0三、证明题(25分)1. (1 0)凸规划问题的一个局部最优解一定是它的全局最优解.2. (10)对任何线性规划问题 ，其对偶的对偶还是原问题。3. (5)叙述强对偶定理.临沂师范学院数学系阶段性测试<<运筹学 >> 试题标准答案一、填空题：(3X5 = 15)1凸集，凸函数，*T 2*n2、' f(x )=0,s '、 f(x )s

4、0,s R ,3、x是一个基本可行解，4、不是多项式时间算法5、必可在其可行域的某个顶点二、计算题1.如图给出了这一问题的可行域F,它是由线段 AB,BC,CD,DA围成的凸多边形(凸集),A,B, C,D是这个凸集的4个顶点。随着同位线的向左移动，目标函数值逐渐减小，f= 3的同位线同可行域相交于可行域的顶点A.如果把f=- 3的同位线向左作任何一点点的移动，尽管目标函数值会有所减小，但同可行域不再有任何交点。也就是说不存在任何使目标函数值 小于-3的可行点，因此可行域的顶点A是上述线性规划问题的最优解，最优目标函数值为-3 .由图我们还可以看出在顶点 A为最优点，即有 xi*=1,X2*=

5、 2 10分(叙述不标准者酌情扣分)2.(20 )解：首先，引入三个松驰变量和人工变量X4 , X5 , X6 , X7将其转化为标准形的线性规划问题min-2捲-3x2 Mx6 Mx7s.t.x1x2 x3x4 = 4_2xi 'X2- X3 -X5' x 13x2 X3 X7 = 9Xj 亠 0, i = 1,2,.,74分取X4 , X6 , X7为初始基变量得下面单纯形表基变量XiX2X3X4X5X6X7右端项_f2 M+34M10M00X411110004x6-21101101X7031000198分取X6为出基变量，X2为入基变量，以1为旋转主元，得下表基变量XiX

6、2X3X4X5X6X7右端项f6 M+30 4M103M4M0X430211103X221101101X76040331612分取X7为出基变量，Xi为入基变量，以6为旋转主元，得下表基变量XiX2X3X4X5XX7右端项_f33100-30M+ -M-222111X400012220X2011000133321111001X322616分取Xi为出基变量，X3为入基变量，以6为旋转主元，得下表基变量X1X2X3X4X5XX7右端项-f3331000M -M+ 24441111X4000222011001115X2244423010331324442X3至此，所有c4 _0, j N4，当前的

7、迭代点已是问题的一个最优解，得最优解为Xi =c530, X2 =X3 =,X4 = 0,X5 =02220分（叙述不标准者酌情扣分）3. (10)解:max24y! 15 y2 30 y3s.t.-4y1 -3y2 _ 72yi -6y2 5y 4-6yi - 4y2 3y3 _ -3yi 乞 0, y2 010分4. (20 )解首先，将本题中的约束转化成V型，再引入松驰变量得min3x1 2x2 4x3s.t.-2x1x2x4 = 5-2X2 X3 ' X5 -10X - 0,i = 1,.,54分基变量XiX2X3X4X5右端项_f324000X4-21010-5X50-210

8、1-10取X5为出基变量，X2为出基变量，以一2为旋转主兀基变量右端项XiX2X3X4X5-f30501-10X4ii-10-20122X2ii501022取X4 , X5为初始基变量得下面单纯形表,得下表12分取X4为出基变量，Xi为出基变量，以一2为旋转主元，得下表基变量X1X2X3X4X5右端项f331 325005 1 -424X1111510 424X21150102216分至此，右端项的所有分量都已非负，当前的迭代点已是问题的一个最优解，得最优解为X1 = 5, X2 = 5, X3 =0,相应的最优目标函数值为25. 20分(叙述不标准者酌情扣分)三、证明题(25)1.(10)证

9、明：设x*是凸规划问题的一个局部最优解，但不是它的全局最优解,则存在另一个可行点，设为y满足f(y)空f(x*) 2分有可行集的凸性，对于任意的 (0,1)，点X* (1 - )y都是可行点 5分又根据目标函数的凸性有f ( x*(1 - '；) y)乞 f (x* )(1 -) f (y)f (x*)(1 -，)f (x*)二 f (x*),8分这表明在X的任意小的邻域内都存在函数值小于 f (X )的可行点，这与X是凸规划问 题的一个局部最优解相矛盾，因此，函数值小于f(x*)的可行点不存在，X* 一定是凸规划问题的一个全局最优解10分2. (10)证明：因为任何形式的线性问题都可以转化为经典形式，在此我们只考虑经典形线性规划问题：min f (x)二 cT xst. Ax _ bx 一0易知，其对偶问题为：max z(y) =bTys.t.ATyc 、分y _0将对偶形式转