Script

LINEAR PROGRAMMING – Basic Concepts

Slide 1

  • Welcome back.
  • Linear programming is one of the most used of all management science techniques for its wide applicability, ease of formulation, and the wide availability of software that has been specifically designed to solve such models. In this module we introduce the basic concepts of linear programming models.

Slide 2

  • We begin with a simple question, “What is linear programming”.
  • A linear programming model is one that seeks to maximize or minimize a linear objective function subject to a set of linear constraints.” That’s a mouthful! Let’s break it down.

Slide 3

  • We begin by defining linear functions.
  • We all know that y = mx + b is the equation of a straight line (a linear relation between the variables x and y).
  • We could have y = -4/3x + 6
  • Well we could multiply through by 3 to get rid of the fraction. You then have: 3y = -4x +18; and bringing the -4x over to the left we would have 4x + 3y = 18.
  • The expression 4x + 3y is an example of a linear function in 2 variables.
  • And, in general, a linear function in more than two variables consists of terms of the form constant times variable, plus constant times variable and so forth where the constants could have either positive, negative or even 0 values. Thus, for example, the expression 5X1 – 4X2 + 0X3 + 6X4 is a linear function in 4 variables with the constants being 5, -4, 0, and 6 respectively.
  • Note that this expression only has terms of a constant times a variable raised to the first power, there are no X-squares, no X1’s divided by X2’s, no e to the minus X2’s, no square roots of X1’s, just constant times variable, constant times variable, constant times variable, sum them all up.

Slide 4

  • So now that we have defined a linear function (which the objective function must be according to the definition of a linear programming model), what are linear constraints?
  • Linear constraints are anything of the form
  • Linear function has some relation to a constant.
  • And the relation in the middle of this expression must take on one of three forms:
  • “less than or equal to”, “equal to”, or greater than or equal to”. Note that the equal to part must be part of each expression.
  • Let’s look at some examples.
  • 4X1 + 5X2 – 6X3 + 2X5 (note the constant for X4 is 0 in this expression) is less than or equal to 34 is a linear constraint.
  • So is: 2X1 - 5X2 + X4 is greater than or equal to 47
  • As well as: -2X2 + 8X3 + 9X4 +2X5 equals 67
  • As are X1 is greater than or equal to 0
  • And X5 is greater than or equal to 0.

Slide 5

  • Since we’ve defined what linear functions and linear constraints are, we can now give an example of a linear program. One such linear program might be:
  • Maximize 4X1 + 7X3 - 6X4
  • Subject to: 2X1 + 3X2 – 2X4 equals 20
  • -2X2 + 9X3 + 7X4 is greater than or equal to 10
  • -2X1 +3X2 + 4X3 + 8X4 is less than or equal to 35
  • And X2 is less than or equal to 5
  • With all the X’s greater than or equal to 0. This is actually a set of four linear constraints:
  • X1 is greater than or equal to 0,X2 is greater than or equal to 0, X3 is greater than or equal to 0, and X4 is greater than or equal to 0.

Slide 6

  • Here is another example
  • MINIMIZE 6X1 + 8X2 + 11X3 + 10X4 + 5X5 + 14X6
  • Subject to: X1 + X2 + X3 ≤ 20
  • X4 + X5 + X6 ≤ 30
  • X1 + X4 = 12
  • X2 + X5 = 15
  • X3 + X6 = 22
  • And all X’s ≥ 0 This was the transportation model we developed previously. This illustrates a key point. We do not set out to build a linear programming model. We build mathematical models. If the model we build turns out to be a linear programming model, then so much the better. We can then use all the techniques and software that have been developed over the years for solving linear programming models. But again – we did not seek to build a linear programming model – it just turned out that way!

Slide 7

  • A linear programming model is no different than any other model except for the word linear is attached to the objective function and the constraints.
  • Thus a linear programming model consists of
  • A set of decision variables
  • A linear objective function
  • And a set of linear constraints.

Slide 8

  • So why are linear programming models important? There are several reasons.
  • First, many real life situations actually can be modeled quite well with linear models.
  • And many others can be closely approximated by linear models, at least within in a range of values that may be of interest to the decision maker.
  • There are many well known and documented applications that can be referred to in the literature in
  • Manufacturing, marketing, finance, advertising, agriculture, and many other areas.
  • There are very efficient solution techniques for solving linear models and hence much software is out there to solve linear models. As we shall see shortly Excel solves linear models.
  • And finally, as a by-product, the output from most linear programming software packages includes the answers to many “what-if” questions in reports typically referred to as sensitivity reports.

Slide 9

  • Any mathematical model that is built is based on certain assumptions, and linear programming models are no exception. So let us briefly review these assumptions before we proceed further.
  • The first is that the parameter values are known with certainty. That means that if we say a company makes a profit of $4 for each unit of a particular product it produces, this means $4 per unit – not an average of $4 with a standard deviation of $1.25, $4.
  • The second is that each variable exhibits constant returns to scale. This means each nets a $4 profit, not $4 after the first 2000 items have been produced, but $4 per unit for every unit.
  • The third assumption is that there is no interaction between terms. In some models, the profit may be $4 per unit, but if another similar model is produced they may share certain variable costs so that the cost per unit on each is smaller. In that case, when both are produced the profit for the first product may rise from $4 per unit. If this is the case, this violates this assumption for linear programming and another model type will be appropriate.
  • Finally the continuity assumption means that the value of the variable can take on a continuous range of values, so if is possible that X could be 1 and another possible value of X is 5, all values for X in between are also possible – like 3, 2.5, 2.345, 1.98765432, and so forth.
  • Later we will discuss integer models where X could only assume the integer values in between 1 and 5 in the previous example – that is the values 1,2,3,4 and 5 only.

Slide 10

  • Let’s consider a specific example.
  • Galaxy Industries is a start-up company that is considering manufacturing two types of water guns.
  • It estimates that each dozen of its Space Ray model will net an $8 profit and
  • Requires 2 pounds of plastic and 3 minutes of production time to make.
  • The second model, called the Zapper, will net $5 per dozen and requires
  • 1 pound of plastic and 4 production minutes to make.
  • There are limits on the weekly availability of the special plastic compound that it uses and in the production time that is available.
  • There are only 1000 pounds of the specially treated plastic and 40 hours of production time available each week.
  • And besides that management has approved a request from its marketing department
  • Not to produce more than 700 dozen total water guns each week and that
  • Production of Space Rays should not exceed that of Zappers by more than 350 dozen.

Slide 11

  • Right now
  • Current reasoning is
  • That the company should produce as many Space Rays, the more profitable item per dozen as possible…….
  • keeping in mind that Space Rays should not exceed Zappers by more than 350 dozen. Then using the remaining resources to make Zappers.
  • Using simple programming on a spreadsheet this has led to a production plan of
  • 450 dozen Space Rays and 100 dozen Zappers weekly
  • Which has netted Galaxy $4100 per week.
  • This is a good solution, but can Galaxy do better?

Slide 12

  • Let’s build the mathematical model for this situation
  • Recall that a mathematical model consists of:
  • A set of decision variables
  • An objective function and
  • A set of constraints. Let’s develop these one by one.
  • We begin with the decision variables, the things under the decision maker’s control. In this case it is the weekly production of the two products.
  • We should be careful that the definition take into account both time and measurement units – in this case the variables should be in terms of dozens per week. So let us define
  • X1 to be the number of dozen Space Rays produced weekly and
  • X2 to be the number of dozen Zappers produced weekly.

Slide 13

  • Next is the objective function.
  • Galaxy’s objective is to maximize its total weekly profit
  • So how much profit will Galaxy make each week?
  • Well, how much will it make from Space Rays?
  • It makes $8 per dozen
  • We don’t know how many Space Rays to produce (that is what we are solving for), but the symbol for the number of dozen produced per week is X1.
  • Thus the total weekly profit from Space Rays is 8X1
  • Similarly when we look at the profit from Zappers.
  • Galaxy makes $5 per dozen Zappers
  • And it will make X2 dozen Zappers
  • So the total weekly profit from making Zappers is 5X2.
  • Thus the total weekly profit is 8X1 + 5X2 and
  • This is a quantity we want to maximize.

Slide 14

  • Now let’s turn to the constraints. We begin with the plastic constraint.
  • At most 1000 pounds of plastic can be used weekly.
  • How much will Galaxy use?
  • When making Space Rays
  • It uses two pounds of plastic per dozen produced
  • It will make X1 dozen Space Rays each week
  • So this will utilize 2X1 pounds of plastic.
  • For Zappers
  • Each dozen Zappers uses 1 pound of plastic
  • It will make X2 dozen Zappers
  • Thus the total amount of plastic used making Zappers is 1X2 and
  • The total amount of plastic used weekly will be 2X1 + 1X2 and
  • This must be less than or equal to 1000 – that is the first functional constraint.

Slide 15

  • Now let’s consider production time. We note production time per dozen units is given in minutes whereas the production limit is given as 40 hours. We have to use the same units when writing constraints. So we must either convert the 40 hours to minutes or the production minutes to fractions of an hour. Here we convert the hours to minutes.
  • There are at most 40 hours or 2400 production minutes that can be used weekly. Now how many will be used.
  • For Space Rays
  • Each dozen Space Rays requires 3 minutes per dozen
  • It will make X1 dozen Space Rays each week
  • So this will use up 3X1 production minutes weekly
  • The time spent making Zappers is
  • 4 minutes per dozen
  • It will make X2 dozen Zappers each week which will take up
  • 4X2 production minutes each week
  • Thus the total number of production minutes used weekly is 3X1 + 4X2 and
  • That must be less than or equal to 2400

Slide 16

  • Now we turn to the maximum production requirement.
  • Remember production will be limited to at most 700 dozen units of total product. How many dozen will be produced?
  • How many dozen Space Rays are produced weekly?
  • That’s simply
  • X1
  • And how many dozen Zappers are produce weekly?
  • That’s just
  • X2
  • So the total number of dozen product produced weekly is X1 plus X2 and
  • This should be less than or equal to 700.

Slide 17

  • There is also a production mix restriction that says we cannot produce more than 350 dozen more Space Rays than Zappers each week. So how many more dozen Space Rays than Zappers will be produced each week?
  • Again
  • The number of dozen Space Rays produced each week is
  • X1
  • And
  • The number of dozen Zappers produced each week is
  • X2
  • The amount in dozens that Space Rays exceeds Zappers is X1 minus X2
  • And this should be less than or equal to 350.

Slide 18

  • Finally we have the nonnegativvity constraints which state that …
  • Galaxy cannot produce a negative amount of either Space Rays or Zappers, that is:
  • X1 is greater than or equal to 0 and X2 is greater than or equal to 0
  • Which we frequently write in a short form as
  • All X’s are greater than or equal to 0

Slide 19

  • Thus the complete mathematical model is to
  • Maximize 8X1 + 5X2
  • Subject to the functional constraints of 2X1 + 1 X2 ≤ 1000, 3X1 + 4 X2 ≤ 2400, X1 + X2 ≤ 700, and X1 - X2 ≤ 350,
  • And the nonnegativity constraints that all X’s are greater than or equal to 0. We’ll discuss how to solve this model in future modules.

Slide 20

  • Let’s review what we’ve done in this module.
  • We’ve defined a linear programming model as one that seeks to maximize or minimize a linear objective subject to linear constraints.
  • We stated that many real life problems are or can be approximated by linear programming models.
  • We’ve said that linear programming models require the assumptions of
  • certainty, constant returns to scale and additivity of the coefficients and that the variables must be continuous between any to possible values.
  • And we’ve stated that there exists fast efficient algorithms and software for solving linear programming models which give valuable sensitivity analyses as a by-product of the solution process.

That’s it for this module. Do any assigned homework and I’ll be back to talk to you again next time.