标题: 求助，单纯形法习题 [打印本页] 作者: 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. % ~' o- @# t* y( P) ]3 Z6 C# |; ? 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?, y* j1 C$ I, N0 K+ W
If an extreme point is optimal, then is it possible that not all z_j-c_j≥0 for an associated basis? ) `' |+ G$ D0 s! S4 K, ]* v& L If there exists a d such that Ad=0,d≥0, and cd≥0, then is the optimal objective value unbounded?) D8 S0 ~/ e. l9 s* ?
Let x ̅ be a feasible solution with exactly m positive components. Is x ̅ necessarily an extreme point of X? ; b, Y& J: m9 u$ a) u! B8 c If a nonbasic variable x_k has z_k-c_k=0 at optimality, then can one claim that alternative optimal solutions exist? + A3 r# T2 g! C! L 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.3 T4 ~* Q: I- a8 ^6 D+ i2 Y
Is it possible for an optimal solution to have more than m positive variables?7 _% l. I! g* \% f
Suppose that n=m+1. What is the least upper bound on the number of extreme points and feasible bases?4 V3 P/ _+ f+ x9 ?, [+ M6 m" X
A p-dimensional polyhedron can have at most p extreme directions. True or false? Explain. ' C9 Q$ f- ~5 s) L 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. * u; d0 ]0 L8 G0 f0 U0 \' l2 J3 b& n. [5 a' r 作者: z919953051 时间: 2014-11-8 13:52
你这个可以用于ACM竞赛了。。。' J: F/ s9 N1 s# r' z5 w 作者: wangxiaohan 时间: 2015-1-18 06:15
好高深呀帮顶下 . K8 m$ {- D O, q( V4 y0 ]( ?' V, F作者: 士心之约 时间: 2015-10-2 09:00 ; j) C" s! _0 x
帮顶下