1. In the graphical method of Linear Programming, the feasible region is:
A. The area covering only one constraint
B. The intersection of axes with constraints
C. The common region satisfying all constraints including non-negativity
D. The region outside all constraints
In the graphical approach, all constraints including non-negativity are plotted, and the feasible region is the common overlapping area where all constraints are satisfied.
2. In a Linear Programming Problem, the optimal solution always lies:
A. At a corner point (vertex) of the feasible region
B. At the mid-point of feasible region
C. Anywhere within the feasible region
D. Outside the feasible region if objective is maximum
Linear Programming problems satisfy the property of convexity; hence the optimal solution is always at one of the corner points of the feasible region.
3. If a Linear Programming Problem has multiple optimal solutions, it occurs when:
A. The feasible region is unbounded
B. No feasible solution exists
C. Two constraints are parallel
D. The objective function is parallel to a constraint line within feasible region
Multiple optimal solutions exist when the objective function line is parallel to one of the constraint boundaries in the feasible region, giving same objective value at more than one vertex.
4. A firm produces two products P and Q with constraints: 2P + Q ≤ 100, P + Q ≤ 80, P ≥ 0, Q ≥ 0. Which method can be used to find the optimal product mix?
A. Simplex method only
B. Graphical method, since there are two variables
C. Only trial-and-error method
D. Transportation method
When there are only two decision variables, the graphical method is applicable. For more than two, Simplex is used.
5. In graphical solution of a maximization problem, if the feasible region is unbounded, then:
A. Solution is always infeasible
B. Solution cannot exist
C. Maximum may or may not exist, needs to be checked
D. Minimum always exists
For unbounded feasible regions, the maximum solution may not exist since the objective function may increase infinitely. Verification is required.
6. The non-negativity constraints in Linear Programming ensure that:
A. The feasible region is a circle
B. The feasible region includes negative values
C. The solution can be anywhere on the plane
D. The solution lies in the first quadrant of the graph
Non-negativity constraints (X ≥ 0, Y ≥ 0) restrict the feasible region to the first quadrant of the coordinate plane.
7. The Simplex method is primarily used for solving:
A. Linear Programming problems with two variables only
B. Linear Programming problems with more than two variables
C. Non-linear optimization problems
D. Only transportation problems
The graphical method works only for two-variable problems. For problems with two or more variables, the Simplex method is the most widely used solution technique.
8. In the Simplex method, the solution proceeds by moving from:
A. Midpoint to midpoint of feasible region
B. Constraint line to constraint line
C. One feasible region to another
D. One corner point (basic feasible solution) to another
The Simplex method is an iterative procedure which starts from an initial basic feasible solution (corner point) and moves to adjacent corner points until the optimal solution is reached.
9. Which of the following is added to convert an inequality constraint (≤ type) into an equation in the Simplex method?
A. Surplus variable
B. Artificial variable
C. Slack variable
D. Decision variable
A slack variable is added to ≤ constraints to convert them into equalities. Surplus and artificial variables are used in ≥ and = constraints respectively.
10. In the Simplex tableau, the entering variable is chosen based on:
A. The most negative value in the objective function row (for maximization)
B. The most positive value in the RHS
C. The smallest ratio of RHS to pivot element
D. The variable with the highest coefficient in constraints
For maximization problems, the entering variable is the one with the most negative coefficient in the objective function row (Cj - Zj row).
11. In the Simplex method, the leaving variable is determined by:
A. Largest ratio test
B. Minimum ratio test (RHS ÷ pivot column)
C. Smallest coefficient in objective row
D. Constraint with the maximum RHS
The leaving variable is determined using the minimum ratio test (RHS divided by pivot column values), which ensures feasibility of the new solution.
12. Which of the following indicates that an optimal solution has been reached in the Simplex method?
A. At least one artificial variable is present
B. All RHS values are negative
C. The feasible region is unbounded
D. All coefficients in the objective function row are non-negative (for maximization)
In the Simplex tableau, when all the values in the objective row (Cj - Zj) are non-negative for a maximization problem, the optimal solution has been achieved.
13. Maximize Z = 3X + 5Y, subject to constraints: X + Y ≤ 4, X ≤ 2, Y ≤ 3, X, Y ≥ 0. What is the optimal solution?
A. X = 0, Y = 3, Z = 15
B. X = 2, Y = 0, Z = 6
C. X = 1, Y = 3, Z = 18
D. X = 2, Y = 2, Z = 16
Checking corner points of feasible region:
(0,0) → Z=0; (2,0) → Z=6; (0,3) → Z=15; (1,3) → Z=18; (2,2) not feasible (since X+Y ≤ 4).
Hence optimal solution is X=1, Y=3 with Z=18.
14. In the first Simplex tableau, the basic variables are slack variables only and Z = 0. After first iteration, if the entering variable is Y and leaving variable is S1, what does this indicate?
A. Y will remain non-basic in next step
B. Y enters the basis, S1 leaves, and solution moves to adjacent vertex
C. Solution is optimal
D. Problem has multiple solutions
In Simplex, one non-basic variable (entering) replaces a basic variable (leaving) based on pivot element. This represents movement from one feasible corner to another with improved objective value.
15. Consider a Simplex tableau where the objective row (Cj - Zj) values are: X = -2, Y = -3, Z = 0. Which variable will enter the basis next?
A. None, solution is optimal
B. X, since -2 is smallest
C. Either X or Y, both negative
D. Y, since -3 is the most negative
For maximization, the most negative Cj - Zj determines the entering variable. Since Y = -3 is most negative, Y enters the basis.
16. A company wants to maximize Z = 2X + Y, subject to constraints: X + Y ≤ 4, X ≤ 3, Y ≤ 2, X,Y ≥ 0. Using Simplex method, what is the optimal Z?
A. Z = 8 at (X=3, Y=1)
B. Z = 7 at (X=2, Y=2)
C. Z = 6 at (X=0, Y=2)
D. Z = 5 at (X=1, Y=2)
Feasible corner points: (0,0)→0; (0,2)→2; (3,0)→6; (3,1)→8; (2,2)→6. Maximum is Z=8 at (3,1).
17. In a Simplex problem, after iterations, all Cj - Zj are non-negative, but one RHS value is negative. This indicates:
A. Solution is optimal
B. Multiple solutions exist
C. Current solution is infeasible (need Two-Phase or Big-M)
D. Problem is unbounded
If RHS is negative, it violates feasibility. This requires use of Artificial variables (Two-Phase or Big-M method) to restore feasibility before optimization.
18. In a Simplex tableau, the ratios for minimum ratio test are: Row1=10, Row2=8, Row3=12. Which variable will leave the basis?
A. Row1 variable
B. Row2 variable
C. Row3 variable
D. Any row since all ratios are positive
The leaving variable is chosen using the minimum ratio test. Since Row2 has the smallest ratio (8), its basic variable leaves the basis.
19. Caselet: A maximization problem — Maximize Z = 3x₁ + 2x₂ subject to:
The initial Simplex tableau has slack variables s₁, s₂, s₃ as the basic variables. Which variable will enter the basis in the first iteration (using the usual Simplex entering rule based on highest objective coefficient)?
A. x₁
B. s₂
C. x₂
D. s₁
Entering variable is chosen by the largest objective coefficient (for maximization) among non-basic variables. Here coefficients are 3 (x₁) and 2 (x₂) — x₁ has the highest, so x₁ enters.
20. Using the tableau above, the minimum ratio test for x₁ gives ratios: Row1 = 4/1 = 4, Row2 = 5/2 = 2.5, Row3 = 7/1 = 7. Which row contains the pivot element (i.e., which basic variable leaves the basis)?
A. Row3 (s₃ leaves)
B. Row2 (s₂ leaves)
C. Row1 (s₁ leaves)
D. No leaving variable — problem is unbounded
The minimum positive ratio is 2.5 (Row2), so the variable in Row2 (s₂) leaves the basis and the pivot element is in Row2, column x₁.
21. After performing the pivot on Row2 (make pivot = 1 by dividing Row2 by 2 and eliminate x₁ from other rows), the new basic solution gives x₁ = 2.5, s₁ = 1.5, s₃ = 4.5. What is the value of Z after this first iteration?
A. Z = 6.0
B. Z = 4.5
C. Z = 3.0
D. Z = 7.5
Objective value Z = 3·x₁ + 2·x₂. After first pivot x₁ = 2.5 and x₂ = 0 (non-basic), so Z = 3×2.5 = 7.5.
22. Continuing from the tableau after first iteration, compute Cj − Zj (reduced cost) for x₂. Using the updated basis (x₁, s₁, s₃) with C_B = {3,0,0}, the contribution to Zj from x₂ is 3×0.5 = 1.5, so Cj − Zj for x₂ = 2 − 1.5 = 0.5. Based on this, which variable will enter the basis next?
A. s₁
B. s₂
C. x₂
D. x₁ (re-enter)
Since Cj − Zj for x₂ is positive (0.5), increasing x₂ will improve the objective — therefore x₂ becomes the entering variable in the next iteration.
23. When x₂ is chosen to enter next, compute the minimum ratio test using current row values in x₂ column: Row1 coefficient 0.5 → ratio 1.5/0.5 = 3; Row2 (x₁ row) coefficient 0.5 → ratio 2.5/0.5 = 5; Row3 coefficient 2.5 → ratio 4.5/2.5 = 1.8. Which basic variable will leave the basis in the next pivot?
A. s₁
B. s₃
C. x₁
D. s₂
The minimum ratio is 1.8 (Row3), so the variable in Row3 (s₃) will leave the basis when x₂ enters.
