1. Consider the following linear program:

Maximize z = 2XI + X2 subject to ble, Xl + X2 :5 3 o:5 Xl :5 2, 0 :5 X2 :5 2

(a) Solve the problem graphically, and trace the sequence of extreme points leading to the optimal solution. (You may use TORA.)

(b) Solve the problem by the upper-bounding algorithm and show that the method produces the same sequence of extreme points as in the graphical optimal solution (you may use TORA to generate the iterations).

(c) How does the upper-bounding algorithm recognize the extreme points?