BAB I

PENDAHULUAN

1.1 Latar Belakang

Program linier integer merupakan bentuk lain dari program linier yang

variabel keputusannya dibatasi bernilai integer, agar jawaban persoalan menjadi realistik.

Misalnya, jika variabel keputusan yang dihadapi berkaitan dengan jumlah orang, mesin – mesin,

kendaraan, dan lain – lain akan terasa sangat janggal jika dikatakan untuk menyelesaikan

pekerjaan tertentu diperlukan 2,5 buah mesin dan 5,5 orang, sebaliknya jika dikatakan bahwa

pekerjaan itu diperlukan 2 atau 3 buah mesin dan 5 orang sehingga pengambilan keputusan akan

terasa menjadi realistik dan lebih mudah.

Oleh karena itu, program linier integer yang merupakan bentuk lain dari program linier,

menyelesaikan persoalan yang variabel keputusannya dibatasi bernilai integer. Seperti persoalan

linier berikut ini :

Maksimumkan : Z=c1 x1+c2 x2+. ..+c j x j+ .. .+cn xn

Dengan kendala : a11x1+a12 x2+ .. .+a1 j x j+. ..+a1n xn≤b1

a21 x1+a22 x2+. ..+a2 j x j+ .. .+a2 n xn≤b2

⋮ ⋮ ⋮ ⋮ ⋮a i1 x1+ai 2 x2+.. . ..+aij x j+. . .. .+ain xn≤b i ….. (1.1)

⋮ ⋮ ⋮ ⋮ ⋮am1 x1+am2 x2+. . .+amj x j+ .. .+amn xn≤bm

x1 , x2 ,. .. , x j , . .. , xn≥0

Algoritma Branch and Bound merupakan salah satu metode penyelesaian untuk persoalan

program linier integer (1.1). Dengan algoritma ini dibuat kendala tambahan yang memotong

daerah fisibel dan persoalan program linier, sehingga dapat mengeliminasi penyelesaian yang

bukan integer. Proses pemotongan pada daerah fisibel ini akan terus berlangsung hingga

diperoleh penyelesaian dengan seluruh variabel bernilai integer.

1.2 Identifikasi Masalah

Berdasarkan latar belakang di atas maka permasalahan yang akan dibahas adalah

bagaimana menentukan peyelsaian optimal dari suatu persoalan program linier integer dengan

algoritma branch and bound.

1.3 Pembatasan Masalah

Dalam hal ini masalah dibatasi pada penentuan penyelesaian persoalan program linier

integer murni (pure integer linier programming) dengan algoritma branch and bound.

1.4 Tujuan Penelitian

Tujuan dari penelitian ini adalah menentukan penyelesaian optimal dari persoalan

program linier integer dengan menggunakan algoritma branch and bound.

1.5 Manfaat Penelitian

untuk menambah wawasan para pembaca dalam menentukan persoalan program linier integer dan contoh soal dengan menggunakan algoritma branch and bound.

BAB II

LANDASAN TEORI

2.1 Konsep – konsep Dasar

Definisi 2.1.1 [2]

Suatu fungsi f ( x1 , x2 , .. . , xn )dari x1 , x2 ,. .. , xn adalah fungsi linier jika dan hanya jika

untuk sejumlah himpunan konstanta c1 , c2 , .. . , cnberlakuf ( x1 , x2 , .. . , xn )=c1 x 1 +c2 x2+. ..+cn xn

Dalam membangun pemrograman linier digunakan karakteristik – karakteristik sebagai

berikut :

1. Variabel keputusan adalah variabel yang menguraikan secara lengkap keputusan –

keputusan yang akan dibahas.

2. Fungsi tujuan merupakan fungsi dari variabel keputusan yang akan dimaksimumkan

dan diminimumkan.

3. Pembatas merupakan kendala yang dihadapi sehingga tidak dapat ditentukan nilai –

nilai variabel keputusannya secara sebarang.

4. Pembatas tanda adalah pembatas yang menjelaskan apakah variabel keputusannya

diasumsiakan hanya bernilai nonnegatif atau variabel keputusannya tersebut bernilai

positif, boleh juga bernilai negatif (tidak terbatas dalam tanda) .

Definisi 2.1.2 [2]

Jika seluruh variabel pada suatu (penyelesaian dasar berharga nonnegatif) maka

penyelesaian itu disebut penyelesaian dasar fisibel.

Persoalan program linier adalah persoalan optimasi melakukan hal berikut :

1. Memaksimumkan atau meminimumkan fungsi tujuan.

2. Nilai dari variabel keputusan harus memenuhi himpunan kendala.

3. Pembatas tanda dikaitkan dengan tiap variabel .

Definisi 2.1.3

Daerah fisibel dari program linier adalah set dari seluruh titik yang memenuhi seluruh

kendala, termasuk pembatas tanda.

Definisi 2.1.4

Pada persoalan maksimasi, solusi optimal dari persoalan program linier adalah suatu titik

pada daerah fisibel dengan nilai fungsi tujuan terbesar dan untuk persoalan minimasi, solusi

optimal dari persoalan program linier adalah suatu titik pada daerah fisibel dengan nilai fungsi

tujuan terkecil.

2.2 Metode Simpleks

Metode simpleks merupakan prosedur aljabar yang bersifat iteratif .

Suatu bentuk model pemrograman linier yaitu :

Maksimumkan : Z=c1 x1+c2 x2+. ..+c j x j+ .. .+cn xn

Dengan kendala : a11x1+a12 x2+ .. .+a1 j x j+. ..+a1n xn≤b1

a21 x1+a22 x2+. ..+a2 j x j+ .. .+a2 n xn≤b2

⋮ ⋮ ⋮ ⋮ ⋮a i1 x1+ai 2 x2+.. . ..+aij x j+. . .. .+ain xn≤b i ….. (1)

⋮ ⋮ ⋮ ⋮ ⋮am1 x1+am2 x2+. . .+amj x j+ .. .+amn xn≤bm

x1 , x2 ,. .. , x j , . .. , xn≥0

Dalam penyelesaian persoalan program linier dengan metode simpleks, persoalan diubah

ke bentuk formulasi yang memiliki sifat – sifat :

1. Pembatas harus berbentuk persamaan dengan ruas kanan nonnegatif

2. Seluruh variabel merupakan variabel non negatif

3. Fungsi tujuan berupa maksimum atau minimum

Variabel slack berkaitan dengan batasan ≤ mewakili jumlah kelebihan sisi kanan dari

batasan suatu kendala dibanding sisi kiri kendala tersebut. Variabel surplus berkaitan dengan

batasan ≥ mewakili jumlah kelebihan sisi kiri dari batasan suatu kendala dibanding sisi kanan

kendala tersebut.

2.2.1 Tabel Metode Simpleks

Tabel awal metode simpleks :CB

Variabel basis

x1 x2 … xj … xn xn+1 xn+2 … xn+i … xn+m Bc1 c2 … cj … cn 0 0 … 0 … 0

0 xn+1 a11 a12 … a1j … a1n 1 0 … 0 … 0 b1

0 xn+2 a21 a22 … a2j … a2n 0 1 … 0 … 0 b2… … … … … … … … … … … … … … …

0 xn+i ai1 ai2 … aij … ain 0 0 … 1 … 0 bi… … … … … … … … … … … … … … …

0 xn+m am1 am2 … amj … amn 0 0 … 0 … 1 bm

Z Z1 Z2 … Zj … Zn 0 0 … 0 … 0

Tabel optimum metode simpleks :CB

Variabel basis

x1 x2 … xj … xn xn+1 xn+2 … xn+i … xn+m Bc1 c2 … cj … cn 0 0 … 0 … 0

C1 x1 1 0 … 0 … 0 y11 y12 … y1i … y1m R1

C2 x2 0 1 … 0 … 0 y21 y22 … y2i … y2m R2… … … … … … … … … … … … … … …

Cj xj 0 0 … 1 … 0 yj1 yj2 … yji … yjm Ri… … … … … … … …… … … … … … … …

Cn xn 0 0 … 0 … 1 yn1 yn2 … yni … ynm Rm

Z 0 0 … 0 … 0 Z1 Z2 … Zj … Zn

2.2.2 Langkah – langkah metode simpleks

Langkah – langkah metode simpleks :

1. Konversikan persoalan program linier dalam bentuk baku

2. Cari penyelesaian fisibel permulaan

3. Jika variabel non basis mempunyai koefisien nonnegatif pada baris fungsi tujuan,

maka penyelesaian dasar fisibel optimal jika tidak pilih koefisien paling negatif pada

baris fungsi tujuan

4. Hitung rasio ruas kanan pada tiap baris kendala dengan koefisien variabel yang

masuk basis pada tiap baris kendala, variabel basis terkecil berubah status menjadi

variabel non basis

Perhitungan pengisian tabel :

a. Hitung rasio

br

ark

=min i { bi

a ik

, a ik¿0}b. Hitung baris ke-r :

yrj=arj

ark , j = 1, 2, …, n i = 1, 2, …, m

c. Untuk baris lain : y ij=aij−arj

aik

ark , j = 1, 2, …, n i = 1, 2, …, m

2.3 Metode Simpleks Dual

Metode simpleks dual adalah seluruh kendala bertanda ≤. Pada metode ini variabel non

basis ditentukan oleh :

1. Variabel keluar basis (kondisi kelayakan) yaitu variabel paling negatif

2. Variabel masuk basis (kondisi optimalitas) yaitu variabel yang berkaitan dengan rasio

terkecil jika meminimumkan.

2.4 Integer Programming

Integer Programming adalah program linear (Linear Programming) di mana variabel

variabelnya bertipe integer. Integer Programming digunakan untuk memodelkan permasalahan

yang variable variabelnya tidak mungkin berupa bilangan yang tidak bulat (bilangan real),

seperti variabel yang merepresentasikan jumlah orang, karena jumlah orang pasti bulat dan tidak

mungkin berupa pecahan. Integer Programming juga biasanya lebih dipilih untuk memodelkan

suatu permasalahan karena program linear dengan variabel berupa bilangan real kurang baik

dalam memodelkan permasalahan yang menuntut solusi berupa bilangan integer.

2.5 Algoritma Branch and Bound

Algoritma Branch and Bound adalah metode algoritma umum untuk mencari solusi

optimal dari dari berbagai permasalahan optimasi, terutama untuk optimasi diskrit dan

kombinatorial. Sebagaimana pada algoritma runut-balik, algoritma Branch and Bound juga

merupakan metode pencarian di dalam ruang solusi secara sistematis. Ruang solusi

diorganisasikan ke dalam pohon ruang status. Yang membedakan keduanya adalah bila pada

algoritma runut-balik, ruang solusi dibangun secara dinamis berdasarkan skema DFS (Depth

First Search), maka pada algoritma Branch and Bound ruang solusi dibangun dengan skema

BFS (Breadth First Search).

Pada algoritma ini, permasalahan dibagi bagi menjadi subregion subregion yang

mungkin mengarah ke solusi. Inilah yang disebut dengan branching, mengingat prosedur ini

akan dilakukan berulang ulang secara rekursif untuk setiap subregion dan setiap subregion yang

dihasilkan akan membentuk sebuah struktur pohon yang disebut sebagai pohon pencarian atau

pohon branch-andbound di mana simpul simpulnya membangun subregion subregion. Selain

branching, algoritma ini juga melakukan apa yang disebut dengan bounding yang merupakan

cara cepat untuk mencari batas atas dan bawah untuk solusi optimal pada subregion yang

mengarah ke solusi.

BAB III

METODOLOGI PENELITIAN

3.1 Cara Penelitian

Langkah-langkah metode Branch dan Bound untuk masalah maksimasi dapat dilakukan seperti

berikut :

1. Selesaikan LP dengan metode simpleks biasa

2. Teliti solusi optimumnya. Jika variabel basis yang diharapkan bulat adalah bulat, solusi

optimum bulat telah tercapai.

3. Nilai solusi pecah yang layak dicabangkan ke dalam sub-sub masalah. Tujuannya adalah

untuk menghilangkan solusi kontinyu yang tidak memenuhi persyaratan bulat dalam

masalah itu.

4. Untuk setiap sub-masalah, nilai solusi optimum kontinyu fungsi tujuan ditetapkan

sebagai batas atas. Solusi bulat terbaik menjadi batas bawah (pada awalnya, ini adalah

solusi kontinyu yang dibulatkan ke bawah). Sub-sub masalah yang memiliki batas atas

kurang dari batas bawah yang ada, tidak diikut sertakan pada analisa selanjutnya. Suatu

solusi bulat layak adalah sama baik atau lebih baik dari batas atas untuk setiap sub

masalah yang dicari. Jika solusi yang demikian terjadi, suatu sub masalah dengan batas

atas terbaik dipilih untuk dicabangkan. Kembali ke langkah 3.

Untuk memperoleh gambaran yang lebih jelas tentang metode Branch dan Bound, perhatikan

contoh masalah berikut :

Maksimumkan Z = 3 X1 + 5 X2

Dengan syarat 2 X1 + 4 X2 ≤ 25 X1 ≤ 8 2 X2 ≤ 10 X1 ; X2 non

Solusi optimum kontinu masalah ini adalah X1 = 8, X2 = 2,26 dan Z = 35,25. Solusi ini

menunjukkan batas atas awal. Batas bawah adalah solusi yang dibulatkan ke bawah X1 = 8, X2

= 2 dan Z = 34. Dalam metode Branch dan Bound, masalah itu dibagi ke dalam dua bagian

untuk mencari nilai solusi bulat yang mungkin bagi X1 dan X2.Variabel dengan nilai solusi pecah

terbesar dipilih. Karena pada solusi ini hanya X2 yang memiliki bagian pecah, ia dipilih. Untuk

menghilangkan bagian pecah dari nilai X2 = 2,25, dua kendala baru dibuat.

Kendala-kendala ini mewakili dua bagian baru dari masalah itu. Dua nilai bulat terdekat

terhadap 2,25 adalah 2 dan 3. Sehingga diperoleh dua masalah baru melalui dua kendala

mutually exclusive, X2 ≤ 2 dan X2 ≥ 3, yang akan diuraikan berikut ini se-bagai bagian A dan B.

Kendala-kendala ini secara efektif menghi-langkan semua nilai pecah yang mungkin bagi X2,

antara 2 dan 3. Pengaruhnya mereka mengurangi ruang solusi layak sehingga angka solusi bulat

yang dievaluasi pada masalah ini makin sedikit.

Perhatikan bahwa:

Kemudian:

Bagian A dan B diselesaikan tanpa pembatasan bilangan bulat dengan metode simpleks. Solusi

simpleksnya adalah :

Bagian A : X1 = 8, X2 = 2 dan Z = 34

Bagian B : X1 = 6,5, X2 = 3 dan Z = 34,5

Ket :

Bagian A menghasilkan suatu solusi yang semuanya bulat. Untuk bagian A batas atas dan

bawah adalah Z = 34. Solusi pecah bagian B membenarkan pencarian lebih lanjut karena

menghasilkan nilai fungsi tujuan yang lebih besar dari batas atas bagian A. Sangat mungkin

bahwa pencarian lebih lanjut dapat menghasilkan suatu solusi yang semuanya bulat dengan nilai

fungsi tujuan melebihi batas atas bagian

A = 34.

Bagian B dicabangkan ke dalam dua sub bagian, B1 dan B2, pertama dengan kendala X1 ≤

6 dan yang lain dengan X2 ≥ 7.

Maka,

Diperoleh solusi simpleksnya adalah :

Sub-bagian B1 : X1 = 6, X2 = 3,25 dan Z = 34,25

Sub-bagian B2 : tidak layak.

Karena sub-bagian B1 menghasilkan nilai fungsi tujuan yang lebih besar dari 34 (batas atas

bagian A), maka harus dica-bangkan lagi ke dalam dua sub masalah, dengan kendala X2 ≤ 3 dan

X2 ≥ 4. Kedua kendala sub masalah diberi nama bagian B1a dan B2b.

Solusi optimum dengan metode simpleks adalah :

Sub-bagian B1a : X1 = 6, X2 = 3 dan Z = 33

Sub-bagian B1b : X1 = 4,25, X2 = 4 dan Z = 33,5

Kedua solusi itu memiliki batas atas ( Z = 33 dan Z = 33,5) yang lebih buruk dibanding dengan

solusi yang dihasilkan oleh bagian A. Karena itu, solusi bulat optimum adalah X1 = 8, X2 = 2 dan

Z = 34 yang dihasilkan oleh bagian A. Jika pencarian telah diselesaikan, solusi bulat dengan

fungsi tujuan tertinggi (dalam masalah maksimasi) dipilih sebagai solusi optimum.

Seluruh prosedur Branch dan Bound untuk contoh yang lalu dapat digambarkan seperti berikut :

Kelemahan dasar dari metode ini adalah bahwa diperlukan pemecahan masalah LP untuk

setiap pencabangan. Dalam masalah yang besar dapat memakan banyak waktu. Karena itu dalam

prosedur pencabangan dan pencarian, analisa selanjutnya dihentikan jika :

1. Hasil dari sub-problem lebih jelek dibanding dengan batas atas yang sudah

diidentifikasi

2. Pencabangan selanjutnya menghasilkan solusi tak layak.

Algoritma ini tetap menghitung kemungkinan solusi dengan tipe variable bilangan real

walaupun pada akhirnya kemungkinan solusi ini tidak akan dipertimbangkan. Tetapi hal ini

menyebabkan waktu komputasi bertambah lama.

BAB IV

JADWAL PENELITIAN

Tugas Akhir ini diharapkan dapat selesai menurut jadwal berikut :

Bulan

No Kegiatan BULAN KE 1 BULAN KE 2 BULAN KE 3

Minggu ke-

1 2 3 4 1 2 3 4 1 2 3 4

1 Memilih masalah x x x

2 Studi pendahuluan x x x

3 Merumuskan masalah x x

4 Menentukan sumber data x x

5 Mengumpulkan data x x x

6 Analisis data x x x

7 Menarik kesimpulan x x x

8 Penyusunan hasil penelitian x x x

9 Pelaporan hasil penelitian x x

BAB V

RENCANA ANGGARAN PENELITIAN

Rencana dari anggaran penelitian ini adalah :

1. Biaya transportasi Rp. 350.000

2. Biaya pembuatan laporan

Alat-alat tulis Rp. 50.000

Proposal penelitian Rp. 50.000

Skripsi Rp. 150.000

3. Biaya tak terduga Rp. 100.000

Jumlah Rp. 750.000

Curriculum Vitae

Nama : Dwi Haryaningsih

Tempat Tanggal Lahir : Ujung Batu II, 31 Desember 1991

Jenis Kelamin : Perempuan

Agama : Islam

Anak ke- : 2 daei 4 bersaudara

Alamat : Jl,Dr.M Hatta no.26 D, padang

Alamat Email : harya_dwiyanie@yahoo.co.id

Riwayat Pendidikan : 1997 – 2003 SDN ALIAGA II

2003 – 2006 SMP BAHARUDDIN

2006 – 2009 SMA BAHARUDDIN

2009 – sekarang Matematika Unand

Organisasi : HIMATIKA UNAND dan Forsilammsu

DAFTAR PUSTAKA

[1] Arya, W, 1985, Dinamik dan Integer Programming, BPFE, Yogyakarta.

[2] Dimyati,T. T, Ahmad Dimyati, 1992, Operation Research _ Model – model Pengambilan

Keputusan, Sinar Baru Algesindo, Bandung.

[3] Simarmata, Dj. A, 1982, Operation Research Sebuah Pengantar Teknik – teknik Optimasi

Kuantitatif dari Sistem – sistem Operasional, Gramedia, Jakarta.

[4] Taha, Hamdi.A, 1996, Riset Operasi Suatu Pengantar Jilid 1, Binarupa Aksara, Jakrta Barat.

[5] Winston.W, 1991, Operation Research Application and Algoritma 2nd Edition, New York.

Proposal Penelitian

Penerapan Metode Algoritma Branch and Bound untuk

Penyelesaian Optimal dari suatu Program Integer

DWI HARYANINGSIH

0910431019

Diajukan Sebagai Syarat untuk

Memenuhi Tugas Akhir Metode Penelitian

Jurusan Matematika

Fakultas Matematika dan Ilmu Pengetahuan Alam

Universitas Andalas

Padang

2012