JAWAHARLAL NEHRU TECHNOLOGICAL UNIVERSITY HYDERABAD B.Tech III OPERATIONS RESEARCH Previous Question Paper (September - 2021 - R18)

To solve the linear programming problem (LPP) graphically, we first identify the feasible region defined by the constraints:

1. Constraint 1: 2x₁ + x₂ ≥ 3. The boundary line is 2x₁ + x₂ = 3. Intercepts are (1.5, 0) and (0, 3). The region lies above this line.
2. Constraint 2: x₁ - x₂ ≥ 0, or x₁ ≥ x₂. The boundary line is x₁ = x₂, passing through (0, 0) and (1, 1). The region lies to the right/below this line.
3. Non-negativity constraints: x₁, x₂ ≥ 0 restrict the solution to the first quadrant.

The intersection of the boundary lines 2x₁ + x₂ = 3 and x₁ = x₂ is found by substitution: 2x₁ + x₁ = 3, which gives 3x₁ = 3, so x₁ = 1 and x₂ = 1. The feasible region is an unbounded region in the first quadrant with corner points (1.5, 0) and (1, 1), extending towards infinity along the line x₁ = x₂.

We evaluate the objective function z = 6x₁ + x₂ at the corner points:

• At (1.5, 0): z = 6(1.5) + 0 = 9
• At (1, 1): z = 6(1) + 1 = 7

Since the feasible region is unbounded and the coefficients of the objective function are positive, as x₁ and x₂ increase along the constraint x₁ = x₂ (where x₁ = x₂ = k as k → ∞), the value of z = 6k + k = 7k also approaches infinity. Therefore, the LPP has an unbounded solution.

To solve the LPP using the Big M method, we first convert the constraints into standard form by introducing slack, surplus, and artificial variables. The objective function becomes: Minimize z = 5x₁ + 3x₂ + 0s₁ + 0s₂ + Ms₃ + Ms₄, where s₁ is a slack variable, s₂ is a surplus variable, and s₃, s₄ are artificial variables.

Standard form constraints:

We express the objective function in terms of non-basic variables by substituting the artificial variables from the constraint equations: s₃ = 10 - 2x₁ - 2x₂ and s₄ = 10 - 5x₁ - 2x₂ + s₂. The modified objective function is: z = 5x₁ + 3x₂ + M(10 - 2x₁ - 2x₂) + M(10 - 5x₁ - 2x₂ + s₂) = (5 - 7M)x₁ + (3 - 4M)x₂ + Ms₂ + 20M.

By performing simplex iterations:

1. Initial Tableau: The entering variable is x₁ (most negative coefficient of M). The leaving variable is s₄.
2. After pivoting, the artificial variables are removed from the basis.
3. Subsequent iterations are performed until all coefficients in the z-row are non-negative.

Following the simplex algorithm steps, the optimal solution is obtained at x₁ = 1, x₂ = 2.5. Substituting these values into the objective function: z = 5(1) + 3(2.5) = 5 + 7.5 = 12.5.