BSIE Operations Research & Linear Programming 1 — Questions and Answers
Question 1: In linear programming, what is the region that satisfies all constraints called?
- Objective region
- Feasible region (Correct answer)
- Optimal region
- Constraint region
Correct answer: Feasible region
The feasible region is the set of all points that satisfy every constraint in a linear programming problem.
Question 2: Which method is most commonly used to solve large-scale linear programming problems?
- Graphical method
- Branch-and-bound
- Simplex method (Correct answer)
- Hungarian algorithm
Correct answer: Simplex method
The simplex method iterates along the edges of the feasible polytope to find the optimal vertex efficiently for large-scale LP problems.
Question 3: In the transportation problem, what condition must be met for a balanced problem?
- Total supply equals total demand (Correct answer)
- Number of sources equals number of destinations
- All costs are equal
- All routes are used
Correct answer: Total supply equals total demand
A balanced transportation problem requires that the sum of all supplies equals the sum of all demands.
Question 4: What does the dual price (shadow price) represent in linear programming?
- The cost of adding a new variable
- The rate of change of the objective function per unit increase in a constraint's RHS (Correct answer)
- The penalty for infeasibility
- The reduced cost of a basic variable
Correct answer: The rate of change of the objective function per unit increase in a constraint's RHS
The shadow price tells the decision-maker how much the optimal objective value improves for each one-unit relaxation of a binding constraint.
Question 5: In queuing theory, what does the notation M/M/1 represent?
- Multiple arrivals, multiple servers, 1 queue
- Markovian arrivals, Markovian service, 1 server (Correct answer)
- Mixed arrivals, mixed service, 1 priority
- Manual arrivals, manual service, 1 stage
Correct answer: Markovian arrivals, Markovian service, 1 server
M/M/1 denotes a queue with Poisson (Markovian) arrivals, exponential (Markovian) service times, and a single server.
Question 6: Which of the following is NOT an assumption of linear programming?
- Linearity
- Divisibility
- Certainty
- Non-linear objective (Correct answer)
Correct answer: Non-linear objective
LP requires a linear objective function; a non-linear objective violates the fundamental linearity assumption of the model.
BSIE Operations Research & Linear Programming 1
In linear programming, what is the region that satisfies all constraints called?