Unformatted text preview:

MA515 Homework #4Due Wednesday, September 28Let us assume we have an LP in the formmax z = cTxs.t. Ax = bx ≥ Owhere the matrix A has full row rank as a result of inserting slack variables. We can representthe data in the form of a tableau T . For example, here is the tableau for the GGMC problem:x1x2x3x4x5−z1 2 1 0 0 0 1201 1 0 1 0 0 702 1 0 0 1 0 1005 4 0 0 0 1 0.Each row represents an equation. For example, the first row represents the equation x1+2x2+ x3= 120 and the last row represents the equation 5x1+ 4x2− z = 0 (which isequivalent to z = 5x1+ 4x2.) Note the identity matrix associated with the columns for theslack variables and the column −z.Now suppose we are interested in focusing our attention on a different basis for thecolumn space of A, say, B = {1, 2, 5}. We can perform row operations on the tableau T toresult in a tableau T0with an identity matrix in the columns associated with the new basis(and the column labeled by −z):x1x2x3x4x5−z1 0 −1 2 0 0 200 1 1 −1 0 0 500 0 1 −3 1 0 100 0 1 −6 0 1 −300The rows of T0represent a set of four equations equivalent to the original four equationsof T .1. How can you easily read off the associated basic solution x from T0? Why does thiswork in general?2. How can you easily read off the associated basic directions from T0? Why does thiswork in general?13. How can you easily read off the costs of the associated basic directions from T0? Whydoes this work in general?4. When contemplating a pivot, how can we determine the entering variable from T0?Why does this work in general?5. When contemplating a pivot, how can we determine whether the LP has unboundedobjective function value from T0? Why does this work in general?6. When contemplating a pivot, how can we perform the ratio test using the data in T0?Why does this work in general?7. How can you easily read off the vector y from T0? Why does this work in


View Full Document

UK MA 515 - MA515 Homework 4

Download MA515 Homework 4
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view MA515 Homework 4 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view MA515 Homework 4 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?