Chapter 6Linear Programming: The Simplex MethodSection 3The Dual Problem: Minimization with Problem Constraints of the Form ≥Learning Objectives for Section 6.3Dual Problem: Minimization with  The student will be able to formulate the dual problem. The student will be able to solve minimization problems. The student will be able to solve applications of the dual such as the transportation problem.Problem Constraints of the Form >2 The student will be able to summarize problem types and solution methods. Dual Problem: Minimization With Problem Constraints of the Form >Associated with each minimization problem with > constraints is a maximization problem called the dual problem. The dual problem will be illustrated through an example. We wish to minimize the objective function C subject to certain constraints: C = 16x1+ 9x2+ 21x33 x1+x2+ 3x3≥ 122x1+ x2+ x3≥ 16x1, x2, x3≥ 0Initial Matrix We start with an initial matrixAwhich corresponds to theWe start with an initial matrix Awhich corresponds to the problem constraints: A1131221116⎡⎢⎢⎤⎥⎥4A=16 9 21 1⎣⎢⎢⎢⎦⎥⎥⎥Transpose of Matrix ATo find the transpose of matrixAinterchange the rows andTo find the transpose of matrix A, interchange the rows and columns so that the first row of A is now the first column of A transpose. The transpose is used in formulating the dual problem to follow. 1216119⎡⎢⎢⎤⎥⎥AT5 312112 16 1⎣⎢⎢⎢⎦⎥⎥⎥ AT=Dual of the Minimization ProblemThe dual of the minimization problem is the following maximization problem:maximization problem:Maximize P under the constraints: P = 12 y1+ 16 y2y1+ 2 y2≤ 16y+y≤96y1+y2≤93y1+ y2≤ 21y1, y2≥ 0Formation of the Dual ProblemGiven a minimization problem with ≥ problem constraints,1. Use the coefficients and constants in the problem constraints and the objective function to form a matrix Awith the coefficients of the objective function in the last row.2. Interchange the rows and columns of matrix Ato 7gform the matrix AT, the transpose of A.3. Use the rows of ATto form a maximization problem with ≤ problem constraints.Theorem 1: Fundamental Principle of DualityA minimization problem has a solution if and only ifA minimization problem has a solution if and only if its dual problem has a solution. If a solution exists, then the optimal value of the minimization problem is the same as the optimum value of the dual problem.8Forming the Dual ProblemWe transform the inequalities into equalities by adding theWe transform the inequalities into equalities by adding the slack variables x1, x2, x3:y1+ 2 y2+ x1= 16y1+ y2+ x2= 99 3y1+ y2+x3=21−12y1− 16 y2+ p = 0Form the Simplex Tableau for the Dual ProblemThe first pivot element is 2 (in red) because it is located in the column p()with the smallest negative number at the bottom (-16), and when divided into the rightmost constants yields the smallest quotient (16/2=8)1212311100162yyxxxPx102311010931001211 0612 0 0 0xxP −−Simplex ProcessDivide row 1 by the pivot element (2) and change the enteringDivide row 1 by the pivot element (2) and change the entering variable to y2121232.5 .50081101091yyxxxPy1123110109310012112 16 0 0 0 0xxP −−Simplex Process(continued)Perform row operations to get zeros in the column containing the pivot element. Result is shown below.element. Result is shown below.Identify the next pivot element (0.5) (in red)121232.5 1 .5008051015yyxyxxPxNew pivot 12230.51012.5 0 .50113080014 28.5Pxx−−−pelementPivot element located in this column because of negative indicatorSimplex Process(continued)Variabley1becomes new entering variableVariable y1becomes new entering variable Divide row 2 by 0.5 to obtain a 1 in the pivot position (circled.)1212321.5 1 .500810 1202yyxxxPyy −13312.5 0 .5011340 800128Px −−Simplex Process(continued)Get zeros in the column containing the new pivot elementGet zeros in the column containing the new pivot element.y1y2x1y2011y110−1x2x3P−10 8202We have now obtained the optimal solution since none of the bottom row 14x3002−518P 0 0 4 8 0 136indicators are negative. Solution of the Linear Programming Problem Solution: An optimal solution to a minimization problem can always be obtained from the bottom row of the final simplex yptableau for the dual problem. Minimum of P is 136, which is also the maximum of the dual problem. It occurs at x1= 4, x2= 8, x3= 012123201110 8yyxxxPy−1521301110 810 120200200 48 0135186Pyyx−−Solution of a Minimization ProblemGiven a minimization problem with non-negative pgcoefficients in the objective function,1. Write all problem constraints as ≥ inequalities. (This may introduce negative numbers on the right side of some problem constraints.)2. Form the dual problem.3Witthiitil t fthd l bl i163.Write the initial system of the dual problem, using the variables from the minimization problem as slack variables.Solution of a Minimization Problem4. Use the simplex method to solve the dual problem.5. Read the solution of the minimization problem from the bottom row of the final simplex tableau in step 4.17Note: If the dual problem has no optimal solution, the minimization problem has no optimal solution.Application:Transportation ProblemOne of the first applications of linear programming was to the problem of minimizing the cost of transporting materials. Problems of this type are referred to as transportation problems.Example: A computer manufacturing company has two assembly plants, plant A and plant B, and two distribution outlets, outlet I and outlet II. Plant A can assemble at most 18,700 computers a month, and plant B can assemble at most 900 computers a month. Outlet I must have at least 500 computers a month, and outlet II must have at least 1,000 computers a month.Transportation Problem (continued)Transportation costs for shipping one computer from each plant to each outlet are as follows: $6 from plant A to outlet I; $5 from plant A to outlet II: $4 from plant B to outlet I; $8 from plant B to outlet II. Find a shipping schedule that will minimize the total cost of shipping the computers from the assembly plants to the distribution outlets. What is the minimum cost? 19Transportation Problem (continued)Solution: To form a shipping schedule, we must decide how many computers to ship from either plant to either outlet. This will involve 4 decision variables:x1= number of computers shipped from plant A to outlet Ix2= number of computers