Chapter 3 - Intro to linear programming

Question 1

What is the most common application of the linear programming tool?

Answer 1

The most common usage of LP is resource allocation problems.

Resource allocation problems typically involve a set of activities that require resources to operate. Our problem is essentially finding out how much of each activity to “fund” so that our resource-usage is as good as it can be.

It is important to add that this is only a problem when the activities are COMPETING in regards to resources. If activities use different resources, then the problem becomes something different.

Question 2

What does “linear programming” mean?

Answer 2

Linear means linear functions.

Programming means “planning”. It is not coding/developing, it is about creating a programme of activities.

Question 3

Elaborate on the classic “glass production” example with 2 products, 3 plants with this restrictions:

product 1 require plant 1 and then plant 3

product 2 require plant 2 and then plant 3

MC is constant.
Profit is 3000 of product 1, 5000 of product 2

Answer 3

We want to maximize Z = 3x_1 + 5x_2 subject to the constraints.

What constraints do we have?

First, we need to find out how much time each product require in each plant.

Then we need to find out how much capacity (in hours) each plant has.

Then we can solve it.

We find that product 1 require 1 hour in P1, and 3 hours in P3.
we find that product 2 require 2 hours in P2 and 2 hours in P3.

We notice that the products both need plant 3, which is the cause for competition.

We also assume that everything produced will be sold.

THe constraints are like this:

P1 can only operate 4 hours a week. P2 12 hours a week. P3 18 hours a week.

We get:

x_1 <= 4
2x_2 <= 12
3x_1 + 2x_2 <= 18

We also get the non-negativity constraints:
x_1 >= 0
x_2 >= 0

We create the feasible region by plotting in these constraints. This is easy due to 2D plot.

Then we use the objective function in slope-intercept form, shift it to the furthest out point in the feasible region, and read the point values.

Question 4

What is a resource-allocation problem?

Answer 4

They are characterized by constraints on the shape of:

variable relations <= constant

when the right hand side of the inequality represent the amount available of some scarce resource, perhaps time.

Question 5

Elaborate on “resources” and “activities”

Answer 5

The terms “resources” and “activities” are general. In the glass example, we used terms like “3 plants” and “2 products”. This is very specific. In the general case, we are talking about “m resources” and “n activities”.

So, plants become the resources we have that can be used.

The number of products become the activities.

A KEY thing is that resources are limited (plant-hours are limited) and activities (products) are to be selected.

Question 6

What variables do we use in LP?

Answer 6

Z: The overall performance measure

x_j: Level of activity j

c_j: Increase in Z that would result from each unit increase in level of activity

b_i: The amount of resource i that is available for allocation to activities.

a_ij: Amount of resource i consumed by each unit of activity j.

So, in the glass example:

Z is the profit.
x_j is the variables we’re solving for.
c_j is marginal profit/profit per bunch due to constant MC.
b_i is the hours of time each plant i has available.
a_ij is the time each activity j (product) require from resource i.

Question 7

What are “decision variables”?

Answer 7

Decision variables are variables we are solving for.

Question 8

What are the other “variables” in the model referred to as?

Answer 8

Parameters.

Question 9

What is “standard form”?

Answer 9

Our standard form is an LP problem that wants to maximize an objective function (linear) and only have inequality constraints where the left hand side is smaller than or equal to some constant value.
AND non-negativity for all.

Max Z = c1x1+c2c2 + … + cnxn

subject to the restrictions

a11x1 + a12x2 + … + a1nxn <= b1
.
.
.
am1x1 + am2x2 + … + amnxn <= bm

and x1 >= 0, …

Thus, the glass example problem fits the standard model with m = 3 and n = 2.

IMPORTANT: There are many other forms that also classify as linear programming models. They are just not what we embrace as our standard form. Some of these forms are:
1) Minimizing rather than maximizing the objective function

2) Some of the functional constraints having a left-hand side that is GREATER THAN or equal to some constant value.

3) Some of the functional constraints having a tight equality bound, i.e. the functional constraint is an equality.

4) Deleting the nonnegativity constraints for some decision variables.

The whole point is that while the model no longer is a strict resource allocation problem, it is still a LP model.

Question 10

What is the “objective function”?

Answer 10

The objective function is the function we want to maximize. Z.

Question 11

Constraints is a collective term for all constraints of a problem. Can we be more specific?

Answer 11

We can separate between constraints that enforce non-negativity and the ones that impose limits on the resources.

1) Functional constraints
2) Nonnegativity constraints.

Functional constraints are also referred to as “structural constraints”.

Question 12

What is the “concise” definition of an LP problem?

Answer 12

A problem is an LP problem if each component of the problem model fits the standard form, or any other legitimate form.

This means, a problem can be a valid LP problem even though it cannot be structured by the standard form. This just means that our interpretation of “allocating limited resources among competing activities” may not be that fitting for some problems.

Question 13

What is a “solution” in LP?

Answer 13

A solution is just a selection of values for the decision variables.

A solution is not necessarily the desired outcome.

Question 14

What is a feasible solution?

Answer 14

A feasible solution is a solution (value selection to decision variables) that satisfies all the constraints.

Question 15

What is an infeasible solution?

Answer 15

A solution where at least one constraint is violated.

Question 16

What is the optimal solution?

Answer 16

the optimal solution is the solution that has the most favorable value of the objective function. Recall that we attempt to either maximize or minimize the objective function.

Question 17

In what cases can we have “no optimal solution”?

Answer 17

There are 2 cases.

1) Whenever there are no feasible solutions

2) Whenever there is no constraint preventing a variable to be “even higher” essentially making it so that “higher level means better reward” and we can always get higher level. This is referred to as an UNBOUNDED objective.

Question 18

Elaborate on the “proportionality” assumption.

Explain what the “real” outcome of this is.

Answer 18

Proportionality is an assumption regarding both the objective function and the functional constraints.

“The contribution of each activity to the value of the objective function Z is proportional to the level of the activity x_j” as represented by the c_j*x_j term in the objective function.

The same argument applies to the functional constraints, but now the terms are given as a_ij*x_j.

The result of this is at we rule out all exponents other than 1.

Note that this does not rule out cross-variable terms. In order to do this, we use further assumptions.

Question 19

Given a list of “profit” corresponding to different levels of activity, how can we figure out if the proportionality assumption is satisfied or not?

Answer 19

Proportionality implies that the rate of change remains the same. Therefore, we need to see if the growth in profit match the growth in activity at all levels.

Question 20

What could violate the proportionality assumption?

Answer 20

Start up costs

Economies of scale

Diseconomies of scale.

Question 21

ELaborate on the additivity assumption

Answer 21

Recall that the proportionality assumption keeps exponents of variables to “1”. However, this does not stop us from using cross-product terms, like this: x_1*x_2. Cross-product terms are RULED OUT by additivity.

Additivity assumption: “Every function in LP (whether the objective function or functional constraints) is the sum of the individual contributions of the respective activities”. Thus, there is no room for cross-product terms.

This means that additivity makes sure that we only use the sum of contributions to each activity.
Keyword: “individual contributions to each acitvity”. In this definition, there is no room for some kind of contribution that applies to the cross-product of some activities/variables.

Question 22

What happens if either proportionality or additivity is not satisfied?

Answer 22

We cannot solve the problem by LP

Question 23

Elaborate on the divisibility assumption

Answer 23

The divisibility assumption is concerned with the allowed values for our decision variables.

Divisibility assumption: “Decision variables in a linear programming model are allowed to have any values, including non-integer values, that satisfy the functional and nonnegativity constraints. Thus ,these values are not restricted to just integer values.”

NB: This assumes that activities can run at fractional levels. Is this really possible?

Question 24

Elaborate on the certainty assumption

Answer 24

This is just about assuming that the parameters of the LP model is assumed to be known

Question 25

What’s important regarding the certainty assumption

Answer 25

It will very seldom be entirely accurate in real life. We usually use predictions. Therefore, sensitivity analysis is important.

Question 26

Why do we want to use LP and not other types of solvers?

Answer 26

LP is fast. if we are going to use non-linear methods, we’ll quickly lose performance,

Question 27

What are the assumptions of linear programming, except for the one that says “the model is good enough to serve as an abstraction of reality”?

Answer 27

There are 4:

1) Proportionality
2) Additivity
3) Divisibility
4) Certainty

Question 28

What is the requirement for graphical solutions?

Answer 28

Typically, only 2 decision variables.

We might be able to use 3, but it is very difficult.

More than 3 is not possible for obvious reasons.

Question 29

Consider the radiation therapy problem. What type of problem is this?

Answer 29

It is not a resource allocation problem.

Instead, this is a type of “cost-benefit-trade-off” problem. The key characteristic of these problems is that they seek to find the best combination/the best trade off between some benefits and some costs.

In the radiation case, the benefit is the cancer treatment. The cost is the amount of additional exposure to other organs etc.

Question 30

What is a “benefit constraint” in a “cost-benefit-trade-off” problem?

Answer 30

It is an inequality that represent the minimum value (constant) required to receive the benefit.

For instance, in the radiation case, the benefit constraint is the minimum level of radiation required to reach the center of the tumor mass.

The benefit constraint is extremely important as it serves as a fundamental for the entire problem type. It specifies the benefit.

In other words, the benefit constraint makes sure that the choice-maker recevies the intended/wanted benefit. By including the benefit as a constraint, we can then focus on minimizing costs or something else without being worried about loosing the benefit, as we ensure it with the benefit constraints.

Question 31

WHen using the excel solver, what do we need to ask ourselves?

Answer 31

1) What are the DECISIONS to be made? in the glass case, it would be the production rates.

2) What are the constraints for these decisions? In the glass case, it would be the hours available by the plants combined with the requirements of the products at each plant

3) What is the overall performance measure for these decisions? Could be profit

Question 32

Using the Excel solver, how do we distinguish between “changing cells” and “non-changing cells”?

Answer 32

Changing cells are typically given a border.

Question 33

Using the excel solver, what is an “output cell”?

Answer 33

An output cell is a cell whose value depends on the value of a “changing cell”. They are typically the constraints. Their values are not used directly in the calculations, but we include them to gain insight in the solution we’re given.

Question 34

Using the excel solver, what is the “objective cell”?

Answer 34

The objective cell is a special type of an output cell. It is the cell containing the value that we are maximizing or minimizing according to our problem.

We typically shade this cell more than the others.

Question 35

Using the excel solver, what is a “range name”?

Answer 35

A range name is a descriptive name given to a block of cells that acts as an identifier for the values there.

It is useful as we can use it as a reference later, and avoid having to use the cell row and col.

Using range names also makes formulas more easy to understand.

Question 36

Using the excel solver, what is a changing cell?

Answer 36

A changing cell is a cell that the solver will change based on the calculations it does. The changing cells are basically the decision variables.

Question 37

What can we say about problems having multiple optimal solutions?

Answer 37

They will have infinite amount of optimal solutions.

Question 38

Another word for “corner points”

Answer 38

Extreme points

Question 39

Elaborate on the radiation case problem

Answer 39

We want to nuke a tumor, but we dont want to destroy healthy tissue.

We use 2 beams. There could in theory be more beams, but we use 2 for simplicity.

The two beams have some “known” information (parameters of the model) on the impact (average9 of the beam on different parts of the body when applied at some specific entry point.
For instance, if we apply a single unit (kilorad) at some point by beam 1, a dosage of 0.4 kilorad will be absorbed by for instance the healthy anatomy.

The performance measure of this problem is to minimize radiation to the “healthy anatomy”.

The constraints is the following:

1) The center of the tumor has to be above some threshold to be nuked.

2) The average dosage on the ENTIRE tumor must be equal to some value

3) The dosage on some critical part of the anatomy must not exceed certain limits

The decision variables are:
1) x_1: The amount of kilorads from beam 1

2) x_2: The amount of kilorads from beam 2

Question 40

How do we typically create very large models?

Answer 40

We need to use a specific modeling language, as the size of the model is too large to use a spreadsheet or algebraically.

Question 41

Describe LP with one sentence

Answer 41

Determining activity levels based on scarce resources.

Allocating scarce resources among different activities to gain the best possible result.

Question 42

What is a “product-mix” type problem?

Answer 42

A product-mix type problem is concerned with finding the optimal way of producing different types of products

Question 43

Elaborate on distribution network problems

Answer 43

The problem type is called “fixed requirements problem”. This is because most of its constraints will be equality requirements, mainly due to the flow in the distribution network.

The network will have certain channels that carry a cost and sometimes an upper limit to throughput.
The constraints are that the amount of product shipped from the sources must equal the level of production from the source. This is the case for every node. These are called “net flow constraints”. IMPORTANT: We need net flow constraints at every location.

Question 44

Why are all variations of the objective function parallel?

Answer 44

They are parallel because they share the same slope. this is apparent when we convert the objective function to “slope-intercept” form.

Question 45

What is an “activity”?

Answer 45

Activity refers to some operation, process etc.

Another way to describe an activity, is as “something that requires fuel, where the fuel can be any type of resource”.

Therefore, we can categorize “production at soime facility” as an activity. The fuel of this activity is resources like capital and labor.

An activity can also be “buying X amounts of food A”. The “resources” in this case, can be money. We can also

Question 46

Define the infeasible region

Answer 46

The infeasible region is defined as the area where there are no feasible solutions.

In order for a solution to be infeasible, at least one of the constraints have to be violated. Or, it is enough that one is violated to make it infeasible.

Question 47

What are the limits of the graphical method?

Answer 47

It is suitable for 2 dimensional problems. We can extend to 3D, but it becomes very difficult.

In addition, it is not really clear what we are doing. We are using graphical principles, also known as the underlying geometrical principles. Principles like parallel lines are important here. We are essentially using the slope-intercept form to find solutions.

Question 48

Elaborate on cross-product terms. What are they? How do they fit in the LP model?

Answer 48

Cross product terms refers to cases where we multiply variables with each other. Ex xy.

Cross-product terms does not violate proportionality assumption, as proportionality just says that a change in one variable should result in a same growth factor all the time.

However, cross-product terms violate the additivity assumption.

Question 49

What could cause decreasing marginal returns, and thus violating the proportionality assumption?

Answer 49

Increasing marketing costs to produce and sell the same amount.

Question 50

Does start up costs trouble LP?

Answer 50

Yes.

We can either amortize the amount across the number of weeks or something similar.
Or we could use integer programming, or mixed integer programming to solve it.

Question 51

Explain a case where additivity is violated in real life, making LP weak for it

Answer 51

Basically when complementary products work together in some way. Consider the choice of marketing the brand as a whole, vs each separate product. If we market the brand, we can save money. Thus, the profit can be higher when marketing for 2 products than for the same 2 individually.

Question 52

What is the implication/effect/result of the divisibility assumption?

Answer 52

We assume that activities, or whatever we consider as the decision variables etc, can run on fractional ‘intensity’ or ‘level’.

Question 53

Consider sensitivity analysis and radiation therapy. Why is sensitivty analysis important?

Answer 53

Radiation try to find the lowest dosage possible that nukes the bad cells. However, without sensitivty analysis we dont know how much we can change the dosage while remaining good. Perhaps we want to nuke a little harder to be sure. How much more can we nuke?

Question 54

The radiation case have an equality constraint. What does this do for us?

Answer 54

We get a feasible region consisting of a line segment, rather than an actual area.

Question 55

Elaborate on cost-benefit type problems (cost-benefit-trade-off type problems)

Answer 55

The essence is that we have some costs, and we have some benefits. Then we want to strike a balance between them according to the objective function.

Typically, we see costs and benefits in terms of the functional constraints. Radiation therapy is an example of this, considering we want to reach the benefit of killing the bad cells, but limit the cost of damaging good cells.

There is not a formal requirement on constraints regarding whether we’re using the term cost-benefit problem. It is more about whether the overall problem is balancing out costs and benefits.

Thus, cost-benefit differ from resource-allocation because resource-allocation does not consider specific costs or benefits. Resource-allocation only consider optimal distribution of resources among possible activities.
One could say that resource-allocation is either “benefit problem” or a “cost problem”, because the activities usually have a cost or a profit with them.

Question 56

There are 3 forms of specifying LP problems, as we consider it. Name them and explain when they are used

Answer 56

1) Explicit. Writing out all the equaitons etc. Typically used in smaller school examples.

2) General summation form. Most used in practice. Very compact.

3) Matrix form. Used in maths.

Question 57

Why is sensitivity analysis important in LP?

Answer 57

The fourth assumption - certainty - is typically inconsistent. We usually use a mean value along with standard deviation. Therefore, we will typically use statistical tests to calculate boundaries we like. We therefore find outer values we believe we will lie within, ex 95% probability confidence interval, and then we use sensitivity analysis to see if we can maintain our solution in this range.