**Transcription for Educational Use: Linear Programming Duality**---**Objective: Write the dual maximization problem, and then solve both the primal and dual problems using the simplex method.**### Primal Problem**Minimize**: \[ g = 4y_1 + 19y_2 \]**Subject to the constraints**: \[ 2y_1 + y_2 \geq 15 \] \[ y_1 + 3y_2 \geq 15 \] \[ y_1 + 4y_2 \geq 16 \]### Solution Variables- Primal \( g \) = ________- Primal \( y_1 \) = ________- Primal \( y_2 \) = ________### Dual ProblemFor the dual problem, use \( x_1, x_2, \) and \( x_3 \) as the variables and \( f \) as the function.- Dual \( f \) = ________- Dual \( x_1 \) = ________- Dual \( x_2 \) = ________- Dual \( x_3 \) = ________---**Notes for Students:**- The primal problem involves minimizing the function \( g \) subject to given inequalities.- In linear programming, every minimization problem has a corresponding dual maximization problem.- To solve these, apply the simplex method, a popular algorithm for linear programming.- Ensure variable constraints are met while solving both primal and dual problems.

Name: **Transcription for Educational Use: Linear Programming Duality**---*
Uploaded: 2024-03-20T07:07:26.000Z
Channel: Bartleby
Description: **Transcription for Educational Use: Linear Programming Duality**---**Objective: Write the dual maximization problem, and then solve both the primal and dual problems using the simplex method.**### Primal Problem**Minimize**: \[ g = 4y_1 + 19y_2 \]

Converting the given problem in standard form, using surplus and artificial variable. Max g = 4y1+19y2+0s1+0s2+0s3-MA1-MA2-MA3 subject to, 2y1+y2-s1+A1=15 y1+3y2- s2+A2=15 y1+4y2-s3+A3=16 and non-negative restriction, y1,y2,s1,s2,s3 , A1 ,A2 ,A3 ≥0 Using Big-M simplex method, 1 Cj 4 19 0 0 0 -M -M -M Minimum Ratio Basis CB XB y1 y2 s1 s2 s3 A1 A2 A3 XByi A1 -M 15 2 1 -1 0 0 1 0 0 15 A2 -M 15 1 3 0 -1 0 0 1 0 5 A3 -M 16 1 4 0 0 -1 0 0 1 4 zj -4M -8M M M M -M -M -M zj-Cj -4M-4 -8M-19 M M M 0 0 0 Here, -8M-19 is most negative, so corresponding column is key column. Minimum ratio is 4, so corresponding row is key row. hence, key element is, 4, so the leaving variable is A3 and entering variable is y2 Now, we will make 4 as 1 and all other elements in that column as zero using row transformation. R3→R34Then.R1→R1-R3 and R2→R2-3R3 2 Cj 4 19 0 0 0 -M -M Minimum Ratio Basis CB XB y1 y2 s1 s2 s3 A1 A2 XByi A1 -M 11 1.75 0 -1 0 0.25 1 0 6.3 A2 -M 3 0.25 0 0 -1 0.75 0 1 12 y2 19 4 0.25 1 0 0 -0.25 0 0 16 zj -2M+4.75 19 M M -M-4.75 -M -M zj-Cj -2M+0.75 0 M M -M-4.75 0 0 Here, 2M+0.75 is most negative, so corresponding column is key column. Minimum ratio is 6.3, so corresponding row is key row. hence, key element is, 1.75, so the leaving variable is A1 and entering variable is y1 Now, we will make 1.75 as 1 and all other elements in that column as zero using row transformation. Solving similarly using big-M simplex method, we get the given primal problem is unbounded.Max g = 4y1+19y2 subject to, -2y1-y2≤-15 -y1-3y2≤-15 -y1-4y2≤-16 and non-negative restriction, y1,y2 ≥0 Dual of this problem is, Min f=-15x1-15x2-16x3 subject to, -2x1-x2-x3≥4 -x1-3x2-4x3≥19 and non-negative restriction, x1,x2,x3 ≥0 Convert it into canonical form, Max f=15x1+15x2+16x3+0s1+0s2 subject to, 2x1+x2+x3+s1=-4 x1+3x2+4x3+s2=-19 and non-negative restriction, x1,x2,x3,s1,s2 ≥0 1 Cj 15 15 16 0 0 Minimum Ratio Basis CB XB x1 x2 x3 s1 s2 XBxi s1 0 -4 2 1 1 1 0 -4 s2 0 -19 1 3 4 0 1 -194 zj 0 0 0 0 0 zj-Cj -15 -15 -16 0 0 Here, -16 is most negative, so corresponding column is key column. Minimum ratio is all negative, so we get infeasible solution