# Branch and Bound Implicit Enumeration

Use Implicit Enumeration to solve the following 0-1 IP.

MAX Z=3X1+X2+2X3-X4+X5

ST 2X1+X2-3X4<=1

X1+2X2-3X3-X4+2X5=>2

Xi=0 or 1

Please show enumeration tree. If a node is fathomed, indicate why it is fathomed. Provide the sequence of problems solved, eg. P1->P3->P4. Clearly indicate what the optimal solution is. Branch on x1 first.

I need to understand the process, so no LINGO solution or any other program please. Steps have to be done by hand.

© BrainMass Inc. brainmass.com October 25, 2018, 5:08 am ad1c9bdddfhttps://brainmass.com/math/algebra/branch-bound-implicit-enumeration-408365

#### Solution Preview

MAX Z=3X1+X2+2X3-X4+X5

ST 2X1+X2-3X4<=1

X1+2X2-3X3-X4+2X5=>2

Xi=0 or 1

Branch on x1

P1: x1=1

P2:x1=0

At P1 x1=1,

The subproblem is

MAX Z=3+x2+2x3-x4+x5

s.t.

2+x2-3x4<=1

1+2x2-3x3-x4+2x5>=2

Or

MAX Z=3+x2+2x3-x4+x5

s.t.

x2-3x4<= -1

2x2-3x3-x4+2x5>=1

By looking at the first constraint, x4 has to be 1, otherwise x2<=-1 is invalid, since x2=1 or 0.

So x4=1

Therefore

X2-3<=-1

2x2-3x3-1+2x5>=1

Or

X2<=2

2x2-3x3+2x5>=2

The first constraint is redundant, since x2= 1 or 0, both satisfying x2<=2.

By looking at the second ...

#### Solution Summary

The solution to Branch and bound with details are provided. Implicit Enumeration to solve the problem is provided.

Quantitative Methods

MULTIPLE CHOICE. Choose the one alternative that best completes the statement or answers the question.

1) A slack variable

A) exists for each variable in a linear programming problem.

B) is the difference between the left and right side of a constraint.

C) is the amount by which the left side of a ≥ constraint is larger than the right side.

D) is the amount by which the left side of a ≤ constraint is smaller than the right side.

2) The last step in solving a graphical linear programming model is

A) solve simultaneous equations at each corner point to find the solution values at each point.

B) plot the model constraints as equations on the graph and indicate the feasible solution area.

C) plot the objective function and move this line out from the origin to locate the optimal solution point.

D) plot the slack or surplus variables.

E) none of the above

3) Multiple optimal solutions provide ________ flexibility to the decision maker.

A) greater or equal B) greater

C) less or equal D) less

4) The ________ property of linear programming models indicates that the values of all the model parameters are known and are assumed to be constant.

A) additivity B) proportionality

C) certainty D) divisibility

5) Except satisfying the non-negativity constraint, a solution that satisfies all the other constraints of a linear programming problem is called

A) infeasible. B) optimal.

C) feasible. D) semi-feasible.

6) A shadow price reflects which of the following in a maximization problem?

A) the marginal cost of adding additional resources

B) the marginal gain in the objective that would be realized by subtracting one unit of a resource

C) the marginal gain in the objective that would be realized by adding one unit of a resource

D) none of the above

7) Mallory Furniture buys two products for resale: big shelves (B) and medium shelves (M). Each big shelf costs $500 and requires 100 cubic feet of storage space, and each medium shelf costs $300 and requires 90 cubic feet of storage space. The company has $75000 to invest in shelves this week, and the warehouse has 18000 cubic feet available for storage. Profit for each big shelf is $300 and for each medium shelf is $150. What is the objective function?

A) Z = $300B + $500M B) Z = $300M + $150B

C) Z = $300B + $150M D) Z = $500B + $300M

9) The owner of Chips etc. produces 2 kinds of chips: Lime (L) and Vinegar (V). He has a limited amount of the 3 ingredients used to produce these chips available for his next production run: 4800 ounces of salt, 9600 ounces of flour, and 200 ounces of herbs. A bag of Lime chips requires 2 ounces of salt, 6 ounces of flour, and 1 ounce of herbs to produce; while a bag of Vinegar chips requires 3 ounces of salt, 8 ounces of flour, and 2 ounces of salt. Profits for a bag of Lime chips are $0.40, and for a bag of Vinegar chips $0.50. For the production combination of 800 bags of Lime and 600 bags of Vinegar, which of the three resources is (are) not completely used?

A) salt only

B) flour only

C) herbs only

D) salt and flour

E) salt and herbs

10) The production manager for the Softy soft drink company is considering the production of 2 kinds of soft drinks: regular and diet. Two of her resources are constraint production time (8 hours = 480 minutes per day) and syrup (1 of her ingredient) limited to 675 gallons per day. To produce a regular case requires 2 minutes and 5 gallons of syrup, while a diet case needs 4 minutes and 3 gallons of syrup. Profits for regular soft drink are $3.00 per case and profits for diet soft drink are $2.00 per case. What is the optimal daily profit?

A) $270 B) $220 C) $520 D) $420 E) $320

11) Which of the choices below constitutes a simultaneous solution to these equations?

1. 3x + 2y = 6

2. 6x + 3y = 12

A) x = 1 / y = 0 B) x = 1 / y = 2

C) x = 0 / y = 2 D) x = 2 / y = 0

12) The solution to the linear programming relaxation of a minimization problem will always be ________ the value of the integer programming minimization problem.

A) greater than or equal to B) equal to

C) less than or equal to D) different than

13) The implicit enumeration method

A) cannot be used to solve linear programming models with multiple infeasible solutions.

B) eliminates obviously infeasible solutions and evaluates the remaining solutions to determine which one is optimal.

C) generates an optimal integer solution when no new constraints can be added to the relaxed linear programming model.

D) is used to solve a mixed integer linear programming model.

14) The linear programming relaxation contains the objective function and the original ________ of the integer programming problem but drops all integer restrictions.

A) constraints

B) decision variables

C) surplus variables

D) different variables

E) slack values

15) ________ is not a bit of information needed in the transportation model.

A) Capacity of the sources B) Demand of the destinations

C) Unit shipping costs D) Unit shipping distances

16) In the process of evaluating location alternatives, the transportation model method minimizes the

A) number of destinations. B) total demand.

C) total supply. D) total shipping cost.

17) A linear programming model consists of

A) constraints. B) an objective function.

C) decision variables. D) all of the above

18) Cully furniture buys two products for resale: big shelves (B) and medium shelves (M). Each big shelf costs $500 and requires 100 cubic feet of storage space, and each medium shelf costs $300 and requires 90 cubic feet of storage space. The company has $75000 to invest in shelves this week, and the warehouse has 18000 cubic feet available for storage. Profit for each big shelf is $300 and for each medium shelf is $150. Which of the following is not a feasible purchase combination?

A) 100 big shelves and 0 medium shelves

B) 0 big shelves and 200 medium shelves

C) 100 big shelves and 100 medium shelves

D) 150 big shelves and 0 medium shelves

E) 100 big shelves and 82 medium shelves

19) Mallory Furniture buys two products for resale: big shelves (B) and medium shelves (M). Each big shelf costs $500 and requires 100 cubic feet of storage space, and each medium shelf costs $300 and requires 90 cubic feet of storage space. The company has $75000 to invest in shelves this week, and the warehouse has 18000 cubic feet available for storage. Profit for each big shelf is $300 and for each medium shelf is $150. What is the weekly maximum profit?

A) $25000 B) $35000 C) $45000 D) $55000 E) $65000

20) The owner of Chips etc. produces 2 kinds of chips: Lime (L) and Vinegar (V). He has a limited amount of the 3 ingredients used to produce these chips available for his next production run: 4800 ounces of salt, 9600 ounces of flour, and 200 ounces of herbs. A bag of Lime chips requires 2 ounces of salt, 6 ounces of flour, and 1 ounce of herbs to produce; while a bag of Vinegar chips requires 3 ounces of salt, 8 ounces of flour, and 2 ounces of salt. Profits for a bag of Lime chips are $0.40, and for a bag of Vinegar chips $0.50. What is the objective function?

A) Z = $0.20L + $0.30V

B) Z = $0.40L + $0.50V

C) Z = $0.50L + $0.40V

D) Z = $2L + $3V

E) Z = $0.30L + $0.20V

21) Binary variables are

A) any negative integer value. B) any continuous value.

C) 0 or 1 only. D) any integer value.

22) In a balanced transportation model where supply equals demand

A) none of the constraints are equalities.

B) all constraints are equalities.

C) none of the constraints are inequalities.

D) all constraints are inequalities.

23) Which of the following statements is not true?

A) A feasible solution point does not have to lie on the boundary of the feasible solution.

B) An infeasible solution violates all constraints.

C) A feasible solution satisfies all constraints.

D) An optimal solution satisfies all constraints.

24) Which of the following could not be a linear programming problem constraint?

A) 4A + 7B + 2C + 9D ≤ 5 B) 3A + 21B > -2

C) 2A + 4B = 3 D) 12A + 9B ≤ 3

25) In a ________ integer model, the solution values of the decision variables are 0 or 1.

A) mixed B) 0-1

C) total D) all of the above

TRUE/FALSE. Write 'T' if the statement is true and 'F' if the statement is false.

26) In the graphical approach, once the feasible solution area and the optimal solution point have been determined from the graph, simultaneous equations are solved to determine the values of x1 and x2 at the solution point.

27) Linear programming is a model consisting of linear relationships representing a firm's decisions given an objective and resource constraints.

28) In a linear programming model, the number of constraints must be less than the number of decision variables.

29) Proportionality means the slope of a constraint or objective function line is not constant.

30) Linear programming models exhibit linearity among all constraint relationships and the objective function.

31) A change in the value of an objective function coefficient will always change the value of the optimal solution.

33) The output of a linear programming problem from a computer package regarding the values of decision variables will always be integer, and therefore, decision variable values never need to be rounded.

34) For a maximization problem, the range of feasibility for a resource is from 8 lb to 20 lb. Assume that the original amount of the resource available to the company is 12 lb, then it can be concluded that if up to 8 lb of this resource is added, neither the product mix nor the total profit will change.

35) Linear programming model of a media selection problem is used to determine the relative value of each advertising media.

36) A systematic approach to model formulation is to first construct the objective function before determining the decision variables.

37) Determining the production quantities of different products manufactured by a company based on resource constraints is a product mix linear programming problem.

38) The solution to the LP relaxation of a maximization integer linear program provides a lower bound for the value of the objective function.

39) The branch and bound solution method cannot be applied to 0-1 integer programming problems.

40) In a mixed integer model, some solution values for decision variables are integer and others can be non-integer.

41) In a transportation problem, items are allocated from sources to destinations at a minimum cost.

42) Non-negativity constraints restrict the decision variables to negative values.

43) The objective function is a linear relationship reflecting the objective of an operation.

45) In an unbalanced transportation model, supply equals demand such that all constraints are equalities.

46) In a transshipment problem, items may be transported from one destination to another.

47) The values of decision variables are continuous or divisible.

48) If we change the constraint quantity to a value outside the sensitivity range for that constraint quantity, the shadow price will not change.

49) A systematic approach to model formulation is to first define decision variables.

View Full Posting Details