Lee L. Lowery, Jr.

Just another CoE WordPress site

Linear Programming Guide

Posted on by

Print out this linear programming guide and bring it with you to class

Learning Objectives

The student should be able to

  • Set up basic linear programming problems, for use in optimization.
  • Set up and solve a basic water supply optimization problem using linear programming

Steps in Linear Programming

1) Ask yourself the question: What might I do? Over what parameters of this problem do I have control?

  • I might find it is in my best economic interest (fiiimbei) to make some nails
  • I might fiiimbei to make some screws
  • I might fiiimbei to make some hammers
  • I might fiiimbei to make some glue pots

 

  • I might fiiimbei to make some nails in January using my employees during normal working time
  • I might fiiimbei to make some nails in January using my employees during overtime
  • I might fiiimbei to take some nails from January’s production and store them for later use
  • I might fiiimbei to sell some 1 bedroom apartments
  • I might fiiimbei to sell some 2 bedroom apartments
  • I might fiiimbei to sell some 3 bedroom apartments
  • I might fiiimbei to get some water from the river
  • I might fiiimbei to get some water from the wells
  • I might fiiimbei to go down one of many roads AB
  • I might fiiimbei to go down one of many roads AC
  • I might fiiimbei to go down one of many roads AG

Note that it is extremely important that you not say: I think I might find it is in my best economic interest to sell 23 3-bedroom apartments. That is the computer’s job to tell you the answer. You MUST only say you think it is in your best economic interest to sell SOME 3-bedroom apartments. The answer to this question becomes the variable in your solution.

2) Realize that each of these things you might do is a variable, and give that variable a name:

  • N = number of nails I fiiimbei to make.
  • S = number of screws I fiiimbei to make
  • H = number of hammers I fiiimbei to make
  • G = number of gluepots I fiiimbei to make
  • NJN = number of nails I fiiimbei to make in January during normal working hours (from 8-5).
  • NJO = number of nails I fiiimbei to make in January during overtime (after 5 pm).
  • NJS = number of nails I fiiimbei to remove from the January production and store until later.
  • B1 = number of one bedroom apartments to sell.
  • B2 = number of two bedroom apartments to sell.
  • B3 = number of three bedroom apartments to sell.
  • R = number of gallons of water to suck from the river each day
  • W = number of gallons of water to suck from the wells each day
  • AB = Should I travel down road AB (= 1 or 0, meaning yes or no, travel down this road as opposed to traveling down a different road.)
  • AC = Should I travel down road AC (= 1 or 0, meaning yes or no, travel down this road as opposed to traveling down a different road.)
  • AG = Should I travel down road AG (= 1 or 0, meaning yes or no, travel down this road as opposed to traveling down a different road.)

Note that all variable names must start with a letter, and must include no blanks.

3) Determine, for each of the things you MIGHT do, what type of answer should result for each of the variables.

For example, looking at the variables above, the variables N, S, H, G, NJ, NJN, NJO, and NJS could take on floating point answers and that would be acceptable. If the computer told me that it was in my best economic interest to make NJO = 1,234,567.86 nails in January using my labor force after 5:00 pm (overtime), I could actually make 1,234,568 nails and the difference between the computer’s answer and what I did would not significantly influence my profit. 

On the other hand, some things like B1, B2, and B3 must be forced to take on integer results. If the computer told me to make 23.22 one bedroom apartments, 42.76 two-bedroom apartments, and 14.53 three-bedroom apartments, I am in trouble, since I cannot sell 0.22 of an apartment, and you cannot just round the numbers and get the best solution. Surprisingly, the answer for this problem may well be 20 one-bedroom, 35 two-bedroom and 51 three-bedroom apartments, when the variables are constrained to integer results, which is greatly different from simply taking the closest integer from the non-integer solution listed above. MOR/LP will constrain your variable answers to integers if you tell it to.

R and W will probably be floating point – i.e. 34,884.345 gallons/hour from the river and 45,232.445 gallons/hour from the wells would be acceptable answers.

The answers for AB, AC and AG must be binary (0/1) since they answer a yes/no question: Is it in my best economic interest to travel down road AB (Yes or No.) MOR/LP will constrain your variable answers to 0/1 (binary yes/no) if requested.

4) Write a bill or a profit statement. Basically, what is desired by this problem? What is your TRUE objective?

Write a detailed bill (known as Z, the Objective Function since it is a function, or equation, and it defines your objective) for how much the job will cost, or how much profit you expect to make, depending on how much everything costs. For example, if water from the river costs $2.00 per 1000 gallons, and $2.80 per 1000 gallons if taken from the wells, your bill would read:

Z = 2R + 2.8W

and since it is your job to minimize that function, you write:

Min Z = 2R + 2.8W

Likewise, the profit to be made from the apartments might result in your desire to maximize the following objective function:

Max Z = 2800B1 + 3850B2 + 4960B3

Determining the quickest way to get from point A in town to point Z across town then might result in an objective function of:

Min Z = 3.8AB + 4.2AC + 1.7AG + 3.1BC + 9.2BG + 6.3BZ + etc.

Regardless, you will find it far simpler to generate your MIN/MAX statement using the following procedure:

1) Blindly write down a list of all of your variables.  Include them all:

VARIABLEab +         VARIABLEac +         VARIABLEad +        …         +              VARIABLEzz

2) Add MIN Z =  or MAX Z in front, depending on what you are trying to do, and multiply each variable times its unit cost or profit:

MIN Z =  COSTab*VARIABLEab + COSTac*VARIABLEac + COSTad*VARIABLEad + …  + COSTzz*VARIABLEzz

or

MAX Z =  PROFITab*VARIABLEab + PROFITac*VARIABLEac + PROFITad*VARIABLEad + …  + PROFITzz*VARIABLEzz

In other words simply list all of your variables in a MAX/MIN statement, one at a time, then go back in and precede them by their unit costs or profits.  This will give you the final total bill or profit that will result no matter what the final answer for each variable turns out to be.

5) List any constraints or requirements specified by the contract or governing agency. These constraints are known as “Subject To’s” in linear programming. What conditions MUST be satisfied for the solution you derive to be acceptable. What conditions SHOULD be satisfied for the solution you derive to be acceptable? What conditions WOULD BE NICE to be satisfied for the solution you derive to be acceptable?

So, if there are only 4000 gallons per day available from the wells, and only 8000 gpd from the river, and if you had already agreed to buy no less than 1000 gpd from the well owners, you would add the following STs:

ST    W < = 4000
R < = 8000
W > = 1000

6) Draw a sketch of the problem. Label all the variables, costs, constraints on this sketch.

7) Note that these problems cannot be solved using Engineering Equation Solver. They are best solved using MOR or some other LP program. They can be solved using Excel, but MOR is better.  Also, hand solutions to LP problems are not really feasible.  You just have to check the computer solution as best you can and be careful.