91Ó°ÊÓ

In order to construct the dual problem, we need to follow these steps: 1. Replace the primal objective function (minimization) with a dual objective function (maximization). 2. Replace the primal constraints (inequalities) with dual constraints (equalities). 3. Transpose the coefficients in the constraints from the primal to the dual problem. The dual problem is given by: $$ \begin{aligned} \text { Maximize } & W=90p+120q \\ \text { subject to } & 2p+3q \leq 3 \\ & 3p+2q \leq 2 \\ & p \geq 0, q \geq 0 \end{aligned} $$

First, we need to convert inequalities into equalities. We can do this by introducing slack variables. Let's introduce slack variables \(s_1\) and \(s_2\): $$ \begin{aligned} \text { Minimize } & C=3x+2y \\ \text { subject to } & 2x+3y + s_1 = 90 \\ & 3x+2y + s_2 = 120 \\ & x \geq 0, y \geq 0, s_1 \geq 0, s_2 \geq 0 \end{aligned} $$

The initial basic feasible solution (BFS) will be obtained by setting x and y to 0: $$ \begin{aligned} BFS_0: x=0, y=0, s_1=90, s_2=120, C=0 \end{aligned} $$ Now, we will create a tableau to start the simplex method.

We will set up the initial simplex tableau for the problem. The tableau looks like this: $$ \begin{array}{c|cccc|c} & x & y & s_1 & s_2 & \text{RHS} \\ \hline s_1 & 2 & 3 & 1 & 0 & 90 \\ s_2 & 3 & 2 & 0 & 1 & 120 \\ \hline C & -3 & -2 & 0 & 0 & 0 \end{array} $$

Following the simplex method, we will choose the most negative entry in the last row as the pivot column (the incoming variable). In this case, x is the incoming variable. Next, we determine the pivot row by calculating the minimum ratio of RHS/entry in pivot column. The minimum ratio is 90/2 = 45, so s_1 is the outgoing variable. The pivot element is 2, so we divide the entire pivot row by 2: $$ \begin{array}{c|cccc|c} & x & y & s_1 & s_2 & \text{RHS} \\ \hline x & 1 & \frac{3}{2} & \frac{1}{2} & 0 & 45 \\ s_2 & 3 & 2 & 0 & 1 & 120 \\ \hline C & -3 & -2 & 0 & 0 & 0 \end{array} $$ Now we will eliminate the entries above and below the pivot element to have zeros in that column: $$ \begin{array}{c|cccc|c} & x & y & s_1 & s_2 & \text{RHS} \\ \hline x & 1 & \frac{3}{2} & \frac{1}{2} & 0 & 45 \\ s_2 & 0 & -\frac{1}{2} & -\frac{3}{2} & 1 & 15 \\ \hline C & 0 & \frac{1}{2} & \frac{3}{2} & 0 & 135 \end{array} $$ The simplex tableau's last row doesn't have any negative entries, which means we have reached the optimal solution.

We can now read the optimal solution from the simplex tableau: Optimal solution: \(x=45, y=0, s_1=0, s_2=15, C=135\) The optimal solution for the primal problem is to set \(x=45\) and \(y=0\), which gives the minimum cost of 135.