Linear programming has been a fundamental topic in the development of managerial decision-making. The subject has its origins in the early work of Fourier (1820s) on attempting to solve systems of linear inequalities. However, it has to wait for the invention of the Standard Simplex Method.
There are also many diverse applications, and therefore many specialized solution algorithms have been developed. Hatami-Marbini and Tavana (2011) introduced a new method called the bounded dual simplex method for bounded fuzzy number linear programming problems which is useful for these situations. This algorithm constructs a dual feasible basic solution after obtaining a working basic and then moves towards attaining primal feasibility while maintaining dual feasibility throughout. The use of graph-based LP model is reported by Diaby (2010), Sowlati, Assadi, and Paradi, (2010) extend the LP-based sensitivity analysis to multi-criteria decisionmaking. While Borgonovo and Percoco (2011) applied sensitivity analysis a portfolio problem with budget constraints that allows for simultaneous sensitivity analysis. Khurana and Arora (2012) modified the classical transportation problem to solve a three–dimensional linear trans–shipment problem. Sun (2010) uses linear programming as nonparametric statistical procedures for multiple-class discriminant and classification analysis.
1.1. Standard Simplex Method
Since World War II, linear programming (LP) has been used to solve small and large problems in almost all disciplines. The most popular solution algorithm is the Simplex method that is implemented in all LP software packages.
The simplex algorithm can be considered as a sub-gradient directional method, jumping from an initial feasible vertex to a neighboring vertex of feasible region until it arrives at an optimal vertex (if any). To start the algorithm, if it is needed, one must create an equivalent LP problem to satisfy its “Standard form requirement.” When the manager obtains the simplex optimal solution, then the manager has to interpret and to transform the final solution of the algorithm to obtain the optimal solution in terms of the original model, including the variables. This may not be an easy task. Moreover, solving LP problems in which some constraints are in (≥) or (=) form with non-negative right-hand side (RHS) has raised difficulties. One version of the simplex, known as the two-phase method, introduces an artificial objective function, which is the sum of artificial variables (Arsham 1997). Another version adds the penalty terms, which are the sum of artificial variables with very large, positive coefficients. The latter approach is known as the Big-M method (Arsham, 2006, 2007). Understanding the intuitive notion of Standard-form, artificial variables, and Big-M, may require a greater mathematical sophistication from most students/managers. The simplex methods have to iterate through many infeasible vertices to reach an initial feasible vertex.
Using the dual simplex method has its own difficulties. For example, when some coefficients in the objective function are not dual feasible, one must introduce an artificial constraint. Handling equality (=) constraints by the dual simplex method is tedious because of introduction of two new variables for each equality constraint: one extraneous slack variable and one surplus variable. Also, one may not be able to remove some equality (=) constraints by elimination at the outset, as this may violate the non-negativity condition introduced when constructing the “standard form.”