For every LP problem, there is a corresponding LP problem called the dual.
The original LP problem is referred to as the primal.
In this video, I'll explain their relationships and how to find the dual from the primal.
Let's start with this example.
It's a maximization problem.
Instead of solving it using the simplex method, we are trying to find a lower bound, l, and
an upper bound, u, of the optimal solution, z*.
The z value of any feasible solution is a lower bound, because it's always less than
or equal to the largest value among all the feasible solutions.
For example, let's just consider this point, x1 = 5, and x2 = 2.
The objective function z = 350, which is ≤ the maximum value z*.
In order to find an upper bound, we need to go through the following three steps.
Step 1: Multiply constraint i by a factor ui.
Choose the sign of ui so that all inequalities are <= after multiplication.
Step 2: Add up all the obtained inequalities into a resultant inequality.
Step 3: Make the coefficients of the resultant constraint match the objective function.
Then, the RHS of the resultant constraint is an upper bound of z*.
For this example problem, we multiply the first constraint by 0.
We will get that the left hand side and the right hand side are both equal to 0.
We multiply the second constraint by 10.
We will get this new constraint.
We multiply the third constraint by -10.
We will get this new constraint and the ≥ sign is changed to the ≤ sign.
We multiply the fourth constraint by -0.
We will get this new constraint and the ≥ sign is changed to the ≤ sign.
We do the same for the last constraint.
Now, we add up these inequalities and this is what we get.
The LHS matches the objective function.
So, the RHS, 370, is an upper bound of the maximum value z*.
In order to match the objective function, we may have many possible combinations of
ui.
Each combination corresponds to an upper bound.
Among all these upper bounds, we want to find the minimum one so the bound is exactly equal
to the max z value.
So, the original problem is changed to a minimum upper bound finding problem.
It is equivalent to finding the best possible multiplication factors for constraints so
that the resultant constraint matches the objective function with a minimum RHS.
Let's check these steps in a general case.
We need to multiply each constraint by a nonnegative variable ui.
For the first constraint, we multiply it by u1.
This is the updated constraint.
For the second constraint, we multiply it by u2.
This is the updated constraint.
For the last three constraints, we multiply them by -u3, -u4, and -u5, respectively, so
the ≥ sign will be changed to ≤ sign.
We add them up.
The resultant inequality is listed here.
We want to match the coefs of x1 and x2 here with the coefs of x1 and x2 in the objective
function.
That is, this item is equal to 30.
This item is equal to 100.
We also want to find the minimum RHS, which represent the minimum upper bound of z*.
Therefore, for this original primal problem, we can formulate a corresponding dual problem.
We want to make some changes so the primal and dual will be in the standard form.
For the primal, we want to change this to ≤ by multiplying -1 for both sides.
These two are sign restrictions.
They can be written in a compact form.
For the dual, u4 can be considered as an excess variable because it has a coefficient 1 and
it appears only in this row and not other rows.
So, we can remove this excess variable and change this = sign to a ≥ sign.
We can do the same for u5.
After we have made such changes, this is the updated primal and dual in the standard form.
If you observe carefully, you will find some interesting patterns, which reveal the relations
between the primal and the dual.
In general, the dual can be considered as the transpose of the primal problem.
The primal is a maximization problem, the dual is a minimization problem.
The RHS of the primal will be the objective coefficients in the dual.
The objective coefficients of the primal will be the RHS of the dual.
The coefficients of the constraints will be transposed.
The primal has three constraints, and the dual has three decision variables.
The primal has two decision variables, and the dual has two constraints.
These are more general primal and dual problems in the standard form.
Note that in the primal, all the constraints are ≤ the RHS, and all the decision variables
are ≥ 0.
In the dual, all the constraints are ≥ the RHS, and all the decision variables are ≥ 0.
If you are given a primal problem, you will be able to use these patterns to find the
dual, and vice versa.
If the primal is not in the standard form, you need to use some general rules to determine
the signs of the dual constraints and the variables.
For example, one constraint in the primal has an equal sign, then the decision variable
in the dual is urs.
Another constraint in the primal has a ≥ sign, then, the decision variable in the dual is
≤ 0.
One decision variable in the primal is urs, then the constraint in the dual has an = sign.
Another decision variable in the primal is ≤ 0, then the constraint in the dual is
≤ the RHS.
Okay, that's the relations between the primal and the dual for LP problems.
Thanks for watching.