Operations Research and Optimization PDF

14-09-2023 Introduction Operations Rese...

14-09-2023 Introduction Operations Research and Many Decisions are needed to be taken and the optimizations tools and techniques helps to take any decision in giving the most feasible/ Optimization optimal result satisfying all the constraints. Decision making under certain as well as uncertain environments might be taken using QT/OR tools Helps in taking sequential decisions as well as give alternative solutions. Techniques to take decision in case of change in any parameter as the model is already made Methodology Problem Formulation Model Building Physical Models: Iconic/ Analogous Symbolic Models/ Mathematical models INTRODUCTION TO LINEAR Obtaining Input Data Solutions of Model (optimum (giving desired output) & satisfying all constraints) PROGRAMMING Feasible/ Infeasible Optimal and Non-optimal Unique and Multiple Sensitivity Analysis Test the solutions/ Model Validation Analyse the results Implementation  14-09-2023 Linear Programming (LP) PURPOSE & OBJECTIVE A model consisting of linear relationships representing a firm’s Scarce resources objective and resource constraints LP is a method of allocating resources in a optimal way LP is a decision aiding tool widely used in industry for drawing LP is a mathematical modeling technique used to determine a inference level of operational activity in order to achieve an objective, subject to restrictions called constraints OBJECTIVE FUNCTION PROBLEMS (PRODUCTION MANAGEMENT) Costs can be minimized Product mix Profits can be maximized To determine the quantity of each product Production planning To determine the minimum cost production plan with an item fluctuating demand Assembly line balancing To minimize the total elapse time  14-09-2023 PROBLEMS (FINANCIAL MANAGEMENT) PROBLEMS (MARKETING MANAGEMENT) Portfolio selection Media selection To find the allocation of which maximizes the total expected return or To determine the advertising media mix so as to maximize the effective minimize the risk under certain limitations exposure, subject to limit of budget, specified exposure rates to different market segment Profit planning Maximization of the profit merging from investment in plant facilities and Travelling salesman problem equipments, cash in hand, & inventory To find the shor5test route from a given city to each of the specified cities & then returning to the original point of departure, provided no city would be visited twice PROBLEMS (MARKETING MANAGEMENT) PROBLEMS (PERSONNEL MANAGEMENT) Physical distribution Staffing problem To determine the most economic and efficient manner of locating To allocate optimum manpower to a particular job so as to minimize the total manufacturing plant & distribution centre for physical distribution overtime cost or manpower Equitable salaries To determine equitable salaries & sales incentives Job evaluation & selection Selection of suitable person for a specified job  14-09-2023 LP Model Formulation LP Model Formulation (cont.) Max/min z = c1x1 + c2x2 +... + cnxn Decision variables subject to: mathematical symbols representing levels of activity of an operation a11x1 + a12x2 +... + a1nxn (≤, =, ≥) b1 Objective function a21x1 + a22x2 +... + a2nxn (≤, =, ≥) b2 a linear relationship reflecting the objective of an operation : most frequent objective of business firms is to maximize profit am1x1 + am2x2 +... + amnxn (≤, =, ≥) bm most frequent objective of individual operational units (such as a production or packaging department) is to minimize cost xj = decision variables bi = constraint levels Constraint cj = objective function coefficients a linear relationship representing a restriction on decision making aij = constraint coefficients where, Assumptions Proportionality: no economies of scale Additivity: Sum total of all activities combined. No synergy or combined effect. Continuity: Decision variables are continuous One shot decision Continuum Certainty: hence LP is deterministic in nature Finite Choices: limited choices and non negative levels  14-09-2023 LP Model: Example RESOURCE REQUIREMENTS Labor Clay Revenue PRODUCT (hr/unit) (lb/unit) ($/unit) Bowl 1 4 40 EXAMPLE Mug 2 3 50 There are 40 hours of labor and 120 pounds of clay available each day Decision variables x1 = number of bowls to produce x2 = number of mugs to produce EXAMPLE LP FORMULATION Steps to be followed for Formulating LPP RESOURCES TABLE (x1) CHAIR (x2) AVAILABLE WOOD (BF) 30 20 300 LABOUR 5 10 110 UNIT PROFIT 6 8 -  14-09-2023 Problem 1 We make the following table from the given data. Example 1 : A paint manufacturer produces two types of paint, one type of Product Available standard quality (S) and the other of top quality (T). To make these paints, Ingredient S-type T-type Stock he needs two ingredients, the pigment and the resin. Standard quality paint requires 2 units of pigment and 3 units of resin for each unit made, and is Pigment 2 4 12 sold at a profit of Rs.1 per unit. Top quality paint requires 4 units of pigment Unit 3 2 10 and 2 units of resin for each unit made, and is sold at a profit of Rs. 1.50 per Profit 1.0 1.5 unit. He has stocks of 12 units of pigment, and 10 units of resin. Formulate (R/Unit) the above problem as a linear programming problem to maximize his profit? We can now write the complete mathematical model of the problem Problem 3 described in Example as Example 1 A firm produces three products. These products are processed on three different machines. The time required to manufacture one unit of each of the three products and the daily capacity of the three machines are given in the table below: Maximize: P = S + 1.5T Time per unit (in minutes) Machine Machine Capacity Subject to: 2S + 4T 12 Product 1 Product 2 Product 3 (min/day) Machine 1 2 3 2 440 3S + 2T 10 Machine 2 4 - 3 470 Machine 3 2 5 - 430 S 0,T 0 It is required to determine the daily number of units to be manufactured for each product. The profit per unit for product 1, 2 and 3 is Rs. 4, Rs.3 and Rs.6 respectively. It is assumed that all the amounts produced are consumed in the market. Formulate the mathematical (L.P.) model that will maximize the daily profit.  14-09-2023 Step 4 Mention the objective function quantitatively and express it as a linear function of Problem 5 variables. In the present situation, objective is to maximize the profit. i.e., Z = 4x1+ 3x2 + 6x3 (Diet problem) A house wife wishes to mix two types of food F1 and F2 Step 5 in such a way that the vitamin contents of the mixture contain at least Put into words the influencing factors or constraints. These occur generally because of constraints on availability (resources) or requirements (demands). Express these 8 units of vitamin A and 11 units of vitamin B. Food F1 costs Rs. 60/Kg constraints also as linear equations/inequalities in terms of variables. and Food F2 costs Rs. 80/kg. Food F1 contains 3 units/kg of vitamin A Here, constraints are on the machine capacities and can be mathematically expressed and 5 units/kg of vitamin B while Food F2 contains 4 units/kg of as 2x1+ 3x2 + 2x3 ≤ 440 vitamin A and 2 units/kg of vitamin B. Formulate this problem as a 4x1+ 0x2 + 3x3 ≤ 470 linear programming problem to minimize the cost of the mixtures. 2x1+ 5x2 + 0x3 ≤ 430 We can now write the complete mathematical model of the problem described in Example as Minimize: C = 60 x1 + 80x2 Subject to: 3 x1 + 4x2 8 Linear Programming 5 x1 + 2x2 11 Graphical Method x1 0 , x 2 0  14-09-2023 To solve a linear programming problem with two decision variables using the Graphical Solution Method graphical method we use the procedure outlined below; 1. Plot model constraint on a set of coordinates in a plane Step 1. Formulate the linear programming problem. 2. Identify the feasible solution space on the graph where all Step 2. Graph the feasible region and find the corner points. The coordinates of the constraints are satisfied simultaneously corner points can be obtained by either inspection or by solving the two equations 3. Plot objective function to find the point on boundary of this space that maximizes (or minimizes) value of objective of the lines intersecting at that point. function Step 3. Make a table listing the value of the objective function at each corner point. Step 4. Determine the optimal solution from the table in step 3. If the problem is of maximization (minimization) type, the solution corresponding to the largest (smallest) value of the objective function is the optimal solution of the LPP. Maximization Co-ordinates Profit (0,0) 0 1. Solve: (50,0) 350 Maximize P = 7x1 + 5x2 (Objective function) (30,40) 410 subject to 4x1 + 3x2 ≤ 240 (hours of carpentry constraint) (0,80) 400 2x1 + x2 ≤ 100 (hours of painting constraint) x1 ≥ 0, x2 ≥ 0 (Non-negativity constraint) Because the point Equation Values (30,40) produces the highest profit we if x1 = 0 then x2 =80 conclude that producing 4x1 + 3x2 =240 If x2 =0 then x1 = 60 30 tables and 40 chairs will yield a maximum if x1 = 0 then x2 =100 2x1 + x2 = 100 profit of 410. If x2 =0 then x1 = 50  14-09-2023 Equation Values if x1 = 0 then Example 2: x2 =1800 6 X1 + 4 X2 = 7200 If x2 =0 then x1 = 1200 Solve the following LPP using Graphical Method: if x1 = 0 then Max Z = 100 X1 + 80 X2 x2 =1000 2 X1 + 4 X2 = 4000 If x2 =0 then Subject to constraints: x1 = 2000 6 X1 + 4 X2 ≤ 7200 Vertex Co-ordinates Z Optimal Profit = Max Z = Rs. 1, 28, 000 O (0,0) 0 Product Mix: 2 X1 + 4 X2 ≤ 4000 A (0,1000) 80000 X1 = No. of units of A / Month = 800 X1, X2 ≥ 0 X B (800,600) 1,28,000 X2 = No. of units of A / Month = 600 C (1200,0) 1,20,000 Minimization Equation Values if x1 = 0 then x2 =18 1. Solve 72 X1 + 12 X2 = 216 If x2 =0 then Min. Z = 40 X1 + 80 X2 x1 = 3 Subject to constraints: if x1 = 0 then x2 =3 72 X1 + 12 X2 ≥ 216 6 X1 + 24 X2 = 72 If x1 =12 then x2 = 0 6 X1 + 24 X2 ≥ 72 if x1 = 0 then 40 X1 + 20 X2 ≥ 200 x2 =10 40 X1 + 20 X2 = 200 If x2 =0 then X1, X2 ≥ 0. x1 = 5 12,0  14-09-2023 For Calculating B 360 X1 + 60 X2 = 1080…… (1) x 5 For Calculating C 30 X1 + 120 X2 = 360 (1) x 5 Some Special Cases 120 X1 + 60 X2 = 600…….. (2) x 3 240 X1 + 120 X2 = 1200 (2) x 6 240 X1 = 480 210 X1 = 840 Multiple Optimal Solutions X1 = 2 X1 = 4 Substituting value of X1 in equation (1), Substituting value of X1 in equation (1), we get: we get Unboundedness 12 X2 = 216 - 144 = 72 24 X2 = 72 - 24 = 48 X2 = 6 X2 = 2 Infeasibility Vertex Co-ordinates Z A (0,18) 1440 Optimal Cost = Z min = Rs. 320 B (2,6) 560 Optimal Product Mix: X1 = No. of units of product A = 4 C (4,2) 320 X2 = No. of units of product B = 2 D (12,0) 480 Multiple Optimal Solution Infeasibility Maximize Z=8x1+16x2 Maximize Z=20x1+30x2 Subjected to: Subjected to: x1+x2≤200 2x1+x2≤40 3x1+6x2≤900 4x1-x2≤20 x2≤125 x1≥30 x1,x2≥0 X1,x2≥0  14-09-2023 Unboundedness Maximize Z=10x1+20x2 Subjected to: 2x1+4x2≥16 Linear Programming X1+5x2≥15 X1,x2≥0 Simplex Method Simplex Method Slack Variables The geometric method of solving linear programming problems “A mathematical representation of surplus resources.” In real life presented before. The graphical method is useful only for problems problems, it’s unlikely that all resources will be used completely, so involving two decision variables and relatively few problem there usually are unused resources. constraints. Slack variables represent the unused resources between the left- hand side and right-hand side of each inequality. What happens when we need more decision variables and more problem constraints? We use an algebraic method called the simplex method, which was developed by George B. DANTZIG (1914-2005) in 1947 while on assignment with the U.S. Department of the air force.  14-09-2023 To solve a linear programming problem in standard form, use the following steps: Basic and Nonbasic Variables 1- Convert each inequality in the set of constraints to an equation by adding slack variables. 2- Create the initial simplex tableau. Basic variables are selected arbitrarily with the restriction that there be as 3- Select the pivot column. ( The column with the “most positive value” element in many basic variables as there are equations. The remaining variables are the last row.) non-basic variables. 4- Select the pivot row. (The row with the smallest non-negative result when the last element in the row is divided by the corresponding in the pivot column.) 5-Use elementary row operations calculate new values for the pivot row so that the pivot is 1 (Divide every number in the row by the pivot number.) This system has two equations, we can select any two of the four 6- Use elementary row operations to make all numbers in the pivot column equal variables as basic variables. The remaining two variables are then non- to 0 except for the pivot number. If all entries in the bottom row are zero or basic variables. A solution found by setting the two non-basic variables negetive, this the final tableau. If not, go back to step 3. equal to 0 and solving for the two basic variables is a basic solution. If a 7- If you obtain a final tableau, then the linear programming problem has a basic solution has no negative values, it is a basic feasible solution. maximum solution, which is given by the entry in the lower-right corner of the tableau. Pivot Simplex Tableau Pivot Column: The column of the tableau representing the variable to Most real-world problems are too complex to solve graphically. They be entered into the solution mix. have too many corners to evaluate, and the algebraic solutions are Pivot Row: The row of the tableau representing the variable to be lengthy. A simplex tableau is a way to systematically evaluate variable replaced in the solution mix. mixes in order to find the best one. Pivot Number: The element in both the pivot column and the pivot row.  14-09-2023 Initial Simplex Tableau Steps to solve LPP using Simplex Method Step 1: Find the initial basic feasible solution Solution Cj All variables bi Step 2: Set up the initial Simplex table bi /aij Constraint aij=respective Step 3: Test for optimality (profit/loss)/unit Value row element Step 4: Choose the variable to enter/leave the basic set Contribution Basic of the selected column Step 5: Update the Simplex table variab Coefficients les A general maximizing linear programming problem General Simplex table Max Z = 40 X1 + 35 X2 involving n unknown (or decision ) variables and m Subject to constraints: constraints 2 X1 + 3 X2 ≤ 60 4 X1 + 3 X2 ≤ 96 X1, X2 ≥ 0 X Maximise: z = c1x1 + c2x2 +... + cnxn Subject to: a11x1 + a12x2 +... + a1nxn ≤ b1 a21x1 + a22x2 +... + a2nxn ≤ b2... am1x1 + am2x2 +... + amnxn ≤ bm x1 , x2 ,... , xn ≥ 0  14-09-2023 Example 1 Maximize: Z = x1 + 1.5x2 Standard form Subject to: 2x1 + 4x2 ≤ 12 3x1 + 2x2 ≤ 10 x1 ≥ 0 , x2 ≥ 0 Maximize: Z = x1 + 1.5x2 +0S1+0S2 Subject to: 2x1 + 4x2 +S1 = 12 For converting it into standard form, We consider the k-th constraint of the general linear 3x1 + 2x2 +S2 = 10 programming problem x1 ≥ 0 , x2 ≥ 0 ak1x1 + ak2x2 +... + aknxn ≤ bk where S1 and S2 are the slack variables. We convert the k-th inequality constraint to an equality constraint by introducing a new variable, Sk ≥ 0, called a slack variable. The name of the variable derives from the fact that if the left hand side of the constraint is to balance with the right hand side of the constraint, then something has to be added to the left side. Step 1: Set up the initial Simplex table Step 1: Find the initial basic feasible solution Cj 1 1.5 0 0 The simplest choice of an initial feasible basic is to assume that none of the Basic X1 X2 S1 S2 bj decision variables are basic. Hence we initially assume that the basic solution 0 S1 2 4 1 0 12 consists only of the slack variables. i.e. Set xi = 0 , i = 1, 2,... , n and xn+k 6= 0 , k = 1, 2,... , m. This choice of the initial solution means that we initially assume that 0 S2 3 2 0 1 10 objective functional value is zero. In Our Example : If in the constraints of the standard form we set x1 = 0, x2 = 0 we have the initial basic feasible solution S1 = 12, S2 = 10, and Z = 0. But that is not Put X1 and X1 equal to zero. Then initial basic variables are S1 = 12 and S2 = 10 optimal!! How?? lets do the optimality check which you can read from the extreme left and right columns of the table  14-09-2023 Step 3: Test for optimality Step 2: Set up the initial Simplex table In the last row of Table 1 we have the positive coefficients 1 and 1.5 corresponding to x1 Cj 1 1.5 0 0 and x2. Thus the present solution is not optimal. Basis X1 X2 S1 S2 bj bj /aij 0 S1 2 4 1 0 12 Step 4: Choose the variable to enter/leave the basic set 0 S2 3 2 0 1 10 In our example the variables x1 and x2 are the candidates for entry into the basis. The most positive Zj coefficient in the last row is 1.5 in the column labeled x2. This is the pivot column and thus the entering variable is x2. This variable is raised from zero a nonzero value which will be determined in the next step. Now we need to decide which variable should leave the basis. If we divide the coefficients of the last column by corresponding coefficients in the x2-column we obtain the quotients 12/4 = 3 and 10/2 = 5. The smallest quotient is 3, corresponding to S1 in the extreme left column. Thus the S1-row is the pivot row, the variable S1 has to leave the basis as x2 enters, and assumes the value 3. The pivot coefficient is 4. (in circle) Lets use this method for our example. Step 5: Update the simplex table Variable S1 will exit and x2 will enter. For determining elements of incoming row x2 , divide elements of outgoing row S1 by pivot element. For Updating Simplex table, Lets use a ABCDE method, where Cj 1 1.5 0 0 Basis X1 X2 S1 S2 bj A = Row that needs to be replaced from previous Matrix 0 S1 2 4 1 0 12 B = Newly entered row in Current Matrix 0 S2 3 2 0 1 10 C = Element at the intersection of pivot column and row A in Previous Zj 0 0 0 0 Matrix 1 1.5 0 0 D= B multiplied by C E= A-D We will get x2 as ½ ,1, ¼ , 0 and 3, update it in new table  14-09-2023 After repeating steps 3 and 4 Updated Table 3 Cj 1 1.5 0 0 Looking at the last row of the Table 2 above we see that there is still a Basis X1 X2 S1 S2 bj positive coefficient, so the solution is not optimal. We repeat the last three 1.5 X2 0 1 3/8 -1/4 2 steps of the Simplex procedure. Since 1/4 in the objective row is the only positive coefficient, the corresponding column is the pivot column and x1 1 X1 1 0 -1/4 1/2 2 enters the basis. The leaving variable is obtained by comparing the Zj 1 1.5 5/16 1/8 quotients 3/2 = 6 and 4/2 = 2. Hence S2 should leave the basis and give way 0 0 -5/16 -1/8 to x1. The pivot coefficient is 2, at the intersection of the pivot row and Since there are no more positive coefficients in the objective row of pivot column. Table 3 we conclude that the current solution is optimal. Hence Optimal Solution would be x1=2; and x2=2 therefore Z=5 Example 2 Table 1 Cj 5 10 8 0 0 0 Maximize z = 5x1 + 10x2 + 8 x3 Subj. to 3x1 + 5x2 + 2x3 ≤ 60 Basis X1 X2 X3 S1 S2 S3 bj bj /aj 4x1 + 4x2 +4x3 ≤ 72 0 S1 3 5 2 1 0 0 60 2x1+4x2 +5x3≤ 100 0 S2 4 4 4 0 1 0 72 0 S3 2 4 5 0 0 1 100 x 1 , x2 , x 3 ≥ 0 Zj Standard Form Maximize z = 5x1 + 10x2 + 8 x3 +0S1+0S2+0S3 Subj. to 3x1 + 5x2 + 2x3+S1=60 4x1 + 4x2 +4x3+S2 = 72 2x1+4x2 +5x3+S3= 100 x1, x2, x3 , S1, S2, S3≥ 0  14-09-2023 Table 1 Cj 5 10 8 0 0 0 0 S1 3 5 2 1 0 0 60 To update table 0 S2 4 4 4 0 1 0 72 Basic X1 X2 X3 S1 S2 S3 bj bj /aj 0 S3 2 4 5 0 0 1 100 0 S1 3 5 2 1 0 0 60 12 S1 will be replaced by X2 and to determine its element divide all 0 S2 4 4 4 0 1 0 72 18 elements of S1 by the pivot element i.e. 5 and get 0 S3 2 4 5 0 0 1 100 25 10 x2 3/5 1 2/5 1/5 0 0 12 Zj 0 0 0 0 0 0 5 10 8 0 0 0 To determine elements for s2 and s3, we will use ABCDE Method, For S2 The initial basic feasible solution is obtained by setting x1 = x2 = x3 = 0 so that S1 = 60, S2 = 72 and S3 = 100. This solution is not optimal since there are positive A s2 4 4 4 0 1 0 72 coefficients in the last row. The entering variable is x2 corresponding to the most B X2 3/5 1 2/5 1/5 0 0 12 positive coefficient, 10. The quotients are 60/5 = 12; 72/4=18 and 100/4 = 25 of C 4 4 4 4 4 4 4 which 12 is the smallest. Thus S2 is the leaving variable and the pivot element is 5. D BXC 12/5 4 8/5 4/5 0 0 48 X2 will be entering variable and S1 will be exiting variable. E A-D 8/5 0 12/5 -4/5 1 0 24 Updated Table 3 Cj 5 10 8 0 0 0 Basis X1 X2 X3 S1 S2 S3 bj 10 X2 1/3 1 0 1/3 1/6 0 8 8 X3 2/3 0 1 -1/3 5/12 0 10 0 S3 Zj -8/3 26/3 0 10 0 8 1/3 2/3 -17/12 5/2 1 0 18 Linear Programming -11/3 0 0 -2/3 -5/2 0 Looking at the coefficient of the last row in Table 3 we note that only negative Big M Method values are there and hence we reach the optimal solution. Solution: Maximize z = 5x1 + 10x2 + 8 x3 = 5X0+ 10x8+ 8X10= 160 In case X1 comes in the solution it will lead to reduction in profit. In case we bring in X1 in the solution we need to give up 1/3 units of X2 and 2/3 units of X3  14-09-2023 A company is selling two chemicals A & B which are sold to the Steps to solve LPP using Simplex Method manufacturer of soaps and detergents. On the basis of the next month’s demand, the management has decided that the total production of A&B should be at least 350 kgs. Moreover, a major 1. LPs in which all the constraints are (≤) with nonnegative right-hand sides offer a customer order of 125 kgs. for product A must also be supplied. convenient all-slack starting basic feasible solution. Product A requires 2 hours of processing time per kg and product B requires one hour of processing time per kg. For the coming month 2. Models involving ( =) and/or (≥) constraints do not. 600 hours of processing time is available. The company wants to 3. The procedure for starting "ill-behaved" LPs with (=) and (≥) constraints is to minimize total production costs. The production costs are Rs. 2/kg of product A and Rs. 3/ kg for product B. use artificial variables that play the role of slacks at the first iteration, and then The company wants to optimize production costs and find the optimal dispose of them legitimately at a later iteration. Use of the M-method we’ll use product mix. to solve these problems. There might be some more methods like two-phased method etc.. Example1 Standard form Minimize 2x1 +3x2 Minimize Z=2X1+3X2+0S1+0S2+0S3+ MA1+MA2 Subject to Subject to X1+X2-S1+A1=350 X1 +X2 ≥ 350 X1 ≥ 125 X1- S2 +A2=125 2x1+X2 ≤ 600 2X1+X2+S3= 600 X1, X2 ≥ 0 X1, X2, S1, S2, S3, A1, A2 ≥ 0  14-09-2023 Table 1` M A1 1 1 -1 0 0 1 0 350 To Update Table 2 M 0 A2 S3 1 2 0 1 0 0 -1 0 0 1 0 0 1 0 125 600 A2 would be exiting and X1 would be entering. To determine new Cj 2 3 0 0 0 M M elements of A2 row divide individual element with the pivot element i.e. 1 So new row would be Basis X1 X2 S1 S2 S3 A1 A2 bj bj /ai M A1 1 1 -1 0 0 1 0 350 350 M A2 1 0 0 -1 0 0 1 125 125 For A1 0 S3 2 1 0 0 1 0 0 600 300 Zj 2M M -M -M 0 M M A A1 1 1 -1 0 0 1 0 350 B X1 1 0 0 -1 0 0 1 125 2-2M 3-M M M 0 0 0 C 1 1 1 1 1 1 1 1 D 1 0 0 -1 0 0 1 125 E 0 1 -1 1 0 1 -1 225 M A1 1 1 -1 0 0 1 0 350 M 0 A2 S3 1 2 0 1 0 0 -1 0 0 1 0 0 1 0 125 600 Updated Table 2 For S3 Cj 2 3 0 0 0 M M A S3 2 1 0 0 1 0 0 600 B X1 1 0 0 -1 0 0 1 125 Basis X1 X2 S1 S2 S3 A1 A2 bj C 2 2 2 2 2 2 2 2 D 2 0 0 -2 0 0 2 250 M A1 0 1 -1 1 0 1 -1 225 E 0 1 0 2 1 0 -2 350 2 X1 1 0 0 -1 0 0 1 125 0 S3 0 1 0 2 1 0 -2 350 Zj 2 M -M M-2 0 M -M+2 0 3-M M 2-M 0 0 2M-2  14-09-2023 M A1 0 1 -1 1 0 1 -1 225 M A1 0 1 -1 1 0 1 -1 225 To Update Table 3 2 0 X1 S3 1 0 0 1 0 0 -1 2 0 1 0 0 1 -2 125 350 2 0 X1 S3 1 0 0 1 0 0 -1 2 0 1 0 0 1 -2 125 350 S3 would be exiting and S2 would be entering. To determine new elements of S3 row divide individual element with the pivot element For X1 i.e. 2 So new row would be A X1 1 0 0 -1 0 0 1 125 B S2 0 1/2 0 1 ½ 0 -1 175 For A1 C -1 -1 -1 -1 -1 -1 -1 -1 A A1 0 1 -1 1 0 1 -1 225 D 0 -1/2 0 -1 -1/2 0 1 -175 B S2 0 1/2 0 1 1/2 0 -1 175 E 1 1/2 0 0 1/2 0 0 300 C 1 1 1 1 1 1 1 1 D 0 1/2 0 1 1/2 0 -1 175 E 0 1/2 -1 0 -1/2 1 0 50 M A1 0 ½ -1 0 -½ 1 0 50 Updated Table 3 To Update Table 4 2 0 X1 S2 1 0 ½ ½ 0 0 0 1 ½ ½ 0 0 0 -1 300 175 A1 would be exiting and X2 would be entering. To determine new Cj 2 3 0 0 0 M M elements of A1 row divide individual element with the pivot element i.e. 1/2 So new row would be \ Basis X1 X2 S1 S2 S3 A1 A2 bj M A1 0 ½ -1 0 -½ 1 0 50 2 X1 1 ½ 0 0 ½ 0 0 300 For X1 A X1 1 1/2 0 0 1/2 0 0 300 0 S2 0 ½ 0 1 ½ 0 -1 175 B X2 0 1 -2 0 -1 2 0 100 Zj 2 1+M/2 -M 0 1-M/2 M 0 C D 1/2 0 1/2 1/2 1/2 -1 1/2 0 1/2 -1/2 1/2 1 1/2 0 ½ 50 0 2-M/2 M 0 -1+ M/2 0 M E 1 0 1 0 1 -1 0 250  14-09-2023 M A1 0 ½ -1 0 -½ 1 0 50 Table 4 2 X1 1 ½ 0 0 ½ 0 0 300 0 S2 0 ½ 0 1 ½ 0 -1 175 Cj 2 3 0 0 0 M M For S2 Basis X1 X2 S1 S2 S3 A1 A2 bj A S2 0 1/2 0 1 1/2 0 -1 175 3 X2 0 1 -2 0 -1 2 0 100 B C X2 0 1/2 1 1/2 -2 1/2 0 1/2 -1 1/2 2 1/2 0 1/2 100 ½ 2 X1 1 0 1 0 1 -1 0 250 D 0 1/2 -1 0 -1/2 1 0 50 0 S2 0 0 1 1 1 -1 -1 125 E 0 0 1 1 1 -1 -1 125 Zj 2 3 -4 0 -1 4 0 0 0 4 0 1 M-4 M Thus the optimal Solution would be X1= 250 and X2= 100 and Z=800 Problem: These discussions led to developing the following definition of the problem: Determine what the production rates should be for the two products in order to The WYNDOR GLASS CO. produces high-quality glass products, including windows and glass doors. It has three maximize their total profit, subject to the restrictions imposed by the limited plants. Aluminum frames and hardware are made in Plant 1, wood frames are made in Plant 2, and Plant 3 produces production capacities available in the three plants. (Each product will be the glass and assembles the products. Because of declining earnings, top management has decided to revamp the produced in batches of 20, so the production rate is defined as the number of company’s product line. Unprofitable products are being discontinued, releasing production capacity to launch two batches produced per week.) Any combination of production rates that satisfies new products having large sales potential: these restrictions is permitted, including producing none of one product and as Product 1: An 8-foot glass door with aluminum framing much as possible of the other. Product 2: A 4 6 foot double-hung wood-framed window Product 1 requires some of the production capacity in Plants 1 and 3, but none in Plant 2. Product 2 needs only Plants 2 and 3. The marketing division has concluded that the company could sell as much of either product as could be produced by these plants. However, because both products would be competing for the same production capacity in Plant 3, it is not clear which mix of the two products would be most profitable. Therefore, an OR team has been formed to study this question. The OR team began by having discussions with upper management to identify management’s objectives for the study.  14-09-2023 Dual Problem Duality and Sensitivity The theory of duality simply states that every linear programming problem Analysis can be written in two forms: the primal form and the dual form. The original problem is called the primal problem. The objective of a dual problem is opposite that of the given primal problem. Thus a primal minimization problem has a dual maximization problem. The same holds for a maximization problem. That is, a primal maximization problem has a dual minimization problem. Introduction In linear programming, duality implies that each linear programming For example, consider the problem of production planning. The problem can be analyzed in two different ways but would have production manager attempts to determine quantities for each equivalent solutions. Any LP problem (either maximization and product to be produced with an objective to optimize the use of minimization) can be stated in another equivalent form based on the available resources so that profit is maximum. But through a dual LP problem approach, he may develop a production plan that optimizes same data. The new LP problem is called dual linear programming resource utilization so that marginal opportunity cost of each unit of a problem or in short dual. In general, it is immaterial which of the two resource is equal to its marginal return (also called shadow price). problems is called primal or dual, since the dual of the dual is primal. The shadow price indicates an additional price to be paid to obtain one additional unit of the resources in order to maximize profit under the resource constraints. The shadow price is also defined as the rate of change in the optimal objective function value with respect to the unit change in the availability of a resource.  14-09-2023 Duality Von Neumann Duality Principle Linear Programming problem exists in pairs so that corresponding to There is an important result called the Von Neumann duality principle which every give LPP there is a another LPP. relates the optimal value of the dual problem to that of the primal problem. The statement of the result is that the optimal solution of a primal linear programming problem, if it exists, has the same value at the optimal solution of the dual problem. Thus the optimal value determined for the dual problem is the same optimal value for the primal problem. Example 1 The augmented matrix corresponding to this minimization problem is Min Z = 3x1 + 2x2 Subject to 2x1 + x2 ≥ 6 x1 + x2 ≥ 4 x1 ≥ 0 and x2≥ 0. There is no need to solve both LP problems separately. Solving one LP problem is equivalent to solving the other simultaneously. Thus, if the optimal solution to one is known, the optimal solution of the other can also be read from the cj – zj row. In some cases, considerable computing time can be reduced by solving the dual LP problem.  14-09-2023 Thus, the matrix corresponding to the dual maximization problem is This implies that the dual maximization problem is as follows. given by the following transpose. Maximize P = 6y1 + 4y2 Subject to the constraints 2y1 + y2 ≤ 3 y1 +y2≤ 2 where y1 ≥ 0 and y2 ≥ 0. Standard form Table 1 Cj 6 4 0 0 Maximize P = 6y1 + 4y2 Basis Y1 Y2 S1 S2 bj Subject to the constraints 2y1 + y2 + S1 = 3 0 S1 2 1 1 0 3 y1 +y2 + S2 = 2 0 S2 1 1 0 1 2 Zj 0 0 0 0 where y1 ≥ 0 and y2 ≥ 0. 6 4 0 0 Here S1 would be exiting variable and y1 would be entering variable. Pivot element is at intersection of these two.  14-09-2023 To update Table 2 Table 2 Cj 6 4 0 0 For Y1, entire row S1 would be divided by pivot element i.e. 2 and new row i.e. y1 would be Basis Y1 Y2 S1 S2 bj 6 Y1 1 1/2 1/2 0 3/2 0 S2 0 1/2 -1/2 1 ½ For S2 , apply ABCDE method Zj 6 3 3 0 A S2 1 1 0 1 2 0 1 -3 0 B Y1 1 1/2 1/2 0 3/2 C 1 1 1 1 1 Here S2 would be exiting variable and Y2 would be entering variable and pivot element is at the D BXC 1 1/2 1/2 0 3/2 intersection of these i.e. 1/2 E A-D 0 1/2 -1/2 1 1/2 To Update Table 3 Table 3 Cj 6 4 0 0 For row y2, row S2 would be divided by pivot element i.e. ½. Basis Y1 Y2 S1 S2 bj For Y1, apply ABCDE technique 6 Y1 1 0 1 -1 1 4 Y2 0 1 -1 2 1 A Y1 1 1/2 1/2 0 3/2 Zj 6 4 2 2 B Y2 0 1 -1 2 1 0 0 -2 -2 C 1/2 1/2 1/2 1/2 ½ D BXC 0 1/2 -1/2 1 1/2 The current solution is optimal since all the coefficients E A-D 1 0 1 -1 1 in the last row are non positive.  14-09-2023 For our particular example, the decision variables x1 and x2 of the primal problem correspond to Note that if we substitute the basic variables of the dual the slack variables of the dual problem and their values are the problem in the dual objective function we have corresponding coefficients in the last P = 6y1 + 4y2 = (6)(1) + (4)(1) = 10. row of the final simplex tableau. Thus the solution is contained in the S1 and S2 columns and is We get the same objective value if we substitute x1 = 2, x2 x1 = 2, x2 = 2 = 2 into the primal objective function and the objective value is in the usual column i.e C = 3x1 + 2x 2 = (3)(2) + (2)(2) = 10 y1 = 1, y2 = 1 This verified the Von Neumann Optimality Principle. Primal Dual Maximization Minimization Some observation No. of Variables No. of Constraints The primal or original linear programming problem is of the maximization No. of Constraints, No. of Variables type while the dual problem is of minimization type. ≤ type of constraint Non negative variable The constraint values of the primal problem become the coefficient of dual variables y1 and y2 in the objective function of a dual problem and while = type of constraint Unrestricted variable the coefficient of the variables in the objective function of a primal problem has become the constraint value in the dual problem. Unrestricted variable = type of constraint The first column in the constraint inequality of primal problem has become Objective function coefficient for RHS constant for jth variable the first row in a dual problem and similarly the second column of jth variable constraint has become the second row in the dual problem. Objective function coefficient for RHS constant for ith variable ith variable The directions of inequalities have also changed, i.e. in the dual problem, the sign is the reverse of a primal problem. Such that in the primal Coefficient aij for in jth in ith Coefficient aij for in ith in jth problem, the inequality sign was “≤” but in the dual problem, the sign of constraint constraint inequality becomes “≥”.  14-09-2023 Transportation Problem Network Representation 1 d1 Transportation c11 s1 1 c12 c13 2 d2 c21 c 22