How to Solve Linear Problems?

(specially with Matrix)

Solve an example problem.

Consider the following linear programming problem:

This problem is solved on the graphical solution web page. The primal optimal program is x = (x₁, x₂) = (63.333, 21.667) yielding a value for the objective function P = 1166.67. The dual optimal program is y = (y₁, y₂, y₃) = (0, 6.67, 6.67), with an optimal value for the objective function D = 1166.67.

The Simplex L.P. Standard Form.

The above example can be stated as a particular set of data of the general canonical form.

The standard forms for the primal and dual problems can be stated with the slack variables s and t:

This example l.p. problem has the nice feature that all constraints are <= constraints, and the vector of RHS coefficients b >= 0.

The Basic Simplex Algorithm.

The first version of the simplex algorithm exploits the special structure of the example l.p. problem. The standard form for the initial simplex tableau in the basic simplex algorithm is:

Label rows & columns. Use the data from the example to fill in the initial tableau. Add two new columns: the column of row sums used to check arithmetic, and the column labelled b⁰ / x⁰₁ whose values are determined in step A. 2. below. (If you perform the simplex row operations on the column of row sums, and then check that each entry equals the sum of that row, you have a check on your arithmetic as you proceed with hand calculations.)

Tableau⁰ solution:

Variables s₁, s₂, s₃ are the basic variables, since their columns are e₁^T = (1, 0, 0, 0), e₂^T = (0, 1, 0, 0), and e₃^T = (0, 0, 1, 0). The primal program is s^T = (65, 90, 85), with x^T = (0.00, 0.00). The primal objective function has the value P = c^Tx = c₁x₁ + c₂x₂ = 0.00. The infeasible dual program (found in the bottom row) is t^T = (-15, -10), and y^T = (0.00, 0.00, 0.00).

Proceed to the next tableau as follows:

A. In Tableau⁰:

1. Since the coefficient of x₁ in the last row, -15, is the most negative, x₁ will enter the basis.

2. Compute the ratios b_i / x_i,1 as per the last column: select the row with the smallest positive ratio, L₂ = 72. Thus x_2,1 = 1.25 is the pivot , and slack variable s₂ will leave the basis.

B. To create Tableau¹:

3. Compute row L¹₂ by dividing row L⁰₂ by the pivot = 1.25.

4. Subtract multiples of row L¹₂ from all other rows of Tableau⁰ so that x¹₁ = e₂ in Tableau¹.

Notes:
1. Step A.2 ensures that b¹ >= 0 after step B.4.
2. Step A.1 ensures that step B.4 adds a positive number to P⁰:   1080 = 15*72 = 15 * (90 / 1.25) = c₁ * b⁰₂ / x⁰_2,1
3. The vector x⁰₁ = .25 s⁰₁ + 1.25 s⁰₂ + 1.0 s⁰₃ - 15 e₄. Since the coefficient of s⁰₂, 1.25, is not zero, x⁰₁ can replace s⁰₂ in the basis. Furthermore, the row operations of Step 3. and 4. do not change the status of vectors x⁰₁, s⁰₁,s⁰₃, and e₄ as a basis of the Euclidean space E⁴.

Tableau¹ solution:

Variables x₁, s₁, s₃ are basic variables. The primal program is s^T = (47, 0, 13), with x^T = (72., 0.00). The primal objective function has the value P = c^Tx c₁x₁ + c₂x₂ = 15*72 + 4*0 = 1080.00. The infeasible dual program (found in the bottom row) is t^T = (0, -4), and y^T = (0.00, 12.00, 0.00).

Proceed to the next tableau as follows:

A. In Tableau¹:

1. Since the coefficient of x₂ in the last row, -4, is the most negative, x₂ will enter the basis.

2. Compute the ratios b_i / x_i,2 as per the last column: select the row with the smallest positive ratio, L₃ = 21.667. Thus x_3,2 = 0.60 is the pivot , and slack variable s₃ will leave the basis.

B. To create Tableau²:

3. Compute row L²₃ by dividing row L¹₃ by the pivot = 0.60.

4. Subtract multiples of row L²₃ from all other rows of Tableau¹ so that x²₂ = e₃ in Tableau².

Tableau² solution:

Variables x₁, x₂, s₁ are basic variables. The feasible primal program is s^T = (27.5, 0, 0), with x^T = (63.333, 21.667). The primal objective function has the value P = c^Tx c^Tx = c₁x₁ + c₂x₂ = 15*63.333 + 4*21.667 = 1111.67. The feasible dual program (found in the bottom row) is t^T = (0, 0), and y^T = (0.00, 6.667, 6.667).

Since these feasible programs satisfy the complementary slackness conditions:

t^Tx = t₁x₁ + t₂x₂= 0

y^Ts = y₁s₁ + y₂s₂ + y₃s₃ = 0,

they are optimal programs.

Notes:

1.0 In the Final Tableau, all the coefficients in the last row corresponding to the primal variables, x₁ and x₂, and the slack variables are nonnegative. Therefore, the simplex algorithm terminates displaying the optimal primal and dual programs along with the optimal value of the objective function.

2.0 Each Tableau contains the unit vectors e₁, e₂, e₃, and e₄ among its columns.

3.0 A given Tableau^k has the form:

4.0 The row operations performed on the matrix of each tableau are equivalent to premultiplying the tableau's matrix by some nonsingular matrix. Therefore, a nonsingular matrix B exists such that:

Tableau² = B Tableau⁰

Validity of the Simplex Algorithm.

In block matrix form, the last equation is:

where B is a 4 by 4 (in the example above) nonsingular matrix, i.e. B has an inverse. The last 2 by 2 block of matrices in this equation implies:

Substituting for B in the first matrix equation, the first 2 by 2 block of matrices implies that:

Equating matrices yields:

Furthermore, since Tableau² is the final tableau, y >= 0, so (y, t) is a feasible program for the dual problem.

By construction of the tableau⁰, and since row operations preserve equations in subsequent tableaus:

Ux + Bs = ß --> BAx + Bs = Bb

using 1. and 2. above. But B nonsingular implies the matrix B is nonsingular. Premultiplying by B's inverse yields:

Ax + s = b

Therefore, (x, s) is a feasible program for the primal problem.

Finally, the steps of the simplex algorithm rule that when a slack variable, s_k, is in the basis, the corresponding dual variable y_k = 0. If s_k is not in the basis, then s_k = 0. Therefore, complementary slackness obtains:

y^Ts = 0.

Similarly, if a primal variable, x_k enters the basis (is not 0), then t_k = 0. Therefore, complementary slackness obtains:

t^Tx = 0.

The pairs (x, s) and (y, t) are feasible and obey complementary slackness. Consequently, (x, s) is an optimal program for the primal problem, and (y, s) is an optimal program for the dual problem.

Example Block Matrices.

Look at Tableau², and note that the basic variables, s₁, x₁, x₂, plus the last column are the unit vectors e₁, e₂, e₃, e₄. Listing the columns corresponding to these variables in Tableau⁰ yields a matrix, call it A_B:

Computing the inverse of A_B yields a matrix found in Tableau², namely B:

Premultiplying Tableau⁰ by B yields Tableau².

The Primal Simplex Algorithm.

The basic simplex algorithm described above can be extended to handle a variety of complications, including = constraints with artificial variables, (Hadley, 108-148). However, an algorithm developed by Dantzig et al. for implementation on computers handles these complications in a straightforward manner that is amenable to hand calculation. The standard form for the primal simplex method assumes all constraints are <=, or = constraints, but places no restrictions on the signs of the RHS b_i variables.

In the primal simplex algorithm, a sequence of tableaux are calculated. A given Tableau^k has the form:

after consolidating the center 2 by 2 block of matrices.

This primal simplex algorithm uses a "three-phase method":

The following example will be solved using the primal simplex algorithm (Restrepo, Linear Programming, 58-66), to illustrate this technique.

Click to pop a new window with the primal and dual l.p. problem displayed with the = constraint replaced with <= and >= constraints, and the solution obtained with the online l.p. solver.

The following diagram illustrates the constraints and the objective function at its maximum value.

If necessary, multiply any = constraints by -1 to get the RHS negative, and introduce the slack variables into the statement of the problem. The variable s₃ is an artificial variable, since the third constraint is an equation.

The standard form for the initial primal simplex tableau is:

Label rows & columns. Use the data from the example to fill in the initial tableau. Label column s₃ with a * to indicate that it is an artificial variable. Add two new columns: the column of row sums used to check arithmetic, and the column labelled b / x_k, that will be used in Phases I and II.

Tableau⁰ solution:

Variables s₁, s₂, s₃ are the basic variables, since their columns are e₁^T = (1, 0, 0, 0), e₂^T = (0, 1, 0, 0), and e₃^T = (0, 0, 1, 0). The primal program is s^T = (85, 90, -51.5), with x^T = (0.00, 0.00, 0.00). The primal objective function has the value P = c^Tx = c₁x₁ + c₂x₂ + c₃x₃ = 0.00.

Proceed to the next tableau as follows:

Phase 0. Drive the artificial variables from the basis.

A. In Tableau⁰:

1. Select an artificial variable in the basis: s^*₃ = e₃.

2. Select a nonzero element in row L3 as pivot: x_3,1 = -.6. (I repeat the simplex algorithm with x_3,2 = -1 as the pivot below.)

B. To Create Tableau¹:

3. Compute row L¹₃ = L⁰₃ / (-0.6).

4. Subtract multiples of row L¹₃ from all other rows of Tableau⁰ so that x¹₁ = e₃ in Tableau¹.

Tableau¹ solution:

Basis: x₁, s₁, s₂. The primal unfeasible program: x^T = (85.8333, 0.00, 0.00); s^T = (-0.8333, -17.292, 0). The primal objective function has the value P = 1287.5.

Proceed to the next tableau as follows: Since the artificial variable s^*₃ associated with the = constraint is not in the basis, Phase 0 is complete.

Phase I. Since b¹₁ and b¹₂ are negative, the algorithm is in Phase I.

Goal: Generate a feasible program so that b >= 0.

A. In Tableau¹:

1. Select a target row, r, with b_r < 0: b¹₂ = -17.292, r = 2.

2. Select any column, col, with a negative entry in row 2 as the pivot column: col = 2 associated with variable x₂, x_2,2 = -1.5834.

3. Compute the ratios b_i / x_i,2 as per the last column. Select the row with the smallest positive ratio: L₁ = 1.25. Thus x_1,2 = -0.6667 is the pivot; slack variable s₁ will leave the basis; x₂ will enter the basis.

To Create Tableau²:

4. Compute row L²₁ = L¹₁ / (-0.6667).

5. Subtract multiples of row L²₁ from all other rows of Tableau¹ so that x²₂ = e₁ in Tableau².

Tableau² solution:

Basis: x₁, x₂, s₂. The primal unfeasible program: x^T = (83.75, 1.25, 0.00); s^T = (0, -15.313, 0). The primal objective function has the value P = 1268.75.

Proceed to the next tableau as follows:

Phase I. Since b²₂ is negative, the algorithm is in Phase I.

Goal: Generate a feasible program so that b >= 0.

A. In Tableau²:

1. Select a target row, r, with b_r < 0: b²₂ = -15.313, r = 2.

2. Select any column, col, with a negative entry in row 2 as the pivot column: col = 3 associated with variable x₃, x_2,3 = -0.4375.

3. Compute the ratios b_i / x_i,3 as per the last column. Select the row with the smallest positive ratio: L₂ = 35. Thus x_2,3 = -0.4375 is the pivot; slack variable s₂ will leave the basis; x₃ will enter the basis.

To Create Tableau³:

4. Compute row L³₂ = L²₂ / (-0.4375).

5. Subtract multiples of row L³₂ from all other rows of Tableau² so that x³₃ = e₂ in Tableau³.

Tableau³ solution:

Basis: x₁, x₂, x₃. The primal feasible program: x^T = (40, 10, 35); s^T = (0, 0, 0). The primal objective function has the value P = 1225.

For this tableau, b >= 0, the artificial variable, s^*₃, is not in the basis, and all entries in the last row corresponding to the variables x₁, x₂, x₃, s₁, and s₂ are nonnegative.

The primal simplex algorithm terminates without proceeding to Phase II, since all conditions of Phase I and II are satisfied.

The optimal programs are:

x = (40, 10, 35), s = (0, 0, 0); y = (15.71, 2.86, 7.14), t = (0, 0, 0); P = 1225.

To demonstrate Phase II of the primal simplex algorithm, begin with Tableau⁰ above, but use x_3,2 = -1 as the pivot.

Proceed to the next tableau as follows:

Phase 0. Drive the artificial variables from the basis.

A. In Tableau⁰:

1. Select an artificial variable in the basis: s^*₃ = e₃.

2. Select a nonzero element in row L3 as pivot: x_3,2 = -1

B. To Create Tableau¹:

3. Compute row L¹₃ = L⁰₃ / (-1.0).

4. Subtract multiples of row L¹₃ from all other rows of Tableau⁰ so that x¹₂ = e₃ in Tableau¹.

Tableau¹ solution:

Basis: x₂, s₁, s₂. The primal feasible program: x^T = (0.00, 51.5, 0.00); s^T = (33.5, 64.25, 0). The primal objective function has the value P = 515.

Proceed to the next tableau as follows:

Phase 0 is complete: The artificial variable s^*₃ = 0.

Phase I is complete: b = ß >= 0.

Phase II. Similar to the Basic Simplex Algorithm: try to increase the value of P = µ by obtaining nonnegative entries in Ø (the last row) for the sign-restricted primal and slack variables.

Tableau² solution:

Basis: x₂, x₃, s₂. The primal program: x^T = (0.00, 18, 67); s^T = (0, 14.0, 0). The primal objective function has the value P = 1185.

Proceed to the next tableau as follows:

Phase II. The last row, Ø, still has a negative entry.

Tableau³ solution:

For this tableau, b >= 0, the artificial variable, s^*₃, is not in the basis, and all entries in the last row corresponding to the variables x₁, x₂, x₃, s₁, and s₂ are nonnegative. The primal simplex algorithm terminates.

Basis: x₁, x₂, x₃. The primal feasible program: x^T = (40, 10, 35); s^T = (0, 0, 0). The primal objective function has the value P = 1225.

The optimal programs are:

x = (40, 10, 35), s = (0, 0, 0); y = (15.71, 2.86, 7.14), t = (0, 0, 0); P = 1225.

Unbounded and Unfeasible Problems.

As shown on the graphical web page, the next example has an unbounded primal solution, with an unfeasible dual problem.

To solve this problem using the primal simplex algorithm, set up the initial tableau as usual:

Phase 0: Complete since there are no artificial variables.

Phase I: Since b⁰₂ = -20 <= 0, the algorithm is in Phase I.

Goal: Generate a feasible program so that b >= 0.

A. In Tableau⁰:

1. Select a target row, r, with b_r < 0: b⁰₂ = -20, r = 2.

2. Select any column, col, with a negative entry in row 2 as the pivot column: col = 1 associated with variable x₁, x_2,1 = -1.5.

3. Compute the ratios b_i / x_i,3 as per the last column. Select the row with the smallest positive ratio: L₂ = 13.3. Thus x_2,1 = -1.5 is the pivot; slack variable s₂ will leave the basis; x₂ will enter the basis.

To Create Tableau¹:

4. Compute row L¹₂ = L⁰₂ / (-1.5).

5. Subtract multiples of row L¹₂ from all other rows of Tableau⁰ so that x¹₂ = e₂ in Tableau¹.

Phase I is complete: b = ß >= 0.

Phase II. Try to increase the value of P = µ = 200 by eliminating negative entries from the last row.

Phase I is complete: b = ß >= 0.

Phase II. The coefficient of s₂ = -10.005 in the last row.

Degeneracy and Cycling.

The primal simplex algorithm calculates a sequence of tableaus. The algorithm breaks down when in a given Tableau^k:

a zero entry appears in the ß column and/or in the Ø row for a variable that is not one of the standard basis variables.

The example from N. Paul Loomba (152) illustrates the degeneracy problem.

The three dimensional diagram shows how the three restraining planes intersect at the point (33.33, 16.67, 16.67).

This problem's initial tableau is:

The pivot column is 2, since -30 is the most negative Ø entry; the pivot row is 1, since 50.0 is the smallest b / x₂ ratio; and the pivot = 2. However, row L⁰₃ also has a 50.0 = b / x₂ ratio. Applying the primal simplex algorithm yields the next tableau:

The variable x₂ has replaced s₁ in the basis. But ß₃ = b¹₃ = 0.0 -- the tableau is degenerate.

Charnes perturbation procedure resolves the degeneracy problem by adding small constants to the RHS of the constraints. Letting € = .1, the RHS vector b becomes:

b_p = (b₁+€, b₂+€², b₃+€³)'

The perturbed problem's initial tableau is:

The pivot column is 2, since -30 is the most negative Ø entry; the pivot row is 3, since 50.005 is the smallest b / x₂ ratio; and the pivot = 2. Applying the primal simplex algorithm yields the next tableau:

Because of the b⁰ vector was perturbed, no zero appears in the b¹ vector.

The variable x₂ has replaced the slack variable s₃ in the basis.

The pivot column is 1, since -7 is the most negative Ø entry; the pivot row is 1, since 0.0990 is the least positive b / x₁ ratio; and the pivot = 1. Applying the primal simplex algorithm yields:

The variable x₁ has replaced the slack variable s₁ in the basis.

The pivot column is 3, since -9 is the most negative Ø entry; the pivot row is 2, since 16.6201 is the least positive b / x₃ ratio; and the pivot = 3. Applying the primal simplex algorithm yields:

The variable x₃ replaces the slack variable s₃ in the basis. The basis consists of all three primal variables, x₁, x₂, and x₃.

The last tableau contains the solutions to the primal and dual perturbed problems. Letting:

The solution to the original primal problem is:

(x₁, x₂, x₃, P)' = B * (b₁, b₂, b₃, 0)' = B *(100, 100, 100, 0) = (33.33, 16.67, 16.67, 1650.0)'.

The solution to the dual problem is:

(y₁, y₂, y₃, D)' = (2.5, 3.00, 11.0, 1650.0)'.