We have already seen the characteristics of the standard form of LPP, let us recall them once again. These are :-

a) All constraints are expressed in the form of equation only the non-negativity constraint is expressed as >=0.

a) The right hand side of each constraint equation is non-negative.

b) All the decision variables are non-negative.

c) The objective function Z, is either to be maximized or minimized.

Let us consider a general problem.

The primal problem can be expressed as

Maximize = C_{1}X_{1}+C_{2}X_{2}+ …. C_{n}X_{n}

Subject to a_{11} X_{1}+a_{12} X_{2} + …. a_{1n }X_{n}<=b_{1}

a_{21} X_{1}+a_{22} X_{2} + …. a_{2n }X_{n}<=b_{2}

a_{m1} X_{1}+a_{m2} X_{2} + …. a_{mn }X_{n}<=b_{m}

The dual can be expressed as follows

Minimize Z = B_{1} Y_{1} + B_{2} Y_{2} + …. + B_{m} Y_{n}

Subject to a_{11} Y_{1}+a_{12} Y_{2} + …. a_{1n }Y_{n}<=b_{1}

a_{21} Y_{1}+a_{22} Y_{2} + …. a_{2n }Y_{n}<=b_{2}

a_{m1} Y_{1}+a_{m2} Y_{2} + …. a_{mn }Y_{n}<=b_{m}

Y_{1}, Y_{2} …. Y_{m} >=0

Where Y_{1}, Y_{2} …. Y_{m} are the dual decision variables.

It may be noted that dual is obtained symmetrically from the primal using the following rules.

- For every primal constraint, there is a dual variable here X
_{1}, X_{2}…. X_{n}are the primal constraints and Y_{1}, Y_{2}…. Y_{n}, are the dual variables. - For every primal variable, there is a dual constraint X
_{1}, X_{2}…. X_{n}are the primal variable. - The constraint coefficient of a primal variable form the left side coefficients of the corresponding dual constraints, and the objective coefficient of the same variable ‘becomes the right hand side of the dual constraint as shown in the shaded column

The above rules indicate that the dual problem will have m variables (Y_{1}, Y_{2} …. Y_{m}) and n constraints (related with X_{1}, X_{2} …. X_{n}). The sense of optimization, type of constraints and the sign of dual variables, for the maximization and minimization types of standard form are given below.

**FORMULATION OF THE DUAL OF THE PRIMAL PROBLEM **

The parameters and structure of the primal provides all the information necessary to formulate a dual.

The following general observations are useful are useful.

- The primal is a maximisation problem and the dual is a minimising problem. The sense of optimisation is always opposite for corresponding primal and dual problems.
- The primal consists of two variables and three constraints and dual consists of three variable and two constraints. The number of variables in the primal always equals the number of constraints in the dual. The number of constraints in the primal always equals the number of variables in the dual.
- The objective function coefficients for x
_{1}and x_{2}in the primal equal the right-hand-side constraints, for constraints (1) and (2) in the dual. The objective function coefficient for the jth primal variable equals the right-hand-side constraint for the jth dual constraint. - The right-hand-side constraints for constraints (1), (2) and (3) in the primal equal the objective function coefficients for the dual variables y
_{1}, y_{2}and y_{3}. The right-hand-side constraints for, the ith primal constraint equals the objective function coefficient for the ith dual variable. - The variable coefficients for constraint (1) of the primal equal the column coefficients for the dual variable y
_{1}. The variable coefficients of constraints (2) and (3) of the primal equal the column (co-efficient of the dual variables Y_{1}and Y_{3}. The coefficients a_{ij}in the primal are transpose of those in the dual. That is, the row coefficients in the primal become column coefficients in the

dual, and vice-versa.

It has been seen earlier in the table comparing the primal and the dual that an equality constraint in one problem responds to an unrestricted variable in the other problem. An unrestricted variable can assume a value which is positive, negative or 0. Similarly, a problem may have non-positive variables. (X_{j} ≤ 0)

2 y_{1}– y_{2} ≥ 12,

y_{1} + 3 y_{2} ≥ 4.

Dual Problem. Let Y = [Y_{1}, Y_{2}, Y_{3}, Y_{4}] be the dual variables, then the dual problem is to determine Y so as to

Minimise f(Y) = (3, 4, 1, 6) [y_{1}, y_{2}, y_{3}, y_{4}]

y_{1}, y_{2} are unrestricted in sign

As for equal to (=) constraint the variable is unrestricted.

**Example 4.7**. Write the dual of LPP.

3 y_{1} + 2 y_{2} – 4 y_{3} ≥ 1

-y – 4 y_{1} + 3 y_{3} ≤- 3

or y_{1} + 4 y_{2} – 3 y_{3} ≥ 3

2 y_{1} + 8 y_{3} = 2

y_{1}, y_{2} , y_{3} , y_{4} , y_{5} ≥ 0

x_{1}, x_{2} ≥ 0

Dual is Maximise Z_{y}=-9y_{1}+90y_{2}-90 y_{3}-800y_{4}

or if we put y_{2}-y_{3}=y

Minimise Z_{y}=-9 y_{1}+90y-800y_{4}

With constraint

– 2 x_{2} + 4 x_{3} + 6 x_{4} ≥ 50

and x_{4} unrestricted in sign.

6 y_{1} – 6 y_{4} ≥ 10

y_{1}, y_{4} ≥ 0 Y2, YJ unrestricted

## Recent Comments