ISE 421 Operations Research 2 Exam 1 Sample
- Consider the integer model:
The optimal tableau associated with the relaxed model is
Basic x1 x2 s1 s2 Solution z 0 0 1 1/4 3/4 41 1/4 x2 0 1 2 1/4 -1/4 2 1/4 x1 1 0 -1 1/4 1/4 3 3/4 The slack variables s1 and s2 are associated with the first and the second constraints. Illustrate how the branch and bound method is applied by performing two iterations of the method.
- In a factory, the industrial engineer is planning the production of a new order of products. The production process consists of 5 operations performed on 4 machines. The first and the last operations are performed on machine 1. However, the setup time of a specific machine is influenced by the type of machine that comes before it. The setup times matrix are as shown below:
The machine before it Machine 1 2 3 4 1 - 10 5 7 2 4 - 3 8 3 3 9 - 5 4 7 7 2 - For example, if machine 1 comes before machine 2, then the setup time is 4 minutes. Show how this problem can be formulated as the traveling salesman problem and write the model.
- Consider an integer LP with the maximization objective
function. The partially explored solution tree of the branch and
bound algorithm is shown below. The number below each node is the
value of the objective function for the LP defined by that node. If
the current best integer solution is z = 13. Which of these nodes
would be considered for further exploration and which will be
considered as non-promising?
- Take the mixed integer LP model
Note that x1 is integer and x2 is continuous.
The optimal tableau for the dual problem is
Basic y1 y2 y3 y4 Solution w 0 0 3 1/3 2/3 10 2/3 y1 1 0 1/3 -1/3 2/3 y2 0 1 1/3 2/3 1 2/3 The dual variables y3 and y4 are slack variables associated with the first and second dual constraints.
Use branch and bound algorithm to solve the mixed integer LP model.
Instructor: Dr Muhammad Al-Salamah