Optimizing Linear Programming Using Slack Variables
In linear programming, replacing inequality constraints with equalities using slack variables can help in finding optimal solutions efficiently. This process involves identifying basic and non-basic variables, applying pivot rules to improve the objective function, and rewriting constraints based on tight constraints. By manipulating variables strategically, the optimization process becomes more manageable and effective.
Download Presentation
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Replace all the inequality constraints by equalities, using slack variables
(x1 = 0, x2 = 0, x3 = 1, x4 = 3, x5 = 2) x5 x3 x4 x1 x2 8 constraints 5 variables (i.e., 5 dimensional space) any vertex solution corresponds to the intersection of 5 tight constraints. 3 of these are three equalities. other 2 must be xi = 0 and xj = 0 for some i,j rewrite constraints to move slack variables to the left. and write the objective function as z =
(x1 = 0, x2 = 0, x3 = 1, x4 = 3, x5 = 2) (x1 = 0, x2 = 1, x3 = 0, x4 = 3, x5 = 1) non-basic vars basic vars x5 x3 x4 x1 x2 non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable (say x2) with positive coefficient in objective which one? (pivot rule) increase its value until some other variable (x3) goes to 0 x2 enters basis, x3 exits basis. constraint for x3 >= 0 now tight constraint x2 >= 0 no longer tight Now rewrite, replacing x3 by x2 using the tight constraint.
(x1 = 0, x2 = 1, x3 = 0, x4 = 3, x5 = 1) x5 x3 x4 x1 x2 non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable (say x2) with positive coefficient in objective increase its value until some other variable (x3) goes to 0 x2 enters basis, x3 exits basis. Now rewrite, replacing x3 by x2 using the tight constraint.
(x1 = 0, x2 = 1, x3 = 0, x4 = 3, x5 = 1) (x1 = 1, x2 = 2, x3 = 0, x4 = 2, x5 = 0) x5 x3 x4 x1 x2 non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable (say x1) with positive coefficient in objective increase its value until some other variable (x5) goes to 0 x1 enters basis, x5 exits basis. Now rewrite, replacing x5 by x1 using the tight constraint.
(x1 = 1, x2 = 2, x3 = 0, x4 = 2, x5 = 0) (x1 = 3, x2 = 2, x3 = 2, x4 = 0, x5 = 0) x5 x3 x4 x1 x2 non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable (say x3) with positive coefficient in objective increase its value until some other variable (x4) goes to 0 x3 enters basis, x4 exits basis. Now rewrite, replacing x4 by x3 using the tight constraint.
(x1 = 3, x2 = 2, x3 = 2, x4 = 0, x5 = 0) x5 x3 x4 x1 x2 non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable with positive coefficient in objective if no such variable, must be at optimum.
non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable (say x2) with positive coefficient in objective If it can be increased arbitrarily, LP is unbounded
non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable (say x2) with positive coefficient in objective If it can be increased by only zero, degenerate vertex.
non-basic vars are set to 0. basic vars values are then fixed Pick a non-basic variable (say x1) with positive coefficient in objective now it can be increased What if we keep cycling in this degenerate vertices (or degenerate faces)? Solution: anti-cycling pivot rules.
Pivot rules largest coefficient largest increase steepest edge often best in practice Bland s rule (non-cycling) Random edge
