New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here

Linear Pro I

by: Loy King

Linear Pro I IOE 510

Loy King
GPA 3.76

Katta Murty

Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Katta Murty
Class Notes
25 ?




Popular in Course

Popular in Industrial Engineering

This 53 page Class Notes was uploaded by Loy King on Thursday October 29, 2015. The Class Notes belongs to IOE 510 at University of Michigan taught by Katta Murty in Fall. Since its upload, it has received 19 views. For similar materials see /class/231587/ioe-510-university-of-michigan in Industrial Engineering at University of Michigan.

Similar to IOE 510 at UM

Popular in Industrial Engineering


Reviews for Linear Pro I


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/29/15
51 Duality Theory Optimality Conditions Katta G Murty lOE 510 LP U Of Michigan Ann Arbor We only consider single objective LPs here Concept of duality not de ned for multiobjective LPs Every LP has another LP called its dual which shares the same data and is derived through rational economic arguments ln this context the original LP called the primal LP Variables in the dual problem are different from those in the primal each dual variable is associated with a primal constraint it is the marginal value or Lagrange multiplier corresponding to that constraint Example Primal Fertilizer Maker s Problem FERTlLlZER MAKER has daily supply of 1500 tons of RM 1 1200 tons of RM2 500 tons of RM 3 She wants to use these supplies to maximize net pro t DETERGENT MAKER wants to buy all of fertilizer maker s 106 supplies at cheapest price for his detergent process Suppose he offers 7r1ton for RMl 7r2ton for RM2 7T3t011 for RM3 These prices are the variables in his problem Total payment comes to 15007r1 12007r2 5007r3 which he wants to minimize FERTILIZER MAKER vvonlt sell supplies unless detergent makerls prices are competitive With each of hi ph lo ph processes Hi ph process converts a packet of 2 tons RM 1 ton RMQ and 1 ton RMS into 15 pro t In terms of detergent makerls prices the same packet yields 27r1 m 7T3 So she demands 27m 7r2 7T3 Z 15 for signing deal Similarly by analyzing lo ph process she demands 7r17r2 Z 10 to sign deal From these economic arguments we see that detergent makerls problem is 107 Dual Associated primal activity Minimize 15007r1 12007r2 5007r3 subject to 27m 7r2 7r3 gt 15 Hi ph 7T1 7r2 Z 10 lo ph 7T1 7T2 7T3 2 0 From arguments we see that if dual problem has unique opt sol it is the marginal value vector for primal 108 54 Procedure for Writing Dual of a General LP 1 Arrange all the constraints in the form of a detached coef cient tableau Here constraint means 0 any condition involving 2 or more variables 0 any nonzero lower bound or upper bound condition on a single variable Hence only conditions not counted as constraints for this purpose are nonnegativity or nonpositivity restrictions on in dividual variables Suppose jj 1 to n are prinial variables and A is the column of ij in this tableau Let c be the coeff of 3 in the primal obj function Let b be the RHS constants vector in this tableau Any prinial variable for which a lower and an upper bound re striction are included among the constraints above is treated as an unrestricted variable 109 2 De ne right type of inequality to mean 0 Z inequality in a minimization problem 0 g inequality in a maximization problem Otherwise inequality constraint called wrong type 3 Associate a separate dual variable for each primal constraint above Let 7r denote row vector of dual variables in proper order 4 ln dual problem 0 dual variables associated with primal equality constraints are unrestricted in sign 0 dual variables associated with right wrong type of pri mal inequality constraints are nonnegative nonpositive variables 5 The dual objective function is 7Tb lf primal ia a minimization problem dual is a maximization problem and vice versa 6 There is one dual constraint for each primal variable The one associated with 7 is 110 o WAj cj if ij is an unrestricted prinial variable 0 WAj 9 Q7 if ij is a sign restricted prinial variable where 9 denotes the right wrong type inequality for dual problem if ij is a nonnegative nonpositive variable 111 57 Complementary Pairs In A Primal Dual Pair Let P D be a primal dual pair of LPs lf ij is a sign restricted variable in P there is an inequality constraint in D associated with it let sj denote the nonnega tive dual slack variable corresponding to it Then 937 sj is a complementary pair in P D Where 937 is 3c 36 if it is a nonnegative nonpositive variable in Similarly if 7r is a sign restricted dual variable it is associated with a primal inequality constraint in Whichever is nonnega tive and the nonnegative primal slack variable corresponding to it also form a complementary pair in P 112 Examples Min z 31112 15333 10 4335 5756 subject to 561 2362 353 2364 365 16 17 32 43456 2 3 264 5 1 7 2 O for allj Minimize ZC subject to ASE b 513 o Minimize Z 661 7362 subject to 1 2 3 10 3273 Z 13 SC o 113 Minimize Z 03 subject to A33 6 Minimize Z 03 subject to A3 336 114 Duality Theory 1 Farkas Lemma Theorem of Alternatives for Lin ear Constraints Including Inequalities For any AW b E R either system 1 has a feasible solution 13 or system 2 has a feasible solution 7r but not both A3 I lt1 6 Z 0 WA 3 0 lt2 7Tb gt O This is a special case of the separating hyperplane theorem for two dtsjotnt convex sets The main duality theorem of LP can be proved as a corollary of Farkas7 lemma and vice versa 115 2 Dual of the dual is the primal 3 Duals of equivalent LPs are equivalent 4 Both the primal and dual problems could be infeasible EXAMPLE Minimize Z 261 4362 subject to 5131 332 1 12 2 6 Z O 5 Weak Duality Theorem ln a primal dual pair if primal is the minimization problem with objective function Zlt IZgt and dual is the maximization problem With objective function Ult7r then for all primal feasible solutions 13 and dual feasible solutions 7r gt v7r Corollaries 116 i The primal objective value at any primal feasible solution is an upper bound for the maximum objective value in the dual ii The dual objective value at any dual feasible solution is a lower bound for the minimum objective value in the primal iii lf primal is feasible and z gt oo in it dual must be infeasible iv lf dual is feasible and v gt oo in it primal must be infeasible v SUFFlClENT OPT CRITERlON FOR PRIMAL DUAL PAlR lf in is primal feasible 7 is dual feasible and z Ult7Tgt then 3 is opt for primal and 7 is opt for dual EXAMPLE Fertilizer problem 3 300900T 7T 5 5 0 EXAMPLE A diet problem 3 OOOO52T 7T 378 117 1 2 333 4 5 6 102212 gt9 013132219 35 30 6O 5O 27 22 zmin 7 2 O for all j 6 Duality Theorem 01 LP ln a primal dual pair of LPs if one has an opt sol the other does also and the two optimum objective values are equal 7 ln a primal dual pair of LPs if one of the problems is feasible and has the objective unbounded then the other problem is infeasible 8 COMPLEMENTARY SLAOKNESS THEOREM ln a primal dual pair of LPs let 8 7 be primal and dual feasi ble respectively They are optimal to the respective problems iff at least one quantity in every complementary pair is O in them OS THEOREM FOR STANDARD FORM Am 118 Primal mm 2 03 subject to A3 b 6 Z 0 Dual max 1 7Tb subject to WA 3 c C pairs are 7 j cj WAJ j 1 to 71 CS THEOREM FOR SYMMETRIC FORM Amxn Primal mm 2 03 subject to A3 2 b 6 Z 0 Dual max 1 7Tb subject to WA 3 c 7r 2 O C pairs are 7 j Cj TI39AJ39 j 1 to n and 7r Aw bj 239 1 to m 9 NBC amp SUE Opt COHdS 101 LP A feasible sol in to an LP the primal is optimal iff there exists a dual feasible solution 7 which satis es the C S Coriols With it Can also be proved from Farkas7 lemma 119 Example Consider the feasible solution in 6 O 1 O 2T for the LP min z 31 2 3363 565 s to 12 324 5 Z 5 21 2363 4 365 2 8 61 Z 6 3234 Z 5 53 475 Z 7 9 Strict Complementary Blackness Theorem Suppose a primal dual pair of LPs have optimum solutions Then there exist optimum solutions to the two problems in which exactly one variable in every complementary pair is zero and the other is positive 120 525 LP in Standard Form Primal and Dual Feasibility Of Basic Vectors Consider the LP in standard form for which the original tableau given below Original Tableau Basic 51 mm scmH Urn z 5131 all 11m 017m1 am 0 b1 scm aml amm am7m1 amn O bm z 01 cm cmH an 1 O A basic vector 133 1 ajm say and the associated basis B are said to be 121 Primal feasible lf the primal basic solution wrt 3 is primal feasible ie Z O ie if B lb Z 0 Dual feasible Dual basic sol obtained by solving sys tem of dual constraints corresponding to basic variables in 133 as a system of eqs ie 7TB 63 So dual basic sol is 7r 03371 This de nition guarantees that the pri mal amp dual basic sols wrt a basic vector always satisfy CS conds 333 said to be dual feasible if the dual basic sol satis es other dual con straints ie if dual slacks Cj 71144 relative cost coeffs wrt 333 are all 2 0 Optimal lf it is both primal and dual feasible So dual feasibility cond for a basic vector same as Opt cond in primal simplex algo 122 Example 1 2 3 4 335 336 z b 1 2 3 2 1 16 0 17 0 1 4 1 1 1 0 2 0 0 1 2 1 0 0 1 311 1510 4 571 0 schOforallj 1111112 1 2 11 0 0 1 4 0 1 2 3 Inverse tableau 0 0 1 0 3 5 4 1 143 13 516 0 116 0 116 0 4 5 6 Inverse tableau 124 23 33 0 5116 6 8316 1 123 To Check Optimality of a Given Feasible Solution Say 3quot Write all equality constraints that dual variables have to satisfy if 3 were to be primal opt from the CS conds lf these equality constraints have a unique sol 7 say and it satis es all other dual constraints then 3quot 7 are respectively prinial and dual opt Example Check whether 3 12 7 2 1 OT is opt to fol lowing LP 331 332 333 334 335 H D D H 00 Q3 00 00 O 6 9 5 10 25 z minimize 27113027520 Example Check whether 3 10 5 O O OT is opt to fol lowing LP 124 1 2 3 4 565 b 2 1 1 2 1 25 2 O 2 1 3 2O 8 6 1O 2O 2 za minimize 1 to 5 2 0 Example Check Whether in 1O15OOOT is opt to following LP 1 2 3 4 565 b 1 O 1 2 1 10 O 1 1 2 2 15 1 1 1 1 1 25 1 4 2 4 2O za minimize 1 to 5 2 0 Theorem lf LP in standard form has a nondegenerate opt BFS dual optimum is unique and it is the marginal value vector for the primal Theorem Any algorithm for solving linear inequalities With out any optimization oan be used to solve an LP directly 125 520 How to Check if an Opt Sol to LP ls Unique Consider LP in standard form min 2 63 subject to A3 b 13 Z 0 Where Amxn and rank m Suppose SE is an opt sol ll 56 is not a BFS obviously the prob lem has alternate optima All feasible solutions obtained during puri cation process to obtain a BFS from in are alternate optima Suppose SE is a BFS Let 3 1 mgt be an optimum basic vector corresponding to 3quot ll relative cost coeffs of nonbasics mH 5 are all positive by CS theorem in is the unique primal optimum solution lf some nonbasic rel costs say mH cm are zero and the others are positive By CS Theorem any feasible solution So With mr1 6 O is optimum to the primal bringing any of the nonbasics mh mm into 5133 leads to an alternate opt BFS if the pivot step is nondegenerate To check if an alternate optimum exists we could x mrh 126 73371 01 O R Katta G Murty lOE 510 Lecture slides Introductory Lecture Operations Research is the branch of science deal ing with techniques for optimizing the performance of systems System is any organization large or small Performance Measure Any criterion measuring the way system is working that is considered important For example if system is a company some important performance measures are total yearly pro t market share etc Optimizing A Performance Measure Performance mea sures are of two types PROFlT MEASURE is one for which the higher its value the more desirable it is COST MEASURE is one for which the lower its value the more desirable it is Optimizing a performance measure means maximizing it if it is a pro t measure or minimizing it if it is a cost measure Optimization involves Maximization or Minimiza tiOH as desired To optimize implies Decision making to deter mine best operating conditions of system that yield best values for performance measures llain function of O R gt Tool for decision making Optimization is main pillar of O E Everyone is interested in Optimization O R Techniques Multicriteria Decision making To chose the best among a small number of alternatives when there are many important characteristics to consider Linear Programming To optimize a single linear objective function subject to linear constraints A technique With many applications Network Programming Optimization problems that can be described over a graph structure Many applications in trans portation distribution etc Dynamic Programming Technique for solving multi period or multi stage decision problems CPM for Project Scheduling Techniques for controlling scheduling various jobs in a project which have to obey a prece dence relationship Integer and Combinatorial Optimization Techniques for solving mathematical models involving discrete decision vari 3 ables Nonlinear Programming Techniques for solving mathe matical models involving nonlinear functions Mathematical Programming lncludes linear network integer combinatorial and nonlinear programming Multi objective Programming Techniques for obtaining good solutions to optimization models involving two or more ob jective functions that need to be optimized simultaneously Goal Programming is one technique for solving multi objective programs Inventory Management Techniques for maintaining inven tories to meet demands for goods While at same time minimizing inventory holding costs Queing Problems To optimize performance of systems in volving waiting lines Simulation Techniques for modeling the operations of a sys tem through computer simulation Algorithms Many of the problems in O R are solved using procedures called algorithms An Algorithm fOI a Problem is a systematic step by step procedure for solving the problem HlStOI y Word comes from title of Latin translation Algoritmz de Numem Indorum meaning Al Khwarzmz Concerning the Hindu Art of Reckon ing written in 825 AD by Arabic Scholar Muhammad lbn Musa Al Khvvarizmi Who lived in lraq lran mostly Bagdad based on earlier lndian and Arabic treatizes Algorithms seem to have originated in work of ancient lndian mathematicians on rules for solving linear and quadratic equa tions An Example Problem lnput Given Positive lnte ger 71 Find all primes g n Eratosthenes Sieve 3rd century BC Step 1 Write all integers 1 to n Strike off 1 and set a pointer at 2 the rst prime General Step Suppose pointer now on 7quot Counting from 7quot strike off every Tth number to right lf all numbers to right of 7 now struck off all numbers not struck off are all primes g n terminate Otherwise move pointer right to next number not struck off and repeat this general step with pointer in its new position EXERCISE n 15 Classi cation of Optimization Problems Optimization Problem To select best among avail able alternatives Category 1 Number of available alternatives very small Usually solved by a 8007 an Method Category 2 No of alternatives nite but large ln teger amp combinatorial optimization problems belong to this cate gory Category 3 Number of alternatives 00 Continuous variable problems linear and nonlinear optimization problems belong to this category For category 2 3 problems we need to construct a llathe matical Model for the problem and solve it using an ef cient algorithm Decision Making by Quantitative Analysis For problems which are very important or very complex good solutions cannot be developed without the aid of quantitative analysis Quantitative analysis requires the representation of the problem using a mathematical model Mathematical modeling is a criti cal part of the quantitative approach to decision making Con structing mathematical models to represent real world problems reasonably closely is an essential skill for all engineers Two types of factors effecting system performance 0 Uncontrollable factors Factors such as environmental factors not under the control of the decision maker 0 Controllable inputs Factors whose values can be con trolled by the decision maker which affect the functioning of the system These factors are called the decision variables in the model Deterministic models lf all uncontrollable inputs are known 8 exactly and do not vary system performance depends only on val ues of decision variables model becomes a deterministic model No uncertaity Stochastic OI Probabilistic models When uncontrollable inputs are uncertain and subject to variation Here system per formance uncertain even when the values of all decision variables are xed We study deterministic models in this course Steps in Decision Making by Quantitative Analysis Model Building Build a mathematical model that represents how system functions identify decision variables constraints on them and objective function that measures system per form an ce Solve Model Use an ef cient algorithm to get an optimum solution Implement solution or Update Model 85 Repeat Check solution for practical feasibility lf it is not make necessary changes in model amp repeat Also many times decision makers use their practical knowl edge to transform optimum solution into an implementable solution Early History of Related Topics Linear Algebra Branch of Math dealing with Systems of linear eqs Note No inequalitiesl Example Steel company has four scrap metals SM 1 to Sll 4 with following compositions Type in type by weight of element Al Si C Fe Sll 1 5 3 4 88 Sll 2 7 6 5 82 Sll 3 2 1 3 94 Sll 4 1 2 1 96 Need to blend into a mixture with composition by weight Al 443 Si 322 C 389 Fe 8846 Determine how to prepare this mixture Elimination Method for linear eqs developed by 3rd century BC by Chinese amp lndian mathematicians Unknown in Europe until C F Gauss discovered it 19th cen 11 tury While studying linear eqs to approximate orbit of asteroid Ceres using Method of least squares W Jordan discussed this method in a book he wrote 1888 Hence method called GJ Elimination method A better version called G Elimination method Both GJ amp G methods cannot directly handle inequalities Linear Programming LP Methods for handling systems of linear eqs amp ineqs Started With Farka7s Lemma Fundamental theoretical result on linear ineqs 1901 G B DantZig7s Simplex Method to solve LPs 1947 So LP a 20th century topic All methods for LP are iterative methods requiring sol of 2 systems of linear eqs in each iteration GJ Method for Solving Linear Eqs Consider system 1 A3 b where coef cient matrix A is m x 71 matrix amp RHS vector bERm Matrix A awan Started as a convenient way to represent the coe icients in a system of linear equations Matrices and matrix algebra introduced by J J Sylvester and Cayley in 1840s AZ 2th row vector of the matrix A i 1 to m Atj jth column vector of the matrix A j 1 to 71 Unit or Identity Matrix 1 O O O 1 O O O 1 Permutation Matrix One Whose rovvs can be rearranged to 13 become the unit matrix 0 1 O O O 1 1 O O Amxn Products 0 A33 de ned only if 13 is a column vector in R 0 WA de ned only if 7r is a row vector in H Main Computational tools Row Operations 1 Multiply a row by a nonzero scalar 2 Add a scalar multiple of a row to another 3 lnterchange two rows Example A1 1 0 3 5 A2 0 I 2 4 12lA1 142 5141 Gauss Jordan Pivot Operation or Pivot Step Speci ed by specifying the pivot column and pivot row IMPORTANT CONDITION Pivot Element element in the pivot row and the pivot column should be nonzero The OJ Pivot operation consists of a series of row operations to convert pivot column into unit column with 1 entry in pivot TOW Example Here PO pivot column PR pivot rovv 6 4 4 O6PR 10 13410 History Developed as a tool for solving systems of linear equations by the Elimination method Example 171 172 173 2 2 2 12 1 O 1 1 Constraints in 1 correspond to rows of coef cient matrix A System 1 in constraint representation is AZ C bz39 1130 m Multiply 2th constraint by 7r 139 1 to m and add This leads to linear combination 2 27117T A 231 7gb lf 3 271 79A O the O row vector 231 7gb 1 then 2 is the inconsistent eq 0 1 So if7r 7T1 7rm satisfying 3 exists 1 has no sol 3 ln matrix notation 3 7rA O 7Tb 1 Theorem System 1 has no solution 1 iff 3 has a solution Both these systems 1 3 can be processed simultaneously by the Gauss Jordan GJ method applied on system For this it is convenient to record 1 in the form of a detached co ef cient tableau The GJ niethod tries to carry out a GJ pivot step in each row of this tableau With the aim of creating a unit subniatrix of order m on its left hand side ln this process at each stage each row in the current tableau Will always be a linear combination of rows in For each row vector in the current tableau the coef cients in this linear combination Will be denoted by a row vector u M1 um These u vectors for the var ious rows in the current tableau are stored and updated under a memory matrix These u vectors for the various rows in the original tableau are the unit vectors in H These are recorded in the original tableau before beginning the application of the GJ niethod Memory matrix Original tableau 7T1 7r2 mm 331 332 6 l O 0 an 112 a1 1 O l O 121 122 121 2 O O 1 am amg amn bm Coeff vector for expressing the row on the right of this memory matrix as a linear combination of rows in the original tableau Carrying out all the computations involved in the pivot steps also on the columns of the memory matrix updates it Here is a summary of the method 1 Select the order in Which rows 1 to m in the tableau are to be chosen as pivot rows 2 General Step Suppose row 7 is the pivot row for the pivot step in the present tableau Let it am ET be the coe icients of the variables and the updated RHS constant in row 7 in the present tableau 19 21 22 lf 611 am y 0 select a variable m for a j such that am y O as the basic variable in row 7quot and the column of Zn in the present tableau as the pivot column and perform the GJ pivot step lf row 7 is the last pivot row in the selected order go to 3 if 23 given below has never occurred so far lf row 7 is not the last pivot row in the selected order With the resulting tableau go back to 2 to perform a pivot step With the next pivot row in the selected order lf 5m am O and ET 0 this row is called the O 077 equation This indicates that the constraint in the original system 1 corresponding to this row is a redun dant constraint and can be eliminated Without changing the set of solutions lf row 7 is the last pivot row in the selected order go to 3 if 23 given below has never occurred so far lf row 7 is not the last pivot row in the selected order With the present tableau go back to 2 to perform a pivot step With the next pivot row in the selected order 20 23 lf ar1am O and ET y 0 this row is called the O oz equation for oz 3T y O or an inconsistent or infeasible equation ln this case the original system 1 has no solution If 11 gm is the row in the memory matrix in row 7quot in the present tableau then 7 15T 1 m is a solution of the alternate system lf it is only required to either nd a solution to 1 or de termine that it is inconsistent the method can terminate here 3 Make all the nonbasic variables in the nal tableau equal to O and the basic variable in each row equal to the updated RHS constant in that row in the nal tableau This is a basic solution to 1 terminate EXAMPLE 1 131 132 133 134 135 101210 1 2 5 1 4 2O 2 O O 2 1 25 3 2 5 3 5 45 5 2 5 5 6 7O EXAMPLE 2 1 2 3 RHS 1 1 5 1 3 1 6 O 4 2 11 2 3 1 1O EXAMPLE 3 81 Marginal and Sensitivity Analyses Katta G Murty lOE 510 LP U Of Michigan Ann Arbor Winter 1997 Consider LP in standard form min 2 03 subject to ASE b 13 Z 0 Where Amxn and rank in Theorem lf this LP has an optimum nondegenerate BPS then its dual opt sol is unique and it is the marginal valve vector for this LP Theorem lf this LP has an optimum sol but no optimal nondegenerate BPS then the dual opt sol may not be unique ln this case marginal value vector may not exist but positive and negative marginal valves exist for each bi They are Positive MV wrt b Max7r over dual opt sols 7r Negative MV wrt bi Min7r over dual opt sols 7r Let fltbgt denote the optimum objective value function as a func tion of the RHS constants vector 9 fltbgt de ned only over I E PosA 159 lf 00 for some I E PosA then it is 00 for all I E PosA Positive Homogeneity lffb nite for some I then f0 O and fb fb for all Z O ConveXity fltbgt is a piecewise linear convex function de ned over PosA Subgadient Property Let 7T1 be a dual opt sol when l 1 Then fltbgt Z 7r1b for all I E PosltAgt ie 7T1 is a subgradient of at 1 160 82 Sensitivity Analysis Also called Post optimality analysis Deals with ef cient tech niques for nding new opt when small changes occur in data Consider LP in standard form min 2 03 subject to ASE b 13 Z 0 Where Amxn and rank m Example Original tableau 1362 563 4 5 66 z b 12010 6 C 11 O 1 1 3 2 1 O 6 1 2 1 3 1 5 C 13 32 3 610 510 scj Z O for allj min 2 161 Optimum Inverse tableau Basic Inverse tableau Basic var values 61 1 2 2 O 3 2 1 1 1 O 4 333 1 O 1 O 2 z 2 4 1 1 11 We assume that we have an opt inverse tableau for the prob lem Let 5133 be the present opt basic vector and 8 7 the primal and dual opt sols Cost Coef cient Ranging This nds the optimality interval for each original cost coef cient OPTIMALITY INTERVAL OF A DATA ELEMENT Set of all values of that data element as it varies in the tableau but all other data remains xed at current values for which the present opt basic vector or present opt sol remain optimal 162 1 Nonbasic Cost Coef cient Ranging Let ij be a present nonbasic variable cj cost coeff of 7 which may change from its present value While all other data remains xed at current values With this change the only thing that Will change is the rel cost coeff of 7 j cj 711441 j remains Z O as long as cj Z 714439 So optimality interval for cj is fl14439 lf cj becomes lt 714439 enter my into 333 and continue simplex iterations until termination again Example Find range for 05 Find new opt sol if 65 changes from present 10 to 6 Cost Ranging a Basic Cost Coeff Let mp be a basic variable in the present opt basic vector 13 B lf its cost coeff cp changes the dual sol changes So to compute opt interval for cp do the following 0 In 63 replace cost coeff of basic var mp by parameter 0p 163 and denote it by 03Cp op dual basic sol as a function of cp CBCPB 1 Each component of Map is an af ne function of 0p ie has 0 1 the form 790 610791 where 79 79 are constants Now compute each nonbasic relative cost coeff Q as a func tion of 0p it is given by 57 Cj CplAj Again each of these is an af ne function of 0p Express the cond that all these rel cost coeffs must be 2 O This yields the opt int for 0p To get new opt sol When cp changes to a value outside its opt interval compute all nonbasic cp and if some of them are lt 0 select one of the corresponding variables as the entering variable and continue the application of the simplex algo Example Find opt range for 61 and new opt if 61 changes to 5 164 Ranging RHS Constants Optimality interval for an RHS constant b set of all values of b for which present opt basic vector 133 rernains opt as b varies While all other data remains xed at current values To nd opt int for a bi replace its present value in RHS constants vector 9 by paranieter bi and denote it by 90 The basic values vector as a function of bi is B 4191 Each component of this vector is an a ine function of by EX press the cond that each of them must be 2 0 this yields the opt int for by As b varies in its opt int the dual opt sol rernains un changed but the primal opt sol is given by Nonbasic variables 0 Basic vector B 1bb opt obj value 7Tbltb lf new value of bi is outside its opt int to nd new opt sol 165 use dual simplex iterations Example Find opt range for 1 and new opt sol when 1 changes to 15 Ranging Input Output Coeffs in a Nonbasic col Let my be a present nonbasic variable and azj an input output coeff in its original column Aj To nd opt range for aw replace its present value in the column Atj by the parameter aw and call it 144mg Then express the condition that the relative cost coeff of my azj Cj Aa lazj 2 0 This yields the opt int for aw lf azj changes to a value outside its opt int to get the new opt sol enter ij into the present basic vector 13 B and continus the application of the simplex algo To Introduce a New Nonnegative Variable Find the rel cost coeff of new variable wrt present opt basic vector 3 166 lf this is Z O extend in by including new variable at O value this is the new opt sol lf rel cost coeff of new var lt 0 bring it into 13 B and continue the application of simplex algo Example lnclude 7 2 O with col vector 1 2 3 E 7T What happens if cost coeff of new variable is 10 instead of 7 Introducing a new Inequality Constraint Let new constraint be Altm1gt aquot g bmH lf present opt sol 3 satis es it it remains opt terniinate lf 3 violates it let n1 be the nonnegative slack var cor responding to new inequality Construct inverse tableau corre sponding to basic vector 133 n1 This basic vector is prinial infeasible to augmented problem but dual feasible Apply dual simplex iterations to get new opt 71 B 0 Bi1 0 a 1 aB 1 1 167


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


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'

Why people love StudySoup

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.