(c) American Institute of Certified Public Accountants. Contact AICPA for permission to reproduce this article., Information Technology

Solve problems with linear programming and Excel

By Clarence Goh, Ph.D.

Management accountants tasked with figuring out the way to make the most of limited resources can employ a form of mathematical optimisation to determine the best approach.

A management accountant’s knowledge of relevant revenues and costs is important for many decisions, among them capital budgeting, outsourcing, special orders, product mix, and the adding or dropping of specific product lines. Many of these decisions require management accountants to determine or recommend specific courses of action that would lead to an optimal outcome (such as maximising profits or minimising costs) given a limited set of resources (such as production inputs). It is therefore important that they apply appropriate analytical techniques in approaching such decisions. Linear programming is one technique that accountants can often readily apply to determine the best outcome in these situations.

This article provides a description of linear programming, demonstrates how it can be performed using Microsoft Excel’s free Solver add-in, and illustrates its use through an example from management accounting.

Linear programming

Linear programming is a form of mathematical optimisation that seeks to determine the best way of using limited resources to achieve a given objective. The key elements of a linear programming problem include:

  • Decision variables: Decision variables are often unknown when initially approaching the problem. These variables usually represent identifiable “things” or inputs that a manager can control (ie, how many of each specific model of washing machines to produce). The goal, then, is to determine those values that maximise or minimise the objective function.
  • Objective function: This is a math-ematical function that incorporates decision variables to express a manager’s goals. A manager’s goal is to either maximise or minimise the objective function.
  • Constraints: These are mathematical functions that incorporate decision variables to express boundaries on possible solutions.
  • Variable bounds: Decision variables are rarely allowed to take on any value (from minus infinity to plus infinity). Instead, they usually have bounds (eg, ≥ 0).

It should also be noted that while all the mathematical expressions for the objective function and constraints in linear programming are necessarily linear in nature (hence the name; see the sidebar “Limitations of Linear Programming” at the bottom of the page), the technique remains one of the most widely used methods of optimisation, and the largest and most complex linear programming problems have millions of decision variables and hundreds of thousands of constraints.

Before we continue, it’s important to note that this article is not intended to be an exhaustive course in linear programming. It’s instead an introduction to the topic and how the Excel Solver add-in can be used to help with this type of complex problem.

The example below demonstrates how a management accountant could use the Solver tool to perform linear programming to determine an optimal product mix that maximises profits given a limited set of resources. This example provides one setting where linear programming can be applied. The technique can be used in many other accounting and business settings to help decision-makers determine optimal outcomes given limited resources.

Mathematical representation of Beacon’s business problem

business-problem

An example from management accounting

Beacon Co. is a manufacturer of washing machines. It currently sells two models of washing machines: the Arkel and the Kallex. At the start of every production cycle, Beacon must decide how many units of each washing machine to produce, given its available resources. In the coming production cycle, Beacon faces key resource constraints. In particular, it has only 3,132 hours of labour, 1,440 feet of rubber hosing, and 200 drums available.

Selling each Arkel unit earns the company a profit of $350 while selling each Kallex unit earns the company a profit of $300. At the same time, manufacturing each Arkel unit requires 18 hours of labour, 6 feet of rubber hosing, and 1 drum, while manufacturing each Kallex unit requires 12 hours of labour, 8 feet of rubber hosing, and 1 drum. Details of the relevant facts are summarised in the table “Summary of Production of Washing Machines”.

Based on these facts and the assumption that 100% of production will be sold, Beacon must decide how many units of each washing machine to produce in the coming production run to maximise profits.


Summary of production of washing machines

production-summary

Doing linear programming in Excel

The first step in linear programming is to develop a mathematical representation of the business problem and to model it on a spreadsheet. Mathematically, the problem in the example can be represented as shown in the chart “Mathematical Representation of Beacon’s Business Problem”, where X1 and X2 represent the decision variables, that is, the number of Arkel and Kallex units produced, respectively.

Next, we implement the mathematical model in an Excel spreadsheet. See the table “Spreadsheet Model” for the spreadsheet model used, and the table “Excel Formulas” for details of the formulas used in the model.

Spreadsheet model

spreadsheet-model

Excel formulas

excel-formulas

You can also download an Excel file with the Spreadsheet Model here. X1 and X2 are represented in cells C3 and D3. The values of these decision variables are unknown at the start of the problem. The unit profits expected from the sale of each unit of Arkel and Kallex are entered in cells C4 and D4. Cell E4 represents the objective function (which is to maximise profits) and calculates the total profit that Beacon can expect in this production cycle based on the corresponding production quantity and unit profit information in cells C3:D4.

Cells C7:C9 contain the amount of each production input required in the production of each unit of Arkel, while cells D7:D9 contain the amount of each production input required in the production of each unit of Kallex. Cells E7:E9 calculate the total amounts of each production input that will be used in the production cycle based on the corresponding number of units of Arkel and Kallex that are produced. Cells F7:F9 contain the total amount of each production input available to Beacon in this production cycle. Together, cells E7:E9 and F7:F9 represent the drum, labour, and rubber hosing constraint functions stated in our original mathematical model. Specifically, cells E7:E9 represent the left-hand side of the constraint functions while cells F7:F9 represent the right-hand side of the constraint functions.

Having implemented the mathematical model in the spreadsheet, we can then use Solver to find the optimal solution to the problem. Solver, as mentioned earlier in the article, is a free Excel add-in that must be installed before it can be launched (see support.office.com for instructions). Once the add-in is installed in Excel, go to Data → Analysis → Solver.

Solver parameters

solver-parameters


The Solver parameter inputs used in our example are shown in the screenshot “Solver Parameters”. In Solver, we need to define three key components of our spreadsheet model. First, we need to define an objective cell (and whether its value should be maximised or minimised). This cell should correspond to the cell in the spreadsheet that represents the objective function in the mathematical model. Second, we need to define variable cells. These cells should correspond to cells in the spreadsheet that represent decision variables in the mathematical model. Third, we need to define constraints. These cells should correspond to cells in the spreadsheet that represent the various constraint functions in the mathematical model. Further, indicating that unconstrained variables should be non-negative sets the decision variable bound where both X1and X2 are greater than or equal to 0. Given that we are executing linear programming, we select Simplex LP as the solving method in Solver.

Once these input parameters have been defined, click “Solve” to instruct Solver to solve for an optimal allocation of production between Arkel and Kallex that maximises profits.

The table “Spreadsheet Model — With Solver Solution” presents the Solver solution to our example. Solver automatically solves for the number of units of Arkel and Kallex washing machines that Beacon should produce to meet the stated objective of maximising profits. Our spreadsheet indicates that Beacon should produce 122 units of Arkel and 78 units of Kallex washing machines (cells C3 and D3), leading to an optimised profit of $66,100 (cell E4).

Spreadsheet model — with solver solution

spreadsheet-model-solver

Proving its value

Linear programming, as demonstrated by applying Excel’s Solver feature, is a viable and cost-effective tool for analysing multi-variable financial and operational problems.

In the example, it was unclear at the outset what the optimal production quantity of each washing machine was given the stated objective of profit maximisation. An intuitive response might have been to focus all production on the washing machine that provides the greater profits per unit (ie, Arkel). However, because of the resource constraints in our example, following such an intuition would not have led to a situation where profits are maximised. Instead, relying on linear programming to analyse the business problem leads to a production mix that definitively maximises profits. While this example is simple, it is reflective of many more complex real-life scenarios in which accountants face situations that require them to fulfil a variety of business objectives while contending with practical constraints. Where required, the modelling can be scaled up to deal with more complicated business problems.

Limitations of linear programming

Linear programming is one of several optimisation techniques that can be employed to determine the most efficient way to use resources. While it is a powerful technique that can be applied to many business situations, it should only be used to solve optimisation problems that involve a single linear objective function and linear constraints that cannot be violated.

There may be situations where linear programming may not be the most appropriate optimisation technique to employ. For example, where optimisation problems involve multiple objectives, nonlinear objective functions and/or constraints, or soft constraints (that can be violated) rather than hard constraints (that cannot be violated), other more appropriate optimisation techniques such as multiple objective linear programming, goal programming, or nonlinear programming should be identified and employed instead.

This article was originally published in Financial Management magazine.