Solved 1. (5 points) Set up the linear programming problem | Chegg.com - Free Printable

Let's solve each part of your problem step by step.

---

Problem 1: Set up the Linear Programming Problem

Word Problem Summary:
- Cabinet X:
- Cost: $10 per unit
- Floor space: 6 sq ft
- Storage: 8 cubic ft
- Cabinet Y:
- Cost: $20 per unit
- Floor space: 8 sq ft
- Storage: 12 cubic ft
- Budget: $140 (maximum)
- Floor space available: 72 sq ft (maximum)
- Goal: Maximize storage volume

---

#### Step 1: Define Variables
Let:
- $ x $ = number of Cabinet X units to buy
- $ y $ = number of Cabinet Y units to buy

---

#### Step 2: Objective Function
We want to maximize storage volume.

- Each Cabinet X holds 8 cubic feet → contributes $ 8x $
- Each Cabinet Y holds 12 cubic feet → contributes $ 12y $

So, the objective function is:
$$
\text{Maximize } Z = 8x + 12y
$$

---

#### Step 3: Constraints

1. Budget constraint: Total cost ≤ $140
- Cabinet X costs $10, Cabinet Y costs $20
$$
10x + 20y \leq 140
$$

2. Floor space constraint: Total floor space ≤ 72 sq ft
- Cabinet X uses 6 sq ft, Cabinet Y uses 8 sq ft
$$
6x + 8y \leq 72
$$

3. Non-negativity constraints:
$$
x \geq 0, \quad y \geq 0
$$

---

#### Final LP Formulation (Do NOT solve):

$$
\text{Maximize } Z = 8x + 12y
$$
Subject to:
$$
\begin{align*}
10x + 20y &\leq 140 \\
6x + 8y &\leq 72 \\
x &\geq 0 \\
y &\geq 0
\end{align*}
$$

✔ This is the complete setup for the linear programming problem.

---

Problem 2: Solve Using the Simplex Method

We are to maximize:
$$
f = 7x + 5y
$$
Subject to:
$$
\begin{cases}
2x + y \leq 100 \\
4x + 3y \leq 240 \\
x \geq 0, \; y \geq 0
\end{cases}
$$

---

#### Step 1: Convert to Standard Form

Introduce slack variables $ s_1 $ and $ s_2 $ to convert inequalities to equations:

$$
\begin{align*}
2x + y + s_1 &= 100 \\
4x + 3y + s_2 &= 240 \\
x, y, s_1, s_2 &\geq 0
\end{align*}
$$

Objective function becomes:
$$
\text{Maximize } f = 7x + 5y + 0s_1 + 0s_2
$$

---

#### Step 2: Initial Simplex Tableau

| Basic | $ x $ | $ y $ | $ s_1 $ | $ s_2 $ | RHS |
|-------|--------|--------|---------|---------|-----|
| $ s_1 $ | 2 | 1 | 1 | 0 | 100 |
| $ s_2 $ | 4 | 3 | 0 | 1 | 240 |
| $ f $ | -7 | -5 | 0 | 0 | 0 |

> Note: The bottom row is $ f = 7x + 5y $, so we write coefficients as $ -7 $ and $ -5 $ in the tableau.

---

#### Step 3: Identify Entering Variable

Look at the bottom row (objective row). Most negative coefficient → $ x $ (-7), so $ x $ enters.

---

#### Step 4: Ratio Test (Minimum Ratio Rule)

Compute $ \frac{\text{RHS}}{\text{pivot column}} $ for positive entries only:

- Row 1: $ 100 / 2 = 50 $
- Row 2: $ 240 / 4 = 60 $

Minimum ratio = 50 → Row 1 is pivot row, so $ s_1 $ leaves.

Pivot element: 2 (at $ x $-column, $ s_1 $-row)

---

#### Step 5: Pivot Operation

Make pivot element 1, then eliminate $ x $ from other rows.

Row 1 (new): Divide row 1 by 2:
$$
x + 0.5y + 0.5s_1 + 0s_2 = 50
$$

Now update other rows.

Row 2 (new): $ R2_{\text{new}} = R2 - 4 \times R1_{\text{new}} $

Original R2: $ 4x + 3y + 0s_1 + s_2 = 240 $

Subtract $ 4 \times (x + 0.5y + 0.5s_1) = 4x + 2y + 2s_1 $

So:
$$
(4x - 4x) + (3y - 2y) + (0 - 2)s_1 + s_2 = 240 - 200 \Rightarrow y - 2s_1 + s_2 = 40
$$

Objective row (f): $ f = 7x + 5y $ → replace with $ f - 7 \times R1_{\text{new}} $

Original f: $ -7x -5y + 0s_1 + 0s_2 = 0 $

Add $ 7 \times (x + 0.5y + 0.5s_1) = 7x + 3.5y + 3.5s_1 $

So:
$$
(-7x + 7x) + (-5y - 3.5y) + (0 + 3.5)s_1 + 0s_2 = 0 + 350
\Rightarrow -1.5y + 3.5s_1 + 0s_2 = 350
$$

Wait — actually, we do:

New $ f $ row = old $ f $ row + 7 × new R1

Because we are eliminating $ x $ from the objective.

Old $ f $: $ -7x -5y + 0s_1 + 0s_2 = 0 $

Add $ 7 \times (x + 0.5y + 0.5s_1) = 7x + 3.5y + 3.5s_1 $

Result:
$$
(-7x + 7x) + (-5y + 3.5y) + (0 + 3.5)s_1 + 0s_2 = 0 + 350
\Rightarrow 0x -1.5y + 3.5s_1 + 0s_2 = 350
$$

So new $ f $ row: $ -1.5y + 3.5s_1 = 350 $ → but this is not standard.

Actually, we write it as:
$$
f = 350 + 1.5y - 3.5s_1
$$

But in tableau form, we keep the coefficients.

So updated tableau:

| Basic | $ x $ | $ y $ | $ s_1 $ | $ s_2 $ | RHS |
|-------|--------|--------|---------|---------|-----|
| $ x $ | 1 | 0.5 | 0.5 | 0 | 50 |
| $ s_2 $ | 0 | 1 | -2 | 1 | 40 |
| $ f $ | 0 | -1.5 | 3.5 | 0 | 350 |

> Wait — the $ f $ row should be: $ f - 7x -5y = 0 $, and we've substituted $ x $, so now we express $ f $ in terms of non-basic variables.

But in simplex, we write the objective row as:
$$
f + 0x + (-1.5)y + 3.5s_1 + 0s_2 = 350
$$
So the coefficients in the $ f $ row are: $ 0, -1.5, 3.5, 0 $, and RHS = 350

So final tableau after first pivot:

| Basic | $ x $ | $ y $ | $ s_1 $ | $ s_2 $ | RHS |
|-------|--------|--------|---------|---------|-----|
| $ x $ | 1 | 0.5 | 0.5 | 0 | 50 |
| $ s_2 $ | 0 | 1 | -2 | 1 | 40 |
| $ f $ | 0 | -1.5 | 3.5 | 0 | 350 |

---

#### Step 6: Check for Optimality

In the $ f $ row, we have a negative coefficient for $ y $: $ -1.5 $. So not optimal.

→ $ y $ enters the basis.

Now perform ratio test:

- Row 1: $ 50 / 0.5 = 100 $
- Row 2: $ 40 / 1 = 40 $

Minimum ratio = 40 → Row 2 is pivot row → $ s_2 $ leaves.

Pivot element: 1 (in $ y $-column, $ s_2 $-row)

---

#### Step 7: Pivot on $ y $-column, $ s_2 $-row

Row 2 (new): Already has 1 in $ y $-column → no change:
$$
0x + y - 2s_1 + s_2 = 40
$$

Update Row 1: $ R1_{\text{new}} = R1 - 0.5 \times R2 $

Original R1: $ x + 0.5y + 0.5s_1 = 50 $

Subtract $ 0.5 \times (y - 2s_1 + s_2) = 0.5y - s_1 + 0.5s_2 $

So:
$$
x + (0.5y - 0.5y) + (0.5s_1 + s_1) - 0.5s_2 = 50 - 20
\Rightarrow x + 1.5s_1 - 0.5s_2 = 30
$$

Update $ f $ row: $ f_{\text{new}} = f + 1.5 \times R2 $

Current $ f $: $ f + 0x -1.5y + 3.5s_1 + 0s_2 = 350 $

Add $ 1.5 \times (y - 2s_1 + s_2) = 1.5y - 3s_1 + 1.5s_2 $

So:
$$
f + (-1.5y + 1.5y) + (3.5s_1 - 3s_1) + (0 + 1.5)s_2 = 350 + 60
\Rightarrow f + 0.5s_1 + 1.5s_2 = 410
$$

So final tableau:

| Basic | $ x $ | $ y $ | $ s_1 $ | $ s_2 $ | RHS |
|-------|--------|--------|---------|---------|-----|
| $ x $ | 1 | 0 | 1.5 | -0.5 | 30 |
| $ y $ | 0 | 1 | -2 | 1 | 40 |
| $ f $ | 0 | 0 | 0.5 | 1.5 | 410 |

---

#### Step 8: Check Optimality

All coefficients in $ f $ row are non-negative ($ 0.5 $, $ 1.5 $), so optimal solution reached.

---

#### Final Solution:

- $ x = 30 $
- $ y = 40 $
- Maximum $ f = 7x + 5y = 7(30) + 5(40) = 210 + 200 = 410 $

---

✔ Final Answer for Problem 2:

The maximum value of $ f = 7x + 5y $ is 410, achieved when:
- $ x = 30 $
- $ y = 40 $

---

✔ Summary:

Problem 1 (Setup):
$$
\text{Maximize } Z = 8x + 12y
$$
Subject to:
$$
\begin{align*}
10x + 20y &\leq 140 \\
6x + 8y &\leq 72 \\
x, y &\geq 0
\end{align*}
$$

Problem 2 (Solved via Simplex):
Maximum $ f = 410 $ at $ x = 30 $, $ y = 40 $

Let me know if you'd like a graphical interpretation or verification!