What is Duality?
• It implies that linear programming problems exist in pairs; that is, another linear programming problem is
associated with a given linear programming problem.
Primal Problem
• It is the original formulation of a linear programming problem.
Dual Problem
• It is a derived linear programming problem that is associated with the primal formulation.
The Primal – Dual Relationship
Steps on How to Create a Dual Problem:
• Convert the given primal linear programming problem in a coefficient matrix form.
• Apply the matrix transposition of the original matrix; we shall use Yn to denote that we are dealing with the
dual problem.
• Construct a set of inequalities using the coefficients of the matrix transposition; these form the dual problem.
• Convert the dual problem in to its standard form and solve using simplex method.
• Read the answers to the primal problem from the last row of the final tableau.
Sample Minimization Problem:
The director of MIS center at a large company wants to staff consulting stations with two (2) shifting teams: Team A
will comprise of three (3) senior programmers and three (3) system analysts; and Team B will consist of two (2) senior
programmers and five (5) system analysts. The director wants to use no more than 42 individuals. There will be at least
48 hours to be filled during the week, with a Team A shift serving for four (4) hours and the Team B shift serving for
three (3) hours. The cost of Team A shift is P 3,200 per hour and P 2,800 per hour for Team B shift. Determine the
number of shifts each team has to render in order to minimize cost.
Sample Maximization Problem: (http://www.shelovesmath.com/algebra/advanced-algebra/linear-programming/)
Cel has an online jewelry shop where she sells earrings and necklaces. She sells earrings for P1,350 and necklaces for
P1,800. It takes 30 minutes to make a pair of earrings and 1 hour to make a necklace, and since Cel is a math tutor,
she only has 10 hours a week to make jewelry. In addition, she only has enough materials to make 15 total jewelry
items per week. She makes a profit of P600 on each pair of earrings and P900 on each necklace. How many pairs of
earrings and necklaces should Cel make each week in order to maximize her profit, assuming she sells all her jewelry?
Sensitivity Analysis, Range of Optimality and Range of Feasibility
What is Sensitivity Analysis?
• It is an analysis of Linear Programming solution to possible changes in the various parameters of the original
problem
Range of Optimality
• It is the range over which the objective function coefficient of a variable in the solution can change without
causing the quantity values of the optimal solution change
Range of Feasibility
• It is the range over which the right–hand–side value of the constraint can change without changing the optimal
solution of a problemThis method may be used in particular when the standard way to carry a linear programming model is not available from an initial basic feasible solution. Consider the following LP problem to illustrate the application of the Dual Simplex Method:
To solve the problem above in a standard form, we must add 2 excess non-negative variables for constraints 1 and 2, which we will respectively call X4 and X5. Thus the problem in its standard format is defined by:
Then we build the initial tableau of the Simplex Method:
How to continue the iterations of the Simplex Method? Before that, it is necessary to have an initial basic feasible solution. In this context if we want to use X4 and X5 as basic variables (and hence X1, X2 and X3 as basic variables) it is required that X4 and X5 are greater than or equal to zero, however, their coefficients in the respective rows are negative and therefore we can’t use them (matrix with “1” as a diagonal, and all the other coefficients at zero). So to form the identity we can multiply by “-1” row 1 and 2, obtaining the following:
Now X4 and X5 are basic variables and adopt the values of -1 and -3/2, respectively, which clearly does not satisfy the conditions of non-negativity for the decision variables, i.e. they do not correspond to a basic feasible solution. However, in this instance we can apply the Dual Simplex Method as an alternative resolution. To do this, we will select a variable to leave the base and adopt as a criterion for basic variable associated with “more negative” right hand side (RHS). In this instance the variable is X5. Then to determine which variable will go into the base we find a minimum quotient between the negative of the reduced cost of the non-basic variables and the strictly less than zero entries for non-core variables in row 2 (row associated with more negative right). I.e.: Min {-160/-2; -120/-2; -280/-2} = 60, then the minimum quotient is reached in the second column associated with the non-basic variable X2, therefore said variable enters the base.
Finally one iteration is done by performing the operations of the necessary rows, so we enter X2 into the base, meanwhile at the same time X5 leaves the base. The results are:
Note that now the basic variables are X4 and X2 where only X4 = -1/4 which does not satisfy the condition of being a feasible basic solution. Therefore we make a new iteration, in this case taking the base to the X4 variable and calculate the minimum quotient: Min {-40/-1; -160/-3; -60/-1/2} = 40, then the minimum quotient is in the first column, therefore variable X1 enters the base. Consequently the remaining table is updated as follows:
The basic variables are now X1=1/4 and X2=1/2 (which meet the conditions of non-negativity). Additionally, the reduced cost of the non-basic variables is greater than or equal to zero, therefore we face the optimal solution. We can additionally recognize that the optimum value is V(P)=100 that would be obtained by evaluating the optimal solution to the objective function, however, the value is obtained by said process with a changed sign.
Operation Research 