Introduction

Linear Programming is the most fundamental of all management science tools. This is due primarily to two reasons:

1. The linear programming model is robust enough to model many problems of practical interest, and
2. The resulting models are solvable in a reasonable amount of time.

In a linear programming model, there are variables representing the decisions to be made. Such variables are normally represented as and so on. There is an objective function which is to be maximized or minimized. This function must be a linear function of the variables, like . Finally, there are a number of constraints limiting the feasible values for the variables. Such constraints are also linear, but can be either equality (=) or inequality constraints ( , ).

The art of linear programming is to use this limited set of structures to accurately model real decision making problems. This can be done only by practice: if you are unfamiliar with formulating linear programming models, please let me know, and I can give you some sample problems.

Once you have a linear programming model, it is very easy to use Excel's Solver or other software program (I generally use a program called LINDO) to find the solution to the model. The software package will find the best values to assign to the decision variables so that all constraints are satisfied and the objective takes on the best value possible. There are a number of technical details on how this is done, but we won't go into them: simply understand that models with thousands of variables and constraints are easily solved on a PC type computer.

There is a lot more information out of a computer run than just the solution however, and from a managerial or consulting point of view, this information may be the most valuable part of the model. The primary piece of information is a ``dual value'' or price for each constraint. Imagine taking a constraint like and increasing the right hand side a bit (from 40 to 41, say). If we then find the new optimal solution, clearly the objective will be better (more for a maximization, less for a minimization). The dual value for a constraint gives an estimate (and generally a very good one) for what that change will be without resolving the problem. This is probably best illustrated with a couple of examples (apologies for the artificial nature of these examples, but I need something small enough to handle easily in class).