What Is Linear Programming? A Simple Case Study from a Shoe Manufacturer

Have you ever wondered how businesses decide the best way to increase profits or reduce costs? It’s a question that economists have been trying to answer for centuries. As early as the time of Adam Smith and Cournot, economic theory focused on solving maximization and minimization problems—a concept that remains crucial in both modern business strategy and everyday decision-making.

Think of an economy like a giant puzzle made of different pieces: labour, money, materials, and time. Each of these can be used in different ways, but the big question is: how do you put them together in the most efficient way? That’s the heart of production theory or welfare economics—figuring out how to make the best choices with what you’ve got.

These days, we’ve got some tools to help. One of them is called operations research (OR), and techniques like linear programming help companies solve resource allocation problems, optimize product mixes, and improve overall efficiency. As a result, they’re able to increase profits, reduce losses, and get more value.

What Is Linear Programming?

In any business, managing resources effectively is a key responsibility of a manager. These resources include raw materials, labor, production facilities, capital, and markets. The big challenge is to optimize the return on these resources (Baldwin, 1984). To solve this challenge, businesses and organizations have been using a technique called Linear Programming (LP)—a method first developed by George B. Dantzig in 1947 to help plan the complex operations of the U.S. Air Force (Dorfman, et al., 1958).

How Linear Programming Works

Linear programming is an interactive mathematical technique for finding the best use of resources subject to constraints (Dunn & Ramsing, 1981). The goal is usually to either maximize profits or minimize costs.

In a linear programming model:

• You create a linear function to represent your objective (like profit or cost).
• This function depends on several variables (like number of units produced).
• You then apply constraints, written as linear inequalities, to reflect real-world limits—such as budget, labor hours, or material supply.

Even though many economic situations are actually nonlinear—like U-shaped cost curves or revenue curves in imperfect competition (Nautiyal, 1988)—these can often be approximated using linear segments. That’s why linear programming is still a powerful and practical tool.

5 Key Conditions for Linear Programming to Work

For linear programming to be used effectively, five basic conditions must be met (Anderson, et al., 1997).

1. Limited Resources: There must be constraints—like limited materials, labor, money, or machines. If there are no limits, there’s no problem to solve.
2. Clear Objective: You must have a specific goal, such as maximizing profit or minimizing cost.
3. Linearity: Relationships must be linear. For example, two is twice as much as one; if it takes 3 hours to make a part, then two parts would take 6 hours, and three parts would take 6 hours.
4. Homogeneity: All units of output are identical. Every machine produces the same product, and each hour of work is equally productive.
5. Divisibility: The model assumes that resources and products can be divided into fractions. If not (e.g., flying half an airplane or hiring one-fourth of a person), a modification of linear programming like integer programming is needed.

Linear programming is a method used to solve complex problems, especially when a company has limited resources. In manufacturing, it helps factory managers decide how to best use limited resources—such as machines, labor, and working hours—to produce the most products or achieve the highest profit without waste. To better understand linear programming, let’s look at a case study from PT Indonesia Murni (IM) below.

Understanding Linear Programming in Manufacturing

IM is one of shoe manufacturer in Indonesia. The company aims to maximize profit from two product lines: the MS78 and the MD Runner sports shoes.

After covering all production and delivery costs (materials, labor, and overhead), IM earns a profit of $1 per pair of MS78 and $0.90 per pair of MD Runner. The production process involves cutting materials with specialized machines and assembling the shoes through manual labor.

To make informed decisions, the company defines decision variables:

• MS = number of pairs of MS78 produced each week
• MD = number of pairs of MD Runner produced each week

The objective function, which represents the goal of maximizing profit, is:.

Profit = 1MS + 0.9MD

This function guides the company’s production strategy. However, IM must operate within specific resource constraints:

• Only 12 cutting machines are available,
• There are 250 workers across pre-sewing, sewing, and assembly lines,
• The factory operates on a 40-hour workweek.

These constraints—expressed as inequalities in linear programming models—limit the number of shoes the company can produce. By applying linear programming, IM can identify the optimal production quantities that align with resource limits while achieving maximum profitability.

A System of Inequalities: Constraints

1. Machine Constraint

Each cutting machine works 50 minutes per hour. So in a 40-hour week, 12 machines can operate for:

12 machines x 50 min/hr x 40 hr/wk = 24000 min

Each pair of MS78 takes 5.1 minutes, and each MD Runner takes 4.5 minutes to cut. So the constraint is:

5.1MS + 4.5MD ≤ 24000 minutes

We use “≤” instead of “=” because machines cannot work beyond their limit of 24,000 minutes.

2. Worker Constraint

With 250 workers working 40 hours a week:

250 workers x 40 hr/wk each = 10000 hr/wk total.

Each pair of MS78 and MD Runner takes 2 hours to assemble. So the constraint becomes:.

2MS + 2MD ≤ 10000 hours

3. Non-Negative Constraints

IM cannot produce a negative number of shoes. So, we also include:

MS ≥ 0 and MD ≥ 0

These constraints ensure that the number of shoes produced is either zero or a positive number.

Visualizing the Constraints: The Feasible Region

Our system of constraint inequalities is:

1. 5.1MS + 4.5MD ≤ 24000
2. 2MS + 2MD ≤ 10000
3. M ≥ 0
4. X ≥ 0

Using the equations and inequations generated above, we can graph these, to find a feasible region — the area where all constraints are met. The optimal solution will lie at one of the corner points of this region (Figure 1).

Searching for the Optimal Solution

The best solution for this problem gives IM a maximum profit. The process of determining this best solution is called optimizing, and the solution itself is called the optimal solution.

To determine the optimal solution, there are many strategies you could use. Now, to verify the solution non-geometrically. Since we know the optimal solution has to occur at one or more corner points, we make a table listing all the corner points and evaluate the objective function at those points.

 

After considering all of the options from that table, IM must make 3000 pairs of MS78 and 2000 pairs of MD Runner each week in order to make the most money. It is the best combination to optimize profits for IM. This is a fairly simple problem, but it is easy to see how this type of organization can be useful and very practical in the industrial world.

 

Conclusion

The IM problem is an example of a “product-mix” problem, which happens when a company makes more than one type of product. By using linear programming techniques, we can learn how to solve a system of linear inequalities and apply it geometrically to real-world problems with two decision variables. If the problem involves more than two variables, the geometric method isn’t suitable anymore, but the problem is still solvable. As long as it’s formulated correctly, software packages can then be used to find the optimal solution.

In today’s business world, quantitative methods and operations research (OR) techniques are super helpful for managers trying to figure out the most profitable product mix. These tools help with maximizing profits or minimizing costs while dealing with constraints like sales limits, production capacity, and available funding.

Linear programming not only give the optimal solution but also provide shadow prices, which show the value of limited resources. These prices help managers identify bottlenecks, where fixing issues could boost overall profits. Additionally, LP software can also answer “what if” questions when the initial assumptions or constraints change.

 

 

References:

---

Anderson, D. R., Sweeney, D. J., Williams, T. A., & Martin, R. K. (1997). An introduction to management science: Quantitative approaches to decision making (8th ed.). St. Paul, Minnesota: West Publishing Company.

Baldwin, R. F. (1984). Operations management in the forest products industry. San Francisco: Miller Freeman Publications.

Dorfman, R., Samuelson, P. A., & Solow, R. M. (1958). Linear programming and economic analysis. New York: McGraw-Hil.

Dunn, R. A., & Ramsing, K. D. (1981). Management science: a practical approach to decision making. New York: Macmillan.

Gale, D. (1960). Theory of linear economics models. New York: McGraw-Hill

Nautiyal, J. C. (1988). Forest economics: principles and applications. Toronto: Canadian Scholar’s Press Inc.