Answer to Question #283100 in Operations Research for Sarah

Question

A school organized a book fair and in this book fair a book seller is selling his books under the following rules:

There are three different packages available.

First package contains 2 Islamic books, 2 Science books and 2 Geography books, second package contains 2 Islamic books, 4 Science books and 1 Geography books and third package contains 3 Islamic books, 4 Science books and 5 Geography books. The book fair has a total of 250 Islamic books, 300 Science books, and 270 Geography books. First package makes a profit of Rs. 120, second package makes Rs.100 and third package makes Rs.270 per pack.

How many packs should be made to maximize book fair profits?

What will the profit be?

Answer 1

Let $x_1, x_2, x_3$ denote the number of packages of the first, the second and the third kind, respectively. Then we have the following linear restrictions

The total number of Islamic books must be not greater than 250: $2x_1+2x_2+3x_3\leq 250$

The total number of Science books must be not greater than 300: $2x_1+4x_2+4x_3\leq 300$

The total number of Geography books must be not greater than 270: $2x_1+x_2+5x_3\leq 270$

We want to maximize the book fair profit: $120x_1+100x_2+270x_3\to \max$ , given that  $x_1, x_2, x_3$ are non-negative integers.

Let’s derive the standard form of this problem. Denote

$y_1=250-(2x_1+2x_2+3x_3)$

$y_2=300-(2x_1+4x_2+4x_3)$

$y_3=270-(2x_1+x_2+5x_3)$

$Z=120x_1+100x_2+270x_3$

Then we have the linear programming problem in the standard form:

$2x_1+2x_2+3x_3+y_1+0y_2+0y_3=250$

$2x_1+4x_2+4x_3+0y_1+y_2+0y_3=300$

$2x_1+x_2+5x_3+0y_1+0y_2+y_3=270$

$Z=120x_1+100x_2+270x_3\to \max$ , given that  $x_1, x_2, x_3, y_1, y_2, y_3$ are non-negative integers.

We will solve this problem by the simplex algorithm. We fill the tableau:

$\begin{vmatrix} Z & x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b\\ 1 & -120 & -100 & -270 & 0 & 0 & 0 & 0\\ 0 & 2 & 2 & 3 & 1 & 0 & 0 & 250\\ 0 & 2 & 4 & 4 & 0 & 1 & 0 & 300\\ 0 & 2 & 1 & 5 & 0 & 0 & 1 & 270\\ \end{vmatrix}$

Columns $y_1, y_2, y_3$ represent the basic variables, the corresponding basic feasible solution is $x_1=x_2=x_3=0$, $y_1= 250,\, y_2= 300,\, y_3= 270$.

Since the first row contains non-negative entries, the obtained solution is not optimal.

Select $x_3$ as an entering variable. Then $\min\{250/3, 300/4, 270/5\}=270/5=54$ and thus, $y_3$ is the corresponding leaving variable. In order to annihilate all entries in column $x_3$, excluding the last one,  we should  add the 4^th row with suitable coefficients to the others:

$R_1\to R_1+(270/5) R_4$,

$R_2\to R_2-(3/5) R_4$,

$R_3\to R_3-(4/5) R_4$

Then we normalize the 4th row and obtain:

$\begin{vmatrix} Z & x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b\\ 1 & -18 & -46 & 0 & 0 & 0 & 54 & 14580\\ 0 & 0.8 & 1.4 & 0 & 1 & 0 & -0.6 & 88\\ 0 & 0.4 & 3.2 & 0 & 0 & 1 & -0.8 & 84\\ 0 & 0.4 & 0.2 & 1 & 0 & 0 & 0.2 & 54\\ \end{vmatrix}$

Since the first row contains non-negative entries, the obtained solution is not optimal.

Select $x_1$ as an entering variable. Then $\min\{88/0.8, 84/0.4, 54/0.4\}=88/0.8=110$ and thus, $y_1$ is the corresponding leaving variable. In order to annihilate all entries in column $x_1$, excluding 0.8,  we should add the 2^nd row with suitable coefficients to the others:

$R_1\to R_1+(18/0.8) R_2$,

$R_3\to R_3-(0.4/0.8) R_2$,

$R_4\to R_4-(0.4/0.8) R_2$.

Then we normalize the 2nd row and obtain:

$\begin{vmatrix} Z & x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b\\ 1 & 0 & -14.5 & 0 & 22.5 & 0 & 40.5 & 16560\\ 0 & 1 & 1.75 & 0 & 1.25 & 0 & -0.75 & 110\\ 0 & 0 & 2.5 & 0 & -0.5 & 1 & -0.5 & 40\\ 0 & 0 & -0.5 & 1 & -0.5 & 0 & 0.5 & 10\\ \end{vmatrix}$

Since the first row contains a non-negative entry, the obtained solution is not optimal.

Select $x_2$ as an entering variable. Then $\min\{110/1.75, 40/2.5\}=40/2.5=16$ and thus, $y_2$ is the corresponding leaving variable. Add the 3^rd row with suitable coefficients to the others:

$R_1\to R_1+(14.5/2.5)R_3$,

$R_2\to R_2-(1.75/2.5) R_3$,

$R_4\to R_4+(0.5/2.5)R_3$.

Then we normalize the 3^rd row and obtain:

$\begin{vmatrix} Z & x_1 & x_2 & x_3 & y_1 & y_2 & y_3 & b\\ 1 & 0 & 0 & 0 & 19.6 & 5.8 & 37.6 & 16792\\ 0 & 1 & 0 & 0 & 1.6 & -0.7 & -0.4 & 82\\ 0 & 0 & 1 & 0 & -0.2 & 0.4 & -0.2 & 16\\ 0 & 0 & 0 & 1 & -0.6 & 0.2 & 0.4 & 18\\ \end{vmatrix}$

Now $x_1, x_2, x_3$ are basic variables and the corresponding basic feasible solution is $y_1=y_2=y_3=0$, $x_1= 82$ , $x_2=16$, $x_3= 18$.

Since all entries in the first row are non-negative, the obtained solution is optimal.

The optimal book fair profit is $Z=16792$.