Introduction Notes Theory HOWTO Examples Engineering Error Questions Matlab Maple

Problem

Given the linear objective function

f(x) = c₁x₁ + c₂x₂ + ⋅⋅⋅ + c_nx_n

subject to a system of system of m linear constraints in n variables, where m ≥ n:

a_1,1 x₁ + a_1,2 x₂ + ⋅⋅⋅ a_1,n x_n ≤ b₁
a_2,1 x₁ + a_2,2 x₂ + ⋅⋅⋅ a_2,n x_n ≤ b₂
⋅
⋅
⋅
a_m,1 x₁ + a_m,2 x₂ + ⋅⋅⋅ a_m,n x_n ≤ b_m

and requiring that each variable is positive

x₁ ≥ 0
x₂ ≥ 0
⋅
⋅
⋅
x_n ≥ 0

find a value x which maximizes the function and satisfies the all of the given constraints.

We may write this as maximizing f(x) = c^Tx subject to Ax ≤ b and x ≥ 0.

Assumptions

The rank of the matrix B is M.

Tools

We will use linear algebra and iteration.

Initial Conditions

Define the matrix

where Id_m is the m × m identity matrix and 0_m is an m-dimensional column vector. This is an (n + m + 1) × (m + 1) matrix.

Note that the bottom right entry is a simple zero. This is the value of the objective function f at the point x = 0.

The entries of the bottom row (excluding the last entry) are termed indicators. A negative value in this location will indicate that an increase in the variable associated with that column will result in a positive increase in the objective function.

Iterative Process

Select a column j such that the indicator is negative. Select the row i (not including the last) which at the least increases the jth variable (divide the last column by the entry in the jth column choose the smallest positive entry, ignoring any division-by-zeros) to be the pivot.

Perform Gaussian elimination on the jth column using row i as the pivot (add the appropriate multiples of row i to all other rows (including the last row).

For instructive purposes, it is most useful to reduce the matrix to row-reduced echelon form.

Continue doing so until all indicators are positive.

Terminating Conditions

We finish when all indicators are positive. Assuming row-reduced echelon form was used, for each variable x₁ through x_n for which the column is still in reduced-echelon form read off the value in the last column of the row containing the 1. Otherwise, set the variable to 0.