We use cookies to improve your experience on our site and to show you relevant advertising. By browsing this website, you agree to our use of cookies. Learn more   

AtoZmath.com
Support us
(New) All problem can be solved using search box
I want to sell my website www.AtoZmath.com with complete code
Home What's new College Algebra Games Feedback About us
Algebra Matrix & Vector Numerical Methods Statistical Methods Operation Research Word Problems Calculus Geometry Pre-Algebra


Home > Operation Research calculators > 0-1 Integer programming problem example
8. 0-1 Integer programming problem example ( Enter your problem )
( Enter your problem )
  1. Algorithm
  2. Capital Budgeting Problem - 1 example
  3. Capital Budgeting Problem - 2 example
 		Other related methods
  1. Formulate linear programming model
  2. Graphical method
  3. Simplex method (BigM method)
  4. Two-Phase method
  5. Primal to dual conversion
  6. Dual simplex method
  7. Integer simplex method
  8. Branch and Bound method
  9. 0-1 Integer programming problem
  10. Revised Simplex method
2. Capital Budgeting Problem - 1 example
(Previous example)		10. Revised Simplex method
(Next method)

3. Capital Budgeting Problem - 2 example


Find solution using 0-1 Integer programming problem method
MAX Z = 6500x1 + 7000x2 + 2250x3 + 2500x4
subject to
700x1 + 850x2 + 300x3 + 350x4 <= 1200
550x1 + 550x2 + 150x3 + 200x4 <= 700
400x1 + 350x2 + 100x3 <= 400
x1 + x2 >= 1
-x3 + x4 <= 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 steps by BigM method

Max `Z``=````6500``x_1`` + ``7000``x_2`` + ``2250``x_3`` + ``2500``x_4`
subject to
```700``x_1`` + ``850``x_2`` + ``300``x_3`` + ``350``x_4`≤`1200`
```550``x_1`` + ``550``x_2`` + ``150``x_3`` + ``200``x_4`≤`700`
```400``x_1`` + ``350``x_2`` + ``100``x_3`≤`400`
`````x_1`` + ````x_2`≥`1`
` - ````x_3`` + ````x_4`≤`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)=9062.5` `(x_1=0,x_2=1,x_3=0.5,x_4=0.375)`

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

The branch and bound diagram
A
`x_1=0,x_2=1,x_3=0.5,x_4=0.375`
`Z_A=9062.5`
`Z_L=7000`
Solution steps by
BigM method


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

Sub-problem B : Solution is found by adding `x_3=0`.
Solution steps by BigM method
Max `Z``=````6500``x_1`` + ``7000``x_2`` + ``2250``x_3`` + ``2500``x_4`
subject to
```700``x_1`` + ``850``x_2`` + ``300``x_3`` + ``350``x_4`≤`1200`
```550``x_1`` + ``550``x_2`` + ``150``x_3`` + ``200``x_4`≤`700`
```400``x_1`` + ``350``x_2`` + ``100``x_3`≤`400`
`````x_1`` + ````x_2`≥`1`
` - ````x_3`` + ````x_4`≤`1`
`````x_1`≤`1`
`````x_2`≤`1`
`````x_3`≤`1`
`````x_4`≤`1`
`````x_3`=`0`
and `x_1,x_2,x_3,x_4 >= 0; `

Solution is
Max `Z_(B)=8875` `(x_1=0,x_2=1,x_3=0,x_4=0.75)`
and `Z_L=7000` `(x_1=0,x_2=1,x_3=0,x_4=0)` obtainted by the rounded off solution values.
Sub-problem C : Solution is found by adding `x_3=1`.
Solution steps by BigM method
Max `Z``=````6500``x_1`` + ``7000``x_2`` + ``2250``x_3`` + ``2500``x_4`
subject to
```700``x_1`` + ``850``x_2`` + ``300``x_3`` + ``350``x_4`≤`1200`
```550``x_1`` + ``550``x_2`` + ``150``x_3`` + ``200``x_4`≤`700`
```400``x_1`` + ``350``x_2`` + ``100``x_3`≤`400`
`````x_1`` + ````x_2`≥`1`
` - ````x_3`` + ````x_4`≤`1`
`````x_1`≤`1`
`````x_2`≤`1`
`````x_3`≤`1`
`````x_4`≤`1`
`````x_3`=`1`
and `x_1,x_2,x_3,x_4 >= 0; `

Solution is
This Problem has an infeasible solution, so this branch is terminated.



The branch and bound diagram
A
`x_1=0,x_2=1,x_3=0.5,x_4=0.375`
`Z_A=9062.5`
`Z_L=7000`
Solution steps by
BigM method
`x_3=0``x_3=1`
B
`x_1=0,x_2=1,x_3=0,x_4=0.75`
`Z_B=8875`
`Z_L=7000`
Solution steps by
BigM method		C

Infeasible Solution

Solution steps by
BigM method



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

Sub-problem D : Solution is found by adding `x_4=0`.
Solution steps by BigM method
Max `Z``=````6500``x_1`` + ``7000``x_2`` + ``2250``x_3`` + ``2500``x_4`
subject to
```700``x_1`` + ``850``x_2`` + ``300``x_3`` + ``350``x_4`≤`1200`
```550``x_1`` + ``550``x_2`` + ``150``x_3`` + ``200``x_4`≤`700`
```400``x_1`` + ``350``x_2`` + ``100``x_3`≤`400`
`````x_1`` + ````x_2`≥`1`
` - ````x_3`` + ````x_4`≤`1`
`````x_1`≤`1`
`````x_2`≤`1`
`````x_3`≤`1`
`````x_4`≤`1`
`````x_3`=`0`
`````x_4`=`0`
and `x_1,x_2,x_3,x_4 >= 0; `

Solution is
Max `Z_(D)=7812.5` `(x_1=0.125,x_2=1,x_3=0,x_4=0)`
and `Z_L=7000` `(x_1=0,x_2=1,x_3=0,x_4=0)` obtainted by the rounded off solution values.
Sub-problem E : Solution is found by adding `x_4=1`.
Solution steps by BigM method
Max `Z``=````6500``x_1`` + ``7000``x_2`` + ``2250``x_3`` + ``2500``x_4`
subject to
```700``x_1`` + ``850``x_2`` + ``300``x_3`` + ``350``x_4`≤`1200`
```550``x_1`` + ``550``x_2`` + ``150``x_3`` + ``200``x_4`≤`700`
```400``x_1`` + ``350``x_2`` + ``100``x_3`≤`400`
`````x_1`` + ````x_2`≥`1`
` - ````x_3`` + ````x_4`≤`1`
`````x_1`≤`1`
`````x_2`≤`1`
`````x_3`≤`1`
`````x_4`≤`1`
`````x_3`=`0`
`````x_4`=`1`
and `x_1,x_2,x_3,x_4 >= 0; `

Solution is
This Problem has an infeasible solution, so this branch is terminated.



The branch and bound diagram
A
`x_1=0,x_2=1,x_3=0.5,x_4=0.375`
`Z_A=9062.5`
`Z_L=7000`
Solution steps by
BigM method
`x_3=0``x_3=1`
B
`x_1=0,x_2=1,x_3=0,x_4=0.75`
`Z_B=8875`
`Z_L=7000`
Solution steps by
BigM method		C

Infeasible Solution

Solution steps by
BigM method
`x_4=0``x_4=1`
D
`x_1=0.125,x_2=1,x_3=0,x_4=0`
`Z_D=7812.5`
`Z_L=7000`
Solution steps by
BigM method		E

Infeasible Solution

Solution steps by
BigM method



In Sub-problem D, `x_1(=0.125)` must be an integer value, so two new constraints are created, `x_1=0` and `x_1=1`

Sub-problem F : Solution is found by adding `x_1=0`.
Solution steps by BigM method
Max `Z``=````6500``x_1`` + ``7000``x_2`` + ``2250``x_3`` + ``2500``x_4`
subject to
```700``x_1`` + ``850``x_2`` + ``300``x_3`` + ``350``x_4`≤`1200`
```550``x_1`` + ``550``x_2`` + ``150``x_3`` + ``200``x_4`≤`700`
```400``x_1`` + ``350``x_2`` + ``100``x_3`≤`400`
`````x_1`` + ````x_2`≥`1`
` - ````x_3`` + ````x_4`≤`1`
`````x_1`≤`1`
`````x_2`≤`1`
`````x_3`≤`1`
`````x_4`≤`1`
`````x_3`=`0`
`````x_4`=`0`
`````x_1`=`0`
and `x_1,x_2,x_3,x_4 >= 0; `

Solution is
Max `Z_(F)=7000` `(x_1=0,x_2=1,x_3=0,x_4=0)`
and `Z_L=7000` `(x_1=0,x_2=1,x_3=0,x_4=0)` obtainted by the rounded off solution values.
This Problem has integer solution, so no further branching is required.
Sub-problem G : Solution is found by adding `x_1=1`.
Solution steps by BigM method
Max `Z``=````6500``x_1`` + ``7000``x_2`` + ``2250``x_3`` + ``2500``x_4`
subject to
```700``x_1`` + ``850``x_2`` + ``300``x_3`` + ``350``x_4`≤`1200`
```550``x_1`` + ``550``x_2`` + ``150``x_3`` + ``200``x_4`≤`700`
```400``x_1`` + ``350``x_2`` + ``100``x_3`≤`400`
`````x_1`` + ````x_2`≥`1`
` - ````x_3`` + ````x_4`≤`1`
`````x_1`≤`1`
`````x_2`≤`1`
`````x_3`≤`1`
`````x_4`≤`1`
`````x_3`=`0`
`````x_4`=`0`
`````x_1`=`1`
and `x_1,x_2,x_3,x_4 >= 0; `

Solution is
Max `Z_(G)=6500` `(x_1=1,x_2=0,x_3=0,x_4=0)`
and `Z_L=6500` `(x_1=1,x_2=0,x_3=0,x_4=0)` obtainted by the rounded off solution values.
This Problem has integer solution, so no further branching is required.



The branch and bound diagram
A
`x_1=0,x_2=1,x_3=0.5,x_4=0.375`
`Z_A=9062.5`
`Z_L=7000`
Solution steps by
BigM method
`x_3=0``x_3=1`
B
`x_1=0,x_2=1,x_3=0,x_4=0.75`
`Z_B=8875`
`Z_L=7000`
Solution steps by
BigM method		C

Infeasible Solution

Solution steps by
BigM method
`x_4=0``x_4=1`
D
`x_1=0.125,x_2=1,x_3=0,x_4=0`
`Z_D=7812.5`
`Z_L=7000`
Solution steps by
BigM method		E

Infeasible Solution

Solution steps by
BigM method
`x_1=0``x_1=1`
F
`x_1=0,x_2=1,x_3=0,x_4=0`
`Z_F=7000`
`Z_L=7000`
Solution steps by
BigM method		G
`x_1=1,x_2=0,x_3=0,x_4=0`
`Z_G=6500`
`Z_L=6500`
Solution steps by
BigM method



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



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


2. Capital Budgeting Problem - 1 example
(Previous example)		10. Revised Simplex method
(Next method)


Share this solution or page with your friends.


Home What's new College Algebra Games Feedback About us
 
Copyright © 2023. All rights reserved. Terms, Privacy
 
 

.