Learn about solving Linear Programming Problems using the Simplex Method. Understand the definition of basic solutions, non-basic solutions, and degenerate basic solutions. Utilize the Simplex Method to solve a specific LPP example involving maximizing Z subject to multiple constraints. Master the process of transforming the LPP into standard form by introducing slack variables. Benefit from detailed explanations and visual aids provided by Dr. SNS Rajalakshmi College of Arts and Science in Coimbatore.
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Dr.SNS RAJALAKSHMI COLLEGE OF ARTS AND SCIENCE Coimbatore 49 An Autonomous Institution Accredited by NAAC(Cycle III) with A+ Grade (Recognized by UGC, Approved by AICTE, New Delhi & Affiliated to Bharathiar University, Coimbatore) MASTER OF BUSINESS ADMINISTRATIONS 21PBA111 QUANTITATIVE TECHNIQUES I YEAR -II SEMESTER UNIT 2: LINEAR PROGRAMMING PROBLEM TOPIC SOLUTION OF LPP BY SIMPLEX METHOD
GENERAL LINEAR PRORAMMING PROBLEMS- SIMPLEX METHODS Definition (1) A set of variable x1, x2, .xnwhich satisfies the constraints of the LPP is called its solution. Definition (2) Any solution to a LPP which satisfies the non-negativity restrictions of the LPP is the feasible solution. Definition (3) Any feasible solution which optimizes the objective function of the LPP is called its optimum solution or optimal solution. SIMPLEX METHOD /21PBA111 QUANTITATIVE TECHNIQUES /RAMESH.T/DEPT OF MATHS /Dr.SNS RCAS 2/17 SNS DESIGN THINKERS
The Simplex Method The most commonly used method for locating the vertex is the simplex method or simplex technique or simplex algorithm. Definition (1) Given a system of m linear equations with n variable (m<n). the solution obtained by setting (n-m) variables equal to zero and solving for remaining m variables is called a basic solution. The m variables are called basic variables and they form the basic solution. The (n-m) variables which are put to zero are called as non-basic variables. SIMPLEX METHOD /21PBA111 QUANTITATIVE TECHNIQUES /RAMESH.T/DEPT OF MATHS /Dr.SNS RCAS 3/17 SNS DESIGN THINKERS
Definition (2) A basic solution is said to be a Non-degenerate basic solution if none of the basic variables is zero. Definition (3) A basic solution is said to be a degenerate basic solution if one or more of the basic variables are zero. Definition (4) A feasible solution which is also basic is called a basic feasible solution. Slack Variable: ax+b < Z ax+b+S =Z 7 < 10 ----- = 7 + 3 = 10 Surplus Variable: ax+b > Z ax+b-S = Z 10 > 7 ---- = 10 3 = 7 SIMPLEX METHOD /21PBA111 QUANTITATIVE TECHNIQUES /RAMESH.T/DEPT OF MATHS /Dr.SNS RCAS 4/17 SNS DESIGN THINKERS
Use simplex method to solve the LPP Maximize Z = 4x1 + 10x2 Subject to 2x1 + x2 50 2x1 + 5x2 100 2x1+ 3x2 90 and x1, x2 0. Solution: Standard form of the LPP By introducing the slack variables s1, s2,and s3,the problem in standard form becomes SIMPLEX METHOD /21PBA111 QUANTITATIVE TECHNIQUES /RAMESH.T/DEPT OF MATHS /Dr.SNS RCAS 5/17 SNS DESIGN THINKERS
Maximize Z = 4x1+ 10x2+ 0s1+ 0s2+ 0s3 Subject to 2x1+ x2+ s1+ 0s2+ 0s3= 50 2x1+ 5x2+ 0s1+s2+ 0s3= 100 2x1+ 3x2+ 0s1+ 0s2+ s3= 90 and x1, x2, s1, s2, s3 0 Since there are 3 equations with 5 variables, the initial basic feasible solution obtained by equating (5-3) = 2 variables to zero. 6
The initial basic feasible solution is s1= 50, s2= 100, s3= 90 (x1= 0, x2= 0, non-basic ) The initial simplex table is given by CJ 4 10 0 0 0 = min Xbi/air CB YB XB X1 X2 S1 S2 S3 0 s1 50 2 1 1 0 0 50 20* 0 s2 100 2 (5) 0 1 0 0 s3 90 2 3 0 0 1 30 ZJ- CJ= ij 0 -4 -10 0 0 0 7
CJ 4 10 0 0 0 CB YB XB X1 X2 S1 S2 S3 0 s1 30 8/5 0 1 -1/5 0 10 x2 20 2/5 1 0 1/5 0 0 s3 30 4/5 0 0 -3/5 1 ZJ- CJ 200 0 0 0 2 0 Since all Zj CJ 0 the current basic feasible solution is optimal. The optimal solution is Max Z = 200, X1= 0, X2= 20 11
Solve the following LPP by simplex method: Minimize Z = 8X1 2X2. Subject to -4x1+ 2x2 1 5x1 4x2 3 and x1, x2 0. Solution : Since the given object function is of minimization type, we shall convert it into a maximization type as follows: Maximize (-z) = Maximize Z*= -8X1+ 2X2 Subject to -4x1 + 2x2 1 5x1 4x2 3 and x1, x2 0 12
By introducing non-negative slack variables s1, s2, the standard form of the LPP becomes Maximize Z*= -8X1+ 2X2+ 0s1+0s2 Subject to constraints -4x1 + 2x2+ s1 + 0s2= 1 5x1 4x2+ 0s1+ s2= 3 and x1, x2, s1, s2 0. The initial basic feasible solution is given by s1= 1, s2= 3, ( x1= x2= 0, non- basic). 13
CJ -8 2 0 0 CB YB XB X1 X2 S1 S2 Ratio * 0 s1 s2 1 -4 (2) 1 0 0 3 5 -4 0 1 - Since ( Z2*- C2) = -2 < 0 , the current basic feasible solution is not optimal 14 ZJ*- CJ 0 8 -2 0 0
