• On linear programming

    2007-01-31

    Standard form

    • A linear function to be maximized
    e.g. maximize c_1 x_1 + c_2 x_2\,
    • Problem constraints of the following form
    e.g. a_{11} x_1 + a_{12} x_2 \le b_1
    a_{21} x_1 + a_{22} x_2 \le b_2
    a_{31} x_1 + a_{32} x_2 \le b_3
    • Non-negative variables
    e.g. x_1 \ge 0
    x_2 \ge 0

    The problem is usually expressed in matrix form, and then becomes:

    maximize \mathbf{c}^T \mathbf{x}
    subject to \mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0

    Augmented form (slack form)

    Linear programming problems must be converted into augmented form before being solved by the simplex algorithm. This form introduces non-negative slack variables to replace non-equalities with equalities in the constraints. The problem can then be written in the following form:

    Maximize Z in:
    \begin{bmatrix} 1 & -\mathbf{c}^T & 0 \\ 0 & \mathbf{A} & \mathbf{I} \end{bmatrix} \begin{bmatrix} Z \\ \mathbf{x} \\ \mathbf{x}_s \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{b} \end{bmatrix}
    \mathbf{x}, \, \mathbf{x}_s \ge 0

    where xs are the newly introduced slack variables, and Z is the variable to be maximized.

    Example

    The example above becomes as follows when converted into augmented form:

    maximize S_1 x_1 + S_2 x_2\,(objective function)
    subject tox_1 + x_2 + x_3 = A\,(augmented constraint)
     F_1 x_1 + F_2 x_2 + x_4 = F\,(augmented constraint)
     P_1 x_1 + P_2 x_2 + x_5 = P\,(augmented constraint)
     x_1,x_2,x_3,x_4,x_5 \ge 0 

    where x_3,x_4,x_5\, are (non-negative) slack variables.

    Which in matrix form becomes:

    Maximize Z in:
    \begin{bmatrix} 1 & -S_1 & -S_2 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & F_1 & F_2 & 0 & 1 & 0 \\ 0 & P_1 & P_2 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} Z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} \ge 0

     Duality

    Every linear programming problem, referred to as a primal problem, can be converted into a dual problem, which provides an upper bound to the optimal value of the primal problem. In matrix form, we can express the primal problem as:

    maximize \mathbf{c}^T \mathbf{x}
    subject to \mathbf{A}\mathbf{x} \le \mathbf{b}, \, \mathbf{x} \ge 0

    The corresponding dual problem is:

    minimize \mathbf{b}^T \mathbf{y}
    subject to \mathbf{A}^T \mathbf{y} \ge \mathbf{c}, \, \mathbf{y} \ge 0

    where y is used instead of x as variable vector.Augmented form (slack form)

    Linear programming problems must be converted into augmented form before being solved by the simplex algorithm. This form introduces non-negative slack variables to replace non-equalities with equalities in the constraints. The problem can then be written in the following form:

    Maximize Z in:
    \begin{bmatrix} 1 & -\mathbf{c}^T & 0 \\ 0 & \mathbf{A} & \mathbf{I} \end{bmatrix} \begin{bmatrix} Z \\ \mathbf{x} \\ \mathbf{x}_s \end{bmatrix} = \begin{bmatrix} 0 \\ \mathbf{b} \end{bmatrix}
    \mathbf{x}, \, \mathbf{x}_s \ge 0

    where xs are the newly introduced slack variables, and Z is the variable to be maximized.

    Example

    The example above becomes as follows when converted into augmented form:

    maximize S_1 x_1 + S_2 x_2\,(objective function)
    subject tox_1 + x_2 + x_3 = A\,(augmented constraint)
     F_1 x_1 + F_2 x_2 + x_4 = F\,(augmented constraint)
     P_1 x_1 + P_2 x_2 + x_5 = P\,(augmented constraint)
     x_1,x_2,x_3,x_4,x_5 \ge 0 

    where x_3,x_4,x_5\, are (non-negative) slack variables.

    Which in matrix form becomes:

    Maximize Z in:
    \begin{bmatrix} 1 & -S_1 & -S_2 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 & 0 & 0 \\ 0 & F_1 & F_2 & 0 & 1 & 0 \\ 0 & P_1 & P_2 & 0 & 0 & 1 \\ \end{bmatrix} \begin{bmatrix} Z \\ x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} = \begin{bmatrix} 0 \\ A \\ F \\ P \end{bmatrix}, \, \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \\ x_5 \end{bmatrix} \ge 0
    Tag：LP
    cindyasu 发表于13:22:00 | 阅读全文 | 评论 0 | 编辑 | 分享 0
共1页 1