Decision Support Systems For Business Intelligence
by Vicki L. Sauter

Modeling Insights: Linear Programming

To understand algorithms and their use, let us consider a specific problem.

An MIS Club plans to sell two special fruit baskets for the upcoming holiday season.  Fruit Basket A contains 3 apples, 4 oranges and 1 honeydew melon and sells for \$8.  Fruit Basket B contains 4 apples, 3 oranges and 2 honeydew melons and sells for \$12.  The amount of each fruit available and their costs to the MIS Club are shown in the table below.  If it is assumed that the MIS Club can sell all the baskets it makes, how many of each one should they make?

 Quantity Available Cost per Piece Apple 160 \$0.30 Orange 180 \$0.20 Melon 60 \$1.20

The first step is to represent the problem mathematically.  In this case, we will have two variables, x and y, where x represents the number of Fruit Basket A to make and y represents the number of Fruit Basket B to make.  We know that each Fruit Basket A sells for \$8 and each Fruit Basket B sells for \$12, but in order to know how much profit we will make, we must compute the costs of each basket.  Basket A contains 3 apples @ \$ .30, 4 oranges @ \$ .20 and I melon @ \$1.20, so it costs \$2.90 to make up the basket (if we assume the actual basket is free).  Hence, the net profit from Basket A is \$5.10.  Using a similar method, we can find that the net profit from Basket B is \$7.80.  Hence, our objective is to:
maximize 5.10 x + 7.80 y

However, there are constraints dictating the availability of fruits which must be met.  Using the quantities above, they are
Apples:            3x + 4y ? 160
Oranges:          4x + 3y ? 180
Melons:            1x + 2y ?   60

Conceptually, the algorithm for solving this problem looks at possible values for x and y and selects the one that maximizes our objective.  Consider the graph below.

The algorithm “knows” to look for the feasible combinations of the two types of Fruit Baskets, as shaded in the graph.  Further, it “knows” that the best combination is going to be one of the four “extreme” or corner points highlighted above.  The algorithm evaluates an extreme point with regard to the objective (5.10x + 7.80y).  It then looks at the adjacent corners to determine if one of them give a better solution.  If so, the algorithm moves to that new point and begins again.  In essence, the algorithm moves from corner to corner, always improving the value of the objective.  With large problems, the process is important because one can have many variables and many constraints resulting in millions of corner points.  Since the algorithm follows a systematic approach to improvement, it ends up checking only a small percentage of the possible points.  In this case, it is the combination of 36 Fruit Baskets of Type A and 12 Fruit Baskets of Type B, giving a profit of \$277.20 to the MIS Club.

Page Owner: Professor Sauter (Vicki.Sauter AT umsl.edu)