Algorithms For Dummies

 

»

Revenue in USD for each product: x=15, y=25

 

»

Production rate per hour: x=50, y=40

 

»

Daily demand per product: x=300, y=200

---

362

 

   

  PART 5 

 Challenging Difficult Problems

In essence, the business problem is to decide whether to produce more x, which is 

easier to assemble but pays less, or y, which guarantees more revenue but less 

production. To solve the problem, first determine the objective function. Express 

it as the sum of the quantities of the two products, multiplied by their expected 

unit revenue, which you know you have to maximize (only if the problem is about 

costs do you have to minimize the objective function):

f(x,y) = 15 * x 

+ 25 * y

This problem has inequalities, which are bounded by x and y values that have to 

hold true to obtain a valid result from the optimization:

0 <= x <= 300

0 <= y <= 200

In fact, you can’t produce a negative number of products, nor does it make sense 

to produce more products than the market demands. Another important limita-

tion is available time, because you can’t exceed eight hours for each work shift. 

This means calculating the time to produce both x and y products and constrain-

ing the total time to less than or equal to eight hours.

x/40 

+ y/50 <= 8

You can represent functions on a Cartesian plane. (For a refresher on plotting func-

tions, consult 

http://www.mathplanet.com/education/pre-algebra/graphing- 

and-functions/linear-equations-in-the-coordinate-plane

.) Because you can 

express everything using functions in this problem, you can also solve the linear 

programming problems as geometry problems on a Cartesian coordinate space. If 

the problem doesn’t involve more than two variables, you can plot the two func-

tions and their constraints as lines on a plane, and determine how they delimit a 

geometric shape. You’ll discover that the lines delimit an area, shaped as a poly-

gon, called the feasible region. This region is where you find the solution, which 

contains all the valid (according to constraints) inputs for the problem.

When the problem deals with more than two variables, you can still imagine it 

using lines intersecting in a space, but you can’t represent this visually because 

each input variable needs a dimension in the graph, and graphs are bound to the 

three dimensions of the world we live in.

At this point, the linear programming algorithm explores the delimited feasible 

region in a smart way and reports back with the solution. In fact, you don’t need 

to check every point in the delimited area to determine the best problem solution. 

Imagine  the  objective  function  as  another  line  that  you  represent  on  the  plane 

(after all, even the objective function is a linear function). You can see that the 

---

CHAPTER 19