Home > Operation Research calculators > Simplex method example

8. 0-1 Integer programming problem example ( Enter your problem )
 AlgorithmCapital Budgeting Problem - 1Capital Budgeting Problem - 2 Other related methods

2. Capital Budgeting Problem - 1

1. Find solution using 0-1 Integer programming problem method
MAX Z = 300x1 + 90x2 + 400x3 + 150x4
subject to
35000x1 + 10000x2 + 25000x3 + 90000x4 <= 120000
4x1 + 2x2 + 7x3 + 3x4 <= 12
x1 + x2 <= 1
and x1,x2,x3,x4 >= 0

Solution:
To apply branch and bound method, the following 4 constraints have to be added to the LP model.
x_1<=1

x_2<=1

x_3<=1

x_4<=1

Solution stpes by BigM method

 Max Z =  300 x_1  +  90 x_2  +  400 x_3  +  150 x_4
subject to
  35000 x_1  +  10000 x_2  +  25000 x_3  +  90000 x_4 ≤ 120000  4 x_1  +  2 x_2  +  7 x_3  +  3 x_4 ≤ 12   x_1  +   x_2 ≤ 1   x_1 ≤ 1   x_2 ≤ 1   x_3 ≤ 1   x_4 ≤ 1
and x_1,x_2,x_3,x_4 >= 0;

Solution is
Max Z_(A)=750 (x_1=1,x_2=0,x_3=1,x_4=0.3333)

and Z_L=700 (x_1=1,x_2=0,x_3=1,x_4=0) obtainted by the rounded off solution values.

The branch and bound diagram
 Ax_1=1,x_2=0,x_3=1,x_4=0.3333Z_A=750Z_L=700Solution stpes by BigM method

In Sub-problem A, x_4(=0.3333) must be an integer value, so two new constraints are created, x_4=0 and x_4=1

Sub-problem B : Solution is found by adding x_4=0.
Solution stpes by BigM method
 Max Z =  300 x_1  +  90 x_2  +  400 x_3  +  150 x_4
subject to
  35000 x_1  +  10000 x_2  +  25000 x_3  +  90000 x_4 ≤ 120000  4 x_1  +  2 x_2  +  7 x_3  +  3 x_4 ≤ 12   x_1  +   x_2 ≤ 1   x_1 ≤ 1   x_2 ≤ 1   x_3 ≤ 1   x_4 ≤ 1   x_4 = 0
and x_1,x_2,x_3,x_4 >= 0;

Solution is
Max Z_(B)=700 (x_1=1,x_2=0,x_3=1,x_4=0)
and Z_L=700 (x_1=1,x_2=0,x_3=1,x_4=0) obtainted by the rounded off solution values.
This Problem has integer solution, so no further branching is required.
Sub-problem C : Solution is found by adding x_4=1.
Solution stpes by BigM method
 Max Z =  300 x_1  +  90 x_2  +  400 x_3  +  150 x_4
subject to
  35000 x_1  +  10000 x_2  +  25000 x_3  +  90000 x_4 ≤ 120000  4 x_1  +  2 x_2  +  7 x_3  +  3 x_4 ≤ 12   x_1  +   x_2 ≤ 1   x_1 ≤ 1   x_2 ≤ 1   x_3 ≤ 1   x_4 ≤ 1   x_4 = 1
and x_1,x_2,x_3,x_4 >= 0;

Solution is
Max Z_(C)=595 (x_1=0,x_2=0.5,x_3=1,x_4=1)
and Z_L=550 (x_1=0,x_2=0,x_3=1,x_4=1) obtainted by the rounded off solution values.
Z_(C)=595 < Z_(B)=700, so no further branching is required.

The branch and bound diagram
 Ax_1=1,x_2=0,x_3=1,x_4=0.3333Z_A=750Z_L=700Solution stpes by BigM method x_4=0 x_4=1 Bx_1=1,x_2=0,x_3=1,x_4=0Z_B=700Z_L=700Solution stpes by BigM method Cx_1=0,x_2=0.5,x_3=1,x_4=1Z_C=595Z_L=550Solution stpes by BigM method

The 0-1 Integer programming problem algorithm thus terminated and the optimal integer solution is :
Z_(B)=700 and x_1=1,x_2=0,x_3=1,x_4=0

This material is intended as a summary. Use your textbook for detail explanation.
Any bug, improvement, feedback then Submit Here