MthSc 440/H440/640: Linear ProgrammingLecture 20Pietro BelottiDept. of Mathematical SciencesClemson UniversityNovember 4, 2010Reading for today: pages 148-166.No class on Tuesday, November 9.Dual feasibilityConsider a primal LP (in standard form) and its dual:max c⊤x min b⊤us.t. Ax ≤ b s.t. A⊤u ≥ cx ≥ 0 u ≥ 0Add slack variables to the primal, surplus1variables to the dual.max c⊤x min b⊤us.t. Ax + Ix′= b s.t. A⊤u − Iu′= cx, x′≥ 0 u, u′≥ 0Note: the d ual is ≡ max{−b⊤u : A⊤u − Iu′= c, (u, u′) ≥ 0}.1Called “surplus” because we subtract from the left-hand side.Examplemax 3x1+2x2+x3min 4u1+6u2s.t. x1+x2+x3≤ 4 s.t. u1+2u2≥ 32x1+x2+3x3≤ 6 u1+u2≥ 2x1, x2, x3≥ 0 u1+3u2≥ 1u1, u2≥ 0becomemax 3x1+2x2+x3s.t. x1+x2+x3+x4= 42x1+x2+3x3+x5= 6x1, x2, x3, x4, x5≥ 0min 4u1+6u2s.t. u1+2u2−u3= 3u1+u2−u4= 2u1+3u2−u5= 1u1, u2, u3, u4, u5≥ 0Primal and dual dictionariesIn the primal, consider the basis (x4, x5) and the dictionaryx4= 4 −x1−x2−x3x5=6 −2x1−x2−3x3z = 3x1+2x2+x3.Feasible2solution (4 ≥ 0, 6 ≥ 0) but not optimal (3, 2, 1 > 0).In the dual, consider the basis (u3, u4, u5) and the dictionaryu3=−3 +u1+2u2u4=−2 +u1+u2u5=−1 +u1+3u2−w = −4u1−6u2.Infeasible solution (−3, −2, −1 < 0). If i t wasn’t, it would beoptimal (as −4, −6 ≤ 0).2Or better, primal feasible.Primal and dual dictionariesChange indices of the dual variables so that dual surplusvariables have indices 1, 2 . . . , n, same as primal originalvariables:min 4u4+6u5(≡ − max −4u4−6u5)s.t. u4+2u5−u1= 3u4+u5−u2= 2u4+3u5−u3= 1u4, u5, u1, u2, u3≥ 0. . . and clear up the link between primal and dual dictionaries:x4=4 −x1−x2−x3x5=6 −2x1−x2−3x3z = 3x1+2x2+x3;u1=−3 +u4+2u5u2=−2 +u4+u5u3=−1 +u4+3u5−w = −4u4−6u5.Basic duals, nonbasic primals (and viceversa)primal dualxibasic ↔ uinonbasicxinonbasic ↔ uibasicThe dual (with surplus variables included) can be written asmin b⊤us.t. Au = cu ≥ 0and A has◮n rows: one for each dual constraint≡ one row for primal variable◮m + n columns:◮one for each original dual variable (there are m) and◮one for each surplus variable (there are n)Dual dictionariesNow partition again A (not the same A as in the primal: why?)as (B|N), and rewrite the dual asmin b⊤BuB+ b⊤NuNs.t. BuB+ NuN= cuB, uN≥ 0Having a dej´a vu here? Dual dictionary:uB= B−1c − B−1NuNz = b⊤BB−1c + (b⊤N− b⊤BB−1N)uNRemember:◮uB↔ xNand uN↔ xB.◮B here is an n × n matrix, not m × m as in the primal.Primal and dual dictionariesDefine¯A := B−1N,¯b := B−1b,¯c := c⊤N− c⊤BB−1N,¯d := c⊤BB−1b.It’s easy to prove (but we won’t) that for a primal dictionaryxB=¯b −¯AxNz =¯d +¯c⊤xNthe corresponding dual dictionary isuB= −¯c +¯A⊤uN−w = −¯d −¯b⊤uNPrimal and dual dictionariesSo far, we have always looked at (and played with) primaldictionaries. Let’s lo ok at dual dictionaries.◮Primal dictionary: B = {4, 5}; N = {1, 2, 3};◮Dual dictionary: B = {1, 2, 3}; N = {4, 5}.x4=4 −x1−x2−x3x5=6 −2x1−x2−3x3z = 3x1+2x2+x3is aprimal feasibledictionary. It is also dual infeasible: its dual dictionaryu1= −3 +u4+2u5u2=−2 +u4+u5u3=−1 +u4+3u5−w = −4u4−6u5is infeasible. Dual infeasibility ⇔¯c = cN− cBB−1N 6≤ 0. Thecolumn−3−2−1= −¯c, so¯c 6≤ 0 ⇒ not optimal.Primal and dual dictionariesPivot: x2enters ⇒ x4leaves.◮Primal dictionary: B = {2, 5}; N = {1, 3, 4};(⋆)x2= 4 −x1−x3−x4x5=2 −x1−2x3+x4z = 6 +x1−x3−2x4⇒ Dual dictionary: B = {1, 3, 4}; N = {2, 5}.(⋆⋆)u1= −1 +u2+u5u3=+1 +u2+2u5u4=+2 +u2−u5−w = −6 −2u2−4u5◮Dictionary (⋆) is primal feasible, dual infeasible.◮Dictionary (⋆⋆) is primal infeasible, dual feasibleOptimal solutions and dual feasibilityPivot: x1enters ⇒ x5leaves.◮Primal dictionary: B = {1, 2}; N = {3, 4, 5};(⋆)x1=2 −2x3+x4−x5x2=2 +x3−x4+x5z = 8 −3x3−x4−x5⇒ Dual dictionary: B = {3, 4, 5}; N = {1, 2}.(⋆⋆)u3= +3 +2u1−u2u4=+1 −u1+u2u5=+1 +u1−u2−w = −8 −2u1−2u2◮Dictionary (⋆) is primal feasible and dual feasible.⇒ It is optimal.Optimal solutions and dual feasibility◮The simplex method visited three dictionaries◮the first two were only feasible◮Or, better, primal feasible and dual infeasible◮The last one was optimal,i.e. Both primal feasible and dual feasible.An alternative to the (primal) simplex method is:◮Start from a primal infeasible (but dual feasible) dictionary;◮Do pivots aimed at◮maintaining dual feasibility;◮improving objective function of the dual;◮Terminate on dictionary both primal and dual feasible.We don’t even need to write the dual dictionary explicitly: theprimal dictionary will do just fine.The dual simplex methodStart from a dual feasible, primal infeasible dictionary:x1= −4 +3x2−11x4+x5x3= 3 −x2+3x4−2x5z = 12 −4x2−x4−x5◮Select a leaving variable among {x1, x3}.◮x3= 3 ≥ 0, so we can only select x1as the leaving variable.◮Choose the entering one so that dual feasibility is retained.◮The rows of the dual dictionary are:u2= 4 − 3u1u4= 1 + 11u1u5= 1 − u1◮Which, among {u2, u4, u5}, decreases to zero first?◮u5(would be the leaving variable in the dual dictionary)⇒ x5is the entering variable.To recapxB= B−1b − B−1NxNz = c⊤BB−1b + (c⊤N− c⊤BB−1N)xNAs long as B is invertible, this is a dictionary.◮If¯b = B−1b ≥ 0, it is primal feasible (i.e., feasible)◮If¯c = c⊤N− c⊤BB−1N ≤ 0, it is dual feasible (i.e., optimal)◮Primal simplex keeps primal feasibility (¯b ≥ 0)i.e. it stops when dual feasibility is reached◮Dual simplex keeps dual feasibility (¯c ≤ 0)i.e. it stops when primal feasibility is reached◮(≡ a primal simplex on dual dictionaries)The dual simplex method (cont.)What steps were performed two slides ago?◮Find leaving variable (look at¯b):¯b1< 0, so x1leaves◮The x1-row of B−1N is3e⊤1B−1N =(1, 0)−3 11 −11 −3 2= (−3, 11, −1)◮Find the entering variable (that drives x1from −4 to zero)◮Keep dual feasibility!¯c must stay ≤ 0⇒ it’s the variable j with minimum−¯cj¯aijand¯aij> 0, i.e., j = 5◮The x5-th column of N: a =01; so d = B−1a =−12◮Set t so that xB− td has a zero at x1: −4 − t(−1) = 0 ⇒ t = 4◮(Psst! What if, instead, i f was (3, 11,