Solving Systems of Linear Equations K.
Goodoory
Introduction
The central mathematical problem of linear programming is to find the solution of a system of linear equations which maximizes or minimizes a given linear objective function
Equivalent systems
Two systems of equations are said to be equivalent if both systems have the same solution set. A solution to one system is automatically a solution to the other system and vice versa The method of solving a system of equations is to get an equivalent system which is easy to solve By solving the simple system, we simultaneously get the solutions to the original system
Elementary row operations
Multiply any equation in the system by a positive or
negative number Add to any equation a constant multiple of any other equation in the system
Basic and Nonbasic Variable
A variable x1 is said to be a basic variable in a given equation if it appears with a unit coefficient in that equation and zeros in all other equations Those variables which are not basic are called nonbasic variables By applying the elementary row operations, a given variable can be made a basic variable.
Pivot Operation
A pivot operation is a sequence of elementary operations that reduces a given system to an equivalent system in which a specified variable has a unit coefficient in one equation and zero elsewhere In order to get a canonical system, a sequence of pivot operations must be performed on the original system so that there exists at least one basic variable in each equation. The number of basic variables is decided by the number of equations in the system
Basic Solution
The solution obtained from a canonical system by setting the nonbasic variables to zero and solving for the basic variables is called a basic solution
Basic Feasible Solution
A basic feasible solution s a basic solution in which the values of the basic variables are non negative With m constraint and n variables the maximum number of basic solutions to the standard linear program is finite and is given by
n! m! n m !
Principles of the Simplex Method
The simplex method as developed by G.B. Dantzig is an iterative procedure for solving linear programming problems expressed in standard form The simplex method requires that the constraint equations be expressed as a canonical system from which a basic feasible solution can be readily obtained.
Steps of the Simplex Method
Start with an initial basic feasible solution in canonical
form Improve the initial solution if possible by finding with a better objective function value. At this step the simplex method implicitly eliminates from consideration all those basic feasible solutions whose objective function values are worse than the present one. This makes the procedure more efficient than the nave approach mentioned earlier. Continue to find better basic feasible solutions improving the objective function values. When a particular basic feasible solution cannot be improved further, it become an optimal solution and the simplex method terminates
Improving a Basic Feasible Solution
The simplex method checks whether it is possible to find a better basic feasible solution with a larger vale of Z(maximization). This is done b first examining whether the present solution is optimal.
Adjacent basic feasible solution
An adjacent basic feasible solution differs from the basic feasible solution in exactly one basic variable. In order to obtain an adjacent basic feasible solution, the simplex method makes one of the basic variable a nonbasic variable, and in its place a nonbasic variable is brought in as a basic variable
