PROGRAMA INTEGER

SEKOLAH TINGGI MANAJEMEN INFORMATIKA & KOMPUTER (STMIK) MERCUSUAR

Jl. Raya Jatiwaringin No. 144 Pondok Gede Bekasi 17411

Programa Integer• Programa Integer merupakan persoalan Programa Linier yang

mensyaratkan jawabannya adalah bilangan Bulat.• Merupakna kondisi yang nyata dilapangan. Misalnya persoalan

kebutuhan kursi dan meja, pasti jumlah kursi dan meja disyaratkan merupakan bilanganbulat.

• Tekni yang digunakan adalah metode “Branch & Bound”• Branch, untuk men coba kemungkinan jawaban bilangan bulat.

Mis: X1 = 3,45 , maka dibuat 2 pencabangan masing2 dengan pembatas baru X1≤3 dan X1≥4

• Bound, memilih salah satu cabang yang jawabannya kearah yang diinginkan

Contoh 1 :Max : Z = 10X1 + 8 X2Pembatas : 2x1 + 3X2 ≤ 11 X1 ≥ 0 X2 ≥ 0 Program I diatas diselesaikan dengan cara grafik bila variabelnya

2, dan diselesaikan dengancara simpleks apabila variabelnya lebih dari 2

Solusinya adalah :

X1 masih bernilai pecahan

X1 X2 Z

0,000 0,000 0,000

0,000 3,667 29,333

5,500 0,000 55,000

Program 2 Tambahkan pembatas baru X1 ≤ 5 Persamaan Programa Liner menjadi;

Max : Z = 10X1 + 8 X2Pembatas : 2x1 + 3X2 ≤ 11 X1 ≤ 5

• Solusinya :o Daerah fisibel adalah (0;0) - (5;0) - (5;0,3) - (3,7;0) o Nilai Z maksimal ada di (5;0,3) = 52,4 (belum solusi integer)

X1 X2 Z

0 0 0 0 3,67 29,33 5,00 - 50,00

5,00 0,33 52,67

Program 3 Tambahkan pembatas baru X2 ≥ 6 pada program 1 Persamaan Programa Liner menjadi;

Max : Z = 10X1 + 8 X2Pembatas : 2x1 + 3X2 ≤ 11 X1 ≥ 6

Solusinya adalah :o Program 3 ini tidak fisibel (tidak ada daerahj awaban). o Caranya: masukkan pembatas 2 (nilai X ≥ 6) ke pembatas 1.

nilainya pasti lebih besar dari batas 11 (berarti tidak terpenuhi syaratnya - tidak fisibel).

o Tidak perlu bounding, pencabangan sudah pasti harus dan program 2 yang selanjutnya akan dicabangkan lagi menjadi program 4 dan 5

• Program 4• Tambahkan pembatas baru X2 ≤ 0 pada program 2 Persamaan Programa Liner menjadi;

Max : Z = 10X1 + 8 X2Pembatas : 2x1 + 3X2 ≤ 11 X1 ≤ 5 X2 ≤ 0

• Solusinya :o Solusinya adalah pada titik (5;0) dengan Z = 50 → solusi

integer

X1 X2 Z

- - -

5,00 - 50,00

• Program 5• Tambahkan pembatas baru X2 ≥ 1 pada program 2 Persamaan Programa Liner menjadi;

Max : Z = 10X1 + 8 X2Pembatas : 2x1 + 3X2 ≤ 11 X1 ≤ 5

X2 ≥1• Solusinya :• SoIusinya pada titik (4;1) dengan Z = 48 → solusi integer,

tetapi masih kalah dengan hasil program 4.

X1 X2 Z - 3,67 29,33 - 1,00 8,00 4,00 1,00 48,00

Pencabangan dan Pembatasan contoh 1

(3)

(2)

(1)

(4)

(5)

Z=55Z=48

Z=52,4

Z=50

X1=5,5X2=0

TidakFeasibel

X1=5X2=0,3

X1=4X2=1

X1=5X2=0

X1≥6

X1≤5 X2≤1

X2≤0

CONTOH 2Program 1

Max : Z = 3X1 + 4X2Pembatas : 2X1 + X2 ≤ 6

2X1 + 3X2 ≤ 9

X1 dan X2 ≥ dan Integer• Daerah fisibel adalah (0;0) – (3;0) – (2,25; 1,5) dan (0;3) • Jawaban optimal pada (2,25; 1,5) dengan Z = 12,75 namun belum

integer X1 maupun X2 X1 X2 Z

0 0 0 3,00 0 9,00

0 3,00 12,00 2,25 1,50 12,75

• Pencabngan dilakukan pada X2 karena nilai desimalnya lebih dekat ke 0,5.

• Selanjutnya buatkan program 2 dan program 3 dengan tambahan fungsi pembatas baru X2 ≤ 1 dan X2 ≥ 2.

Program 2• Tambahkan pembatas baru X2 ≤ 1 pada program 1

Max : Z = 3X1 + 4X2Pembatas : 2X1 + X2 ≤ 6

2X1 + 3X2 ≤ 9

X2 ≤ 1• Solusinya

o Daerah fisibe1 adalah (0;0) - (3;0) - (2,5;1) - (0;1) o Z maksimal ada di (2,5; 1) = 11,5 (be1um integer)

X1 X2 Z0 0 03 0 90 1 4

2,5 1 11,5

Program 3• Tambahkan pembatas baru X2 ≥2 pada program 1

Max : Z = 3X1 + 4X2Pembatas : 2X1 + X2 ≤ 6

2X1 + 3X2 ≤ 9

X2 ≥ 2• Solusinya• Daerah fisibel adalah (0;2) - (1,5;2) - (0;3) • Z maksimal ada di (1,5;2) = 12,5 (belum integer)

X1 X2 Z 0,00 3,00 12,00 0,00 2,00 8,00 1,50 2,00 12,50

• Dari solusi program 2 dan 3, dilakukan bounding (pembatasan) dengan menetapkan bahwa pencabangan berikutnya adalah dari program 3 yang nilai Z-nya lebih besar → buatkan program 4 dan 5.

• Dasar bounding adalah nilai terbesar - bila kedua cabang program adalah fisibel.

• Pencabangan dilakukan dengan menambahkan pembatas baru ke program 3, dengan XI≤1 dan XI ≥ 2 menjadi program 4 dan 5

Program 4• Tambahkan pembatas baru XI ≤ 1 ke program 3

Max : Z = 3X1 + 4X2Pembatas : 2X1 + X2 ≤ 6

2X1 + 3X2 ≤ 9

X2 ≥ 2X1 ≤ 1

• Solusinya• Daerah fisibel adalah (0;2) - (1 ;2) - (1 ;2,3) - (O;3) • Z maksimal pada (1;2,3) = 12,33 → belum integer.

X1 X2 Z 0,00 3,00 12,00 0,00 2,00 8,00 1,00 2,33 12,33 1,00 2,00 11,00

Program 5• Tambahkan pembatas barn X1 ≥ 2. ke program 3

Max : Z = 3X1 + 4X2Pembatas : 2X1 + X2 ≤ 6

2X1 + 3X2 ≤ 9

X2 ≥ 2X1 ≥ 2

• Solusinya– Program 5 tidak fisibel → masukkan pembatas 3 dan 4 ke

pembatas 2 - hasilnya tidak fisibel. – Dari gambar → tidak ada daerah yang mernenuhi syarat

program 3' dan X1 ≥ 2

• Program 6• Lakukan pencabangan baru dari program 4 ini menjadi

program 6 dan 7 dengan menambahkan pembatas yang baru X2 ≤ 2 dan X2 ≥ 3

• Tambahkan pembatas baru X2 ≤ 2 pada program 4Max : Z = 3X1 + 4X2Pembatas : 2X1 + X2 ≤ 6

2X1 + 3X2 ≤ 9

X2 ≥ 2X1 ≤ 1 X2 ≤ 2

• Solusi Program 6 ini ada pada (1;2) denngan Z = 11 X1 X2 Z

0,00 2,00 8,00 1,00 2,00 11,00

Program 7• Tambahkan pembatas baru X2 ≥ 3 pada program 4

Max : Z = 3X1 + 4X2Pembatas : 2X1 + X2 ≤ 6

2X1 + 3X2 ≤ 9

X2 ≥ 2X1 ≤ 1X2 ≥ 3

• Solsi untuk Program 7 adalah pada (0;3) dengan Z = 12 (solusi sudah integer) → Optimal, karena lebih baik nilainya dari solusi program 6

X1 X2 Z

0,00 3,00 12,00

Pencabangan dan Pembatasan contoh 2

(3)

(2)

(1)

(4)

(5)

Z=12,75

Z=11,5

Z=12,33

X1=2,25X2=1,5

X1=2,5X2=1

X1=1X2=2,3

X2≥2

X2≤1

X1≥2

X1≤1

(6)

(7)

Z=12

Z=11

X1=0X2=3

X1=1X2=2

Z=12,5

X1=1,5X2=2,0

Tidak fisibel

X2≤2

X2≤1