Systems of Inequalities and Linear Programming
The non-graphical method is much more complicated, and is perhaps much harder to visualize all the possible solutions for a system of inequalities. However, when you have several equations or several variables, graphing may be the only feasible method.
Application of Systems of Inequalities: Linear Programming
Linear programming involves finding an optimal solution for a linear equation, given a number of constraints.
Learning Objectives
Explain the steps of the Simplex Method to solve applications of systems of linear inequalities
Key Takeaways
Key Points
- The standard form for a linear program is: minimize [latex]c\cdot x[/latex], subject to [latex]Ax=b, x_{i}\geq0[/latex]. c is the coefficients of the objective function, x is the variables, A is the left-side of the constraints and b is the right side.
- The Simplex Method involves choosing an entering variable from the nonbasic variables in the objective function, finding the corresponding leaving variable that maintains feasibility, and pivoting to get a new feasible solution, repeating until you find a solution.
- In the Simplex Method, if there are no positive coefficients corresponding to the nonbasic variables in the objective function, then you are at an optimal solution.
- In the Simplex Method, if there are no choices for the leaving variable, then the solution is unbounded.
Key Terms
- objective function: A function to be maximized or minimized in optimization theory.
- canonical form: The format in which a linear program in standard form can be represented, if the columns of A are rearranged so that it contains the the number of rows in A.
- pivot: Moving from one basic feasible solution to an adjacent basic feasible solution.
- constraint: A condition that a solution to a problem must satisfy.
- the simplex method: An algorithm that optimizes a system of linear inequalities.
A common application of systems of inequalities is linear programming. Linear programming is a mathematical method for determining a way to achieve the best outcome for a list of requirements represented as linear relationships.
An example where linear programming would be helpful to optimize a system of inequalities is as follows:
A factory makes three types of chairs, A, B, and C. The factory makes a profit of $2 on chair A, $3 on chair B, and $4 on chair C. Chair A requires 30 man-hours, chair B requires 20, and chair C requires 10. Chair A needs 2m2 of wood, chair B needs 5m2, and chair C needs 3m2. Given 100 man-hours and 15m2 of wood per week, how many chairs of each type should be made each week to maximize profit?
The Simplex Method
The most common method in linear programming is the Simplex Method, or the Simplex Algorithm. To use the Simplex Method, we need to represent the problem using linear equations. Let a be the number of A chairs, b the B chairs, and c the C chairs. Then, we can write two linear inequalities where three variables must be non-negative, and all constraints must be satisfied. One linear inequality will show a relationship between the man-hours required for the project, and the other will show the amount of wood needed in the project:
First, an inequality for for man-hours, simplified:
[latex]30a+20b+10c\leq100
\\3a+2b+c\leq10[/latex]
Then, an inequality for materials:
[latex-display]2a+5b+3c\leq15[/latex-display]
The function to be maximized (the objective function, and in this case, the profit on the chairs) is:
[latex-display]P=2a+3b+4c[/latex-display]
Standard Form
The standard form for the Simplex Method is:
Minimize [latex]c\cdot x[/latex]
Subject to: [latex]Ax=b, x_{i}\geq0[/latex]
Where [latex]x=[x_{1}, x_{2},..., x_{n}]^{T}[/latex] are the variables, [latex]c=[c_{1}, c_{2},..., c_{n}][/latex] are the coefficients of the objective function, A is the left-side of the constraints, and [latex]b=[b_{1}, b_{2},..., b_{p}]^{T}[/latex] the right.
The solution of a linear program is accomplished in two steps. In the first step, Phase I, a starting extreme point is found. Phase I either gives a basic feasible solution or no solution. If there is no solution, the linear program is considered infeasible.
In the second step, Phase II, the Simplex Algorithm is applied using the solution found in Phase I as a starting point. The possible results from Phase II are either an optimal solution or an unbounded solution.
Achieving Standard Form
You may have noticed that we had been given inequalities, such as [latex]3a+2b+c \leq 10[/latex], but standard form calls for equalities, or equations. We therefore introduce a slack variable that represents the difference between the two sides of the inequality and is non-negative.
This gives us the new equality:
[latex-display]3a+2b+c+s=10[/latex-display]
The other inequality, [latex]2a+5b+3c \leq 15[/latex], becomes:
[latex-display]2a+5b+3c+t=15[/latex-display]
Standard form also requires the objective function to be a minimization. If the problem calls for maximization, multiply the objective function by [latex]-1[/latex].
Here are the pieces for standard form:
[latex-display]x=[a, b, c, s, t]^{T}[/latex-display]
[latex-display]c=[-2, -3, -4, 0, 0][/latex-display]
[latex-display]A=\begin{bmatrix} 3 & 2&1&1& 0\\ 2& 5&3&0&1 \end{bmatrix}[/latex-display]
[latex-display]b=\begin{bmatrix} 10 \\ 15 \end{bmatrix}[/latex-display]
Canonical Tableaux
A linear program in standard form can be represented as a tableau of the form
[latex-display]\begin{bmatrix} 1 & -c&0 \\ 0&A&b \end{bmatrix}[/latex-display]
where the first row defines the objective function and the remaining rows specify the constraints. If the columns of A can be rearranged so that it contains the p-by-p identity matrix (the number of rows in A), then the tableau is said to be in canonical form. The variables corresponding to the columns of the identity matrix are called basic variables, while the remaining variables are called nonbasic or free variables. If the nonbasic variables are assumed to be [latex]0[/latex], then the values of the basic variables are easily obtained as entries in b, and this solution is a basic feasible solution.
Pivots
Moving from one basic feasible solution to an adjacent basic feasible solution is called a pivot. First, a nonzero pivot element is selected in a nonbasic column. The row containing this element is multiplied by its reciprocal to change this element to 1, and then multiples of the row are added to the others to change the other entries in the column to [latex]0[/latex]. The result is that if the pivot is in row [latex]r[/latex], then the column becomes the [latex]r[/latex]-th column of the identity matrix. The variable for this column is now basic, replacing the variable which corresponded to the [latex]r[/latex]-th column of the identity matrix. The variable corresponding to the pivot column enters the set of basic variables, and the variable being replaced leaves the set of basic variables.
Now, the Simplex Method proceeds by performing successive pivot operations which each improve the basic feasible solution; the choice of pivot element at each step is largely determined by the requirement that this pivot improves the solution.
For the entering variable, choose any column in which the entry in the objective row is positive. If all the entries in the objective row are less than or equal to [latex]0[/latex], then no choice of entering variable can be made and the solution is optimal.
For the choice of pivot row, only positive entries in the pivot column are considered. This guarantees that the value of the entering variable will be non-negative. If there are none in the pivot column, then the entering variable can take any non-negative value with the solution remaining feasible. Therefore, the objective function is unbounded.
Next, the pivot row must be selected so that all the other basic variables remain positive. This occurs when the resulting value of the entering variable is at a minimum. If the pivot column is c, then the pivot row r is chosen so that [latex]b_{r}/a_{cr}[/latex] is at a minimum.
Using our example, the canonical tableau is:
[latex-display]\begin{bmatrix} 1&2&3&4&0&0&0 \\ 0&3&2&1&1&0&10\\ 0&2&5&3&0&1&15 \end{bmatrix}[/latex-display]
Columns 5 and 6 are the basic variables s and t, and the basic feasible solution is [latex]a=b=c=0, s=10, t=15[/latex].
Columns 2, 3, and 4 can be selected as pivot columns; for this example column 4 is selected. The values of x resulting from the choice of rows 2 and 3 as pivot rows are [latex]\frac{10}{1}=10[/latex] and [latex]\frac{15}{3}=5[/latex] respectively. Of these, the minimum is 5, so row 3 must be the pivot row. Performing the pivot produces:
[latex-display]\begin{bmatrix} 1&\frac{-2}{3}&\frac{-11}{3}&0&0&\frac{-4}{3}&-20 \\ 0&\frac{7}{3}&\frac{1}{3}&0&1&\frac{-1}{3}&5\\ 0&\frac{2}{3}&\frac{5}{3}&1&0&\frac{1}{3}&5 \end{bmatrix}[/latex-display]
Now columns 4 and 5 represent the basic variables c and s and the corresponding basic feasible solution is:
[latex-display]a=b=t=0, s=5, c=5[/latex-display]
For the next step, there are no positive entries in the objective row, and in fact:[latex]-P=-20+\frac{2}{3}a+\frac{11}{3}b+\frac{4}{3}t[/latex]
So, we should make 5 chairs of type C to maximize our profits with 20 dollars.Licenses & Attributions
CC licensed content, Shared previously
CC licensed content, Specific attribution
