The current solution optimal extract the solutionafter completing the iterations
2. Find the optimal solution using simplex method.
Min Z=10x1 +5x2
Problem Statement
Minimize: Z = 10x1 + 5x2
Subject to: 2x1 + 5x2 ≥ 150 3x1 + x2 ≥ 120 x1, x2 ≥ 0
- 2x1 + 5x2 − s1 + a1 = 150
- 3x1 + x2 − s2 + a2 = 120
- s1, s2: Surplus variables (to account for the excess over the minimum requirement).
- a1, a2: Artificial variables (introduced to handle the ≥ constraints).
The objective function is to minimize Z = 10x1 + 5x2. To handle minimization, we use the Big-M Method, where we assign a large penalty M to the artificial variables in the objective function:
Z = 10x1 + 5x2 + Ma1 + Ma2
Basis | x1 | x2 | s1 | s2 | a1 | a2 | RHS |
---|---|---|---|---|---|---|---|
a1 | 2 | 5 | -1 | 0 | 1 | 0 | 150 |
a2 | 3 | 1 | 0 | -1 | 0 | 1 | 120 |
Z | -10 | -5 | 0 | 0 | -M | -M | 0 |
Iteration 1:
- For a1: 150/2 = 75
- For a2: 120/3 = 40
- The smallest ratio is 40, so a2 leaves the basis.
Pivot on the element in row a2 and column x1:
- Divide row a2 by 3 to make the pivot element 1: $\text{New~row~}x_{1}:\left\lbrack 1,\frac{1}{3},0, - \frac{1}{3},0,\frac{1}{3},40 \right\rbrack$
- Update the other rows to eliminate x1:
- For row a1: New row a1 = Old row a1 − 2 × New row x1 $\text{New~row~}a_{1}:\left\lbrack 0,\frac{13}{3}, - 1,\frac{2}{3},1, - \frac{2}{3},70 \right\rbrack$
- For row Z: New row Z = Old row Z + 10 × New row x1 $\text{New~row~}Z:\left\lbrack 0, - \frac{5}{3},0, - \frac{10}{3}, - M,M - \frac{10}{3},400 \right\rbrack$
Updated Table:
Basis | x1 | x2 | s1 | s2 | a1 | a2 | RHS |
---|---|---|---|---|---|---|---|
a1 | 0 | $$\frac{13}{3}$$ | -1 | $$\frac{2}{3}$$ | 1 | $$- \frac{2}{3}$$ | 70 |
x1 | 1 | $$\frac{1}{3}$$ | 0 | $$- \frac{1}{3}$$ | 0 | $$\frac{1}{3}$$ | 40 |
Z | 0 | $$- \frac{5}{3}$$ | 0 | $$- \frac{10}{3}$$ | -M | $$M - \frac{10}{3}$$ | 400 |
Iteration 2:
Identify the entering variable: The most negative coefficient in the Z-row is $- \frac{5}{3}$ (for x2), so x2 enters the basis.
- For a1: $70/\frac{13}{3} = \frac{210}{13} \approx 16.15$
- For x1: $40/\frac{1}{3} = 120$
- The smallest ratio is $\frac{210}{13}$, so a1 leaves the basis.
- Divide row a1 by $\frac{13}{3}$ to make the pivot element 1: $\text{New~row~}x_{2}:\left\lbrack 0,1, - \frac{3}{13},\frac{2}{13},\frac{3}{13}, - \frac{2}{13},\frac{210}{13} \right\rbrack$
- Update the other rows to eliminate x2:
- For row x1: $\text{New~row~}x_{1} = \text{Old~row~}x_{1} - \frac{1}{3} \times \text{New~row~}x_{2}$ $\text{New~row~}x_{1}:\left\lbrack 1,0,\frac{1}{13}, - \frac{5}{13}, - \frac{1}{13},\frac{5}{13},\frac{350}{13} \right\rbrack$
- For row Z: $\text{New~row~}Z = \text{Old~row~}Z + \frac{5}{3} \times \text{New~row~}x_{2}$ $\text{New~row~}Z:\left\lbrack 0,0, - \frac{5}{13}, - \frac{20}{13}, - M + \frac{5}{13},M - \frac{20}{13},\frac{2650}{13} \right\rbrack$
Updated Table:
Basis | x1 | x2 | s1 | s2 | a1 | a2 | RHS |
---|---|---|---|---|---|---|---|
x2 | 0 | 1 | $$- \frac{3}{13}$$ | $$\frac{2}{13}$$ | $$\frac{3}{13}$$ | $$- \frac{2}{13}$$ | $$\frac{210}{13}$$ |
x1 | 1 | 0 | $$\frac{1}{13}$$ | $$- \frac{5}{13}$$ | $$- \frac{1}{13}$$ | $$\frac{5}{13}$$ | $$\frac{450}{13}$$ |
Z | 0 | 0 | $$- \frac{5}{13}$$ | $$- \frac{20}{13}$$ | $$- M + \frac{5}{13}$$ | $$M - \frac{20}{13}$$ | $$\frac{2650}{13}$$ |
Step 5: Extract the Solution
After completing the iterations, we obtain:
- $x_{1} = \frac{550}{13}34.61$
- $x_{2} = \frac{210}{13} \approx 16.15$
- $Z = \frac{2650}{13} \approx 203.85$
- x1 = 34.61
- x2 = 16.15
- Minimum cost Z = 426.85