Optimization and Decision Making: How to solve Linear programming problems.

In the realm of decision-making, optimization plays a pivotal role making (Albright & Winston, 2020). Linear programming, particularly the Simplex Method, is a fundamental technique for optimizing a given objective function subject to a set of constraints (Bradley, Hax y Magnanti ,1977; Dantzig, G., 1987). This article will guide you through solving a linear optimization problem using both graphic and mathematical method and a simplex method with solver from excel.

?

Example Problem: Production Optimization

Let's consider a production optimization problem for a manufacturing company that produces two products, A and B. The company aims to maximize its profit while adhering to resource constraints and market demands. Each unit of product A requires 2 units of resource 1 and 1 unit of resource 2, while each unit of product B requires 1 unit of each resource. The company has a maximum of 100 units of resource 1 and 80 units of resource 2 available. Additionally, market demand limits the production of product A to 40 units.

Objective: Maximize profit

?Variables: x1 (units of product A), x2 (units of product B)

Objective Function: Maximize Z = 40x1 + 30x2

Constraints:

? 2x1 + x2 <= 100 (resource 1)

? x1 + x2 <= 80 (resource 2)

? ?x1 <= 40 (market demand for A)

? ?x1, x2 > 0 (non-negativity)

Solving the Problem

Graphically we have:

?In the graph, we plot the constraints to visualize the feasible region and identify the optimal solution. The blue line represents the first constraint, The red line represents the second constraint, and the green vertical line represents the market demand constraint.

The shaded grey area represents the feasible region where all constraints are satisfied simultaneously. This region is bounded by the lines representing the constraints and the axes.

The black dot marks the optimal solution at ??1=20 and ???2=60. The optimal solution is where the objective function ?? is maximized, given the constraints. The maximum profit ?? at this point is 2600 = 40(20) +30(60).

?

Note that you can solve the system of two equations with two variables:

2x1 + x2 <= 100 (resource 1)

? x1 + x2 <= 80 (resource 2)

By multiplying the first -1 you obtain -2x1 - x2 = -100 and then adding it up to the second equation x1 + x2 = 80 you obtain that x1 = 20 (satisfying also the third constraint) and therefore x2 = 60

Finally, you can use SOLVER from excel using the simplex method.

Set up Solver:

1. Go to the Data tab and click Solver.
2. Set Objective: Select cell with the objective function (B4)
3. To: Select Max.
4. By Changing Variable Cells: Select cells B2 and B3 (decision variables).
5. Add constraints: Click Add and set up the constraints: Constraint 1: B5 <= 100 Constraint 2: B6 <= 80 Constraint 3: B2 <= 40 Ensure all variable cells are non-negative.
6. Solve the problem: Click Solve, then OK to keep the solutio

Solver will find the optimal solution:

Hint: if you don’t have solver add-in, you could go to Options and install it.

P.S. In our next newsletter we will introduce risk by proposing and solving a Foreign Portfolio Investment Optimization Problem using Markowitz's framework (Markowitz,1952).

REFERENCES

Bradley, Hax y Magnanti (1977): “Applied Mathematical Programming” recuperado de https://web.mit.edu/15.053/www/AMP.htm

Dantzig, George (1987).?"Origins of the simplex method". In Nash, Stephen G. (ed.).?A History of Scientific Computing. Association for Computing Machinery. pp.?141–151.

Markowitz, H. (1952). PORTFOLIO SELECTION. The Journal of Finance, 7(1), 77–91. https://doi.org/10.1111/J.1540-6261.1952.TB01525.X