integer programming
TRANSCRIPT
*****
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