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 > Simplex method 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
1. Algorithm
(Previous example)		3. Capital Budgeting Problem - 2 example
(Next example)

2. Capital Budgeting Problem - 1 example


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 steps 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
A
`x_1=1,x_2=0,x_3=1,x_4=0.3333`
`Z_A=750`
`Z_L=700`
Solution steps 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 steps 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 steps 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
A
`x_1=1,x_2=0,x_3=1,x_4=0.3333`
`Z_A=750`
`Z_L=700`
Solution steps by
BigM method
`x_4=0``x_4=1`
B
`x_1=1,x_2=0,x_3=1,x_4=0`
`Z_B=700`
`Z_L=700`
Solution steps by
BigM method		C
`x_1=0,x_2=0.5,x_3=1,x_4=1`
`Z_C=595`
`Z_L=550`
Solution steps 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


1. Algorithm
(Previous example)		3. Capital Budgeting Problem - 2 example
(Next example)


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
 
 

.