Linear Programming 4: Slack/Surplus, Binding Constraints, Standard Form

welcome in this tutorial we calculate slack and surplus variables identify binding constraints and write the linear programming model in standard form let's begin with this LP model here is a graph of the model showing the constraint line and the feasible region the optimal solution occurs at the intersection of the first two constraints at the point x equals 24 and y equals 12 the constraints that taught your intersect at the optimal solution point are called binding constraints so the first two constraints are binding and the third one is non binding now let's see what happens when we plug the optimal solution point into the left-hand side of each constraints for resource 1 plugging in x equals 24 and y equals 12 gives 60 so the left side equals the right side this tells us that resource 1 was fully utilized at optimal solution that is there is no slack the term slack refers to the amount of a resource that is unused and it applies only to less than or equal to constraints it is basically the amount of under utilization or amount left over so for this first constraint we have a slack of 0 that is all the available 60 units were utilized at optimal solution plug in the optimal solution into resource 2 we have 120 that is all available 120 units of resource 2 were utilized so we have a slack of 0 again recall that the first two constraints are binding it follows that if a less than or equal to constraint is binding its slack value would be 0 the third constraint is a greater than or equal sign on plugging in X we have 24 greater or equal to 10 that is we are required to produce at least 10 units of X and we produce 24 which is 14 more than 10 therefore because this is a greater than constraint we will say that we have a surplus of 14 surplus simply refers to the amount by which we exceed the minimum requirement and it applies only to greater or equal to constraints let's now write the LP in standard form that is we convert the inequalities into equality's by adding slack and surplus variables since the first constraint is a less than or equal constraint we introduce the slack variable and add it to the left side of the constraint so for the first constraint we write X plus 3y plus s1 equals 60 where s 1 is the slack variable to write the second constraint in standard form we add the slack variable s 2 and change the less than sign to equal sign since the third constraint is a greater or equal constraint we introduce the surplus variable and subtract it from the left side of the constraint now slack and surplus variables are always non-negative so the non negativity constraints are written to include slack and surplus variables the slack and surplus variables do not affect the objective function in any way so we usually just include them in the objective function with zero coefficients the standard form of the LP is now complete let's see another example suppose the optimal solution to this LP model occurs at x equals 3 and y equals 4 we want to write it in standard form calculate the slack and surplus values and determine which constraints are binding let's first write it in standard form the first constraint is a greater or equal sign so we introduce it's applause variable with a negative sign as we convert the inequality to equality the second constraint is a less or equal sign so we introduce a slack variable with a positive sign the third constraint will also have a stoploss with a negative sign the fourth constraint is an equality constraint since the purpose of writing the model in standard form is to convert inequalities to equalities this constraint is already in standard form because it contains equality already so no slack or surplus variable is needed for this fourth constraint here are the non negativity constraints and here is the objective function we now use the standard form of the constraints to obtain their slack and surplus values recall that the optimal solution is x equals 3 and y equals 4 so for the first constraint we plug in the optimal solution point to give 20 minus s1 equals 20 that is s1 equals 0 plugging in the optimal solution into the second constraint we have negative 2 plus s2 equals 6 so s2 equals 8 for the third constraint we have 3 plus 4 minus x3 equals 4 so s 3 equals 3 the fourth constraint as neither slackness applause so which of these four constraints are binding constraint one is binding because it has a surplus of 0 constraint 2 is non-binding because it has a nonzero slack of 8 constraint 3 is non-binding because it has a slack of 3 constraint for is binding because it neither has a slackness applause or we can just say that the slack or surplus is 0 in other words an equality constraints will always be binding at optimal solution therefore only constraints 1 and 4 are binding and there you have it thanks for watching

Channel: Joshua Emmanuel

Views: 184,218

Rating: 4.9484673 out of 5

Keywords: Maximize, minimize, lp, problem, model, slack surplus, introduction, linear programme, objective, constraints, nonnegativity, optimal solution, optimization, simplex, binding, standard form

Id: 4hp0mJgzmgc

Length: 5min 30sec (330 seconds)

Published: Tue Aug 11 2015