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
and to make a chair it requires
45 wood and
But we only have a certain amount of
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
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
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.
# 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)
# 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.
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
# restating the problem with the original contraints problem = cp.Problem(objective, constraints) # Solve to get the dual values computed and ready to display problem.solve() # 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.
# 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")
36.59340662035528 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
# 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