Program Linear Metode Branch and Bound [PDF]

Citation preview

Tugas Terstruktur Dalam Matakuliah



Dosen Pembimbing



Program Linear



Hayatun Nufus



METODE BRANCH AND BOUND



Di Susun Oleh: Kelompok 2 Fitrah Abdullah Pane (11810511211) Mifta Oktarianti (11810523274) Rini Andani (11810523275)



JURUSAN PENDIDIKAN MATEMATIKA FAKULTAS TARBIYAH DAN KEGURUAN UNIVERSITAS ISLAM NEGERI SULTAN SYARIF KASIM RIAU PEKANBARU



KATA PENGANTAR



Alhamdulillah, puji syukur kami panjatkan kehadirat Allah Swt, yang telah melimpahkan rahmat, hidayah dan inayah-Nya sehingga kami dapat  menyelesaikan makalah berjudul “Metode Branch and Bound” dalam mata kuliah Bimbingan Konseling. Dalam menyelesaikan makalah ini, kami mendapatkan begitu banyak bimbingan dari berbagai pihak, untuk itu kami mengucapkan banyak terimakasih kepada



siapa



saja



yang



membantu



dalam



menyelesaikan



makalah



ini.Mudah-mudahan makalah ini dapat memberikan manfaat dalam segala bentuk belajar mengajar.Sehingga dapat mempermudah pencapaian tujuan pendidikan nasional. Namun, makalah ini masih ada kekurangan, oleh karena itu kami mengharap kritik dan saran yang akan menjadikan makalah ini lebih baik.



Pekanbaru,19 April 2020



Tim Penulis



1



DAFTAR ISI



KATA PENGANTAR



i



DAFTAR ISI



ii



BAB I PENDAHULUAN 1.1 Latar Belakang Masalah



1



1.2 Rumusan Masalah



1



1.3 Tujuan Penulisan



1



BAB II KAJIAN TEORI 2.1 Pengantar teori



2



2.2 Langkah-langkah



2



2.3 Contoh penerapan



6



2.4 Soal latihan



27



BAB III PENUTUP 3.1 Kesimpulan



29



3.2 Saran



29



DAFTAR PUSTAKA



30



2



BAB I PENDAHULUAN 1.1



Latar Belakang Masalah Salah satu pendekatan yang dapat dilakukan untuk menyelesaikan masalah program linier adalah metode branch and bound, pengembangan dari Program Linear di mana beberapa atau semua variabel keputusannya harus berupa integer.  Pemrograman bulat dibutuhkan ketika keputusan harus dilakukan dalam bentuk bilangan bulat (bukan pecahan yang sering terjadi bila kita gunakan metode simpleks). Model matematis dari pemrograman bulat sebenarnya sama dengan model linear programming, dengan tambahan batasan bahwa variabelnya harus bilangan bulat. Untuk lebih jelasnya, dalam makalah ini penulis akan membahas metode branch and bound.



1.2



Rumusan Masalah 1.         Apa pengertian Metode Branch and Bound? 2.         Bagaimana langkah-langkah dari metode Branch and Bound? 3.         Bagaimana penetapan batas dari metode Branch and Bound? 4.         Bagaimana penghentian pencabangan dari metode Branch and Bound?



1.3



Tujuan Penulisan Berdasarkan rumusan masalah di atas maka tujuan dalam penulisan makalah ini sebagai berikut: 1.      Untuk mengetahui apa itu Metode Branch and Bound 2.      Untuk mengetahui apa langkah-langkah dari metode Branch and Bound 3.      Untuk mengetahui penetapan batas dari metode Branch and Bound 4.      Untuk mengetahui penghentian pencabangan dari metode Branch and Bound 1



BAB II KAJIAN TEORI 2.1 Pengantar teori Teknik Branch and Bound merupakan teknik solusi untuk persoalan program linear yang mengharuskan variabeknya 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 di temukan. Teknik Branch and Bound pada persoalan program linear 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 linear relaksasi (program linear yang mengabaikan batas-batas bilangan bulat) sesuai dengan fungsi tujuan dan batasannya. Node prtama akan memuat solusi program linear relaksasi dan 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.1 2.2 Langkah-langkah Berikut



ini adalah langkah-langkah penyelesaian suatu masalah



maksimisasi dengan metode branch and bound : 1.



Selesaikan masalah program linier dengan metode simpleks selesaikan masalah tanpa pembatasan bilangan integer.



1



Hayatun Nufus, Erdawati Nurdin, Program Linear. (Pekanbaru: Cahaya Firdaus, 2016), hal.46



2



2. Teliti solusi optimalnya, jika variabel keputusan yang diharapkan adalah bilangan integer, solusi optimum integer telah tercapai. Jika satu atau lebih variabel keputusan yang diharapkan ternyata bukan bilangan integer, lanjutkan ke langkah 3. 3. Jadikan solusi pada penyelesaian langkah 1 menjadi batas atas dan untuk batas bawahnya merupakan solusi yang variabel keputusannya telah diintegerkan (rounded – down).2 4. Pilih variabel yang mempunyai nilai pecahan terbesar (artinya bilangan desimal



terbesar



dari masing-masing vaariabel untuk



dijadikan



pencabangan ke dalam sub-sub masalah. Tujuannya adalah untuk menghilangkan solusi yang tidak memenuhi persyaratan integer dalam masalah itu. Pencabangan itu dilakukan secara mutually exclusive untuk memenuhi persyaratan integer dengan jaminan tidak ada solusi fisibel (layak) yang diikutsertakan. Hasilnya adalah sebuah sub masalah dengan batasan ≤ atau batasan ≥ 5. Untuk setiap sub-masalah, nilai optimum fungsi tujuan ditetapkan sebagai batas atas. Solusi optimum yang diintegerkan menjadi batas bawah (solusi yang sebelumnya tidak integer kemudian diintegerkan). Sub-sub masalah yang memiliki batas atas kurang dari batas bawah yang ada, tidak diikutsertakan pada analisa selanjutnya. Suatu solusi integer fisibel (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 4.3



2 3



Gede Suryawan. Penerapan Branch and Bound Algorithm. Jurnal Matematika Arum pratiwi. Implementasi Algoritma Branch and Bound (UNNES Journal 0f Mathematics)



3



4



Langkah-langkah pengerjaan metode Branch and Bound45 Dengan metode pembulatan langsung (round off)dan solusi optimal (x1 = 3,75 x2 = 1,5) diperoleh hasil yang paling mendekati yaitu X1 = 4 unit X2 = 1 unit Pada sub bab ini akan dibahas secara rinci metode penyelesaian dengan menggunakan branch and bound. Karena hasil yang diperoleh mengandung variabel yang tidak bulat maka dilakukan pencabangan. Jika terdapat variabel yang tidak bulat (misal xj*), maka dibentuk dua program bilangan bulat baru dengan kendala xj ≤ I, atau kendala xj ≥ i2.i1 dan i2 adalah dua bilanganbulat tak negative yang berurutan. Dari soal diatas, diperoleh hasil optimal x1 = 3,75 x2 = 1,5 dan z =40,5. Hasil yang diperoleh tidak layak karena bentuknya pecahan sehingga tidak memenuhi persyaratan integer. Algoritma branch and bound memodifikasi ruang pemecahan masalah LP yang akhirnya akan memberikan solusi optimum untuk masalah ILP. Solusi optimum LP (x1= 3,75) tidak memenuhi persyaratan integer sehingga titik ini tidak layak dan dilakukan modifikasi dengan mencari titik lain yang integer pada titik 3 dan 4 (3 ˂ x1 ˂ 4). Ruang pemecahan baru membuat adanya batasan baru yaitu x1 ≤ 3 dan x1 ≥ 4. Untuk menemukan solusi optimum dengan menggunakan algoritma branch and bound.6



2.3 Contoh Penerapan 4



A Pasaribu, priandy Hasian, Implementasi Metode Branch and Bound dalam Mengoptimalkan Jumlah Produk guna Memaksimalkan Keuntungan (Studi Kasus: CV. Ridho Mandiri). Skripsi Sarjana hal. 29 5 Margiyani, Aplikasi Algoritma Branch and Bound. (Yogyakarta, Universitas Islam Sunan Kalijaga) 6 Ilyas Masudin, Linear Programming dengan R : (Aplikasi untuk Teknik Industri). (Malang, Universitas Muhammadiyah Malang, 2018), hal. 108



5



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 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 ( m² )



Harga Beli



Percetakan



15



Rp 8.000.000,00



Bubut



30



Rp 4.000.000,00



Anggaran pembelian mesin adalah sebesar Rp 40.000.000,000 sedangkan tempat yang tersedia adalah 200 m². Pemilik ingin mengetahui berapa banyak tiap jenis mesin yang dapat dibeli untuk memaksimumkan kenaikan keuntungan perhari. Penyelesaian Model matematis untuk persoalan diatas adalah : Memaksimumkan : z = 100.000x1 + 150.000x2 Berdasarkan 8.000.000x1 + 4.000.000x2 ≤ 40.000.000 15x1 + 30x2 ≤ 200 x1 , x2 ≥ 0 ; x1 , x2 bilangan bulat Langkah 1. Mencari solusi optimal dari program linear yang bersangkutan



6



Persoalan diatas diubah menjadi program linear relaksasi sehingga : Maksimumkan : z = 100.000x1 + 150.000x2 Berdasarkan.



: (1) 8.000.000x1 + 4.000.000x2 ≤ 40.000.000 (2)15x1 + 30x2 ≤ 200 (3) x1 , x2 ≥ 0 ; x1 , x2 bilangan bulat



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 variabel x3, sehingga : 8.000.000x1 + 4.000.000x2 + x3 = 40.000.000 Batasan (2) harus ditambah dengan sebuah slack variabel x4, sehingga : 15x1 + 30x + x4 = 200 Fungsi tujuan diubah menjadi : z - 100.000x1 - 150.000x2 = 0 b. Menyusun persamaan-persamaan di dalam tabel Fungsi tujuan dan batasan yang telah diubah disusun dalam tabel simpleks berikut :



Tabel A. Solusi Simpleks Relaksasi pada Mode 1



7



Variabel



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



dasar



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 Indeks = Nilai kolom NK : Nilai kolom kunci 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.



8



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) Baris pertama -150.000



-100.000



-150.0000



0



0



koefisien



0,5



1



0



0,33



6,67



-25.000



0



0



49.500



1.000.500



-



Nilai baru. Baris kunci ● Baris fungsi x3 diubah dengan rumus : Baris baru = baris lama – ( koefisien pada kolom kunci x nilai baru baris kunci)



9



Baris lama 4.000.00



8.000.000



4.000.000



1



koefisien



0,5



1



0,33



6.000.000



0 0



1



0



40.000.000 6,67



-1.320.000



13.320.000



Nilai baru. Baris kunci i. Melanjutkan perbaikan-perbaikan/perubahan-perubahan Karena kolom kunci adalah kolom x2 dan baris kunci adalah baris x4, maka x2 masuk kedalaman variabel dasar menggantikan x4, sehingga tabel A akan berubah menjadi : Tabel B. Solusi Simpleks Relaksasi pada Note 1 Variabel



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



dasar



⮚ Memilih kolom kunci



10



Kolom kunci pada tabel diatas adalah kolom yang mempunyai nilai negatif dengan angka terbesar pada baris fungsi tujuan, yaitu kolom x1 dengan nilai -25.000. ⮚ Menentukan nilai indeks pada tiap-tiap baris Nilai indeks pada masing-masing baris ditentukan dengan rumus Indeks = Nilai kolom NK : Nilai kolom kunci Indeks baris x3 = 13.320.000 : 6.000.000 =10 Indeks baris x2 = 6,67 : 0,5= 13,34 memilih baris kunci Karena nilai indeks positif dengan angka terkecil terdapat pada baris x3, maka baris x3 dinyatakan sebagai 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 Baris kunci x3 diubah dengan cara membagi angka-angkanya dengan 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



11



⮚ 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) -25.000



0



0



49.500



1.000.500



1



0



0



-0,22



2,22



0



0



44.000



1.056.000



-25.000 0



-



● Baris x2 diubah dengan rumus : Baris baru = baris lama – ( koefisien pada kolom kunci x nilai baru baris kunci)



0,5



0,5



1



0



0,033



6,67



1



0



0



-0,22



2,22



0



1



0



0,143



5,56



-



Karena kolom kunci adalah kolom x1 dan baris kunci adalah baris x3, maka x1 masuk ke dalam variabel dasar menggantikan x3 sehingga tabel B akan berubah menjadi :



Tabel C. Solusi optimal Simpleks Relaksasi pada Node 1



12



Variabel



Z



X1



X2



X3



X4



NK



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



Indeks



dasar



Pada tabel C, seluruh elemen 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 x1 = 2.22 dan x2 = 5.56. Langkah 2. Menyatakan solusi persoalan program linear relaksasi sebagai batas atas ( upper bound) dan pembulatan kebawah 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 x1 = 2,22 dan x2 = 5,56 b. Batas bawah 950.000 dengan x1 = 2 dan x2 = 5 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 : x2 ≤ 5 dan x2 ≥ 6



13



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 : BA = 1.056.000 (X 1= 2,22 , X2=5,56) BB = 950.000 (X1=2 , X2=5)



X2 ≤ 5



X2 ≥ 6



Langkah 5. Menyelesaikan model program linear relaksasi dengan batasan baru yang ditambahkan pada tiap Node NODE 2 Memaksimumkan : z = 100.000x1 + 150.000x2 Berdasarkan.



: (1) 8.000.000x1 + 4.000.000x2 ≤ 40.000.000 (2) 15x1 + 30x2 ≤ 200 (3) x2 ≤ 5 (4) x1 , x2 ≥ 0



14



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 variabel x3, sehingga : 8.000.000x1 + 4.000.000x2 + x3 = 40.000.000 Batasan (2) harus ditambah dengan sebuah slack variabel x4, sehingga : 15x1 + 30x2 + x4 = 200 Batasan (3) harus ditambah dengan sebuah slack variabel x5 x2 + x5 = 5 Fungsi tujuan diubah menjadi : z - 100.000x1 - 150.000x2 = 0 b. Menyusun persamaan-persamaan di dalam tabel Fungsi tujuan dan batasan yang telah diubah disusun dalam tabel simpleks berikut :



15



Tabel A. Solusi Simpleks relaksasi pada Node 2 Variabel



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,033



1



5



5



dasar



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 Indeks = Nilai kolom NK : Nilai kolom kunci Indeks baris x3 = 40.000.000 : 4.000.000 =10 Indeks baris x4 = 200 : 30 = 6,67 Indeks baris x5 = 5: 1= 5 e. Memilih baris kunci Karena nilai indeks positif dengan angka terkecil terdapat pada baris x5, maka baris x5 dinyatakan sebagai baris kunci.



16



f. Menentukan angka kunci Angka kunci pada tabel di atas adalah 1, 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 (1) ● Kolom x1 baris x5 = 0 : 1 = 0.5 ● Kolom x2 baris x5 = 1 : 1 = 1 ● Kolom x3 baris x5 = 0 : 1 = 0 ● Kolom x4 baris x5 = 0 : 1 = 0 ● Kolom NK baris x5 = 5 : 1 = 5 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)



-150.000



-100.000



-150.000



0



0



0



0



0



1



0



0



1



5



0



150.000



-100.000



0



0



-



750.000



● Baris x3 diubah dengan rumus :



17



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



4.000.000 1



0



0



40.000.000



1



5



0



1



0



0



8.000.000



0



1



0 -400000



-



20.000.000



● Baris x4 diubah dengan rumus : Baris baru = baris lama – ( koefisien pada kolom kunci x nilai baru baris kunci)



30



15



30



0



1



0



200



0



1



0



0



1



5



15



0



0



1



-30



50



-



i. Melanjutkan perbaikan-perbaikan/perubahan-perubahan Karena kolom kunci adalah kolom x2 dan baris kunci adalah baris x5, maka x2 masuk kedalaman variabel dasar menggantikan x5, sehingga tabel A akan berubah menjadi :



Tabel B. Solusi Simpleks relaksasi pada Node 2



18



Variabel



Z X1



X2



X3



X4



X5



NK



Indeks



Z



1



-100.000



0



0



0



150.00



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



63,33



X2



0



0



1



0



0



1



5



∞



dasar



⮚ Memilih kolom kunci Kolom kunci pada tabel diatas adalah kolom yang mempunyai nilai negatif dengan angka terbesar pada baris fungsi tujuan, yaitu kolom x1 dengan nilai -100.000. ⮚ Menentukan nilai indeks pada tiap-tiap baris Nilai indeks pada masing-masing baris ditentukan dengan rumus Indeks = Nilai kolom NK : nilai kolom kunci Indeks baris x3 = 20.000.000 : 8.000.000 =2,5 Indeks baris x4= 50 : 15= 3,33 Indeks baris x2 = 5 : 0 = ∞



⮚ Memilih baris kunci Karena nilai indeks positif dengan angka terkecil terdapat pada baris x3, maka baris x3 dinyatakan sebagai baris kunci. 19



⮚ Menentukan angka kunci Angka kunci pada tabel di atas adalah 8.000.000, karena merupakan nilai yang termasuk kolom kunci sekaligus baris kunci. ⮚ Mengubah nilai-nilai baris kunci Baris kunci x3 diubah dengan cara membagi angka-angkanya dengan 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 ● 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 : 8.000.000 = 2.5 ⮚ 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



-100.000



0



0



0



150.000



1



0



0



0



-0,5



0



0



0



0



100.000



750.000 2,5



-



1.000.000



20



● Baris x4 diubah dengan rumus : Baris baru = baris lama – ( koefisien pada kolom kunci x nilai baru baris kunci)



15



15



0



0



1



-30



50



1



0



0



0



-0,5



2,5



0



0



0



1



-22,5 12,5



-



● Baris x2 diubah dengan rumus : Baris baru = baris lama – ( koefisien pada kolom kunci x nilai baru baris kunci)



0



0



1



0



0



1



5



1



0



0



0



-0,5



2,5



0



1



0



0



1



5



-



Karena kolom kunci adalah kolom x1 dan baris kunci adalah baris x3, maka x1 masuk ke dalam variabel dasar menggantikan x3 sehingga tabel B akan berubah menjadi :



Tabel C. Solusi optimal simpleks relaksasi pada Node 2



21



Variabel



Z



X1



X2



X3



X4



X5



NK



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



Indeks



dasar



Pada tabel C, seluruh elemen pada baris fungsi tujuan tidak ada lagi yang bernilai 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 x1 = 2,2 dan x2 = 5. Dari tabel C solusi optimal simpleks relaksasi pada Node 2 diperoleh : Batas atas 1.000.000 dengan x1 = 2,5 dan x2 = 5 Batas bawah 950.000 dengan x1 = 2 dan x2 = 5 NODE 3 Memaksimumkan : z = 100.000x1 + 150.000x2 Berdasarkan.



:



(1) 8.000.000x1 + 4.000.000x2 ≤ 40.000.000 (2) 15x1 + 30x2 ≤ 200 (3) x2 ≥ 6



22



(4) x1 , x2 ≥ 0 Persoalan yang telah dinyatakan dalam bentuk model matematis seperti di atas diselesaikan dengan menggunakan metode simpleks sebagaimana pada langkah penyelesaian untuk Node 2, sehingga diperoleh solusi optimal relaksasi pada Node 3, seperti tampak pada tabel berikut : Tabel. Solusi optimal simpleks relaksasi pada Node 3 Variabel



Z X1 X2 X3 X4



X5



X6



NK



Z



1 0



0



0



6.600



50.000



M-50.000



1.340.000



X3



0 0



0



1



-528.00



-12.000.00



12.000.000 5.280.000



X1



0 1



0



0



0



0



X2



0 0



0



0



0,066



2



0



-1



Indeks



dasar



-2



1,34



1



6



Pada tabel diatas, seluruh elemen pada baris fungsi tujuan tidak ada lagi yang bernilai 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.034.000 dengan x1 = 1,34 dan x2 = 6 Dari tabel diatas solusi optimal simpleks relaksasi pada Node 3 diperoleh : a. Batas atas 1.034.000 dengan x1 = 1,34 dan x2 = 6 b. Batas bawah 1.000.000 dengan x1 = 1 dan x2 = 6



23



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 x1 ≤ 1 dan x2 ≥ 2. Sehingga diperoleh dua Node baru yang merupakan cabang dari Node 3. Jika langkah pengerjaan diteruskan hingga hasil yang paling optimal dan berupa bilangan bulat, maka diperoleh :



BA = 1.056.000 (x 1 = 22,2, x2 = 5,56)



24



BB = 950.000 (x1 = 2, x2 = 5)



BA = 1.000.000 (x 1 = 2,5, x2 = 5)



x2 ≤ 5



BB = 950.000 (x1 = 2, x2 = 5)



BA = 1.034.000 (x 1 = 1,34, x2 = 6) x2 ≥ 6



BB = 1.000.000 (x1 = 1, x2 =



6)



x1 ≤ 1



x1 ≥ 2



BA = 1.025.500 (x 1 = 1, x2 = 6,17) BB = 1.000.000 (x1 = 1, x2 = 6) x2 ≤ 6



x2 ≥ 7



BA = 1.000.000 (x 1 = 1, x2 = 6) BB = 1.000.000 (x1 = 1, x2 = 6) Gambar di atas menunjukkan bahwa solusi bilangan bulat optimal telah tercapai pada node 6, yaitu z = 1.000.000 untuk x1 = 1 dan x2 = 6. 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 yg diperoleh pada Node 6. Sedangkan solusi pada node 5 dan 7 tidak layak.



25



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 : Batas atas 1.056.000 dengan x1 = 2,22 dan x2 = 5,56 Batas bawah 1.000.000 dengan x1 = 1 dan x2 = 6 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 linear 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. 7



2.4 Soal latihan: 7



Hayatun Nufus, ibid.



26



1. Misalkan sebuah perusahaan PT. Lightning merakit 3 jenis senter. Senter jenis A, senter jenis B, dan senter jenis C. senter jenis A dirakit dengan membutuhkan waktu 3 menit, jenis B selama 8 menit dan jenis C selama 5 menit. Waktu pengerjaan yang tersedia tiap minggunya selama 1500 menit. Senter jenis A membutuhkan besi seberat 9 gram, senter jenis B membutuhkan besi seberat 6 gram, dan senter jenis C membutuhkan besi seberat 7 gram. Jumlah besi yang dapat disediakan oleh perusahaan hanya 2000 gram tiap minggunya. Untuk senter jenis A membutuhkan aluminium seberat 5 gram, senter B membutuhkan aluminium seberat 3 gram, dan senter C seberat 8 gram. Jumlah aluminium yang dapat disediakan oleh perusahaan tiap minggunya mencapai 1800 gram. Jika keuntungan bersih yang diperoleh dari hasil penjualan senter A, senter B, senter C berturut-turut adalah sebesar Rp9000, Rp 7000, Rp 8000. Berapa kombinasi dari ketiga senter ini yang harus diproduksi sehingga keuntungan dapat maksimum? Jawaban akhir: Jadi perusahaan harus memproduksi senter A sebanyak 47, senter B sebanyak 62 dan senter C sebanyak 172 agar menghasilkan keuntungan optimum 2.233.000. 2. Sebuah perusahaan mie kering memproduksi 2 jenis produk, yaitu jenis A dan jenis B. Masing-masing jenis produk melalui tahapan proses yaitu pembuatan adonan dan pengeringan. Waktu yang diperlukan untuk pembuatan adonan mie jenis A adalah 6 jam, sedangkan untuk mie jenis B adalah 5 jam. Sedangkan waktu yang diperlukan untuk pengeringan mie jenis A adalah 2 jam, dan untuk mie jenis B adalah 3 jam. Perusahaan tersebut hanya mempunyai waktu untuk pembuatan adonan selama 30 jam dan waktu pengeringan 12 jam per minggu. Mie jenis A menghasilkan keuntungan Rp8.000,00 per kg sedangkan mie jenis B menghasilkan keuntungan Rp7.000,00 per kg. Berapakah keuntungan maksimal dari memproduksi mie kering tersebut?



27



Jawaban akhir: Jadi, keuntungan maksimal dari memproduksi mie kering adalah 40,5 dan 40.



BAB III



28



PENUTUP



3.1 Kesimpulan 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.



3.2 Saran Adapun saran yang penulis dapat kemukakan adalah apabila pemateri mempresentasikan hasil makalahnya sebaiknya peserta diskusi memperhatikan dengan baik sehingga penjelasannya itu tidak diulang-ulang guna mengefesienkan waktu.



DAFTAR PUSTAKA



29



A Pasaribu, priandy Hasian, Implementasi Metode Branch and Bound dalam Mengoptimalkan Arum pratiwi. Implementasi Algoritma Branch and Bound (UNNES Journal 0f Mathematics) Gede Suryawan. Penerapan Branch and Bound Algorithm. Jurnal Matematika Hayatun Nufus, Erdawati. 2016. Program Linear. Pekanbaru: Cahaya Firdaus Ilyas Masudin, Linear Programming dengan R : (Aplikasi untuk Teknik Industri). (Malang, Universitas Muhammadiyah Malang, 2018) Jumlah Produk guna Memaksimalkan Keuntungan (Studi Kasus: CV. Ridho Mandiri). Margiyani, Aplikasi Algoritma Branch and Bound. Yogyakarta: Universitas Islam Sunan Kalijaga



30