Answer to Question #185205 in Operations Research for Vaishu

Question

Write the dual of the following LPP :

Minimize Z = 16x1 + 9x2 + 21x3

Subject to the constraints

x1+ x2 + x3 = 16

2x1 + x2+ x3 ≥ 12

x1, x2 ≥ 0

x3 - unrestricted.

Answer 1

Solution.

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=(16 9 21)

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

$B=\begin{pmatrix} 16 \\ 12 \end{pmatrix}$

The matrix of coefficients of the forward problem:

$A=\begin{pmatrix} 1&1&1\\ 2&1&1 \end{pmatrix}$

$C_{dual}=B^T=(16_{ } 12)$

$B_{dual}=C^T=\begin{pmatrix} 16\\ 9\\ 21 \end{pmatrix}$

$A_{dual}=A^T=\begin{pmatrix} 1& 2 \\ 1& 1\\ 1&1 \end{pmatrix}$

From here, we have dual of the following LLP:

$16y_1+12y_2\implies max,$

$\begin{Bmatrix} y_1+2y_2\leq 16 \\ y_1+y_2\leq 9,\\ y_1+y_2=21. \end{Bmatrix}$