Answer to Question #207735 in Operations Research for Richard

Question

According to the model: 

4x1+x2+8x3+5x4+2x5>= 12000 

x2+x4+2x5+3x6>=18000 

F(c)=0,1x1+0,2x2+0,2x3+0,3x4+0,4x5+0x6

Build a dual model, solve using the graphical method 

Answer 1

The following linear programming problem is set:

4x1+x2+8x3+5x4+2x5>= 12000

x2+x4+2x5+3x6>=18000

F(c)=0,1x1+0,2x2+0,2x3+0,3x4+0,4x5+0x6

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 "≥". 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} 0.1 & 0.2 &0.2&0.3&0.4&0 \end{pmatrix}$

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

$B=\begin{pmatrix} 12000\\ 18000 \end{pmatrix}$

The matrix of coefficients of the forward problem

$A=\begin{pmatrix} 4& 1&8&5&2&0\\ 0&1&0&1&2&3 \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} 12000&18000 \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} 0.1\\ 0.2\\ 0.2\\0.3\\0.4\\0 \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} 4 & 0\\ 1& 1\\ 8&0\\ 5&1\\ 2&2\\ 0&3 \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.

Therefore dual problem there are constraints in the form if inequalities.

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

$12000y_1+18000y_2\to max$

$4y_1\leq0.1 , \newline y_1+y_2\leq0.2 , \newline 8y_1\leq 0.2 ,\newline 5y_1+y_2\leq 0.3,\newline 2y_1+2y_2\leq 0.4,\newline 3y_2\leq 0 .$

From here A(0.025,0).

And F=12000•0.025+18000•0=300.

Answer. 300