Answer to Question #113396 in Operations Research for mary

Question

Two kinds of ice-cream. The vanilla ice-cream sells for $2.50 each while the chocolate flavour ice-cream sells for $4.50 cents each. It costs the company 1 labour hour to make the vanilla flavour ice-cream and 2 labour hours to make the chocolate flavour ice-cream. The company has a total of 300 labour hours available. It costs the company 3 machine hours for the vanilla ice-cream and 2 machine hours for the chocolate ice-cream. The company has a total of 480 machine hours available. How much of each type of ice-cream should the company produce to maximise revenue? What is the maximum revenue?

Answer 1

Maximize revenue:

$S=2.5x+4.5y$ , wher $x$ - count of vanilla ice-cream and $y$ - count of chocolate flavour ice-cream.

Labour time:

$x+2y\le300$

Machine time:

$3x+2y\le480$

$x,y\ge0$

Solving this with simplex method.

To build a system of support equations, additional functions are used (transition to the canonical form).

In the 1st inequality of meaning (≤), we introduce the basis variable x₃. In the 2nd inequality of meaning (≤), we introduce the basis variable x₄.

$x+2y+x3=300\\ 3x+2y+x4=480$

Basic variables are variables that are included in only one equation of the constraint system and, moreover, with a unit coefficient.

We solve the system of equations for basis variables: x₃, x₄

Assuming that the free variables are 0, we get the first reference plan:

X₀ = (0,0,300,480)

A basic solution is called admissible if it is non-negative.

We pass to the basic algorithm of the simplex method.

Iteration number 0.

1. Verification of the optimality criterion.

The current reference plan is not optimal, as there are negative coefficients in the index row.

2. Definition of a new base variable.

As the lead, we select the column corresponding to the variable $y$ , since this is the largest coefficient modulo.

3. Definition of a new free variable.

We calculate the values ​​of D_i in the rows as the quotient of the division: b_i / a_i2

and from them we choose the smallest:

min (300: 2, 480: 2) = 150

Therefore, the 1st row is leading.

The resolving element is (2) and is at the intersection of the leading column and the leading row.

4. Recalculation of the simplex table.

We form the next part of the simplex table. Instead of the variable x3, plan 1 will include the variable $y$ .

The row corresponding to the variable $y$ in plan 1 is obtained by dividing all the elements of row x3 of plan 0 by the resolving element RE = 2. In place of the resolving element, we get 1. In the remaining cells of the column $y$ , we write zeros.

Thus, in new plan 1, row $y$ and column $y$ are filled. All other elements of the new plan 1, including elements of the index row, are determined by the rule of the rectangle.

To do this, we select four numbers from the old plan, which are located at the vertices of the rectangle and always include the resolving element of the RE.

NE = SE - (A * B) / RE

STE is an element of the old plan, RE is the resolving element (2), A and B are elements of the old plan, forming a rectangle with elements of STE and RE.

Iteration number 1.

1. Verification of the optimality criterion.

The current reference plan is not optimal, as there are negative coefficients in the index row.

2. Definition of a new base variable.

As the lead, we select the column corresponding to the variable x, since this is the largest coefficient modulo.

3. Definition of a new free variable.

We calculate the values ​​of Di in the rows as the quotient of the division: b_i / a_i1

and from them we choose the smallest:

min (150: 1/2, 180: 2) = 90

Therefore, the 2nd row is leading.

The resolving element is (2) and is at the intersection of the leading column and the leading row.

4. Recalculation of the simplex table.

We form the next part of the simplex table. Instead of variable x4, plan 2 will include variable x.

The row corresponding to the variable x in plan 2 was obtained by dividing all the elements of row x4 of plan 1 by the resolving element RE = 2. In place of the resolving element, we get 1. In the remaining cells of the column x, we write zeros.

Thus, in new plan 2, row x and column x are filled. All other elements of the new plan 2, including elements of the index row, are determined by the rule of the rectangle.

Verification of the optimality criterion.

Among the values of the index row there are no negative ones. Therefore, this table determines the optimal plan for the task.

The optimal plan can be written as follows:

$x=90$, $y=105$

$S=2.5*90+4.5*105=697.5$