Algorithms For Dummies

Using Linear Functions as a Tool

This  section  shows  how  to  address  a  problem  where  someone  transforms  the 

objective (the representation of cost, profit, or some other quantity to maximize or 

minimize  subject  to  the  constraints)  and  constraints  (linear  inequalities  derived 

from the application, such as the limit of a 40-hour work week) of that problem 

into linear functions. The purpose of linear programming is to provide an opti-

mum numeric solution, which could be a maximum or a minimum value, and the 

set of conditions to obtain it.

This definition may sound a little bit tricky because both math and some abstrac-

tion is involved (objective and constraints as linear functions), but things become 

clearer after considering what a function is and when we can determine whether 

a function is linear or not. Beyond the math jargon, linear programming is just a 

different point of view when dealing with algorithmic problems, where you trade 

operations and manipulations of data inputs with mathematical functions and you 

perform calculations using a software program called an optimizer.

You can’t use linear programming to solve all problems, but a large number of 

them fit linear programming requirements, especially problems requiring opti-

mization using previously defined limits. Previous chapters discuss how dynamic 

programming is the best approach when you need to optimize problems subject to 

constraints. Dynamic programming works with problems that are discrete, that is 

the  numbers  you  work  with  are  whole  numbers.  Linear  programming  mainly 

works with decimal numbers, although special optimization algorithms are avail-

able  that  provide  solutions  as  integer  numbers  (for  instance  you  can  solve  the 

---

CHAPTER 19