Essentials of Linear Programming for Managers: From System of Inequalities to Software Implementation

Essentials of Linear Programming for Managers: From System of Inequalities to Software Implementation

Hossein Arsham (Johns Hopkins University, USA), M. Bardossy (University of Baltimore, USA) and D. K. Sharma (University of Baltimore, USA)
Copyright: © 2014 |Pages: 32
DOI: 10.4018/978-1-4666-4506-6.ch007


This chapter provides a critical overview of Linear Programming (LP) from a manager's perspective. The main objective is to provide managers with the essentials of LP as well as cautionary notes and defenses on common modeling issues and software limitations. The authors illustrate the findings by solving a simple LP directly on the original decision variables and constraints space without adding new variables or translating the model to fit a specific solution algorithm. The aims are the unification of diverse set of topics in their natural states in a manner that are easy to understand and providing useful information to the managers. The advances in computing software have brought LP tools to the desktop for a variety of applications to support managerial decision-making. However, it is already recognized that current LP tools, in ample circumstances, do not answer the managerial questions satisfactorily. For instance, there is a costly difference between the mathematical and managerial interpretations of sensitivity analysis. LP software packages provide one-change-at-a-time sensitivity results; the authors develop the largest sensitivity region, which allows for simultaneous dependent and/or independent changes, based on the optimal solution. The procedures are illustrated by numerical examples including LP in standard-form and LP in non standard-form.
Chapter Preview

1. Introduction

Linear programming (LP) has been a fundamental topic in the development of managerial decision-making. The subject has its origins in the early work of L. B. J. Fourier (1820s) on attempting to solve systems of linear inequalities. However, the wide spread use and acceptance of LP had to wait until the invention of the Standard Simplex Method.

1.1 Standard Simplex Method

Since World War II, LP has been used to solve problems of various dimensions in almost all disciplines. The most popular solution algorithm is the Simplex method that is implemented by most 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 the feasible region until it arrives at an optimal vertex. The Simplex method requires that the model be expressed in a special format called “Standard Form”, that is, some constraints and variables must be transformed. Consequently, when the manager obtains a solution through the Simplex method, she/he is left with the task of interpreting and transforming the Simplex solution back to the original managerial problem. However, this may not be an easy task.

For instance, solving LP problems in which some constraints are in (≥) or (=) form with non-negative right-hand side (RHS) has raised difficulties. With that purpose, the simplex method requires a feasible stating solution. When such starting solution is not readily at-hand, alternative methods are necessary. One version of the Simplex method, known as the two-phase method, introduces an artificial objective function, which is the sum of artificial variables (see Arsham 1997a, 1997b). Another version adds penalty terms, which are the sum of artificial variables with very large, positive coefficients. The latter approach is known as the Big-M method, (see Arsham 2006, 2007). On the other hand, 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 the 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.”

Arsham (2013) proposes a tabular interior boundary approach that intents to address these concerns and solves the original managerial LP model, without any need of “Standard Form”, artificial variables, artificial constraints, and Big-M. While these variants of the simplex successfully handle an array of constraint forms, they impose a burden and mathematical sophistication on manager that make difficult the success of LP applications.

1.2 The Costly Difference Between the Managerial and Modeler Interpretation

Koltai and Terlaky (2000) state that managerial questions are not answered satisfactorily with the mathematical interpretation of sensitivity analysis. Software packages provide sensitivity results focused on the optimality of a basis and not on the optimality of the values of the decision variables. The implementation of the misunderstood shadow prices and their range of validity may coax managers to take poor decisions with considerable financial losses and strategic consequences. Another source of confusion is the similarity of terms used in operations research (i.e., re-search, as a process), and other related fields. For example, “shadow price” and “opportunity cost” have somewhat different meanings in the LP and Economics literature. The “opportunity cost” of an action in economics can be interpreted as the “shadow price” of that action on the budget.

The LP software packages provide sensitivity results about the optimality of a basis and not about the optimality of the values of the decision variables and the shadow prices that are of interest to the manager. In Section 6 we develop the largest sensitivity region based on the optimal vertex, and allows for simultaneous dependent/independent changes.

Complete Chapter List

Search this Book: