Linear Programming for Business Decisions

Every business runs on limited resources: machine hours, labour, raw material, space and cash. Linear programming (LP) tells a manager how to divide those resources between competing activities so that profit is as large, or cost as small, as possible. In this guide we build LP models from plain business language, solve them graphically, and read the answers the way a manager would.

What Makes a Problem "Linear Programming"?

An LP model has three ingredients:

1. Decision variables – the quantities the manager controls, such as the number of chairs and tables to make each week.
2. An objective function – a linear expression to maximise (profit, revenue) or minimise (cost, time).
3. Constraints – linear inequalities describing the limits on resources, plus non-negativity (you cannot make a negative number of tables).

"Linear" means every term is a constant times a variable: doubling production doubles both profit and resource use. This proportionality is usually a good approximation over a sensible range of output.

The standard form of a two-variable maximisation problem is

$$ \text{Maximise } Z = c_1 x + c_2 y \quad \text{subject to} \quad a_{i1}x + a_{i2}y \le b_i, \; x \ge 0, \; y \ge 0. $$

The Corner-Point Theorem

The set of all points satisfying every constraint is called the feasible region. For LP, this region is a convex polygon, and a key theorem states that if an optimal solution exists, it occurs at a corner point (vertex) of that region. So the graphical method is simple: draw the constraints, list the corners, evaluate the objective at each corner, and pick the best.

Worked Example 1: A Furniture Workshop in Lahore

A small workshop makes chairs and tables. Each chair needs 2 hours of carpentry and 3 hours of polishing; each table needs 4 hours of carpentry and 2 hours of polishing. Each week there are 160 carpentry hours and 120 polishing hours available. Profit is PKR 1,800 per chair and PKR 3,000 per table. How many of each should be made?

Step 1: Define variables. Let \( x \) = chairs per week and \( y \) = tables per week.

Step 2: Write the objective.

$$ \text{Maximise } Z = 1800x + 3000y $$

Step 3: Write the constraints.

$$ 2x + 4y \le 160 \quad \text{(carpentry)} $$

$$ 3x + 2y \le 120 \quad \text{(polishing)} $$

with \( x \ge 0, \; y \ge 0 \).

Step 4: Find the corner points. The carpentry line meets the axes at \( (80, 0) \) and \( (0, 40) \). The polishing line meets them at \( (40, 0) \) and \( (0, 60) \). The feasible region is bounded by the tighter intercepts, so its corners are \( (0,0) \), \( (40, 0) \), \( (0, 40) \) and the intersection of the two lines.

To find the intersection, divide the carpentry equation by 2 to get \( x + 2y = 80 \). Subtract this from \( 3x + 2y = 120 \):

$$ (3x + 2y) - (x + 2y) = 120 - 80 \;\Rightarrow\; 2x = 40 \;\Rightarrow\; x = 20. $$

Then \( 20 + 2y = 80 \), so \( y = 30 \).

Step 5: Evaluate the objective at each corner.

Decision: make 20 chairs and 30 tables each week for a maximum profit of PKR 126,000. Notice that the best plan is a mix: specialising in tables alone gives less profit because it leaves polishing hours idle.

Reading the Answer Like a Manager: Shadow Prices

At \( (20, 30) \) both constraints are binding (fully used): \( 2(20) + 4(30) = 160 \) and \( 3(20) + 2(30) = 120 \). A manager will ask: "What is one extra hour of carpentry worth?"

Increase carpentry hours to 161. The new intersection solves \( x + 2y = 80.5 \) and \( 3x + 2y = 120 \), giving \( x = 19.75 \) and \( y = 30.375 \). The new profit is

$$ 1800(19.75) + 3000(30.375) = 35{,}550 + 91{,}125 = 126{,}675. $$

Profit rises by PKR 675, so the shadow price of carpentry is PKR 675 per hour. The same method shows polishing is worth PKR 150 per hour. As a check, \( 160 \times 675 + 120 \times 150 = 108{,}000 + 18{,}000 = 126{,}000 \), exactly the optimal profit, which is what duality theory predicts. If a carpenter can be hired on overtime for less than PKR 675 an hour, it pays to do so (within the range where the same constraints stay binding).

Worked Example 2: Minimising the Cost of a Feed Blend

A poultry farm near Faisalabad blends two feeds. Feed A costs PKR 60 per kg and Feed B costs PKR 90 per kg. Each kg of A gives 1 unit of protein and 2 units of energy; each kg of B gives 3 units of protein and 1 unit of energy. A batch needs at least 180 units of protein and 120 units of energy. Find the cheapest blend.

Variables: \( x \) = kg of A, \( y \) = kg of B.

$$ \text{Minimise } C = 60x + 90y $$

$$ x + 3y \ge 180 \quad \text{(protein)}, \qquad 2x + y \ge 120 \quad \text{(energy)}, \qquad x, y \ge 0. $$

With "greater than or equal to" constraints, the feasible region lies above both lines and is unbounded, but for a minimisation with positive costs the optimum is still at a corner.

Corners. The protein line meets the x-axis at \( (180, 0) \); this point gives energy \( 2(180) = 360 \ge 120 \), so it is feasible. The energy line meets the y-axis at \( (0, 120) \); protein there is \( 3(120) = 360 \ge 180 \), so it is feasible too. For the intersection, substitute \( x = 180 - 3y \) into the energy equation:

$$ 2(180 - 3y) + y = 120 \;\Rightarrow\; 360 - 5y = 120 \;\Rightarrow\; y = 48, \quad x = 180 - 144 = 36. $$

Costs.

• At \( (180, 0) \): \( C = 60 \times 180 = 10{,}800 \)
• At \( (0, 120) \): \( C = 90 \times 120 = 10{,}800 \)
• At \( (36, 48) \): \( C = 2{,}160 + 4{,}320 = 6{,}480 \)

Decision: blend 36 kg of A with 48 kg of B for a minimum cost of PKR 6,480 per batch. Using a single feed costs PKR 10,800, so smart blending saves 40%.

Check: protein \( 36 + 144 = 180 \) and energy \( 72 + 48 = 120 \). Both requirements are met exactly, with no expensive surplus.

Beyond Two Variables

Real businesses have hundreds of products and constraints. These are solved with the simplex method (developed by George Dantzig in 1947) or interior-point algorithms, using software such as Excel Solver, LINGO, R's lpSolve package or Python's scipy.optimize.linprog. The modelling skill, however, is the same as above: define variables, write the objective, translate every business rule into a linear constraint.

Typical applications include production planning, transporting goods from factories in Karachi and Lahore to warehouses at minimum freight cost, assigning staff to jobs, portfolio allocation under risk limits, and splitting an advertising budget across media to maximise reach.

Did You Know?

• The Soviet economist Leonid Kantorovich developed early LP ideas in 1939 for plywood production planning and later shared the 1975 Nobel Prize in Economics with Tjalling Koopmans.
• Airlines use LP and its integer extensions to schedule crews; savings can run into millions of dollars a year.
• Shadow prices tell managers which constraint is the real bottleneck, often more valuable than the optimal plan itself.

Key Takeaways

• An LP model has decision variables, a linear objective and linear constraints.
• The optimum always lies at a corner point of the feasible region, so evaluate every corner.
• Binding constraints are the bottlenecks; their shadow prices show the value of one more unit of resource.
• Minimisation problems with "at least" constraints are solved the same way, with the region lying above the lines.
• Software handles large models, but correct formulation is the skill that matters.

Struggling with an LP formulation, simplex table or sensitivity analysis in your assignment? Send your question to Amathify's subject experts and PhD scholars via WhatsApp or the Ask a Question form for clear, step-by-step solutions.