Question

question:

Objective function: Zmax = 6X1 + 10X2

LIMITS: 3X1 + 6X2 ≤ 24
And 5X1 + 6X2 ≤ 30
X1, X2 ≥ 0 and integer (integer)

Apply the following to the question above.
a. Branch-bound algorithm
b. (0-1) Integer programming
c. Gomory cutting plane

Answer 1

We are given

Z = 6x1 + 10x2 subject to the constraints

3x1 + 6x2<=24 (GREEN LINE)

, 5x1 + 6x2<=30 (RED LINE)

18and both x1 and x2 are greater than zero

so assuming x1 = 0 in 1st constraint we get (x1,x2) = (0,4)

assuming x2 = 0 in 1st constraint we get (x1,x2) = (8,0)

assuming x1 = 0 in 2nd constraint we get (x1,x2) = (0,5)

assuming x2 = 0 in 2nd constraint we get (x1,x2) = (6,0)

So we plot a graph with the points (0,4), (8,0) - green line , (0,5) and (6,0) red line, and see that the orange part is our feasible region

The meeting point of the green and red line is defined by the solution point of both constraints

So initially solve for x1 and x2 assuming them as equation i.e solve for 3x1 + 6x2=24, 5x1 + 6x2=30, we get x1 = 3, x2 = 2.5, so the meeting point of the lines is i.e b is (3,2.5)

We can find the value of our objective function at all four points a,b,c,d

Z value at a (i.e 0,4) = 40

Z value at b(i.e 3,2.5) = 43

Z value at c (i.e 6,0) = 36

Z value at d (o,o) = 0

So our Zmax = 43 and this happens when (x1,x2) = (3,2.5) - but x2 is not an integer, so this is not an optimal solution, so we need to do branching on x2

So add the new constratints x2<=2 and x2>=3 into the main problem

So we have Sub-Problem 1

Z = 6x1 + 10x2 subject to the constraints

3x1 + 6x2<=24, 5x1 + 6x2<=30, and both x1 and x2 are greater than zero, x2< =2

So we have Sub-Problem 2

Z = 6x1 + 10x2 subject to the constraints 3x1 + 6x2<=24, 5x1 + 6x2<=30, and both x1 and x2 are greater than zero, x2>=3

So set up graphs for sub-problem 1 and sub-problem 2 we have

Check the solution at Point P1 and P2, these are the optimum points

Point P1 is (3.6,2) and Point P2 is (2,3), so we have Z value at P1 = 80 and Z value at P2 = 42

So Z max happens at (3.6,2) but again here x1 is not an integer

so again create two new sub problems, with two new constraints x1<=3 and x1>=4, so we have

for sub-problem 1, point p1 is (3,2) and Z value = 38

for sub-problem 2, point p2 = (3.6,2) and Z value = 80 and point p3 is (4,1.666) and Z value = 41.667

so again Z max is at point p2 i.e at (3.6,2) so now we reach the same iteration as before

So from the graphs it is clear that the highest value of x1 is 3, and the highest integer value of x2 = 2

So solution is (3,2) and Z max value is 32

=======================================================================================

I ran out of time, could not do part c).

Kindly repost only that part as a new question and I will solve it

Please rate thumbsup if you like my work as it encourages us to keep learning more and providing quality solutions