Linear ProgrammingThe objective function is of the formZ = c1x1+ c2x2+ . . . + cnxnwherec1, . . . , cnare given constantsx1, . . . , xnare the variables to be optimized.In the standard form of LP the constraints are formulated asa11x1+ a12x2+ . . . + a1nxn= b1a21x1+ a22x2+ . . . + a2nxn= b2......am1x1+ am2x2+ . . . + amnxn= bmx1≥ 0...xn≥ 0We either want to minimize or maximize the objective function, subject tothe constraints. That is, given the parameters aij, bi, cias input, we want tofind values for the xivariables, such that all constraints are satisfied and theobjective function takes minimum or maximum value, depending on whetherwe want to minimize or maximize.Form the mathematical point of view, minimization and maximization areequivalent, since minimizing an objective function Z means the same as max-imizing −Z, and vice versa.Thus, a linear programming problem (or linear program, for short; abbrevi-ated LP) looks like this for minimization:min Z = c1x1+ c2x2+ . . . + cnxnsubject toa11x1+ a12x2+ . . . + a1nxn= b1a21x1+ a22x2+ . . . + a2nxn= b2......am1x1+ am2x2+ . . . + amnxn= bmx1≥ 0...xn≥ 0For maximization it would look the same, just the “min” would be replacedby “max”.An important restriction is that we only allow linear expressions, both in theobjective function and in the constraints. A linear expression (in terms ofthe xivariables) can only be one of the following:• a constant• a variable ximultiplied by a constant (such as cixi)• sum of expressions that belong to either the above types(Examples: c1x1+ c2x2+ . . . + cnxn, or 3x4− 2).No other types of expressions are allowed. In particular, no product of vari-ables, no logical case separation, etc.The standard form LP in vector-matrix notation:min Z = cxsubject toAx = bx ≥ 0Other formulations are also possible. An often used version is shown below(some textbooks call this one the standard form, rather than the one above):min Z = cxsubject toAx ≥ bx ≥ 0Note: x is meant a column vector, which implies that c must be row a vector,so that the cx product makes sense. If c is a column vector, then we writecT. Usually it is clear from the context, which vector is column and whichis row, so often the distinction is not shown explicitely.When we write an inequality between vectors, then it means it holds com-ponentwise. For example, Ax ≤ b means that when we take matrix-vectorproduct Ax, then each component of the resulting vector is ≤ than the cor-responding component of the vector b. Similarly, x ≥ 0 means that eachcomponent of x is ≥ 0.The different formulations can be easily converted into each other, usuallyat the price of increasing the number of variables.Why does it make sense to increase the number of variables? Because thestandard form may be advantageous (For example, an LP solver programmay require the input in standard form).Exercises1. Convert the following LP into standard form:min Z = 5x − 6ysubject to2x − 3y ≥ 6x − y ≤ 4x ≥ 3Solution: Set y = x2− x3for the free (unbounded) variable y, using thefact that any number can be expressed as the difference of two nonnegativenumbers. Furthermore, introduce a slack variable in each inequality. Theseslack variables, as discussed in class, “fill the gap” between the two sides ofthe inequality, to convert it into an equation.For example, the first constraint 2x − 3y ≥ 6 will be transformed as follows.Let us use x1instead of x, for uniform notation. The variable y will bereplaced by x2− x3, where x2, x3≥ 0. Then we get2 x1|{z}=x− 3 (x2− x3)| {z }this was y− x4|{z}slack variable= 6.Notice that this will indeed force the original left-hand side (the part beforex4) greater than or equal to 6, as the original inequality required. The reasonis that x4≥ 0 must hold, since all variables are forced to be nonnegative inthe standard from. Therefore, the expression before x4must be ≥ 6, sincesubtracting a positive (or 0) quantity makes it equal to 6. If the originalinequality had the ≤ direction, then the only difference would be that wewould add the slack variable, rather than subtracting it.After transforming the other inequalities, too, and also substituting the oldvariables in the objective function with the new ones, we get the entire stan-dard form:min Z = 5x1− 6x2+ 6x3subject to2x1− 3x2+ 3x3− x4= 6x1− x2+ x3+ x5= 4x1− x6= 3x1, x2, x3, x4, x5, x6≥
View Full Document
Unlocking...