An Alternative to the Simplex Method for Solving Linear Programming Problems: A Managerial Perspective

By Lev, Benjamin; Kowalski, Krzysztof | International Journal of Management, August 2010 | Go to article overview

An Alternative to the Simplex Method for Solving Linear Programming Problems: A Managerial Perspective


Lev, Benjamin, Kowalski, Krzysztof, International Journal of Management


The objective of this paper is to develop a simpler alternative to the widely-used Simplex Method for solving linear programming problems, from the perspective of practicing managers. It allows bounded variables where the lower and upper bounds could be negative or positive, therefore eliminating the need for introducing additional variables for the purpose of preserving non-negativity. The variables upper bounds do not require additional constraints. The inequality constraints are handled through slack/surplus variables. In contrast to the Simplex Method there is no need for substituting variables and all operations are performed only on the original equations. This method can not only form the basis for more efficient computer programs, but can also enable linear programming problems to be more easily taught to a larger audience than at present, that includes practicing managers.

1. Introduction

Linear Programming (LP) problems are the most commonly formulated problems in Operations Research and Management Science (OR/MS). Their wide application makes them a subject of an extensive research resulting in a development of very efficient computer programs designed to find the optimal solution. Most of those codes are based on the Simplex Method developed over the last 50 years. LP is usually introduced at the university undergraduate level and in some cases graduate level mostly due to the fact that the Simplex Method is complex and may require matrix algebra. The main goal of the authors is to attract practitioners outside OR/MS and to simplify the solution technique. The Simplex theory, while excellent for commercial use is very awkward for class room demonstration especially when solving the problem manually. It requires a formulation of non-negative variables at a cost of adding constraints and variables (slack, surplus, artificial) which eventually increase the size of the problem. The Simplex requires updating the coefficient matrix and often requires inverting the matrix. An error is carried further into subsequent iterations. Such is not the case in the proposed method. All iterations are performed on the original set of equations and any error corrects itself in the next iteration.

2. The LP Problem

LP is an optimization problem with a linear objective function and a set of linear constraints. The theory behind LP can be found in many OR/MS text books; see for example Hillier and Lieberman [1, 3, 4, and 5].

LP formulation:

Equation (2) can also represent relaxed constraints. In such case the equality sign is replaced with ≤ or ≥ inequality symbol.

Notice that there is no restriction on the x^sup min^^sub j^ and x^sup max^^sub j^ values, both can be negative, zero or positive.

Definitions: A loose variable is at value not equal to its bounds, i.e. to x^sup min^^sub j^ or to x^sup max^^sub j^ while a tight variable is equal to its bounds, i.e. to x^sup min^^sub j^ or to x^sup max^^sub j^. x^sub j^ is loose if x^sup min^^sub j^ < x^sub j^ < x^sup max^^sub j^ and x^sub j^ is tight if x^sub j^ = x^sup min^^sub j^ or if x^sub j^ = x^sup max^^sub j^.

3. Description of the new procedure

The proposed method is based on the principle of linearity, including an ?-m degree of freedom for ? variables, m constraints in an m ? ? set of linear equations. First step is finding an initial feasible solution, not necessarily basic. This can be done using any of the many available methods in OR/MS basic textbooks. In the next step m+1 loose variables are selected for analysis. Of those one variable will be changed (increased or decreased) by one unit from the originally assigned value and the remaining m variables are adjusted/computed accordingly to comply with the constraints; and a new Z value is computed. Simultaneously all the rates of change for the m variables are recorded. Tracking the Z value in the improved direction we analyze the changes in all variables to identify the one which reaches its bound first. …

The rest of this article is only available to active members of Questia

Sign up now for a free, 1-day trial and receive full access to:

  • Questia's entire collection
  • Automatic bibliography creation
  • More helpful research tools like notes, citations, and highlights
  • Ad-free environment

Already a member? Log in now.

Notes for this article

Add a new note
If you are trying to select text to create highlights or citations, remember that you must now click or tap on the first word, and then click or tap on the last word.
One moment ...
Default project is now your active project.
Project items

Items saved from this article

This article has been saved
Highlights (0)
Some of your highlights are legacy items.

Highlights saved before July 30, 2012 will not be displayed on their respective source pages.

You can easily re-create the highlights by opening the book page or article, selecting the text, and clicking “Highlight.”

Citations (0)
Some of your citations are legacy items.

Any citation created before July 30, 2012 will labeled as a “Cited page.” New citations will be saved as cited passages, pages or articles.

We also added the ability to view new citations from your projects or the book or article where you created them.

Notes (0)
Bookmarks (0)

You have no saved items from this article

Project items include:
  • Saved book/article
  • Highlights
  • Quotes/citations
  • Notes
  • Bookmarks
Notes
Cite this article

Cited article

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

(Einhorn, 1992, p. 25)

(Einhorn 25)

1

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

Cited article

An Alternative to the Simplex Method for Solving Linear Programming Problems: A Managerial Perspective
Settings

Settings

Typeface
Text size Smaller Larger Reset View mode
Search within

Search within this article

Look up

Look up a word

  • Dictionary
  • Thesaurus
Please submit a word or phrase above.
Print this page

Print this page

Why can't I print more than one page at a time?

Full screen

matching results for page

Cited passage

Style
Citations are available only to our active members.
Sign up now to cite pages or passages in MLA, APA and Chicago citation styles.

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn, 1992, p. 25).

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences." (Einhorn 25)

"Portraying himself as an honest, ordinary person helped Lincoln identify with his audiences."1

1. Lois J. Einhorn, Abraham Lincoln, the Orator: Penetrating the Lincoln Legend (Westport, CT: Greenwood Press, 1992), 25, http://www.questia.com/read/27419298.

Cited passage

Welcome to the new Questia Reader

The Questia Reader has been updated to provide you with an even better online reading experience.  It is now 100% Responsive, which means you can read our books and articles on any sized device you wish.  All of your favorite tools like notes, highlights, and citations are still here, but the way you select text has been updated to be easier to use, especially on touchscreen devices.  Here's how:

1. Click or tap the first word you want to select.
2. Click or tap the last word you want to select.

OK, got it!

Thanks for trying Questia!

Please continue trying out our research tools, but please note, full functionality is available only to our active members.

Your work will be lost once you leave this Web page.

For full access in an ad-free environment, sign up now for a FREE, 1-day trial.

Already a member? Log in now.