Answer to Question #203613 in Operations Research for Agar

Question

Write the dual of the following LPP after reducing it to canonical form.

Min Z = 3x₁ + 4x₂ + 3x₃

Subject to

2x₁+4x₂ =12

5x₁+3x₃ ≥11

6x₁+ x₂ ≥ 8

x₁,x_2,x₃≥0

Answer 1

The following linear programming problem is set:

$3x_1+4x_2+3c_3\to min$

$2x_1+4x_2+0x_3=12,\newline 5x_1+0x_2+3x_3\geq 11,\newline 6x_1+1x_2+0x_3\geq 8,\newline x_1\geq 0,x_2\geq 0,x_3\geq 0.$

Create a dual linear programming problem.

Let us indulge the problem of linear programming. For the maximum problem, the constraints of the linear programming problem must be either in the form of equalities or in the form "≤", and for the minimum problem - either in the form of equalities or in the form "≥". We have a minimum problem and constraints in the form "≥" or "=". Therefore, we do not take any action.

Let us make the following notation. Vector of coefficients of the objective function of the direct problem:

$C=\begin{pmatrix} 3 & 4 &3 \end{pmatrix}$

Free members of the system of constraints of the direct problem:

$B=\begin{pmatrix} 12 \\ 11\\ 8 \end{pmatrix}$

The matrix of coefficients of the forward problem

$A=\begin{pmatrix} 2 & 4&0 \\ 5&0&3\\ 6&1&0 \end{pmatrix}$

The dual problem is constructed as follows. If the objective function of the original problem is investigated to the maximum, before the objective function of the dual problem is investigated to the minimum and vice versa. The coefficients of the objective function of the dual problem coincide with the free terms of the system of constraints of the direct problem:

$C_{dual}=B^T=\begin{pmatrix} 12&11&8 \end{pmatrix}$

The free terms of the dual problem are equal to the coefficients of the objective function of the direct problem

$B_{dual}=C^T=\begin{pmatrix} 3\\ 4\\ 3 \end{pmatrix}$

The matrix of coefficients of the dual problem is equal to the matrix of coefficients of the direct problem, taken in transposed form.

$A_{dual}=A^T=\begin{pmatrix} 2 & 5&6\\ 4& 0&1\\ 0&3&0 \end{pmatrix}$

The number of variables in the dual problem is equal to the number of constraints in the direct problem, and the number of constraints in the dual problem is equal to the number of variables in the direct problem.

Since our objective function of the dual problem is investigated to the maximum, the constraints of the dual problem must be either in the form "≤" or in the form "=", and the sign "=" will be in the event that the variable of the original problem corresponding to this line does not have restriction in the form of its non-negativity. If in the original problem there are constraints in the form of equalities, then the corresponding variables of the dual problem do not have a constraint in the form of non-negativity.

We have $x_1\geq 0, x_2\geq 0$ and $x_3\geq 0.$ Therefore dual problem there are constraints in the form if inequalities.

Considering the above, we write down the dual linear programming problem:

$12y_1+11y_2+8y_3\to max$

$2y_1+5y_2+6y_3\leq 3, \newline 4y_1+y_3\leq 4, \newline 3y_2\leq 3,\newline y_1 \,is\,unrestricted,y_2\geq 0, y_3\geq 0.$