Scribd
Upload
13 views

Integer Linear Programming

this is my second document

Uploaded by

Saida Islam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
13 views

Integer Linear Programming

this is my second document

Uploaded by

Saida Islam
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as DOCX, PDF, TXT or read online on Scribd
You are on page 1/ 8

Integer Linear Programming: Branch and Bound Method Operation

Research:
Example:

For Graphical Method:

Max Z=8x1 +5x2

Subject to, 9x1+5x2 ≤ 45

x1+x2 ≤ 6

x1,x2 ≥ 0 and x1,x2 integers.

Solution:

From the given constrains, we can write

For 9x1+5x2 = 45………………(1)

(x1,x2) = (0,9) & (5,0)

For x1+x2 = 6…………………….(2)

(x1,x2) =( 0,6 ) & ( 6,0 )

For point B,

Multiplying (2) by 9 then subtracting from (1)

-4x2 = -9 => x2 = 2.25 and x1 = 3.75


Max Z=8x1 +5x2

For A (0, 6), Z= 30

For B (3.75, 2.25), Z = 41.25

For C (5, 0), Z=40

So, Max Z = 41.25 (For B)

Where x1 = 3.75 and x2 = 2.25 which are not integers.

Now branching this problem:

Here x1 > x2 and x1 = 3.75

So x1 ≤3 and x1 ≥ 4

Sub problem-1

Max Z=8x1 +5x2

Subject to, 9x1+5x2 ≤ 45

x1+x2 ≤ 6

x1 ≤ 3

x1,x2 ≥ 0 and x1,x2 integers.

Sub problem-2

Max Z=8x1 +5x2

Subject to, 9x1+5x2 ≤ 45

x1+x2 ≤ 6

x1 ≥ 4

x1,x2 ≥ 0 and x1,x2 integers.

Graphical Representation of Sub Problems:


Sub Problem-1:

Here, For A, Z= 30

For B, Z= 39

For C, Z= 24

So, Max Z = 39 ( For B)

x1 = 3, & x2 = 3

Those Values are integers.

Sub Problem-2:

Here, For A, B, C
Max Z = 41 (For B)

Where x1 = 4, & x2 = 1.8

x2 is not integer.

Again, x2 ≤ 1 and x2 ≥ 2

Sub Problem-3:

Max Z=8x1 +5x2

Subject to, 9x1+5x2 ≤ 45

x1+x2 ≤ 6

x1 ≥ 4

x2 ≤ 1

Graph for Sub Problem-3

Here, Max Z= 40.5

Where, x1 = 4.44 & x2 = 1 ( x1 is not integer).

Again branching:
Sub Problem-4:

Max Z=8x1 +5x2

Subject to, 9x1+5x2 ≤ 45

x1+x2 ≤ 6

x1 ≥ 4

x2 ≥ 2

Graph for sub Problem-4

There is no common area. So, infeasible solution exists.

For intersecting point ( 4, 0 ).

Max Z = 42

x1 ≤ 4, x1 ≥ 5
Sub Problem-5:

Max Z=8x1 +5x2

Subject to, 9x1+5x2 ≤ 45

x1+x2 ≤ 6

x1 ≥ 4

x2 ≤ 1

x1 ≤ 4

For ( 4,1)

Max Z =37

x1 = 4, & x2 = 1. Those are integers.


Sub Problem-6:

Max Z=8x1 +5x2

Subject to, 9x1+5x2 ≤ 45

x1+x2 ≤ 6

x1 ≥ 4

x2 ≤ 1

x1 ≥ 5

For (5,0) ,

Max Z= 40

x1 = 5, & x2 = 0. There is no Common area.

So the solution is infeasible.

From Sub Problem 1 and 5

Max Z=39

So the solution is optimal. Where, x1 = 3, x2 = 3.


The branch and bound procedure for the given problem is shown in the following figure:

Z= 41.25

x1 = 3.75, x2 = 2.25

x1≤3 x1≥4

Z= 39 Z= 41

x1 = 3, x2 = 3 x1 = 4, x2 = 1.8

x1≤1 x1≥2

Z= 40.5
Infeasible
x1 = 4.44, x2 = 1

x1≤4
x1≥5

Z= 37
Infeasible
x1 = 4, x2 = 1

You might also like