integer programming

*****

Merupakan bentuk lain dari programa linier dimana asumsi divisibilitas melemah.

Asumsi divisibilitas melemah artinya sebagian nilai variabel keputusan harus berupa bilangan bulat dan sebagian yang lain boleh berupa bilangan pecahan. Oleh karena itu terdapat 3 macam programa intejer yaitu Intejer Murni, Intejer Campuran dan Intejer 0-1

Contoh Intejer Murni (Pure Integer):

Maks. f = 3x1 + 2x2

kendala: x1 + x2 ≤ 6

x1, x2 ≥ 0 ; x1, x2 : intejer

Contoh Intejer Campuran (Mixed Integer):

Maks. f = 3x1 + 2x2

kendala: x1 + x2 ≤ 6

x1, x2 ≥ 0 ; x1: intejer

Contoh Intejer ) 0 – 1 (Zero – One)

Maks. f = x1 − x2

kendala:

x1 + 2x2 ≤ 2

2x1 − x2 ≤ 1

x1, x2 = 0 atau 1

Contoh 1:

Maks. f = 10x1 + x2

kendala: 2x1 + 5x2 ≤ 11

x1, x2 ≥ 0 dan intejer

Solusi Grafis akan diperoleh:

x1

x2

0 6

6

3

3

A

B

A(0;2,2) maka f = 2,2 (tdk fisibel) B(5,5;0) maka f = 55 (fisibel)

5 < x1 < 6

Solusi fisibel dibagi 2 menjadi:

(1) Maks. f = 10x1 + x2

kendala: 2x1 + 5x2 ≤ 11

x1 ≤ 5

x1, x2 ≥ 0 dan intejer, dan

(2) Maks. f = 10x1 + x2

kendala: 2x1 + 5x2 ≤ 11

x1 ≥ 6

x1, x2 ≥ 0 dan intejer

Problem (2) infeasible.

Problem (1) mempunyai solusi fisibel dengan:

x1 = 5 ; x2 = 0,2 dengan f = 50,2

Pencabangan dilakukan pada x2 karena:

0 ≤ x2 ≤ 1, sehingga terbentuk dua permasalahan lagi yaitu:

(3) Maks. f = 10x1 + x2

kendala: 2x1 + 5x2 ≤ 11

x1 ≤ 5

x2 ≤ 0

x1, x2 ≥ 0 dan intejer, dan

(4) Maks. f = 10x1 + x2

kendala: 2x1 + 5x2 ≤ 11

x1 ≤ 5

x2 ≥ 1

x1, x2 ≥ 0 dan intejer

Problem (3) diperoleh solusi:

x1 = 5 ; x2 = 0 dan f=50

Problem (4) diperoleh solusi:

x1 = 3 ; x2 =1 dan f=31

Karena keduanya sudah intejer, maka tidak ada lagi pencabangan.

Permasalahannya Maksimasi, maka solusi optimumnya adalah x1* = 5 ; x2* = 0 dengan f = 50

1

3

2

4

5 f*=55

(5,5;0)

f* = 50,2

(5; 0,2)

f* = 50

f* = 31

infeasible

Contoh 2:

Maks. f = 3x1 + 4x2

kendala: 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

x1, x2 ≥ 0 dan intejer

Dengan mengikuti solusi dari programa linier, diperoleh solusi fisibel dengan:

x1* = 2,25 ; x2* =1,5 dan f =12,75

I. Gunakan pencabangan pada x2: 1≤ x2 ≤2

(2) Maks. f = 3x1 + 4x2

kendala: 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

x2 ≤ 1

x1, x2 ≥ 0 dan intejer, dan

(3) Maks. f = 3x1 + 4x2

kendala: 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

x2 ≥ 2

x1, x2 ≥ 0 dan intejer, dan

Solusi fisibel (2) diperoleh:

x1 = 2,5 ; x2 = 1 dan f = 11,5

Solusi fisibel (3) diperoleh:

x1 = 1,5 ; x2 = 2 dan f = 12,5

Keduanya belum intejer. Pencabangan dilanjutkan pada (3) karena lebih dekat ke solusi optimal sesuai fungsi tujuan.

Pencabangan dilakukan pada x1 : 1≤ x1≤ 2

(4) Maks. f = 3x1 + 4x2

kendala: 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

x2 ≥ 2

x1 ≤ 1, x1, x2 ≥ 0 dan intejer

(5) Maks. f = 3x1 + 4x2

kendala: 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

x2 ≥ 2

x1 ≥ 2

x1 ≤ 1, x1, x2 ≥ 0 dan intejer

Solusi (5) infeasible.

Solusi fisibel (4) diperoleh:

x1 = 1 ; x2 = 7/3 dan f = 12,33

Selanjutnya dilakukan pencabangan pada x2 dengan : 2 ≤ x1 ≤ 3

(6) Maks. f = 3x1 + 4x2

kendala: 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

x2 ≥ 2

x1 ≤ 1

x2 ≤ 2

x1, x2 ≥ 0 dan intejer

(7) Maks. f = 3x1 + 4x2

kendala: 2x1 + x2 ≤ 6

2x1 + 3x2 ≤ 9

x2 ≥ 2

x1 ≤ 1

x2 ≥ 3

x1, x2 ≥ 0 dan intejer

Solusi fisibel (6) adalah:

x1 =1 ; x2 = 2 dengan f = 11

Solusi fisibel (7) adalah:

x1 = 0 ; x2 = 3 dengan f = 12

Keduanya intejer, maka solusi optimum adalah (7) sesuai fungsi tujuan.

1

3

2

5

4 7

6

f* = 12,75

f* = 11,5

f* = 12,5 infeasible

f* = 12,33

f* = 11

f* = 12

(2,5;1)

(2,25;1,5)

(1,5;2)

(1;7/3)

(1;2)

(0;3)

x2≤1 x2≤2

x1≤1 x2≥2

x2≥3

x1≥2