Pemrograman Integer Pemrograman Integer (PI) adalah suatu PL dengan tambahan

persyaratan bahwa semua atau beberapa variabel bernilai integer non-negatif. (misalnya tidak mungkin solusinya adalah 1,5 mobilatau 2,76 orang)

Parameter model tidak termasuk dalam persyaratan ini Jika semua variabel harus integer, model ini disebut pure integer

programming Jika hanya berlaku untuk beberapa variabel saja, disebut mixed

integer programming Jika variabelnya dibatasi bernilai nol atau satu, disebut zero one

integer programming Dalam kuliah ini akan dibahas tentang pure integer programming

dengan menggunakan metode cutting plane dan branch and bound

Contoh: Diberikan masalah pemrograman integer berikut:

1 2

1 2

1 2

1 2

Max Z 7 9dengan syarat:

3 67 35

, integer non negatif

X X

X XX X

X X

= +

+ +

Dengan menggunakan metode simpleks, diperoleh pemecahan sementara berikut: Basis X1 X2 S1 S2 Solusi Z 0 0 28/11 15/11 63 X2 0 1 7/22 1/22 7/2 X1 1 0 -1/22 3/22 9/2

Jelas bahwa solusi ini tidak layak karena nilai X1 dan X2tidak integer Karena itu, perlu ditambahkan sebuah kendala Gomory pada tabel. Persamaan x1 dan x2 memiliki nilai fi yang sama yaitu , sehingga salah satu dapat digunakan. Misalkan digunakan persamaan x2, maka dihasilkan:

7 712 1 222 22 2X S S+ + = atau

7 1 12 1 222 22 2(0 ) (0 ) (3 )X S S+ + + + = +

sehingga diperoleh kendala Gomory: 7 1 1

1 1 222 22 2gS S S =

Sg1

Penambahankendala

Penambahankendala

Penambahankendala

X

X

XModel Awal

Bagian A

Bagian B

Bagian B1

Bagian B2

Bagian B1a

Bagian B1b

BaganPenyelesaian

Pustaka: Sri Mulyono, Riset Operasional, Penerbit

FEUI