How is the standard minimization problem related to the dual standard maximization problem?
At this point, the connection between the standard minimization problem and the standard maximization problem is not clear. Let’s look at an example of a standard minimization problem and another related standard maximization problem.
The linear programming problem
is a standard minimization problem. The related dual maximization problem is found by forming a matrix before the objective function is modified or slack variables are added to the constraints. The entries in this matrix are formed from the coefficients and constants in the constraints and objective function:
To find the coefficients and constants in the dual problem, switch the rows and columns. In other words, make the rows in the matrix above become the columns in a new matrix,
The values in the new matrix, called the transpose, help us to form the constraints and objective function in a standard maximization problem:
Notice the inequalities have switched directions since the dual problem is a standard maximization problem and the names of the variables are different from the original minimization problem. Putting these details together with non-negativity constraints, we get the standard maximization problem
This strategy works in general to find the dual problem.
Example 2 Find the Dual Maximization Problem
In Example 1, we rewrote a linear programming problem as a standard minimization problem,
Find the dual maximization problem associated with this standard minimization problem.
Solution The dual maximization problem can be formed by examining a matrix where the first two rows are the coefficients and constants of the constraints and the last row contains the coefficients on the right side of the objective function.
In the case of this standard maximization problem, we get the 3 x 3 matrix
The vertical line separates the coefficients from the constants, and the horizontal line separates the entries corresponding to the constraints from the entries corresponding to the objective function. Notice that the entries are written before introducing slack variables or rearranging the objective function. The zero in the last column corresponding to the objective function comes from the fact that the objective function has no constants in it.
The coefficients and constants for the dual maximization problem are formed when the rows and columns of this matrix are interchanged. The new matrix,
is utilized to find the dual problem. The first row corresponds to the constraint 1/4 x1 + 7x2 ≤ 4. The second row corresponds to the constraint x1 + 4x2 ≤ 1. Notice that each constraint includes a less than or equal to ( ≤ ) to insure it fits the format of a standard maximization problem. The last row corresponds to the objective function z = 2x1 + 32x2.
These inequalities and equations are combined to yield the standard maximization problem
