### Create a StudySoup account

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

Already have a StudySoup account? Login here

# LINEAR OPTIMIZATION MATH 407

UW

GPA 3.76

### View Full Document

## 17

## 0

## Popular in Course

## Popular in Mathematics (M)

This 39 page Class Notes was uploaded by Addison Beer on Wednesday September 9, 2015. The Class Notes belongs to MATH 407 at University of Washington taught by Staff in Fall. Since its upload, it has received 17 views. For similar materials see /class/192100/math-407-university-of-washington in Mathematics (M) at University of Washington.

## Reviews for LINEAR 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: 09/09/15

Math 407 Summer 2008 Second Half Bradley M Bell August 247 2008 Contents H O CO Software 5 lil A Simple Octave Matlab Simplex Algorithm i i i i i i i i i i i i i i i i i i i i i i 5 lilil Routine That Performs One Pivot Operation i i i i i i i i i i i i i i i i i i 5 L12 Example i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 6 L13 Problem i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 7 1 2 Neos E mail Interface to the Clp Linear Program Solver i i i i i i i i i i i i i i i i 7 L21 MPS lnput File Format i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 9 122 Some Clp Executable Commands i i i i i i i i i i i i i i i i i i i i i i i i i ll 123 Example Neos E mail Interface to Clp i i i i i i i i i i i i i i i i i i i i i 13 1 24 Problem i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 16 General Linear Programming Duality 19 2 1 Matrix Games i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 20 2ilil Example i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 23 2 12 Problem i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 26 2 2 Lagrangians i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 26 2 1 Limits i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 26 222 Example i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 27 223 General Duality i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 29 2 24 Problem i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 30 Geometry 31 3 1 Geometry Example i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 31 32 The Simplex Vertex Theorem i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 33 3 3 Degeneracy Geometry i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 35 34 Cycling Example i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 36 35 Problems i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i i 37 CONTENTS Chapter 1 Software 11 A Simple Octave Matlab Simplex Algorithm Matlab Documetation httpwwwmathworkscomsupportproductproducthtmlproductML Octave Documentation httpwwwgnuorgsoftwareoctavedocinterpreter 111 Routine That Performs One Pivot Operation OctaveMatlab Primal Pivot Routine function E pivotA r c format fid Preforms one pivot of the primal simplex algorithm 70 Z A m by n matrix containing the tableau before the pivot operation Z r integer between 1 and m specifying the row index for the pivot Z c integet between 1 and n specifying the column for the pivot X B m by n matrix containing the tableau after the pivot operation format C style format string for outputing each value in B optional 0 fid file id that will record the values of r c and B optional a Printing B If r is not zero the values r c and the matrix B are written to the file corresponding to fid In this case Ar c must not be zero If format is not present the default format Z8g is used If fid is not present the output is written to the screen Printing A If r is zero only the matrix A is written to the file corresponding to fid If format is not present the default format Z8g is used If fid is not present the output is written to the screen a a o a a o a a o a a CHAPTER 1 SOFTWARE Z size of the input and output matrices m n sizeA Z initialize B as equal to A B X if r is not equal to zero if r 0 Z pivot row of B pivot row of A pivot element Br Ar Ar c X for each row index 1 though m for i 1 m X if this is not the pivot row if i r X row operation that results in zero for Bi c Bi Ai Ai c Br end end end format Z8g if nargin gt 4 Z format is present in argument sequence format format end fid 1 Z default output is to screen if nargin gt 5 Z fid is present in argument sequence fid fid end if r 0 X if r is not zero fprintffid r c g ogn r c end for i 1 m fprintffid format Bi 2 fprintffid n end 112 Example Equation 2 1 Program OctaveMatlab Program for Equation 21 X Equation 21 in Vasek Chvatal s book Linear Programming Z maximize 5x1 4x2 3x3 Z subject to 2x1 3x2 x3 lt 5 4x1 x2 2x3 lt 11 3x1 4x2 2x3 lt 8 Z x1 x2 x3 gt 0 Z The solution is x1 2 x2 0 x3 1 Z fid fopen eq21out wt Z file that will contain the print results 12 NEOS E MAIL INTERFACE TO THE CLP LINEAR PROGRAM SOLVER 7 format 8g quot0 format for printing each tableau element quot0 heading for each of the colums in the tableau fprintffid 485 7x17 7x27 zxsz 7517 7527 7537 Ibr fprintffid n A I quot0 initial tableau 2 3 1 1 O O 5 4 1 2 O 1 O 11 3 4 2 O O 1 8 5 4 3 O O O O r O c 0 quot0 special row value for just printing pivotA r c format fid quot0 print initial tableau r 1 c 1 quot0 row and column for first pivot B pivotA r c format fid quot0 print r c and B r 3 c 3 quot0 row and column for next pivot C pivotB r c format fid quot0 print r c and C fclosefid quot0 close the file Output OctaveMatlab Output for Equation 21 113 Problem We are given the problem maximize 7511 612 7 913 7 814 Wirit z E R subject to 11 212313z4 S 5 I1I22133I4 S3 Fill in the missing characters below denoted by underbars so that the OctaveMatlab program preforms one fesible pivot for the problem above A I quot0 initial tableau 1 2 3 5 1 1 2 3 0 0 0 format quot 83g fprintf 85 x1 x2 7x37 x4 751 752 b n r C B pivotA r c format 12 Neos Email Interface to the Clp Linear Program Solver Purpose The Neos server is a free public service7 see httpwwwneos mcsanlgovneosfaqhtmlwho 8 CHAPTER 1 SOFTWARE This is a description of how to use the Neos E mail interface to Clp to solve linear programming prob ems Clp Mailing List if you have problems using Clp7 you are encouraged to join the Clp Mailing List and then ask the list members What the problem is Email To When sending a problem to Neos for solution7 the To eld of your email message should contain the address neos mcs anl gov Questions about using Neos7 and user feedback7 can be sent to the address neoscommentstcs anl gov Email Subject The Subject eld of the email message should contain a name that describes the problem being solved Email Message The body of the email message should be the following text ltdocumentgt ltprioritygtshortltprioritygt ltcategorygt1pltcategorygt ltsolvergtC1pltsolvergt ltinputMethodgtMPSltinputMethodgt ltcommentsgtlt CDATAE ProblemDescn39ption gtltcommentsgt ltMPSgtlt CDATA ltparamgtlt CDATAE ClpCommzmds gtltparamgt ltdocumentgt Where the text replacements for ProblemDescription IllpsFarmat7 and ClpCommzmds are discussed below Priority The command ltprioritygtshortltprioritygt instructs Neos that this is a short job and should have high priority if thejob does not nish quickly7 it Will be terminated Problem Description The text ProblemDescn39ption above should be replaced by information that Will remind you What problem you are solving MPS Format The text MpsFormat above should be replaced by a valid instance of MPS format This de nes the linear equations and the constraints for the linear programming problem you are solving Clp Commands The text ClpCommzmds is a sequence of Clp commands Example Section 123 contains an example email input and solution output for this interface to Clp 12 NEOS E MAIL INTERFACE TO THE CLP LINEAR PROGRAM SOLVER 9 121 MPS Input File Format Purpose This is a speci cation of suf cient conditions a le to be in MPS format ie if a le meets these speci cations it will be called an MPS formatted le References You can nd the speci cations below in Section 92 ofBA Murtagh7s book Advanced Linear Programming Computation and Practice McGrawHill international Book Co New York 1981 You can also nd a discussion of this input format in Chapter 3 of lL Nazareth s book Computer Solution of Linear Programs Oxford University Press New York 1987 Notation We use I E R to denote the problem variable vector 12 E Rm to denote the constraint right hand side vector and E Rmxn to denote the constraint matrix File Structure An MPS input le has the following structure NameRecord RowsRecord ColumnsRecord Rthecord BoundsRecord Endata Fields We use the eld names below to refer to the corresponding columns Field Keyword Op Name0 Namel Valuel Name Value Columns 1 23 512 1522 2536 4047 5061 Comment Lines A comment line has a in column one and any characters in the rest of the line Any other character in column one is the start of a Keywor Keyword Keyword is special in that it always begins in column one and extends to the rst space character in the line if the Keyword eld extends into another eld the eld it extends into is not present in that line Name Fields it is unspeci ed if leading and trailing white space has any signi cance in Name0 Namel and Name2 For example the seven characters between the quotes 77x1 77 may or may not signify the same information as the seven characters 77 x1 Value Fields Leading and trailing white space in the Value elds is ignored Name Record The NameRecord is a single line with the following structure Keyword Namel where Keyword is NAME and Namel is the name of the problem for this input le Rows Record The rst line of RowsRecord contains the text eyword where Keyword is RUWS Each of the other lines in the RowsRecord has the following structure ame 10 CHAPTER 1 SOFTWARE In the i th line below the RUWS line7 NameU speci es the name of the i th row of the matrix ie7 the name associated With the value 1413111 Am n The Op eld speci es the type of the row and is one of the following values Op Equation or inequality E 1413111 Am n bi G 1413111 Am n 2 bi L 1413111 Am n S bi 1413111 Am n The objective function is de ned as the rst row in Which Op is equal to N The other rows With Op equal to N are ignored Columns Record The ColumnsRecord is used to name the variables 11 through In and to set the value of the nonzero coef cients in the matrix A zero is the default value for A The rst line of the ColumnsRecord contains the text Keyword Where Keyword is COLUMNS Each of the other lines has the structure NameU Namel Valuel or it has the structure NameU Namel Valuel Name Value NameO The string NameU speci es the name corresponding to the variable zj for the information on the line All of the lines corresponding to one variable all the lines With the same value for NameU must be grouped together The record is called the ColumnsRecord because each variable corresponds to a column of the matrix A Namel7 Valuel The string Namel must be one of the row names in the RowsRecord The number Valuel speci es the value of AM Where 239 corresponds to Namel and j corresponds to NameU for this line Name27 Value2 lf Name is present7 it must also be equal to one of the row names in the RowsRecord In this case7 the number Value speci es the value of AM Where 239 corresponds to Name andj corresponds to NameU for this line Rhs Record This record is used to specify nonzero coef cients in the right hand side for each row of the matrix A ie7 each equation or inequality zero is the default right hand side value The rst line of the Rthecord contains the text Keyword Where Keyword is RHS Each of the other lines has the structure Each of the other lines has the structure NameU Namel Valuel NameO The string NameU is a name for the entire right hand side vector 12 E Rm It must be the same for all of the lines in the Rthecord Namel The string Namel must be one of the names in the RowsRecord lt speci es the row index i 12 NEOS E MAIL INTERFACE TO THE CLP LINEAR PROGRAM SOLVER 11 Valuel corresponding to the information on this line The number Valuel speci es the value for this right hand side coef cient ie7 bi Bounds Record For each variable 11 through In the default lower bound is zero and the default upper bound is plus in nity ie7 by default OSzjlt00 If these are the only bounds you want7 you need not include BoundsRecord The rst line of Bound sRecord contains the text Keyword where Keyword is BOUNDS Each of the other lines has the structure Op NameU Namel or the structure Op NameU Namel Valuel Op7 Valuel The string Op speci es the type of each bound and is one of the following values Op Description LU lower bound Valuel S zj lt 00 UP upper bound 0 S zj S Valuel FX xed variable zj Valuel FR free variable 00 lt zj lt 00 MI minus in nity 00 lt zj lt 0 PL plus in nity 0 S zj lt 00 NameO The string NameU speci es a name for the bound It must be the same for all of these lines Namel The string Namel must be one of the variable names in the NameU eld of the Column sRecord The corresponding variable zj has its bounds set by the current line Endata Record The Endata Record is just one line eyword where Keyword is ENDATA Example In Section 123 the MPS input le is the text below the line ltMPSgtlt CDATA and above the line gtltMPSgt 122 Some Clp Executable Commands Purpose The executable for the Clp linear programming solver has an extensive set of commands This is section contains documentation for some of these commands Convention The command syntax leading railmg 12 CHAPTER 1 SOFTWARE means that the characters in leading are necessary and that any number of the characters in trailing are optional if the trailing characters are present7 they need not all appear but those that do must be in order Some of the commands below are of limited use or not helpful at all when using the Neos email interface to Clp in this case7 a comment to this effect is added at the end of the command description direction The syntax for this command is one of the following three choices direction minimize direction maximize direction zero This sets the objective direction for optimization the default is minimize You can also set the objective direction using the commands minimize and maximize directory The syntax for this command is directory DefaultDiTectory This sets the default directory for reading and writing les To be specific7 the commands import7 export7 saveModel7 and restoreModel7 The initial value for this default directory is the current working directory ie This command is not useful with the email Neos interface to Clp import The syntax for this command is import MpsFileName This will read the Mps formatted le speci ed by MpsFileName it will use the default directory as speci ed by the directory command if MpsFileName is equal to Q the previous value for the le name is used The le name is initially empty ie there is no default value and it must be set if you have libgz7 Clp can read compressed les by ending MpsFileName with the three characters gz This command is not useful with the email Neos interface to Clp maximize The syntax for this command maximize This sets the optimization direction to maximize The default optimization direction is to minimize You can also use the command direct ion to set the optimization direction to maximize minimize The syntax for this command minimize This sets the optimization direction to minimize The default optimization direction is to minimize You can also use the command direct ion to set the optimization direction to minimize primalPivot The syntax for this command is pr ima1Pivot selection This command determines the primal pivot selection method The possible values for selection are auto mat ic exa ct dant z ig part ial st eep est change sprin The Dantzig method is implemented to show a simple method but its use is deprecated Exact 12 NEOS E MAIL INTERFACE TO THE CLP LINEAR PROGRAM SOLVER 13 devex is the method of choice and there are two variants which keep all weights updated but only scan a subset each iteration Partial switches this on while change initially does dantzig until the factorization becomes denser This is still a work in progress primalSimplex The syntax for this command is pr imalSimp1ex This command solves the current model using the primal simplex algorithm The default is to use the exact devex column selection method The time and iterations may be effected by settings such as presolve7 scaling7 crash and also by column selection method7 infeasibility weight and dual and primal tolerances printingOptions The syntax for this command is printing0pt ions option where option is one of the following choices option Description normal print the nonzero column variable values rows print nonzero column variable and row activities all print all column variable and row activities The default value for this option is normal solution The syntax for this command is solution SolutionFileName print the current solution to the le speci ed by SolutionFileName This will use the default di rectory as speci ed by the previous directory command lf SolutionFileName is Q the previous value for the solution le name is used This solution le name is initialized to standard output The amount of output can be varied using the printing opt ions or printMask We use m for the number of rows and n for the number of columns in the matrix A speci ed by the Mps formatted input The solution is output in two parts The rows section of the solution contains the following lines for i 0m71 i NameRowJ PiimalRowJ DualRowJ The columns section of the solution contains the following lines for j 0 7 n 7 1 j ameColuan PiimalalueColumnj DualColuan If you are using this command with the email Noes interface to Clp7 you should use SolutionFile Name equal to which instructs Clp to write the solution to standard output 123 Example Neos Email Interface to Clp Input The email message sent to Neos for this problem was Neos Clp Input for Equation 21 ltdocumentgt ltcategorygt1pltcategorygt ltsolvergtC1pltsolvergt lt inputMet hodgtMPSlt inputMet hodgt ltcommentsgtlt CDATAE Equation 21 in Vasek Chvatal s book Linear Programming 14 CHAPTERSOFTWRE maximize 5x1 4x2 3x3 2 subject to 2x1 3x2 x3 lt 5 r1 4x1 x2 2x3 lt 11 I2 3x1 4x2 2x3 lt 8 r3 x1 x2 x3 gt 0 The solution is x1 2 x2 0 x The residuals are 0s15r1 1s211r2 0s38r3 gtltcommentsgt ltMPSgtltCDATA Up Name0 Name1 alue1 Name Value2 23 56789012 56789012 567890123456 01234567 012345678901 NAME eq21 RUNS N z L r1 L r2 L r3 COLUMNS x1 2 5 r1 2 x1 r2 4 r3 3 x2 2 4 r1 3 x2 r2 1 r3 4 x3 2 3 r1 1 x3 r2 2 r3 2 RHS b r1 5 b I2 11 I3 The next two lines are not necessary because 0 lt x1 is the default bound BOUNDS x1 0 ENDATA gtltMPSgt ltparamgtltCDATA maximize primalSimplex printingUptions all solution gtltparamgt ltdocumentgt 12 NEOS E MAIL INTERFACE TO THE CLP LINEAR PROGRAM SOLVER 15 Con rmation The following con rmation was returned when Neos queued this problem for execution Noes Clp Con rmation for Equation 21 From neos mcsanlgov Sat Jul 12 073643 2008 Date Sat 12 Jul 2008 093642 0500 From Neos Server ltneos mcsanlgovgt To Some One ltsomeonesomewhereedugt Subject NEOS Confirmation for Job 1672727 NEOS has received and assigned your submission as job 1672727 password hFLyEIIzq Current queue Running job1672671 go ASA AMPL submitted 0711 2358 started 0712 0850 job1672701 milp scip AMPL submitted 0712 0305 started 0712 0306 job1672702 milp scip AMPL submitted 0712 0308 started 0712 0309 job1672722 milp scip AMPL submitted 0712 0707 started 0712 0708 job1672723 milp scip AMPL submitted 0712 0709 started 0712 0709 Queued job1672727 lp Clp MPS submitted 0712 0936 Output The following results were returned when Neos nished this problem Noes Clp Output for Equation 1 From neos mcsanlgov Sat Jul 12 074143 2008 Date Sat 12 Jul 2008 094143 0500 From neos mcsanlgov To someonesomewhereedu Subject NEOS Results for Job 1672727 You are using the solver clpmps ZZZZZZZZZZZZZZZZZZZZ CLP Results ZZZZZZZZZZZZZZZZZZZZ Load Avg 00 00 00 Coin LP version 10303 build Aug 18 2006 command line homeneosneosbinclp clpmps At line 4 NAME eq2 1 At line 5 RUWS At line 10 COLUMNS At line 19 RIIS At line 23 ENDATA Problem CE21 has 3 rows 3 columns and 9 elements Model was imported from clpmps in 0001 seconds Switching to line mode 16 CHAPTER 1 SOFTWARE ClpClpClpPresolve 3 0 rows 3 0 columns and 9 0 elements 0 Obj 0 Dual inf 15 3 2 Obj 13 Optimal objective value 13 Optimal objective 13 2 iterations time 0002 ClpClp 0 r1 5 1 1 r2 10 0 2 r3 8 1 0 x1 2 1110223e 16 1 x2 0 2 x3 1 55511151e 17 Clp ZZZZZZZZZZZZZZZZZZZZ CLP Results ZZZZZZZZZZZZZZZZZZZZ 124 Problem maximize 311 12 Wirit z E R subject to 11 7 12 S l 11 i 12 S 3 211 12 S 4 Fill in the missing Characters denoted by in the message below so that e mailing the resulting message to Neos would solve the problem above Do not ll in any text for Characters that should be a spacer ltdocumentgt ltcategorygtlpltcategorygt ltsolvergtClpltsolvergt lt inputMet hodgtMPSlt inputMet hodgt ltcommentsgtlt CDATAE Problem 39a in Vasek Chvatal s book Linear Programming gtltcommentsgt ltMPSgtlt CDATA Up Name0 Name1 alu 1 Name Value2 23 56789012 56789012 567890123456 01234567 012345678901 NAME pr39a RUNS N z r1 r2 3 COLUMNS x1 2 3 r1 1 x1 r2 1 r3 2 12 DUEOE ELA4AIL HVQYERICACUE FO 1Y1E CLILIN114R PIRDCHlAAd SOIJUER x2 r2 1 r3 1 RHS b r1 b r2 b r3 ENDATA gtltMPSgt ltparamgtltCDATA maximize primalSimplex printingUptions all solution gtltparamgt ltdocumentgt CHAPTER SOFTWRE Chapter 2 General Linear Programming Duality Notation We are given the following information mEZ mg EZ Ai7 Rm gtlt ni A E Rm gtlt 71 Alti E ng gtlt ni AS e RmS X W number of equality constraints number of inequality constraints number of free variables number of nonnegative variables objective coef cients corresponding to the free variables objective m 39 col 1 quot to the t39 constraint value corresponding to equality constraints constraint limit corresponding to inequality constraints variables matrix block7 equality constraints and free variables matrix block7 equality constraints and nonnegative variables matrix block7 inequality constraints and free variables matrix block7 inequality constraints and nonnegative variables Note that we use m for m When it appears as a superscript or subscriptl We use a similar notation for the other indicesl General Primal Problem maximize Ai A Ii subject to lt Agi AS gt lt 1 Ii 6 Ii i T T It C C i v 1 gt 1 6 var WW A H l H 19 20 CHAPTER 2 GENERAL LINEAR PROGRAMMING DUALITY Primal in Standard Form De ne Ii I 7 I Where I E R and I 6 Hit The primal problem above is equivalent to Ii 1 E R maximize a 7 75 7 0 I Wrt I E R 1 1 6 RT Ai 7Ai A I b subject to 7142i Aai 7142 I S 71 143i Asi Asa 06 53 Dual in Standard Form y y 6 RT minimize I 7 7b 7 122 y W rt y 6 RT mlt y ylt 6 RJ ATi 7143i Agi 9 Ci subject to iAli Aii iAgi y 2 ici ylt 5 AT A AT 7 General Dual Problem De ne y E Rm by y y 7 y The general dual form is y E Rm minimize b3 bT y Wrt Sltylt ygeRTS AI AT 7 subject to lt gt it gt lt y gt A AS 9 General Duality Theorem The following combinations for the general primal and dual problems are possible and impossible Dual Optional Dual lnfeasible Dual Unbounded lVH mm l Primal Optimal Possible lmpossible lmpossible Primal lnfeasible lmpossible Possible Possible Primal Unbounded lmpossible Possible lmpossible In the case Where the primal and dual have optimal values7 these optimal values are equal lf zi7 1 is feasible for the primal and yi7y is feasible for the dual7 GLEN gtltyy gtlt 21 gtltfgt3b b ltgt 21 Matrix Games Introduction We are given two players X and Y and a matrix A E Rmxn lf player X makes choice j E 17 7 n and player Y makes choice i E 17 7 m7 player X Wins player Y loses A units 21 MATRIX GAMES 21 Strategy We use the notation Pn to denote the set of probability measures on the indices 17 i i 7n iiei7 F1 Pn I 6 RI such that ij 1 If player X adopts a strategy I E Pn and player Y adopts a strategy Q E Pm7 the expected Winnings for player X losing for player Y is m n yTAI Z Z M13111 i1 j1 Lemma inf supQTAz l I E lQ E 2 sup infQTAz l Q E l1 6 Proof For all i E Pn and all Q E Pm7 supQTAz l I E 2 QTAi 2 infQTAi l Q E Taking the inf of the left side With respect to Q E Pm and the sup of the right side With respect to i E Pn we obtain the conclusion of the lemma Lemma For each i E R and Q E Rm7 M x H t 141ij lie 1mm sup QTAI l I E max EA infQTAilQEPm min Ms j luin 1 H t Proof Let k E 17 H7721 be an index such that ZAktjij min 214139ij l i E 1Hi7m 11 j1 De ne 9 6 Rm by 9k 1 and for t39 y It 91 0 Note that y e Pm and that ZAtja cj QTAi j1 min 21413ij l i E 1Hi7m 2 inf QTAi l Q E j1 22 CHAPTER 2 GENERAL LINEAR PROGRAMMING DUALITY But7 from the choice of k we also have that for any Q E Pm7 ZAkjIj ZAkjIj j1 j1 i1 n m min ZAlJij l i 6 1111721 ZAszj j1 1 11 J S ZgiZAig39Ij 11 j1 TAi S infyTAily Pm This completes the proof of the rst inequality in the lemma This other inequality can be proved in a similar way Primal Suppose that player X chooses her strategy rst and then player Y gets to choose his strategy It follows that player X should choose the strategy I E Pn that solves the problem maximize infyTAz l y E Wirit z E Pn We use the lemma above to convert the primal problem to the following equivalent linear programing problem maximize 2 Wirit z 6 RC subject to 21Amzj 2 z 17 7m n j1 Ii 1 We use the notation 0mm lmxn to denote an m X n matrix of zeros ones The problem above can be Written as 2 t 2 E R I Wiri i I E R1 0 11m 2 1 subjectto lt1mx1 7A I S 0m Dual The problem above has the form of a general primal problemi The corresponding dual problem is maximize l 01X lt minimize l 7 lem lt 1 gt Wiriti w E R ye RT 0 llxm w 1 subject to lt 1 iAT gt lt y gt 2 lt0nx1 gt This problem is equivalent to minimize supyTAz l I E Wirit y E Pm This problem corresponds to the case Where player Y makes his choice rst and then player X makes her choice 21 MATRIX GAMES 23 Theorem Both the primal and dual games above have an optimal solutions and the optimal values are equal ie7 inf supyTAz l I E ly E sup infyTAz l y E 1 E 211 Example In problem 151 of the text player X and player Y hide either a nickel or a dime If the two coins match7 X gets both Otherwise7 Y gets both We de ne 11 probability that X chooses for playing a nickel 12 probability that X chooses for playing a dime yl probability that Y chooses for playing a nickel yg probability that Y chooses for playing a dime Payo 39 Matrix The payoff matrix for this game is 5 710 A lt 75 10 gt Primal Problem The corresponding primal problem is maximize 2 wrt 2 E R 7 11 E R 7 12 E R subject to 11 12 l 2 7 511 1012 S 0 2 511 71012 S 0 Standard Form Replacing 2 E R by 2 2 r 7 2 where 2 r E R and 2 E R and using 12 l 7 11 to replace 12 we obtain the following standard form representation of the problem minimize 2 r 7 2 wrt 2 r E R 7 2 E R 7 11 E R 11 S l 272 751110l7zl S0 272 511710l7zl S0 subject to Solution Using Simplex Method We can use 12 as as the slack variable and after one pivot obtain the tableau corresponding to the problem above Then7 after a pivot with 2 as the entering variable and the smallest right hand side as the leaving variable7 we obtain a feasible basis From there the simplex method proceeds as normal Here is the corresponding output printed by the program on 5 Pivot Routine Output for Problem 151 So the solution to the standard form version of the problem is 2 r 07 2 0 7 11 237 12 13 Also note the solution to the dual variables yl 12 and yg 12 can be found along the bottom row because the slack variable 31 corresponds to yl and 32 corresponds to yg Check Answer The dual problem is minimize w wrt w E R 7 yl E R 7 yg E R subject to yl yg l w i 591 5y2 2 0 w 1091 710y2 2 0 24 CHAPTER 2 GENERAL LINEAR PROGRAMMING DUALITY lt suf ces to Check that 2 07 11 237 and 12 13 is feasible for the primal and that w 07 yl 127 and yg 12 is feasible for the dual Solution Using Neos and Clp Input The email message sent to Neos see page 8 for this problem was Neos Clp Input for Problem 1511 ltdocumentgt ltcategorygtlpltcategorygt ltsolvergtClpltsolvergt lt inputMet hodgtMPSlt inputMet hodgt ltcommentsgtlt CDATAE Problem 151 in Vasek Chvatal s book Linear Programming maximize x0 2 subject to x1 x2 1 r1 x0 5x1 10x2 lt 0 r2 x0 5x1 10x2 lt 0 r3 x1 x2 gt 0 The primal solution is x0 0 x1 23 x2 13 gtltcommentsgt ltMPSgtlt CDATA Up Name0 Name1 alu 1 Name Value2 23 56789012 56789012 567890123456 01234567 012345678901 NAME pr151 RUWS N z E r1 L r2 L r3 COLUMNS x0 2 1 r1 0 x0 r2 1 r3 1 x1 r1 1 r2 5 x1 r3 5 x2 r1 1 r2 10 x2 r3 10 RHS b r1 1 b r2 0 b r3 0 BOUNDS F39Re x0 21 MATRIX GAMES ENDATA gtltMPSgt ltparamgtltCDATA maximize primalSimplex printingOptions all solution gtltparamgt ltdocumentgt Output The following results were returned When Neos nished this problem Neos Clp Output for Problem 1511 From neos mcsanlgov Tue Jul 22 082330 2008 Date Tue 22 Jul 2008 102329 0500 From neos mcsanlgov To someonesomewhereedu Subject NEOS Results for Job 1677349 You are using the solver clpmps ZZZZZZZZZZZZZZZZZZZZ CLP Results ZZZZZZZZZZZZZZZZZZZZ Load Avg 003 005 001 Coin LP version 10303 build Aug 18 2006 command line homeneosneosbinclp clpmps At line 4 NAME pr151 At line 5 ROWS At line 10 COLUMNS At line 19 RHS At line 23 BOUNDS At line 25 ENDATA Problem pr151 has 3 rows 3 columns and 8 elements Model was imported from clpmps in 0 seconds Switching to line mode ClpClpClpPresolve 2 1 rows 2 1 columns and 4 4 elements 0 Obj 0 Primal inf 0666667 1 Dual inf 101e10 2 2 Obj 0 Optimal objective value 0 After Postsolve objective 0 infeasibilities dual 0 0 primal 0 0 Optimal objective 0 2 iterations time 0002 Presolve 000 ClpClp 0 r1 1 0 1 r2 66613381e 16 05 2 r3 66613381e 16 05 0 x0 0 0 26 CHAPTER 2 GENERAL LINEAR PROGRAMMING DUALITY 1 x1 066666667 0 2 x2 0 33333333 0 C113 ZZZZZZZZZZZZZZZZZZZZ CLP Results ZZZZZZZZZZZZZZZZZZZZ 212 Problem We consider a game where players X and Y simultaneously and repeatedly choose one of the following options Rock7 Paper7 or Scissor The following table gives the payoff from player Y to player X for each of the possible cases X Rock Pap er Scissor 1 Rock Y Paper 1 0 l Scissor l l 0 Write down a linear programming problem that corresponds to X choosing the optimal strategy under the assumption that Y discovers the strategy Show that Q i 13713713T is the optimal strategy for both X and Y 22 Lagrangians Notation We use R to denote the set of real number nonnegative real numbers together with plus and minus in nity ie R U 007 700 221 Limits Upper Bound Given a set of numbers U C R we say that b is an uppeT bound for U if u S b for all u E U lf 8 is an upper bound for U and s S b for any other upper bound 127 we say that s is the least upper bound for U which is also referred to as the supTemum of U and denoted by ssupu l uE U supu uEU LOWEI39 Bound Given a set of numbers U C R we say that b is a loweT bound for U if u 2 b for all u E U If T is a lower bound for U and T 2 b for any other lower bound 127 we say that T is the greatest lower bound for U which is also referred to as the of U and denoted by T1nfuluEU11161 u 22 LAGRANGIANS 27 222 Example Primal Problem The primal problem for the example in Section 21111 is maximize 2 wirit 2 E R 7 1 E R subject to 11 12 1 2 7 511 1012 S 0 2 511 71012 S 0 We use U to denote the feasible set for this problem ilel7 11 12 1 U 271 E R X R1 2 7 511 1012 S 0 2 511 7 1012 S 0 The extended primal objective function f R X REF 7 R is de ned by fz71 Z if2 zeU 700 otherwise Solving the primal problem is equivalent to maximize wirit 2 E R 7 1 E R Lagrangian The Lagrangian L R X R X R X R 7gt R corresponding to the primal problem Lz717w7y 2 w17 11 7 12 y10 7 2 511 71012y20 7 2 7 511 1012 Note that the free dual variable w corresponds to the equality constraint and the nonnegative dual variables yl 7 y2 correspond to the inequality constraints Claim fzyrinfLzyzywy1 My 6 R X R3 Proof Case 1 Suppose that 27 1 E U and 107 y E R X R It follows that w1 7 11 7 12 y10 7 2 511 71012 y20 7 2 7 511 1012 0 0 0 Lz7 17 107 y 2 1V 1 1 We therefore know that infLz717w7y 1 w7y E R X R3 2 2 But substituting in zero for w and y we conclude that infL27I7wy1 My 6 R X R3 S 2 28 CHAPTER 2 GENERAL LINEAR PROGRAMMING DUALITY Thus the claim holds for this case Case 2 Suppose that l 7 11 7 12 f 0 It follows that Lzzw0 zwl7zl7zg infLz7 z w7 0 l w E R 700 infLzyrw7y l My 6 R X R3 00 Thus the claim holds for this case Case 3 Suppose that 0 7 2 511 7 1012 lt 0 It follows that Lzz0y10 zy107z51171012 infLzz07 y170 l yl E R 700 infLzzwy l my 6 R X R3 700 Thus the claim holds for this case Conclusion The proof of case 0 7 2 7 511 1012 lt 0 is very similar to Case 3 Since that is the nal case7 this completes the proof of this claimi Dual Problem The extended dual objective 9 R X R 7gt R is de ned by 90079 suPL2717wvyl 271 E R X R3 Regrouping the terms de ning Lz7 z w7 y we have 142717707 9 w Z1 yi y2 110 w 591 5W2 12 w i 1091 10 We de ne the set V by M y2 1 V wyeRxR i w 5y1 5 2 0 w low 7 10y 2 0 Using reasoning similar to that in the proof of the claim above7 we obtain 9w7y SUPL2717W79l 27 6 R X R3 w if my 6 V 00 otherwise The dual problem is de ned as minimize gwy wirit w E R 7 y E R This problem is equivalent to minimize w wirit w E R 7 y E R3 subject to yl yg l w i 591 5y2 2 0 w10y1710y2 2 0 22 LAGRANGIANS 29 223 General Duality Primal Problem Using the notation on page 197 the primal problem is maximize fziz wrt Ii 6 R i 1 6 RT where the extended primal objective f R i gtlt RT A R is de ned by Aizi Jr AI 11 AgiIi Ag1 S 53 700 otherwise It 1 cizi 011 if 7 S Lagrangian The Lagrangian L R i gtlt RT gtlt Rm gtlt RT and dual problems is A R corresponding to the primal Lzizyy5 cizi 011 907 Ai1i AI y Asia 143 bEy bin 13 Aiiy Agiys 136 Ay e Agyggt Dual Problem The dual problem is minimize gyy5 wrt y E Rm yg 6 RTS where the extended dual objective 9 Rm gtlt Rmi A R is de ned by Agiy Ain Ci Ay Agyg 2 6 00 otherwise 12 bT 39f sways y T 3y 1 T Weak Duality Theorem For all ii e R fur e R Q 6 Rmi 95 e Rmi g73 supLIivz77S T zi716 Rni X RnT fth infLii7i7y7yg 92 6 Rm X ng 975 2 fiiyi Proof The proof of the rst two equalities is very similar to the proof of the claim on page 27 The inequality follows from the rst two equalities because g7 i supLIivr77S T zi71 E Rni X RnT Lii7i77 infLiiiyyS yy5 E Rm gtlt ng fltii7i 2 2 Remark It follows from the theorem above that if g5 fiii then iii solves the primal problem and Q g solves the dual problem 30 CHAPTER 2 GENERAL LINEAR PROGRAMMING DUALITY 224 Problem De ne X R X R and Y R gtlt R X R We are given the following Lagrangian L z X X Y A R LI17127y17y27y3 3x1 2E2 y14 11 y278 511 i 312 ya23 i 411 i 212 We de ne the extended primal objective f z X A R and dual objective 9 Y A R by fr infL17y W r t y 6 Y 7 99 supL17 y W r t I 6 X 1 Write down a description of the set call it U Where is equal to 700 2 Write down the value of for z E X and z U in terms of 11 and 12 and With any inf 3 Write down a description of the set call it V Where gy is equal to 00 4 Write down the value of gy for y E Y and y V in terms of y1 yg and yg and With any sup Chapter 3 Geometry 31 Geometry Example Problem Consider the plastic cup factory optimization problem from the Section 1 of Professor Burke7s notes 1 Note that the constraint 1115 1215 S 8 has been converted to the equivalent form 11 12 S 1201 maximize 2511 2012 Wirlt z E R subject to 2011 1212 S 1800 11 12 S 120 Output The following pivots correspond to the problem above Pivots for Plastic Cup Problem x1 x2 51 52 b 20 12 1 0 1800 1 1 0 1 120 2 20 0 0 0 r c 11 1 06 005 0 90 0 04 005 1 30 0 5 125 0 2250 r c 22 1 0 0125 15 45 0 1 0125 25 75 0 0 0625 125 2625 Simplex Method 1 The initial tableau in the output above corresponds to the basic solution 11 07 12 0 This corresponds to the intersection of the line labeled A With the line labeled B in the gure on page 32 These two lines are represented by the rows in the equation lt5gtltgtlt3gt 31 32 CHAPTER 3 GEOZWETRY Figure 31 A labels z gt 0 B labels z gt 0 C labels the constraint 2011 12z2 1800 D labels xi M g 120 F labels the objective direction 2520 32 THE SIMPLEX VERTEX THEOREM 33 2 The second tableau in the output above corresponds to the basic solution 11 907 12 0 This corresponds to the intersection of the line labeled B with the line labeled C in the gure These two lines are represented by the rows in the equation 20 12 I1 7 1800 0 1 I2 7 0 3 The third tableau in the output above corresponds to the basic solution 11 457 12 75 This corresponds to the intersection of the line labeled C with the line labeled D in the gure These two lines are represented by the rows in the equation 210 112 gt lt gt lt 1182000 32 The Simplex Vertex Theorem Vertex We are given A E Rmx 7 b E Rm7 c E R and our problem is minimize 5T1 wrt z 6 RC subject to AI S b A point i is called a vertex of z 6 RC AI lt b if it is in z 6 RC AI S b and there are sets of indices I C lm and J C 17 7n such that I J n and i is the unique solution of 2141ij bi for allieI j zj OforalleJ where I and J are the number of indices in the sets I and J respectively Theorem The simplex method proceeds from one vertex to another until it determines that the problem is unbounded or it nds an optimal solution that is also a vertex PI39OOf As a consequence of the results for Blandls selection method7 we only need show that each basic feasible solution is a vertex for the feasible region The simplex method works with the following reformulated version of the problem above minimize 5T1 wrt z E R 7 s E R subject to A1 s b Each pivot of the simplex algorithm corresponds to multiplication of the tableau on the left by a nonsingular 721 l X m 1 matrix see Simplex Algorithm on a Tableau in Matrix Notation in Professor Burkels notes on the Simplex Algorithm We use the notation T E Rm1xnm1 the initial tableau T7 A E b CT 01m 0 34 CHAPTER 3 GEOMETRY where E is the m X m identity matrix Using a similar notation for the current tableau T A A 131 g T A A A lt CT yT 2 gt As noted in Professor Burkels notes where 1751 is denoted by R the matrix 1751 6 Rmxm is nonsingular an A 7 1 TltI T 0X1gtT 31 where B 6 RA Multiplying both sides by the inverse of the matrix factor between tableaus we have R 0mgtlt1 A A T T 32 lt B lyTR A84 gt In the tableau T7 let J be the indices of the 1 components that are nonbasic7 let I be the indices of s that are nonbasic7 and let i denote the basic solution This solution also satis es the equation in the initial tableau TA For each i E I we have i 0 and hence n ZAlJij bi forz39 e I 33 j1 ij 0 forj E J So it suf ces to show that there is only one solution to these equations to complete the proof We use the one to one mapping B Lnm Hlnm to represent the current basis ie each row index in the tableau T is mapped to the index of the corresponding variable where 17 A A A 7 n correspond to z and n 17A A A 7 n m correspond to 8A We use KlA A A to denote the set ofi E 1AAA7m such that S nA Note that each component of I that is basic can be written as 130 where i 6 KA It follows from equation 32 that ieK a RkiAkBiforklAAAm i K a R EkBinfork1AAAm remember that E is the m X m identity matrixA Note that each component of s that is basic can be written as 33in where 239 KA The matrix R is nonsingular and hence its determinant is nonzeroA We use 17AAAIlIl to index the elements I iAeA7 the nonbasic components of 8A Note that 1 The matrix R has nonzero determinantA Using expansion by minors for the columns of 13 corresponding to EkBZn above7 we conclude that the following matrix has nonzero determinant ALB lt AAIlt1gtBltKlt1gtgt7w mBMKi gt 1lKlgtBK17 7 1lKlgtBKlKl But this is just a reordering of the columns in the matrix corresponding to equation 33 with the nonbasic columns of I removed iAeA7 the columns in JA Hence it is not singular and this completes the proof 3 3 DEGENERACY GEOZWETRY Figure 32 A labels e2 3 0 B labels e1 3 0 c labels the cohstralht 2011 12z2 g 1800 D labels e1 M g 120 E labels e1 g 90 F labels the objective direction 25 20 33 Degeneracy Geometry Pivots The following plvots correspond to the problem above Pivots for Degenerate Problem MN 0H 2 rgt c OHOOALWHH 12 maximize OOOH 25ml 20m subject to 2011 12z2 12 2 ooo ooo Wit g 1800 1 90 2 zeRJr 36 CHAPTER 3 GEOMETRY r c 12 0 1 008333 0 1667 0 0 0 008333 1 06667 30 1 0 0 0 90 0 0 1667 0 8333 2250 r c 25 0 1 O125 25 0 75 0 0 O125 15 1 45 1 0 0125 15 0 45 0 0 O625 125 0 2625 Simplex Method 1 F The initial tableau in the output above corresponds to the basic solution 11 07 12 0 This corresponds to the intersection of the line labeled A with the line labeled B in the gure on page 35 These two lines are represented by the rows in the equation 1 0 I1 7 0 0 1 I2 7 0 The second tableau in the output above corresponds to the basic solution 11 907 12 0 This corresponds to the intersection of the line labeled B with the line labeled F in the gure These two lines are represented by the rows in the equation 1 0 I1 7 90 0 1 I2 7 0 The third tableau in the output above corresponds to the basic solution 11 907 12 0 This time it corresponds to the intersection of the line labeled F with the line labeled C in the gure These two lines are represented by the rows in the equation 1 0 7 90 20 12 7 180 The fourth tableau in the output above corresponds to the basic solution 11 457 12 75 This corresponds to the intersection of the line labeled C with the line labeled D in the gure These two lines are represented by the rows in the equation lt50 M gtltf ooogt 11 12 11 12 34 Cycling Example The following pivots demonstrate cycling Output for Cycling Demonstration 35 PROBLEMS 37 35 Problems 1 We are given the optimization problem maximize 11 12 Wirit 1 E R3 subject to 11 212 S 2 a Write down the two linear equations corresponding to each vertex of the feasible region corresponding to the problem above b Write down the objective value corresponding to each of the vertices and Which of the vertices correspond to the optimal value for the objective function 2 We are given the optimization problem maximize 11 122 13 Wirit 1 E R subject to 211 12 213 S 2 a Write down the three linear equations corresponding to each vertex of the feasible region corresponding to the problem above b Write down the objective value corresponding to each of the vertices and Which of the vertices correspond to the optimal value for the objective function Index bound lower 26 upper 26 clp executable command 11 neos emai 7 neos email example 13 commands clp executable 11 cup plastic problem 31 cycling example 36 degeneracy geometry 35 duality general linear programming 19 general theorem 20 weak theorem 29 email neos clp example 13 example matrix game 23 mps 11 neos clp email 13 executable clp commands 11 le mps example 11 mps input format 9 format mps example 11 mps input le 9 game example 23 matrix 20 matrix theorem 23 general duality theorem 20 linear programming duality 19 geometry degeneracy 35 simplex method 31 greatest lower bound 26 inf limit 26 in mum 26 input mps example 11 mps le format 9 lagrangian 26 example 27 least upper bound 26 limit 26 lower bound 26 matlab documentation 5 pivot software 5 matrix game 20 game theorem 23 matrix game example 23 mps example 11 input le format 9 INDEX 39 neos clp email 7 clp email example 13 octave documentation 5 pivot software 5 pivot matlab software 5 octave software 5 plastic cup problem 31 simplex method geometry 31 software matlab pivot 5 octave pivot 5 sup limit 26 supremum 26 theorem general duality 20 matrix game 23 vertex 33 weak duality 29 per bound 26 vertex theorem 33 duality theorem 29

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

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

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

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

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

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