Deck 22: Linear Programming: The Simplex Method

Question 1

Slack and surplus variables are used in simplex only for the solution of maximization problems.

Answer 1

False

Question 2

If there are seven less-than-or-equal constraints in a problem,the simplex table contains seven slack variables.

Answer 2

True

Question 3

For a maximization problem,the Z_j values in the body of the simplex table represent the gross profit given up by adding one unit of this variable into the current solution.

Answer 3

True

Question 4

A surplus variable is added to a constraint in order to create an equality,and represents a quantity of unused resource.

Question 5

In any linear programming problem,if a variable is to enter the solution,it must have a positive coefficient in the C_j - Z_j row.

Question 6

Artificial variables can be used in both maximization and minimization problems but are most often used in minimization problems.

Question 7

The constraint 5 X₁ + 6 X₂ ≤ 30,when converted to an = constraint for use in the simplex algorithm,will be 5 X₁ + 6 X₂ - S = 30.

Question 8

The constraint 5 X₁ + 6 X₂ = 30,when converted to an = constraint for use in the simplex algorithm,will be 5 X₁ + 6 X₂ - A = 30.

Question 9

In the simplex process,the new pivot row is found by dividing each number in the row by the pivot number.

Question 10

In linear programs with more than two decision variables,the area of feasible solutions is represented by an n-dimensional polyhedron.

Question 11

If all of a resource represented by a slack variable is used,that slack variable will not be in the production mix column of a linear programming simplex tableau.

Question 12

A correctly formulated linear program,when solved with the simplex algorithm,will always yield a single optimal solution.

Question 13

A basic feasible solution is a solution to a linear programming problem that corresponds to a corner point of the feasible region.

Question 14

In a maximization problem,if a variable is to enter the solution,it must have a positive coefficient in the C_j - Z_j row.

Question 15

Because slack variables yield no profit,they are not included in the objective function when creating the initial simplex tableau.

Question 16

A basic feasible solution to a system of n equations is found by setting n variables equal to 0 and solving for the other variables.

Question 17

A surplus variable is added to an = constraint in order to utilize the simplex algorithm.

Question 18

In a maximization problem,the C_j - Z_j row gives the net loss from introducing one unit of each variable into the solution.

Question 19

The constraint 5X₁ + 6X₂ ≥ 30,when converted to an = constraint for use in the simplex algorithm,will be 5 X₁ + 6 X₂ - S = 30.

Question 20

In linear programs with many variables,even though we cannot graph the feasible region,the optimal solution will still lie at a "corner point."

Question 21

How should the constraint,5X - 2Y ≥ 6,be converted into simplex tableau form?

A)5X - 2Y + S + A = 6
B)5X - 2Y - S + A = 6
C)5X - 2Y - S = 6
D)5X - 2Y + A = 6
E)5X - 2Y + S − A = 6

Question 22

Shadow prices are the positives of the numbers in the C_j - Z_j row's slack variable columns.

Question 23

If all the numbers in the pivot column are negative,this implies that the solution is unbounded.

Question 24

Consider the following general form of a linear programming problem: Maximize Profit
Subject to: Amount of resource A used ≤ 100 units
Amount of resource B used ≤ 240 units
Amount of resource C used ≤ 50 units
The shadow price for S₁ is 25,for S₂ is 0,and for S₃ is 40.If the right-hand side of constraint 3 were changed from 150 to 151,what would happen to maximum possible profit?

A)It would not change.
B)It would increase by 25.
C)It would decrease by 25.
D)It would increase by 40.
E)It would decrease by 40.

Question 25

An infeasible solution is indicated when all the C_j - Z_j row entries are of the proper sign to imply optimality,but an artificial variable remains in the solution.

Question 26

In a maximization problem,if a variable is to enter the solution,it must have a negative coefficient in the C_j - Z_j row.

Question 27

The numbers in the body of the simplex tableau can be thought of as substitution rates.

Question 28

As we are doing the ratio calculations for a simplex iteration,if there is a tie for the smallest ratio,the problem is degenerate.

Question 29

Which of the following is not true about slack variables in a simplex tableau?

A)They are used to convert ≤ constraint inequalities to equations.
B)They represent unused resources.
C)They require the addition of an artificial variable.
D)They may represent machine time,labor hours,or warehouse space.
E)They yield no profit.

Question 30

If,at an optimal solution,the C_j - Z_j value for a real variable that is not in the solution mix has a value of one,there are multiple optimal solutions.

Question 31

Dual variables represent the potential value of resources.

Question 32

In LP problems with more than two variables,the area of feasible solutions is known as an n-dimensional

A)pentagon.
B)cube.
C)octagon.
D)hydra.
E)polyhedron.

Question 33

The simplex method begins with an initial feasible solution in which all real variables are set equal to 0.

Question 34

The substitution rates give

A)the number of units of each basic variable that must be removed from the solution if a new variable is entered.
B)the gross profit or loss given up by adding one unit of a variable into the solution.
C)the net profit or loss that will result from introducing one unit of the variable indicated in that column into the solution.
D)the maximal value a variable can take on and still have all the constraints satisfied.
E)None of the above

Question 35

The dual problem formulation can be solved using the same simplex process used for the primal formulation.

Question 36

The shadow price is the value of one additional unit of a scarce resource.

Question 37

How does Karmarkar's Algorithm differ from the simplex method?

A)It follows a path of integer solutions.
B)It follows a path inside the feasible region.
C)It follows a counterclockwise path around the outside edges of the feasible region.
D)It follows a clockwise path around the outside edges of the feasible region.
E)It incorporates a second set of artificial variables.

Question 38

In 1984,who developed an alternative to the simplex algorithm,which often takes significantly less computer time to solve very large-scale LP problems?

A)Carmichael
B)Kruskev
C)Karmarkar
D)Krakov
E)Carpenter

Question 39

Sensitivity testing of basic variables involves reworking the initial simplex tableau.

Question 40

We can solve a minimization problem by maximizing the negative of the minimization problem's objective function.

Question 41

How should the constraint,5X - 2Y = 6,be converted into simplex tableau form?

A)5X - 2Y + A = 6
B)5X - 2Y - A = 6
C)5X - 2Y + A₁ - A₂ = 6
D)5X - 2Y + S = 6
E)5X - 2Y - S = 6

Question 42

Table M7-1
According to Table M7-1,all of the resources are being used.If the amount of resource A were changed from 64 to 65,then the maximum possible total profit would be

A)416.
B)417.
C)416.5.
D)415.5.
E)None of the above

Question 43

An artificial variable has no physical interpretation but

A)is added to each ≤ constraint to facilitate the simplex process.
B)is added to each ≥ constraint to facilitate the simplex process.
C)is added to each ≤ or = constraint to facilitate the simplex process.
D)is merely another manner of introducing a negative slack.
E)None of the above

Question 44

The C_j - Z_j row of a simplex tableau gives

A)the number of units of each basic variable that must be removed from the solution if a new variable is entered.
B)the gross profit or loss given up by adding one unit of a variable into the solution.
C)the net profit or loss that will result from introducing one unit of the variable indicated in that column into the solution.
D)the maximal value a variable can take on and still have all the constraints satisfied.
E)None of the above

Question 45

Table M7-2
According to Table M7-2,which is a summarized solution output from simplex analysis,the optimal solution to this problem is

A)X₁ = 0,X₂ = 16.667,S₁ = 300,S₂ = 0.
B)X₁ = 0,X₂ = 16.667,S₁ = 0,S₂ = 0.
C)X₁ = 12,X₂ = 30,S₁ = 0,S₂ = 0.625.
D)X₁ = 12,X₂ = 30,S₁ = 0.625,S₂ = 0.
E)None of the above

Question 46

Using the simplex method,we know we have an optimal solution when

A)all slack variables have a zero value.
B)all basic variables are negative.
C)all the real variables have a nonzero value.
D)all the artificial variables have a positive value.
E)None of the above

Question 47

If one changes the contribution rates in the objective function of an LP problem,

A)the feasible region will change.
B)the slope of the iso-profit or iso-cost line will change.
C)the optimal solution to the LP will no longer be optimal.
D)All of the above
E)None of the above

Question 48

Table M7-2
According to Table M7-2,which is a summarized solution output from simplex analysis,if the amount of resource A were decreased so that there were only 550 units available instead of 600,what would happen to total profits?

A)They would decrease.
B)They would increase.
C)They would not change.
D)Unable to determine from the given information.
E)None of the above

Question 49

A slack variable

A)is added to each ≤ constraint to facilitate the simplex process.
B)is added to each ≥ constraint to facilitate the simplex process.
C)is added to each ≤ or = constraint to facilitate the simplex process.
D)is added to each = constraint to facilitate the simplex process.
E)None of the above

Question 50

The number -2 in the X₂ column and X₁ row of a simplex tableau implies that

A)if 1 unit of X₂ is added to the solution,X₁ will decrease by 2.
B)if 1 unit of X₁ is added to the solution,X₂ will decrease by 2.
C)if 1 unit of X₂ is added to the solution,X₁ will increase by 2.
D)if 1 unit of X₁ is added to the solution,X₂ will increase by 2.
E)None of the above

Question 51

Which of the following is not true of artificial variables?

A)They have no meaning in a physical sense-nothing more than a computational tool.
B)In all linear programs,they appear in the objective function with a very low cost ($M).
C)They are usually used with ≥ constraints.
D)They are usually used with = constraints.
E)None of the above

Question 52

Shadow prices represent

A)the value of one additional unit of a basic variable.
B)the value of one less unit of a basic variable.
C)the value of one less unit of a specific resource.
D)the value of one additional unit of a specific resource.
E)None of the above

Question 53

The substitution rates

A)decrease with each iteration of the simplex method.
B)tell us the number of units of a basic variable that must be removed from the solution for another variable to enter the basis.
C)tell the amount of one resource that can be substituted for another.
D)tell us the amount of a resource that must be used to gain another unit of profit.
E)None of the above

Question 54

Shadow prices

A)can be derived from the coefficients of the slack variables in the C_j - Z_j row of an optimal simplex tableau.
B)represent the value of one additional unit of a resource.
C)are found in the solution to the dual LP.
D)All of the above
E)None of the above

Question 55

Consider the following linear programming problem: Maximize 40 X₁ + 30 X₂ + 60X₃
Subject to: X₁ + X₂ + X₃ ≥ 90
12 X₁ + 8 X₂ + 10 X₃ ≤ 1500
X₁ = 20
X₃ ≤ 100
X₁ ,X₂ ,X₃ ≥ 0
How many slack,surplus,and artificial variables would be necessary if the simplex algorithm were used to solve this problem?

A)3 slack,6 surplus,and 6 artificial
B)2 slack,1 surplus,and 2 artificial
C)1 slack,2 surplus,and 2 artificial
D)1 slack,2 surplus,and 1 artificial
E)None of the above

Question 56

Table M7-1
According to Table M7-1,it is currently profitable to produce some units of X₁ and the current profit per unit of X₁ is $20.What is the lowest value that this could be to allow this variable to remain in the basis?

A)8
B)16
C)20
D)30
E)None of the above

Question 57

If one changes a nonbasic objective function coefficient,the optimal solution of a maximization problem will remain optimal if

A)the increase in the coefficient does not exceed the value of the Z_j associated with that nonbasic variable.
B)the increase in the coefficient does not exceed the values of the Z_j's of every basic variable.
C)the decrease in the coefficient does not exceed the value of the Z_j associated with the nonbasic variable.
D)the new C_j - Z_j associated with the nonbasic variable remains positive.
E)None of the above

Question 58

Consider the following linear programming problem: Maximize 40 X₁ + 30 X₂ + 60X₃
Subject to: X₁ + X₂ + X₃ ≥ 90
12 X₁ + 8 X₂ + 10 X₃ ≤ 1500
X₁ ,X₂ ,X₃ ≥ 0
How many slack,surplus,and artificial variables would be necessary if the simplex were used to solve this problem?

A)3 slack,3 surplus,and 3 artificial
B)1 slack,2 surplus,and 2 artificial
C)1 slack,4 surplus,and 4 artificial
D)1 slack,1 surplus,and 1 artificial
E)None of the above

Question 59

Which of the following is true about surplus variables in a simplex tableau?

A)They are used to convert ≤ constraint inequalities to equations.
B)They require the addition of an artificial variable.
C)They represent unused resources.
D)They should be added to the left-hand side of the equation.
E)They yield a positive profit.

Question 60

Table M7-1
According to Table M7-1,all of the resources are being used.If the amount of resource B were changed from 96 to 97,then the maximum possible total profit would be

A)416.
B)417.
C)419.
D)420.
E)None of the above

Question 61

Nonbasic variables in the simplex method of linear programming are

A)variables in the solution mix.
B)variables not in the solution mix.
C)the real variables in the initial solution.
D)the slack variables in the optimum solution.
E)always the slack,surplus,and artificial variables.

Question 62

Sensitivity analysis cannot be used to examine the effects of

A)changes in the contribution rates for each variable.
B)changes in the technological coefficients.
C)changes in the available resources.
D)the addition or deletion of a constraint.
E)None of the above

Question 63

In applying the simplex solution procedure to a maximization problem to determine which variable enters the solution mix,

A)pick the one with the largest positive C_j - Z_j.
B)pick the one with the smallest C_j - Z_j.
C)pick the one with the largest C_j.
D)pick the one with the smallest Z_j.
E)pick the smallest nonnegative number formed by dividing each amount in the quantity column by the appropriate column at the exiting variable.

Question 64

Table M7-3
According to Table M7-3,which is the final simplex tableau for a problem with two variables and two constraints,what is the maximum possible profit (objective function value)for this problem?

A)20
B)40
C)800
D)26.667
E)None of the above

Question 65

If,in the final optimal simplex tableau,the C_j - Z_j value for a nonbasic variable is zero,this implies

A)infeasibility.
B)unboundedness.
C)degeneracy.
D)alternate optimal solutions.
E)None of the above

Question 66

If,in the optimal tableau of a linear programming problem,an artificial variable is present in the solution mix,this implies

A)infeasibility.
B)unboundedness.
C)degeneracy.
D)alternate optimal solutions.
E)a finite optimal solution.

Question 67

Sensitivity analysis may be used to

A)experiment with possible future changes in the firm that may affect profits.
B)determine whether a corner point of the feasible region actually yields optimal profit.
C)replace the simplex method.
D)reduce the number of variables in a complex LP problem.
E)solve LP problems that require solutions only in whole numbers.

Question 68

Table M7-3
According to Table M7-3,which is the final simplex tableau for a linear programming problem (maximization),what would happen to profits if the X₁ column were selected as the pivot column and another iteration of the simplex algorithm were performed?

A)Total profits would increase.
B)Total profits would decrease.
C)An infeasible solution would be found.
D)Another optimal solution would be found.
E)None of the above

Question 69

For every primal

A)that is a maximization problem,the dual is a minimization problem.
B)the right-hand side quantities become the dual's objective function coefficients.
C)constraint inequality signs are reversed in the dual.
D)the transpose of the constraint coefficients become the dual's constraint coefficients.
E)All of the above

Question 70

Table M7-3
According to Table M7-3,which is the final simplex tableau for a problem with two variables and two constraints,the 0.667 in the X₁ column means that

A)to produce 1 unit of X₁,0.667 units of X₂ must be given up.
B)to produce 1 unit of X₂,0.667 units of X₁ must be given up.
C)if 1 unit of X₁ is produced,profits on X₂ will decrease by 0.667.
D)if 1 unit of X₁ is produced,profits on X₂ will increase by 0.667.
E)None of the above

Question 71

In applying the simplex solution procedure to a minimization problem to determine which variable enters the solution mix,

A)pick the one with the most positive C_j - Z_j.
B)pick the one with the largest C_j.
C)pick the one with the smallest Z_j.
D)pick the one with the most negative C_j - Z_j.
E)pick the smallest nonnegative number formed by dividing each amount in the quantity column by the appropriate column at the exiting variable.

Question 72

In solving a linear programming minimization problem using the simplex method,

A)every time an artificial variable is added,a surplus variable must also be added.
B)every time an artificial variable is added,a surplus variable must be subtracted.
C)every time a surplus variable is added,an artificial variable must be added.
D)every time a surplus variable is added,an artificial variable must be subtracted.
E)every time a surplus variable is subtracted,an artificial variable must be added.

Question 73

Sensitivity analyses are used to examine the effects of changes in

A)contribution rates for each variable.
B)technological coefficients.
C)available resources.
D)All of the above
E)None of the above

Question 74

Table M7-3
According to Table M7-3,which is the final simplex tableau for a problem with two variables and two constraints,what are the values for all the variables in this solution?

A)X₁ = 20,X₂ = 40,S₁ = 0,S₂ = 0
B)X₁ = 0,X₂ = 40,S₁ = 0,S₂ = 40
C)X₁ = 0,X₂ = 20,S₁ = 0,S₂ = 40
D)X₁ = 0,X₂ = 0,S₁ = 0,S₂ = 0
E)None of the above

Question 75

The dual of a linear programming problem

A)always exists.
B)may be easier to solve.
C)may contain economic information useful to management.
D)while equivalent,is derived through an alternative procedure.
E)All of the above

Question 76

Variables in the solution mix are called

A)standard.
B)surplus.
C)real.
D)revealed.
E)basic.

Question 77

Table M7-3
According to Table M7-3,which is the final simplex tableau for a problem with two variables and two constraints,what can be said about the optimal solution and the constraints?

A)There is slack remaining in the first constraint.
B)There is slack remaining in the second constraint.
C)There is slack remaining in both constraints.
D)There is no slack remaining in either constraint.
E)None of the above

Question 78

Right-hand side ranging

A)tells us the number of units of a constraint that may be added or subtracted without changing the profit (objective function value).
B)requires computation of the dual before being accomplished.
C)is a method to find the range over which shadow prices remain constant.
D)All of the above
E)None of the above

Question 79

The solution to the dual LP problem

A)can always be derived by examining the Z_j row of the primal's optimal simplex tableau.
B)is better than the solution to the primal.
C)presents the marginal profits of each additional unit of a resource.
D)All of the above
E)None of the above

Question 80

A solved LP problem indicated that the optimal solution was X₁ = 5,X₂ = 10,A₁ = 40.The first constraint was: 4X₁ + 2X₂ ≥ 80.This solution is:

A)indeterminant.
B)degenerate.
C)infeasible.
D)unbounded.
E)None of the above