Deck 5: Linear Programming: Sensitivity Analysis, Duality, and Specialized Models

Question 1

Sensitivity analysis answers "what if" questions to help the decision maker.

Answer 1

True

Question 2

Sensitivity analysis could be used to estimate the range of values of the objective function coefficient, taken one at a time, that would keep the current solution optimal.

Answer 2

True

Question 3

Sensitivity analysis could be used to estimate the range of values of the objective function coefficient, taken two at a time, that would keep the current solution optimal.

Answer 3

False

Question 4

Sensitivity analysis could be used to estimate the range of values of the right hand side, taken one at a time, that would keep the same variables as the current solution in the optimal solution (same variables basic) - though the magnitude of the variables may change.

Question 5

In a two-variable graphical linear program, if the coefficient of one of the variables in the objective function is changed (while the other remains fixed), then the slope of the objective function expression will change.

Question 6

In a two-variable graphical linear program, if the RHS of one of the constraints is changed (keeping all other things fixed), then the plot of the corresponding constraint will move in parallel to its old plot.

Question 7

In a two-variable graphical linear program, if the RHS of one of the constraints is changed (keeping all other things fixed), then the problem cannot become infeasible.

Question 8

In a two-variable graphical linear program, if the RHS of one of the constraints is increased (keeping all other things fixed), the plot of the line will move away from the origin.

Question 9

Sensitivity analysis could be used to estimate the range of values of the coefficient of the constraints, taken one at a time, that would keep the same variables as the current solution, in the optimal solution (same variables basic), though the magnitude of the variables may change.

Question 10

Sensitivity analysis could be used to estimate the range of values of the coefficient of the constraints, taken two at a time, that would keep the same variables as the current solution in the optimal solution (same variables basic) --though the magnitude of the variables may change.

Question 11

The value of 0 will always be included in any range produced by sensitivity analysis.

Question 12

The value of ${ }^{\infty}$ will always be included in any range produced by sensitivity analysis.

Question 13

The value of ${ }^{\infty}$ may be included as part of the range produced by sensitivity analysis in some problems.

Question 14

If a problem has a $\leq$ constraint with a positive RHS, then increasing the RHS would leave the optimal solution's objective function value the same or improve it (i.e. increase the objective function value corresponding to the optimal solution if it is a "maximize" objective function and decrease it if it is a "minimize" objective function).

Question 15

If a problem has a $\leq$ constraint with a positive RHS, then decreasing the RHS cannot improve (i.e. increase the objective function value corresponding to the optimal solution if it is a "maximize" objective function and decrease it if it is a "minimize" objective function) the objective function value.

Question 16

If a problem has a $\leq$ constraint with a positive RHS, and if that resource is fully utilized in the optimal solution, then the upper limit on the range using sensitivity analysis for that RHS will be ${ }^{\infty}$ .

Question 17

If a problem has a $\leq$ constraint with a positive RHS, and if that resource is not fully utilized in the optimal solution, then the upper limit on the range using sensitivity analysis for that RHS will be $\infty$ .

Question 18

In a two-variable linear programming problem, if the RHS corresponding to a binding constraint were to be increased, the value of the variables corresponding to the optimal solution would also change.

Question 19

In a two-variable linear programming problem, even if the RHS corresponding to a binding constraint were to be increased by a very large amount, it will always continue to be a binding constraint corresponding to the changed problem.

Question 20

Shadow price of a resource corresponding to a nonbinding constraint is always 0 .

Question 21

Shadow price of a resource corresponding to a binding constraint may be positive.

Question 22

Shadow price of a resource corresponding to a binding constraint may sometimes be 0 .

Question 23

Shadow price of resources corresponding to a binding constraint will not change even if the RHS corresponding to one of the binding constraints is changed, as long as the same constraints continue to be binding constraints.

Question 24

In a two-variable linear programming problem, a nonbinding constraint cannot become a binding constraint, even if the RHS of the nonbinding constraint is changed dramatically.

Question 25

The lower bound of the feasibility range of a nonbinding constraint is determined by decreasing the RHS of the constraint by the amount of surplus.

Question 26

In order to consider changes to the objective function coefficients and the RHS simultaneously, one can apply the $100 \%$ rule - total \% changes must be less than 100 - where negative change is also added without the negative sign.

Question 27

When considering simultaneous changes to the RHS of two or more constraints, we add up the \% change of each constraint without ignoring the sign. If the total is less than or equal to 100 , then the current variables will continue to be basic variables in the optimal solution.

Question 28

When considering simultaneous changes to the objective function coefficients of a linear program, if the sum of the absolute \% changes in the objective function coefficients is less than or equal to $100 \%$ , then the current solution will continue to be the optimal solution, though the value of the objective function may change.

Question 29

When considering simultaneous changes to the objective function coefficients of a linear program, if the sum of the absolute \% changes in the objective function coefficients is more than $100 \%$ , then the current solution will not be optimal.

Question 30

Every linear programming problem can have two forms, the original formulation (primal) and another form called dual.

Question 31

Since the solution to the primal problem also contains the solution to the dual problem, there is no need to study dual problems.

Question 32

In a linear program, even if RHS of constraint/s is/are changed with the range of feasibility, the shadow price of one or more resources may change.

Question 33

If the primal problem has maximize objective function with $\leq$ constraints and non-negative variables, the dual will have minimize objective function with $\geq$ constraints and strictly negative variables.

Question 34

If the primal problem has maximize objective function, non-negative variables, and 4 constraints, each of which is $\leq$ type, then the dual problem will have 4 variables and all of them will be non-negative.

Question 35

Any linear programming problem can be rewritten as an equivalent linear programming problem with maximize objective function, all $\leq$ constraints and non-negative variables.

Question 36

The dual formulation of a linear programming problem has a maximize objective function, all $\leq$ constraints and non-negative variables, and a minimize objective function, all $\geq$ constraints and nonnegative decision variables.

Question 37

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right), 3$ constraints (all $\leq$ type), and a maximize objective function $\left(Y_{i}\right.$ , where $i=1,2,3$ , respective to the dual variables associated with constraints 1,2 and 3 ),
Max: $250 X_{1}+500 X_{2}$
Constraints: $X_{1} \leq 320 \quad 2 X_{1}+5 X_{2} \leq 1100 \quad 1 X_{1}+1.2 X_{2} \leq 480$
Variables are non-negative
One of the constraints of the dual problem is

A) $0 Y_{1}+2 Y_{2}+1 Y_{3} \geq 250$
B) $1 Y_{1}+2 Y_{2}+1 Y_{3} \geq 250$
C) $1 Y_{1}+2 Y_{2}+1 Y_{3} \geq 320$
D) $0 Y_{1}+2 Y_{2}+1 Y_{3} \geq 500$

Question 38

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right), 3$ constraints (all $\leq$ type), and a maximize objective function $\left(Y_{i}\right.$ , where $i=1,2,3$ , respective to the dual variables associated with constraints 1,2 and 3),
Max: $250 X_{1}+500 X_{2}$
Constraints: $X_{1} \leq 320 \quad 2 X_{1}+5 X_{2} \leq 1100 \quad 1 X_{1}+1.2 X_{2} \leq 480$
Variables are non-negative one of the constraints of the dual problem is

A) $0 Y_{1}+2 Y_{2}+1.2 Y_{3} \geq 320$
B) $1 Y_{1}+2 Y_{2}+1 Y_{3} \geq 500$
C) $0 Y_{1}+5 Y_{2}+1.2 Y_{3} \geq 500$
D) $0 Y_{1}+5 Y_{2}+1.2 Y_{3} \geq 480$

Question 39

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , 3 constraints (all $\leq$ type), and a maximize objective function $\left(Y_{i}\right.$ , where $i=1,2,3$ , respective to the dual variables associated with constraints 1,2 and 3 ),
Max: $250 X_{1}+500 X_{2}$
Constraints: $X_{1} \leq 320 \quad 2 X_{1}+5 X_{2} \leq 1100 \quad 1 X_{1}+1.2 X_{2} \leq 480$
Variables are non-negative the objective function of the dual problem is

A) $\operatorname{Max}: 0 Y_{1}+2 Y_{2}+1 Y_{3}$
B) $\operatorname{Min}: 1 Y_{1}+2 Y_{2}+1 Y_{3}$
C) $\operatorname{Max}: 320 Y_{1}+1100 Y_{2}+480 Y_{3}$
D) $\operatorname{Min}: 320 Y_{1}+1100 Y_{2}+480 Y_{3}$

Question 40

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right), 3$ constraints (all $\leq$ type), and a maximize objective function $\left(Y_{i}\right.$ , where $i=1,2,3$ , respective to the dual variables associated with constraints 1,2 and 3 ),
Max: $250 X_{1}+500 X_{2}$
Constraints: $X_{1} \leq 320 \quad 2 X_{1}+5 X_{2} \leq 1100 \quad 1 X_{1}+1.2 X_{2} \leq 480$
Variables are non-negative the variables of the dual problem are required to be

A) strictly negative
B) non-negative
C) strictly positive
D) non-positive

Question 41

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $X_{2}$ ), find the range of values for the objective function coefficient of $X_{1}$ that will leave the current solution optimal (that is range of optimality or range of insignificance as the case may be) (hint: both constraints are binding)
Max: $100 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 104 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $[0,1000]$
B) $[-\infty, 1000]$
C) $[80,900]$
D) $[80,1000]$

Question 42

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of values for the objective function coefficient of $X_{2}$ that will leave the current solution optimal (that is range of optimality or range of insignificance as the case may be) (hint: both constraints are binding)
Max: $100 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 104 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $[20,250]$
B) $[-\infty, 250]$
C) $[0,250]$
D) $[20, \infty]$

Question 43

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of feasibility for the RHS of constraint 1 (hint: both constraints are binding)
Max: $100 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 104 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $[80,1000]$
B) $[30,150]$
C) $[12,150]$
D) $[12, \infty]$

Question 44

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of feasibility for the RHS of constraint 2 (hint: both constraints are binding) Max: $100 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 104 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $[52,780]$
B) $[62.4,90]$
C) $[52,62.4]$
D) $[62.4,780]$

Question 45

Shadow price of a resource corresponding to a binding constraint in a problem with maximize profit as its objective function

A) is also known as double price
B) is the additional profit obtained by having 1 more unit of the resource
C)is the additional profit obtained by having one more unit of the resource, as long as the additional
D) quantity is within the range of feasibility for the constraint
Dis the additional profit obtained by having one more unit of the resource, as long as the additional
E) quantity is within the range of optimality for the constraint

Question 46

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of values for the objective function coefficient of $X_{1}$ that will leave the current solution optimal (that is range of optimality or range of insignificance as the case may be) (hint: both constraints are not binding)
Max: $10 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 100 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $[-\infty, 1000]$
B) $[-\infty, 80]$
C) $[80, \infty]$
D) $[-\infty, \infty]$

Question 47

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of values for the objective function coefficient of $X_{2}$ that will leave the current solution optimal (that is range of optimality or range of insignificance as the case may be) (hint: both constraints are not binding)
Max: $10 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 100 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $[200, \infty]$
B) $[-\infty, 25]$
C) $[25, \infty]$
D) $[-\infty, \infty]$

Question 48

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of feasibility for the RHS of constraint 1 (hint: both constraints are not binding)
Max: $10 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 100 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $\left[150,{ }^{\infty}\right]$
B) $[-\infty, 150]$
C) $[0, \infty]$
D) $[0,150]$

Question 49

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of feasibility for the RHS of constraint 2 (hint: both constraints are not binding)
Max: $10 X_{1}+200 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 100 \quad 15 X_{1}+3 X_{2} \leq 90$
Variables are non-negative

A) $[60, \infty]$
B) $[-\infty, 60]$
C) $[60,150]$
D) $[0,60]$

Question 50

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ , find the range of feasibility for the RHS and range of values for the objective function coefficients that will leave the current solution optimal. You may use graphical method for your analysis, since the problem has only 2 decision variables
Max: $50 X_{1}+75 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 99 \quad 5 X_{1}+4 X_{2} \leq 120$
Variables are non-negative

Question 51

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ and the range of values for the objective function coefficients that will leave the current solution optimal, answer the question that follows
Max: $50 X_{1}+75 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 99 \quad 5 X_{1}+4 X_{2} \leq 120$
Variables are non-negative
Range of values of the objective function coefficients:
$30 \leq \mathrm{C} 1 \leq 93.75$
$40 \leq \mathrm{C} 2 \leq 125$
Suppose that $\mathrm{C} 1$ is changed to 60 and $\mathrm{C} 2$ is changed to 50 simultaneously, will the same solution remain optimal?

Question 52

Given the following linear programming problem with two non-negative variables $\left(X_{1}\right.$ and $\left.X_{2}\right)$ and given the range of feasibility for the RHS and range of values for the objective function coefficients that will leave the current solution optimal, answer the question that follows
Max: $50 X_{1}+75 X_{2}$
Constraints: $2 X_{1}+5 X_{2} \leq 99 \quad 5 X_{1}+4 X_{2} \leq 120$
Variables are non-negative
Range of values of the right hand side values analyzed below:
$48 \leq$ RHS $1 \leq 150$
$79.2 \leq$ RHS $2 \leq 247.5$
Suppose that the RHS1 is changed to 82 and RHS2 is changed to 140 simultaneously. Will the current solution be feasible? (same variables remain as basic variables)

Question 53

Wilkinson Auto Dealership sells standard automobiles and station wagons. The profit contribution for automobiles is $\$ 250.00$ per unit and $\$ 500.00$ per unit for station wagons. The company is planning the placement of orders with the manufacturer for next quarter. Orders for automobiles and station wagons can not exceed 320 and 160, respectively. Dealer preparation takes 2 hrs/auto and 5.0 hrs/wagon. They have 1100 hrs of preparation time next quarter. Autos take 1 unit of space, whereas wagons take 1.2 units of space. 480 units of space are available. In order to maintain some balance, the number of cars ordered should not be more than $150 \%$ the number of wagons ordered. Assume that they can sell all the autos and wagons they order for the quarter. The formulation of the problem is given below. Using excel-solver, completea sensitivity analysis of the objective function coefficients and report on the range of values of the coefficients that will leave the current solution optimal
find the range of feasibility for changes in the RHS of each constraint
Decision variables: Let $X_{1}$ be the number of automobiles and $X_{2}$ be the number of station wagons ordered next quarter.
Objective function: Max: $250 X_{1}+500 X_{2}$
Constraints: $X_{1} \leq 320 \quad X_{2} \leq 160 \quad 2 X_{1}+5 X_{2} \leq 1100 \quad 1 X_{1}+1.2 X_{2} \leq 480 \quad X_{1} \leq 1.5 X_{2}$
Variables are non-negative
Optimal solution using Solver: $X_{1}=206.25 \quad X_{2}=137.5$
The objective function value corresponding to the optimal solution is: $\$ 120.312 .50$

Question 54

Find the dual of the following problem:
PRIMAL:
Max: $2 X_{1}+4 X_{2}+5 X_{3}$
Subject to:
$$\begin{aligned}2 X_{1}+5 X_{2}+3 X_{3} \leq 3.0 \quad 2 X_{1}+4 X_{2}+1 X_{3} \leq 4.5 & X_{1} \geq 0 \\& X_{2} \geq 0 \\& X_{3} \geq 0\end{aligned}$$

Question 55

Find the dual of the following problem:
PRIMAL:
Max: $2 X_{1}+4 X_{2}+5 X_{3}$
Subject to:
$$\begin{array}{rrr}2 X_{1}+5 X_{2}+3 X_{3} \geq 3.0 \quad 2 X_{1}+4 X_{2}+1 X_{3} \leq 50 \quad 3 X_{1}+4 X_{2}+2 X_{3}=20 & X_{1} \geq 0 \\& X_{2} \geq 0 \\& X_{3} \geq 0\end{array}$$