Introduction to Industrial Engineering

By Jane M. Fraser

Chapter 10

Operations research and other mathematical methods


Return to the Table of Contents.

10.4 Deterministic models

IEs are responsible for efficiency, including the efficient use of time and resources. You already know from calculus class how to find the maximum or minimum of a function and calculus is one tool that IEs use. However, IEs often need to maximize or minimize a linear function, which sounds easy, but finding the solution isn’t easy when there are many variables and also some constraints. The following is an example of such a problem.

Dairy cattle have various nutrient requirements, such as protein, calcium, and potassium, that can be met by different types of feed, such as alfalfa, hominy, and corn cobs. The dairy farmer wants to mix a feed for the dairy cows that will meet the nutrient requirements at the minimum cost. I have created a very simplified version of the Diet Problem as applied to feeding dairy cattle. The following table gives the nutrient content (protein and potassium) of certain feeds (alfalfa, hominy, and corn cobs), as well as the nutrient requirement for protein and potassium (as a percent of the feed) and the cost of alfalfa, hominy, and corn cobs (in $/ton).

Alfalfa Hominy Corn cobs Required
Protein 28.0 11.9 3.0 15.0
Potassium 0.26 0.65 0.06 0.25
Cost 160 60 0

For example, alfala is 28% protein, 0.26% potassium, and costs $160 per ton. Alfalfa is a good source of protein and a medium source of potassium, but it is expensive. Hominy is a medium source of protein and a good source of potassium, and it is cheaper than alfalfa. Corn cobs are not a good source of either protein or potassium, but since they are otherwise a waste product, they are free. With some thought, you can see that the optimal mix will probably need alfalfa to meet the protein requirement, hominy to meet the potassium requirement, and corn cobs to keep the cost down.

We want to determine how to mix the feed, that is, what fraction should be alfalfa (A), hominy (H), and corn cobs (C). We will use linear programming to solve this problem, by expressing the situation as minimizing a linear objective function (cost) subject to linear constraints (protein and potassium). We also know that A+H+C=1.

Here is the linear programming formulation:

Minimize 190 A + 60 H

s.t. 19.3 A + 11.9 H + 3 C &ge 15

.28 A + .65 H + .06 C &ge .25

A + H + C = 1

This model is an example of a linear programming model. We can solve it in Excel (although there are better tools for solving LP models). Because this model has only two decision variables (X1 and X2) we will first solve this one graphically. You won’t usually solve an LP model graphically, but we will do it this time to help you understand LP models better.

Each LP model has an associated problem, called the dual problem, which gives us more useful information. First, let’s add units or dimensions to all the quantities in the model.

We create the dual problem by transposing the matrix of coefficients in this set of inequalities; what was a row becomes a column and vice versa. We get this dual model; with each number I retained the units associated with it. I created a decision variable for each row in the original problem, Y1 through Y6.

If you look closely at the first inequality, you can figure out that Y1 must have units of $/protein and so forth. Here is the dual model with units added. [complementary slackness]

Now let’s solve the original LP model with Excel, using the Solver Add-In.

I used Excel to solve this problem because no matter where you work, you will probably have Excel available. However, if you use LP a lot in your work, you will want to have your company buy a computer package that solves LPs.

Commercial packages are available to solve the nutrition problem for animals, for exampe, Feedsoft, SEIFormulator, and TailoredDiet.

This problem is an example of how industrial engineers use mathematics to promote efficiency. In this case, we helped the family use their resources and time efficiently to maximize their revenue from their crafts. This model is an example of an LP model, or, more broadly, an example of a deterministic optimization model. “Deterministic” means the model has no probabilities and “optimization” means we found the optimal, or best, solution.

An LP model is just one type of deterministic optimization model. Actually, we were lucky that we got an integer solution for this problem because the family really can’t sell, for example, 1/2 of a puppet; an LP where the decision variables must be integers is called an integer programming model (IP).

Industrial engineers must be able to recognize situations where a deterministic model can be applied, create an appropriate model, and solve the model using an appropriate tool. The following list describes situations where a deterministic optimization model might be useful:

Use Brazilian bulb article.

For any real world problem that you can’t solve just by looking at it and thinking hard, you will need to use a computer package. Widely used computer packages for deterministic optimization include:

These computer packages are general purpose, that is, they will solve any linear programming problem and some deterministic optimization problems. If you develop a model that must be solved repeatedly with different data (for example, the daily production schedule), you will probably want to develop (with the help of skilled computer programmers) a specialized computer program adapted to efficiently solve exactly that type of problem. Such a specialized program will usually be faster, often much faster, because the program will take advantage of the structure of the problem.

Some deterministic optimization problems, however, are just so hard that even the best specialized program may take close to forever to find the best solution.

In section 10.4 we looked at a small routing problem, which was an example of the Traveling Salesman Problem (TSP). A driver who has to deliver packages wants to pick the best route, that is, the sequence in which to deliver packages. The driver has to make loop starting at A and visiting B, C, and D before returning to A. The table gives the distances between each site that must be visited.

A B C D
A - 5 4 3
B 5 - 6 8
C 4 6 - 4
D 5 8 4 -

As I said in section 7.5, this small problem can be solved by looking at all the different orders to find the smallest (it has length 18). However, the number of possible solutions to a TSP with n nodes is n! and n! gets very large very fast. An algorithm for a particular type of problem is a method to find the optimal solution for that class of problems; it is guaranteed to find the optimal solution, but it may take a very long time to do that.

If you have a problem, like the TSP, that is really hard to solve, you may need to be satisfied with a good solution that you can’t prove is the optimal solution. A heuristic for a particular type of problem is a method to find a good solution for that class of problems; it is not guaranteed to find the optimal solution. A good heuristic finds a good solution in a reasonable amount of time.

If you need to determine the route for a truck driver 6 A.M. based on data available at 6 P.M. the previous day, your computer program can’t take more than 12 hours to solve the problem. Stephan Mertens has provided some interactive versions of well known heuristics such as the nearest neighbor heuristic and the insertion heuristic.

IEs can specialize in Operations Research, which involves the study of particular classes of problems, such as TSPs. Operations Research specialists devise better algorithms and heuristics for solving problems. They also try to find specific methods to solve problems that occur in special applications. As described in this article from InformationWeek, UPS uses operations research to optimize its delivery network.