Computational Optimisation

1) A general LP problem can fail to be a standard maximization problem for one or both of the following reasons. The objective function is to be minimized, rather than maximized. One or more of the contraints has the form Ax + By + Cz + . . . N We must add slack variables to form a system of linear equations.All constraints must be turned into equations including the objective function!

2) We form an initial tableau of coefficients.  The variables as column titles, and rows being  the coefficients in each equation.

3) Pivot operation:We identify the lowest value in the objective function (bottom row) to pivot on.We now find the ratio of every element in the pivot column and its corresponding constant (far right column).The element with the smallest ratio is the pivot element.

4) We now try to make the pivot element 1, by using elementary row operations. After this we try to make every other element in the column 0 by applying multiples of the pivot row to each other row.If there are any negatives left in the objective row, go back to step 3)

1. For each constraint in the primal, we have a corresponding variable in the dual. (This variable is the multiplier).

2. For each variable in the primal, we have a corresponding constraint in the dual. These constraints say that when we multiply the primal constraints with the dual variables and add them, the sum of coecients of any primal variable should be less than or equal to the coecient of the variable in the primal objective function.

3. The dual objective function is to maximize the sum of products of right hand sides of primal constraints and the corresponding dual variables. (This is maximizing the lower bound on the primal LP solutions). 

1) Put the problem into Standard form:Minimise I = y + 2xsubject to x + y - s1 + a1 = 202x + 5y - s2 + a2 = 707x + 3y - s3 + a3 = 84

2) Modify the objective function to include the artificial variables: Minimise I = y + 2x + M(a1 + a2 + a3)subject to x + y - s1 + a1 = 202x + 5y - s2 + a2 = 707x + 3y - s3 + a3 = 84

3 - Substitute for artificial variables in the objective function:

1) Find Ratios:r1 = 10/2 = 5r2 = 8/2 = 4r3 = 4/4 = 1r4 = 7/5 = 1/4r1 > r2 > r4 > r3

2) Because of the second constraint, we can only assign the Xs either 1 or 0 (like a max sat!)We select those 

Simplex Method

Duality

Big M Method

Branch and Bound