Linear Programming and Its Related Methods

INTRODUCTION

Linear Programming in a general form is the problem of maximizing a linear function in d variables subject to n linear inequalities. If, in addition, we require all variables to be nonnegative, we have an LP in standard form which can be written as follows. where the cj, bi and aij are real numbers. By defining this can be written in more compact form as where the relations <= and >= hold for vectors of the same length if and only if they hold component wise. The vector c is called the cost vector of the LP, and the linear function z : x -> cT x is called the objective function. The vector b is referred to as the right-hand side of the LP. The inequalities for i = 1; : : : : ; n and xj >= 0, for j = 1; : : : ; d are the constraints of the linear program. The LP is called feasible if there exists a non-negative vector x‘ satisfying Ax‘ <= b such an x‘ is called a feasible solution; otherwise the program is called infeasible. If there are feasible solutions with arbitrarily large objective function value, the LP is called unbounded; otherwise it is bounded. A linear program which is both feasible and bounded has a unique maximum value cT x‘ attained at a (not necessarily unique) optimal feasible solution x‘. Solving the LP means finding such an optimal solution x‘ (if it exists). To avoid trivialities we assume that the cost vector and all rows of A are nonzero.

The simplex algorithm starts of by introducing slack variables xd+1,……, xd+n to transform the inequality system Ax <= b into an equivalent system of equalities and additional nonnegativity constraints on the slack variables. The slack variable xd+i closes the gap between the left-hand side and right-hand side of the i-th constraint, and the linear program can be written as or in a more compact form as where A is the n X (d + n) - matrix c is the (d + n) - vector and x is the (d + n)-vector where xO is the vector of original variables, xS the vector of slack variables. Together with the objective function, the n equations for the xd+i in (1.3) contain all the information about the LP. Following tradition, we will represent this information in tableau form where the objective function denoted by z is written last and separated from the other equations by a solid line. In this way we obtain the initial tableau for the LP. The compact form here is An example illustrates the process of getting the initial tableau from an LP in standard.

After introducing slack variables x3; x4; x5, the LP in equality form is From this we obtain the initial tableau Abstracting from the initial tableau (1.7), a general tableau for the LP is any system T of n + 1 linear equations in the variables x1,.. , xd+n and z, with the properties that (i) T expresses n left-hand side variables xB and z in terms of the remaining d righthand side variables xN, i.e. there is an n-vector β, a d-vector γ, an n X d-matrix Λ and a real number z0 such that T is the system (ii) Any solution of (1.12) is a solution of (1.8) and vice versa. By property (ii), any tableau contains the same information about the LP but represented in a different way. All that the simplex algorithm is about is constructing a sequence of tableaus by gradually rewriting them, finally leading to a tableau in which the information is represented in such a way that the desired optimal solution can be read off directly. We will immediately show how this works in our example. By setting the right-hand side variables x1, x2 to zero, we find that the left-hand side variables x3, x4, x5 assume nonnegative values x3 = 1, x4 = 3, x5 = 2. This means, the vector x = (0, 0, 1, 3, 2) is a feasible solution of (1.10) and the vector x0 = (0, 0) is a feasible solution of (1.9). The objective function value z = 0 associated with this feasible solution is computed from the last row of the tableau. In general, any feasible solution that can be obtained by setting the right-hand side variables of a tableau to zero is called a basic feasible solution (BFS). In this case we also refer to the tableau as a feasible tableau. The left-hand side variables of a feasible tableau are called basic and are said to constitute a basis, the right-hand side ones are nonbasic. The goal of the simplex algorithm is now either to construct a new feasible tableau with a corresponding BFS of higher z-value, or to prove that there exists no feasible solution at all with higher z-value. In the latter case the BFS obtained from the tableau is reported as an optimal solution to the LP; in the former case, the process is repeated, starting from the new tableau. In the above tableau we observe that increasing the value of x1 i.e. making x1 positive will increase the z-value. The same is true for x2, and this is due to the fact that both variables have positive coefficients in the z-row of the tableau. Let us arbitrarily choose x2. By how much can we increase x2 ? If we want to maintain feasibility, we have to be careful not to let any of the basic variables go below zero. This means, the equations determining the values of the basic variables may limit x2's increment. Consider the first equation Together with the implicit constraint x3 >= 0, this equation lets us increase x2 up to the value x2 = 1 (the other nonbasic variable x1 keeps its zero value). The second equation does not limit the increment of x2 at all, and the third equation allows for an increase up to the value x2 = 2 before x5 gets negative. The most stringent restriction therefore is x3 >= 0, imposed by (1.13), and we will increase x2 just as much as we can, so we get x2 = 1 and x3=0. From the remaining tableau equations, the values of the other variables are obtained as To establish this as a BFS, we would like to have a tableau with the new zero variable x3 replacing x2 as a nonbasic variable. This is easy, the equation (1.13) which determined the new value of x2 relates both variables. This equation can be rewritten as: and substituting the right-hand side for x2 into the remaining equations gives the new tableau with corresponding BFS x = (0, 1, 0, 3, 1) and objective function value z = 1.

This process of rewriting a tableau into another one is called a pivot step, and it is clear by construction that both systems have the same set of solutions. The effect of a pivot step is that a nonbasic variable (in this case x2) enters the basis, while a basic one (in this case x3) leaves it. Let us call x2 the entering variable and x3 the leaving variable. In the new tableau, we can still increase x1 and obtain a larger z-value. x3 cannot be increased since this would lead to smaller z-value. The first equation puts no restriction on the increment, from the second one we get x1 < = 3 and from the third one x1 <= 1. So the third one is the most stringent, will be rewritten and substituted into the remaining equations as above. This means, x1 enters the basis, x5 leaves it, and the tableau we obtain is with BFS x = (1, 2, 0, 2, 0) and z = 3. Performing one more pivot step (this time with x3 the entering and x4 the leaving variable), we arrive at the tableau with BFS x = (3, 2, 2, 0, 0) and z = 5. In this tableau, no non-basic variable can increase without making the objective function value smaller, so we are stuck. Luckily, this means that we have already found an optimal solution. Why? Consider any feasible solution x‘ = (x‘1,………, x‘5) for (1.10), with objective function value z0. This is a solution to (1.11) and therefore a solution to (1.14). Thus, must hold, and together with the implicit restrictions x4; x5 ¸ 0 this implies z0 <= 5.

The tableau even delivers a proof that the BFS we have computed is the unique optimal solution to the problem: z = 5 implies x4 = x5 = 0, and this determines the values of the other variables. Ambiguities occur only if some of the non-basic variables have zero coefficients in the z-row of the final tableau. Unless a specific optimal solution is required, the simplex algorithm in this case just reports the optimal BFS it has at hand.

K. L. Clarkson (2014). A Las Vegas Algorithm for Linear and Integer Programming when the Dimension is Small. In Proceedings of 29th Annual IEEE Symposium Foundations of Computer Science. T. H. Cormen, C. E. Leiserson, and R. L. Rivest: Introduction to Algorithms. The MIT Press, Cambridge, MA. G. B. Dantzig (2013). Linear Programming and Extensions. Princeton University Press, Princeton, NJ. M. E. Dyer (1986). On a Multidimensional Search Technique and Its Application to the M. E. Dyer and A. M. Frieze: A Randomized Algorithm for Fixed-Dimensional Linear Programming. Math. Programming. H. Edelsbrunner and R. Seidel: Voronoi diagrams and arrangements. Discrete Comput. Geom. B. Gartner: A subexponential algorithm for abstract optimization problems. In Proceedings of 33rd Annual IEEE Symposium on Foundations of Computer Science. B. Gartner and E. Welzl: Vapnik-Chervonenkis dimension and pseudo-hyperplane arrangements. Discrete Comput. Geom. B. Gartner and E. Welzl: Linear programming randomization and abstract frameworks. In Proceedings of 13th Annual Symposium on Theoretical Aspects of Computer Science (STACS), volume 1046 of Lecture Notes in Computer Science.

Research Scholar, Shri Venkateshwara University, Gajraula