Popular in Course
Popular in Industrial Engineering
This 7 page Class Notes was uploaded by Dr. Jamel Schultz on Monday October 26, 2015. The Class Notes belongs to IE2082 at University of Pittsburgh taught by Staff in Fall. Since its upload, it has received 55 views. For similar materials see /class/229409/ie2082-university-of-pittsburgh in Industrial Engineering at University of Pittsburgh.
Reviews for LINEAROPTIMIZATION
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/26/15
IE 2082 Simplex Algorithms l Brady Hunsaker August 30 2006 IE 2032 Sim plex Algorithms August 30 2006 Simplex algorithm 0 Uses the general method of the previous lecture 0 Only considers certain solutions called basic feasible solutions 0 Algebraically Divide variables into a set of basic variables and a set of nonbasic variables Set each nonbasic variable to one of its bounds lower bound or upper bound and solve for basic variables to satisfy constraints 0 Geometrically The set of feasible solutions is a polyhedron and basic feasible solutions are extreme points of the polyhedron 0 Issue Is it sufficient to consider only basic feasible solutions IE 2032 Sim plex Algorithms August 30 2006 Convert to standard form Standard form for LPs is the following o Maximization problem 0 Only 3 constraints and nonnegativity constraints 0 All variables nonnegative We use standard form to help us understand the algorithm but most implementations do not actually do it this way IE 2032 Sim plex Algorithms August 30 2006 Standard form with slack variables added max C1X1 C2X2 Can 515 a11X1 a12X2 31an W1 191 a21X1 322X2 39 39 39 32an W2 192 amlxl am2X2 l39 l39 3man l39 Wm bm X17X277Xn Z 0 W17W27Wmgt0 IE 2032 Sim plex Algorithms August 30 2006 Notations different points of view We will use several alternative notations in this course Think of them as different ways of expressing the same idea 0 Ellipsis a1X1 a2X2 aX7 g b n 11 o Summation Z ainj g b 0 Matrixvector aX g b or AX g b for all the nontrivial constraints IE 2032 Sim plex Algorithms August 30 2006 Bases and dictionaries To get a dictionary solve the system of equations not including nonnegativity for m variables in terms of the other variables It is easy to solve for the slack variables max C clxl C2X2 cnxn 513 W1 2 b1 311X1 312X2 alan W2 192 a21X1 322X2 39 39 39 aZan Wm bm amlxl am2X2 aman X17X277Xn Z O W17W277Wm Z O This system has the same optimal solutions as the previous system IE 2032 Sim plex Algorithms August 30 2006 Bases and dictionaries For now we will not differentiate between slack variables sometimes called auxiliary variables and original variables sometimes called structural variables max C C1X1 C2X2 cX7 51 Xnl b1 a11X1 a12X2 39 39 39 a1ner Xn2 192 a21X1 322X2 39 39 39 32an Xnm bm amlxl am2X2 aman X17X277Xnm Z 0 IE 2032 Sim plex Algorithms August 30 2006 Basic solutions 0 We associate each dictionary with a basic solution 0 The In variables we solved for are the basic variables The other variables are nonbasic variables 0 Set each nonbasic variable to one of its bounds 0 In this case variables have lower bounds of O and no upper bounds so all nonbasic variables are set to zero Later in the course we will consider the more general case 0 Then it is easy to determine the values of the basic variables Is the resulting basic solution feasible 0 In determining the values of basic variables we ignored any lower and upper bounds on the variables The basic solution is a basic feasible solution if all basic variables satisfy their bounds IE 2032 Sim plex Algorithms August 30 2006 General form of a dictionary Let B be the set of basic variable indices and N be the set of nonbasic variable indices C C ZEJXJ jeN X B EB jeN The bars are placed over coefficients because their values are not the same as the initial values IE 2032 Simplex Algorithms August 30 2006 o y 14 Optimality conditions 0 Remember the second step of the general method Is this solution good enough 0 How can we tell whether a basic feasible solution is optimal 0 Look at the row in the dictionary with the objective value C 5 ZEN ijj o The objective value of the current bfs is IE 2032 Sim plex Algorithms August 30 2006 10 i 14 Optimality conditions continued The current solution is optimal if Ej g 0 for all 6 N Proof The current dictionary is a set of equations satisfied by every feasible solution to the LP In particular every feasible solution to the LP satisfies C C ZEN By nonnegativity no value OfXj can be less than zero so the best objective value we can hope for is C The current bfs achieves this objective value and is therefore optimal D The values are called the reduced costs of the variables IE 2032 Sim plex Algorithms August 30 2006 11 i 14 Finding a better solution Simplex pivot 0 If the current bfs is not optimal then choose an entering variable This can be any nonbasic variable with E gt 0 Let the entering variable be Xk o Xk will enter the basis and force another variable to leave the basis The leaving variable is chosen so that the resulting basic solution is in fact a bfs That is we must preserve feasibility o The effect of the pivot is that the value of Xk will increase from O to some positive value while all the other nonbasic variables remain at zero Therefore we can consider only the part of the dictionary with Xk For a basic variable X we have X 3 aikxk How much can we increase Xk before X violates feasibility IE 2032 Sim plex Algorithms August 30 2006 12 i 14 Simplex pivot continued Punchline choose leaving variable X such that is maximal I A is minimal alk Equivalently choose X such that am gt O and This is called the ratio test Note that the choice of entering variable and leaving variable may not be unique So the simplex algorithm is really a family of algorithms each with its own pivot rules to select an entering and leaving variable After choosing the entering and leaving variable solve the leaving variable39s equation for the entering variable Then plug this value for the entering variable into all the other equations to get the new dictionary IE 2032 Sim plex Algorithms August 30 2006 Pivot practice IE 2032 Sim plex Algorithms August 30 2006 14 y 14
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'