Operations Madness – How to write the simplest LP

Linear Programming (LP)

Linear programming (LP) is a mathematical optimization tool that translates a problem into an objective function. The goal is usually to find the combination of values that either minimizes or maximizes the value of the function.

We deal with linear problems because the objective function is linear, the unknowns are linear, and the constraints are linear equalities (or inequalities). In layman’s terms: we will not multiply decision variables in the function or in the constraints.

To get to grasps with LP:

1. sets as the items in our problem. Usually a nominal variable.
2. parameters as numeric attributes of each set (or intersection). It may refer to costs and prices, or (in the combination of sets) distances or demand estimates between clients and shops.
3. decision variables, as the elements under our control whose value determines the solution of the model. The decision variables are often the quantities in a “how many..?” problem.
4. objective function as the goal of the optimization problem. Optimizing a solution involves maximizing or minimizing a quantity like e.g. the debt to equity ratio, or the possible size of a production run.
5. constraints delimiting the area of feasible solutions e.g. like the cost of borrowing, or the number of work-hours available in a day.

The solution to a LP is a value that satisfies all constraints and finds an optimal value for the objective function. There are ways of solving these problems with pen and paper, mainly: (1) geometric solutions sketching out the area of possible solutions, and (2) finding the optimal point at a corner of the solution region; pivoting values in the simplex method.

Since we spent the last century building calculators, there are easier options and our spreadsheet editors are entirely capable of solving small LPs. The solver is an add-on to MS Excel, Google Sheets, and Apple Numbers. It is free to use and very powerful: the only word of warning is to understand what decision variables are needed in the solution; what is the goal (the objective function); and which constraints apply to the problem.

Solving a LP may yield three different results:

1. No solution is feasible when there is no combination of decision variables satisfying the constraints;
2. Unbounded solution, pointing at a function (e.g. maximize profit) that can increase or decrease without violating any constraint (e.g. by selling an infinite amount of units);
3. one or multiple feasible solutions where there is more than one possible combination of variables yielding the maximum (or minimum) value for the objective function.

Please note that decision variables are allowed to take any continuous value. It is not always practical, since some quantities are best left whole (e.g. you need to determine the number of workers in a shift, and you cannot have 1.33 Samanthas). In case the decision variables are only allowed integer values we deal with integer linear programming.

In the example below, the LP is not an integer LP because the variables can take any values. This is due to the fact that kilos can be divided into grams, and the quantities are very close to full kilos.

---

Example: The Gluten Tag Bakery.

Jaco just opened a bakery. He booked ±16 Kg of bread, and plans to use 10 Kg of flour for the production. He plans to sell his bread at 10.00 EUR/Kg of flour (above market prices), and estimates his baking costs at 7.00 EUR per Kg of flour. He is evaluating three different suppliers of flour.

The set for this problem is given by the flour involved A, B, or C. The parameters are the individual value attributes for each item in the set (content and cost).

The decision variables will be how much flour to use. The solution depends on the quantity in kilos of brands A, B, and C. Let’s call these X_A, X_B, and X_C.

The objective function is to maximize profit. Profit is revenue minus cost, and we know the revenue from the sale:

Revenue = 10 Kg * 10 EUR/Kg = 100,00 EUR

The cost, however, depends on the 7.00 EUR cost per kg and the type and quantity of flour (e.g. baking bread using Brand A flour costs 7.00 + 1.1 = 8.1 EUR/kg)

Baking Cost = 8.1 * X_A + 8.6 * X_B + 7.9 * X_C

Thus our objective function is to maximize:

Profit = 100.00 – (8.1 * X_A + 8.6 * X_B + 7.9 * X_C)

However, we have constraints from the recipe. These are given by the share of fibers and protein in the mix, and the total amount of flour we are planning to use.

We want to bake 10 kilos of bread:

X_A + X_B + X_C = 10

The mix should not exceed 4.5% of fibers in the 10 kilos total weight:

.02 * X_A + .03 * X_B + .05 * X_C ≤ 0.045 * 10

The mix should have at least 11% of protein in the 10 kilos total weight:

.10 * X_A + .14 * X_B + .09 * X_C ≥ 0.11 * 10

All the weights are parameters given by the initial problem and represent the contribution of each brand to the final mix.

Since this is a mathematical formulation we need to specify that weight cannot be negative (bread cannot have negative mass). The non-negativity of all variables is always an implicit condition of linear programming.

X_A ≥ 0; X_B ≥ 0; X_C ≥ 0

In this case the solution can be found on Google Sheets at this public link. The optimal solution involves mixing 4 Kg of Brand B flour and 6 Kg of Brand C flour.

The profit is a whopping 18.20 EUR.

---

For the wisdom of the ancients, there is the excellent Bradley, Stephen P.; Hax, Arnoldo C.; Magnanti, Thomas L. (1977) Applied Mathematical Programming. Addison Wesley Publishing Company, available online at the Internet Archive, or in excerpts at the MIT course website. Chapter 1 of this book has everything you need to understand LP

For a more thorough introduction, see: Luenberger, D. G., & Ye, Y. (2015). Linear and nonlinear programming. In International series in management science/operations research/International series in operations research & management science. https://doi.org/10.1007/978-3-319-18842-3