A Quick Intro to Linear Programming
Linear programming (LP) is a specialized form of matrix algebra that we can use to solve constrained multi-variable optimization scenarios. LP is part of a larger discipline known as Operations Research, which uses advanced mathematics to inform and optimize decision making.
The discussion and example herein are intended for intermediate-level Excel users who have little or no experience with using Solver to calculate LP problems.
Mathematically, we characterize LP as an equation of the form:
s.t. Ax ≤ b
As you may recall, for n = length, bold lower-case letters represent a 1 × n array, and bold upper-case letters represent an n × n matrix. The superscript capital T denotes a transpose; for example, turning a 1 × n array 90 degrees to form its n × 1 representation.
Also be aware that the term, matrix, is actually a generic expression that can apply as well to an n × n matrix, a 1 × n array, or a single-cell scalar. To avoid confusion, in addition to matrix, we’ll use the more specific terms array and scalar where applicable.
In the LP model above, the expression cTx is called the objective function. It signifies a matrix multiplication of the function to be minimized (or maximized), cT, by the decision variables, x. Decision variables are those elements of an LP problem that are discretionary; in other words, controllable by the decision maker.
Actually, LP is just a way of optimizing the objective function subject to the constraints A and b. And along the way, Solver adjusts the values of the decision variables, x, as necessary to produce the optimal outcome. It does this by ranking possible solutions according to the value of cTx they generate.
The variable A is a set of linear inequality constraints. We use A to limit the decision variables in x to being greater than or less than the corresponding values set forth in b. In this way, the relationship between c and x is defined and enforced.
Fortunately, the built-in version of Solver will allow us to calculate LP solutions for most simple (and even some moderately complex) LP scenarios. In setting up the calculation for Solver, we’ll also be using the built-in Excel functions MMULT and/or SUMPRODUCT to do our matrix arithmetic.
As you formulate your LP arguments, you’ll want to keep in mind the following:
- MMULT and SUMPRODUCT require at least two ranges separated by commas. For purposes of this article, we’ll assume exactly two ranges throughout.
- If the result of an operation will span more than one cell, you’ll need to set it up as an array formula. In Excel for Mac, you evaluate an array formula by pressing command-shift-return.
- SUMPRODUCT will return an error unless the dimensions of the ranges are exactly alike. In other words, SUMPRODUCT will not operate on a 1 × n array and an n × 1 array.
- MMULT will return an error unless the number of columns in the first range is equal to the number of rows in the second range. That means that if you want to use MMULT on the same two expressions that you successfully referenced in SUMPRODUCT, you’ll have to use the TRANSPOSE function on one or the other, like so:
=SUMPRODUCT(array1, array2) =MMULT(TRANSPOSE(array1), array2)
Note: in this article, we’ll forgo a review of matrix arithmetic/matrix algebra theory and the various mathematical operations that can be performed on arrays and matrices. Interested readers can find a good one-page review of the topic here. For the truly interested, all the materials for an undergraduate MIT course in managerial LP are available free online.
Formulating an Employee Work Schedule
In terms of practical application, a simple LP example might involve optimizing the schedule of a company’s workforce to minimize labor cost. Assume a scheduled airline operates seven days a week at a particular airport. The station’s daily labor demands (in terms of hours worked) for ground crew employees are as follows:
We’ll assume the collective bargaining agreement in place specifies the following:
- All employees are paid $20 per hour for straight time worked
- The company operates only one 8-hour shift per day
- Management is prohibited from hiring part-time employees
- The scope clause permits management to assign any employee to perform any necessary task
- Employees must receive two consecutive days off per week
To keep things simple, we will disregard seniority, bidding and the relative desirability of certain days off. We will also disallow overtime.
Based on the demand for labor in terms of hours, we can calculate the minimum number of employees required to work on a given day with the following argument:
This argument divides the number of hours required by 8 hours per employee, and if there is a remainder, the CEILING function returns the next integer value greater than the fractional result.
One way to solve the scheduling problem is to create a tableau of employee schedules (see below). Note that we treat the tableau values as binary: 1 for days worked, and 0 for days off. Note also that the tableau accounts for every possible combination of consecutive days off.
Next, we need an array of values representing the number of employees who are starting their 5-day work week on a particular day. We can specify any integer value here, since these are the values that Solver will change to optimize our solution. For the sake of simplicity, I’ve specified 20 employees for each day.
Next, we’ll create an array that sets out the number of employees who are scheduled to work on a particular day.
We’ll generate these values from a matrix multiplication of the binary (1, 0) values for each day in the table, and the entire array of employees who start work on each week day. Assume the tableau of days worked and days off is located at D11:J17, and the array of employees who start their work week on a particular day is located in L11:L17. The argument for available employees on Sunday is:
Note that I’ve included the dollar-sign designation in the second array because this range will be the same for all seven calculations.
After you’ve calculated the available employees for each day, it’s helpful to go ahead and recap the values for number of employees required just below. You’ll also want to designate a cell (L20) that captures the total number of employees, SUM(L11:L17).
We’ll create a cell (D23) to hold the value corresponding with the hourly rate of pay, and another cell (D24) to hold our objective function.
Our objective function in this case is the airline’s weekly payroll for ground crew:
Or, hourly pay rate, times eight hours per day, times total employees.
Once you’ve entered all of the above, we’ll save time by naming the range L11:L17 as “Sked_Emp,” the range D20:J20 as “Emp_Avail,” and the range D21:J21 as “Emp_Reqd.” The best way to name a range of cells is to select all of the cells in question, and then enter the (unique) name in the window to the left of the argument window:
We’re almost ready to calculate. Click on the Data tab and then on the Solver icon. When the Solver pane pops up, configure the LP problem like so:
There’s one final thing to check. Click on the Options button next to the Solving Method combo box, and make sure the box marked “Ignore Integer Constraints” is unchecked.
Now click the Solve button, and Excel should return the following changed values: