Copyright

Using Linear Programming to Solve Problems

Instructor: Kristina Dougherty

Kris has taught science, math, and conservation to high school, college and graduate students, and she has a Ph.D. in wildlife ecology and a J.D.

This lesson describes the use of Linear Programming to search for the optimal solutions to problems with multiple, conflicting objectives, using linear equations to represent the decision problem.

Why Use Linear Programming?

Most decisions require us to consider multiple, usually conflicting, objectives. For example, civil engineers face multi-objective decisions as they try to site a highway in order to balance efficient travel, noise reduction, air quality, cost, and proximity to residential areas. Historically, the approach to finding solutions to multi-objective problems has been a cost-benefit analysis, where all objectives are converted to a single, common currency, typically money, and then the alternative with the highest payoff wins.

Multi-objective optimization is an alternative to a cost-benefit analysis that allows us to analyze decisions that have multiple, conflicting objectives without conversion to a common currency. Linear programming (LP) is a special form of multi-objective optimization, where the objectives and constraints that describe a decision are represented by linear equations, which are then used to find the best (optimal) solutions.

Linear Programming Steps

Linear programming can be divided into seven steps. The first five are about defining the problem to be solved, which may be more important than the mathematics. In the last two steps, we build the linear program equations and solve them. Let's do a simple example.

Step 1. Set the decision context:

Define and limit the problem to be tackled. The simple example here will be that we want a time budget for our daily activities.

Step 2. Identify the stakeholders:

Who should have a voice in this decision? Who has a stake in the outcome? Maybe your mother wants to be a named stakeholder in this decision because she likes to see you be productive. But, let's just focus on you as the single stakeholder.

Step 3. Identify the objectives:

Make a list of the objectives to be achieved. Some common objectives are to minimize costs or maximize productivity. Here, our objectives are to maximize our energy level and maximize the time we have to relax. Notice, that these two objectives are measured in different currencies!

  • Energy (Z1) can be measured by the number of calories available to eat.
  • Time to relax (Z2) is measured in a time unit such as hours.

This is the beauty of linear programming. We do not need to convert energy and time into a common currency. Assume that every hour of food shopping yields 5 calories of food, and every hour relaxing costs 2 calories. Further, assume that every hour spent food shopping is an hour that cannot be spent relaxing and that every hour spent looking for couches yields 4 hours of rest.

Step 4. Identify the decision variables:

The objectives are what is to be achieved. The decision variables are the variables that we can control to achieve the objectives. Here, we have just two decisions to make:

  1. The amount of time to spend food shopping (this makes energy available: x1).
  2. The amount of time to spend looking for couches (this makes relaxation opportunities available: x2).

Step 5. Identify the constraints:

There are always limits to the alternatives. For this problem:

  • Constraint #1 - the food stores are only open for 6 hours
  • Constraint #2 - the couches become uncomfortable after 4 hours
  • Constraint #3 - there are only 8 hours for shopping or searching for couches in a day
  • Constraint #4 - we never want to couch search more than 3 hours longer than we food shop (so as not to look lazy)

Step 6. Formulate the linear equations:

Now create the linear equations for both the objectives and the constraints.

The Objectives:


the objectives


The Constraints:


the constraints


Note the last constraint says that negative values for the decision variables are not allowed. (We cannot spend negative hours food shopping or searching for couches.)

Step 7. Find the optimal solutions:

The algorithm that is used to solve LP is called the Simplex Method and there are many software tools available for it. The solutions produced by the Simplex Method algorithm are optimal solutions, meaning that there are no other feasible options that can offer higher levels of all of the objectives. The graphical representation of our example problem is a visual way to see the optimal solutions generated by the Simplex Method.

Solution to the Example LP

The first visual representation of the solutions is called the Decision Space for the LP problem because it shows all of the combinations of decisions (time spent looking for couches vs. time to spent food shopping) that are feasible, given the constraints. Just to get oriented:


Decision Space
decision space


To unlock this lesson you must be a Study.com Member.
Create your account

Register to view this lesson

Are you a student or a teacher?

Unlock Your Education

See for yourself why 30 million people use Study.com

Become a Study.com member and start learning now.
Become a Member  Back
What teachers are saying about Study.com
Try it risk-free for 30 days

Earning College Credit

Did you know… We have over 200 college courses that prepare you to earn credit by exam that is accepted by over 1,500 colleges and universities. You can test out of the first two years of college and save thousands off your degree. Anyone can earn credit-by-exam regardless of age or education level.

To learn more, visit our Earning Credit Page

Transferring credit to the school of your choice

Not sure what college you want to attend yet? Study.com has thousands of articles about every imaginable degree, area of study and career path that can help you find the school that's right for you.

Create an account to start this course today
Try it risk-free for 30 days!
Create an account
Support