标题: 求助，单纯形法习题 [打印本页] 作者: lianfs 时间: 2014-11-5 20:50 标题: 求助，单纯形法习题 Answer the following questions along with a concise explanation with respect to the linear program to maximize cx subject to x∈X={x:Ax=b,x≥0}, where A is m×n of rank m<n. ' m- J% z) ]+ t$ c8 R [ In a simplex tableau, if z_j-c_j=-7 for a nonbasic variable x_j, what is the change in objective value when x_j enters the basis given that the minimum ratio is 3 in the pivot? 9 {' X* Q& A0 j) D% { If an extreme point is optimal, then is it possible that not all z_j-c_j≥0 for an associated basis? : s. x: B' e$ |# z8 _+ y+ z) j0 z If there exists a d such that Ad=0,d≥0, and cd≥0, then is the optimal objective value unbounded? " B% t$ W! V$ ~ Let x ̅ be a feasible solution with exactly m positive components. Is x ̅ necessarily an extreme point of X? ( a. t7 A7 i( B( d' N: [2 ] If a nonbasic variable x_k has z_k-c_k=0 at optimality, then can one claim that alternative optimal solutions exist?5 d, e$ A; }) P0 q& ?# C- P
If x_1 and x_(2 )are adjacent points and if B_1 and B_2 are respective associated bases, then these bases are also adjacent. True or false? Explain. ' b+ n: F6 Q7 j9 D+ [) ]1 v l. F Is it possible for an optimal solution to have more than m positive variables? . v( J9 p& h" D, B# T2 }! z; H Suppose that n=m+1. What is the least upper bound on the number of extreme points and feasible bases? 2 E7 w8 i6 \/ V K4 }8 v' \ A p-dimensional polyhedron can have at most p extreme directions. True or false? Explain.9 e/ w: F# i) u8 ~
Let x ̅ be an extreme point having (m-1) positive components. Then there are (p+1) bases associated with this extreme point, where p=n-m. True or false? (Assume that Ax=b does not imply any variable to be a constant) Explain. e' ]8 L( @0 l2 V, n6 q& g# \. B/ O( k 作者: z919953051 时间: 2014-11-8 13:52
你这个可以用于ACM竞赛了。。。 5 _% a5 b0 d9 E作者: wangxiaohan 时间: 2015-1-18 06:15
好高深呀帮顶下, A/ z4 A9 E6 W R2 @5 N3 F {4 C 作者: 士心之约 时间: 2015-10-2 09:00 ; G2 I$ N8 ~0 H' [! h7 G& B, w/ l
帮顶下, A/ z4 A9 E6 W R2 @5 N3 F {4 C