Operations Research [PDF]

Citation preview

Operations Research Chapter 4



12/28/2018



BG



1



Duality in Linear Programming Problems  For every Linear programming Problem, there is a corresponding unique problem involving the same data and it also describes the original problem.  The original problem is called primal program and the corresponding unique problem is called Dual program.  The two programs are very closely related and optimal solution of dual gives complete information about optimal solution of primal and vice versa.



 Different useful aspects  If primal has large number of constraints and small number of variables, computation can be considerably reduced by converting problem to Dual and then solving it.  Economic interpretation of the dual helps the management in making future decision.  Calculation of the dual checks the accuracy of the primal solution.  Duality is used to solve LPP in which the initial solution is infeasible. 12/28/2018



BG



2



 Points to remember while converting into dual  If the primal contains n variables and m constraints, the dual will contain m variables and n constraints.  The maximization problem in the primal becomes the minimization problem in the dual and vice versa.  The maximization problem has (≤) constraints while the minimization problem has (≥) constraints.  The constants c1, c2, …, cn in the objective function of the primal appear in the constraints of the dual.  The constants b1, b2, …, bm in the constraints of the primal appear in the objective function of the dual.  The variables in both problems are non-negative.



12/28/2018



BG



3



 Important modification  Objective function : If the objective function is maximum in Primal then it will change to minimize in Dual LPP and vice versa.



 Co-efficient of objective function : Co-efficient of objective function in Primal LPP will be the RHS of constraints in Dual LPP.  Constraints : RHS of constraints in Primal LPP will function as co-efficient of objective function in Dual LPP. 12/28/2018



BG



4



 Conversion of primal to its dual Primal



Decision variables: x Maximize Z = cx s. to Ax  b n x0 m



Dual



Decision variables: y Minimize W = yb s. to yA  c m y0 n The general L.P.P. or Primal in Now its Dual is: canonical form is: Minimize w = b1y1+b2y2+…+bmym Maximize z = c1x1+c2x2+…+cnxn Subject to Subject to a11y1+a21y2+…+am1ym ≥ c1 a11x1+a12x2+…+a1nxn ≤ b1 a12y1+a22y2+…+am2ym ≥ c2 a21x1+a22x2+…+a2nxn ≤ b2 …………..…………………………… …………..………………………… ……………………………………….. …………………………………….. a1ny1+a2ny2+…+amnym ≥ cn am1x1+am2x2+…+amnxn ≤ bm where, the dual variables y1, y2,…, ym, where, x1, x2, ...,xn, all ≥ 0. all ≥ 0. 12/28/2018



BG



5



 Co-efficient of decision variables in each constraints : Transverse matrix of Primal LPP is applicable to the co-efficient of decision variables in each constraint for Dual LPP.



Summary of the rules for constructing the Dual problem:



12/28/2018



BG



6



Example Primal :



Dual :



12/28/2018



BG



7



Primal-Dual relationships  If one problem (either primal or dual) has an optimal feasible solution, other problem too has an optimal feasible solution. The optimal value is same for both primal and dual.  If one problem is infeasible), the other problem is either infeasible or unbounded.  If one problem is unbounded the other problem is infeasible.  The dual of the dual is the primal.  Primal-Dual objective values: For any pair of feasible primal and dual solutions,



At the optimum, the relationship is a strict equation, meaning that the two objective values are equal. The optimum can’t occur with z strictly less than w (z < w) because, no matter how close z and w are, there is always room for improvement, which contradicts optimality.



12/28/2018



BG



8



Summary on Matrix Operations:



12/28/2018



BG



9



12/28/2018



BG



10



12/28/2018



BG



11



Simplex Tableau Layout and Optimal Dual Solution: Simplex Tableau Layout and Optimal Dual Solution:



12/28/2018



BG



12



Optimal Dual Solution:



12/28/2018



BG



13



Dual Simplex Method  Dual Simplex Method starts with ‘infeasible but optimal’ solution.  In successive iterations, feasibility improves without disturbing optimality.  Algorithm ends when all the solutions are feasible , i.e. non zero. For the starting solution to be infeasible, at least the right hand side of one of the inequalities is negative.



Steps: 1) Arrange the problem in standard form with basic variables in each equation and represent in tabular form. All the constraints must be of type (≤). - (≥) type constraints are converted to (≤) type by multiplying both sides of the inequality by -1. - (=) constraints are replaced by two inequalities. For example, x1 + x2 = 1 is equivalent to x1 + x2 ≤ 1 and x1 + x2 ≥ 1 or, x1 + x2 ≤ 1 and - x1 - x2 ≤ - 1 12/28/2018



BG



14



2. Select leaving variable (LV) using ‘dual feasibility condition’. Dual Feasibility Condition: The leaving variable xr is the basic variable having the most negative value (ties are broken arbitrarily). If al the basic variables are nonnegative, the algorithm ends. 3. Select entering variable (EV) using ‘dual optimality condition’. Dual Optimality Condition: Given that xr is the leaving variable, let čj be the reduced cost (coefficient) of nonbasic variable xj and αrj the constraint coefficient in the xr – row and xj – column of the tableau. The entering variable is the nonbasic variable with αrj < 0 that corresponds to čj , αrj < 0 αrj If all αrj ≥ 0, the primal will not have any feasible and optimal solution. 4. Carry out the pivotal and row operations as in general simplex to form the new tableau. If all solutions are ≥ 0, the current solution is optimal. Otherwise repeat steps 2 and 3. 12/28/2018



BG



15



Example:



12/28/2018



BG



16



Economic Interpretation of Duality Consider the following primal problem: Maximize subject to



z = c1x1 + ……. + cnxn



all xi ≥ 0 Economic interpretation:  n economic activities, m resources  cj is revenue per unit of activity j  bi is maximum availability of resource i  aij is consumption of resource i per unit of activity j 12/28/2018



BG



17



The Dual Minimize w = b1y1 + ……… + bmym subject to



all yi ≥ 0



12/28/2018



BG



18



Interpreting the Dual Variables If (x1, ………, xn) is optimal for the primal, and (y1, ………, ym) is optimal for the dual, then we know: c1x1 + …….. + cnxn = z = w = b1y1 + …… + bmym Left-hand side: z is the maximal revenue Right-hand side: w= =



resource i) (availability of resource i) × (revenue per unit of resource i)



In other words: Value of yi at optimal is dual (or shadow) price of resource i. It represents the worth per unit of resource i. Away from optimality, we have z < w or (Revenue) < (Worth of Resources) Solution is not optimal because resources are not being fully utilized. Optimality is s reached only when the resources have been exploited completely. 12/28/2018



BG



19



Interpreting the Dual Constraints If (x1, ……., xn) is feasible (not necessarily optimal) for the primal, and (y1, ……., ym) is the corresponding collection of dual values, then :



cj is a measure of revenue, (dollars per unit of activity j). Then must also be in dollars per unit for consistency. So, cj represents revenue and which appears in the equation with the opposite sign must represent cost. 12/28/2018



BG



20



Thus, we have



So it is concluded that the dual variable yi represents the imputed cost per unit of resource i, and we can think of the quantity as the imputed cost of all the resources needed to produce one unit of activity j. The quantity (= imputed cost of activity j – cj) is known by the standard name reduced cost of activity j. The maximization optimality condition of the simplex method is that an increase in the level of an unused (nonbasic) activity j can improve revenue only if its reduced cost is negative.



12/28/2018



BG



21



Post-optimal (sensitivity) Analysis  It is required to make changes in the parameters of the model and find the new optimum solution.  Post-optimal analysis determines the new solution in an efficient way.  The new computations are rooted in the use of duality and the primal-dual relationships. Cases that can arise and the actions needed to obtain the new solution:



12/28/2018



BG



22



Example: TOYCO assembles 3 types of toys: trains, trucks and cars, using 3 operations (mode/sequence of production). Available assembly time for the 3 operations are 430, 460, and 420 minutes per day, respectively, and the revenues per toy, truck, and car are $3, $2, and $5, respectively. The assembly times per train for the three operations are 1, 3, and 1 minutes respectively. The corresponding times per truck and per car are (2,0,4) and (1,2,0) minutes (a zero time indicates the not used operation). Letting x1, x2, and x3 represent the daily number of units assembled of trains, trucks, and cars, the LP model and its dual are formed and solved. 12/28/2018



1



2



1/2



-1/4 1/2



2



1



0



1



The optimal primal solution - producing no toy trains, 100 toy trucks and 230 toy cars. BG



23



(1) Changes affecting feasibility The feasibility of the current optimum solution is affected only if the right-hand side of the constraint is changed, or a new constraint is added.



Changes in the right-hand side of the constraint: This change requires recomputing the RHS of the tableau using the following formula:



Situation 1: TOYCO is increasing the daily capacity of operations 1, 2, and 3 to 600, 640, and 590 minutes, respectively. How does this change affect the total revenue? Solution: Here are the optimum simplex tableau and the two equations.



12/28/2018



BG



24



With these increases in constraints, optimum objective value is changed. The new solution is computed as follows:



Thus the current basic variables x2, x3, and x6 remain feasible. x2 = 140, x3 = 322 , x6 = 28, and the new optimum revenue is $1,880. Situation 2: Although the new solution is appealing, its implementation may take some time. So another proposal is is to shift the slack capacity of operation 3 (x6 = 20 minutes) to the capacity of operation 1. How would this change impact the optimum solution? Solution: With this change, the capacity mix of the three operations changes to 450, 460, and 400 minutes respectively.



12/28/2018



BG



25



The resulting solution is,



This solution is infeasible because x6 = - 40. This requires the application of dual simplex method to recover feasibility.



With x6 leaving and x4 entering, a new optimal solution is obtained as follows. The optimum solution becomes same to the original. So this is not advantageous. Another remaining alternative is to shift this surplus to operation 2. 12/28/2018



BG



26



Get the solution and determine whether this proposal is advantageous.



x2 = 95, x3 = 240 , x6 = 20, and the new optimum revenue is $1,390.



12/28/2018



BG



27



Addition of a new constraint: The addition of a new constraint can never improve the current optimum objective value.  If the new constraint is redundant, it will have no effect on the current solution.  Else the current solution doesn’t satisfy the new constraint, and a new solution must be determined by the dual simplex method. Situation 1: Suppose that TOYCO is changing the design of its toys and that the change will require the addition of a fourth assembly operation. The daily capacity of the new operation is 500 minutes and the times per unit for the three products on this operation are 3, 1, and 1 minutes respectively. The new constraint for operation 4 is, The constraint is redundant here, because it is satisfied by the current optimum solution x1 = 0, x2 = 100, and x3 = 230. Hence, the current solution remains unchanged. Situation 2: Suppose, instead, that TOYCO unit times on the fourth operation are changed to 3, 3, and 1 minutes respectively. All the remaining data remain the same. The new constraint operation 4 is 12/28/2018



BG



28



The constraint is not satisfied by the current optimum solution, and it is added to the current optimum tableau as follows (x7 is a slack variable):



In the tableau, x7 = 500 is not consistent with the values of x2 and x3 in the rest of the tableau. The reason is that the basic variables x2 and x3 have not been substituted out in the new constraint. The substitution is achieved by the following operation: This is equivalent to the following substitutions:



12/28/2018



BG



29



The new tableau is given as



No feasible solution? New optimum solution as obtained by the dual simplex method is x1 = 0, x2 = 90, x3 = 230, and z = $1370. This solution shows that the addition of operation 4 worsens the revenue from $1350 to 1330.



12/28/2018



BG



30



(2) Changes affecting optimality Changes in the objective function coefficients These changes affect only the optimality of the solution and require recomputing the z-row coefficients (reduced costs) according to the following procedures: 1. Compute the dual values using:



2. Substitute the new dual values in the following equation to determine the new reduced costs (z-row coefficients)



If the z-row satisfies the optimality condition, the solution remains unchanged(the optimum objective value may change, however), If it is not, the primal simplex is used to recover optimality. 12/28/2018



BG



31



Situation 1: In the TOYCO model, the company has a new pricing policy to meet the competition. The unit revenues are $2, $3, and $4 for train, truck and car toys, respectively. The new objective function is



The new dual variables are computed as



The z-coefficients are determined as the difference between the left and right-hand sides of the dual constraints. Not necessary to compute the z-row coefficients of x2, x4 and x6! 12/28/2018



BG



32



Situation 2: The objective function is changed to Will the optimum solution change? We have,



12/28/2018



BG



33



12/28/2018



BG



34



Addition of new activity A new activity means a new variable to the model.



12/28/2018



BG



35



12/28/2018



BG



36