USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

DUAL PROBLEMS WHEN PRIMAL IS IN THE STANDARD FORM

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 = C1X1+C2X2+ …. CnXn

Subject to a11 X1+a12 X2 + …. a1n Xn<=b1

a21 X1+a22 X2 + …. a2n Xn<=b2

am1 X1+am2 X2 + …. amn Xn<=bm

The dual can be expressed as follows

Minimize Z = B1 Y1 + B2 Y2 + …. + Bm Yn

Subject to a11 Y1+a12 Y2 + …. a1n Yn<=b1

a21 Y1+a22 Y2 + …. a2n Yn<=b2

am1 Y1+am2 Y2 + …. amn Yn<=bm

Y1, Y2 …. Ym >=0

Where Y1, Y2 …. Ym are the dual decision variables.

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

  1. For every primal constraint, there is a dual variable here X1,  X2 …. Xn are the primal constraints and Y1, Y2 …. Yn, are the dual variables.
  2. For every primal variable, there is a dual constraint X1,  X2 …. Xn are the primal variable.
  3. 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 (Y1, Y2 …. Ym) and n constraints (related with X1, X2 …. Xn). 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.

  1. 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.
  2. 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.
  3. The objective function coefficients for x1 and x2 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.
  4. The right-hand-side constraints for constraints (1), (2) and (3) in the primal equal the objective function coefficients for the dual variables y1, y2 and y3. The right-hand-side constraints for, the ith primal constraint equals the objective function coefficient for the ith dual variable.
  5. The variable coefficients for constraint (1) of the primal equal the column coefficients for the dual variable y1. The variable coefficients of constraints (2) and (3) of the primal equal the column (co-efficient of the dual variables Y1 and Y3. The coefficients aij 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. (Xj ≤ 0)

2 y1- y2 ≥ 12,

y1 + 3 y2 ≥ 4.

Dual Problem. Let Y = [Y1, Y2, Y3, Y4] be the dual variables, then the dual problem is to determine Y so as to

Minimise f(Y) = (3, 4, 1, 6) [y1, y2, y3, y4]

y1, y2 are unrestricted in sign

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

Example 4.7. Write the dual of LPP.

3 y1 + 2 y2 – 4 y3 ≥ 1

-y – 4 y1 + 3 y3 ≤- 3

or y1 + 4 y2 – 3 y3 ≥ 3

2 y1 + 8 y3 = 2

y1, y2 , y3 , y4 , y5 ≥ 0

x1, x2 ≥ 0

Dual is Maximise Zy=-9y1+90y2-90 y3-800y4

or if we put y2-y3=y

Minimise Zy=-9 y1+90y-800y4

With constraint

- 2 x2 + 4 x3 + 6 x4 ≥ 50

and x4 unrestricted in sign.

6 y1 – 6 y4 ≥ 10

y1, y4 ≥ 0 Y2, YJ unrestricted