1
Chris Guzman
IE 416
Dr. Parisay’s comments are in red.
Refer to the assigned problem to your group in this link. Each member of the group should do the homework individually.
Page 93, Problem 8: branch on “X1” and then “X2”
a) Using LP option of WinQSB and creating the branch-and-bound tree up to two levels as assigned. Document input and output for each subproblem. If after the first branching, you get integer value for the second branching, then use another variable to branch on. You need to demonstrate two levels of branching. Create the Branch and Bound tree with as much info on it as possible. Print screen input and output for each node of the tree.
b) Using ILP option of WinQSB solve the problem.
Problem Statement:
Highland’s TV-Radio Store must determine how many TVs and radios to keep in stock. A TV requires 10 sq ft of floorspace, whereas a radio requires 4 sq ft; 200 sq ft of floorspace is available. A TV will earn Higland $60 in profits, and a radio will earn $20. The store stocks only TVs and radios. Marketing requirements dictate that at least 60% of all appliances in stock be radios. Finally, a TV ties up $200 in capital, and a radio, $50. Highland wants to have at most $3000 worth of capital tied up at any time. Create a branch and bound tree up to two levels first branching on TVs and than branching on radios.
Table 1:Summary
Item / Decision Variables / Floorspace / Profit / Capital / RequirementTV / X1 / 10 / 60 / 200
Radio / X2 / 4 / 20 / 50 / 60%
Max / <=200 sq ft / <=3000
O.F.: / Maximize profit for Highland Tv-Radio Store
Max Z= 60X1 + 20X2
Constraints
Space / 10X1 + 4X2 ≤ 200
Capital / 200X1 + 50X2 ≤ 3000
Requirement / X2/(X1+X2)≥ 0.6
Steps to Follow
1 / Notice you have to variables to assign in this problem since you will only deal with TV's and Radios
2 / TV's and Radios are constrained by the max floor space and max capital
3 / Radios need to be 60% of stock
Take this key information from the problem you should be able to solve the for the max profit
- All variables are positive amounts X1 and X2 >=0
Solution from LP and step by step Branch and Bound:
Table 2:Input LP relaxation problem:
Table 3: Solution Summary for Original LP:
Branch Out On TVs
Table 4: Input added TV =< 6
Table 5: Solution Summary for Table 4 TV <= 6:
Table 6: Input added TV => 7
Table 7: Solution Summary for Table 6 TV >= 7
Branch and Bound Tree for X1 the TVs
Notice that you have obtained integer values for variables in both branches. So both are candidate nodes and cannot branch out any further. Also, the Z value for both nodes 2 and 3 are the same. That is both are optimal solution. There exists a multi-optimal solution.
Now let’s try from the beginning and to branch from X2 which is the radios, first the following input and output tables exist.
Table 2:Input LP relaxation ILP:
Table 3: Solution Summary for Original LP:
Branch Out On radios
Table 8: Inputadded Radio =< 33
Table 9: Solution Summary for Table 8 Radio <= 33
Table 10: Input added Radio >= 34
Table 11: Solution Summary for Table 10 Radio >= 34
Table 12: Input added Radio <= 33 TV <= 6
Table 13: Solution Summary for Table 12 Radio <= 33 TV <= 6
Table 14: Input added Radio <= 33 TV >= 7
Table 15: Solution Summary for Table 14 Radio <= 33 TV >= 7
Table 16: Input added Radio >= 34 TV <= 6
Table 17: Solution Summary for Table 16 Radio >= 34 TV <= 6
Table 18: Input added Radio >= 34 TV >= 7
Table 19: Solution Summary for Table 18 Radio >= 34 TV >= 7
Branch and Bound Tree for X2 the Radios
Notice that Node 4 is a candidate node, but its Z value is less than the others therefore cannot be optimal solution. Here again you have two Nodes 5 and 6 that are optimal solution. These are the same as the other two optimal solutions. You have a total of 2 optimal solutions as below:
Z= 1060
X1: TV / X2: Radio7 / 32
6 / 35
Part B: ILP for Problem 8 pg 93.
Input Table for ILP:
Solution Summary for Input Table with ILP:
Notice you have obtained only one optimal solution here.