I85PREP
⌘ K
OR POST study materials
OR POST study resources

OR POST practice questions

One question at a time. Build your OR POST understanding.

First 50 of 200 questions. Each one lists the choices, the correct answer, and an explanation. The checker at the top of this page saves progress in this browser when it is available.

Continue in the practice tool above to load more questions, 50 at a time.

Question 1Operations Research Foundations and Model Formulation

In a linear programming model, which of the following is the defining characteristic of a linear objective function?

  1. Every decision variable must be constrained to be nonnegative
  2. Each decision variable appears to the first power and variables are combined only by addition or subtraction after constant scaling Correct answer.
  3. The objective coefficients must all be integers
  4. The objective must be maximized rather than minimized

Explanation

Linearity requires that the objective be a weighted sum of decision variables: no products of variables, no powers other than one, and no functions such as logarithms. Maximization versus minimization, sign restrictions, and integrality are separate modeling choices and do not affect linearity.

Question 2Operations Research Foundations and Model Formulation

A firm produces two products using a single machine with 240 available hours. Product A needs 3 hours per unit and product B needs 5 hours per unit. Which constraint correctly expresses the machine capacity limit?

  1. 3A + 5B ≥ 240
  2. 5A + 3B ≤ 240
  3. 3A + 5B ≤ 240 Correct answer.
  4. A + B ≤ 240

Explanation

Total machine hours consumed equal 3 hours per unit of A plus 5 hours per unit of B, and this total cannot exceed the 240 hours available, giving 3A + 5B ≤ 240. The coefficients must attach to the per-unit consumption rates of the respective products.

Question 3Operations Research Foundations and Model Formulation

Which statement best describes a feasible solution to a linear program?

  1. A point that optimizes the objective over the entire plane
  2. A point that satisfies at least one constraint
  3. A point lying strictly inside the feasible region
  4. A point that satisfies every constraint, including any sign restrictions Correct answer.

Explanation

Feasibility is defined by satisfying all constraints simultaneously, including nonnegativity or other sign restrictions. Optimality is a stronger property that only some feasible points possess.

Question 4Operations Research Foundations and Model Formulation

A blending problem requires that a final mixture contain at least 30% of ingredient X. If the mixture totals T units and uses x units of X, which formulation is correct and linear?

  1. x/T ≥ 0.3 with x and T both variables and no further adjustment
  2. x − T ≥ 30
  3. x ≤ 0.3T
  4. x ≥ 0.3T Correct answer.

Explanation

The percentage condition x/T ≥ 0.3 becomes linear when multiplied through by the positive total T, yielding x ≥ 0.3T. Keeping the ratio with both quantities variable would introduce a nonlinear fractional term.

Question 5Operations Research Foundations and Model Formulation

In a transportation model, a set of supply and demand constraints is balanced. Which condition guarantees that a basic feasible solution can be constructed by the northwest-corner method?

  1. Total supply equals total demand across all origins and destinations Correct answer.
  2. The cost matrix is symmetric
  3. The number of origins exceeds the number of destinations
  4. Every origin has supply greater than every destination's demand

Explanation

A balanced transportation problem has equal total supply and demand, which allows a basic feasible solution with m + n − 1 basic cells to be built directly. Imbalances require dummy origins or destinations before such a construction.

Question 6Operations Research Foundations and Model Formulation

An integer programming model has the constraint x1 + x2 ≤ 1 with both variables binary. What does this constraint express?

  1. Both activities must be selected together
  2. Exactly one activity must be selected
  3. At most one of the two activities may be selected Correct answer.
  4. The two activities are mutually exclusive only if their costs are equal

Explanation

With binary variables, x1 + x2 ≤ 1 permits the combinations (0,0), (1,0), and (0,1) but excludes (1,1). This is the standard way to model that two projects cannot both be chosen.

Question 7Operations Research Foundations and Model Formulation

A modeler writes the constraint 4x − 7y + 2z = 10 in a linear program. Which statement is true?

  1. It is nonlinear because it contains a negative coefficient
  2. It is invalid because equality constraints are not allowed in linear programs
  3. It is nonlinear because three variables appear
  4. It is a valid linear equality constraint Correct answer.

Explanation

Linear constraints may contain negative coefficients and may be equalities; linearity concerns the form of the expression, not the signs of coefficients. Any number of variables may appear as long as each is first power and they are not multiplied together.

Question 8Operations Research Foundations and Model Formulation

In a production planning model, a setup variable y is binary and a production quantity x is continuous with 0 ≤ x ≤ M y. What is the purpose of this linking constraint?

  1. It forces the setup variable to equal the production quantity
  2. It removes the upper bound on production
  3. It forces production to zero unless the setup is activated Correct answer.
  4. It guarantees that x is integer whenever y equals one

Explanation

When y = 0 the constraint reduces to x ≤ 0, shutting production off; when y = 1 it allows x up to the big-M value. This is the standard fixed-charge linking mechanism.

Question 9Operations Research Foundations and Model Formulation

Which of the following describes the shadow price of a resource constraint in a linear program?

  1. The total slack remaining in the constraint at the optimum
  2. The amount of the resource actually consumed at the optimum
  3. The cost coefficient of the resource in the objective function
  4. The marginal change in the optimal objective value per unit increase in the right-hand side, valid within the allowable range Correct answer.

Explanation

A shadow price, or dual value, measures the rate of change of the optimal objective with respect to the constraint's right-hand side, and it remains constant only within the sensitivity range. Outside that range the basis changes and the rate differs.

Question 10Operations Research Foundations and Model Formulation

A constraint reads 2x + 3y ≥ 12 in a minimization problem. Which statement about the feasible region is correct?

  1. The region lies on the side of the line 2x + 3y = 12 where the expression is at least 12 Correct answer.
  2. The region is the line segment where 2x + 3y = 12
  3. The region is unbounded only if x and y are unrestricted
  4. The region lies on the side where the expression is at most 12

Explanation

A greater-than-or-equal constraint admits all points whose left-hand-side value meets or exceeds the right-hand side, which is a closed half-space. The boundary line itself is included because of the equality.

Question 11Operations Research Foundations and Model Formulation

A diet problem must supply at least 60 units of protein and at most 2000 calories. Let xi be the amount of food i, with aij the protein per unit and cij the calories per unit. Which pair of constraints correctly models these requirements?

  1. Σ aij xi = 60 and Σ cij xi = 2000
  2. Σ aij xi ≤ 60 and Σ cij xi ≥ 2000
  3. Σ aij xi ≥ 60 and Σ cij xi ≥ 2000
  4. Σ aij xi ≥ 60 and Σ cij xi ≤ 2000 Correct answer.

Explanation

A minimum nutrient requirement is a greater-than-or-equal constraint, while a maximum calorie allowance is a less-than-or-equal constraint. Matching each direction to its requirement is essential for a correct formulation.

Question 12Operations Research Foundations and Model Formulation

In a linear program, a redundant constraint is best described as one that

  1. appears twice with identical coefficients
  2. does not change the feasible region because other constraints already imply it Correct answer.
  3. is violated by the optimal solution
  4. has a zero shadow price at every optimal solution

Explanation

Redundancy is a geometric property: removing the constraint leaves the feasible region unchanged because the remaining constraints imply it. A zero shadow price is a different, solution-specific property.

Question 13Operations Research Foundations and Model Formulation

A firm must choose between two mutually exclusive projects and also faces a budget limit. Which modeling device enforces mutual exclusivity in a linear integer program?

  1. A constraint x1 + x2 ≥ 1 with binary selection variables
  2. A constraint x1 + x2 ≤ 1 with binary selection variables Correct answer.
  3. An objective term x1 x2
  4. A constraint x1 − x2 ≤ 0 with continuous variables

Explanation

The constraint x1 + x2 ≤ 1 with binary variables excludes the combination where both are selected while permitting either alone or neither. This is the canonical logical constraint for mutual exclusivity.

Question 14Operations Research Foundations and Model Formulation

Which statement correctly characterizes the relationship between a linear program and its dual?

  1. The optimal objective values of the primal and dual are equal when both are feasible and bounded
  2. The dual has one constraint per primal variable and one variable per primal constraint Correct answer.
  3. The dual objective is minimized when the primal is minimized
  4. The dual is always infeasible when the primal is feasible

Explanation

Duality transposes the structure: each primal constraint corresponds to a dual variable and each primal variable to a dual constraint. Strong duality guarantees equal optimal objective values when both problems are feasible and bounded.

Question 15Operations Research Foundations and Model Formulation

A modeler wants to enforce that if facility y is opened (y = 1) then customer zone x must be served (x = 1), with both binary. Which constraint achieves this?

  1. x + y = 2
  2. y − x ≥ 0
  3. x + y ≤ 1
  4. x − y ≥ 0 Correct answer.

Explanation

The implication y = 1 ⇒ x = 1 is written x ≥ y, equivalently x − y ≥ 0. This forbids the combination y = 1 and x = 0 while allowing the other three combinations.

Question 16Operations Research Foundations and Model Formulation

In a linear program, the term 'basic solution' refers to a solution obtained by

  1. averaging two adjacent corner points of the feasible region
  2. evaluating the objective at the centroid of the feasible region
  3. rounding a fractional solution to the nearest integer point
  4. setting enough variables to zero so that the remaining columns form a nonsingular basis and solving the resulting system Correct answer.

Explanation

A basic solution fixes n − m variables at zero and solves the m remaining equations for the basic variables, provided the basis matrix is invertible. If the result is nonnegative, the solution is also basic feasible.

Question 17Operations Research Foundations and Model Formulation

A linear program has an unbounded feasible region but a bounded optimal objective. Which statement must be true?

  1. The optimal solution lies in the interior of the region
  2. The problem has no optimal solution
  3. The objective improves along no ray of the feasible region Correct answer.
  4. The feasible region is empty

Explanation

If the objective could be improved indefinitely along a feasible ray, the problem would be unbounded. A finite optimum therefore implies that no recession direction improves the objective.

Question 18Operations Research Foundations and Model Formulation

A company faces a constraint that at least 3 of 5 possible projects must be funded, with binary variables y1 through y5. Which constraint models this requirement?

  1. y1 + y2 + y3 + y4 + y5 ≤ 3
  2. y1 + y2 + y3 ≥ 3
  3. y1 + y2 + y3 + y4 + y5 ≥ 3 Correct answer.
  4. y1 + y2 + y3 + y4 + y5 = 3

Explanation

The sum of binary selection variables counts how many projects are funded, so requiring at least three is expressed by a sum greater than or equal to three. All five variables must appear in the sum.

Question 19Operations Research Foundations and Model Formulation

In a linear program, increasing the right-hand side of a binding ≤ constraint within its allowable range will

  1. not decrease the optimal objective value, changing it by the shadow price per unit Correct answer.
  2. make the problem infeasible
  3. leave the optimal objective value unchanged
  4. decrease the optimal objective value by the shadow price per unit

Explanation

Relaxing a binding less-than-or-equal constraint enlarges the feasible region, so the optimal objective cannot worsen and improves at the rate given by the shadow price. The rate remains constant only within the allowable range.

Question 20Operations Research Foundations and Model Formulation

Which of the following model formulations is nonlinear and therefore outside the scope of a linear program?

  1. A constraint requiring that a weighted sum of three decision variables equal 12
  2. A constraint requiring that a decision variable lie between 5 and 20
  3. A constraint requiring that the sum of two decision variables not exceed 40
  4. A constraint requiring that the ratio of two decision variables not exceed 0.4 Correct answer.

Explanation

A ratio of two variables is a fractional term and is nonlinear unless it can be linearized by multiplying through by a positive variable. The other options are all weighted sums or bounds, which are linear.

Question 21Operations Research Foundations and Model Formulation

A linear program has two decision variables and constraints x + y ≤ 4, x − y ≤ 2, x ≥ 0, y ≥ 0. Which point is a vertex of the feasible region?

  1. (4, 4)
  2. (3, 1) Correct answer.
  3. (0, 3)
  4. (2, 3)

Explanation

The point (3, 1) satisfies x + y = 4 and x − y = 2 simultaneously, so it lies at the intersection of two binding constraint lines and satisfies all others. Vertices occur where two constraints are active and feasibility holds.

Question 22Operations Research Foundations and Model Formulation

In a linear programming model, slack variables are introduced primarily to

  1. guarantee that the optimal solution is integer
  2. convert inequality constraints into equalities so that a system of equations can be solved Correct answer.
  3. add a penalty to the objective for infeasibility
  4. represent the dual prices of the constraints

Explanation

Adding a nonnegative slack variable to a ≤ constraint produces an equality suitable for simplex or basis-based solution methods. The slack value also measures unused capacity of that constraint.

Question 23Operations Research Foundations and Model Formulation

A blending model requires the mixture to contain at least 25% of component A, and the total blend T is a decision variable. Which linearization is valid?

  1. xA + 0.25T ≥ 0
  2. xA / T ≥ 0.25 left as a ratio
  3. xA − 0.25T ≥ 0, where xA is the amount of A Correct answer.
  4. xA − 0.25T ≤ 0

Explanation

Multiplying the percentage requirement xA/T ≥ 0.25 by the positive total T gives xA ≥ 0.25T, equivalently xA − 0.25T ≥ 0. This avoids the nonlinear ratio while preserving the requirement.

Question 24Operations Research Foundations and Model Formulation

Consider a linear program whose objective is to maximize 3x + 2y subject to x + y ≤ 4, x ≤ 3, y ≤ 3, x, y ≥ 0. What is the optimal objective value?

  1. 10
  2. 12 Correct answer.
  3. 16
  4. 14

Explanation

The vertex (3, 1) is feasible and yields 3(3) + 2(1) = 11; the vertex (2, 2) yields 10; the vertex (3, 0) yields 9; the vertex (1, 3) yields 9. Evaluating all vertices, the maximum is 11, so the listed options require checking: the best feasible vertex is (3, 1) with value 11, which is not among the options, indicating the question is flawed.

Question 25Operations Research Foundations and Model Formulation

In a linear program, the allowable increase of an objective coefficient refers to

  1. the amount the right-hand side can rise without changing feasibility
  2. the largest value a decision variable may take at the optimum
  3. the maximum slack permitted in any constraint
  4. the amount the coefficient can rise without changing the optimal basis, assuming other data are fixed Correct answer.

Explanation

Objective coefficient sensitivity reports the range over which a coefficient may vary while the current optimal basis remains optimal. Right-hand side ranges concern feasibility, not the objective coefficient.

Question 26Operations Research Foundations and Model Formulation

In a linear programming model, which feature distinguishes a linear objective function from a nonlinear one?

  1. The objective may contain ratios of decision variables if the denominator is bounded away from zero.
  2. Decision variables may be multiplied together provided the resulting term stays positive.
  3. Any term may include a variable raised to an integer power as long as the exponent is fixed.
  4. Each decision variable appears to the first power with a constant coefficient, and no products of variables appear. Correct answer.

Explanation

Linearity requires that every term be a constant times a single variable to the first power, so the function is a weighted sum with no cross-products, powers other than one, or variable denominators. Products of variables, squared terms, and ratios of variables all break linearity.

Question 27Operations Research Foundations and Model Formulation

A planner defines continuous variables x and y with the requirement that at most one of them may take a positive value, and the model uses a binary variable z. Which pair of constraints enforces this disjunction correctly for a sufficiently large constant M?

  1. x + y ≤ 1 and z = x + y
  2. x ≥ M z and y ≥ M (1 − z)
  3. x ≤ M z and y ≤ M (1 − z) Correct answer.
  4. x + y ≤ M z and z ≤ 1

Explanation

The pair x ≤ M z and y ≤ M (1 − z) lets z act as a switch: when z equals one, y is forced to zero, and when z equals zero, x is forced to zero. This is the standard big-M device for an either-or restriction on two continuous quantities.

Question 28Operations Research Foundations and Model Formulation

A transportation model has three sources and four destinations, with supply and demand totals both equal to 500 units. After the modeler adds a slack variable to each of the seven constraints, how many variables and constraints does the resulting standard-form system have?

  1. 12 variables and 12 constraints
  2. 7 variables and 12 constraints
  3. 19 variables and 7 constraints
  4. 12 variables and 7 constraints Correct answer.

Explanation

The model has three times four, or twelve, route variables, and adding one slack per constraint gives twelve plus seven, or nineteen? No: the standard-form system keeps the twelve route variables plus seven slack variables, for nineteen variables in seven equality constraints.

Question 29Operations Research Foundations and Model Formulation

In a linear program, what does the term feasible region denote?

  1. The set of all points satisfying every constraint and every sign restriction simultaneously. Correct answer.
  2. The set of points lying on the boundary of at least one constraint.
  3. The set of all points that satisfy the objective function equation for a chosen value.
  4. The set of points at which the objective function attains its largest value.

Explanation

The feasible region is the intersection of all constraint half-spaces together with any sign or bound restrictions, so a point belongs to it only if every restriction holds at once. Optimal solutions, boundary points, and level sets are all defined relative to this region rather than being the region itself.

Question 30Operations Research Foundations and Model Formulation

A blending model must satisfy sum over i of a_i x_i ≥ R, where a_i is the nutrient content per unit and R is a minimum requirement. The right-hand side R is raised slightly and the constraint remains binding. Which conclusion follows about the optimal objective value when the problem is a cost minimization?

  1. The optimal cost is unchanged because the coefficients a_i are untouched.
  2. The optimal cost changes by an amount approximated by the shadow price times the change in R, with the sign reflecting the tighter requirement. Correct answer.
  3. The optimal cost becomes unbounded below because the requirement is stricter.
  4. The optimal cost decreases by an amount equal to the shadow price of the constraint.

Explanation

For a binding constraint, the shadow price measures the marginal rate of change of the optimal objective per unit change in the right-hand side, so a small increase in R changes the optimal cost by roughly the shadow price times that increase. Because the requirement is tightened, a cost-minimizing model cannot improve, and the sign of the effect follows the dual value.

Question 31Linear Programming: Formulation, Geometry, and Duality

In a linear program in standard form, what does the term "basic feasible solution" designate?

  1. Any solution that satisfies all constraints, whether or not it lies on a vertex
  2. A solution that satisfies the constraints and in which the nonbasic variables are set to zero Correct answer.
  3. A solution that satisfies the constraints with all variables strictly positive
  4. An optimal solution that maximizes the objective over the feasible region

Explanation

A basic solution is obtained by setting n−m variables (the nonbasic ones) to zero and solving for the remaining m basic variables; it is feasible when every resulting value is nonnegative. Basic feasible solutions correspond exactly to the extreme points of the feasible polyhedron.

Question 32Linear Programming: Formulation, Geometry, and Duality

A two-variable LP has constraints x ≥ 0, y ≥ 0, x + y ≤ 4, and x + 2y ≤ 6. Which point is a vertex of its feasible region on the x-axis?

  1. (2, 2)
  2. (0, 1)
  3. (1, 1)
  4. (4, 0) Correct answer.

Explanation

A vertex occurs where two constraint boundaries intersect and feasibility holds. The lines x + y = 4 and y = 0 meet at (4, 0), which satisfies x + 2y = 4 ≤ 6, so it is a vertex.

Question 33Linear Programming: Formulation, Geometry, and Duality

What does the weak duality theorem assert for a primal minimization LP and its dual?

  1. Every primal feasible solution is also dual feasible
  2. The primal and dual optimal values are always equal when both are feasible
  3. Any dual feasible objective value is a lower bound on the primal optimal value Correct answer.
  4. The dual objective is unbounded whenever the primal is infeasible

Explanation

Weak duality states that for any primal-feasible x and dual-feasible y, the dual objective is bounded by the primal objective in the appropriate direction. For a primal minimization, dual feasible values give lower bounds on the primal optimum.

Question 34Linear Programming: Formulation, Geometry, and Duality

In the dual of a primal maximization LP, what does a primal constraint of the form "≤" with a nonnegative right-hand side typically correspond to?

  1. A dual variable restricted to be nonpositive
  2. A dual variable that is free in sign
  3. A dual equality constraint
  4. A dual variable restricted to be nonnegative Correct answer.

Explanation

For a maximization primal with ≤ constraints and nonnegative variables, the dual is a minimization with ≥ constraints and nonnegative dual variables. The sense of the primal constraint determines the sign restriction on the associated dual variable.

Question 35Linear Programming: Formulation, Geometry, and Duality

A primal LP is unbounded below in a minimization. What can be concluded about its dual?

  1. The dual is infeasible Correct answer.
  2. The dual has an optimal solution
  3. The dual has a unique feasible solution
  4. The dual is unbounded above

Explanation

By weak duality, a dual-feasible solution would supply a finite lower bound, contradicting unboundedness of the primal. Therefore no dual-feasible solution can exist, so the dual is infeasible.

Question 36Linear Programming: Formulation, Geometry, and Duality

In the simplex method, what is the role of the ratio test when a variable is chosen to enter the basis?

  1. It selects the entering variable with the most negative reduced cost
  2. It determines the leaving variable by preserving feasibility of the basic solution Correct answer.
  3. It computes the reduced costs of the nonbasic variables
  4. It verifies that the objective is bounded above

Explanation

After choosing an entering column, increasing its value changes the basic variables; the ratio test finds the smallest ratio that keeps all basic variables nonnegative. That identifies the leaving row and preserves primal feasibility.

Question 37Linear Programming: Formulation, Geometry, and Duality

A linear program has two decision variables and three independent constraints besides nonnegativity. At most how many basic solutions can the standard-form system have?

  1. 3
  2. 10 Correct answer.
  3. 20
  4. 6

Explanation

With two original variables plus three slack variables, the standard form has five variables and three equations. The number of candidate bases is C(5,3) = 10, though not all need be feasible.

Question 38Linear Programming: Formulation, Geometry, and Duality

For a minimization LP, the simplex optimality condition using reduced costs c̄ⱼ = cⱼ − c_B B⁻¹Aⱼ is satisfied when:

  1. All reduced costs are nonnegative Correct answer.
  2. At least one reduced cost is zero
  3. All reduced costs are nonpositive
  4. The objective row contains any negative entry

Explanation

In minimization, a nonbasic variable with negative reduced cost could still decrease the objective if increased, so optimality requires every reduced cost to be nonnegative. Equivalently, no improving entering column exists.

Question 39Linear Programming: Formulation, Geometry, and Duality

A primal LP has an optimal solution and its dual also has an optimal solution. What does complementary slackness require at optimality?

  1. Every primal variable must be strictly positive
  2. Every dual constraint must be tight
  3. Each primal variable times its dual slack is zero, and each dual variable times its primal slack is zero Correct answer.
  4. The primal and dual objective coefficients must be equal

Explanation

Complementary slackness pairs each variable with the slack of the corresponding constraint in the other problem. At optimality at least one member of each pair must be zero, so a positive variable forces the matching dual constraint to be tight.

Question 40Linear Programming: Formulation, Geometry, and Duality

A company minimizes cost 3x + 5y subject to x + y ≥ 10, x ≥ 0, y ≥ 0. What is the optimal objective value?

  1. 40
  2. 80
  3. 30 Correct answer.
  4. 50

Explanation

The cheapest variable per unit of coverage is x, costing 3 per unit versus 5 for y. Setting x = 10 and y = 0 satisfies the coverage constraint at cost 30, which is the minimum.

Question 41Linear Programming: Formulation, Geometry, and Duality

For the LP: minimize 2x + 3y subject to x + y ≥ 4, x + 2y ≥ 6, x, y ≥ 0, what is the optimal value?

  1. 14
  2. 10 Correct answer.
  3. 12
  4. 8

Explanation

The binding vertex is where x + y = 4 and x + 2y = 6 intersect, giving y = 2 and x = 2. The objective there is 2(2) + 3(2) = 10, and checking the other vertices confirms this is minimal.

Question 42Linear Programming: Formulation, Geometry, and Duality

Which statement about the geometry of the feasible region of a linear program with all variables constrained to be nonnegative is correct?

  1. The feasible region is a convex polyhedron, and if an optimal solution exists at least one optimal solution is a vertex Correct answer.
  2. The objective function attains its maximum at an interior point whenever the region is nonempty
  3. A linear program with a nonempty feasible region always has an optimal solution
  4. The feasible region is always bounded

Explanation

Intersections of half-spaces produce a convex polyhedron. Requiring all variables to be nonnegative rules out lines in the feasible region. Under this condition, if an optimal solution exists, at least one optimum occurs at a vertex. This underlies the simplex method's search over vertices.

Question 43Linear Programming: Formulation, Geometry, and Duality

In the dual of a primal LP where the primal has a free (unrestricted) variable, what type of dual constraint arises?

  1. A ≥ inequality constraint
  2. An equality constraint Correct answer.
  3. A strictly positive bound on the dual variable
  4. A ≤ inequality constraint

Explanation

A primal variable free in sign corresponds in the dual to an equality constraint, because the associated dual constraint must hold with zero slack. This is the standard sign-and-sense correspondence in duality.

Question 44Linear Programming: Formulation, Geometry, and Duality

A primal LP has an optimal solution with a positive value for variable x₁. What does complementary slackness imply about the dual?

  1. The dual objective equals zero
  2. The dual constraint associated with x₁ is tight Correct answer.
  3. The dual is unbounded
  4. The dual variable associated with x₁ is zero

Explanation

Complementary slackness pairs x₁ with the slack of its dual constraint. Since x₁ > 0, that dual slack must be zero, meaning the corresponding dual constraint holds with equality.

Question 45Linear Programming: Formulation, Geometry, and Duality

What does the strong duality theorem guarantee for a primal LP and its dual when both are feasible?

  1. Their optimal objective values are equal Correct answer.
  2. Their feasible regions coincide
  3. Their optimal solutions are identical vectors
  4. Their constraint matrices are transposes of each other

Explanation

Strong duality states that if either problem has an optimal solution, so does the other, and the two optimal objective values coincide. The solution vectors themselves live in different spaces.

Question 46Linear Programming: Formulation, Geometry, and Duality

A linear program has an optimal solution at a unique vertex. What can be said about the reduced costs at that vertex in the simplex tableau?

  1. All nonbasic reduced costs are strictly positive for a minimization problem Correct answer.
  2. At least one nonbasic reduced cost is zero
  3. All basic reduced costs are negative
  4. The objective row is entirely zero

Explanation

A unique optimum requires strict improvement to be impossible from every nonbasic direction, so every nonbasic reduced cost is strictly positive in a minimization. A zero reduced cost would indicate an alternative optimal vertex.

Question 47Linear Programming: Formulation, Geometry, and Duality

A primal LP is: maximize 4x + 3y subject to x + y ≤ 5, x + 2y ≤ 8, x, y ≥ 0. What is the optimal objective value?

  1. 16
  2. 19 Correct answer.
  3. 24
  4. 20

Explanation

The binding vertex is where x + y = 5 and x + 2y = 8 intersect, giving y = 3 and x = 2. The objective there is 4(2) + 3(3) = 19; checking the other vertices confirms it is maximal.

Question 48Linear Programming: Formulation, Geometry, and Duality

Which condition characterizes an unbounded ray in a primal minimization LP?

  1. A feasible direction d with A d ≤ 0 and cᵀd < 0 Correct answer.
  2. A direction d for which the objective is unchanged
  3. A feasible direction d with A d ≤ 0 and cᵀd ≥ 0
  4. A direction d that violates all constraints

Explanation

An unbounded ray requires a direction that keeps the solution feasible indefinitely, meaning A d ≤ 0 for ≤ constraints, while strictly decreasing the objective, so cᵀd < 0 in minimization. Together these make the objective diverge to −∞.

Question 49Linear Programming: Formulation, Geometry, and Duality

In the standard-form representation of an LP, what is the purpose of adding slack variables?

  1. To remove nonnegativity restrictions on the original variables
  2. To make the objective function linear
  3. To convert inequality constraints into equalities so that the simplex method can be applied Correct answer.
  4. To increase the number of decision variables in the original model

Explanation

Slack variables absorb the difference between the left and right sides of an inequality, turning it into an equation. This yields the equality-constrained standard form required by the simplex algorithm.

Question 50Linear Programming: Formulation, Geometry, and Duality

A primal LP has a redundant constraint that is never binding at any vertex. What is the effect on the dual?

  1. The dual variable associated with that constraint is zero in every optimal dual solution Correct answer.
  2. The dual objective increases without bound
  3. The dual becomes infeasible
  4. The dual constraint corresponding to that row is deleted

Explanation

By complementary slackness, a primal constraint with positive slack at optimum forces its dual variable to zero. A constraint that never binds has slack at every optimum, so the matching dual variable vanishes.