标题: 求助，单纯形法习题 [打印本页] 作者: 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. {& \$ L! H% B2 S2 p; O 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?) M1 S/ X ^1 _2 C7 }* W0 `9 K
If an extreme point is optimal, then is it possible that not all z_j-c_j≥0 for an associated basis? c1 ^* z \6 v% d If there exists a d such that Ad=0,d≥0, and cd≥0, then is the optimal objective value unbounded? ! q, o8 H Q- d5 V# s6 I1 s Let x ̅ be a feasible solution with exactly m positive components. Is x ̅ necessarily an extreme point of X? ; v, v) x( q! K If a nonbasic variable x_k has z_k-c_k=0 at optimality, then can one claim that alternative optimal solutions exist?4 l2 ]4 x0 m5 O! I7 h. F7 \' m5 `
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.2 T& @2 @6 l0 i7 R. `) ?3 w
Is it possible for an optimal solution to have more than m positive variables?) x3 ]9 q/ {$ f0 e2 q' ?
Suppose that n=m+1. What is the least upper bound on the number of extreme points and feasible bases?# P7 \9 Z1 g9 P- T- }$ e) M
A p-dimensional polyhedron can have at most p extreme directions. True or false? Explain. t! x* g! e5 K
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. / D+ z! I7 n4 M* o6 t8 N8 ^! ~, o& h+ L+ ]/ b 作者: z919953051 时间: 2014-11-8 13:52
你这个可以用于ACM竞赛了。。。 , l/ o3 k- z5 V* S8 H作者: wangxiaohan 时间: 2015-1-18 06:15
好高深呀帮顶下 ; a; |8 @' v/ ~7 G- m4 I8 g作者: 士心之约 时间: 2015-10-2 09:00 ; N9 Z1 t7 p( i& x3 Z! o
帮顶下