Answer to Question #251059 in Operations Research for VINCENT

Question

Use the simplex method to obtain the optimal solution of the dual of following linear programming model

𝑀𝑖𝑛𝑖𝑚𝑖𝑧𝑒 𝑃 = 70𝑥1 + 50𝑥2

𝑠𝑢𝑏𝑗𝑒𝑐𝑡 𝑡𝑜

40𝑥1 + 30𝑥2 ≤ 2400

−20𝑥1 − 10𝑥2 ≥ 1000

𝑥1 ≥ 0, 𝑥2 ≥ 0

Answer 1

Let's solve the direct problem of linear programming by the simplex method, using the simplex table.

Let us determine the minimum value of the objective function $F(x)=70x_1+50x_2$ under the following conditions-restrictions.

$40x_1+30x_2\le2400$

$-20x_1-10x_2\ge1000$

To construct the first reference plan, we reduce the system of inequalities to a system of equations by introducing additional variables (transition to the canonical form).

In the 1st inequality of meaning ($\le$ ) enter the base variable $x_3$. In the 2nd inequality of meaning ($\ge$) we introduce the basic variable $x_4$ with a minus sign.

$40x_1+30x_2+x_3=2400$

$-20x_1-10x_2-x_4=1000$

Let us reduce the system to the identity matrix by the method of Jordanian transformations.

1. You can choose $x_3$ as the base variable.

2. You can choose $x_4$ as the base variable.

We get a new matrix:

$\begin{pmatrix} 40 & 30 &1& 0 & 2400 \\ 20 & 10 & 0 & 1 & -1000 \end{pmatrix}$

Let's move on to the main algorithm of the simplex method.

1. Checking the optimality criterion.

None of the index row values are positive. Therefore, this table determines the optimal task plan.

The final version of the simplex table:

$\begin{pmatrix} x_3&40 & 30 &1& 0 & 2400 \\ x_4&20 & 10 & 0 & 1 & -1000\\ F(x)&0&-70&-50&0&0 \end{pmatrix}$

There are negative values among the basic variables. The objective function is not limited. There is no solution.