Answer to Question #176431 in Operations Research for Nomi

Question

A baby products firm produces a strained baby food containing liver and milk, each of which con- tribute protein and iron to the baby food. Each jar of baby food must have 36 milligrams of protein and 50 milligrams of iron. The company has developed the following linear programming model to determine the number of ounces of liver (x1) and milk (x2) to include in each jar of baby food to meet the requirements for protein and iron at the minimum cost.

minimize Z = 0.05x1 + 0.10x2 (cost, $) subject to

6x1+ 2x2 > or equal to 36 (protein, mg)

5x1 + 5x2 >or equal to 50 (iron, mg)

X1, X2> or equal to 0

Solve this model using the simplex method.

Answer 1

Let us solve the direct linear programming problem using the simplex method, using a simplex table.

Let us determine the minimum value of the function of the function F (X) = 0.05x1 + 0.1x2 under the following conditions-restrictions.

6x1 + 2x2≥36

5x1 + 5x2≥50

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

In the 1st meaning inequality (≥), we introduce the basic variable x₃ with a minus sign. In the second inequality of meaning (≥), we introduce the basic variable x₄ with a minus sign.

6x₁+2x₂-x₃ = 36

5x₁+5x₂-x₄ = 50

Extended matrix of the system of constraints-equalities of this problem:

$\begin{vmatrix} 6 & 2 & -1 & 0 & 36 \\ 5 & 5 & 0 & -1 &50 \end{vmatrix}$

Let us reduce the system to the unit matrix by the method of Jordan transformations.

1. You can choose x3 as the base variable.

We get a new matrix:

$\begin{vmatrix} -6 & -2 & 1 & 0 & -36 \\ 5 & 5 & 0 & -1 &50 \end{vmatrix}$

2. You can choose x4 as the base variable.

We get a new matrix:

$\begin{vmatrix} -6 & -2 & 1 & 0 & -36 \\ -5 & -5 & 0 & 1 &-50 \end{vmatrix}$

Since the system has a unit matrix, we take X = (3,4) as basic variables.

Let's express the basic variables in terms of the others:

x₃ = 6x₁+2x₂-36

x₄ = 5x₁+5x₂-50

Let's substitute them into the objective function:

F (X) = 0.05x₁ + 0.1x₂

There are negative values among the free members b_i, therefore, the resulting baseline plan is not a reference one.

Instead of the variable x₄, you should enter the variable x₂.

We perform transformations of a simplex table using the Jordan-Gauss method.

The final version of the simplex table:

$\begin{vmatrix} basis & B & x_1 & x_2 & x_3 & x_4\\ x_3& -16 & -4& 0 & 1 & -2/5\\ x_2 & 10 & 1 & 1 & 0 &-1/5 \\ F(x0) & -1 & -0.05 & 0 & 0 & 0.02 \end{vmatrix}$

There are negative values among the free members bi, therefore, the resulting baseline plan is not a reference one.

Instead of the variable x₃, enter the variable x₄.

We perform transformations of a simplex table using the Jordan-Gauss method.

$\begin{vmatrix} basis & B & x_1 & x_2 & x_3 & x_4\\ x_4& 40 & 10& 0 & -5/2 & 1\\ x_2 & 18 & 3 & 1 & -1/2 &0 \\ F(x0) & -1.8 & -0.25 & 0 & 0.05 & 0 \end{vmatrix}$

Let's express the basic variables in terms of the others:

x4 = -10x1 + 5 / 2x3 + 40

x2 = -3x1 + 1 / 2x3 + 18

Let's substitute them into the objective function:

F (X) = 0.05x1 + 0.1 (-3x1 + 1 / 2x3 + 18)

or

F (X) = -0.25x1 + 0.05x3 + 1.8

10x1-5 / 2x3 + x4 = 40

3x1 + x2-1 / 2x3 = 18

In the calculations, the value Fc = 1.8 is temporarily disregarded.

The matrix of coefficients A = a (ij) of this system of equations has the form: Let us express the basic variables in terms of the others:

x4 = -10x1 + 5 / 2x3 + 40

x2 = -3x1 + 1 / 2x3 + 18

Let's substitute them into the objective function:

F (X) = 0.05x1 + 0.1 (-3x1 + 1 / 2x3 + 18)

or

F (X) = -0.25x1 + 0.05x3 + 1.8

10x1-5 / 2x3 + x4 = 40

3x1 + x2-1 / 2x3 = 18

In the calculations, the value Fc = 1.8 is temporarily ignored.

Iteration # 1.

1. Checking the criterion of optimality.

The current reference plan is not optimal because there are positive coefficients in the index row.

2. Determination of a new basis variable.

As the leading, we will choose the column corresponding to the variable x3, since this is the largest coefficient.

3. Definition of a new free variable.

Let's calculate the values ​​of Di line by line as a quotient of division: bi / ai3

and choose the smallest of them:

min (-, 6: 1/4) = 24

Therefore, the 2nd line is the leading one.

The permissive element is (1/4) and is at the intersection of the leading column and the leading row.

$\begin{vmatrix} basis & B & x_1 & x_2 & x_3 & x_4\\ x_1& 10 & 1& 1 & 0 & -1/5\\ x_3 & 24 & 0 & 4 & 1 &-6/5 \\ F(x3) & -1.3 & 0 & -0.05 & 0 & -0.01 \end{vmatrix}$

The optimal plan can be written like this:

x₁ = 10, x₂ = 0

F(X) = 0.05*10 + 0.1*0 = 0.5

Answer:0.5