Linear Programs in Standard
Form
Every linear program can be converted into standard form to be used
in algorithms like the Simplex algorithm where the objective is
maximized, the constraints are equalities and all variables xi are non-negative like so:
maxsubject toc1x1+c2x2+...+cnxna11x1+a12x2+...a1nxn...am1x1+am2x2+...+amnxnx1≥0,...xn≥0=b1=...=bm
To get linear program into standard form, we apply each of the
following rules:
Rule 1: If the problem is min z, convert it to
max −z
Example: min x1+x2⇒max −x1−x2
Rule 2: Remove a negative RHS by multiplying the
whole constraint by −1
Example: −2x1+4x2−x3≥−9⇒2x1−4x2+x3≤9
Rule 3: If a constraint reads ai1x1+ai2x2+...+ainxn≤bi, add a non-negative slack variable si≥0 to get
ai1x1+ai2x2+...+ainxn+si=bi. The slack variable
represents the amount of unused resource.
Example: x1+2x2+x3−x4≤5⇒x1+2x2+x3−x4+s1=5
Rule 4: If a constraint reads ai1x1+ai2x2+...+ainxn≥bi, subtract a non-negative surplus variable si≥0 to get
ai1x1+ai2x2+...+ainxn−si=bi. The surplus
variables represent the amount the LHS exceeds the RHS.
Example: x1+2x2+x3−x4≥5⇒x1+2x2+x3−x4−s1=5
Rule 5: If a variable xj can be positive or negative (called a
free variable, which is unrestricted in sign), substitute xj everywhere (also in the objective)
with the difference xj′−xj′′ where xj′≥0 and
xj′′≥0.
Example: x1+3x2≤7⇒x1+3x2′−3x2′′≤7 with x3′,x3′′≥0 and
x3∈R
Another way to remove free variables is to substitute xj with a constraint that contains
the
variable.
Example: We have the constraint x1+2x2+x3=4 and x3 can be positive or
negative, then
solve for x3=4−x1−2x2 and
substitute 4−x1−2x2 for every
x3.
Rule 6: Resolve variables and constraints with
percentages. The total of all utilization is x1+x2+...xn. If a constraint must be
xk to have p percent, we can write x1+x2+xk+...xnxk≤p⇔(1−p)xk−px1−px2−...−pxn≤0.
Example: We want at least p=30%
of x2 and we have 3 variables. So
x1+x2+x3x3≥0.3
from which follows 0.7x3−0.3x1−0.3x2≤0.
Another way to solve percentage constraints is by
introducing a summation variable xn+1=x1+x2+...+xn from which follows the set of contraints
x1+x2+...+xn−xn+1x1−pxn+1x2−pxn+1...xn−pxn+1=0≤0≤0≤0
This form is easier to compute since a lot of zero-coefficients are
in the matrix. But this adds another variable, which might increase the
overall execution time.
Simplex algorthm