IEOPER1 Quiz 3 Flashcards
In the optimal solution to a linear program, there are 20 units of slack for a constraint. From this, we know that:
A. The dual price for this constraint is 20
B. The problem must be a maximization problem
C. The constraint must be redundant
D. The dual price for this constraint is 0.
D. The dual price for this constraint is 0
Which of the following statements is true?
A. If a constraint is non-binding then its LHS is greater than its RHS
B. An equality constraint is always nonbinding
C. Changes to an objective function coefficient will not affect the size of the feasible region.
C. Changes to an objective function coefficient will not affect the size of the feasible region
The report which shows the final values of the decision variables, the objective function, and the formula, slack or surplus, status, and LHS value for each constraint is the ____________.
Answer Report
A linear program has been solved and sensitivity analysis has been
performed. The ranges for the objective function coefficients have been found. For the profit on X1, the upper bound is 80, the lower bound is 60, and the current value is 75. Which of the following must be true if the profit on this variable is lowered to 70 and the optimal solution is found?
A. The values for all the decision variables will remain the same
B. The maximum possible total profit may increase
C. A new corner point will become optimal
A. The values for all the decision variables will remain the same
Suppose that a MAX problem contained the following constraint: 5x + 8y ≤ 40. Then which of the following statements is true?
A. For the point (8,5), the slack for this constraint would have a value of 40
B. For the point (4,2), the slack for this constraint would be zero
C. For the point (4,2.5), the slack for this constraint would be a positive value.
D. For the point (1,4), the slack for this constraint would have a value of 3.
D. For the point (1,4), the slack for this constraint would have a value of 3.
Given the following linear programming problem with two non-negative variables X and X and 3 constraints all of which are type, and a maximize objective function and assuming Y, i = 1, 2, 3 as the dual variables associated with constraints 1, 2 and 3 respectively, the dual constraints in the dual problem is:
Max: 250X1 + 500 X2
Constraints:
X1 <= 320
2X1 + 5X2 <= 1100
x1 + 1.2 X2 <= 480
Y1 + 2Y2 + Y3 >= 250
5Y2 + 1.2 Y3 >= 500
Any change in the values for the RHS (Right Hand Side) of a binding
the constraint of an LP problem will
A. Not change the feasibility region
B. Change the slope of that constraint
C. Not change the slope of the constraint but move it parallel to the original
D. Change the slope of the objective function
C. Not change the slope of the constraint but move it parallel to the original
Consider a scenario with an objective function Minimize $14X + $17Y. Assume that the value of X in the optimal solution is zero and the reduced cost for variable X is $3. At what objective function coefficient will X first become part of the optimal solution?
A. 14
B. 17
C. 20
D. 11
D. 11
The options under Solver in Excel that should always be checked (turned
on) for the general LP problem are the following:
A. Only ‘Assume Linear Model’
B. Both ‘Assume Linear Model’ and ‘Assume Non-Negative’
C. Only ‘Assume Non-Negative’
D. Neither ‘Assume Linear Model’ nor ‘Assume Non-Negative’
B. Both ‘Assume Linear Model’ and ‘Assume Non-Negative’
Which of the following would cause a change in the feasible region?
A. Increasing an objective function coefficient in a maximization problem
B. Increasing an objective function coefficient in a minimization problem
C. Changing the right-hand side of a non-redundant constraint
D. Adding a redundant constraint
C. Changing the right-hand side of a non-redundant constraint
Modified True or False. The (symmetric) form of a primal LP model is needed to formulate its dual model whereas the (standard form) is needed to begin the solution process
True
Modified True or False. The addition of a new constraint to an existing LP model after an optimal solution has already been determined (will cause the current optimal solution to become superoptimal)
False. introducing a new constraint can at most maintain or reduce current optimal value, but it cannot improve beyond the original optimal solution
In RHS ranging (shortcut method), if all ratios are negative then there is _________.
No upper limit
In RHS ranging (shortcut method), if all ratios are positive then there is _________.
No lower limit
For the dual simplex method, how is the EV chosen?
Max: Smallest absolute value of the ratio
Min: Smallest ratio
For the dual simplex method, in getting the ratios, ____________ denominator values and _______ do not qualify as an entering variable.
Positive denominator values and zero
Formula for Shadow Price
Change of Z / Change of b
If the problem changes the b value, the vectors affected are _____________.
XB and Z
For OFC ranging, the criterion for maximization problems is _______________
CB(B^-1N)- CN >= 0
For OFC ranging, the criterion for minimization problems is _______________
CB(B^-1N)- CN <= 0
In OFC Ranging (Shortcut Method) for basic variables, u represents __________ and v represents __________.
u = least negative ratio
V = least positive ratio
In RHS Ranging (Shortcut Method), x represents __________ and y represents __________.
x = least negative ratio
y = least positive ratio
In OFC Ranging (Shortcut Method) for basic variables, the ratio is determined by ____________
-g/h; wherein
g = optimal CB (B^-1N) - CN
h = kth row of optimal B^-1N
In RHS Ranging (Shortcut Method), the ratio is determined by ____________
-e/c; wherein
e = present optimal solution (XB)
c = ith column of B^-1
In OFC Ranging (Shortcut Method) for basic variables, if all ratios are negative then ____________
There will be no upper limit
In OFC Ranging (Shortcut Method) for basic variables, if all ratios are positive then ____________
There will be no lower limit
In RHS Ranging (Shortcut Method), if the divisor of the ratio is 0 then ____________
Treat all divisions by zero as positive infinity before determining the y (least positive ratio)
In OFC Ranging (Shortcut Method) for basic variables, enumerate the relationships of hk (+/-) and the type of problem (max/ min) if there is a 0 ratio (g=0)
Max and +hk; u=0
Min and +hk; v=0
Max and -hk; v=0
Min and -hk, u=0
In OFC Ranging (Shortcut Method) for NBVs, it follows that the range is __________ for a max problem and ___________ for a min problem.
Max: -inf <= Cj <= Cjo + g
Min: Cjo + g <= Cj <= +inf
wherein g = corresponding element in the optimal CB(B^-1N) - CN
Modified True or False. According to the complementary slackness theorem, the associated resource of any two constraints which have slack in the optimal solution must have identical, (non-zero shadow price).
False. According to the complementary slackness theorem, the associated resource of any constraint that has slack in the optimal solution must have a zero shadow price.
Modified True or False. If the standard LP primal model has a minimization objective with ≤ constraints, then its dual model should have a (maximization objective with ≥ constraints)
True (based on copilot)
Modified True or False. The addition of a new variable to an existing LP model after an optimal solution has already been determined (increases the number of basic variables in the optimal iteration of the model).
False. The number of basic variables is determined by the number of constraints in the model, not the number of variables.
Modified True or False. The change in the optimal objective function value per unit decrease in a constraint’s right-hand side value is given by the (negative of the shadow price for that constraint).
True
Modified True or False. The (dual simplex method) is used to solve for the new optimal solution if an objective function coefficient is changed beyond its allowable range of values.
False. Revised simplex method
Modified True or False. Changing the right-hand side value of a constraint will (definitely change the optimal value of the objective function).
False. It may potentially change depending on the constraints (ex. binding constraints) but it may also remain the same (ex. non-binding constraints)
Modified True or False. If a particular constraint for a dual LP model is binding at optimum, then (the corresponding primal decision variable will be non-basic at optimum).
False. (idk what reason yet here)
Modified True or False. When a primal LP problem has a superoptimal solution, (the corresponding dual solution will be superoptimal).
False. The dual solution will be sub-optimal
Modified True or False. If a constraint for a primal LP model is not binding at optimum, then (the optimal value of the corresponding dual variable will be zero).
True
Modified True or False. The Optimality Criterion Theorem states that (if there exists a solution for both primal and dual such that the corresponding values of their objective functions are equal), then this solution is in fact the optimal solution to their respective problems.
False (based on OT)
Modified True or False. Changing the objective function coefficient (OFC) of a non-basic variable (will not change the current optimal value of the objective function as long as the change in the OFC is within the allowable OFC range).
True
Modified True or False. If the right-hand side value (b) of a constraint is changed, the present basic optimal solution mix may or may not change depending on its RHS range, but any increase or decrease in the value of b will (definitely affect the optimal value of the objective function).
False. it depends on whether the constraint is binding (copilot)
Modified True or False. When the iteration of a primal problem is sub-optimal, the corresponding iteration of the dual problem is superoptimal (regardless of solution methodology used).
False. A sub-optimal iteration in the primal problem typically corresponds to a sub-optimal iteration in the dual problem. (copilot)
Modified True or False. Changing the objective function coefficient (OFC) of a basic variable (will not change the current optimal value of Z as long as the change in the OFC is within the allowable OFC range).
False (based on OT)
Modified True or False. The number of equality constraints in the primal is (the same) as the number of unrestricted variables in the dual, and the number of unrestricted variables in the primal is (the same) as the number of equality constraints in the dual
True
Modified True or False. The symmetric form of a primal LP model is (needed to solve its dual model).
False. The symmetric form is needed to covert the primal model to a dual model using the established relationships
Modified True or False. The dual simplex method is used to (solve for the optimal solution of dual LP models).
False. It’s used to solve for the optimal solution coming from a superoptimal solution (could be applied to both primal and dual models)
Modified True or False. If the number of primal variables is much smaller than the number of primal constraints, it is (less efficient) to obtain the solution of the primal by solving its dual
False. More efficient
Enumerate the three duality theorems
Weak Duality Theorem
Optimality Criterion Theorem
Complementary Slackness Theorem
The objective function value of the dual is always >= to the objective function value of the primal for any feasible solution
Weak Duality Theorem
WEAK DUALITY THEOREM: COROLLARY 1
The maximum value for the objective
the function of the primal is a ______ bound for the objective function value of the dual.
Lower
WEAK DUALITY THEOREM: COROLLARY 2
If the primal is feasible and unbounded,
then the dual has ______________.
No feasible solution
WEAK DUALITY THEOREM: COROLLARY 3
If the dual is feasible and unbounded,
then the primal has ________________.
No feasible solution
If there exists feasible solutions such that
the objective function value of the primal and the objective function value of the dual are equal, then these feasible solutions are in fact optimal solutions to their respective problems.
THEOREM 2: OPTIMALITY CRITERION
THEOREM
For every basic solution of the primal, there is a corresponding complementary basic solution for the dual with the complementary slackness relationship. This relationship happens wherein the primal variable is basic and the dual variable becomes non-basic and vice versa.
THEOREM 3: COMPLEMENTARY
SLACKNESS THEOREM
In order to use the dual simplex method, the initial solution must be ___________ and must _____________.
Infeasible and must satisfy optimality conditions
If the slack variable is _______ at optimum, then the shadow price of the resource is 0
Basic
If the slack variable is _______ at optimum, then the shadow price of the resource associated with the slack variables should be positive
Non-basic (value is found at CB*B^-1N-CN)
When adding a new variable, if the solution remains optimal, then it means that _____________
The addition of a new variable/product has no value
When adding a new constraint, you have to check if ______________
The current basic variable values will satisfy the constraint
