Course 3 : Duality Theory and Dual Simplex Method

Author: OptimizationCity Group

Introduction

One of the most important discoveries in the early development of linear programming was the concept of duality and its many important specification. This discovery revealed that every linear programming problem has associated with it another linear programming problem called the dual. The relationships between the dual problem and the primal problem prove to be extremely useful in a variety of ways. To clarify the subject, consider the model as follow:

If we consider the variable y_i of constraint i, the dual problem of the above model is expressed as follows:

Before converting primary program model to dual form, the objective function and constraints must be compatible, that is, for the primary problem, seek to maximize the objective function and constraints in a smaller or equal form.

Writing the dual problem

The necessary steps to write the dual problem are given below. Whenever the primary problem does not have an equality constraint or a unrestricted variable, it will be as follows:

Step 1) If the objective function of the primal problem is maximization, we make the constraints of the dual problem less or equal.

Step 2) If the constraints of the primary problem are less or equal, then the constraints of the dual problem will be less or equal, too.

Step 3) For each constraint in the primary problem, we consider a variable in the dual problem.

Step 4) The coefficients of the objective function of the dual problem are formed from the numbers on the right hand side of the primary problem.

Step 5) The numbers on the right hand side of the constraints of the dual problem are obtained from the coefficients of the objective function of the primary problem.

Step 6) All the variables of the primary and dual problem are non-negative.

Example: Write the dual model of the following model.

How to create a dual model is shown in the figure below. If the constraints are smaller or equal, the variables are non-negative and the objective function is maximal, then the dual model can be created as follows.

Dual problem for other forms

If the initial problem has constraints in the form of equality, each constraint in the form of equality is replaced by two constraints with the same variables and coefficients, one greater or equal and the other smaller or equal. Then by multiplying the greater or equal constraint by minus one, both constraints will be smaller or equal.

Example: write the dual model of the following problem.

Solution: The first constraint is equivalent to the following two inequality constraints:

Now the problem becomes like this:

If we denote the variable of the dual problem with the above three constraints by y₁, y₂ , and y₃; the dual problem will be as follows.

By changing the above problem, y₄=y₁-y₂, y₄ becomes a unrestricted variable. Because the result of the difference of two non-negative values y₂ and y₁ can be positive or negative, so we have:

So as a rule we can say:

Whenever an equality constraint is established in the primary problem, the variable corresponding to that constraint in the dual problem is unrestriced.

If the initial problem has a unrestriced variable, then for the unrestricted variable xj, changing the variable (x_j‘-x_j”) is done.

Example: Write the dual model of the following problem.

Solution:

We change the unrestriced x₁ as x₂-x₃.

In this way, the dual problem can be written as follows:

The first constraint can be replaced by the equality constraint. The final form of the problem is as follows:

So as a rule we can say:

Whenever a variable is unrestriced in the primary problem, the contraint of that variable in the dual problem is equality.

Example: Consider the following model:

Construct the dual problem.

Solution:

The optimal solution of primal and dual problems is shown in the table below:

Observation: As we can see in the table above, the value of the shadow price of the constraints in the primal model is equal to the optimal value of the variables in the dual model, which is called the duality theory in the operations research literature. Likewise, the optimal value of the variables in the primal model is equal to the value of shadow price in the dual model. These two models have important properties that we will discuss in the rest of text. The table below lists all the basic solutioin of the primal and dual models for this example.

Observation: It can be seen from the above table that in only one case the solution to the primal and dual problems are feasible; and this solution is the optimal solution of both models. In the other cases, either problem is infeasible.

Relationships between the solutions of the primal and dual problems

Whenever the primay problem has a limited optimal solution, in this case the dual problem also has a limited optimal solution. But if the primal problem has an unbounded solution, then the dual problem has no optimal solution. Both problems can be without optimal solutions, but both problems cannot have unbounded optimal solutions.

The summary of the presented cases is described below.

Example: Construct and graph a primal problem with two decision variables and two functional constraints that has feasible solutions and an unbounded objective function. Then construct the dual problem and demonstrate graphically that it has no feasible solutions.

Solution:

The model is as follows:

If x₁=x₂=c and c approaches to infinity, then Z=2c and therefore the objective function approaches to infinity. The Dual problem is as follows.

The below figures graphically shows the primal model and dual model are unbounded and infeasible, respectively.

The dual problem is infeasible.

Example: Consider the following problem.

a) Construct the dual problem for this primal problem.

b) Solve both the primal problem and the dual problem graphically.

c) Use the information obtained in part (b) to construct a table listing the complementary basic solutions for these problems.

d) Work through the simplex method step by step to solve the primal problem. After each iteration (including iteration 0), identify the basic feasbile solution for this problem and the complementary basic solution for the dual problem.

Solution:

a)

b) The optimal solution of primal model was found graphically in below figure:

The optimal solution is (x₁^*,x₂^*)=(2.5,3.75) and Z^*=45.

The optimal solution of dual model was found graphically in below figure: 

The optimal solution is (y₁^*,y₂^*)=(0.5,3.5) and W^*=45.

c)

d)

Primal : (0,0,20,10) 

Dual : (0,0,-6,-8)

Primal : (0,5,10,0)

Dual : (0,4,-2,0)

Primal : (2.5,3.75,0,0)

Dual : (0.5,3.5,0,0)

Dual Simplex Method

The dual simplex method can be thought of as the mirror image of the simplex method. The simplex method deals directly with basic solutions in the primal problem that are primal feasible but not primal optimal or not dual feasible. It then moves toward an optimal solution to achieve dual feasibility as well (the optimality test for the simplex method). By contrast, the dual simplex method deals with basic solutions in the primal problem that are dual feasible(primal optimal) but not primal feasible. It then moves toward an optimal solution to achieve primal feasibility as well.

The dual simplex method is very useful in certain special types of situations. Ordinarily it is easier to find an initial basic solution that is feasible than one that is dual feasible (primal optimal). However, it is occasionally necessary to introduce many artificial variables to construct an initial basic feasible solution artificially. In such cases it may be easier to begin with a dual feasible basic solution and use the dual simplex method.

In maximization form, the problem to be solved is

We need to introduce the artificial variables S_i to convert the standard format.

The summary of dual simplex method is as follow:

Step 0: After converting any functional constraints in ≥ form to ≤ form (by multiplying through both sides by –1), introduce slack variables (if needed) to construct a set of equations in equal form. Find a basic solution such that the coefficients in row 0 (objective function) are zero for basic variables and nonnegative for nonbasic variables (so the solution is optimal if it is feasible). Go to the step 1.

Step 1: Check to see all the basic variables are nonnegative (b_i≥0 for all i=1,…,m). If they are, then this solution is feasible, and therefore optimal, so stop. Otherwise (b_i<0  Ǝi), go to an step 2.

Step 2: Follow the steps below:

Step 2-1: Determine the leaving basic variable. Select the negative basic variable,r, that has the largest absolute right hand side, meaning:

If all the coefficients of the variables in the r-th row are negative (a_rj≥0 for all j=1,…,n), stop because the problem is infeasible. If a_rj<0 Ǝj  holds, go to step 2-2.

Step 2-2: Determine the entering basic variable. Select the nonbasic variable being made by checking the nonbasic variables with negative coefficients (a_rj<0) in that equation and selecting the one with the smallest absolute value of the ratio of the row 0 coefficient to the coefficient in that equation, Meaning:

In above rule, we enter variable s to the basis and leave variable r from basis. Put a box around the row front of variable x_r, and call this the pivot row. Put a box around the column below of variable x_s, and call this the pivot column. Also call the number that is in both boxes the pivot number.

Step 2-3: Determine the new basic solution by using elementary row operations as follows:

1- Divide the pivot row by the pivot number.

2- For each other row (including row 0) that has a negative coefficient in the pivot column, add to this row the product of the absolute value of this coefficient and the new pivot row.

3- For each other row that has a positive coefficient in the pivot column, subtract from this row the product of this coefficient and the new pivot row.

Go to step 1.

Example: Consider the following problem.

Use the dual simplex method to solve this problem.

Solution:

To begin with, the constraints must be ≤ and then the constraints being equalized by adding the slack variables. In this case, the model is as follows.

The initial basic solution (0,0,0,-3,-5) with Z=0  which is not feasible because x₄ and x₅ are the negative values. Dual simplex method is applied in the following table.

Iteration 0: Select the variable x₅ because |-5|>|-3| as the entering basic variable. To select the leaving  basic variable, we use the ratio test because 12÷2<18÷2 so the variable x₂ is selected as the leaving variable. To leave x₂ and enter x₅ , divide the row 2 by 2.

Iteration 1: Check the termination condition. Because -3 is not greater than zero, the current solution is not optimal. x₄ is the leaving basic variable and according to the minimum ratio test (4÷1>6÷3), x₃ is the entering basic variable.  To construct a new simplex tableau in proper, divide the equation of row 1 by -3.

Iteration 2: We find that this solution is optimal because none of the right hand side is non-negative, so the algorithm is finished.

Example: Use the dual simplex method manually to solve this problem.

Solution:

To start the dual simplex method (for a maximization problem), we must have all the coefficients in row (0) nonnegative. The basic solutions will be infeasible because all of the variables are negative. The details of the dual simplex method are summarized next.

Example: Consider the following model:

a) Solve by the original simplex method. Identify the complementary basic solution for the dual problem obtained at each iteration.

b) Solve the dual of this problem by the dual simplex method. Compare the resulting sequence of basic solutions with the complementary basic solutions obtained in part (a).

Solution:

a)

b)

we construct the dual model for the original model as follows:

Example: Consider the following model:

a) Solve the problem graphically.

b) Use the dual simplex method manually to solve this problem.

c) Draw the path connecting the basic solutions.

Solution:

a)

b)

c) we draw the path of basic solutions for the dual model in below:

The prime-dual simplex algorithm

This algorithm is used for problems that are infeasible (due to the presence of negative numbers on the right hand side of the constraints) and non-optimal (due to the presence of negative numbers in the row 0). The advantage of this algorithm compared to the previous methods is that there is no need to add an artificial variable. The prime-dual algorithm is based on the concepts of the prime simplex and the dual simplex algorithm.

Note: There are other algorithms called prime-dual algorithm, which, despite the nominal similarity, have major differences from each other in terms of the solution method and the efficiency of the algorithm.

Steps of the prime-dual simplex algorithm

Step 1. Like the standard form of the simplex method, transform all the constraints of the problem into a smaller or equal form and the objective function into a maximum.

Step 2. After adding auxiliary variables to the constraints, enter the problem into the simplex table.

Step 3. Calculate the amount of change in the objective function by calculating the effect of using the prime simplex or the dual simplex as follows:

A) prime simplex effect: This effect is checked when there is a variable with a negative coefficient in the row 0 and the number of the pivot column and the value on the right hand side opposite this number are non-negative. This effect is calculated as follows.

b) Dual simplex effect: This effect can be calculated when there is a variable in the zero row with a non-negative coefficient and the number of the pivot column and the value on the right hand side opposite this number are negative. This effect is similar to part A and is calculated as follows.

Step 4. We select the largest calculated absolute value related to the effect of the prime and dual simplex and act according to the prime or dual algorithms. If it is not possible to use a prime or a dual simplex, you have reached the end of the operation, otherwise go to step 3.

Example: Consider the following problem.

Solution:

Based on steps 1 and 2, we transform the problem as follows.

The prime simplex effect is calculated according to the presence of the negative coefficient x₂ in the zero row (-6) and the existence of the only positive number in this column, i.e. (a₃₂=5) and the positive number on the right side b₃=35, as follows:

The dual simplex effect is calculated based on the non-negative coefficient x₁ in the zero row (number 3), and the negative numbers in the column below it and b₁=-6 and b₂=-9.

Since the largest calculated effect among the above three effects is related to the prime simplex (42), the new calculations are performed using the prime simplex method. The calculations of this step are done in Table 1.

In Table 2, since there is no negative number in the zero row, it is not possible to calculate the initial simplex effect. But since the only negative number related to the basic variable s₂ is -2, the only negative number is -1.6 in row 2, and 57÷5>0 , it is possible to calculate the dual simplex effect. This effect, which is also the only effect, is calculated as follows:

In Table 3, since there is no negative number in the zero row, it is not possible to calculate the prime simplex effect. In the same way, all the numbers on the right hand side are positive, the dual simplex effect cannot be calculated either. So the table 2 is optimal.

Comparing the number of iteration of this algorithm with the prime simplex algorithm and dual simplex algorithm, it can be seen that the number of iterations here is less than the number of iterations of other algorithms. The following figure shows the performance of this algorithm compared to the prime simplex algorithm, for instance. In the prime-dual simplex method, after two iterations, we reach the optimal solution, which is shown by the red line of the path to the optimal solution. If we solve this problem using the prime simplex algorithm, after three iterations we will reach the optimal solution, which is obviously one iteration more than the prime-dual simplex algorithm. In the figure below, the path to reach the optimal solution using the prime simplex algorithm is shown with the green line.

Special cases in the prime-dual simplex

In this algorithm, similar to the prime simplex algorithm, certain situations may occur, which will be discussed below.

a) Degeneracy

The sign of this case is similar to the simplex algorithm. Refer to lesson 2 to learn how to get ride of a degeneracy.

b) Existence of unbounded optimal solution

The sign of this case is the presence of non-negative numbers (negative or zero) in the pivot column of at least one input variable. To clarify the issue, we give an example.

The tabular representation of the above model is as follows:

The prime simplex effect will have the maximum effect. So the problem is solved through the initial simplex.

According to the column below x₂, the algorithm can be stopped. The absence of a positive number in this column indicates that the optimal value of the objective function is unlimited.

c) Multiple optimal solution

The sign of the existence of multiple optimal solution is the same as the sign of the prime simplex method. For this purpose, refer to lesson 2.

d) Infeasibilty

In the prime simplex method, the presence of an artificial variable with a non-zero value in the optimal table indicates the special case of not having an feasible region. This method is not possible in the prime-dual simplex algorithm due to the absence of artificial variables. The sign of this case in the prime-dual algorithm is the impossibility of determining the pivoe row or pivot column using the prime simplex or the dual simplex method. For this purpose, we give an example.

Because there is no positive number in the row zero, therefore, the effect of the dual simplex is not calculated. The first iteration table is as follows.

The prime simplex effect is calculated as follows.

So the variable s₂ leaves the base and the variable x₁ enters the base. The second iteration table is as follows.

All zero row numbers are non-negative, so it is not possible to calculate the prime simplex effect. Also, since there is no negative number in the pivot row – dual simplex row, it is not possible to have a dual simplex effect, and therefore, this problem has no answer.

Two important theorems in dual theory

Weak duality theorem

if (x₁,x₂,…,x_n) is a feasible solution of the prime problem and (y₁,y₂,…,y_m) is a feasible solution of the dual problem, then we have:

The distance between the optimal objective function of the prime problem and the dual problem is called duality gap. In linear programming, there is no gap between the values ​​of the optimal objective function of the prime and the dual problems, and it is called the strong duality theorem.

Strong duality theorem

if the prime problem has an optimal solution (x₁,x₂,…,xn), its dual problem also has an optimal solution (y₁,y₂,…,y_m) so that: