Question

6.10. consider the following problem.
maximize $z = x_1 + 4x_2$
subject to
$2x_1 + x_2 \leq 24$
$-x_1 + x_2 \leq 4$
$3x_1 + 5x_2 \leq 60$
$x_1, x_2 \geq 0$
(a) solve this problem graphically.
(b) write the dual problem in standard equality form. using complementary s
ness and the optimal primal solution found in part (a), find an optimal solutio
the dual problem

Explanation:

Part (a): Solve Graphically

Step 1: Identify Constraints

We have three inequalities:

• \( 2x_1 + x_2 \leq 24 \) (Constraint 1)
• \( -x_1 + x_2 \leq 4 \) (Constraint 2)
• \( 3x_1 + 5x_2 \leq 60 \) (Constraint 3)
• \( x_1, x_2 \geq 0 \) (Non-negativity)

Step 2: Find Intercepts for Each Line

• Constraint 1 (\( 2x_1 + x_2 = 24 \)):
• \( x_1 = 0 \): \( x_2 = 24 \) (Point: \( (0, 24) \))
• \( x_2 = 0 \): \( x_1 = 12 \) (Point: \( (12, 0) \))

• Constraint 2 (\( -x_1 + x_2 = 4 \)):
• \( x_1 = 0 \): \( x_2 = 4 \) (Point: \( (0, 4) \))
• \( x_2 = 0 \): \( x_1 = -4 \) (Discard, since \( x_1 \geq 0 \))

• Constraint 3 (\( 3x_1 + 5x_2 = 60 \)):
• \( x_1 = 0 \): \( x_2 = 12 \) (Point: \( (0, 12) \))
• \( x_2 = 0 \): \( x_1 = 20 \) (Point: \( (20, 0) \))

Step 3: Plot Feasible Region

Plot the lines and shade the region where all constraints (including \( x_1, x_2 \geq 0 \)) are satisfied. The feasible region is a polygon bounded by intersection points of the constraints.

Step 4: Find Intersection Points of Constraints

• Intersection of Constraint 1 and 2:

Solve \( 2x_1 + x_2 = 24 \) and \( -x_1 + x_2 = 4 \).
Subtract the second equation from the first: \( 3x_1 = 20 \Rightarrow x_1 = \frac{20}{3} \approx 6.67 \), then \( x_2 = 4 + \frac{20}{3} = \frac{32}{3} \approx 10.67 \).

• Intersection of Constraint 1 and 3:

Solve \( 2x_1 + x_2 = 24 \) (multiply by 5: \( 10x_1 + 5x_2 = 120 \)) and \( 3x_1 + 5x_2 = 60 \).
Subtract: \( 7x_1 = 60 \Rightarrow x_1 = \frac{60}{7} \approx 8.57 \), \( x_2 = 24 - 2(\frac{60}{7}) = \frac{48}{7} \approx 6.86 \).

• Intersection of Constraint 2 and 3:

Solve \( -x_1 + x_2 = 4 \) (so \( x_2 = x_1 + 4 \)) and \( 3x_1 + 5x_2 = 60 \).
Substitute: \( 3x_1 + 5(x_1 + 4) = 60 \Rightarrow 8x_1 + 20 = 60 \Rightarrow 8x_1 = 40 \Rightarrow x_1 = 5 \), \( x_2 = 9 \).

Step 5: Evaluate Objective Function at Vertices

The vertices of the feasible region are:

• \( (0, 0) \): \( z = 0 + 0 = 0 \)
• \( (0, 4) \): \( z = 0 + 16 = 16 \)
• \( (5, 9) \): \( z = 5 + 36 = 41 \)
• \( (\frac{60}{7}, \frac{48}{7}) \approx (8.57, 6.86) \): \( z = \frac{60}{7} + 4(\frac{48}{7}) = \frac{60 + 192}{7} = \frac{252}{7} = 36 \)
• \( (12, 0) \): \( z = 12 + 0 = 12 \)

The maximum \( z \) occurs at \( (5, 9) \) with \( z = 41 \).

Part (b): Dual Problem in Standard Form

Step 1: Primal Problem Structure

Primal (maximization) with \( n = 2 \) variables, \( m = 3 \) constraints:
\( \max z = c^T x \), \( Ax \leq b \), \( x \geq 0 \), where:
\( c =

$$\begin{bmatrix} 1 \\ 4 \end{bmatrix}$$

\), \( A =

$$\begin{bmatrix} 2 & 1 \\ -1 & 1 \\ 3 & 5 \end{bmatrix}$$

\), \( b =

$$\begin{bmatrix} 24 \\ 4 \\ 60 \end{bmatrix}$$

\).

Step 2: Dual Problem (Minimization)

Dual variables: \( y_1, y_2, y_3 \geq 0 \) (since primal constraints are \( \leq \)).
Dual objective: \( \min w = b^T y \), \( A^T y \geq c \), \( y \geq 0 \).

Standard equality form (introduce surplus variables \( s_1, s_2 \geq 0 \)):
\( A^T y - s = c \), so:

• \( 2y_1 - y_2 + 3y_3 - s_1 = 1 \)
• \( y_1 + y_2 + 5y_3 - s_2 = 4 \)
• \( y_1, y_2, y_3, s_1, s_2 \geq 0 \)

Objective: \( \min w = 24y_1 + 4y_2 + 60y_3 \).

Using Complementary Slackness

From primal solution \( x = (5, 9) \):

• Primal constraints:
• \( 2(5) + 9 = 19 \leq 24 \) (slack \( s_1' = 24 - 19 = 5 > 0 \))
• \( -5 + 9 = 4 \leq 4 \) (slack \( s_2' = 0 \))
• \( 3(5) + 5(9) = 60 \leq 60 \) (slack \( s_3' = 0 \))

By complementary slackness:

• If primal slack \( s_i' > 0 \), then dual variable \( y_i = 0 \). So \( y_1 = 0 \) (since \( s_1' = 5 > 0 \)).
• For primal variables \( x_j > 0 \), dual surplus \( s_j = 0 \). So \( s_1 = 0 \) ( \( x_1 = 5 > 0 \) ), \( s_2 = 0 \) ( \( x_2 = 9 > 0 \) ).

Substitute \( y_1 = 0 \), \( s_1 = 0 \), \( s_2 = 0 \) into dual equations:

1. \( -y_2 + 3y_3 = 1 \)
2. \( y_2 + 5y_3 = 4 \)

Solve: Add the two equations: \( 8y_3 = 5 \Rightarrow y_3 = \frac{5}{8} \), then \( y_2 = 4 - 5(\frac{5}{8}) = \frac{32 - 25}{8} = \frac{7}{8} \).

Optimal dual solution: \( y = (0, \frac{7}{8}, \frac{5}{8}) \), \( w = 24(0) + 4(\frac{7}{8}) + 60(\frac{5}{8}) = \frac{28 + 300}{8} = \frac{328}{8} = 41 \) (matches primal \( z \), as expected).

Answer:

s:
(a) Optimal primal solution: \( x_1 = 5 \), \( x_2 = 9 \), \( z = 41 \)
(b) Dual in standard form: \( \min w = 24y_1 + 4y_2 + 60y_3 \) s.t. \( 2y_1 - y_2 + 3y_3 - s_1 = 1 \), \( y_1 + y_2 + 5y_3 - s_2 = 4 \), \( y_1, y_2, y_3, s_1, s_2 \geq 0 \). Optimal dual solution: \( y_1 = 0 \), \( y_2 = \frac{7}{8} \), \( y_3 = \frac{5}{8} \), \( w = 41 \)