ABSTRACT

The purpose of this research paper is to introduce Easy Simplex Algorithm which is developed by author. The simplex algorithm first presented by G. B. Dantzing, is generally used for solving a Linear programming problem (LPP). One of the important steps of the simplex algorithm is to convert all unequal constraints into equal form by adding slack variables then proceeds to basic solution. Our new algorithm i) solves the LPP without equalize the constraints and ii) leads to optimal solution definitely in lesser time. The goal of suggested algorithm is to improve the simplex algorithm so that the time of solving an LPP will be definitely lesser than the simplex algorithm. According to this Easy Simplex (AHA Simplex) Algorithm the use of Big M method is not required.

Keywords:

Linear Programming, Simplex Algorithm, Optimal Solution, Easy Simplex Algorithm, AHA Simplex Algorithm

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

$\text{Max}z=c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$

$\begin{array}{l}\text{Subject}\text{to}{a}_{11}{x}_1+a_{12}{x}_2+\cdots +a_{1n}{x}_n\le b_1,\\ a_{21}{x}_1+a_{22}{x}_2+\cdots +a_{2n}{x}_n\le b_2,\\ ⋮\\ a_{m1}{x}_1+a_{m2}{x}_2+\cdots +a_{mn}{x}_n\le b_m,\end{array}$ LPP (2.1)

Non negative condition $x_1,x_2,\cdots ,x_n\ge 0$

It can be written in Matrix form as:

$\text{Max}z=c^{\text{T}}X$

$\begin{array}{l}\text{Subject}\text{to}AX\le b\\ X\ge 0\end{array}$ LPP (2.2)

where

$X=n\times 1\text{Column}\text{Vector}$ ,

$A=m\times n\text{Coefficient}\text{Matrix}$ ,

$b=m\times 1\text{Column}\text{Vector}$ ,

$c=1\times n\text{Row}\text{Vector}$

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 $b_i\left(i=1,2,3,\cdots ,m\right)$ are non negative. If any one of $b_i$ is negative then multiply the corresponding inequation by −1, so as to get all $b_i\left(i=1,2,3,\cdots ,m\right)$ 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 $x_B=B^{-1}b$ and put it in the first column of the simplex tableu.

Step 5. Compute the net evaluations $z_j-c_j\left(j=1,2,\cdots ,n\right)$ using the relation $z_j-c_j=C_B{y}_j-C_j$ where $y_j=B^{-1}{a}_j$ examine the sign $z_j-c_j$

a) If all $\left(z_j-c_j\right)\ge 0$ then the initial basic feasible solution is an optimal basic feasible solution.

b) If at least one $z_j-c_j<0$ , proceed to the next step.

Step 6. If there is more than one $z_j-c_j<0$ then choose the most negative of them. Let it be for $j=r$

a) If all $y_{ir}\le 0\left(i=1,2,3,\cdots ,m\right)$ then the problem is an unbounded solution to the given problem.

b) If at least one $y_{ir}>0\left(i=1,2,3,\cdots ,m\right)$ then corresponding vector $y_r$ is known as pivotal column, enter the basis $y_B$ .

Step 7. Compute the ratios $\left\{\frac{x_{Bi}}{y_{ir}};\forall y_{ir}>0\right\}$ and choose the minimum ratio. Suppose the vector $y_k$ have the minimum ratio then it is known as pivotal row, will leave the basis $y_B$ . The common element of pivotal column and pivotal row is pivotal element $y_{kr}$ .

Step 8. Convert the pivotal element to unity by dividing its row by pivotal element $y_{kr}$ and all other elements in pivotal column to zero by making use of the relations:

$y_{ij}\left(New\right)=\frac{y_{kj}\left(Old\right)}{y_{kr}\left(Old\right)};\forall j=1,2,3,\cdots ,n,i=k$

$y_{ij}\left(New\right)=y_{ij}\left(Old\right)-\frac{y_{kj}\left(Old\right)\times y_{ir}\left(Old\right)}{y_{kr}\left(Old\right)};\forall i=1,2,3,\cdots ,m,i\ne k,j=1,2,3\cdots ,n,$

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:

$\text{Max}z\le c_1{x}_1+c_2{x}_2+\cdots +c_n{x}_n$ (3.2.1)

or

$\text{Max}\left[\begin{array}{cc}1& -c^{\text{T}}\end{array}\right]\left[\begin{array}{c}z\\ x\end{array}\right]\le 0$ (3.2.2)

$\text{Subject}\text{to}\left[\begin{array}{cc}0& A\end{array}\right]\left[\begin{array}{c}z\\ x\end{array}\right]\le b$ (3.3.3)

$X\ge 0$ (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 $b_i\left(i=1,2,3,\cdots ,m\right)$ are non negative. If any one of $b_i$ is negative then multiply the corresponding inequation by −1, so as to get all $b_i\left(i=1,2,3,\cdots ,m\right)$ must be non negative.

Step 3. Examine the sign of all decision variables in objective inequation $-c_j$

a) If all $-c_j\ge 0$ then the solution is an optimal solution where $z=0$ and $x_j=0\forall \left(j=1,2,\cdots ,n\right)$ .

b) If at least one $-c_j<0$ , proceed to the next step.

Step 4. If there is more than one $-c_j<0$ then choose the most negative of them. Let it be for $j=r$

a) If all $a_{ir}\le 0\left(i=1,2,3,\cdots ,m\right)$ then the problem is an unbounded solution to the given problem.

b) If at least one $a_{ir}>0\left(i=1,2,3,\cdots ,m\right)$ then corresponding vector $x_r$ is known as pivotal column, enter into the basis $y_B$ .

Step 5. Compute the ratios $\left\{\frac{b_i}{a_{ir}};\forall a_{ir}>0,i=1,2,3,\cdots ,m\right\}$ and choose the minimum ratio. Suppose $\left\{\frac{b_k}{a_{kr}};\forall a_{kr}>0\right\}$ have the minimum ratio then it is known as pivotal row, which is initially blank will fill by entering the variable $x_r$ into the basis $y_B$ . The common element of pivotal column and pivotal row is pivotal element $a_{kr}$ .

Step 6. Convert the pivotal element to unity by dividing the row by pivotal element $a_{kr}\left(New\right)=\frac{a_{kj}\left(Old\right)}{a_{kr}\left(Old\right)}$ , and all other elements in pivotal column to zero by making use of the relations:

$-c_j\left(New\right)=-c_j\left(Old\right)-\left\{-c_r\left(Old\right)\right\}\times a_{kj}\left(New\right);\forall c_j$

$a_{ij}\left(New\right)=a_{ij}\left(Old\right)-\left\{a_{ir}\left(Old\right)\right\}\times a_{kj}\left(New\right);\forall a_{ij},i\ne k$

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.

$\text{Max}z=12x_1+20x_2+18x_3+40x_4$

$\begin{array}{l}\text{Subject}\text{to}4x_1+9x_2+7x_3+4x_4\le 6000,\\ x_1+x_2+3x_3+40x_4\le 4000,\\ \text{and}{x}_1,x_2,x_3,x_4\ge 0\end{array}$

Solution: Since there is Maximization type objective function and all constraints are less than type. Then we use the AHA Simplex method as

$\text{Max}z-12x_1-20x_2-18x_3-40x_4\le 0$

$\begin{array}{l}\text{Subject}\text{to}4x_1+9x_2+7x_3+4x_4\le 6000,\\ x_1+x_2+3x_3+40x_4\le 4000,\\ \text{and}{x}_1,x_2,x_3,x_4\ge 0\end{array}$

Initial Table (Table 1)

The most negative coefficients of $x_4$ in objective inequation is ? 40 in $\left(Ro{w}_0\right)$ in Table 1, so the entering variable is $x_4$ . Minimum positive ratio is 100, so the $x_4$ enter into $\left(Ro{w}_2\right)$ . Therefore pivotal element is 40.

$R_2\left(New\right)=R_2\left(Old\right)÷40$

$R_0\left(New\right)=R_0\left(Old\right)+40\times R_2\left(New\right)$

$R_1\left(New\right)=R_1\left(Old\right)+\left(-10\right)\times R_2\left(New\right)$

First Iteration (Table 2)

The most negative coefficients of $x_2$ in objective inequation is −19 in $\left(Ro{w}_0\right)$ in Table 2, so the entering variable is $x_2$ . Minimum positive ratio is $\frac{5000}{35/4}\approx 571.429$ , so the $x_2$ enter into $\left(Ro{w}_1\right)$ . Therefore pivotal element is 35/4.

$R_1\left(New\right)=R_1\left(Old\right)÷35/4$

$R_0\left(New\right)=R_0\left(Old\right)+19\times R_1\left(New\right)$

$R_2\left(New\right)=R_2\left(Old\right)+\left\{-\left(1/40\right)\right\}\times R_1\left(New\right)$

Second Iteration (Table 3)

The most negative coefficients of $x_1$ in objective inequation is −20/7 in $\left(Ro{w}_0\right)$ in Table 3, so the entering variable is $x_1$ . Minimum positive ratio is $\frac{4000/7}{3/7}\approx 1333.33$ , so the $x_1$ enter into $\left(Ro{w}_1\right)$ . Therefore pivotal element is 3/7.

$R_1\left(New\right)=R_1\left(Old\right)÷3/7$

$R_0\left(New\right)=R_0\left(Old\right)+\left(20/7\right)\times R_1\left(New\right)$

$R_2\left(New\right)=R_2\left(Old\right)+\left\{-\left(1/70\right)\right\}\times R_1\left(New\right)$

Third Iteration (Table 4)

Since the all coefficients of $x_j$ in objective inequation in $\left(Ro{w}_0\right)$ 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 $z=\frac{56000}{3}$ , $x_1=\frac{4000}{3}$ , $x_4=\frac{200}{3}$

Illustration 2: Solve the following LPP.

$\text{Max}z=4x_1+3x_2$

$\begin{array}{l}\text{Subject}\text{to}{x}_1+x_2\le 50,\\ x_1+2x_2\ge 80,\\ 3x_1+2x_2\ge 40\\ \text{and}{x}_1,x_2\ge 0\end{array}$

Solution: Since there is Maximization type objective function and some constraints are in greater than form, so subtract extra variables as follows.

$\text{Max}z=4x_1+3x_2+0x_3+0x_4$

$\begin{array}{l}\text{Subject}\text{to}{x}_1+x_2\le 50,\\ x_1+2x_2-x_3\le 80,\\ 3x_1+2x_2-x_4\le 40\\ \text{and}{x}_1,x_2,x_3,x_4\ge 0\end{array}$

Then we use the AHA Simplex method as

Initial Table (Table 5)

The most negative coefficients of $x_1$ in objective inequation is―4 in $\left(Ro{w}_0\right)$ of Table 5, so the entering variable is $x_1$ . Minimum positive ratio is 40/3, so the $x_1$ enter into $\left(Ro{w}_3\right)$ . Therefore pivotal element is 3.

$R_3\left(New\right)=R_3\left(Old\right)÷3$

$R_0\left(New\right)=R_0\left(Old\right)+4\times R_3\left(New\right)$

$R_1\left(New\right)=R_1\left(Old\right)+\left(-1\right)\times R_3\left(New\right)$

$R_2\left(New\right)=R_2\left(Old\right)+\left(-1\right)\times R_3\left(New\right)$

First Iteration (Table 6)

The most negative coefficients of $x_4$ in objective inequation is −4/3 in $\left(Ro{w}_0\right)$ of Table 6, so the entering variable is $x_4$ . Minimum positive ratio is $\frac{110/3}{1/3}=110$ , so the $x_4$ enter into $\left(Ro{w}_1\right)$ . Therefore pivotal element is 1/3.

$R_1\left(New\right)=R_1\left(Old\right)÷1/3$

$R_0\left(New\right)=R_0\left(Old\right)+\left(4/3\right)\times R_1\left(New\right)$

$R_2\left(New\right)=R_2\left(Old\right)+\left\{-\left(1/3\right)\right\}\times R_1\left(New\right)$

$R_3\left(New\right)=R_3\left(Old\right)+\left(1/3\right)\times R_1\left(New\right)$

Second Iteration (Table 7)

Since the all coefficients of $x_j$ in objective inequation $\left(Ro{w}_0\right)$ 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 $z=200$ , $x_1=50$ , $x_4=110$ .

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.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

Cite this paper

Ansari, A.H. (2019) Easy Simplex (AHA Simplex) Algorithm. Journal of Applied Mathematics and Physics, 7, 23-30. https://doi.org/10.4236/jamp.2019.71003

References