Lets look at an example Linear Program for a supply constrainted problem


lets say that we are a manufacturing company and we have two main products (tables and chairs)

We can sell each table for 30 and each chair for 45. But both tables and chairs are made up of similar materials and require a certain amount of each to produce one table or chair.

Say in order to make a table it requires 22 wood and 15 steel and to make a chair it requires 45 wood and 10 steel.

But we only have a certain amount of wood(5500) and steel(2500) avalible to make our products. So we must distribute the resources effectively such that we waste the least amount and make the most amount of money.

So all in all We want to Maximize total earned with constriants of total wood and steel avalible

Converting Example to standard form

we can reformulate the problem into a Maximization problem of we can make the amount of tables = x and amount of chairs = x2

so we want to find

f(x, x2) = Max(30x + 45x2) with the constraints of wood (22x + 45x2) <= 5500 and steel (15x + 10x2) <= 2500 and of course we want to make a positive amount of tables and chairs so x,x2 >= 0. Concisely this looks like

f(x) = Max(30x + 45x2)
Subject to. 
(22x + 45x2) <= 5500
(15x + 10x2) <= 2500
x,x2 >= 0

We can see this problem formulated and solved with the cvxpy library below, But if you were to solve it manualy look up simplex method since this is a linear program or look into the interior point method

We can see a graphical solution (hence only two variable) https://www.desmos.com/calculator/su3zgtoa8j

In [18]:
import cvxpy as cp

# Defining the variables we want to solve for
x = cp.Variable()
x2 = cp.Variable()

# This is our objective function we want to maximize
objective = cp.Maximize(30*x + 45*x2)

# These are our constrints representive indiviually as inequalities
variableConstraints = (x >= 0)
variableConstraints1 = (x2 >= 0)
woodConstraint = (22*x + 45*x2 <= 5500)
steelConstraint = (15*x + 10*x2 <= 2500)

# we put all the constraints into a container(array) called constraints
constraints = [variableConstraints, variableConstraints1, woodConstraint, steelConstraint]

# Now we have our formulated problem
problem = cp.Problem(objective, constraints)

# outputing the results
print("The max amount of money we can make on these chairs and tables is:", problem.solve())
print("table (x) amount is: ", x.value)
print("chair (x2) amount is: ",  x2.value)
The max amount of money we can make on these chairs and tables is: 6510.989009341022
table (x) amount is:  126.37362623933787
chair (x2) amount is:  60.43956049246413

Adding a new constraint (feasibility analysis)

Lets go back to the example and say that we find out after computing our values that we need we find out that we actually have another product which we have a limited supply of and it is also required. That product is Glue

Say that for each Table it costs 3 glue and for a Chair it cost 2 glue and we only have 550 glue.

Then it would be pretty easy to add a new constraint as it would just be

glueConstraint = (3*x + 2*x2 <= 550)

now we can plug our previous values into the inequality and we can see if our previous anwser holds

3(126) + 2(60) <= 550 True

Now since the result was true then that means we dont need to do anything because we are already at a feasibility point.

In [19]:
# Here we are adding a new constraint to our previous contraints
newConstraints = constraints + [3*x + 2*x2 <= 550]

# We then reconstruct the problem with the new constraints
problem = cp.Problem(objective, newConstraints)

# We now print out the computed results to prove that it will be the same as the previous problem
print("The new max that we can possibly make:", problem.solve())
print("The new x and x2 values respectivly: ", x.value, x2.value)
The new max that we can possibly make: 6510.989009058838
The new x and x2 values respectivly:  126.37362628453253 60.439560456063575

We can see that the results were the same as without the new constraint so no need to recompute since we know this to be true.

But say instead we only have 300 glue avalible then that means

3(126) + 2(60) <= 300 False

and then we would need to recompute a new feasible value

with the added constraint of

glueConstraint = (3*x + 2*x2 <= 300)
In [20]:
# Here we will take the first set of contraints and then add the newer constraint that should tighten the feasible region
newConstraints = constraints + [3*x + 2*x2 <= 300]

# Redefining the problem with the tighter contraint
problem = cp.Problem(objective, newConstraints)

# Proof to show that when recomputed we get a tighter response
print("The new max that we can possibly make:", problem.solve())
print("The new x and x2 values respectivly: ", x.value, x2.value)
The new max that we can possibly make: 5719.7802170083605
The new x and x2 values respectivly:  27.472527201573207 108.79120891024809

We can see that we get drastically different values for x and x2 because of this new constraint. And we get a smaller value in the objective function

Now adding a new constraint is pretty straight forward but next we're going to take a look at adding a new product which invloves the dual problem.

Adding new product (Dual Problem & Sensitivity Analasyis)

Now imagine that the big boss said that we are going to be adding a new product to our compnay and thus we need to factor in the amount of materials it uses.

Say that we wanted to add dressers to our product line and it takes 30 wood and 15 steel to make and we make 50 off of it. but you may notice that if we were to add this to our original problem it would make a change to every single line, including our objective function.

f(x) = Max(30x + 45x2 + 50x3)
Subject to. 
(22x + 45x2 + 30x3) <= 5500
(15x + 10x2 + 15x3) <= 2500
x,x2,x3 >= 0

Insead we can take the dual of the problem like so

f(y) = Min(5500y1 + 2500y2)
Subject to.
22y1 + 15y2 >= 30
45y1 + 10y2 >= 45
30y1 + 15y2 >= 50
y1, y2 is an element of the Reals

you may notice that the dual of the original problem is the same as the dual of the new problem with the last constraint removed which is related to our new product.

Now even though it may not be visiblile because it is hidden behind the cvxpy library but when we compute the first problem we are given dual values or sometimes called shadow prices which are our y1 and y2 values. These values seen below give us the same output for the minimization objective function as a the maximization one in the initial problem. as seen below

In [21]:
# restating the problem with the original contraints
problem = cp.Problem(objective, constraints)

# Solve to get the dual values computed and ready to display

# showing that the y values multiplied by the shadow/dual values gets us the original solution
print("Solution to minimization problem: ", 5500*woodConstraint.dual_value + 2500*steelConstraint.dual_value)

# printing out dual values
print("Dual value represented in y1: ", woodConstraint.dual_value)
print("Dual value represented in y2: ", steelConstraint.dual_value)
Solution to minimization problem:  6510.989015802337
Dual value represented in y1:  0.8241758248195796
Dual value represented in y2:  0.7912087917178597

Now that we can see that our original problem gave us two shadow prices that we could use in the dual problem now we can decide whether or not we need to recalculate for our new product by simply inputing our shadow price values for our new constriant in the dual problem.

In [22]:
# Showing that the adding the constraint of dressers with 30 wood and 15 steel multiplied by the dual values
# is false meaning we need to recompute the feasibile value
print(30*woodConstraint.dual_value + 15*steelConstraint.dual_value)
print("this is false")
this is false

We now see that adding a new product makes the problem now infeasible meaning that we need to recompute the solution which is pretty straight forward. Which would be adding a new value to each row and then applying the algorithm of choice. For a linear program you could use the Simplex method

below we are just redefining the problem with the new product but since it touches all of the items we need to update each row

In [36]:
# Creating new x3 variable
x3 = cp.Variable()
# creating minimum value for the x3 constraint
variableConstraints2 = (x3 >= 0)

# Redefining the material constraints with the new product
woodConstraint = (22*x + 45*x2 + 30*x3 <= 5500)
steelConstraint = (15*x + 10*x2 + 15*x3 <= 2500)

# we put all the constraints into a container(array) called constraints
constraints = [variableConstraints, variableConstraints1, variableConstraints2, woodConstraint, steelConstraint]

# This is our objective function we want to maximize
objective = cp.Maximize(30*x + 45*x2 + 50*x3)

# Printing results
problem = cp.Problem(objective, constraints)
print("Solution to problem: ", problem.solve())
print("The amount of Table value: ", x.value)
print("The amount of Chair value: ", x2.value)
print("The amount of Dresser value:", x3.value)
print("Wood constraint Dual/Shadow Value: ", woodConstraint.dual_value)
print("Steel constraint Dual/Shadow Value: ", steelConstraint.dual_value)
Solution to problem:  8566.666665947438
The amount of Table value:  5.158440996338224e-09
The amount of Chair value:  19.99999996726792
The amount of Dresser value: 153.33333334531252
Wood constraint Dual/Shadow Value:  0.46666666715030436
Steel constraint Dual/Shadow Value:  2.4000000005977715
In [ ]:
In [ ]:
In [ ]: