Solve the following linear goal programming problem using the modified simplex algorithm:

Question

Minimize { P1d
+
1
, P2d
−
2
}
subject to
x1 + 2x2 ≤ 10
x1 + d
−
1 − d
+
1 = 5
x2 + d
−
2 − d
+
2 = 10
xi
, d−
i
, d+
j ≥ 0 for i = 1, 2

Answer 1

To solve the linear goal programming problem using the modified simplex algorithm, we can follow these steps:

1. Set up the initial tableau representing the problem:

- Original variables are x1, x2, d.
- Auxiliary variables are d-1, d-2, d+1, d+2.
- Objective row: -P1d+1 + P2d-2.
- Constraint rows: x1 + 2x2 + s1 = 10, x1 + d-1 - d+1 + e1 = 5, x2 + d-2 - d+2 + e2 = 10.
- The initial tableau will have the following structure:

Base x1 x2 d d-1 d-2 d+1 d+2 s1 e1 e2 RHS
P -P1 0 P2 0 0 0
s1 1 2 0 10
e1 1 -1 1 -1 1 5
e2 1 -2 -1 1 10

2. Apply the modified simplex algorithm to find an optimal solution:

- Select the most negative P coefficient (-P1) as the pivot column.
- Select the smallest RHS/s1 ratio (10/1) as the pivot row.
- Perform row operations to make the pivot element 1 and other elements in the pivot column 0.
- Update the tableau accordingly.

Base x1 x2 d d-1 d-2 d+1 d+2 s1 e1 e2 RHS
P 5/2 0 0 3/2 -3/2 1/2 -1/2 -P1/2 0 0 -5/2
s1 -1 0 0 1/2 -1/2 1/2 5/2 0 0 5
e1 -3/2 1 1 -1/2 1/2 1/2 -5/2 1 0 5/2
e2 -2 0 1 -1 3 0 1 5

- Select the most negative -P1 coefficient as the pivot column.
- Select the smallest 5/2 ratio as the pivot row.
- Perform row operations to make the pivot element 1 and other elements in the pivot column 0.
- Update the tableau accordingly.

Base x1 x2 d d-1 d-2 d+1 d+2 s1 e1 e2 RHS
P 0 0 0 2 -2 1 -1 -P1 0 0 0
x1 1/2 0 0 1/4 -1/4 1/4 -1/4 0 -1/4 0 5/4
e1 1 0 1 0 1/2 -1/2 1/2 -2 1/2 0 3
e2 -1/2 1 0 0 3/2 -1/2 3/2 0 -1/2 1 15/2

- All the P coefficients are non-negative, indicating an optimal solution.
- Read the optimal solution from the tableau: x1 = 5/2, x2 = 0, d = 5/2, d-1 = 0, d-2 = 0, d+1 = 0, d+2 = 0, s1 = 0, e1 = 3, e2 = 15/2.
- Therefore, the optimal values for P1d+1 and P2d-2 are P1d+1 = 5/2 and P2d-2 = 0.

Therefore, the linear goal programming problem is solved with the optimal values P1d+1 = 5/2 and P2d-2 = 0.