Answer to Question #221270 in Operations Research for Viy

Question

1.)  Establish the initial feasible solutions of the LP model using NCR (North west Corner Rule), MCM ( Minimum Cost Method or Greedy Method), and VAM ( Vogel’s Approximation Method)

 Minimize: C = 14X_1A + 25X_1B + 13X_1C + 18 X_1D.+ 10X_2A + 12X_2B + 13X_2C + 11X_2D+ 15X_3A + 20X_3B + 11X_3C+ 25X_3D

Subject to: X_1A + X_1B + X_1C + X_1D = 140   X_1A + X_2A + X_3A = 100

                X_2A + X_2B + X_2C + X_2D = 160     X_1B + X_2B + X_3B = 100

               X_3A + X_3B + X_3C + X_3D = 50       X_1C + X_2C + X_3C = 50

              X_1D + X_2D + X_3D = 100 X_ij      

Answer 1

$\text{The initial tableau for this problem is: }\\\begin{matrix} & &&&140 \\\hline &&&&160\\\hline&&&&50\\\hline100&100&50&100 \end{matrix} \\\text{Using North-west corner method, we locate the upper-most variable$(X_{1A})$ in the }\\\text{tableau and set it to the min(100,140) = 100 and we cancel out column 1} \\\begin{matrix} 100& &&&40 \\\hline &&&&160\\\hline&&&&50\\\hline X&100&50&100 \end{matrix} \\\text{Repeating the process, we obtain the following tableaus} \\\begin{matrix} 100& 40&&&X\\\hline &&&&160\\\hline&&&&50\\\hline X&60&50&100 \end{matrix} \\\begin{matrix} 100& 40&&&X\\\hline &&&&100\\\hline&&&&50\\\hline X&X&50&100 \end{matrix} \\ \\\begin{matrix} 100& 40&&&X\\\hline &60&50&&50\\\hline&&&&50\\\hline X&X&X&100 \end{matrix} \\\begin{matrix} 100& 40&&&X\\\hline &60&50&50&X\\\hline&&&&50\\\hline X&X&X&50 \end{matrix} \\\begin{matrix} 100& 40&&&X\\\hline &60&50&50&X\\\hline&&&50&X\\\hline X&X&X&X \end{matrix} \\\text{Therefore, the solution is feasible, the solution is $X_{1A}=100,X_{1B}=40,X_{2B}=60$,}\\\text{$X_{2C}=50,X_{2D}=50,X_{3D}=50,C=5570$} \\\text{We locate the smallest cost(10) at $X_{2A}$ in our initial matrix, we then set the value of $X_{2A}$}\\\text{to the min(100,160). Next,we cross out column 1 and reduce $S_2$(160) to 160-100=60. We }\\\text{repeat the process for the remaining uncrossed out rows and columns to obtain the final tableau}\\ \\\begin{matrix} & 100&&40&X\\\hline 100 &&&60&X\\\hline&0&50&&X\\\hline X&X&X&X \end{matrix} \\\text{Therefore, the initial feasible solution is }\\X_{1B}=100,X_{1D}=40,X_{2A}=100,X_{2D}=60, X_{3B}=0,X_{3C}=50,z=5430 \\\text{Next, we use the Vogel's approximation method to find the basic feasible solution. We }\\\text{compute the penalties by computing the difference between the smallest numbers in each}\\\text{row, we select the row with the largest penalty, after which we select the variable with }\\\text{the smallest value.}\\\text{From the table below, column 3 has the largest penalty, we choose $X_{3C}$ since has the smallest}\\\text{cost} \\\begin{matrix} 14 & 25&13&18&140 &&&14-13=1 \\\hline 10 &12&13&11&160&&&11-10=1\\\hline15&20&11&25&50&&&15-11=4\\\hline100&100&50&100&&& \end{matrix} \\\text{Repeating the process, we obtain the final tableau} \\\begin{matrix} 100 &&&40&X\\\hline &100&&60&X\\\hline0&&50&&X\\\hline X&X&X&X \end{matrix} \\X_{1A}=100,X_{1D}=40,X_{2B}=100,X_{2D}=60, X_{3A}=0,X_{3C}=50,z=4530$