This guide or article contains 100 Multiple Choice Questions (MCQs) on Linear Programming (LPP) with detailed answers and explanations. Perfect for students preparing for exams .
๐ Table of Contents
MCQs 1–20 on Linear Programming (LPP)
Q1. Linear Programming Problem (LPP) deals with:
A) Linear objective & constraints
B) Non-linear equations
C) Random variables
D) None of these
Answer: A — LPP is based on linear objective function and linear constraints only.
Q2. The objective of an LPP can be:
A) Only maximization
B) Only minimization
C) Either maximization or minimization
D) None
Answer: C — Objective function in LPP can be both maximization (profit) or minimization (cost).
Q3. The feasible region of LPP is always:
A) A polygon
B) Convex set
C) Circle
D) Non-convex set
Answer: B — Feasible region is always convex, formed by intersection of linear constraints.
Q4. Optimal solution of LPP always lies:
A) At the center
B) At a corner (extreme) point
C) Anywhere in feasible region
D) Outside feasible region
Answer: B — By fundamental theorem of LPP, the optimum is always at an extreme (corner) point.
Q5. Graphical method of solving LPP can be applied when number of variables are:
A) 1
B) 2
C) 3
D) More than 3
Answer: B — Graphical method is limited to two-variable LPP only.
Q6. Which method is used to solve LPP with more than two variables?
A) Graphical
B) Trial and error
C) Simplex method
D) None
Answer: C — The simplex method is used for LPP with ≥3 variables.
Q7. Slack variables are introduced in:
A) ≤ constraints
B) ≥ constraints
C) Equalities
D) None
Answer: A — Slack variables are added to convert ≤ inequalities into equalities.
Q8. Surplus variables are introduced in:
A) ≤ constraints
B) ≥ constraints
C) Equalities
D) None
Answer: B — Surplus variables are subtracted in ≥ constraints to convert them into equalities.
Q9. Artificial variables are used in:
A) Simplex method (for ≥ or = constraints)
B) Only Graphical method
C) Transportation problem
D) None
Answer: A — Artificial variables are temporary, used in Simplex method for ≥ or = constraints.
Q10. Standard form of LPP includes:
A) Maximization objective only
B) Minimization objective only
C) Non-negativity constraints (x ≥ 0)
D) Both A and C
Answer: D — Standard form assumes maximization and non-negativity constraints.
Q11. Infeasible solution means:
A) At least one constraint is violated
B) Optimal solution is not unique
C) All variables are negative
D) None
Answer: A — Infeasible solution does not satisfy all constraints.
Q12. Unbounded solution occurs when:
A) Feasible region is closed
B) Objective function increases indefinitely
C) There is no feasible solution
D) Multiple solutions exist
Answer: B — If feasible region allows indefinite improvement, solution is unbounded.
Q13. Which of the following always has a feasible solution?
A) Unbounded LPP
B) Infeasible LPP
C) Balanced transportation problem
D) None
Answer: C — Balanced transportation problem always has a feasible solution.
Q14. Dual of a minimization problem is always:
A) Maximization problem
B) Minimization problem
C) Transportation problem
D) None
Answer: A — Duality principle: minimization ↔ maximization.
Q15. Shadow price in LPP indicates:
A) Cost per unit
B) Improvement in objective per unit increase in resource
C) Slack variable value
D) None
Answer: B — Shadow price = Marginal value of resource.
Q16. If feasible region is empty:
A) Solution is infeasible
B) Solution is unbounded
C) Solution is multiple
D) None
Answer: A — Empty feasible region means infeasible LPP.
Q17. Alternate optima exist when:
A) More than one corner point gives same optimum
B) No feasible solution exists
C) Solution is unbounded
D) None
Answer: A — If two or more corner points give same optimal value.
Q18. Transportation problem is a special case of:
A) Assignment problem
B) Linear programming problem
C) Game theory
D) None
Answer: B — Transportation problem is a special type of LPP.
Q19. Assignment problem is a special case of:
A) Transportation problem
B) Simplex method
C) Dynamic programming
D) None
Answer: A — Assignment problem is a special type of transportation problem.
Q20. Simplex method was developed by:
A) Dantzig
B) Kuhn
C) Kantorovich
D) None
Answer: A — George Dantzig developed simplex method (1947).
MCQs 21–40 on Linear Programming (LPP)
Q21. In standard form of LPP, decision variables are assumed to be:
A) Always negative
B) Always non-negative
C) May be negative
D) None
Answer: B — By definition, decision variables are always non-negative (x ≥ 0).
Q22. Which method is more efficient for large-scale LPP?
A) Graphical method
B) Simplex method
C) Enumeration
D) Trial and error
Answer: B — Simplex method is most efficient for large-scale LPP.
Q23. The set of all feasible solutions in an LPP is called:
A) Convex polyhedron
B) Circle
C) Ellipse
D) None
Answer: A — Feasible region is a convex polyhedron (bounded or unbounded).
Q24. Which theorem guarantees the existence of an optimal solution at corner points?
A) Duality theorem
B) Fundamental theorem of LPP
C) Saddle point theorem
D) None
Answer: B — Fundamental theorem states optimum lies at extreme (corner) points.
Q25. If all constraints are equations (equalities), then feasible region is:
A) A single point
B) A line
C) A polygon
D) None
Answer: A or B — Depending on number of constraints, feasible region may reduce to a point or line.
Q26. Which of the following is not an assumption of LPP?
A) Proportionality
B) Additivity
C) Divisibility
D) Non-linearity
Answer: D — Non-linearity is not allowed in LPP.
Q27. Degeneracy in LPP occurs when:
A) Two or more basic feasible solutions are identical
B) Multiple optimal solutions exist
C) Solution is unbounded
D) Solution is infeasible
Answer: A — Degeneracy arises when basic feasible solution has fewer positive variables than required.
Q28. The dual of the dual problem is:
A) Same as primal
B) Opposite of primal
C) Unbounded
D) None
Answer: A — Dual of dual is primal problem itself.
Q29. Which of the following is not true for LPP?
A) Objective function is linear
B) Constraints are linear
C) Decision variables can be fractional
D) Constraints must be quadratic
Answer: D — Constraints must be linear, not quadratic.
Q30. Sensitivity analysis in LPP studies:
A) Effect of changes in coefficients
B) Feasible region shape
C) Graphical solution only
D) None
Answer: A — Sensitivity analysis studies effect of changes in objective/constraints.
Q31. Which method is used when initial basic feasible solution is not obvious?
A) Simplex
B) Big-M method
C) Graphical
D) Dual method
Answer: B — Big-M method introduces artificial variables to start simplex.
Q32. Two-phase method is used to:
A) Minimize objective
B) Solve degeneracy
C) Remove artificial variables systematically
D) None
Answer: C — Two-phase method removes artificial variables in two stages.
Q33. Which condition ensures bounded feasible region?
A) Parallel constraints
B) Constraints enclosing a closed polygon
C) At least one equality constraint
D) None
Answer: B — Closed polygon ensures bounded feasible region.
Q34. The dual variable is also known as:
A) Slack variable
B) Shadow price
C) Artificial variable
D) Surplus variable
Answer: B — Dual variables are interpreted as shadow prices.
Q35. Who is regarded as father of linear programming?
A) Newton
B) Dantzig
C) Kuhn
D) Turing
Answer: B — George Dantzig is called father of linear programming.
Q36. If constraints are inconsistent, then:
A) Unique solution exists
B) Multiple solutions exist
C) No feasible solution exists
D) Unbounded solution
Answer: C — Inconsistent constraints lead to infeasible LPP.
Q37. Iso-cost or Iso-profit lines are used in:
A) Simplex method
B) Graphical method
C) Transportation problem
D) None
Answer: B — Iso-profit lines are used in graphical method to find optimum.
Q38. Which property of LPP ensures divisibility of resources?
A) Continuity
B) Additivity
C) Proportionality
D) None
Answer: A — Continuity assumption allows fractional values of decision variables.
Q39. If objective function coefficients are all zero, then:
A) Any feasible solution is optimal
B) No solution
C) Unbounded
D) Infeasible
Answer: A — If objective coefficients are zero, every feasible solution gives same value.
Q40. Which method is an alternative to simplex for LPP?
A) Interior point method
B) Transportation method
C) Hungarian method
D) None
Answer: A — Interior point method is an alternative to simplex.
MCQs 41–60 on Linear Programming (LPP)
Q41. Standard form of an LPP means:
A) Objective function is maximization, constraints are ≤ type, variables non-negative
B) Objective function is minimization only
C) Constraints are ≥ type only
D) Variables can be negative
Answer: A — In standard form, LPP is written as maximize Z with ≤ constraints and x ≥ 0.
Q42. Slack variable is added to:
A) ≤ type constraint
B) ≥ type constraint
C) Equality constraint
D) Objective function
Answer: A — Slack variable is added to ≤ constraints to convert into equality.
Q43. Surplus variable is used in:
A) ≤ constraint
B) ≥ constraint
C) Equalities only
D) None
Answer: B — Surplus variable is subtracted from ≥ constraints to convert into equality.
Q44. Artificial variables are introduced in:
A) ≥ and = constraints
B) Only ≤ constraints
C) Objective function
D) None
Answer: A — Artificial variables are added in ≥ and = constraints for simplex start.
Q45. The optimum solution of an LPP always lies:
A) At a corner (extreme) point of feasible region
B) At the mid-point
C) Outside feasible region
D) None
Answer: A — Fundamental theorem ensures optimum lies at corner of feasible region.
Q46. Which is true for feasible region of LPP?
A) Always convex
B) Always concave
C) Non-convex
D) None
Answer: A — Feasible region of LPP is always convex.
Q47. If two constraints are parallel and inconsistent:
A) Multiple solution
B) No feasible solution
C) Infinite solutions
D) Unbounded
Answer: B — Parallel and inconsistent lines ⇒ infeasible.
Q48. Redundant constraint means:
A) Does not affect feasible region
B) Makes region infeasible
C) Removes solution
D) None
Answer: A — Redundant constraint does not affect feasible region.
Q49. In simplex, entering variable is chosen based on:
A) Most negative coefficient in objective row
B) Largest positive value
C) Any random
D) None
Answer: A — Entering variable chosen by most negative (for max problem).
Q50. Leaving variable in simplex is chosen by:
A) Minimum ratio test
B) Maximum ratio test
C) Largest coefficient
D) Random
Answer: A — Minimum ratio test determines leaving variable.
Q51. If no ratio is possible in simplex test:
A) Problem unbounded
B) Multiple solutions
C) Infeasible
D) None
Answer: A — No ratio possible ⇒ unbounded solution.
Q52. Alternative optima occur when:
A) More than one solution gives same objective value
B) Problem infeasible
C) Degeneracy
D) None
Answer: A — Alternative optima exist if multiple corner points give same optimum.
Q53. Big-M method penalizes artificial variables with:
A) Large positive M
B) Large negative M
C) Zero
D) Fraction
Answer: B — For maximization, artificial variables get large negative penalty (−M).
Q54. Shadow price of a resource represents:
A) Marginal worth of that resource
B) Actual market price
C) Surplus value
D) None
Answer: A — Shadow price shows how much objective will improve if resource increased by 1 unit.
Q55. If feasible region is unbounded:
A) Optimal solution may not exist
B) Always infeasible
C) Always multiple solutions
D) None
Answer: A — Optimum may or may not exist if region is unbounded.
Q56. Duality in LPP provides:
A) Relationship between two problems
B) No relation
C) Only feasible region
D) None
Answer: A — Every LPP has a dual, closely related to primal.
Q57. Dual of a minimization problem is:
A) Another minimization
B) A maximization problem
C) Both
D) None
Answer: B — Dual of minimization is maximization and vice versa.
Q58. Complementary slackness theorem connects:
A) Primal and dual optimal solutions
B) Graphical and simplex
C) Shadow price and surplus
D) None
Answer: A — Complementary slackness links primal-dual solutions.
Q59. Simplex method stops when:
A) All coefficients in objective row are non-negative (for max)
B) One variable negative
C) Ratios not possible
D) None
Answer: A — Optimum reached when no negative coefficients remain.
Q60. Which of the following cannot happen in LPP?
A) Unique solution
B) Multiple solutions
C) No solution
D) Non-linear solution
Answer: D — Only linear solutions exist in LPP.
MCQs 61–80 on Linear Programming (LPP)
Q61. A linear programming model is feasible if:
A) It has a unique solution
B) At least one solution satisfies all constraints
C) All variables are integers
D) Objective value is maximum
Answer: B — Feasible means at least one point meets every constraint.
Q62. Which is a real-life application of LPP?
A) Factory production planning
B) Diet planning
C) Transportation and logistics
D) All of these
Answer: D — All are classic LPP applications.
Q63. The dual of a transportation problem is:
A) Assignment problem
B) Diet problem
C) Linear programming problem
D) Another transportation problem
Answer: C — Transportation is a special LP; its dual is also an LP.
Q64. Corner point method is based on the fact that:
A) Optimum lies at an extreme point of feasible region
B) Optimum is at the center
C) Optimum does not exist
D) None
Answer: A — Fundamental theorem of LPP.
Q65. When supply ≠ demand in a transportation problem:
A) It is unbalanced
B) It is infeasible
C) It becomes assignment problem
D) It cannot be solved
Answer: A — Add dummy supply/demand to balance.
Q66. Number of constraints in the dual equals:
A) Number of variables in the primal
B) Number of constraints in the primal
C) Sum of both
D) None
Answer: A — Roles of variables and constraints swap.
Q67. A two-variable LPP is best solved by:
A) Simplex only
B) Graphical method
C) MODI method
D) Hungarian method
Answer: B — Graphical is ideal for 2 variables.
Q68. In simplex, the pivot element is at the intersection of:
A) Entering column and leaving row
B) Any random element
C) Largest number
D) Smallest number
Answer: A — That element is used for the pivot operation.
Q69. An LPP is unbounded if:
A) Feasible region allows objective to increase without limit
B) Constraints are inconsistent
C) There is no BFS
D) Variables are integers
Answer: A — Objective improves indefinitely along a feasible direction.
Q70. Which is NOT an application of LPP?
A) Blending problem
B) Travelling salesman problem
C) Production scheduling
D) Diet problem
Answer: B — TSP is a combinatorial optimization/graph problem.
Q71. The optimal value of the dual is:
A) Unrelated to primal
B) Greater than primal
C) Equal to primal (when both feasible)
D) Less than primal
Answer: C — Strong duality: primal optimum = dual optimum.
Q72. The feasible region of any LPP is always:
A) Convex
B) Concave
C) Non-convex
D) Empty
Answer: A — Intersection of half-spaces is convex.
Q73. Degeneracy in a transportation problem occurs when:
A) Number of allocations < (m + n − 1)
B) Number of allocations > (m + n − 1)
C) Supply ≠ demand
D) Cost matrix is large
Answer: A — Add ฮต (or dummy allocation) to resolve.
Q74. Hungarian method is used for:
A) Transportation problem
B) Assignment problem
C) Dual simplex
D) Blending problem
Answer: B — It solves the assignment problem optimally.
Q75. In simplex, multiple optima exist when:
A) A non-basic variable has zero reduced cost at optimum
B) No feasible solution exists
C) Solution is unbounded
D) Problem is infeasible
Answer: A — Zero reduced cost indicates alternate BFS with same Z.
Q76. A redundant constraint is one that:
A) Does not change the feasible region
B) Makes solution infeasible
C) Always improves objective value
D) Cannot be included in simplex
Answer: A — It is implied by other constraints.
Q77. Shadow price of a non-binding constraint is:
A) Positive
B) Zero
C) Negative
D) Undefined
Answer: B — Non-binding constraints have zero dual value.
Q78. If primal has m constraints and n variables, then the dual has:
A) m variables and n constraints
B) n variables and m constraints
C) m + n constraints
D) None
Answer: B — Variables and constraints swap counts.
Q79. In assignment, minimizing cost is equivalent to:
A) Maximizing profit (after suitable transformation)
B) Transportation maximization
C) Integer programming
D) None
Answer: A — Convert profits to costs (or vice versa) to use Hungarian method.
Q80. The simplex method was developed by:
A) George Dantzig
B) Hitchcock
C) Koopmans
D) Gomory
Answer: A — Dantzig introduced the simplex algorithm in 1947.
MCQs 81–100 on Linear Programming (LPP)
Q81. Linear Programming mainly deals with:
A) Linear objectives & linear constraints
B) Nonlinear objectives
C) Differential equations
D) Dynamic systems
Answer: A — Both objective and constraints must be linear.
Q82. In graphical LPP, optimum solution is found by:
A) Checking all corner points
B) Picking mid-point
C) Guessing
D) Ignoring constraints
Answer: A — Compare Z-values at corner points.
Q83. In simplex, artificial variables are introduced in:
A) ≥ constraints
B) ≤ constraints
C) Equality constraints
D) Both ≥ and = constraints
Answer: D — Artificial variables help to start feasible basis.
Q84. Transportation problem is a special case of LPP because:
A) It has a specific structure (supply = demand)
B) Only two variables exist
C) Always infeasible
D) None
Answer: A — Special structure makes it easier to solve.
Q85. Assignment problem is a special case of:
A) Transportation problem
B) Integer programming
C) Nonlinear programming
D) Game theory
Answer: A — It is transportation with unit supply/demand.
Q86. Sensitivity analysis in LPP studies:
A) Effect of parameter changes on optimal solution
B) Derivatives
C) Game strategies
D) None
Answer: A — It checks robustness of the solution.
Q87. Which is true for any LPP?
A) Feasible region is convex
B) Optimum lies at corner
C) Multiple optima possible
D) All of these
Answer: D — All are correct properties.
Q88. If all variables in an LPP must take integer values, it becomes:
A) Integer programming problem
B) Transportation problem
C) Assignment problem
D) None
Answer: A — Integer restrictions make it IPP.
Q89. Two-phase simplex is used when:
A) Artificial variables are present
B) All constraints are ≤ type
C) Problem has only two variables
D) Solution is integer
Answer: A — Phase-I removes artificial variables.
Q90. If optimum solution satisfies more constraints than necessary, the problem shows:
A) Degeneracy
B) Unboundedness
C) Infeasibility
D) Multiple optima
Answer: A — Extra active constraints = degeneracy.
Q91. An infeasible LPP means:
A) No solution satisfies all constraints
B) Solution is unbounded
C) Multiple optima exist
D) Z-value is zero
Answer: A — Feasible region is empty.
Q92. The term "basic feasible solution" means:
A) Feasible solution with exactly m non-zero variables (for m constraints)
B) Solution with all variables zero
C) Infeasible solution
D) None
Answer: A — BFS has number of non-zero variables = number of constraints.
Q93. Shadow price is also called:
A) Dual value
B) Reduced cost
C) Opportunity cost
D) Pivot value
Answer: A — Shadow price = dual variable value.
Q94. Reduced cost of a basic variable in simplex is always:
A) Zero
B) Positive
C) Negative
D) Undefined
Answer: A — Basic variables always have zero reduced cost.
Q95. If the objective is to minimize cost, simplex method uses:
A) Dual simplex
B) Same method but with minimization rule
C) Only graphical method
D) MODI method
Answer: B — Simplex can be used for both max and min problems.
Q96. The northwest corner rule is used to find:
A) Initial feasible solution of transportation problem
B) Optimal assignment
C) Shadow price
D) Dual variables
Answer: A — It gives starting allocation.
Q97. In an assignment problem, if the number of jobs ≠ number of workers:
A) Add dummy rows/columns
B) Problem is infeasible
C) Convert to transportation
D) None
Answer: A — Make it balanced before solving.
Q98. The dual simplex method is applied when:
A) Solution is infeasible but optimality condition satisfied
B) Problem is nonlinear
C) Degeneracy occurs
D) All variables are integers
Answer: A — Dual simplex fixes feasibility while keeping optimality.
Q99. Who is considered the father of Linear Programming?
A) George Dantzig
B) Hitchcock
C) Koopmans
D) Fourier
Answer: A — Dantzig is known as father of LP.
Q100. The solution of an LPP lies:
A) Always inside feasible region
B) Always at a corner (extreme point)
C) Outside feasible region
D) None
Answer: B — Optimum is achieved at a vertex of feasible region.
Final Notes for Revision
- Optimal solution of LPP always lies at a corner point.
- Graphical method works only for 2 variables.
- Simplex method solves higher-variable LPP.
- Slack variables for ≤, surplus + artificial for ≥.
- Dual problem gives resource values (shadow prices).
Comments
Post a Comment