branch and bound program linier

BAB I

PENDAHULUAN

Program linier merupakan suatu model umum yang dapat digunakan

dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara

optimal. Masalah tersebut timbul apabila seseorang diharuskan untuk memilih

atau menentukan tingkat setiap kegiatan yang akan dilakukannya, dimana masing-

masing kegiatan membutuhkan sumber yang sama sedangkan jumlahnya terbatas.

Banyak cara yang dapat dilakukan untuk menyelesaikan persoalan

program linier, diantaranya dengan menggunakan metode grafik, simpleks,

simpleks dua fase, antrian, penugasan, transportasi dan lain sebagainya. Setiap

metode hanya dapat digunakan pada persoalan tertentu sesuai dengan karakteristik

masing-masing metode. Seperti metode grafik yang hanya bisa digunakan untuk

persoalan program linier yang hanya mempunyai dua buah variabel, apabila lebih,

maka metode grafik tidak akan dapat menyelesaikannya. Sedangkan metode

simpleks merupakan teknik yang paling berhasil dikembangkan untuk

menyelesaikan persoalan program linier yang mempunyai jumlah variabel dan

pembatas yang banyak.

Contoh persoalan program linier yang terjadi :

Pemilik dari toko jual beli mesin merencanakan untuk mengadakan

perluasan dengan membeli beberapa mesin baru, yaitu mesin pencetak dan mesin

bubut. Pemilik menganggarkan bahwa tiap mesin pencetak akan menaikkan

keuntungan Rp 100.000,00 per hari dan tiap mesin bubut akan menaikkan

2

keuntungan Rp 150.000,00 per hari. Banyaknya jumlah mesin yang dapat dibeli

dibatasi dengan biaya mesin dan tersedianya ruang dalam toko. Harga beli mesin

dan luas tempat yang diperlukan untuk masing-masing mesin adalah sebagai

berikut :

Mesin Luas Tempat ( m2

) Harga Beli

Pencetak 15 Rp 8.000.000,00

Bubut 30 Rp 4.000.000,00

Anggaran pembelian mesin adalah sebesar Rp 40.000.000,00, sedangkan tempat

yang tersedia adalah 200 m2. Pemilik ingin mengetahui berapa banyak tiap jenis

mesin yang dapat dibeli untuk memaksimumkan kenaikan keuntungan perhari.

Persoalan di atas dapat diselesaikan dengan metode grafik ataupun metode

simpleks. Solusi yang dihasilkan dari kedua metode tersebut adalah keuntungan

maksimum yang diperoleh sebanyak Rp 1.056.000,00 dengan membeli 2,22

mesin pencetak dan 5,56 mesin bubut. Namun dalam kehidupan nyata, tidaklah

mungkin membeli 2,22 atau 5,56 mesin, melainkan harus membeli mesin dengan

jumlah yang bulat, bukan berupa pecahan. Oleh karena itu, harus ditentukan,

apakah akan membeli 2 atau 3 mesin pencetak dan 5 atau 6 mesin bubut.

Pembulatan jumlah produksi yang dilakukan sangat mempengaruhi keuntungan

yang diperoleh dan biaya yang dikeluarkan. Persoalan di atas harus diselesaikan

sedemikian rupa sehingga solusi bilangan bulat optimal dijamin tercapai.

Berdasarkan uraian di atas, diperoleh suatu rumusan masalah. Teknik

apakah yang dapat digunakan untuk memperoleh solusi bilangan bulat yang

optimal dari persoalan program linier ?

3

Memperhatikan masalah tersebut, penulis ingin memperkenalkan salah

satu teknik yang dianggap efisien dan efektif untuk mencari solusi bilangan bulat

yang optimal dari persoalan program linier, yaitu teknik Branch and Bound.

Teknik ini merupakan suatu pendekatan solusi yang layak digunakan

dalam menyelesaikan permasalahan program linier, khususnya bilangan bulat,

dengan membagi daerah solusi yang layak menjadi subset yang lebih kecil, untuk

selanjutnya dilakukan evaluasi secara sistematis terhadap subset tersebut sampai

solusi yang terbaik ditemukan.

Dari uraian di atas, penulis mencoba untuk mengangkat teknik Branch and

Bound untuk mendapatkan solusi bilangan bulat yang optimal dari persoalan

program linier.

4

BAB II

MATERI PENDUKUNG

2.1 Metode Simpleks

Metode simpleks merupakan prosedur aljabar yang bersifat iteratif

(pengulangan), yang bergerak selangkah demi selangkah, dimulai dari suatu titik

ekstrem pada daerah fisibel (ruang solusi) menuju ke titik ekstrem yang optimum.

Secara matematis, permasalahan program linier dapat ditulis sebagai

berikut :

Maks. atau min. : nn xcxcxcz ...2211

Berdasarkan :

nix

bxaxaxa

bxaxaxa

bxaxaxa

i

mnmnmm

nn

nn

,...2,1,0

....

.

.

.

....

....

2211

22222121

11212111

Jika kita defenisikan :

mnmm

n

n

aaa

aaa

aaa

A

...

.

.

.

...

...

21

22221

11211

;

nx

x

x

X

.

.

.

2

1

;

mb

b

b

B

.

.

.

2

1

Maka pembatas dari model tersebut dapat dituliskan ke dalam bentuk sistem

persamaan BAX

5

2.1.1. Langkah-langkah Penyelesaian

Berikut ini langkah-langkah penyelesaian persoalan program linier dengan

menggunakan metode simpleks :

a. Mengubah fungsi tujuan dan batasan-batasan

Fungsi tujuan diubah menjadi fungsi implisit, artinya semua nn xc

digeser ke ruas kiri persamaan. Pada bentuk standar, semua batasan

mempunyai tanda . Ketidaksamaan ini harus diubah menjadi kesamaan.

Caranya dengan menambahkan slack variable, yaitu variabel tambahan

yang mewakili tingkat pengangguran atau kapasitas yang merupakan

batasan. Slack variable ini adalah ,, 21 nn xx . . . , mnx .

b. Menyusun persaman-persamaan di dalam tabel

Setelah fungsi tujuan dan batasan diubah, kemudian disusun ke

dalam tabel, dalam bentuk simbol seperti tampak pada tabel berikut :

Tabel Simpleks dalam Bentuk Simbol

Variabel

Dasar Z 1x 2x ... nx 1nx 2nx ... mnx NK

Z 1 -c1 -c2 ... -cn 0 0 ... 0 0

1nx 0 11a 12a ... na1 1 0 ... 0 1b

2nx 0 21a 22a ... na2 0 1 ... 0 2b

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

.

mnx 0 1ma 2ma ... mna 0 0 ... 1 mb

Keterangan :

m = jenis batasan-batasan sumber/fasilitas yang tersedia

6

n = jenis batasan-batasan kegiatan yang menggunakan sumber/fasilitas

tersebut

i = nomor setiap sumber/fasilitas yang tersedia (1 sampai dengan m)

j = nomor setiap jenis kegiatan yang menggunakan sumber/fasilitas

(1 sampai dengan n)

jx = tingkat kegiatan ke-j

ija = banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit

keluaran/output kegiatan j

ib = banyaknya sumber/fasilitas yang tersedia untuk dialokasikan ke

setiap unit kegiatan (1 sampai dengan m)

Z = nilai yang dioptimalkan

Cj = kenaikan nilai Z apabila ada pertambahan kegiatan ( jx ) dengan satu

satuan/unit/merupakan sumbangan setiap satuan keluaran kegiatan

ke-j terhadap nilai Z

NK = nilai yang berada di sebelah kanan tanda sama dengan

c. Memilih kolom kunci

Cara menentukan kolom kunci adalah dengan memilih kolom yang

mempunyai nilai negatif dengan angka terbesar pada baris fungsi tujuan.

d. Menentukan nilai indeks pada tiap-tiap baris

Nilai indeks tiap-tiap baris ditentukan dengan cara membagi nilai-

nilai pada kolom NK dengan nilai yang sebaris dengan kolom kunci, atau :

kuncikolomnilai

NKkolomnilaiIndeks

7

e. Memilih baris kunci

Baris kunci adalah baris yang mempunyai indeks positif dengan

angka terkecil.

f. Menentukan angka kunci

Angka kunci adalah angka yang termasuk dalam kolom kunci dan

juga termasuk pada baris kunci dinamakan angka kunci.

g. Mengubah nilai-nilai baris kunci

Nilai baris kunci diubah dengan cara membaginya dengan angka

kunci.

h. Mengubah nilai-nilai selain pada baris kunci

Nilai-nilai baris yang lain, selain pada baris kunci dapat diubah

dengan rumus sebagai berikut :

Baris baru = baris lama – (koefisien pada kolom kunci x nilai baru baris

kunci)

i. Melanjutkan perbaikan-perbaikan / perubahan-perubahan

Ulangi langkah-langkah perbaikan mulai langkah ke-c sampai

langkah ke-f untuk memperbaiki tabel yang telah diubah/diperbaiki

nilainya. Perubahan baru berhenti setelah pada baris pertama (baris fungsi

tujuan) tidak ada lagi yang bernilai negatif.

2.1.2. Bentuk-bentuk Penyimpangan

Pada penyelesaian persoalan program linier yang menggunakan metode

simpleks, terdapat beberapa penyimpangan dari bentuk standar, diantaranya

adalah sebagai berikut :

8

a. Batasan dengan tanda sama dengan (=)

Batasan dari persoalan program linier yang bertanda sama dengan

(=) harus diubah agar sesuai dengan bentuk standar, sehingga dapat

diselesaikan dengan menggunakan metode simpleks. Caranya adalah

dengan menambahkan variabel buatan (artivicial variable) yang bernilai

positif, yang dilambangkan dengan ,1nx 2nx , …

Sebelum variabel buatan masuk, batasan sudah berbentuk

persamaan, setelah variabel buatan masuk, masih berbentuk persamaan.

Akibatnya, timbul syarat agar tetap sesuai dengan persamaan semula,

maka variabel buatan harus bernilai nol (0).

Variabel buatan yang ditambahkan hanya merupakan syarat supaya

algoritma metode simpleks dapat berjalan. Sebagai usaha agar variabel

buatan segera bernilai nol (0), maka disusunlah fungsi tujuan baru dengan

bentuk 1 nxMzz dimana M adalah bilangan positif yang sangat besar

tapi tak terhingga. Dengan demikian diharapkan agar variabel buatan

segera keluar dari kolom variabel dasar karena koefisiennya bernilai

negatif yang sangat besar.

b. Minimasi

Fungsi tujuan dari persoalan program linier yang bersifat minimasi

harus diubah menjadi maksimasi, agar sesuai dengan bentuk standar, yaitu

maksimasi., sehingga dapat diselesaikan dengan menggunakan metode

simpleks. Caranya adalah dengan mengganti tanda positif dan negatif pada

fungsi tujuan, sebagai berikut :

9

Minimumkan

n

j

jj xcZ1

berubah menjadi :

Maksimumkan

n

j

jj xcZ1

Contoh :

Minimumkan : 21 53 xxZ diubah menjadi :

Maksimumkan: 21 53 xxZ

c. Fungsi pembatas bertanda lebih dari atau sama dengan ( )

Bila suatu fungsi pembatas bertanda , maka harus diubah

menjadi agar sesuai dengan bentuk standar dengan pembata bertanda ,

sehingga metode simpleks dapat berjalan. Hal ini dilakukan dengan jalan

mengubah tanda tiap-tiap koefisien dari positif menjadi negatif dan

sebaliknya. Selanjutnya, pertidaksamaan diubah menjadi persamaan

(bertanda =) dengan menambahkan slack variable, agar dapat diselesaikan

dengan metode simpleks.

d. Bagian kanan persamaan bertanda negatif

Bila di bagian kanan persamaan bertanda negatif, maka harus

diubah menjadi positif, kemudian ditambah dengan variabel buatan

(artivicial variable). Variabel buatan yang ditambahkan haruslah bernilai

positif.

2.2 Program Linier Relaksasi

Program linier relaksasi adalah bentuk program linier yang diperoleh

dengan mengabaikan pembatas bilangan bulat. Contoh : Pemilik dari toko jual

10

beli mesin merencanakan untuk mengadakan perluasan dengan membeli beberapa

mesin baru, yaitu mesin pencetak dan mesin bubut. Pemilik menganggarkan

bahwa tiap mesin pencetak akan menaikkan keuntungan Rp 100.000,00 per hari

dan tiap mesin bubut akan menaikkan keuntungan Rp 150.000,00 per hari.

Banyaknya jumlah mesin yang dapat dibeli dibatasi dengan biaya mesin dan

tersedianya ruang dalam toko. Harga beli mesin dan luas tempat yang diperlukan

untuk masing-masing mesin adalah sebagai berikut :


) Harga Beli

Pencetak 15 Rp 8.000.000,00

Bubut 30 Rp 4.000.000,00

Anggaran pembelian mesin adalah sebesar Rp 40.000.000,00, sedangkan tempat

yang tersedia adalah 200 m2. Pemilik ingin mengetahui berapa banyak tiap jenis

mesin yang dapat dibeli untuk memaksimumkan kenaikan keuntungan perhari.

Pada persoalan di atas, tidak akan mungkin membeli mesin pencetak dan

mesin bubut dengan jumlah pecahan. Oleh karena itu, model matematis untuk

persoalan diatas adalah :

Memaksimumkan : 21 000.150000.100 xxz

Berdasarkan : 000.000.40000.000.4000.000.8 21 xx

2003015 21 xx

0, 21 xx ; 21 , xx bilangan bulat

Program linier relaksasi dari model matematis pada persoalan program linier di

atas adalah :

Maksimumkan: 21 000.150000.100 xxz

11

Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

(3) 0, 21 xx

12

BAB III

PEMBAHASAN

Teknik Branch and Bound merupakan teknik solusi untuk persoalan

program linier yang mengharuskan variabelnya berupa bilangan bulat. Prinsip

yang mendasari teknik ini adalah bahwa total set solusi yang fisibel dapat dibagi

menjadi subset-subset solusi yang lebih kecil. Subset-subset ini selanjutnya dapat

dievaluasi secara sistematis sampai solusi yang terbaik ditemukan. Teknik Branch

and Bound pada persoalan program linier digunakan bersama-sama dengan

metode simpleks.

Teknik ini menggunakan suatu diagram yang terdiri dari node dan cabang

(branch) sebagai suatu kerangka dalam proses pemerolehan solusi optimal.

Masing-masing node memuat solusi program linier relaksasi sesuai dengan fungsi

tujuan dan batasannya. Node pertama akan memuat solusi program linier relaksasi

dari persoalan yang diberikan. Node kedua, ketiga, keempat, dan seterusnya

memuat solusi program linier relaksasi dari persoalan yang diberikan ditambah

dengan batasan yang terdapat pada masing-masing cabangnya.

3.1 Algoritma Teknik Branch and Bound

Langkah-langkah penggunaan teknik Branch and Bound adalah sebagai

berikut :

a. Dapatkan solusi simpleks optimal dari program linier relaksasi yang

bersangkutan.

13

b. Solusi yang dihasilkan pada langkah a dinyatakan sebagai batas atas

(upper bound) dan pembulatan ke bawah sebagai batas bawah (lower

bound) pada node 1

c. Pilihlah variabel dengan pecahan yang terbesar untuk pencabangan

(branch). Ciptakan dua batasan baru untuk variabel ini. Hasilnya adalah

sebuah batasan dan sebuah batasan .

d. Ciptakan dua node baru, satu dengan batasan dan satu dengan

batasan

e. Selesaikan model program linier relaksasi dengan batasan baru yang

ditambahkan pada tiap node

f. Solusi simpleks relaksasi adalah merupakan batas atas pada tiap node, dan

solusi bilangan bulat maksimum yang ada (pada node mana saja) adalah

merupakan batas bawah

g. Jika proses ini menghasilkan solusi bilangan bulat fisibel dengan nilai

batas atas pada akhir node mana saja, maka solusi bilangan bulat optimal

telah tercapai. Jika tidak muncul solusi bilangan bulat fisibel, lakukan

pencabangan dari node dengan batas atas terbesar

3.2 Contoh Penerapan

Persoalan :

Pemilik dari toko jual beli mesin merencanakan untuk mengadakan

perluasan dengan membeli beberapa mesin baru, yaitu mesin pencetak dan mesin

bubut. Pemilik menganggarkan bahwa tiap mesin pencetak akan menaikkan

keuntungan Rp 100.000,00 per hari dan tiap mesin bubut akan menaikkan

14

keuntungan Rp 150.000,00 per hari. Banyaknya jumlah mesin yang dapat dibeli

dibatasi dengan biaya mesin dan tersedianya ruang dalam toko. Harga beli mesin

dan luas tempat yang diperlukan untuk masing-masing mesin adalah sebagai

berikut :


) Harga Beli

Pencetak 15 Rp 8.000.000,00

Bubut 30 Rp 4.000.000,00

Anggaran pembelian mesin adalah sebesar Rp 40.000.000,00, sedangkan

tempat yang tersedia adalah 200 m2. Pemilik ingin mengetahui berapa banyak tiap

jenis mesin yang dapat dibeli untuk memaksimumkan kenaikan keuntungan

perhari.

Penyelesaian :

Model matematis untuk persoalan diatas adalah :

Memaksimumkan : 21 000.150000.100 xxz

Berdasarkan : 000.000.40000.000.4000.000.8 21 xx

2003015 21 xx

0, 21 xx ; 21 , xx bilangan bulat

Langkah 1. Mencari solusi optimal dari program linier relaksasi yang

bersangkutan

Persoalan di atas diubah menjadi program linier relaksasi sehingga :


Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

15

(3) 0, 21 xx

Persoalan yang telah dinyatakan dalam bentuk model matematis seperti di atas

diselesaikan dengan menggunakan metode simpleks, yaitu :

a. mengubah fungsi tujuan dan batasan

Batasan (1) harus ditambah dengan sebuah slack variable x3, sehingga :

000.000.40000.000.4000.000.8 321 xxx


2003015 421 xxx

Fungsi tujuan diubah menjadi :

0000.150000.100 21 xxz

b. menyusun persamanan-persamaan di dalam tabel

Fungsi tujuan dan batasan yang telah diubah disusun dalam tabel simpleks

berikut:

Tabel A. Solusi Simpleks Relaksasi pada Node 1

Varibel

Dasar z x1

x2 x3 x4 NK Indeks

z 1 -100.000 -150.000 0 0 0

x3 0 8.000.000 4.000.000 1 0 40.000.000 10

x4 0 15 30* 0 1 200 6,67

c. memilih kolom kunci

Kolom kunci pada tabel di atas adalah kolom yang mempunyai nilai

negatif dengan angka terbesar pada baris fungsi tujuan, yaitu kolom x2 dengan

nilai -150.000.

d. menentukan nilai indeks pada tiap-tiap baris

Nilai indeks pada masing-masing baris ditentukan dengan rumus :

16

- -25.000 0 0 49.500 1.000.500

kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 40.000.000 : 4.000.000 = 10

Indeks baris x4 = 200 : 30 = 6,67

e. memilih baris kunci

Karena nilai indeks positif dengan angka terkecil terdapat pada baris x4,

maka baris x4 dinyatakan sebagai baris kunci.

f. menentukan angka kunci

Angka kunci pada tabel di atas adalah 30, karena merupakan nilai yang

termasuk kolom kunci sekaligus baris kunci.

g. mengubah nilai-nilai baris kunci

Baris kunci x4 diubah dengan cara membagi angka-angkanya dengan

angka kunci yang telah ditentukan (30)

Kolom x1 baris x4 = 15 : 30 = 0,5

Kolom x2 baris x4 = 30 : 30 = 1

Kolom x3 baris x4 = 0 : 30 = 0

Kolom x4 baris x4 = 1 : 30 = 0,033

Kolom NK baris x4 = 200 : 30 = 6,67

h. mengubah nilai-nilai selain pada baris kunci

Angka-angka pada kolom z tidak mengalami perubahan

Baris fungsi tujuan z diubah dengan rumus :

Baris baru = baris lama – (koefisien pada kolom kunci x nilai baru baris kunci)

-100.000 -150.000 0 0 0

-150.000 0,5 1 0 0,33 6,67

Koefisien

Baris lama

Nilai baru

Baris kunci

17

- 6.000.000 0 1 -1.320.000 13.320.000

Baris fungsi x3 diubah dengan rumus :


8.000.000 4.000.000 1 0 40.000.000

4.000.000 0,5 1 0 0,33 6,67

i. melanjutkan perbaikan-perbaikan/perubahan-perubahan

Karena kolom kunci adalah kolom x2 dan baris kunci adalah baris x4, maka

x2 masuk ke dalam variabel dasar menggantikan x4, sehingga tabel A akan

berubah menjadi :

Tabel B. Solusi Simpleks Relaksasi pada Node 1

Varibel

Dasar z

x1 x2 x3 x4 NK Indeks

z 1 -25.000 0 0 49.500 1.000.500

x3 0 6.000.000* 0 1 -1.320.000 13.320.000 2,22

x2 0 0,5 1 0 0,033 6,67 13,34

memilih kolom kunci



nilai -25.000.

menentukan nilai indeks pada tiap-tiap baris


kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 13.320.000 : 6.000.00 = 2,22

Indeks baris x2 = 6,67 : 0,5 = 13,34

Koefisien

Baris lama

Nilai baru

Baris kunci

18

-

memilih baris kunci



menentukan angka kunci

Angka kunci pada tabel di atas adalah 6.000.000, karena merupakan nilai

yang termasuk kolom kunci sekaligus baris kunci.

mengubah nilai-nilai baris kunci


angka kunci yang telah ditentukan (6.000.000)

Kolom x1 baris x3 = 6.000.000 : 6.000.000 = 1

Kolom x2 baris x3 = 0 : 6.000.000 = 0

Kolom x3 baris x3 = 1 : 6.000.000 = 0,00000017 = 0

Kolom x4 baris x3 = -1.320.000 : 6.000.000 = -0,22

Kolom NK baris x3 = 13.320.000 : 6.000.000 = 2,22

mengubah nilai-nilai selain pada baris kunci




-25.000 0 0 49.500 1.000.500

-25.000 1 0 0 -0,22 2,22

0 0 0 44.000 1.056.000

Koefisien

Baris lama

Nilai baru

Baris kunci

19

- 0 1 0 0,143 5,56

Baris x2 diubah dengan rumus :


0,5 1 0 0,033 6,67

0,5 1 0 0 -0,22 2,22


x1 masuk ke dalam variabel dasar menggantikan x3, sehingga tabel B akan

berubah menjadi :

Tabel C. Solusi Optimal Simpleks Relaksasi pada Node 1

Varibel

Dasar Z x1 x2 x3 x4 NK Indeks

Z 1 0 0 0 44.000 1.056.000

x1 0 1 0 0 -0,22 2,22

x2 0 0 1 0 0,143 5,56

Pada tabel C, seluruh eleman pada baris fungsi tujuan telah bernilai positif.

Hal ini berarti bahwa perbaikan yang dilakukan sudah merupakan hasil optimal,

sehingga tidak perlu lagi dilakukan upaya perbaikan. Nilai optimal yang

dihasilkan adalah fungsi tujuan z yang maksimum yaitu 1.056.000 dengan

22,21 x dan 56,52 x .

Langkah 2. Mennyatakan solusi persoalan program linier relaksasi sebagai

batas atas (upper bound) dan pembulatan ke bawah sebagai

batas bawah (lower bound) pada node 1

Dari tabel C solusi optimal simpleks relaksasi pada node 1, diperoleh:

a. batas atas 1.056.000 dengan 22,21 x dan 56,52 x

b. batas bawah 950.000 dengan 21 x dan 52 x

Koefisien

Baris lama

Nilai baru

Baris kunci

20

Langkah 3. Memilih variabel dengan pecahan yang terbesar untuk

pencabangan (branch) dan menciptakan dua batasan baru

Pada langkah 2, diketahui bahwa x1 memiliki pecahan sebesar 0,22 dan x2

memiliki pecahan sebesar 0,56. Bagian pecahan x2 lebih besar dari x1. Oleh karena

itu, x2 akan menjadi variabel yang diberi cabang sehingga diperoleh dua batasan

baru yang dikembangkan dari x2, yaitu : 52 x dan 62 x .

Langkah 4. Menciptakan dua node baru, satu dengan batasan dan satu

dengan batasan

Berdasarkan langkah 3, maka diperoleh dua node baru, seperti tampak pada

gambar berikut :

Langkah 5. Menyelesaikan model program linier relaksasi dengan batasan

baru yang ditambahkan pada tiap node

NODE 2


Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

(3) 52 x

(4) 0, 21 xx

BA = 1.056.000 ( 22,21 x , 56,52 x )

BB = 950.000 ( 21 x , 52 x )

Node 1

1.056.000

Node 2 Node 3

52 x 62 x

21

Persoalan yang telah dinyatakan dalam bentuk model matematis seperti di

atas diselesaikan dengan menggunakan metode simpleks, yaitu :



000.000.40000.000.4000.000.8 321 xxx


2003015 421 xxx

Batasan (3) harus ditambah dengan sebuah slack variable x5 , sehingga :

552 xx

Fungsi tujuan diubah menjadi :

0000.150000.100 21 xxz



berikut:


Varibel

Dasar z x1 x2 x3 x4 x5 NK Indeks

z 1 -100.000 -150.000 0 0 0 0

x3 0 8.000.000 4.000.000 1 0 0 40.000.000 10

x4 0 15 30 0 1 0 200 6,67

x5 0 0 1* 0 0 1 5 5




nilai -150.000.

22



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 40.000.000 : 4.000.000 = 10

Indeks baris x4 = 200 : 30 = 6,67

Indeks baris x5 = 5 : 1 = 5















Kolom NK baris x5 = 5 : 1 = 5

23

-

- 8.000.000 0 1 0 -4.000000 20.000.000

- 15 0 0 1 -30 50





-100.000 -150.000 0 0 0 0

-150.000 0 1 0 0 1 5

-100.000 0 0 0 150.000 750.000



8.000.000 4.000.000 1 0 0 40.000.000

4.000.000 0 1 0 0 1 5



15 30 0 1 0 200

30 0 1 0 0 1 5




berubah menjadi :


Varibel

Dasar z

x1 x2 x3 X4 x5 NK Indeks

z 1 -100.000 0 0 0 150.000 750.000

x3 0 8.000.000* 0 1 0 -4.000.000 20.000.000 2,5

x4 0 15 0 0 1 -30 50 3,33

x2 0 0 1 0 0 1 5

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

24

memilih kolom kunci



nilai -100.000.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 20.000.000 : 8.000.00 = 2,5

Indeks baris x4 = 50 : 15 = 3,33

Indeks baris x2 = 5 : 0 =

memilih baris kunci




Angka kunci pada tabel di atas adalah 8.000.000, karena merupakan nilai

yang termasuk kolom kunci sekaligus baris kunci.



angka kunci yang telah ditentukan (8.000.000)

Kolom x1 baris x3 = 8.000.000 : 8.000.000 = 1

Kolom x2 baris x3 = 0 : 8.000.000 = 0

Kolom x3 baris x3 = 1 : 8.000.000 = 0,0000001 = 0

25

-

-

-

Kolom x4 baris x3 = 0 : 8.000.000 = 0

Kolom x5 baris x3 = -4.000.000 : 8.000.000 = -0,5

Kolom NK baris x3 = 20.000.000 : 6.000.000 = 2,5





-100.000 0 0 0 150.000 750.000

-100.000 1 0 0 0 -0,5 2,5

0 0 0 0 100.000 1.000.000



15 0 0 1 -30 50

15 1 0 0 0 -0,5 2,5

0 0 0 1 -22,5 12,5



0 1 0 0 1 5

0 1 0 0 0 -0,5 2,5

0 1 0 0 1 5



berubah menjadi :

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

26


Varibel

Dasar z x1 x2 x3 x4 x5 NK Indeks

z 1 0 0 0 0 100.000 1.000.000

x1 0 1 0 0 0 -0,5 2,5

x4 0 0 0 0 1 -22,5 12,5

x2 0 0 1 0 0 1 5

Pada tabel C, seluruh eleman pada baris fungsi tujuan tidak ada lagi yang

benilai negatif. Hal ini berarti bahwa perbaikan yang dilakukan sudah merupakan

hasil optimal, sehingga tidak perlu lagi dilakukan upaya perbaikan. Nilai optimal

yang dihasilkan adalah fungsi tujuan z yang maksimum yaitu 1.000.000 dengan

5,21 x dan 52 x .

Dari tabel C solusi optimal simpleks relaksasi pada node 2, diperoleh:

a. batas atas 1.000.000 dengan 5,21 x dan 52 x

b. batas bawah 950.000 dengan 21 x dan 52 x

NODE 3


Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

(3) 62 x

(4) 0, 21 xx



27



000.000.40000.000.4000.000.8 321 xxx


2003015 421 xxx

Batasan (3) harus diubah menjadi :

6

6

6

52

52

2

xx

xx

x

Karena x5 bernilai negatif, maka bukanlah variabel dasar, sehingga perlu

ditambah artivicial variable 6x , maka :

6652 xxx

Dengan memperhatikan perubahan fungsi tujuan karena batasan (3), maka fungsi

tujuan diubah menjadi :

0000.150000.100 621 xMxxz

Untuk mengubah agar nilai 6x pada batasan menjadi 0, maka dilakukan

pengurangan-pengurangan sebagai berikut :

1 -100.000 -150.000 0 0 0 M 0

0 0 1 0 0 -1 1 6

1 -100.000 -150.000-M 0 0 M 0 -6M

Sehingga fungsi tujuan menjadi :

MMxxMxz 6000.150000.100 521



berikut:

-M

---- dikalikan dengan (-1)

…… ditambahkan slack variable x5

...... dikalikan dengan (-1)

28


Variabel

Dasar z x1

x2 x3 x4 x5 6x NK Indeks

z 1 -100.000 -150.000-M 0 0 M 0 -6M

x3 0 8.000.000 4.000.000 1 0 0 0 40.000.000 10

x4 0 15 30 0 1 0 0 200 6,67

6x 0 0 1* 0 0 -1 1 6 6




nilai -150.000-M.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 40.000.000 : 4.000.000 = 10

Indeks baris x4 = 200 : 30 = 6,67

Indeks baris 6x = 6 : 1 = 6


Karena nilai indeks positif dengan angka terkecil terdapat pada baris 6x ,

maka baris 6x dinyatakan sebagai baris kunci.




29

-

- 8.000.000 0 1 0 4.000.000 -4.000.000 16.000.000


Baris kunci 6x diubah dengan cara membagi angka-angkanya dengan


Kolom x1 baris 6x = 0 : 1 = 0




Kolom x5 baris 6x = -1 : 1 = -1

Kolom 6x baris

6x = 1 : 1 = 1

Kolom NK baris 6x = 6 : 1 = 6





-100.000 -150.000-M 0 0 M 0 -6M

-150.000-M 0 1 0 0 -1 1 6

-100.000 0 0 0 -150.000 150.00+M 900.000



8.000.000 4.000.000 1 0 0 0 40.000.000

4.000.000 0 1 0 0 -1 1 6

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

30

- 15 0 0 1 30 -30 20



15 30 0 1 0 0 200

30 0 1 0 0 -1 1 6


Karena kolom kunci adalah kolom x2 dan baris kunci adalah baris 6x ,

maka x2 masuk ke dalam variabel dasar menggantikan 6x , sehingga tabel A akan

berubah menjadi :


Variabel

Dasar Z x1 x2 x3 x4 X5

6x NK Indeks

z 1 -100.000 0 0 0 -150.000 150.000+M 900.000

x3 0 8.000.000 0 1 0 4.000.000 -4.000.000 16.000.000 4

x4 0 15 0 0 1 30* -30 20 0,67

x2 0 0 1 0 0 -1 1 6 -6

memilih kolom kunci



nilai -150.000.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 16.000.000 : 4.000.00 = 4

Koefisien

Baris lama

Nilai baru

Baris kunci

31

Indeks baris x4 = 20 : 30 = 0,67

Indeks baris x2 = 6 : -1 = -6

memilih baris kunci









Kolom x1 baris x4 = 15 : 30 = 0,5



Kolom x4 baris x4 = 1 : 30 = 0,033

Kolom x5 baris x4 = 30 : 30 = 1

Kolom 6x baris

6x = -30 : 30 = -1

Kolom NK baris x4 = 20 : 30 = 0,67





32

-

-

-

-100.000 0 0 0 - 150.000 150.000+M 900.000

-150.000 0,5 0 0 0,033 1 -1 0,67

-25.000 0 0 4.950 0 M 1.000.500



8.000.000 0 1 0 4.000.000 -4.000.000 16.000.000

4.000.000 0,5 0 0 0,033 1 -1 0,67

6.000.000 0 1 -132.000 0 0 13.320.000



0 1 0 0 -1 1 6

-1 0,5 0 0 0,033 1 -1 0,67

0,5 1 0 0,033 0 0 6,67



berubah menjadi :

Tabel C. Solusi Simpleks Relaksasi pada Node 3

Variabel

Dasar z x1 x2 x3 x4 X5 6x NK Indeks

z 1 -25.000 0 0 4.950 0 M 1.000.500

x3 0 6.000.0000 0 1 -132.000 0 0 13.320.000 2,22

x5 0 0,5* 0 0 0,033 1 -1 0,67 1,34

x2 0 0,5 1 0 0,033 0 0 6,67 13,34

memilih kolom kunci



nilai -25.000.

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

33



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 13.500.000 : 6.000.000 = 2,25

Indeks baris x4 = 0,67 : 0,5 = 1,34

Indeks baris x2 = 6,67 : 0,5 = 13,34

memilih baris kunci




Angka kunci pada tabel di atas adalah 0,5, karena merupakan nilai yang




angka kunci yang telah ditentukan (0,5)

Kolom x1 baris x5 = 0,5 : 0,5 = 1

Kolom x2 baris x5 = 0 : 0,5 = 0

Kolom x3 baris x5 = 0 : 0,5 = 0

Kolom x4 baris x5 = 0,033 : 0,5 = 0,066

Kolom x5 baris x5 = 1 : 0,5 = 2

Kolom 6x baris x5 = -1 : 0,5 = -2

Kolom NK baris x4 = 0,67 : 0,5 = 1,34

34

-

-

-





-25.000 0 0 4.950 0 M 1.000.500

-25.000 1 0 0 0,066 2 -2 1,34

0 0 0 6.600 50.000 M-50.000 1.034.000



6.000.000 0 1 -132.000 0 0 13.320.000

6.000.000 1 0 0 0,066 2 -2 1,34

0 0 1 -528.000 -12.000.000 12.000.000 5.280.000



0,5 1 0 0,033 0 0 6,67

0,5 1 0 0 0,066 2 -2 1,34

0 0 0 0 -1 1 6


x1 masuk ke dalam variabel dasar menggantikan x5, sehingga tabel C akan

berubah menjadi :

Tabel D. Solusi Optimal Simpleks Relaksasi pada Node 3

Variabel

Dasar z X1 x2 x3 X4 x5 6x NK Indeks

z 1 0 0 0 6.600 50.000 M-50.000 1.034.000

x3 0 0 0 1 -528.000 -12.000.000 12.000.000 5.280.000

x1 0 1 0 0 0,066 2 -2 1.34

x2 0 0 0 0 0 -1 1 6

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Baris lama

Koefisien

Nilai baru

Baris kunci

35

Pada tabel D, seluruh eleman pada baris fungsi tujuan tidak ada lagi yang

bernilai negatif. Hal ini berarti bahwa perbaikan yang dilakukan sudah merupakan



34,11 x dan 62 x .

Dari tabel D solusi optimal simpleks relaksasi pada node 3, diperoleh:

a. batas atas 1.034.000 dengan 34,11 x dan 62 x

b. batas bawah 1.000.000 dengan 11 x dan 62 x

Mengingat bahwa belum diperoleh suatu solusi bilangan bulat yang layak

dan optimal, maka harus dibuat cabang dari salah satu antara node 2 atau node 3.

Dengan memperhatikan tabel C solusi optimal simpleks relaksasi pada node 2

terlihat bahwa jika membuat cabang dari node 2, maka nilai maksimum yang

mungkin dapat dicapai adalah 1.000.000 (batas atas). Namun, jika membuat

cabang dari node 3, nilai maksimum yang mungkin dicapai adalah 1.034.000

(batas atas). Oleh karena itu, kita akan membuat cabang dari node 3.

Pertama, dipilih variabel yang memiliki bagian pecahan terbesar. Karena

x2 memiliki nilai berupa bilangan bulat, maka x1 dengan bagian pecahan sebesar

0,34 adalah satu-satunya variabel yang dipilih. Jadi, dua batasan baru

dikembangkan dari x1, yaitu : 11 x dan 21 x . Sehingga diperoleh dua node

baru yang merupakan cabang dari node 3, seperti tampak pada gambar berikut :

36

NODE 4


Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

(3) 62 x

(4) 11 x

(5) 0, 21 xx





000.000.40000.000.4000.000.8 321 xxx

Node 1

1.056.000

BA = 1.056.000 ( 22,21 x , 56,52 x )

BB = 950.000 ( 21 x , 52 x )

Node 2

1.000.000

Node 3

1.034.000

52 x 62 x

Node 4 Node 5

11 x 21 x

BA = 1.034.000 ( 34,11 x 62 x )

BB = 1.000.000 ( 11 x , 62 x )

BA = 1.000.000 ( 5,21 x 52 x )

BB = 950.000 ( 21 x 52 x )

37


2003015 421 xxx


6

6

6

52

52

2

xx

xx

x



6652 xxx


171 xx



0000.150000.100 621 xMxxz



1 -100.000 -150.000 0 0 0 M 0 0

0 0 1 0 0 -1 1 0 6

1 -100.000 -150.000-M 0 0 M 0 0 -6M


MMxxMxz 6000.150000.100 521



berikut:

-M




38


Variabel

Dasar z x1 x2 x3 x4 x5

6x x7 NK Indeks

z 1 -100.000 -150.000-M 0 0 M 0 0 -6M

x3 0 8.000.000 4.000.000 1 0 0 0 0 40.000.000 10

x4 0 15 30 0 1 0 0 0 200 6,67

6x 0 0 1* 0 0 -1 1 0 6 6

x7 0 1 0 0 0 0 0 1 1




nilai -150.000-M.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 40.000.000 : 4.000.000 = 10

Indeks baris x4 = 200 : 30 = 6,67









39

-

-








Kolom x5 baris 6x = -1 : 1 = -1

Kolom 6x baris

6x = 1 : 1 = 1







-100.000 -150.000-M 0 0 M 0 0 -6M

-150.000-M 0 1 0 0 -1 1 0 6

-100.000 0 0 0 -150.000 150.00+M 0 900.000



8.000.000 4.000.000 1 0 0 0 0 40.000.000

4.000.000 0 1 0 0 -1 1 0 6

8.000.000 0 1 0 4.000.000 -4.000.000 0 16.000.000

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

40

-

-



15 30 0 1 0 0 0 2 00

30 0 1 0 0 -1 1 0 6

15 0 0 1 30 -30 0 20



1 0 0 0 0 0 1 1

0 0 1 0 0 -1 1 0 6

1 0 0 0 0 0 1 1




berubah menjadi :


Variabel

Dasar z x1 x2 x3 x4 x5 6x x7 NK Indeks

z 1 -100.000 0 0 0 -150.000 150.000+M 0 900.000

x3 0 8.000.000 0 1 0 4.000.000 -4.000.000 0 16.000.000 4

x4 0 15 0 0 1 30* -30 0 20 0,67

x2 0 0 1 0 0 -1 1 0 6 -6

x7 0 1 0 0 0 0 0 1 1

memilih kolom kunci



nilai -150.000.

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

41



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 16.000.000 : 4.000.00 = 4

Indeks baris x4 = 20 : 30 = 0,67



memilih baris kunci









Kolom x1 baris x4 = 15 : 30 = 0,5



Kolom x4 baris x4 = 1 : 30 = 0,033

Kolom x5 baris x4 = 30 : 30 = 1

Kolom 6x baris

6x = -30 : 30 = -1

42

-

-

-

-


Kolom NK baris x4 = 20 : 30 = 0,67





-100.000 0 0 0 -150.000 150.00+M 0 900.000

-150.000 0,5 0 0 0,033 1 -1 0 0,67

-25.000 0 0 4.950 0 M 0 1.000.500



8.000.000 0 1 0 4.000.000 -4.000.000 0 16.000.000

4.000.000 0,5 0 0 0,033 1 -1 0 0,67

6.000.000 0 1 -132.000 0 0 0 13.320.000



0 1 0 0 -1 1 0 6

-1 0,5 0 0 0,033 1 -1 0 0,67

0,5 1 0 0,033 0 0 0 6,67



1 0 0 0 0 0 1 1

0 0,5 0 0 0,033 1 -1 0 0,67

1 0 0 0 0 0 1 1

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

43



berubah menjadi :


Variabel

Dasar z

x1 x2 x3 x4 x5 6x x7 NK Indeks

z 1 -25.000 0 0 4.950 0 M 0 1.000.500

x3 0 6.000.000 0 1 -132.000 0 0 0 13.320.000 2,22

x5 0 0,5 0 0 0,033 1 -1 0 0,67 1,34

x2 0 0,5 1 0 0,033 0 0 0 6,67 13,34

x7 0 1* 0 0 0 0 0 1 1 1

memilih kolom kunci



nilai -25.000.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 13.320.000 : 6.000.00 = 2,22

Indeks baris x5 = 0,67 : 0,5 = 1,34

Indeks baris x2 = 6,67 : 0,5 = 13,34


memilih baris kunci



44

-












Kolom 6x baris x7 = 0 : 1 = 0


Kolom NK baris x7 = 1 : 1 = 1





-25.000 0 0 4.950 0 M 0 1.000.500

-25.000 1 0 0 0 0 0 1 1

0 0 0 4.950 0 M 25.000 1.025.500



Koefisien

Baris lama

Nilai baru

Baris kunci

45

-

-

-

-

6.000.000 0 1 -132.000 0 0 0 13.320.000

6.000.000 1 0 0 0 0 0 1 1

0 0 1 -132.000 0 0 -6.000.000 7.320.500



0,5 0 0 0,033 1 -1 0 0,67

0,5 1 0 0 0 0 0 1 1

0 0 0 0,033 1 -1 -0,5 0,17



0,5 1 0 0,033 0 0 0 6,67

0,5 1 0 0 0 0 0 1 1

0 1 0 0,033 0 0 -0,5 6,17


x1 masuk ke dalam variabel dasar menggantikan x7, sehingga tabel C akan

berubah menjadi :


Variabel


6x x7 NK Indeks

z 1 0 0 0 4.950 0 M 25.000 1.025.500

x3 0 0 0 1 -132.000 0 0 -6.000.000 7.320.000

x5 0 0 0 0 0,033 1 -1 -0,5 0,17

x2 0 0 1 0 0,033 0 0 -0,5 6,17

x1 0 1 0 0 0 0 0 1 1





11 x dan 17,62 x

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Nilai baru

Baris kunci

Baris lama

Koefisien

Baris lama

Nilai baru

Baris kunci

46

Dari tabel D solusi optimal simpleks relaksasi pada node 4 diperoleh:

a. batas atas 1.025.500 dengan 11 x dan 17,62 x


NODE 5


Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

(3) 62 x

(4) 21 x

(5) 0, 21 xx





000.000.40000.000.4000.000.8 321 xxx


2003015 421 xxx


6

6

6

52

52

2

xx

xx

x




47



6652 xxx


2

2

2

71

71

1

xx

xx

x



2871 xxx

Dengan memperhatikan perubahan fungsi tujuan karena batasan (3) dan (4), maka

fungsi tujuan diubah menjadi :

0000.150000.100 8621 xMxMxxz

Untuk mengubah agar nilai 6x dan 8x pada batasan menjadi 0, maka dilakukan


1 -100.000 -150.000 0 0 0 M 0 M 0

0 0 1 0 0 -1 1 0 0 6

0 1 0 0 0 0 0 -1 1 2

1 -100.000-M -150.000-M 0 0 M 0 M 0 -8M


MMxMxxMxMz 8000.150000.100 7521



berikut:

-M

-M




48


Variabel

Dasar z

x1 x2 x3 x4 x5 6x x7

8x NK Indeks

z 1 -100.000

-M

-150.000

-M 0 0 M 0 M 0 -8M

x3 0 8.000.

000

4.000.

000 1 0 0 0 0 0

40.000.

000 10

x4 0 15 30 0 1 0 0 0 0 200 6,67

6x 0 0 1* 0 0 -1 1 0 0 6 6

8x 0 1 0 0 0 0 0 -1 1 2




nilai -150.000-M.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 40.000.000 : 4.000.000 = 10

Indeks baris x4 = 200 : 30 = 6,67


Indeks baris 8x = 1 : 0 =




49

-











Kolom x5 baris 6x = -1 : 1 = -1

Kolom 6x baris

6x = 1 : 1 = 1








-100.000-M -150.000-M 0 0 M 0 M 0 -8M

-150.000-M 0 1 0 0 -1 1 0 0 6

-100.000-M 0 0 0 -150.000 150.00+M M 0 -2M+900.000

Koefisien

Baris lama

Nilai baru

Baris kunci

50

-

-

-



8.000.000 4.000.000 1 0 0 0 0 0 40.000.000

4.000.000 0 1 0 0 -1 1 0 0 6

8.000.000 0 1 0 4.000.000 -4.000.000 0 0 16.000.000



15 30 0 1 0 0 0 0 2 00

30 0 1 0 0 -1 1 0 0 6

15 0 0 1 30 -30 0 0 20

Baris 8x diubah dengan rumus :


1 0 0 0 0 0 -1 1 2

0 0 1 0 0 -1 1 0 0 6

1 0 0 0 0 0 -1 1 2




berubah menjadi :


Variabel

Dasar z

x1 x2 x3 x4 x5 6x x7 8x NK Indeks

z 1 -100.000

-M 0 0 0

-150.

000

150.00

0+M M 0

-2M+

900.000

x3 0 8.000.

000 0 1 0

4.000.

000

-4.000.

000 0 0

16.000.

000 2

x4 0 15* 0 0 1 30 -30 0 0 20 1,33

x2 0 0 1 0 0 -1 1 0 0 6

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

51

8x 0 1 0 0 0 0 0 -1 1 2 2

52

memilih kolom kunci



nilai -100.000-M.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 16.000.000 : 8.000.00 = 2

Indeks baris x4 = 20 : 15 = 1,33



memilih baris kunci









Kolom x1 baris x4 = 15 : 15 = 1


53

-

-

-


Kolom x4 baris x4 = 1 : 15 = 0,067

Kolom x5 baris x4 = 30 : 15 = 2

Kolom 6x baris x4 = -30 : 15 = -2

Kolom x7 baris x4= 0 : 15 = 0


Kolom NK baris x4 = 20 : 15 = 1,33





-100.000-M 0 0 0 -150.000 150.00+M M 0 -2M+900.000

-100.000-M 1 0 0 0,067 2 -2 0 0 1,33

0 0 0 50.000+2M M 0



8.000.000 0 1 0 4.000.000 -4.000.000 0 0 16.000.000

8.000.000 1 0 0 0,067 2 -2 0 0 1,33

0 0 1 -536.000 12.000.000 0 0 5.360.000



0 1 0 0 -1 1 0 0 6

0 1 0 0 0,067 2 -2 0 0 1,33

0 1 0 0 -1 1 0 0 6

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

-50.000-M 6.700+0,067M -0,67M+1.033.000

-12.000.000

54

-



1 0 0 0 0 0 -1 1 2

1 1 0 0 0,067 2 -2 0 0 1,33

0 0 0 -0,067 -2 2 -1 1 0,67



berubah menjadi :


Variabel

Dasar z x1 x2 x3 x4 x5 6x x7 8x NK Indeks

z 1 0 0 0 6.700+

0,067M

50.000

+2M

-50.000

-M M 0

-0,67M+

1.033.000

x3 0 0 0 1 -536.

000

-

12.000.

000

12.000.

000 0 0 5.360.000 0,44

x1 0 1 0 0 0,067 2 -2 0 0 1,33 -0,667

x2 0 0 1 0 0 -1 1 0 0 6 6

8x 0 0 0 0 -0,067 -2 2* -1 1 0,67 0,335

memilih kolom kunci


negatif dengan angka terbesar pada baris fungsi tujuan, yaitu kolom 6x dengan

nilai -50.000-M.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 5.360.000 : 12.000.00 = 0,45

Indeks baris x1 = 1,33 : -2 = -0,665

Koefisien

Baris lama

Nilai baru

Baris kunci

55


Indeks baris 8x = 0,67 : 2 = 0,335

memilih baris kunci












Kolom x4 baris 8x = -0,067 : 2 = -0,0335

Kolom x5 baris 8x = -2 : 2 = -1

Kolom 6x baris 8x = 2 : 2 = 1

Kolom x7 baris 8x = -1: 2 = -0,5

Kolom 8x baris 8x = 1 : 2 = 0,5

Kolom NK baris 8x = 0,67 : 2 = 0,335

56

-

-

-

-





0 0 0 6.700+0,067M 50.000+2M -50.000-M M 0 -0,67M+1.033.000

-50.000-M 0 0 0 -0,0335 -1 1 -0,5 0,5 0,335

0 0 0 5.025+0,0335M M 0 0,5M+25.000



0 0 1 -536.000 -12.000.000 12.000.000 0 0 5.360.000

12.000.000 0 0 0 -0,0335 -1 1 -0,5 0,5 0,335

0 0 1 -134.000 0 0 6.000.000 1.340.000



1 0 0 0,067 2 -2 0 0 1,33

-2 0 0 0 -0,0335 -1 1 -0,5 0,5 0,335

1 0 0 0 0 0 -1 1 2



0 1 0 0 -1 1 0 0 6

1 0 0 0 -0,0335 -1 1 -0,5 0,5 0,335

0 1 0 0,0335 0 0 0,5 -0,5 5,665

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

0,5M-25.000 0,0335M+1.049.500

-6.000.000

Koefisien

Baris lama

Nilai baru

Baris kunci

57

Karena kolom kunci adalah kolom 6x dan baris kunci adalah baris 8x ,

maka 6x masuk ke dalam variabel dasar menggantikan 8x , sehingga tabel C akan

berubah menjadi :


Variabel


6x x7 8x NK Indeks

z 1 0 0 0 5.025+

0,0335M M 0

0,5M-

25.000

25.000

+0,5M

783.750-

0,335M

x3 0 0 0 1 134.000 0 0 6.000.

000

-6.000.

000 1.340.000

x1 0 1 0 0 0 0 0 -1 1 2

x2 0 0 1 0 0,0335 0 0 0,5 -0,5 5,665

6x 0 0 0 0 -0,0335 -1 1 -0,5 0,5 0,335

Seluruh elemen pada baris fungsi tujuan tidak ada lagi yang bernilai

negatif, maka tidak perlu lagi dilakukan upaya perbaikan. Namun karena solusi

yang ditunjukkan tabel D Solusi Optimal simpleks relaksasi pada Node 5 masih

memuat artivicial variable, maka solusi tersebut tidak layak. Dengan demikian,

pada node 5 tidak terdapat solusi.

Mengingat bahwa belum diperoleh suatu solusi bilangan bulat yang layak

dan optimal, maka harus dibuat cabang dari salah satu antara node 2, node 4 atau

node 5. Karena solusi yang ditunjukkan tabel solusi optimal simpleks relaksasi

pada node 5 memuat artivicial variable, maka solusi tersebut tidak layak,

sehingga tidak perlu dilakukan perbandingan batas terhadap node 5. Melainkan

membandingkan batas antara node 2 dan 4, dan karena batas node 4 lebih besar

dari batas node 2, maka pencabangan dilakukan pada node 4. Berdasarkan tabel

solusi optimal simpleks relaksasi pada node 4, diketahui bahwa variabel x1 sudah

bernilai bilangan bulat dan x2 masih memiliki bagian yang bernilai pecahan, yaitu

58

0,17. Jadi, dua batasan baru dikembangkan dari x2, yaitu : 62 x dan 72 x .

Sehingga diperoleh dua node baru yang merupakan cabang dari node 3, seperti

tampak pada gambar berikut :

NODE 6


Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

(3) 62 x

(4) 11 x

(5) 62 x

(6) 0, 21 xx

Node 1

1.056.000

BA = 1.056.000 ( 22,21 x , 56,52 x )

BB = 950.000 ( 21 x , 52 x )

Node 2

1.000.000

Node 3

1.034.000

52 x 62 x

Node 4

1.025.500

Node 5

Tidak layak

11 x 21 x

BA = 1.034.000 ( 34,11 x 62 x )

BB = 1.000.000 ( 11 x , 62 x )

BA = 1.000.000 ( 5,21 x 52 x )

BB = 950.000 ( 21 x 52 x )

Node 6

Node 7

62 x 72 x

BA = 1.025.500 ( 11 x 17,62 x )

BB = 1.000.000 ( 11 x 62 x )

59





000.000.40000.000.4000.000.8 321 xxx


2003015 421 xxx


6

6

6

52

52

2

xx

xx

x



6652 xxx


171 xx


682 xx



0000.150000.100 621 xMxxz



1 -100.000 -150.000 0 0 0 M 0 0 0

0 0 1 0 0 -1 1 0 0 6




-M

60

1 -100.000 -150.000-M 0 0 M 0 0 0 -6M


MMxxMxz 6000.150000.100 521



berikut:


Variabel

Dasar z

x1 x2 x3 x4 x5 6x x7

8x NK Indeks

z 1 -100.

000

-150.000

-M 0 0 M 0 0 0 -6M

x3 0 8.000.

000

4.000.

000 1 0 0 0 0 0 40.000.000 10

x4 0 15 30 0 1 0 0 0 0 200 6,67

6x 0 0 1* 0 0 -1 1 0 0 6 6

x7 0 1 0 0 0 0 0 1 0 1

8x 0 0 1 0 0 0 0 0 1 6 6

memilih kolom kunci



nilai -150.000-M.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 40.000.000 : 4.000.00 = 10

Indeks baris x4 = 200 : 30 = 6,67



61


memilih baris kunci













Kolom x5 baris 6x = -1 : 1 = -1

Kolom 6x baris

6x = 1 : 1 = 1


Kolom 8x baris

6x = 0 : 1 = 0


62

-

-

-

-

-





-100.000 -150.000 0 0 M 0 0 0 -6M

-150.000-M 0 1 0 0 -1 1 0 0 6

-100.000 0 0 0 -150.000 150.000+M 0 0 900.000



8.000.000 4.000.000 1 0 0 0 0 0 40.000.000

4.000.000 0 1 0 0 -1 1 0 0 6

8.000.000 0 1 0 4.000.000 -4.000.000 0 0 16.000.000



15 30 0 1 0 0 0 0 200

30 0 1 0 0 -1 1 0 0 6

15 0 0 1 30 -30 0 0 20



1 0 0 0 0 0 1 0 1

0 0 1 0 0 -1 1 0 0 6

1 0 0 0 0 0 1 0 1



0 1 0 0 0 0 0 1 6

1 0 1 0 0 -1 1 0 0 6

0 0 0 0 1 -1 0 1 0

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

63



berubah menjadi :


Variabel

Dasar z x1 x2 x3

x4 x5 6x x7

8x NK Indeks

z 1 -100.

000 0 0 0

-150.

000

150.000

+M 0 0 900.000

x3 0 8.000.

000 0 1 0

4.000.

000

-4.000.

000 0 0 16.000.000 4

x4 0 15 0 0 1 30 -30 0 0 20 0,67

x2 0 0 1 0 0 -1 1 0 0 6 -6

x7 0 1 0 0 0 0 0 1 0 1

8x 0 0 0 0 0 1* -1 0 1 0 0

memilih kolom kunci



nilai -150.000.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 16.000.000 : 4.000.00 = 4

Indeks baris x4 = 20 : 30 = 0,67




64

memilih baris kunci














Kolom 6x baris

8x = -1 : 1 = -1


Kolom 8x baris

8x = 1 : 1 = 1




65

-

-

-

-

-



-100.000 0 0 0 -150.000 150.000+M 0 0 900.000

-150.000 0 0 0 0 1 -1 0 1 0

-100.000 0 0 0 0 M 0 150.000 900.000



8.000.000 0 1 0 4.000.000 -4.000.000 0 0 16.000.000

4.000.000 0 0 0 0 1 -1 0 1 0

8.000.000 0 1 0 0 0 0 -4.000.000 16.000.000



15 0 0 1 30 -30 0 0 20

30 0 0 0 0 1 -1 0 1 0

15 0 0 1 0 0 0 -30 20



0 1 0 0 -1 1 0 0 6

-1 0 0 0 0 1 -1 0 1 0

0 1 0 0 0 0 0 1 6



1 0 0 0 0 0 1 0 1

0 0 0 0 0 1 -1 0 1 0

1 0 0 0 0 0 1 0 1

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

66


maka x5 masuk ke dalam variabel dasar menggantikan 8x , sehingga tabel B akan

berubah menjadi :


Variabel

Dasar z

x1 x2 x3 x4 x5 6x x7

8x NK Indeks

z 1 -100.

000 0 0 0 0 M 0 150.000 900.000

x3 0 8.000.

000 0 1 0 0 0 0 -4.000.000 16.000.000 2

x4 0 15 0 0 1 0 0 0 -30 20 1,33

x2 0 0 1 0 0 0 0 0 1 6

x7 0 1* 0 0 0 0 0 1 0 1 1

x5 0 0 0 0 0 1 -1 0 1 0

memilih kolom kunci



nilai -100.000.



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 16.000.000 : 8.000.00 = 2

Indeks baris x4 = 20 : 15 = 1,33




67

memilih baris kunci




















68

-

-

-

-

-



-100.000 0 0 0 0 M 0 150.000 900.000

-100.000 1 0 0 0 0 0 1 0 1

0 0 0 0 0 M 100.000 150.000 1.000.000



8.000.000 0 1 0 0 0 0 -4.000.000 16.000.000

8.000.000 1 0 0 0 0 0 1 0 1

0 0 1 0 0 0 -8.000.000 -4.000.000 8.000.000



15 0 0 1 0 0 0 -30 20

15 1 0 0 0 0 0 1 0 1

0 0 0 1 0 0 -15 -30 5



0 1 0 0 0 0 0 1 6

0 1 0 0 0 0 0 1 0 1

0 1 0 0 0 0 0 1 6



0 0 0 0 1 -1 0 1 0

0 1 0 0 0 0 0 1 0 1

0 0 0 0 1 -1 0 1 0

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

69

Karena kolom kunci adalah kolom x1 dan baris kunci adalah baris x7,

maka x1 masuk ke dalam variabel dasar menggantikan x7, sehingga tabel C akan

berubah menjadi :


Variabel


6x x7 8x NK Indeks

z 1 0 0 0 0 0 M 100.000 150.000 1.000.000

x3 0 0 0 1 0 0 0 -

8.000.000 -4.000.000 8.000.000

x4 0 0 0 0 1 0 0 -15 -30 5

x2 0 0 1 0 0 0 0 0 1 6

x1 0 1 0 0 0 0 0 1 0 1

x5 0 0 0 0 0 1 -1 0 1 0





11 x dan 62 x .

Dari tabel solusi optimal simpleks relaksasi pada node 6 diperoleh:

a. batas atas 1.000.000 dengan 11 x dan 62 x

b. batas atas 1.000.000 dengan 11 x dan 62 x

NODE 7


Berdasarkan :

(1) 000.000.40000.000.4000.000.8 21 xx

(2) 2003015 21 xx

(3) 62 x

70

(4) 11 x

(5) 72 x

(6) 0, 21 xx





000.000.40000.000.4000.000.8 321 xxx


2003015 421 xxx


6

6

6

52

52

2

xx

xx

x



6652 xxx


171 xx


7

7

7

82

82

2

xx

xx

x



7982 xxx







71

Dengan memperhatikan perubahan fungsi tujuan karena batasan (3) dan (5), maka

fungsi tujuan diubah menjadi :

0000.150000.100 9621 xMxMxxz

Untuk mengubah agar nilai 6x dan 9x pada batasan menjadi 0, maka dilakukan


1 -100.000 -150.000 0 0 0 M 0 0 M 0

0 0 1 0 0 -1 1 0 0 0 6

0 0 1 0 0 0 0 0 -1 1 7

1 -100.000 -150.000-2M 0 0 M 0 0 M 0 -13M


MMxMxxMxz 132000.150000.100 8521



berikut:


Variabel

Dasar z

x1 x2 x3 x4 x5 6x x7 x8 9x NK Indeks

z 1 -100.

000

-150.000

-2M 0 0 M 0 0 M 0 -13M

x3 0 8.000.

000

4.000.

000 1 0 0 0 0 0 0

40.000.

000 10

x4 0 15 30 0 1 0 0 0 0 0 200 6,67

6x 0 0 1* 0 0 -1 1 0 0 0 6 6

x7 0 1 0 0 0 0 0 1 0 0 1

9x 0 0 1 0 0 0 0 0 -1 1 7 7

memilih kolom kunci



nilai -150.000-M.

-M

-M

72



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 40.000.000 : 4.000.00 = 10

Indeks baris x4 = 200 : 30 = 6,67




memilih baris kunci












73

-

-

-


Kolom x5 baris 6x = -1 : 1 = -1

Kolom 6x baris

6x = 1 : 1 = 1



Kolom 9x baris

6x = 0 : 1 = 0






-100.000 -150.000-2M 0 0 M 0 0 M 0 -13M

-150.000-2M 0 1 0 0 -1 1 0 0 0 6

-100.000 0 0 0 -150.000-M 150.000+2M 0 M 0 900.000-M



8.000.000 4.000.000 1 0 0 0 0 0 0 40.000.000

4.000.000 0 1 0 0 -1 1 0 0 0 6

8.000.000 0 1 0 4.000.000 -4.000.000 0 0 0 16.000.000



15 30 0 1 0 0 0 0 0 200

30 0 1 0 0 -1 1 0 0 0 6

15 0 0 1 30 -30 0 0 0 20

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

74

-

-



1 0 0 0 0 0 1 0 0 1

0 0 1 0 0 -1 1 0 0 0 6

1 0 0 0 0 0 1 0 0 1



0 1 0 0 0 0 0 -1 1 7

1 0 1 0 0 -1 1 0 0 0 6

0 0 0 0 1 -1 0 -1 1 1



berubah menjadi :


Variabel

Dasar z x1 x2 x3 x4 x5 6x x7 x8 9x NK Indeks

z 1 -100.

000 0 0 0

-150.000

-M

150.000

+2M 0 M 0

900.000

-M

x3 0 8.000.

000 0 1 0

4.000.

000

-4.000.

000 0 0 0

16.000.

000 4

x4 0 15 0 0 1 30* -30 0 0 0 20 0,67

x2 0 0 1 0 0 -1 1 0 0 0 6 -6

x7 0 1 0 0 0 0 0 1 0 0 1

9x 0 0 0 0 0 1 -1 0 -1 1 1 1

memilih kolom kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

75



nilai -150.000-M.

76



kuncikolomnilai

NKkolomnilaiIndeks

Indeks baris x3 = 16.000.000 : 4.000.00 = 4

Indeks baris x4 = 20 : 30 = 0,67




memilih baris kunci









Kolom x1 baris x4 = 15 : 30 = 0,5

Kolom x2 baris x4 = 0 : 30 = 0,


Kolom x4 baris x4 = 1 : 30 = 0,033

Kolom x5 baris x4 = 30 : 30 = 1

77

- Nilai baru

Baris kunci

-

-

1.000.500-0,33M

Kolom 6x baris x4 = -30 : 30 = -1




Kolom NK baris x4 = 20 : 30 = 0,67





-100.000 0 0 0 -150.000-M 150.000+2M 0 M 0 900.000-M

-150.000-M 0,5 0 0 0,033 1 -1 0 0 0 0,67

25.000+0,5M 0 0 4.950+0,33M 0 M 0 M 0



8.000.000 0 1 0 4.000.000 -4.000.000 0 0 0 16.000.000

4.000.000 0,5 0 0 0,033 1 -1 0 0 0 0,67

6.000.000 0 1 -132.000 0 0 0 0 0 13.320.000



0 1 0 0 -1 1 0 0 0 6

-1 0,5 0 0 0,033 1 -1 0 0 0 0,67

0,5 1 0 0,033 0 0 0 0 0 6,67

Koefisien

Baris lama

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

78

-

-



1 0 0 0 0 0 1 0 0 1

0 0,5 0 0 0,033 1 -1 0 0 0 0,67

1 0 0 0 0 0 1 0 0 1



0 0 0 0 1 -1 0 -1 1 1

1 0,5 0 0 0,033 1 -1 0 0 0 0,67

-0,5 0 0 -0,033 0 0 0 -1 1 0,33



berubah menjadi :


Variabel

Dasar z x1 x2 x3 x4 x5 6x x7 x8 9x NK Indeks

z 1 -25.000

+0,5M 0 0

4.950+

0,033M 0 M 0 M 0

1.000.500

-0,33M

x3 0 6.000.

000 0 1

-132.

000 0 0 0 0 0

13.320.

000

x5 0 0,5 0 0 0,033 1 -1 0 0 0 0,67

x2 0 0,5 1 0 0,033 0 0 0 0 0 6,67

x7 0 1 0 0 0 0 0 1 0 0 1

9x 0 -0,5 0 0 -0,033 0 0 0 -1 1 0,33

Seluruh elemen pada baris fungsi tujuan tidak ada lagi yang benilai

negatif. Namun karena solusi yang ditunjukkan tabel C Solusi Optimal simpleks

relaksasi pada Node 7 masih memuat artivicial variable, maka solusi tersebut

tidak layak. Dengan demikian, pada node 5 tidak terdapat solusi.

Koefisien

Baris lama

Nilai baru

Baris kunci

Koefisien

Baris lama

Nilai baru

Baris kunci

79

Gambar di atas menunjukkan bahwa solusi bilangan bulat optimal telah

tercapai pada node 6, yaitu 000.000.1z untuk 11 x dan 62 x . Suatu

perbandingan antara solusi-solusi pada node 2, 5, 6, dan 7 memperlihatkan bahwa

tidak memungkinkan memperoleh solusi yang lebih baik. Batas atas pada node 2

adalah 1.000.000, sama dengan yang diperoleh pada node 6. Sedangkan solusi

pada node 5 dan 7 tidak layak

Langkah 6. Solusi simpleks relaksasi adalah merupakan batas atas pada tiap

node, dan solusi bilangan bulat maksimum yang ada (pada node

mana saja) adalah merupakan batas bawah

Berdasarkan uraian pada langkah 5, maka diperoleh :

a. batas atas 1.056.000 dengan 22,21 x dan 56,52 x


Node 1

1.056.000

BA = 1.056.000 ( 22,21 x , 56,52 x )

BB = 950.000 ( 21 x , 52 x )

Node 2

1.000.000

Node 3

1.034.000

52 x 62 x

Node 4

1.025.500

Node 5

Tidak layak

11 x 21 x

BA = 1.034.000 ( 34,11 x 62 x )

BB = 1.000.000 ( 11 x , 62 x )

BA = 1.000.000 ( 5,21 x 52 x )

BB = 950.000 ( 21 x 52 x )

Node 6

1.000.000

Node 7

Tidak Layak

62 x 72 x

BA = 1.025.500 ( 11 x 17,62 x )

BB = 1.000.000 ( 11 x 62 x )

BA = 1.000.000 ( 11 x , 62 x )

BB = 1.000.000 ( 11 x , 62 x )

80

Langkah 7. Jika proses ini menghasilkan solusi bilangan bulat fisibel dengan

nilai batas atas pada akhir node mana saja, maka solusi bilangan

bulat optimal telah tercapai. Jika tidak muncul solusi bilangan

bulat fisibel, lakukan pencabangan dari node dengan batas atas

terbesar

Berdasarkan langkah 1 sampai dengan 6, telah diperoleh solusi bilangan

bulat optimal, yaitu z = 1.000.000 dengan x1 = 1 dan x2 = 6. Oleh karena itu, tidak

perlu lagi dilakukan pencabangan. Jadi, solusi optimal dari persoalan program

linier untuk toko jual beli mesin adalah membeli 1 unit mesin cetak dan 6 unit

mesin bubut, sehingga akan diperoleh keuntungan maksimum sebesar Rp

1.000.000,00 setiap harinya.

81

BAB IV

KESIMPULAN DAN SARAN

4.1 Kesimpulan

Teknik Branch and Bound merupakan teknik solusi yang sesuai digunakan

untuk menyelesaikan persoalan program linier yang mengharuskan setiap

variabelnya bernilai bilangan bulat dan dikembangkan dengan prinsip bahwa total

set solusi yang fisibel dapat dibagi menjadi subset-subset solusi yang lebih kecil.

Subset-subset ini selanjutnya dapat dievaluasi secara sistematis sampai solusi

yang terbaik ditemukan. Teknik Branch and Bound pada persoalan program linier

digunakan bersama-sama dengan metode simpleks. Teknik ini menggunakan

suatu diagram yang terdiri dari node dan cabang sebagai suatu kerangka dalam

proses pemerolehan solusi optimal.

Langkah-langkah penggunaan teknik Branch and Bound adalah sebagai

berikut :

a. Dapatkan solusi simpleks optimal dari program linier relaksasi yang

bersangkutan.

b. Solusi yang dihasilkan pada langkah a dinyatakan sebagai batas atas

(upper bound) dan pembulatan ke bawah sebagai batas bawah (lower

bound) pada node 1

c. Pilihlah variabel dengan pecahan yang terbesar untuk pencabangan

(branch). Ciptakan dua batasan baru untuk variabel ini. Hasilnya adalah

sebuah batasan dan sebuah batasan .

82

d. Ciptakan dua node baru, satu dengan batasan dan satu dengan

batasan

e. Selesaikan model program linier relaksasi dengan batasan baru yang

ditambahkan pada tiap node

f. Solusi simpleks relaksasi adalah merupakan batas atas pada tiap node, dan

solusi bilangan bulat maksimum yang ada (pada node mana saja) adalah

merupakan batas bawah

g. Jika proses ini menghasilkan solusi bilangan bulat fisibel dengan nilai

batas atas pada akhir node mana saja, maka solusi bilangan bulat optimal

telah tercapai. Jika tidak muncul solusi bilangan bulat fisibel, lakukan

pencabangan dari node dengan batas atas terbesar

4.2 Saran

Untuk menyelesaikan program linier yang mengharuskan setiap

variabelnya bernilai bilangan bulat, sangat sesuai bila menggunakan teknik

Branch and Bound. Teknik ini dapat dipadukan dengan metode simpleks, metode

dua fase ataupun dengan metode grafik. Oleh karena itu, bagi pembaca dapat

menerapkan teknik Branch and Bound ini dengan menggunakan metode grafik

atau metode dua fase.

83

DAFTAR PUSTAKA

Dimyati, T. dan Dimyati, A.,1994, Operations Research Model-model

Pengambilan Keputusan, Sinar Baru Algesindo, Bandung.

Subagyo, P., Asri, M. dan Handoko, H., 1992, Dasar-dasar operations research,

BPFE, Yogyakarta.

Taylor III, B., 1996, Sains Manajemen Pendekatan Matematika untuk Bisnis,

Salemba Empat, Jakarta.

branch and bound program linier

Documents