### Create a StudySoup account

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

Already have a StudySoup account? Login here

# LINEAR AND COMBINATORIAL OPTIMIZATION MA 515

UK

GPA 3.54

### View Full Document

## 21

## 0

## Popular in Course

## Popular in Mathematics (M)

This 38 page Class Notes was uploaded by Kennith Herman on Friday October 23, 2015. The Class Notes belongs to MA 515 at University of Kentucky taught by C. Lee in Fall. Since its upload, it has received 21 views. For similar materials see /class/228140/ma-515-university-of-kentucky in Mathematics (M) at University of Kentucky.

## Reviews for LINEAR AND COMBINATORIAL OPTIMIZATION

### 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/23/15

1 Basic De nitions De nition 11 Lot 3quot trquot 6 R4 and l E R Tht n t2quot Altr39 t t t t2quotquot is 11 l a lincai combination 016ml t2quot 2 an a inc combination 015er Jquot if I t t t 1 3 a nonncgatii39c combination 0163quotVrquot if I 2 0 1 a COH I CT combination of 3quot trquot if I t t t l and l 2 0 Remark 12 For 3quot trquot 6 Rd writs and l 21 Jan 1 n also 11 Tht n tht four cascs in tht ahovt lt nition can ht t Kprt sst d rt spt ctivt ly as 3 t2quot AA 2 O 1 Am 2 2 De nition 13 Lot 3quot trquot 6 R4 39I hcn 3quot trquot is l lincai lg dcpcnrlcnt if 3A1 E R not all Zt ro such that Altrl t t t t2quotquot O Otht rwist 3quot t2quotquot is lincai lg inrlcpcnrlcnt 2 a incly dcpcnrmt if ll E R not all Z0ro such that l3quot 3quotquot O and l i i i 0 Oth0rwis0 3quot 3quotquot is a incly ilirQMirmt Theorem 14 I 3quot 3quotquot g R4 is lilicarly dcpmrmit thch mists am of tho 3quot that can 6 CT prcsscrl as a lilicar combination of tho atIcrs x3 3quot 3quotquot g R4 is a incly dcpmirmit thch mists am of tho 3quot that can 6 CT prcsscrl as an a inc combination of tho atIcrs Pnoor 11K0rcis0 El Theorem 15 Lat 5 3quot 3 quot g R4 and dc nc x1 and 4 as in Hmnark 72 I 5 is lilicarly ilircpmirmt rank x1 n i clim E Rquot 31A O 0 In particular 77 gt 1 than 5 is lilicarly dcpcnrlmt ranka n i clim E Rquot 31 O 0 In particular ncly dcpcnrlmit x3 5 is a incly ilircpmrmt n gt 11 than 5 is a Pnoor 11K0rcis0 El Exercise 16 3 03quot3 quot g R4 is a in0ly incl0p0ncl0nt in 3quot 3 03quotquot 30 is lin0arly incl0p0ncl0nt De nition 17 10t 5 g R4 1 5 is a lilicar sct or subspacc if 5 75 Q and V3quoty E 5 VA E R 3quot y 6 10 b is non0mpty in particular 5 contains 0 and clos0cl uncl0r all lin0ar combinations of two 0l0m0nts 2 5 is an a inc sct a inc spacc or at if V3 y E 5 VA E R such that l 3quot y 6 10 5 is clos0cl uncl0r all a in0 combinations of two 0l0m0nts 3 5 is a caliper cam if 5 75 Q and V3quoty E 5 V nonn0gatiV0 6 R 3quot y 6 10 5 is non0mpty in particular 5 contains 0 and is clos0cl uncl0r all nonn0gatiV0 combinations of two 0l0m0nts 1 5 is a COH I CT sct if V3 y E 5 V nonn0gatiV0 6 R such that l 3quot y E 10 5 is clos0cl uncl0r all conVOK com hinations of two 0l0m0nts Renlark 18 W oftt n but not always rm k r t0 It mt nts of Iint ar subspact s and Coth x Cont s as I CCtOI S and It mt nts of af nt and Coth x scts as points Theoreln 19 Lct AKC rlcnotc tbc colaction of all lincar subspaccs a inc scts concs and conI39m scts rcspcctii39cly ofRJ 17an g C and K g C and tbcsc inclusions arc strict Fart76 A 0 K L Pnoor Exorcism El Exercise 110 Classify tho ibllowing st ts 2quot E R4 S l 2 E R4 1772 1wht r00 75 a E R4 and n E R Such a sot is callcd a bypm planc 2 E R4 Mm O wht rt M is an n X 1 matrix i i 1 2 E R4 Maquot S O wht rt M is an n X 1 matrix 2 E R4 Mm b wht rt M is an n X 1 matrix and b E Rquot i 2 E R4 Maquot S b wht rt M is an n X 1 matrix and b E Rquot Theorem 111 Lot 5 g Rd 7 5 is a lincar subspacc 5 75 Q and 5 is closcrl 39unrlm lincar combinations of nitc n39umbm s of I CCtOI s in 7 9 is an a inc sct 5 is closcrl 39unrlm a inc combinations of nitc n39umbcrs of points in 5 is a conc 75 Q and 5 is closcrl 39unrlcr nonncgatii39c combinations of nitc n39umbcrs of I CCtOI S in 5 is a COH I CT sct 5 is closcrl 39unrlcr COH I CT combinations of nitc n39umbm s of points in Pnoor Exorcism El Theoreln 112 Lct 5 bc a noncmptg subsct of R4 Than 5 is an a inc sct tbm c mists a lincar subspacc I of R4 and a point 3 such that 5 I y ic 5 2quot y 2quot E L In this cast I is 39uniq39uc and y can bc cboscn to bc any particular point of Pnoor Exorcism El Theorem 113 Lct 5 g Rd 9 is a lincar subspacc 5 is a sat of thc farm 3quot E R4 Mm O for sonic n X I N matrir M in 5 is an a inc sct is a sat of iICfOI W 3quot E R4 Mm b for sonic n X I mati ir M 39s IZOIZCI771i l than in this cast 5 L y IUIICI C y is any particular and I E Rquot If paint in 5 and L 3quot E R4 Maquot O Pnoor Exorcism El Relnark 114 Not all Conos aro of tho form 3quot E R4 Maquot S O Thoso that aro aro callod comma palglicrli a cancs Similarly not all mmon sots aro of tho form 3quot E R4 Maquot S b Thoso that aro aro callod cancer palyIcrli a Pnoor Exorcism El Theorem 115 I Hoary lincar subspacc is tIc intm scctian of a nitc IllWIMP of ligpm pancs containing 2 Hoary a inc sct is tIc intm scctian of a nitc IllWIMP of ligpm plancs Pnoor Exorcism El Theoreln 116 7776 intm scctian of any calaction of lincar subspaccs a inc scts cancs COH I CT scts is again a lincar subspacc a inc sct canc COH I CT sct i cspcctii39cly Pnoor Exorcism El De nition 117 Lot 5 g Rd 1 Tho lilif span of 5 span 5 is tho intorsoction of all linoar suhspacos Containing 2 Tho a inc span of 5 a 39b is tho intorsoction of all af no sots Containing 3 Tho canc of 5 pos 5 is tho intorsoction of all Conos Containing 1 The cani39m hull of 5 convb is the intersection of all convex sets containing 5 De nition 118 Let T g R4 1 1165 span 739 then we say 739 linearly spans 2 1165 a 39Y39 then we say 739 affiney spans co n v 5 is Theorem 119 Suppose 5 is a nonempty s39uhsct off Then span 5 a 39b pos s the set of all linear a inc 39 cani39m quot 39 I 71 77 af nite numbers of elements in Pnoorz Exercise El De nition 120 1165 g R51 is a nite set posb is called a nite cane and convb is called a comma palytape Theorem 121 Let 5 g Rd 7 If 5 75 O is a linear subspace then lt2 trquot E 5 such that every 3quot E 5 can he mpi csserl uniquey as a linear combination of t2quot39trquot In this ca 6 i the mar hum s 6 afa linearly independent s39uhsct afb and the mi afa s39uhsct afb that spans 5 linearly quot a t 1 Ifb 75 Q is an affine t then El uniquey as an affine combination of an affiney independent s39uhsct afb and the minimum s 5 a incly in yr 6 5 such that every 3quot E 5 can he mpi c quot he mamim39um of of a subset of b that spans trquot In this ca 6 n is Pnoorz Exercise El De nition 122 In the rst case above 3quot 3quotquot is called a basis ofb and the dimension of 5 dim 5 equals n 1 0 then dim b 0 In the second case above t2quot39trquot is called an affine basis of b and 5 is the translate L y of some linear n l dimensional subspace verify this We say that the dimension of 5 dim 5 equals 77 l n af ne set is 0 dimensional iff it is a set consisting of a single point t ne sets of dimension 1 and 2 are called lines and planes respectively Exercise 123 Let 5 be an af ne subset of H Show that 5 is a hyperplane i 39 dim 5 1 1 Qt sq 01 pauypp 10S zQLiLLIJ JLH 30 Ll0SLIJLLIP JLHJ 39JJS JUEHJK LIB 5 JOJ B Ll0SLIJLLIP 30 SLIO1LIP xng JUL JJOX 395 BBLLIEP sq 01 pauypp E5 LLIH E5 30 1101511911111 JLHJ 39PH 30 JJSqHS z1dLlJLlLl 13 5 JSOddHS HOECHHQBG 39n39 W P 5 MP Llatu lt1 z n39 H 3 r 5 75 D H 39z 39n39 aw P 5 WP Mn 0 m H 3 r 5 H 391 39HH 3 PUB XUBLLI I X U LIB JSOGdHS BSEDJBXEI 5 LLIOI LIJSOL sq U13 5 141 JO SS13q JUEHJK LIB JUL AAOLIS 5 LLIOIJ LIJSOL sq U13 5 LIBdS JO SS13q IBJU 13 JUL AAOLIS 39pH 5 5 Jo vz t asgoaaxg TWO COIN MORRA This gamo is playod by two playors H and C39 Each playor hidos oithor ono or two silyor dollars in hishor hand Simultanoously oaCh playor guossos how many Coins tho othor playor is holding 11quot H guossos Corroctly and 39 doos not thon 39 pays R an amount of monoy oqual to tho total numbor of dollars Concoalod by bot7 playors lf C39 guossos Corroctly and H doos not thon H pays 39 an amount of monoy oqual to tho total numbor of dollars Concoalod by bot7 playors 11quot both playors guoss Corroctly or incorroctly no monoy oKChangos hands Cloarly oaCh playor must doCido how many Coins to hido and what numbor to guoss Vo will uso tho notation 12 to moan that a playor hidos 1 dollar and guossos 27quot 39quoto can roprosont tho possiblo outcomos of a round of play by a payoff matrix indicating how much R will rocoiyo from 39 giyon tho stratogios followod by oaCh playor 39 nogatiyo numbor moans that 39 rocoiyos monoy from H L1 L2 L1 252 11 0 2 3 0 12 2 0 0 3 H 21 3 0 0 1 22 0 3 1 0 This is an oxamplo of a fl two parson cmsum gnmc Finito39i39i rotors to tho fact that oaCh playor has a nito numbor of stratogios Zoro sumquot rotors to tho fact that what ono playor gains in woalth tho othor losos Supposo H doCidos to uso only stratogy 12 This is an oxamplo ofa p39urr stratogy Sinco tho minimum ontry in that row is 2 H can guarantoo losing no moro than por round and this will happon if 39 Consistontly usos stratogy 11 But what if H doCidos to uso oithor stratogy 12 or 21 oaCh half of tho timo but randomly miKod so that thoro is no dotoctablo pattorn39 For oKamplo ho Could ip a Coin to doCido which of tho two stratogios to uso This is an oKamplo of a mind stratogy To calculato tho oxpoctod outcomo wo mix tho soCond and third rows by multiplying thom oaCh by 12 and adding thom togothor Tho rosult is 2 0 0 3 lsmu am aLug aq Jto Llunq u sag amus 5ng J10 LIQBJ sasn J X amus saw Xpualsgsuoo H 31 suadduq 51L puu punm Iad g3 450w m use 0 padxa U13 g s A LILLIHIO u qua LLIHLLIXBLLI up aougg 3901 gm JL Xllmq mm cos 0 qua LLIHLLIXBLLI aq m upiool u paganng A A s AA A A v A s f A A s 05 H mud 4mg swnotuu wasmdaJ Axgumu aq u sJoqLunu JLLL z z A aguus AILIO asn o sappop asoddns aldtuuxo IOA 39AIJLILIBLLI IBLLIS u u PJHNUS sq U13 sag amus s Lowz uqu Ia wl s qua LLIHLLIULLI aq Amale aJlungu u 1ng 110K uug 39owz 4513a m s 0 l1 2 0M L 0 0 2M 2 0 0 Zrch 0 2 z 0W u quo LLIHLLILILLI up 4m Lpns due 0 LLIHS 4m 1d E d ch ld woqtunu aAguauuou 1ng 04 Xu AIBIHQHAIBG LI alauaq LIJAJ s LLAA H JO X amus JXLLI u 1ng 0 XJL uIanOJd 39z z PUB z l SJy J ngS XILIO SOS Xlwolsgsuoo LIJddBL 01 SN padxo U13 JL PUB J BAIJAB JLH U0 PLIHOAI Jud IBHOP IJLIBHb 13 URL JAIOLLI 0U JSOI 01 podxo PIHOAA H L KAULIJ LLIILLILILLI JLH JQLIHC ugAg ilaqp og Luang ugppu puu lAl Xq Luang JLo LIQBJ ug ldgglmu Xq 5mm 5ng saxgtu H LIJLH atugg up Jto lAI X amus LIQBJ saw H H 15ng uqu Iauaq 01 H uug 39z z X amus sasooq Xlgualsgsuoo J uodduq o 51L padxa uu JL puu a uJaAu aq uo A v s A A PLIHOJ Idd IBHOP BHBL LIBLH JJOLLI 0U J50 01 JQJdAJ LIB H 5 AJJLIJ LLIHLLILILLI JLH JQLILC 39 ugLuLou md IBJLIII ugsn Lualqmd 5ng ugAlos XIL ugpgq s H sugoo quLu mm mouq mu saop 45 4 Ll uoLp LIJAJ a mumpu Km 4 aAg 4 amqu sassau H gm 43134 aqg we gown s 0le cos 0 spuuq IIJLH uado LHOL LIJLH puu puooas sassan 4 45 sassau H mq Xlsnoauuglmugs sassau IIJLH aounouuu mu 01 4 puu H441 JULIAA uIanOJd 39X amus pawng 544 sq 0511 mm 5ng XJpLuLqu Kg 390 4410 anlm u LHIAA gz Yd gg Ed 5 uogmlos lutupdo LAluo up JUO 0 Z Id d Zd ld 1le Ycll 2ch 39le S 2 Id E le ado lclg S 2 1ch E le ado ldz S 2 1le 2 ch chz 39le S 2 Id 211 311 Id 394395 2 quu 0 uoggnlos pawng up puH ugLuLou md IBJLIII Xq H JO X aguus 45m aqg 1ng 0 mm s JJJH 394 JO X aguus 45ml up 513 JLLIBS up sq 0 H JO X aguus 45ml aqg padxa U13 am XJpLuLqu Xq asmoo 4K 39z z puu z l sog amus XILIO saw Xpualsgsuoo H 4 5ng padxa U13 JL puu a uJaAu up uo puum Iad quop Iayuub u LILng JJOLLI ou use 0 padxa U13 4 X amus pangu 5ng ugsn Xq 111 5 qua LLIIILLIIXBLLI aqg aougg 0 I E I L 0 L 0 I E I 0 I 0 I Z 0 E Z l I I l SPIJIX SILLL 39IJL1JOJ LLIJLH LIIPPB PUB AL LLIJLH 30 LIQBJ LIIXIGIHHLLI XL SLILLIHIO JLH XILLI Linear Programming Notes Carl W Lee Department of Mathematics University of Kentucky Lexington KY 40506 leemsukyedu Solutions Submitted by Course Members Fall 2006 Contents n References Exercises Matrix Algebra Polytopes 31 Convex Combinations and V Polytopes 32 Exercises 33 Linear Inequalities and H Polytopes 34 Exercises 35 H Polytopes are V Polytopes 36 Exercises 37 V Polytopes are H Polytopes Introduction to Linear Programming 41 Example 42 De nitions 43 Back to the Example Exercises Linear Programs Solving Linear Programs 61 Matrices 62 Four Vector Spaces Associated with a Matrix 63 Graphs and Digraphs 64 Systems of Equations 65 Solving Linear Programs The Revised Simplex Method Theorems of the Alternatives 71 Systems of Equations 72 Fourier Motzkin Elimination 7 A Starting Example Showing our Example is Feasible An Example of an Infeasible System 75 Fourier Motzkin Elimination in General More Alternatives Exercises Systems of Linear Inequalities 35 35 37 40 41 43 45 47 9 Duality 50 91 Economic Motivation 50 92 The Dual Linear Program 51 93 The Duality Theorems 53 94 Comments on Good Characterization 58 95 Complementary Slackness 58 96 Duals of General LP7s 59 97 Geometric Motivation of Duality 64 10 Exercises Duality 66 iii 1 References The textbook for this course is Jon Lee7 A First Course in Combinatorial Optimization7 Cambridge7 2004 Four good references for linear programming are H Dimitris Bertsimas and John N Tsitsiklis7 Introduction to Linear Optimization7 Athena Scienti c E0 Vasek Chvatal7 Linear Programming7 WH Freeman 9 George L Nemhauser and Laurence A Wolsey7 Integer and Combinatorial Optimiza tion7 Wiley Hr Christos H Papadimitriou and Kenneth Steiglitz7 Combinatorial Optimization Algo rithms and Complexity7 Prentice Hall I used some material from these sources in writing these notes Also7 some of the exercises were provided by Jon Lee and Francois Margot Exercise 11 Find as many errors in these notes as you can and report them to me D 2 Exercises Matrix Algebra It is important to have a good understanding of the content of a typical one semester un dergraduate matrix algebra course Here are some exercises to try Note Unless otherwise speci ed all of my vectors are column vectors If I want a row vector 1 will transpose a column vector Exercise 21 Consider the product 0 AB of two matrices A and B What is the formula for 07 the entry of C in row 239 column j Explain why we can regard the 2th row of C as a linear combination of the rows of B Explain why we can regard the jth column of C as a linear combination of the columns of A Explain why we can regard the 2th row of C as a sequence of inner products of the columns of B with a common vector Explain why we can regard the jth column of C as a sequence of inner products of the rows of A with a common vector Consider the block matrices A B E F O D G 39 Assume that the number of columns of A and 0 equals the number of rows of E and F and that the number of columns of B and D equals the number of rows of G and H Describe the product of these two matrices D and Exercise 22 Associated with a matrix A are four vector spaces What are they how can you nd a basis for each and how are their dimensions related Give a natural77 basis for the nullspace of the matrix All where A is an m gtlt 71 matrix and I is an m gtlt m identity matrix concatenated onto A D Exercise 23 Suppose V is a set of the form Ax x E Rk where A is an n gtlt k matrix Prove that V is also a set of the form y E R By 0 where B is an Z gtlt 71 matrix and explain how to nd an appropriate matrix B Conversely suppose V is a set of the form y E R By 0 where B is an Z gtlt 71 matrix Prove that V is also a set of the form Ax x E Rk where A is an n gtlt k matrix and explain how to nd an appropriate matrix A D Exercise 24 Consider a linear system of equations Ax b What are the various elemen tary row operations that can be used to obtain an equivalent system What does it mean for two systems to be equivalent D Exercise 25 Consider a linear system of equations Ax b Describe the set of all solutions to this system Explain how to use Gaussian elimination to determine this set Prove that the system has no solution if and only if there is a vector y such that yTA OT and yTb 31 0 D Exercise 26 If x E R what is the de nition of Of Of For xed matrix A not necessarily square and vector b explain how to minimize HAx 7 Mb Note From now on in these notes if no subscript appears in the notation then the norm is meant D Exercise 27 Consider a square 71 gtlt 71 matrix A What is the determinant of A How can it be expressed as a sum with n terms How can it be expressed as an expansion by cofactors along an arbitrary row or column How is it affected by the application of various elementary row operations How can it be determined by Gaussian elimination What does it mean for A to be singular Nonsingular What can you tell about the determinant of A from the dimensions of each of the four vector spaces associated with A The determinant of A describes the volume of a certain geometrical object What is this object D Exercise 28 Consider a linear system of equations Ax b where A is square and nonsin gular Describe the set of all solutions to this system What is Cramer7s rule and how can it be used to nd the complete set of solutions D Exercise 29 Consider a square matrix A When does it have an inverse How can Gaussian elimination be used to nd the inverse How can Gauss Jordan elimination be used to nd the inverse Suppose 6739 is a vector of all zeroes except for a 1 in the jth position What does the solution to Ax 6739 have to do with A l What does the solution to xTA e have to do with A l Prove that if A is a nonsingular matrix with integer entries and determinant i1 then A 1 is also a matrix with integer entries Prove that if A is a nonsingular matrix with integer entries and determinant i1 and b is a vector with integer entries then the solution to Ax b is an integer vector D Exercise 210 What is LU factorization What is QR factorization Gram Schmidt or thogonalization and their relationship D Exercise 211 What does it mean for a matrix to be orthogonal Prove that if A is or thogonal and x and y are vectors then 7 yHZ HAx 7 AyHZ ie multiplying two vectors by A does not change the Euclidean distance between them D Exercise 212 What is the de nition of an eigenvector and an eigenvalue of a square matrix The remainder of the questions in this problem concern matrices over the real numbers with real eigenvalues and eigenvectors Find a square matrix with no eigenvalues Prove that if A is a symmetric n gtlt 71 matrix there exists a basis for R consisting of eigenvectors of A D Exercise 213 What does it mean for a symmetric matrix A to be positive semi de nite Positive de nite If A is positive de nite7 describe the set x TAz S 1 What is the geometrical interpretation of the eigenvectors and eigenvalues of A with respect to this set D Exercise 214 Suppose E is a nite set of vectors in R Let V be the vector space spanned by the vectors in E Let I S Q E S is linearly independent Let C S Q E S is linearly dependent7 but no proper subset of S is linearly dependent Let B S Q E S is a basis for V Prove the following 1 WEI E0 If S1 6 I S2 6 I and card S2 gt card S17 then there exists an element 6 6 S2 S1 such that S1 U 6 E I 3 If S E I and S U 6 is dependent7 then there is exactly one subset of S U 6 that is in C 4 If S1 6 B and S2 6 B then card S1 card S2 5 If S1 6 8 S2 6 B and 61 6 S17 then there exists an element 62 6 S2 such that S1 61 U 62 E B 6 If S1 6 C7 S2 6 C7 6 6 S1 S27 and 6 E S1S27 then there is a set S3 6 C such that S3 Q S1 U S2 e and 6 6 S3 3 Polytopes 31 Convex Combinations and V Polytopes De nition 31 Let 111117 be a nite set of points in R and A1 Am 6 R such that Al 207239177m7 and A1m1 Then m Z Ail j1 m is called a conver combination of 01 1 7 Exercise 32 Give some examples of convex combinations in R17 R27 and R3 lnclude diagrams D De nition 33 A subset S Q R is conver if it is closed under all convex combinations of its elements Exercise 34 Give some examples of convex sets in R17 R27 and R3 D Exercise 35 ls the empty set convex ls R convex D Exercise 36 Are the following sets convex 1 x E R Ax O for a given matrix A Yes7 the set is convex Proof Suppose we have 111112 1 E x E R Ax O7 and 3ij some convex i1 combination of the M Then we have i i1 Z A 0 i1 GEMS Q Thus every convex combination of every set of W is in the set7 that is7 the set is convex Wells 2 x E R Ax S O for a given matrix A 3 x E R Ax b for a given matrix A and vector b Suppose 1727zk E S Let A12k E R such that A 2 0 for 1 g i g k and 21 j 1 Consider h h A Z Aj j Z Ainj j1 7391 So 21 ijj E S Therefore S is convex Clark 4 x E R Ax S b for a given matrix A and vector b D Proposition 37 A subset S Q R is convex if and only if A1111 A2112 6 S whenever A1 1 A2 1 and A12 2 0 That is to say it su ces that the set is closed under all convex combinations of pairs of elements D Proposition 38 The intersection of any collection of convex sets is convex D De nition 39 Let V Q R De ne the convex hull of V denoted conv V to be the intersection of all convex sets containing V coan S V Q S S convex Lemma 310 For all V Q R the set coan is convex PROOF Clear from the previous proposition since it is de ned to be the intersection of a collection of convex sets D Lemma 311 quotConvex combinations of convex combinations are convex combinations PROOF Consider a set V Suppose x E V for all values ofi and j Additionally suppose7 since we are dealing with convex combinations7 the appropriatly labeled A sum to one c A1A11z11 Alkzlk Amm1zm1 Amzm AlAnzll AlAlkzlk AmAmlzml AWLsz All of the x are from V7 so we only need to check that the sum of all of the coef cients is equal to one 11111k mAml i n i AmAmn 1 111hm m1mn A11 A2lt1gt Am1 1 Therefore7 c is a convex combination Clark D Proposition 312 Let V Q R Then coan equals the set of all conue combinations of elements of V D Lemma 313 Let 017 7cm 6 R Let A be the matricc 7J1 gm That is to say A is created by listing the points oi as columns and then appending a row ofl s Let i E R Then 1 equals the conue combination 221 Ami if and only ifA A17 7AmlT is a solution of A1 PROOF If we think of AA as a linear combination of columns of A7 then 1 is equivalent to omi 1 which in turn is equivalent to A1v1Amvmv A1m1 D Exercise 314 What can you say about the rank of the matrix A in the previous problem D Theorem 315 Carath odory Suppose z is a convep combination of vl7 7v 6 R where m gt n 1 Then z is also a convep combination of a subset of v177vm of cardinality at most n1 Suggestion Think about the matrip A in the previous two problems Assume that the columns associated with positive values of A are linearly dependent What can you do now D De nition 316 A V polytope is the convex hull of a nite collection of points in R 32 Exercises Exercise 317 In each of the following cases describe conV V 1 V i1i1i1 c R3 2 V 100 010 001 c R3 3 V i100 0i10 00i1 c R3 4 V 0ii i c R D Theorem 318 Radon Let V 111 v Q R Ifm gt n 1 then there eists a partition V1 V2 ofV such that conVV1 coang 7 Q E Theorem 319 Helly Let V V1 Vm be a family ofm eonver subsets of R with m 2 n1 If every subfamily 0fn1 sets in V has a nonempty intersection then gllVi 31 0 U 33 Linear Inequalities and HPolytopes De nition 320 Let a E R and b0 6 R Then aTx be is called a linear equation7 and aTz S be and aTx 2 be are called linear inequalities Further7 if a 31 07 then the set x E R aTz be is called a hyperplane7 the sets x E R aTz S be and x E R aTz 2 be are called closed halfspaees7 and the sets x E R aTz lt b0 and x E R aTz gt be are called open halfspaees Exercise 321 Why do we require a 31 0 in the de nitions of hyperplanes and halfspaces D De nition 322 A subset S Q R is bounded if there exists a number M E R such that S M for all z E S De nition 323 We can represent systems of a nite collection of linear equations or linear inequalities in matrix form For example7 the system 011 1min S b1 aml l i i amnxn S bm can be written compactly as Ax lt b where an aln A s aml amn and 51 b s bm A subset of R of the form x E R Ax S b is called an III polyhedron A bounded H polyhedron is called an H polytope Exercise 324 ls the empty set an H polytope ls R an H polyhedron D Exercise 325 Prove that a subset of R described by a nite collection of linear equations and inequalities is an H polyhedron D 34 Exercises Exercise 326 In each case describe the H polyhedron P x Ax S b where A and b are as given 1 7 7 7 7 1 0 0 1 0 1 0 1 0 0 1 1 A 71 0 0 b 1 0 i1 0 1 7 0 0 717 717 2 7 1 1 1 i1 1 1 1 171 1 1 7171 1 1 A 1 171 b 1 i1 171 1 17171 717 717171 35 HPolytopes are V Polytopes De nition 327 Suppose P x E R Ax S b is an H polytope and T E P Partition the linear inequalities into two sets those that 7 satis es with equality the tight or bind ing inequalities and those that T satis es with strict inequality the slack or nonbinding inequalities AW 3 b1 where A17 bl7 Azx S b2 where A27 lt b2 De ne NT to be the linear space that is the nullspace of the matrix A1 ie7 the solution space to Alx 0 Even though this is not an of cial term in the literature7 we will call NT the nullspace of T with respect to the system de ning P D De nition 328 Let P be an H polytope and T E P such that dim NT 0 Then T is called a vertem of P D Lemma 329 No two di erent vertices of an H polytope have the same set of tight inequal ities D Proposition 330 IfP is an H polytope then P has a nite number of vertices D Lemma 331 Let P x E R Ax b be an H polytope and E P such that T is not a vertex Choose any nonzero w E NT and consider the line T in Then there is a positive value oft for which 7 in is in P and has more tight constraints than T Similary there is a negative value oft for which E m is in P and has more tight constraints than T D Theorem 332 Minkowski Every H polytope P is the COTZUCCE hull of its vertices Hence every H polytope is a V polytope Suggestion Prove this by induction on the number of slack inequalities for a point 7 E P D 36 Exercises Exercise 333 Determine the vertices of the polytope in R2 described by the following inequalities 1 22 S 1 2 S 70 21 2 S 1 2 0 2 2 0 D Exercise 334 Determine the vertices of the polytope in R3 described by the following inequalities 1 2 S 1 1 3 S 1 2 3 S 1 1 2 0 2 2 0 3 2 0 D Exercise 335 Consider the polytope in R9 described by the following inequalities 1112131 2122231 3132331 1121311 1222321 1323331 11 20 12 20 13 20 21 20 22 20 23 20 31 20 32 20 33 20 Find at least one vertex D 37 V Polytopes are HPolytopes In order to prove the converse of the result in the previous section7 ie7 to prove that every V polytope is an H polytope7 we will need to invoke a procedure called Fourier Motzkin elimination7 which will be discussed later in Sections 72775 What we need to know about this procedure for the moment is that whenever we have a polyhedron P described by a system of inequalities in the variables7 say7 17 7 we can eliminate one or more variables of our choosing7 say7 k177m to obtain a new system of inequalities describing the projection of P onto the subspace associated with 17 7 Theorem 336 Weyl UP is a V polytope then it is m H polytope PROOF Assume P conv1177vm Consider P nx 22117701 7 z 07 221177 17 r 2 0 Then P r7xE1nvi7 S O7E 1Ti i 2 07 221177 17 221 n 2 17 r 2 0 Then a description for P in terms of linear inequalities is obtained l H from that of P by using Fourier Motzkin elimination to eliminate the variables r17 Mm Finally7 we note that every V polytope is necessarily a bounded setiwe can7 for example7 bound the norm of any feasible point z in terms of the norms of 017 711 quot if z 221 771 with 221771 andn 20for allz39177m7 then m Z 770 i1 H cll m S anlvlll i1 m S Elli1H i1 D Exercise 337 Experiment with the online demo of polymakef7 wwwmathtu berlindepolymallte7 which can convert between descriptions of polytopes as V polytopes and as H polytopes D 4 Introduction to Linear Programming 41 Example Consider a hypothetical company that manufactures gadgets and gewgaws H One kilogram of gadgets requires 1 hour of labor7 1 unit of wood7 2 units of metal7 and yields a net pro t of 5 dollars E0 One kilogram of gewgaws requires 2 hours of labor7 1 unit of wood7 1 unit of metal7 and yields a net pro t of 4 dollars 9 Available are 120 hours of labor7 70 units of wood7 and 100 units of metal What is the company7s optimal production mix We can formulate this problem as the linear program maxz 5x1 4x2 st 1 2x2 3 120 1 2 S 70 21 2 S 100 17 2 2 0 ln matrix notation7 this becomes which is a problem of the form max ch st Ax S b x 2 0 We can determine the solution of this problem geometrically Graph the set of all points that satisfy the constraints Draw some lines for which the objective function assumes a constant value note that these are all parallel Find the line with the highest value of 2 that has nonempty intersection with the set of feasible points In this case the optimal solution is 3040 with optimal value 310 O00 A060 B2050 C3040 optimal D500 5x4y310 42 De nitions A linear function is a function of the form alzl anzn where a1 an E R A linear equation is an equation of the form alzl anzn B where a1 am E R If there exists at least one nonzero aj then the set of solutions to a linear equation is called a hyperplane A linear inequality is an inequality of the form alzl anzn S B or alzl anzn 2 B where a1 am E R If there exists at least one nonzero a then the set of solutions to a linear inequality is called a halfspace A linear constraint is a linear equation or linear inequality A linear programming problem is a problem in which a linear function is to be maximized or minimized subject to a nite number of linear constraints A feasible solution or feasible point is a point that satis es all of the constraints If such a point exists the problem is feasible otherwise it is infeasible The set of all feasible points is called the feasible region or feasible set The objective function is the linear function to be optimized An optimal solution or optimal point is a feasible point for which the objective function is optimized The value of the objective function at an optimal point is the optimal value of the linear program In the case of a maximization minimization problem if arbitrarily large small values of the objective function can be achieved then the linear program is said to be unbounded More precisely the maximization minimization problem is unbounded if for all M E R there exists a feasible point z with objective function value greater than less than M Note It is possible to have a linear program that has bounded objective function value but unbounded feasible region so dont let this confusing terminology confuse you Also note 16 that an infeasible linear program has a bounded feasible region Exercise 41 Graphically construct some examples of each of the following types of two variable linear programs H lnfeasible E0 With a unique optimal solution 9 With more than one optimal solution 4 Feasible with bounded feasible region Cf Feasible and bounded but with unbounded feasible region 03 Unbounded A linear program of the form V L maxZCJxj j 1 V L St Zaijzj S bi 1m j1 zJZO7 j1n which7 in matrix form7 is machx st Ax S b x 2 O is said to be in standardform For every linear program there is an equivalent one in standard form begin thinking about this 43 Back to the Example Suppose someone approached the Gadget and Gewgaw Manufacturing Company GGMC7 offering to purchase the company7s available labor hours7 wood7 and metal7 at 150 per hour of labor7 1 per unit of wood7 and 1 per unit of metal They are willing to buy whatever amount GGMC is willing to sell Should GGMC sell everything This is mighty 17 tempting because they would receive 350 more than what they would gain by their current manufacturing plan However observe that if they manufactured some gadgets instead for each kilogram of gadgets they would lose 450 from the potential sale of their resources but gain 5 from the sale of the gadgets Note however that it would be better to sell their resources than make gewgaws So they should not accept the offer to sell all of their resources at these prices Exercise 42 In the example above GGMC wouldn7t want to sell all of their resources at those prices But they might want to sell some What would be their best strategy D Exercise 43 Suppose now that GGMC is offered 3 for each unit of wood and 1 for each unit of metal that they are willing to sell but no money for hours of labor Explain why they would do just as well nancially by selling all of their resources as by manufacturing their products D Exercise 44 In general what conditions would proposed prices have to satisfy to induce GGMC to sell all of their resources If you were trying to buy all of GGMC7s resources as cheaply as possible what problem would you have to solve D Exercise 45 If you want to purchase just one hour of labor or just one unit of wood or just one unit of metal from GGMC what price in each case must you offer to induce GGMC to sell D 5 Exercises Linear Programs Exercise 51 Consider the following linear program P 1 2 3 Hr maxz 1 2x2 st 3x1 x2 3 3 1 Graph the feasible region Locate the optimal points Explain why the four constraints have the following respective outer normal vectors an outer normal vector to a constraint is perpendicular to the de ning line of the constraint and points in the opposite direction of the shaded side of the constraint 1 371V 2 UV 3 170lT 4 OrllT Explain why the gradient of the objective function is the vector 17 2T For each corner point of the feasible region7 compare the outer normals of the binding constraints at that point the constraints satis ed with equality by that point with the gradient of 2 From this comparison7 how can you tell geometrically if a given corner point is optimal or not Vary the objective function coef cients and consider the following linear program maxz clm 02 st 3x1 2 3 3 1 2 S 172 Z 0 Carefully and completely describe the optimal value 2017 02 as a function of the pair 0102 What kind of function is this Optional Use some software such as Maple to plot this function of two variables 5 Vary the right hand sides and consider the following linear program rnaxz 1 2x2 St 31 2 S b1 1 2 S 52 172 Z 0 Carefully and completely describe the optimal value 2b17b2 as a function of the pair bhbg What kind of function is this Optional Use some software such as Maple to plot this function of two variables 6 Find the best nonnegative integer solution to That is7 of all feasible points for P haVing integer coordinates7 nd the one with the largest objective function value D Exercise 52 Consider the following linear program P rnaxz i l 7 2 st 1 3 12 1 Answer the analogous questions as in Exercise 51 D Exercise 53 1 Consider the following linear program rnaxz 2x1 x2 st x1 2 1 12 4 liiggl P Associated with each of the 6 constraints is a line change the inequality to equality in the constraint Consider each pair of constraints for and examine the point of intersection of the two line primal feasible pair if the intersection point falls in the feasible region for 20 which the lines are not parallel7 s Call this pair of constraints a Call this pair of constraints a dual feasible pair if the gradient of the objective function can be expressed as a nonnegative linear combination of the two outer normal vectors of the two constraints The motivation for this terminology will become clearer later on List all primal feasible pairs of constraints7 and mark the intersection point for each pair List all dual feasible pairs of constraints whether primal feasible or not7 and mark the intersection point for each pair What do you observe about the optimal points 2 Repeat the above exercise for the GGMC problem D Exercise 54 We have observed that any two variable linear program appears to fall into exactly one of three categories 1 those that are infeasible7 2 those that have unbounded objective function value7 and 3 those that have a nite optimal objective function value Suppose P is any two variable linear program that falls into category lnto which of the other two categories can P be changed if we only alter the right hand side vector b The objective function vector 0 Both b and 0 Are your answers true regardless of the initial choice of P Answer the analogous questions if P is initially in category ln category D Exercise 55 Find a two variable linear program machx P st Ax S b x 2 O with associated integer linear program max ch IP st Ax S b x 2 O and integer such that P has unbounded objective function value7 but IP has a nite optimal objective function value Note z integer77 means that each coordinate of z is an integer D Exercise 56 Prove the following For each positive real number d there exists a two variable linear program P with associated integer linear program IP such that the entries of A7 b7 and c are rational7 P has a unique optimal solution xi IP has a unique optimal solution 77 and the Euclidean distance between f and T exceeds d Can you do the same with a one variable linear program D Exercise 57 Find a subset S of R2 and a linear objective function ch such that the optimization problem max ch st x E S is feasible7 has no optimal objective function value7 but yet does not have unbounded objec tive function value D Exercise 58 Find a quadratic objective function fx7 a matrix A with two columns7 and a vector b such that the optimization problem maxfx st Ax S b x 2 O has a unique optimal solution7 but not at a corner point D Exercise 59 Chvatal problem 15 Prove or disprove If the linear program max CT P st Ang x20 is unbounded7 then there is a subscript k such that the linear program maxxk st Ax S b x 2 O is unbounded D Exercise 510 Bertsimas and Tsitsiklis problem 112 Consider a set S Q R described by the constraints Ax S b The ball with center y E R and radius r E R1 is de ned as x E R 7 S r Construct a linear program to solve the problem of nding a ball with the largest possible radius that is entirely contained within the set S D Exercise 511 Chvatal7 problems 11714 D 6 Solving Linear Programs 61 Matrices Suppose A is an m gtlt n matrix7 B is an n gtlt p matrix7 and C AB Then 71 Cikaijbjk7 Z39177m7 kl77p j1 We can recognize this as the inner product of the 2th row of A with the kth column of B blk Cik ai177aml bnk We can also see that the 2th row of C is a linear combination of the rows of B using as coef cients the entries in the 2th row of A Ci177Cip ai1b1177b1p bn177bnp7 and the kth column of C is a linear combination of the columns of A using as coef cients the entries in the kth column of E 01k an aln blk E bnk ka aml amn 62 Four Vector Spaces Associated with a Matrix De nition 61 Let A be an m gtlt 71 matrix The four vector spaces associated with A are 1 The column space of A This is the space of all linear combinations of the columns of A7 columnspaceA Ax z E R 2 The row space of A This is the space of all linear combinations of the rows of A7 rowspaceA yTA y E Rm 3 The nullspace of A7 nullspaceA x E R Ax O 4 The left nullspace of A7 leftnullspaceA y E Rm yTA OT 23 To nd bases for each of the four spaces perform Gaussian elimination on A to obtain a matrix A in row reduced form By multiplying the matrices corresponding to the various row operations determine the square invertible matrix M such that MA A The leading nonzero entries in each nonzero row of A are called the pivot entries The rows in which they appear are called the pivot rows and the columns in which they appear are called the pivot columns You should be able to verify the following assertions 1 To obtain a basis for the column space of A select the columns of A corresponding to the pivot columns of A Note that A and A do not necessarily have the same column space but their column spaces have the same dimension namely the number of pivot entries E0 The nonzero rows of A form a basis for the row space of A Hence they have the same dimension namely the number of pivot entries 00 Matrices A and A have the same nullspace There is one basis vector for each nonpivot column A of A Set ivS 1 and w 0 for all other nonpivot columns Aj Then determine the unique multipliers w for the pivot columns of A to solve A w 0 So the dimension of the nullspace equals the number of nonpivot columns 7 Suppose the zero rows of A are precisely the last h rows of A Then the last h rows of M form a basis for the left nullspace of A In particular the dimension of the left nullspace equals the number of nonpivot rows As an immediate consequence we have Theorem 62 1 The dimension of the row space equals the dimension of the column space This numbeiquot is also called the rank of A 16 The dimension of the column space plus the dimension of the nullspace equals the numbeiquot of columns 93 The dimension of the row space plus the dimension of the left nullspace equals the numbeiquot of rows 63 Graphs and Digraphs De nition 63 A directed graph digraph G V E is a nite set V VG of vertices and a nite set E EG of edges Associated with each edge e is an ordered pair uo of usually distinct vertices We way u is the tail of e o is the head of e and u and o are the endpoints of e If u and o are distinct we may sometimes write e no if there is no other edge having the same tail as e and the same head as e If u i then e is called a loop In this course unless otherwise indicated we will consider only digraphs without loops We can represent a directed graph by a drawing using points for vertices and arrows for edges with the arrow pointing from the tail to the head If each edge is associated with an unordered instead of ordered pair of endpoints then we say that we have an undirected graph De nition 64 A subgraph of a digraph G V E is a digraph G V E where V Q V E Q E A path in a digraph is an alternating sequence o0 e1o1e2o2 ekok of vertices and edges where the vertices o are all distinct the edges e are all distinct and 151 and o are the two endpoints of e either one of oiin could be the tail the other being the head If you have an alternating sequence in which h 2 1 oo ilk and otherwise the vertices and edges are distinct the sequence is called a cycle We also often identify paths and cycles with just the sets of edges in them Two vertices are connected if there is a path from one to the other The set of all vertices connected to a given vertex is a component of the digraph A digraph is connected if it has only one component A forest is a graph containing no cycle ie acylic A tree is a connected forest A spanning forest of a digraph is a subgraph that is a forest containing every vertex of the digraph A connected spanning forest of a digraph is a spanning tree A twig of a digraph is an edge that is not a loop and has an endpoint that is not the endpoint of any other edge in the digraph Theorem 65 Forests with at least one edge have twigs PROOF Assume the contrary Choose any vertex in the forest that is the endpoint of some edge in the forest Begin making a path If every vertex encountered is new at every new vertex there will be another vertex having that vertex as an endpoint that can be used to continue the path Since there is only a nite number of vertices this cannot continue forever So at some point a vertex will be encountered for a second time But then a cycle will be detected which is also impossible D

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.