2.8 MCQs-Linear Programming

---

Linear Programming

Basic Concepts and Formulation

1. Linear Programming (LP) is a method for:

1. Solving systems of linear equations

2. Finding the optimal value of a linear objective function subject to linear constraints

3. Graphing linear functions

4. Calculating matrix determinants

Show me the answer

Answer: 2. Finding the optimal value of a linear objective function subject to linear constraints

Explanation: Linear programming is a mathematical optimization technique used to achieve the best outcome (maximum profit, minimum cost, etc.) in a mathematical model whose requirements are represented by linear relationships. The standard form of an LP problem is:

Maximize (or Minimize): $z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$

Subject to: $a_{11}x_1 + a_{12}x_2 + \cdots + a_{1n}x_n \leq b_1$ $a_{21}x_1 + a_{22}x_2 + \cdots + a_{2n}x_n \leq b_2$ $\vdots$ $a_{m1}x_1 + a_{m2}x_2 + \cdots + a_{mn}x_n \leq b_m$ $x_1, x_2, \ldots, x_n \geq 0$

2. The feasible region in an LP problem is:

1. The set of all points that satisfy the objective function

2. The set of all points that satisfy all constraints including non-negativity

3. The set of corner points of the constraint graph

4. The optimal solution point

Show me the answer

Answer: 2. The set of all points that satisfy all constraints including non-negativity

Explanation: The feasible region is the set of all possible points (solutions) that satisfy all the constraints of the LP problem, including the non-negativity restrictions $x_i \geq 0$. In graphical terms (for 2-variable problems), it is the intersection of half-planes defined by the constraints. The feasible region is always a convex polygon (in 2D) or polyhedron (in higher dimensions).

3. In an LP problem, the objective function is:

1. A set of linear inequalities

2. A linear function to be maximized or minimized

3. The feasible region boundary

4. The non-negativity constraints

Show me the answer

Answer: 2. A linear function to be maximized or minimized

Explanation: The objective function is the linear function that we want to optimize (either maximize or minimize). It represents the quantity we want to optimize, such as profit, cost, revenue, etc. The general form is:

$z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$

where $c_i$ are coefficients (profit/cost per unit) and $x_i$ are decision variables.

Graphical Method

4. In the graphical method of solving LP problems, the optimal solution:

1. Always lies at the origin

2. Always lies on the boundary of the feasible region

3. Always lies at a corner point of the feasible region

4. Can be anywhere in the feasible region

Show me the answer

Answer: 3. Always lies at a corner point of the feasible region

Explanation: For linear programming problems, the Fundamental Theorem of Linear Programming states that if an optimal solution exists, then at least one optimal solution occurs at a corner point (vertex) of the feasible region. This is why the simplex method works by moving from one corner point to another along the edges of the feasible region.

5. For the constraints $x + y \leq 4$, $2x + y \leq 6$, $x \geq 0$, $y \geq 0$, the feasible region has:

1. 3 corner points

2. 4 corner points

3. 5 corner points

4. 6 corner points

Show me the answer

Answer: 2. 4 corner points

Explanation: Let's find the corner points:

1. Intersection of $x=0$ and $y=0$: (0, 0)

2. Intersection of $x=0$ and $x+y=4$: (0, 4)

3. Intersection of $y=0$ and $2x+y=6$: (3, 0)

4. Intersection of $x+y=4$ and $2x+y=6$: Solve: $x+y=4$ and $2x+y=6$ Subtract first from second: $x=2$, then $y=2$ So (2, 2)

That's 4 corner points: (0,0), (0,4), (3,0), (2,2).

6. When the objective function lines are parallel to a boundary of the feasible region:

1. There is no optimal solution

2. There is a unique optimal solution

3. There are multiple optimal solutions

4. The problem is infeasible

Show me the answer

Answer: 3. There are multiple optimal solutions

Explanation: If the objective function line (isoprofit/isocost line) is parallel to a constraint line that forms a boundary of the feasible region, then all points along that edge are optimal solutions. This gives infinitely many optimal solutions, all giving the same optimal value of the objective function.

Example: If maximizing $z = 2x + 2y$ with constraints $x+y \leq 4$, $x \geq 0$, $y \geq 0$, then the entire line segment from (0,4) to (4,0) gives $z=8$.

Types of Solutions

7. An LP problem is said to be unbounded when:

1. The feasible region is empty

2. The objective function can be increased indefinitely

3. There are multiple optimal solutions

4. All constraints are equalities

Show me the answer

Answer: 2. The objective function can be increased indefinitely

Explanation: An LP problem is unbounded if the objective function can be made arbitrarily large (in a maximization problem) or arbitrarily small (in a minimization problem) while still satisfying all constraints. This occurs when the feasible region extends infinitely in the direction of improving the objective function value.

Graphically, the feasible region is unbounded and the objective function lines can be moved indefinitely in the improving direction without leaving the feasible region.

8. An LP problem is infeasible when:

1. The objective function has no maximum

2. The feasible region is empty

3. There are too many constraints

4. The objective function is nonlinear

Show me the answer

Answer: 2. The feasible region is empty

Explanation: An LP problem is infeasible if there is no solution that satisfies all constraints simultaneously. Graphically, this means the constraints define regions that don't overlap, resulting in an empty feasible region.

Example: $x+y \leq 2$ and $x+y \geq 3$ with $x \geq 0$, $y \geq 0$ cannot be satisfied simultaneously.

9. A degenerate solution in LP occurs when:

1. The optimal solution is not unique

2. More than two constraints are binding at a corner point

3. A basic variable takes the value zero in the optimal solution

4. The problem is infeasible

Show me the answer

Answer: 3. A basic variable takes the value zero in the optimal solution

Explanation: In the simplex method, a basic feasible solution is degenerate if one or more basic variables have value zero. Geometrically, this occurs when more than $n$ constraints (where $n$ is the number of variables) pass through a corner point. Degeneracy can cause cycling in the simplex method, though this is rare in practice.

Standard Form and Conversions

10. The standard form of an LP problem requires:

1. All constraints to be equations

2. All variables to be non-negative

3. The objective function to be maximization

4. Both 1 and 2

Show me the answer

Answer: 4. Both 1 and 2

Explanation: The standard form for an LP problem has:

1. All constraints are equations (not inequalities)

2. All variables are non-negative

3. The objective function is either maximization or minimization (though maximization is more common in textbooks)

To convert inequalities to equations:

• For $\leq$ constraints: Add a slack variable: $a_{i1}x_1 + \cdots + a_{in}x_n + s_i = b_i$, $s_i \geq 0$

• For $\geq$ constraints: Subtract a surplus variable: $a_{i1}x_1 + \cdots + a_{in}x_n - s_i = b_i$, $s_i \geq 0$

11. A slack variable is used to convert:

1. A $\leq$ constraint to an equation

2. A $\geq$ constraint to an equation

3. An equation to a $\leq$ constraint

4. A non-negativity constraint to an equation

Show me the answer

Answer: 1. A $\leq$ constraint to an equation

Explanation: Slack variables represent unused resources. For a $\leq$ constraint like $a_{i1}x_1 + \cdots + a_{in}x_n \leq b_i$, we add a slack variable $s_i \geq 0$ to convert it to an equation:

$a_{i1}x_1 + \cdots + a_{in}x_n + s_i = b_i$

The slack variable $s_i$ measures how much of resource $i$ is unused in a particular solution. If $s_i = 0$, the constraint is binding (all resources used).

12. A surplus variable is used to convert:

1. A $\leq$ constraint to an equation

2. A $\geq$ constraint to an equation

3. An equation to a $\geq$ constraint

4. A non-negativity constraint to an equation

Show me the answer

Answer: 2. A $\geq$ constraint to an equation

Explanation: Surplus variables represent excess above a minimum requirement. For a $\geq$ constraint like $a_{i1}x_1 + \cdots + a_{in}x_n \geq b_i$, we subtract a surplus variable $s_i \geq 0$ to convert it to an equation:

$a_{i1}x_1 + \cdots + a_{in}x_n - s_i = b_i$

The surplus variable $s_i$ measures how much the solution exceeds the minimum requirement. If $s_i = 0$, the constraint is binding (exactly meeting the requirement).

Simplex Method

13. The simplex method solves LP problems by:

1. Evaluating the objective function at all corner points

2. Moving from one corner point to an adjacent one with better objective value

3. Using calculus to find the maximum/minimum

4. Solving the dual problem instead

Show me the answer

Answer: 2. Moving from one corner point to an adjacent one with better objective value

Explanation: The simplex method is an iterative algorithm that:

1. Starts at a corner point (basic feasible solution) of the feasible region

2. Moves to an adjacent corner point that improves the objective function value

3. Continues until no adjacent corner point gives improvement (optimal solution found)

It uses a tableau format to systematically perform these operations through pivot operations.

14. In the simplex method, the entering variable is chosen by:

1. The most negative coefficient in the objective row (for maximization)

2. The most positive coefficient in the objective row (for maximization)

3. The smallest ratio in the ratio test

4. Random selection

Show me the answer

Answer: 1. The most negative coefficient in the objective row (for maximization)

Explanation: In the simplex method for maximization problems:

• The entering variable (variable to enter the basis) is the one with the most negative coefficient in the objective row (Z-row or C-row).

• This corresponds to the variable that will increase the objective function value the fastest per unit increase.

• For minimization problems, we would choose the most positive coefficient.

This rule assumes we are using the standard form and the objective function coefficients are in the top row of the simplex tableau.

15. In the simplex method, the leaving variable is determined by:

1. The most negative coefficient in the objective row

2. The minimum ratio test (smallest non-negative ratio)

3. The maximum ratio test

4. The variable with the smallest coefficient

Show me the answer

Answer: 2. The minimum ratio test (smallest non-negative ratio)

Explanation: Once the entering variable is chosen, the leaving variable (variable to leave the basis) is determined by the minimum ratio test:

1. For each row (constraint), compute the ratio: Right-hand side (RHS) / Coefficient of entering variable in that row

2. Consider only positive coefficients of the entering variable (ignore zero or negative)

3. Choose the row with the smallest non-negative ratio

This ensures we move to an adjacent corner point while maintaining feasibility (all variables non-negative).

16. The optimality condition in the simplex method for maximization is:

1. All coefficients in the objective row are positive or zero

2. All coefficients in the objective row are negative or zero

3. All coefficients in the objective row are zero

4. The RHS values are all positive

Show me the answer

Answer: 1. All coefficients in the objective row are positive or zero

Explanation: In the simplex method for maximization problems:

• When all coefficients in the objective row (excluding the RHS) are non-negative (≥ 0), the current solution is optimal.

• This means no variable can enter the basis to improve the objective function value.

• For minimization problems, optimality occurs when all coefficients in the objective row are non-positive (≤ 0).