B Semester : I Semester Subject : Quantitative Techniques Subject Code : BBA LLB
Ms. Preeti Goel, Assistant Professor, MAIMS
Introduction to Linear Programming Optimization Problem What is Linear Programming ? Linear programming is a mathematical technique for finding an optimum (maximum or minimum) value of a function, called objective function of several independent variables, these variables being subject to various restrictions (or constraints) expressed as equations or inequalities. The term 'linear' indicates that the function to be maximized or minimized is linear & corresponding constraints be represented by a system of linear inequalities or linear equations involving the variables.
A linear programming problem has the following essential parts:
i. An objective function to be maximized or minimized subject to the above constraints ii. A set of linear constraints representing the limitations on the use of machinery, labour etc. iii. A set of non-negative restrictions. This is to avoid getting negative solutions in which we are not interested. For example, negative price or negative output do not mean anything. Characteristics of LPP Assumptions of LPP Formulation of Linear Programming Problem Steps Step 1: Identification of Decision Variables
Step 2: Identification of Objective Function
Step 3: Identification of Constraint Functions
Step 4: Identification of Non-Negative restrictions
Step 5: Formulation of LPP - Expressing these decision
variables, objective function and constraints function in Linear programming format. Terminology EXAMPLE
Two products: Chairs and Tables
Decision: How many of each to make this month? Objective: Maximize profit Tables Chairs (per table) (per chair) Profit Contribution Rs 7 Rs 5 Hours Available Carpentry 3 hrs 4 hrs 2400 Painting 2 hrs 1 hr 1000 Other Limitations: Make no more than 450 chairs & Make at least 100 tables
Solution Max Z = 7x1 + 5x2 (profit)
Subject to the constraints: 3x1 + 4x2 < 2400 (carpentry hrs) 2x1 + 1x2 < 1000 (painting hrs) x2 < 450 (max # chairs) x1 > 100 (min # tables) x1, x 2 > 0 (nonnegativity) METHODS OF SOLVING LPP
1. Graphical Method
2. Simplex Method GRAPHICAL METHOD
▪ Graphical methods provide visualization of how a solution for
a linear programming problem is obtained. ▪ Graphical solution is limited to linear programming models containing only two decision variables (can be used with three variables but only with great difficulty). Graphic Method GRAPH OF A LINEAR INEQUALITY Step 1: Find Feasible region Step 2: Find Solutions to all Corner Points
Step 3: Find Optimal Solution - The corner point
with the best objective function value is optimal Simplex Method ADDITIONAL VARIABLES USED IN SOLVING LPP MAXIMIZATION CASE ALL CONSTRAINTS IN STANDARD FORM Step 1: Introduce Slack Variables and convert constraint inequalities to equations.
Note slack variables are assigned zero coefficients in objective function.
Step 2: To set up the Initial Basic Feasible Solution – take the slack variables as basic variables. Step 3: To set up the Initial Simplex Tableau i) First Row Cj – Coefficients of variable in Objective Function. Always remain same. ii) Second Row - Major column headings. Always remain same. iii) First Column – Coefficients of basic variables in Objective Function iv) Second Column – Basic variables (slack variables in initial tableau) v) Third Column labelled Solution – Solution value of basic variables (RHS value of constraints). vi) Body Matrix – Coefficient of decision variable in constraint set vii) Second last row Zj – Multiply the entries in that column by corresponding entries of Cj column and add the products (always 0 in initial tableau) viii) Last row Cj-Zj or Index row or New evaluation row – Subtracting each Zj value (second last row) from Cj value (first row). Step 4: Test the solution for Optimality – Check the entries of Cj- Zj row. In maximization problems, if all the entries in this last row are negative or zero, the solution is optimal. Positive entries indicate that solution can be further improved.
Step 5: Revise the Current Simplex Tableau – Now, the aim is to
move from current basic feasible solution to a better basic feasible solution. Replace one current basic variable (departing variable) by a non-basic variable (entering variable) and derive new tableau.
A. Entering Variable ➢ Key(pivot) Column – Column with largest +ve value in Cj-Zj row (indicate by ) ➢ Variable lying in the key (pivot) column is entering variable. B. Departing Variable ➢ Ratio Column – Make a new column labelled Ratio. Divide each entry of solution column by corresponding positive entry of key column & write in Ratio column. ➢ Key Row - Smallest nonnegative entry in this column is key(pivot) row ➢ (indicate by ) ➢ Corresponding variable in this key row is Departing Variable.
The number lying at the intersection of key column and key row is called key or (pivot) number. Place a circle around this number
C. Derivation of New Tableaux
i. Reduce the key number to 1, i.e. divide all the entries of old key row with key number to get new key row values
ii. Change the non-key row values by using the formula:
Step 6: Test the solution for Optimality – Check the entries of Cj-Zj row. In maximization problems, if all the entries in this last row are negative or zero, the solution is optimal. Positive entries indicate that solution can be further improved.
In case of positive entry in the last row, repeat step 5 and step 6. Entering Variable
Step 4: Test the solution for Optimality – Since there are positive entries in Cj-Zj row, solution is not optimal. Step 5: Determine key column – Column with Largest positive entry in Cj – Zj row. Calculate Ratio Column by dividing solution column with key column Determine key row – Row with smallest nonnegative ratio. Key element – Value at intersection of key row and key column Entering variable – variable of key column – y is entering variable Departing variable – variable of key row – s3 is departing variable Step 5: Derivation of Tableau II. (a) Transformation of key row – Divide each entry of key row with key number. Thus, the entries for y-row are
(b) Transformation of non-key rows – To replace non-key rows, we use formula
Entering Variable
Step 6 - Test the solution for Optimality – Since there are positive entries in Cj-Zj row, solution is not optimal.
Determine key column – Column with Largest positive entry in Cj – Zj row.
Calculate Ratio Column by dividing solution column with key column Determine key row – Row with smallest nonnegative ratio. Key element – Value at intersection of key row and key column Entering variable – variable of key column – x is entering variable Departing variable – variable of key row – s1 is departing variable Repeat Step 5: Derivation of Tableau III. (a) Transformation of key row – Divide each entry of key row with key number. (b) Transformation of non-key rows - use formula
Repeat Step 6 - Test the solution for Optimality – Since there are no positive entries in Cj-Zj row, solution is optimal. That is, a total of 3 units of x and 9 units of y are to be produced to give a maximum profit of Rs. 330. Tie Breaking in Simplex Method
Tie for Entering Variable – When variables are tied for having largest positive Cj-Zj entry, there is tie for entering variable. We can choose any one of the entering variable. The optimal solution will be reached eventually, regardless of the tied variable chosen.
Tie for Departing Variable – Where two or more quotients in the ratio column are tied for being the smallest nonnegative, we may choose any one for departing variable. In this case, a basic feasible solution will have a basic variable that is 0, and the solution is said to degenerate.
In a degenerate solution, it is possible that the subsequent tableaux give
the same value of objective function. This is called cycling. In cycling, we may never obtain the optimum value of objective function. Additional Information from Final Simplex Tableau 1. Unbounded Solution When each entry in the key column is either negative or zero, the problem is said to have unbounded solution.
2. Multiple/Alternative Optimal Solution
If the non-basic variable has 0 in Cj-Zj row, then the problem is said to have multiple/alternative optimal solutions.
3. Degenerate Solution Tie for the smallest quotient in Ratio Column OR solution value of basic variable is 0. It may lead to same Z value in subsequent tableaux.
4. Resource Utilization Existence of slack variable – Resource has not been fully utilized (value of slack variable in optimal solution is not zero) Non-existence of slack variable – Resource is fully utilized (value of slack variable in optimal solution is zero) 5. Marginal Contribution – Impact of additional unit of production on profit Check for x and y variable entries in Cj-Zj row in final Simplex Tableau (also called marginal contribution). These values tell us the net impact of one additional unit of production on the profit objective function
Marginal Contribution of x is Marginal Contribution of y
0, indicating that increase in 1 is 0, indicating that increase extra unit production of x will in 1 extra unit production of not have any impact on y will not have any impact profit. Profits will neither on profit. Profits will neither increase or decrease. increase or decrease. 6. Shadow Price - Price to be paid for extra one hour of machine Check for slack variable entries in Cj-Zj row in final Simplex Tableau (also called shadow prices). These values tell us what difference it would make if we could provide an extra hour of each resources.
Shadow price for the first resource is 5
(absolute value), i.e., we could increase For 3rd resource, objective function by 5 if we had an for2nd resource, shadow price is additional hour of that resource. shadow price is 0. 5/2, i.e. we can So, manager has to pay below 5 for additional An additional hour increase objective hour of first resource, then profits could be of 2nd resource function by 5/2 if increased. Hence maximum price for won't help, since we had an additional hour of first resource is 5. this resource has additional hour of not been fully this resource utilised MAXIMIZATION CASE ALL CONSTRAINTS NOT IN STANDARD FORM Omitting the A Column when A = 0 MINIMIZATION CASE DUALITY THEORY Primal Dual Correspondence Solution of a Dual Problem Duality Principle – If either the primal or dual problem has an optimal solution, then so does the other problem (dual or primal) and the optimal value of the primal’s objective function is the same as that of its dual.
