Linear Programming Basics: A Case at Shoe Manufacturer

Do you like Linear Programming, or do you think it is the worst class ever? I remember one hour of my matriculation class where a Proffesor said:

“Ok guys.. Today, we are going to learn about Linear Programming again! 🙂 “

…and class stares in shock.. 😯 😯 😯 …and I ask myself:

“Where is my brain? Where is my brain????? Oh my brain, please remember Linear Programming back!!  😦 “

I have a huge passion in engineering, but I fail to enjoy learning math 😀 . Mathematics is one of the most interesting subject provided you understand it. If you learn it with your interest then it become like a game but if you lack the interest then it very tough to learn. The posting that I have given below is just a simple math problem of linear programing  application in the real world…hope you enjoy it.. glory engineering!!

 

***

 

Since at least the time of Adam Smith and Cournot, economic theory has been concerned with maximum and minimum problems (Dorfman, et al., 1958). Maximum and minimum problems occur frequently in pure and applied economics. Firms try to maximize profits or minimize costs (Gale, 1960), allocating scarce resources among competing ends (Nautiyal, 1988).

At any time, an economy has in its control given quantities of various factors of production, and a number of activities to which those factors can be applied. Those factors of production can be allocated to the different activities in many ways. The most frequent problem in the theory of production or in welfare economics is how to allocate the resources available in any given situation in the “best” way.

In recent years, to solve resource allocation problems, product mixes and other resource optimization, operation research (OR) techniques such as linear programming, have greatly assisted in better decision-making, resulting in improved profit, reduction of losses and better utilization of resources.

 

Linear Programming

The manager’s duty is to manage resources: raw materials, human beings, production facilities, markets for products and available funds. The challenge is to optimize the return on these resources (Baldwin, 1984). So, to optimize the use of such scarce resource linear programming models have been applied extensively since their development by George B. Dantzig in 1947 as a technique for planning the diversified activities of the USA Air Force (Dorfman, et al., 1958).

The linear programming model has been defined as an interactive mathematical technique for finding the best use of resources subject to constraints (Dunn & Ramsing, 1981). Mathematically, formulation of resource allocation in terms of linear problems requires a linear function of the number of variables to be maximized (or minimized) when those variables are subject to a number of constraints in the form of linear inequalities (Dorfman, et al., 1958). However, we know that economic relationships are frequently nonlinear. The u-shaped cost curves and the total revenue curves in imperfect competition (Nautiyal, 1988) are examples of nonlinear relationships. In such situations, many nonlinear economic relationships can be approximated by a number of linear segments and modeled for solution through linear programming.

There are five essential conditions in a problem situation for linear programming to pertain (Anderson, et al., 1997).

1. First, there must be limited resources (such as a limited number of workers, equipment, finances, and material); otherwise there would be no problem.
2. Second, there must be an explicit objective (such as maximize profit or minimize cost).
3. Third, there must be linearity (two is twice as much as one; if it takes three hours to make a part, then two parts would take six hours, and three parts would take nine hours).
4. Fourth, there must be homogeneity (the products produced on a machine are identical, or all the hours available from a worker are equally productive).
5. Fifth is divisibility: Normal linear programming assumes that products and resources can be subdivided into fractions. If this subdivision is not possible (such as flying half an airplane or hiring one-fourth of a person), a modification of linear programming, called integer programming, can be used.

Linear programming is a method often used to solve large, complicated problems. These problems often require a manager determine how to use the company’s limited resources most efficiently. In order to see how linear programming is used to solve such problems, let’s investigate a problem experienced at the PT Indonesia Murni (IM). IM problem is just a fraction of the size of those actually encountered in the real world.

 

Understanding the Problem

IM is one of few shoe manufacturers in Indonesia. IM wants to maximize the company’s profits in one line from two brands of sport shoe, MS78 and MD Runner.

After IM pays all of the expenses incurred to manufacture and deliver a product (e.g., materials, overhead, labor cost), IM earns $1 profit on each pair of MS78 and $0.9 profit on each pair of MD Runner. The steps in manufacturing the shoes include cutting the materials on a machine and having workers assemble the pieces into shoes.

Decision variables represent a quantity that a manager can change, for example: the number of shoes to be made.

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

IM goal is to make the most money or maximize their profits. Using MS and MD, write a function to model the profit.

 

Profit = 1MS + 0.9MD

 

This function is called the objective function. The objective function is the equation that represents the goal of either maximizing profit or minimizing cost.

The number of machines, workers, and factory operating hours put constraints on the number of pairs of shoes that the company can make. Constraints are limitations created by scarce resources (time, equipment, etc.). They are expressed algebraically by inequalities. IM has the following constraints. There are 12 machines that cut the materials, 250 workers in pre-sewing, sewing and assembling lines that assemble the shoes, and the assembly plant works a 40 hour week.

 

A System of Inequalities: Constraints

Machine Cutting Constraint Inequality

Each hour, each cutting machine can do 50 minutes of work. How many minutes of work can 12 machines do in a 40 hour work week?

 

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

Each pair of MS78 requires 5.1 minutes of cutting time while MD Runner requires 4.5 minutes. The mathematical model representing the constraint of the cutting machines is

5.1MS + 4.5MD ≤ 24000 minutes

Why do we use ≤ 12000 minutes instead of = 12000 minutes? Machines can only work 12000 minutes per week, never more.

 

Worker Assembly Constraint Inequality

How many minutes of work can 250 assembly workers do in a week?

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

 

Each worker takes 2 hours to assemble a pair of MS78 and 2 hours to assemble a pair of MD Runner. Write the constraint inequality modeling the amount of time it takes to assemble the shoes for the week.

 

2MS + 2MD ≤ 10000 hours

 

Other Constraints

The number of pairs of shoes that IM manufactures is never negative, but could possibly be zero. Why? The default lower bounds on all variables are zero. People tend to forget this build-in default. If no negative (or negative infinite) lower bound is explicitly set on variables, they can and will take only positive (zero included) values. Therefore, two more constraints on our variables, MS and MD are,

 

MS ≥ 0 and MD ≥ 0

 

Graphing a System of Inequalities – 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. Our feasible region is the shaded region represents the set of points which satisfy all of the constraints. The graph of this system of constraint inequalities appears in the following figure (Figure 1).

 

In this situation, one of the vertices of this feasible region will provide the optimal choice, so we must first consider all of the corner points of the feasible region and find which pair of coordinates makes us the most money.

 

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

IM problem is an example of what are called “product-mix” problems, and it occurs whenever a company produces more than one item. Through the application of linear programming techniques to the analysis of this case, we will learn how to apply the solution of a system of linear inequalities to solve geometrically a real-world problem involving two decision variables. One way to extend the basic problem is to consider problems involving more than two decision variables. Although the geometric technique is no longer appropriate, the problem is still solvable. If the problem can be formulated, software packages can them be used to determine the optimal solution.

Currently, in the business world, to find the most profitable product-mix, quantitative methods and OR-techniques are helpful tools to the management continuously facing the problem of maximizing profits or minimizing costs, under different sets of restrictions like sales possibilities, production capacity, financing, etc.

OR, like linear programming models, provides, besides the optimal solution, a set of dual evaluators of the limited resources. This set of shadow prices directs the attention of managers to the points where the removal of bottlenecks will positively affect the profit as a whole. on the other hand, LP-packages also answer the question: What if the sets of initial assumptions are modified?

 

 

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.