Simplex method for linear programming problems

This macro finds the optimal solution of a linear program, using the Revised Form of the Simplex. Linear programming (LP) deals with an objective function with only linear terms, and assumes only linear constraints exist.

Usually, if the number of constraints is much smaller than the number of decision variables, the original form of the Simplex is inefficient.

The objective function can either be to maximize or minimize a mathematical function, such as representing a profit or cost. The optimization is usually constrained, meaning the optimal solution must be found within certain bounds usually defined by the amount of available resources or budget for a project.

Download the Macro

Be sure that Minitab knows where to find your downloaded macro. Choose Tools > Options > General. Under Macro location browse to the location where you save macro files.

Important

If you use an older web browser, when you click the Download button, the file may open in Quicktime, which shares the .mac file extension with Minitab macros. To save the macro, right-click the Download button and choose Save target as.

Required Inputs

  • A column containing the coefficients of the objective function.
  • Columns corresponding to each of the elements of the objective function including variables, equality symbol, and result. Each row in this set of columns identifies a constraint on the optimization.

The example that follows is taken from Hillier and Lieberman and represents the manufacturing of two products (x1, x2) for the Wyndor Glass Co. The three constraints represent the ability of each one of their three plants to use resources for the production of Product 1 (x1) and Product 2 (x2).

MAXIMIZE Profit = 3x1 + 5x2 (Objective function)

SUBJECT TO:

x1   <= 4 (Plant 1)
  2x2 <= 12 (Plant 2)
3x1 +2x2 <= 18 (Plant 3)

x1 ≥ 0, x2 ≥ 0 (Non-negativity constraints)

The coefficients, equality signs, and results should be entered in a Minitab worksheet as follows:

C1 C2 C3 C4 C5
x1 x2 inequality results objective
1 0 <= 4 3
0 2 <= 12 5
3 2 <= 18  

Optional Inputs

MIN
By default, the macro will solve a maximization problem. If you want to minimize the objective function, put a semicolon after the main command and in the second line use the command MIN and a period ("."), indicating the end of the command.

Running the Macro

Suppose your data are organized as above. To run the macro, choose Edit > Command Line Editor and type:

%SIMPLEX C1-C2 C4 C5; 
INEQ C3.

Click Submit Commands.

More Information

Usually, n + 2 columns are specified to formulate the problem. The final argument entered in the main command corresponds to the column containing the coefficients of the objective function. The penultimate argument requires a column specifying the right hand side of all inequalities in the problem (with the exception of non-negativity, since this is assumed by default). The first n columns specify the coefficients (a11, a12,...,a1n) for all linear constraints of type a11*x1 + a12*x2 + ... + a1n*xn.

Finally, if all inequalities are of a "<=" type, then you don't have to do anything; otherwise specify the symbols for all constraints in one column. You may enter any of the following symbols: >=, >, ≥, ≤, <=, <, =.

For more technical details about the algorithm see:

Bazaraa, M.S., Jarvis, J.J. and Sherali, H.D. "Linear Programming and Network Flows", Fourth edition. John Wiley & Sons, New Jersey, 2010.

By using this site you agree to the use of cookies for analytics and personalized content.  Read our policy