Home > Operation Research calculators > Simplex method example

8. 0-1 Integer programming problem example ( Enter your problem )
  1. Algorithm
  2. Capital Budgeting Problem - 1
  3. Capital Budgeting Problem - 2
Other related methods
  1. Simplex (BigM) method
  2. Two-Phase method
  3. Graphical method
  4. Primal to dual conversion
  5. Dual simplex method
  6. Integer simplex method
  7. Branch and Bound method
  8. 0-1 Integer programming problem

2. Capital Budgeting Problem - 1

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

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


 
Copyright © 2018. All rights reserved. Terms, Privacy