1. Introduction
One of the most dynamic areas of applied mathematics is linear programming (LP). The simplex method was first time implemented by George Barnard Dantzig during Second World War, then the method was introduced by [1] , the simplex algorithm is an iterative procedure for solving linear programming problem in finite number of steps. It provides an algorithm which consists of moving from one vertex of feasible region to another vertex of feasible region in such a manner that the value of objective function at the neighboring vertex is near to optimal than at the previous vertex. The procedure is repeated until the optimal solution reached and since the number of vertices are finite, therefore the method leads to an optimal vertex (Optimal solution) in a finite number of repetition of process or indicate about the existence of unbounded or infeasible solution. This method tests adjacent vertices of the feasible set (which is a polytope) in succesion so that each new vertex improves the objective function value or leaves it unchanged. The Simplex method is very efficient in practice. However, in [2] , Klee and Minty gave an example of a linear programming problem in which the polytope is a distortion of an n-dimensional cube. They show the number of arithmetic operations in the simplex algorithm grows exponentially with the number of variables. In [3] , Khachiyan proposed the first polynomial algorithm, the ellipsoid method. In [4] , Karmarkar suggested the second polynomial-time algorithm, which appears to be more efficient than Simplex method, especially when the problem size increases above some thousands of variables [5] . These authors motivate me to think in different procedure by which the time of solving an LPP should take less time with the less number of variables. One of the important steps of the simplex algorithm is of course selection of basis-entering variable. Dantzig simplex method still seems to be the most efficient procedure for majority of practical problems, especially for small problems.
In this research paper, I proposed an easy simplex algorithm and defined it as AHA simplex algorithm (by the short name of author). The algorithm will definitely take less time in solving an LPP with the help of assumption that there is no basic variables at initial stage, the objective function value is zero at this stage with all non basic variables which is same as the simplex method. The idea is to improve the objective function value in each iteration by entering non basic variable in blank set of basic variables. Then, we do the calculation according to the easy simplex algorithm which is explained in the coming sections with illustration.
2. Notation
The general form of an LPP is
LPP (2.1)
Non negative condition
It can be written in Matrix form as:
LPP (2.2)
where
,
,
,
If the above problem has only two vectors, then it can solve easily by Graphical method. If the LPP has more than two variables, then simplex method is appropriate and powerful method to solve these types of problems.
3. Proposed AHA Simplex Simulation Algorithm
3.1. The Simplex Algorithm
To solve any LPP using simplex algorithm, the existence of an initial basic feasible solution is always assumed. Consider the LPP (2.2). The steps for the computation of an optimum solution are as follows:
Step 1. Check whether the objective function of the given LPP is to be maximized or minimized. If it is to be minimized then we convert it into a problem of maximizing it by using the result Maximum z = −Minimum (−z)
Step 2. Check whether all
are non negative. If any one of
is negative then multiply the corresponding inequation by −1, so as to get all
must be non negative.
Step 3. Convert all the inequations of the constraints into equations by introducing slack and/or surplus variables in the constraints. Put the costs of these variables equal to zero.
Step 4. Obtain an initial basic feasible solution to the problem in the form
and put it in the first column of the simplex tableu.
Step 5. Compute the net evaluations
using the relation
where
examine the sign
a) If all
then the initial basic feasible solution is an optimal basic feasible solution.
b) If at least one
, proceed to the next step.
Step 6. If there is more than one
then choose the most negative of them. Let it be for
a) If all
then the problem is an unbounded solution to the given problem.
b) If at least one
then corresponding vector
is known as pivotal column, enter the basis
.
Step 7. Compute the ratios
and choose the minimum ratio. Suppose the vector
have the minimum ratio then it is known as pivotal row, will leave the basis
. The common element of pivotal column and pivotal row is pivotal element
.
Step 8. Convert the pivotal element to unity by dividing its row by pivotal element
and all other elements in pivotal column to zero by making use of the relations:
Step 9. Go to step 5 and repeat the computational procedure until either an optimum solution is obtained or there is an unbounded solution.
3.2. The Easy Simplex (AHA Simplex) Algorithm
Consider the same LPP (2.2). Without loss of generality the objective function can be written as objective inequation:
(3.2.1)
or
(3.2.2)
(3.3.3)
(3.3.4)
Steps for the computation of an optimum solution are as follows:
Step 1. Check whether the objective function of the given LPP is to be maximized or minimized. If it is to be minimized then we convert it into a problem of maximizing it by using the result Maximum z = −Minimum (−z).
Step 2. Check whether all
are non negative. If any one of
is negative then multiply the corresponding inequation by −1, so as to get all
must be non negative.
Step 3. Examine the sign of all decision variables in objective inequation
a) If all
then the solution is an optimal solution where
and
.
b) If at least one
, proceed to the next step.
Step 4. If there is more than one
then choose the most negative of them. Let it be for
a) If all
then the problem is an unbounded solution to the given problem.
b) If at least one
then corresponding vector
is known as pivotal column, enter into the basis
.
Step 5. Compute the ratios
and choose the minimum ratio. Suppose
have the minimum ratio then it is known as pivotal row, which is initially blank will fill by entering the variable
into the basis
. The common element of pivotal column and pivotal row is pivotal element
.
Step 6. Convert the pivotal element to unity by dividing the row by pivotal element
, and all other elements in pivotal column to zero by making use of the relations:
Step 7. Go to step 3 and repeat the computational procedure until either an optimum solution is obtained or there is an unbounded solution.
4. Numerical Illustrations
Illustration 1: Solve the following LPP.
Solution: Since there is Maximization type objective function and all constraints are less than type. Then we use the AHA Simplex method as
Initial Table (Table 1)
The most negative coefficients of
in objective inequation is ? 40 in
in Table 1, so the entering variable is
. Minimum positive ratio is 100, so the
enter into
. Therefore pivotal element is 40.
First Iteration (Table 2)
The most negative coefficients of
in objective inequation is −19 in
in Table 2, so the entering variable is
. Minimum positive ratio is
, so the
enter into
. Therefore pivotal element is 35/4.
Second Iteration (Table 3)
The most negative coefficients of
in objective inequation is −20/7 in
in Table 3, so the entering variable is
. Minimum positive ratio is
, so the
enter into
. Therefore pivotal element is 3/7.
Third Iteration (Table 4)
Since the all coefficients of
in objective inequation in
of Table 4 is either zero or positive, means the optimal solution achieved, and optimal solution always lies at extreme point thus the optimal solution is as
,
,
Illustration 2: Solve the following LPP.
Solution: Since there is Maximization type objective function and some constraints are in greater than form, so subtract extra variables as follows.
Then we use the AHA Simplex method as
Initial Table (Table 5)
The most negative coefficients of
in objective inequation is―4 in
of Table 5, so the entering variable is
. Minimum positive ratio is 40/3, so the
enter into
. Therefore pivotal element is 3.
First Iteration (Table 6)
The most negative coefficients of
in objective inequation is −4/3 in
of Table 6, so the entering variable is
. Minimum positive ratio is
, so the
enter into
. Therefore pivotal element is 1/3.
Second Iteration (Table 7)
Since the all coefficients of
in objective inequation
of Table 7 is either zero or positive, means the optimal solution achieved, and optimal solution always lies at extreme point thus the optimal solution is as
,
,
.
5. Conclusion
Since the Simplex Algorithm is an algorithm to solve the Linear Programming Problem (LPP) for more than two variables (also applicable in two variable) in such a manner that the optimal solution is achieved after a fixed number of iteration, the proposed Easy (AHA) Simplex Algorithm is a better algorithm to solve an LPP, because it has lesser calculation because the number of variables are less and steps (in some cases) and take lesser time than the Simplex algorithm.