How to Solve Linear Problems?

(specially Graphical)

Linear programming problems come in pairs — a primal linear program (P) and an associated dual linear program (D). I illustrate the mathematical statement of a linear programming problem with the following example.

The following diagrams help one to visualize the primal and dual problems and suggest a way of solving linear programming problems. The area in yellow, called the feasible set, represents values of x₁ and x₂, (or y₁ and y₂), that satisfy the constraints L1 and L2, (or G₁ and G₂). Such vectors x = (x₁, x₂) (or y = (y₁, y₂) are called feasible vectors for the primal program (or dual program).

The lines P', P, and P'' in the primal diagram represent the objective function for different values of P, (988.89, 1288.89, 1588.89). Where P = 1288.89, the objective function (P) intersects the feasible set only at the point (x₁, x₂) = (51.111, 52.222). Here P attains its maximum value on the feasible set.

The points (0,0 ), (72, 0), (51.111, 52.222), and (0, 65) are called the vertices of the feasible set. An optimal program obtains at a vertex of the feasible set.

Similarly, in the dual diagram where D = 1288.89, the objective function (D) intersects the feasible set only at the point (y₁, y₂) = (4.444, 11.111). Here D attains its minimum on the feasible set.

Notes:

1. In the primal problem, the vector (x₁, x₂) = (51.111, 52.222) is the optimal primal program. For any other point in the feasible set, like (x'₁, x'₂) = (40, 40), the value of the objective function is less than the value of the objective function at the optimal program. i.e.,

15 x'₁ + 10 x'₂ = 15*40 + 10*40 = 1000 < 1288.89 = 15*51.111 + 10*52.222 = P

2. In the dual problem, the vector (y₁, y₂) = (4.444, 11.111) is the optimal dual program. For any other point in the feasible set, like (y'₁, y'₂) = (20, 20), the value of the objective function is greater than the value of the objective function at the optimal program. i.e.,

D = 1288.89 = 65*4.444 + 90*11.111 < 3100 = 65*20 + 90*20 = 65 y'₁ + 90 y'₂

Extreme Points and Basic Solutions.

The next diagram repeats the primal diagram above, but from a longer perspective. The primal problem has an extreme point at the intersection of any two constraints, including the non-negativity constraints. The six extreme points are (0, 180), (0, 65), (0, 0), (72, 0), (260, 0), and (51.111, 52.222). Each extreme point is called a basic solution, but only (0, 65), 0, 0), (72, 0), and (51.111, 52.222) are basic feasible solutions. An optimum basic feasible solution for the primal problem maximizes the objective function P on the feasible set.

The feasible set of a linear programming problem is called a convex set, because the feasible set includes the line connecting any two points in the feasible set, (including points on the boundary of the feasible set).

Unbounded and Unfeasible Problems.

The above linear programming problem is called feasible because the feasible sets of the primal and dual programs were non-empty. In other words, vectors x = (x₁, x₂) and y = (y₁, y₂) exist that satisfy the constraints (L1, L2) and (G1, G2).

In the next example, the primal problem is unbounded, and the dual problem is unfeasible.

In the following diagram, the objective function P is unbounded since it intersects the feasible set for any large positive number = P.

The dual linear programming problem is unfeasible since the constraint G1 implies that y₂ <= -10, contradicting the requirement that y₂ >= 0.

If the primal program is unbounded, then the dual program is unfeasible, and vice versa. However, if the primal program is unfeasible, then the dual program is either unbounded or unfeasible, and vice versa.

The General Problem Statement.

Using matrix and vector notation with the superscript ^T indicating the transpose of a matrix or vector, let :

The primal / dual programming problem is stated conveniently as:

This statement of the linear programming problem generalizes to A (m by n) matrix, x and b (1 by n), and y and c (1 by m) matrices.

Adding a Constraint.

Adding a constraint to the primal program adds a variable to the dual program. If the new constraint binds, the optimal programs shift, and the optimal value of each objective function is diminished.

The primal optimal program, x = (x₁, x₂) = (63.333, 21.667), obtains at the intersection of the L2 and L3 constraint lines, with an optimal value for the objective function P = 1166.67.

This solution can be verified by using the simplex solver. If one proceeds this way, the results page displays as:

The dual optimal program is y = (y₁, y₂, y₃) = (0, 6.67, 6.67), with an optimal value for the objective function:

D = 65 y₁ + 90 y₂ + 85 y₃ = D = 65*0 + 90*6.6667 + 85*6.6667 = 1166.67.

The three dimensional dual graph shows this situation. In the diagram below, the objective function, D, and the constraints, G1 and G2, are planes in (Y1, Y2, Y3) space, while the G1 and G2 planes intersect along a line:

Using the online linear programming solver is easier than using a 3-dimensional graph to find the solution when the problem has three or more variables.

Solving the dual problem directly.

One can obtain the solution to the dual problem directly using the online linear programming solver. Multiply the dual objective function by -1 to change it to a maximization problem; similarly change the primal objective function to a minimization problem. Also, switch the x and y variable labels.

Using the simplex solver, the results page displays as:

Of course, solving the dual problem as the primal results in the same solution.

Slack Variables.

In a linear programming problem, each vector x determines a vector s = b - A x, the vector of slack variables for P; each vector y determines a vector t^T = y^T A - c^T, the vector of slack variables for D. In the problem above:

For x = (40, 30) the vector s^T = (25, 25, 15); for y = (0, 10, 10) the vector t^T = (7.5, 5).

For the optimal program x = (63.333, 21.667) the vector s^T = (27.5, 0, 0); for the optimal program y = (0, 6.667, 6.667) the vector t^T = (0, 0);

With slack variables, the constraints of this linear programming problem become the following systems of equations:

The primal problem's system of equations has five variables and three equations. The diagram of this simultaneous system of linear equations for the constraints L1, L2, and L3 follows:

In a basic solution for the primal problem's system of equations, the values of exactly 5 - 3 = 2 variables must be zero. For example, at the point (51.11, 52.22) at the intersection of the L₁ and L₂ equations, the system's variables take the values:

x^T = (x₁, x₂) = (51.11, 52.22) and s^T = (s₁, s₂, s₃) = (0, -0, -18.33).

This basic solution is not a feasible solution because s₃ = -18.33 is negative.

In a basic feasible solution for this system, the values of exactly 2 variables must be zero, the remaining 3 variables must be positive. For example, at the point (26.67, 58.33) at the intersection of the L₁ and L₃ equations, the system's variables take the values:

x^T = (x₁, x₂) = (26.67, 58.33) and s^T = (s₁, s₂, s₃) = (0, 27.5, -0).

The optimum basic feasible solution for this system obtains at the point (63.33, 21.67) at the intersection of the L₂ and L₃ equations. Here the system's variables take the values:

x^T = (x₁, x₂) = (63.33, 21.67) and s^T = (s₁, s₂, s₃) = (27.5, 0, 0).

The basic feasible solution at the origin deserves special mention. Here the system's variables take the values:

x^T = (x₁, x₂) = (0, 0) and s^T = (s₁, s₂, s₃) = (65, 90, 85).

The primal simplex algorithm used to solve linear programming problems starts at the basic feasible solution at the origin, and proceeds to the optimum basic feasible solution along the vertices of the feasible set.

Let:

With slack variables, the constraints of the linear programming problem can be stated in general as the systems of equations:

L.P. Solution Algorithms.

Many algorithms are available for solving linear programming problems. An early step in using a specific algorithm requires one to convert the mathematical statement of the linear programming problem to the standard form for that algorithm.

The standard form for the solution algorithm permits one to have <=, >=, and = constraints in the specification of the feasible set for the primal problem. However, it insists that the RHS (right hand side) of the constraints be non-negative. i.e. the vector of coefficients (b₁, b₂, ... b_n) >= 0.

Many text books introduce students to the simplex algorithm, a computational method that one can use to solve small l.p. problems "by hand," permitting one to learn a systematic method to compute a solution and to understand how the solution depends on the constraints and the objective function.

In the general linear programming problem, A is an (m by n) matrix, I_m is the m dimensional identity matrix; x, t, and b are n-dimensional column vectors; I_n is the n dimensional identity matrix; and y, s and c are m-dimensional column vectors.

The specification of a linear programming problem is said to be in canonical form if all constraints are stated as <= constraints without slack variables s and t; it is said to be in a standard form if stated with slack variables s and t and all constraints are = constraints.

To convert the primal problem to canonical form, change any = constraints into a pair of <= and >= constraints. Change all >= constraints to <= constraints by muliplying both sides of the constraint by -1. When all constraints in the primal program are <= constraints, all constraints in the dual problem must be >= constraints.

If the linear programming problem has a variable x_k that is unrestricted in sign, replace x_k in each constraint with the difference of two new non-negative variables. i.e. x_k = x'_k - x''_k; x'_k >= 0, x''_k >= 0.

(Note that absolute value expressions can be changed into a pair of <= and >= constraints by definition, i.e. |a| <= b implies that -b <= a <= b, and |a| >= b implies that either a >= b, or a <= -b.)

The standard form of the primal problem includes m simultaneous linear equations in n + m variables. Let the matrix A consist of the concatenation of matrices A and I_m, i.e. A = [A | I_m]. From linear algebra I know that a basic solution (a solution with exactly m non-zero variables) can be written as:

x_B = B*b

where B is the inverse of a matrix, Å, formed by selecting m appropriate linearly independent columns of the matrix A.

Consequently, the number of possible basic solutions = (n + m)! / (n! * m!), the number of combinations of n + m variables taken m at a time.

For example, the system above with 2 primal variables and 3 slack variables has (2 + 3)! / (2! * 3!) = 10 basic solutions or extreme points.

Its A = [A | I₃] matrix is:

If I select the columns of A corresponding to the variables x₁, x₂, and s₂, the Å matrix and its inverse, B, are:

Since the vector b^T = (65, 90, 85), the basic solution x_B is:

x_B = (x₁, x₂, s₂) = B*b = (26.6667, 58.3333, 27.5000),

the basic solution at the intersection of the L1 and L3 constraints.

Complementary Necessary and Sufficient Conditions.

If the vectors x, s, y, t satisfy the primal and dual program constraints, and the complementary slackness conditions:

then x (x, s) is an optimal primal program, and y (y, t) is an optimal dual program.

If x and y are optimal programs, then for any other pair of feasible programs x and y:

c^Tx <= c^Tx = y^Tb <= y^Tb

On the Simplex Algorithm web page I present methods to solve linear programming problems by hand. While more sophisticated algorithms are used on computers, the simplex algorithm and primal simplex algorithm permit one to get a grasp of linear programming knowing just the basics of linear algebra. Furthermore, these algorithms were the first ones developed, and were an important step in the development of more sophisticated algorithms, like the dual simplex algorithm, and Karmarkar's algorithm of 1984.