Question #283100

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?


1
Expert's answer
2021-12-28T16:25:30-0500

Let x1,x2,x3x_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: 2x1+2x2+3x32502x_1+2x_2+3x_3\leq 250

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

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

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

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

y1=250(2x1+2x2+3x3)y_1=250-(2x_1+2x_2+3x_3)

y2=300(2x1+4x2+4x3)y_2=300-(2x_1+4x_2+4x_3)

y3=270(2x1+x2+5x3)y_3=270-(2x_1+x_2+5x_3)

Z=120x1+100x2+270x3Z=120x_1+100x_2+270x_3

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

2x1+2x2+3x3+y1+0y2+0y3=2502x_1+2x_2+3x_3+y_1+0y_2+0y_3=250

2x1+4x2+4x3+0y1+y2+0y3=3002x_1+4x_2+4x_3+0y_1+y_2+0y_3=300

2x1+x2+5x3+0y1+0y2+y3=2702x_1+x_2+5x_3+0y_1+0y_2+y_3=270

Z=120x1+100x2+270x3maxZ=120x_1+100x_2+270x_3\to \max , given that  x1,x2,x3,y1,y2,y3x_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:

Zx1x2x3y1y2y3b11201002700000022310025002440103000215001270\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 y1,y2,y3y_1, y_2, y_3 represent the basic variables, the corresponding basic feasible solution is x1=x2=x3=0x_1=x_2=x_3=0, y1=250,y2=300,y3=270y_1= 250,\, y_2= 300,\, y_3= 270.

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

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

R1R1+(270/5)R4R_1\to R_1+(270/5) R_4,

R2R2(3/5)R4R_2\to R_2-(3/5) R_4,

R3R3(4/5)R4R_3\to R_3-(4/5) R_4

Then we normalize the 4th row and obtain:

Zx1x2x3y1y2y3b11846000541458000.81.40100.68800.43.20010.88400.40.21000.254\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 x1x_1 as an entering variable. Then min{88/0.8,84/0.4,54/0.4}=88/0.8=110\min\{88/0.8, 84/0.4, 54/0.4\}=88/0.8=110 and thus, y1y_1 is the corresponding leaving variable. In order to annihilate all entries in column x1x_1, excluding 0.8,  we should add the 2nd row with suitable coefficients to the others:

R1R1+(18/0.8)R2R_1\to R_1+(18/0.8) R_2,

R3R3(0.4/0.8)R2R_3\to R_3-(0.4/0.8) R_2,

R4R4(0.4/0.8)R2R_4\to R_4-(0.4/0.8) R_2.

Then we normalize the 2nd row and obtain:

Zx1x2x3y1y2y3b1014.5022.5040.516560011.7501.2500.75110002.500.510.540000.510.500.510\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 x2x_2 as an entering variable. Then min{110/1.75,40/2.5}=40/2.5=16\min\{110/1.75, 40/2.5\}=40/2.5=16 and thus, y2y_2 is the corresponding leaving variable. Add the 3rd row with suitable coefficients to the others:

R1R1+(14.5/2.5)R3R_1\to R_1+(14.5/2.5)R_3,

R2R2(1.75/2.5)R3R_2\to R_2-(1.75/2.5) R_3,

R4R4+(0.5/2.5)R3R_4\to R_4+(0.5/2.5)R_3.

Then we normalize the 3rd row and obtain:

Zx1x2x3y1y2y3b100019.65.837.61679201001.60.70.48200100.20.40.21600010.60.20.418\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 x1,x2,x3x_1, x_2, x_3 are basic variables and the corresponding basic feasible solution is y1=y2=y3=0y_1=y_2=y_3=0, x1=82x_1= 82 , x2=16x_2=16, x3=18x_3= 18.

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

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


Need a fast expert's response?

Submit order

and get a quick answer at the best price

for any assignment or question with DETAILED EXPLANATIONS!

Comments

No comments. Be the first!
LATEST TUTORIALS
APPROVED BY CLIENTS