Learning Initial Basis Selection for Linear Programming via Duality-Inspired Tripartite Graph Representation and Comprehensive Supervision

Contents in the later chapters of the book, there is a canonical rate associated with a given programming problem that seems to govern the speed of convergence of many algorithms when applied to that problem. It is this fact that underlies the potency of the theory, allowing definitive comparisons among algorithms to be made even without detailed knowledge of the problems to which they will be applied. Together these two properties, simplicity and potency, assure convergence analysis a permanent position of major importance in mathematical programming theory. Define the n-vector y = (y 1 , y 2 , . . . , y k , 0, 0, . . . , 0). Since x i > 0, 1 i k, it is possible to select ε such that x + εy 0, x -εy 0. We then have x = 1 2 (x+εy)+ 1 2 (x-εy) which expresses x as a convex combination of two distinct vectors in K. This cannot occur, since x is an extreme point of K. Thus a 1 , a 2 , . . . , a k are linearly independent and x is a basic feasible solution. (Although if k < m, it is a degenerate basic feasible solution.) L This correspondence between extreme points and basic feasible solutions enables us to prove certain geometric properties of the convex polytope K defining the constraint set of a linear programming problem. Corollary 1. If the convex set K corresponding to ( 18 ) is nonempty, it has at least one extreme point. Proof. This follows from the first part of the Fundamental Theorem and the Equivalence Theorem above. L Corollary 2. If there is a finite optimal solution to a linear programming problem, there is a finite optimal solution which is an extreme point of the constraint set. Corollary 3. The constraint set K corresponding to (18) possesses at most a finite number of extreme points. minimize f (x) subject to Ax = b, x 0. Show how to convert this problem to a linear programming problem. 10. A small computer manufacturing company forecasts the demand over the next n months to be d i , i = 1, 2, . . . , n. In any month it can produce r units, using regular production, at a cost of b dollars per unit. By using overtime, it can produce additional units at c dollars per unit, where c > b. The firm can store units from month to month at a cost of s dollars per unit per month. Formulate the problem of determining the production schedule that minimizes cost. (Hint: See Exercise 9.) 11. Discuss the situation of a linear program that has one or more columns of the A matrix equal to zero. Consider both the case where the corresponding variables are required to be nonnegative and the case where some are free. 12. Suppose that the matrix A = (a 1 , a 2 , . . . , a n ) has rank m, and that for some p < m, a 1 , a 2 , . . . , a p are linearly independent. Show that mp vectors from the remaining n-p vectors can be adjoined to form a set of m linearly independent vectors. 13. Suppose that x is a feasible solution to the linear program ( 12 ), with A an m × n matrix of rank m. Show that there is a feasible solution y having the same value (that is, c T y = c T x) and having at most m + 1 positive components. 14. What are the basic solutions of Example 3, Section 2.5? 15. Let S be a convex set in E n and S * a convex set in E m . Suppose T is an m × n matrix that establishes a one-to-one correspondence between S and S * , i.e., for every s ∈ S there is s * ∈ S * such that Ts = s * , and for every s * ∈ S * there is a single s ∈ S such that Ts = s * . Show that there is a one-to-one correspondence between extreme points of S and S * . 16. Consider the two linear programming problems in Example 1, Section 2.1, one in E n and the other in E n+m . Show that there is a one-to-one correspondence between extreme points of these two problems. * The exact solution is obviously symmetric about the center of the chain, and hence the problem could be reduced to having 10 links and only one constraint. However, this symmetry disappears