Branch and Bound QM [PDF]

Citation preview

IMPLEMENTASI METODE BRANCH AND BOUND DALAM MENGOPTIMALKAN JUMLAH PRODUK GUNA MEMAKSIMALKAN KEUNTUNGAN (Studi Kasus: CV. Ridho Mandiri)



SKRIPSI



APRIANDY HASIAN PASARIBU 140803061



DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2018



UNIVERSITAS SUMATERA UTARA



IMPLEMENTASI METODE BRANCH AND BOUND DALAM MENGOPTIMALKAN JUMLAH PRODUK GUNA MEMAKSIMALKAN KEUNTUNGAN (Studi Kasus: CV. Ridho Mandiri)



SKRIPSI



Ditulis Sebagai Syarat untuk Mencapai Gelar Sarjana Sains di Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara.



APRIANDY HASIAN PASARIBU 140803061



DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2018



UNIVERSITAS SUMATERA UTARA



PERNYATAAN ORISINALITAS



IMPLEMENTASI METODE BRANCH AND BOUND DALAM MENGOPTIMALKAN JUMLAH PRODUK GUNA MEMAKSIMALKAN KEUNTUNGAN (Studi Kasus: CV. Ridho Mandiri)



SKRIPSI



Saya menyatakan bahwa skripsi ini adalah hasil karya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.



Medan,



April 2018



Apriandy Hasian Pasaribu 140803061



UNIVERSITAS SUMATERA UTARA



PENGESAHAN SKRIPSI



Judul



Kategori Nama Nomor Induk Mahasiswa Program Studi Departemen Fakultas



: Implementasi Metode Branch and Bound Dalam Mengoptimalkan Jumlah Produk Guna Memaksimalkan Keuntungan (Studi Kasus: CV. Ridho Mandiri) : Skripsi : Apriandy Hasian Pasaribu : 140803061 : Sarjana (S1) Matematika : Matematika : Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara



Disetujui di Medan,



April 2018



Ketua Program Studi Departemen Matematika FMIPA USU



Pembimbing



Dr. Suyanto, M.Kom NIP. 19590813 198601 1 002



Dra. Laurentina Pangaribuan, M.Si NIP. 19540828 198103 1 004



i



UNIVERSITAS SUMATERA UTARA



IMPLEMENTASI METODE BRANCH AND BOUND DALAM MENGOPTIMALKAN JUMLAH PRODUK GUNA MEMAKSIMALKAN KEUNTUNGAN (Studi Kasus: CV. Ridho Mandiri)



ABSTRAK



Kelancaran proses produksi sangat ditentukan oleh perencanaan produksi yang baik. Perencanaan produksi berhubungan dengan penentuan volume produksi, ketetapan waktu penyelesaian dan pemanfaatan bahan baku yang tersedia.. CV. Ridho Mandiri merupakan perusahaan yang bergerak dalam bidang tekstil. Bahan baku yang digunakan ada tujuh belas jenis yaitu full cotton, pewarna, resleting, kancing paku, kancing rivet, Mr. kertas, Stn.kt.belakang, Stn.kt.depan, Stn.cara cuci, Stn.nomor celana, kulit pinggang, Kt.belakang, Kt.depan, sticker, pembungkus, saten pinggang , merk. Penelitian bertujuan untuk untuk mengoptimalkan bahan baku pembuatan celana jeans di CV. Ridho Mandiri.. Program linier adalah suatu teknik penyelesaian optimal atas suatu problema keputusan dengan cara menentukan terlebih dahulu fungsi tujuan dan fungsi kendala yang ada ke dalam model matematik persamaan linier. Metode Branch and Bound adalah metode umum untuk mencari solusi optimal dari berbagai permasalahan optimasi, Prinsip kerja metode Branch and Bound adalah mencabangkan variabel keputusan yang tidak memiliki penyelesain bulat, percabangan dilakukan terus hingga diperoleh penyelesaian bulat sehingga semua variabel keputusannya bernilai bulat. Tujuan dari penelitian ini adalah untuk memperlihatkan bahwa metode Branch and Bound pada linear programming merupakan salah satu alternatif yang dapat digunakan untuk mengoptimalkan bahan baku pembuatan celana jeans di CV. Ridho Mandiri. Dari hasil analisis menggunakan metode Branch and Bound, jumlah celana yang optimal diproduksi yaitu 155 lusin celana pendek ukuran kecil, 165 lusin celana pendek ukuran big size, 138 lusin celana penek ukuran super jumbo, 178 lusin celana panjang ukuran kecil, 85 lusin celana panjang ukuran big size dan 237 lusin celana panjang ukuran super jumbo dengan keuntungan sebesar Rp. 903.567.400 dan Dengan menggunakan metode Branch and Bound, keuntungan naik sebesar 4,3 % atau Rp. 37.335.715 dari keuntungan perusahaan.



Kata Kunci: branch and bound, program linier



ii



UNIVERSITAS SUMATERA UTARA



IMPLEMENTATION OF BRANCH AND BOUND METHOD IN OPTIMIZING AMOUNT OF PRODUCTS TO USE MAXIMIZE THE PROFITS (Case Study: CV Ridho Mandiri)



ABSTRACT



The smoothness of the production process is largely determined by good production planning. Production planning is related to the determination of production volume, timing of completion and utilization of available raw materials. CV. Ridho Mandiri is a company engaged in the field of textiles. The raw materials used there are seventeen types namely full cotton, dye, zipper, nail button, button rivet, Mr. paper, Backstage, Front Line, Wash wash, Stn. trouser number, waist skin, Kt.belakang, Kt.depan, sticker, wrapping, satin belt, brand. The research aims to optimize the raw material of making jeans in CV. Ridho Mandiri Linear program is a technique of optimal settlement of a decision problem by first determining the purpose function and function of the existing constraints into the mathematical model of linear equations. The Branch and Bound method is a common method for finding the optimal solution of various optimization problems. The working principle of the Branch and Bound method is to decompose decision variables that do not have a round resolving, branching is done until the round completion is reached so that all decision variables are round. The purpose of this research is to show that Branch and Bound method on linear programming is one alternative that can be used to optimize the raw material of jeans pants in CV. Ridho Mandiri. From the results of the analysis using the Branch and Bound method, the optimal number of trousers produced is 155 dozen small shorts, 165 dozen shorts big size size, 138 dozen super jumbo shorts, 178 dozen small pants, 85 dozen size trousers big size and 237 dozen super jumbo size trousers with a profit of Rp. 903.567.400 and By using the method of Branch and Bound, profits rose by 4,3% or Rp.37.335.715 of company profits.



Keywords: linear programming, branch and bound



iii



UNIVERSITAS SUMATERA UTARA



PENGHARGAAN



Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa atas berkat dan karunia-Nya penulis dapat menyelesaikan skripsi ini dengan judul “IMPLEMENTASI METODE BRANCH AND BOUND DALAM MENGOPTIMALKAN JUMLAH PRODUK GUNA MEMAKSIMALKAN KEUNTUNGAN (Studi Kasus: PT. CV. Ridho Mandiri)” dengan baik dan tepat waktu. Penulis mengucapkan terima kasih kepada semua pihak yang telah membantu dan membimbing penulis dalam penyusunan skripsi ini. Ucapan terima kasih penulis sampaikan kepada: 1. Ibu Dra. Laurentina Pangaribuan, MS selaku dosen pembimbing penulis atas segala waktu dan arahan yang diberikan selama penyusunan skripsi ini. 2. Bapak Prof. Dr. Tulus M.Si dan Bapak Drs. Gim Tarigan M.Si selaku dosen pembanding atas segala saran dan masukan yang diberikan selama penyelesaian skripsi ini. 3. Bapak Dr. Suyanto, M.Kom dan Drs. Rosman Siregar, M.Si selaku Ketua dan Sekretaris Departemen Matematika FMIPA USU. 4. Bapak Dr. Kerista Sebayang, MS selaku Dekan FMIPA USU serta semua Wakil Dekan FMIPA USU. 5. Semua Dosen Departemen Matematika FMIPA USU dan pegawai di FMIPA USU. 6. Ibunda T. Hutapea atas segala dukungan moral maupun materil dan doa yang telah diberikan selama ini terkhusus pada penyelesaian skripsi ini serta semua abang dan keluarga penulis. 7. Teman-teman jurusan Matematika khususnya stambuk 2014 yang selalu mendukung penulis, adik-adik stambuk 2015, satambuk 2016, stambuk 2017 serta Abang dan Kakak Alumni. Penulis menyadari bahwa masih banyak kekurangan dalam penulisan skripsi ini. Oleh karena itu, penulis menerima saran dan kritik yang positif dan membangun dari pembaca untuk penyempurnaan skripsi ini.



Medan, Penulis



Maret 2018



Apriandy Hasian Pasaribu



iv



UNIVERSITAS SUMATERA UTARA



DAFTAR ISI Halaman i



PENGESAHAN ABSTRAK ABSTRACK PENGHARGAAN DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR



ii iii iv v vii viii



BAB 1 PENDAHULUAN 1.1 Latar Belakang 1.2 Perumusan Masalah 1.3 Batasan Masalah 1.4 Tujuan Penelitian 1.5 Manfaat Penelitian 1.6 Tinjauan Pustaka 1.7 Lokasi Penelitian 1.8 Metodologi Penelitian



1 3



4 4 4 5 6 6



BAB 2 LANDASAN TEORI 2.1 Program Linear 2.1.1 Model Program Linear 2.1.2 Terminologi Umum dan Asumsi-Asumsi Dasar Program Linier 2.2 Metode Grafik 2.3 Metode Simpleks 2.4 Program Integer 2.5 Metode Branch and Bound (Pencabangan dan Pembatasan) 2.5.1 Langkah-Langkah Metode Branch and Bound 2.5.2 Syarat Pencabangan (Fathoming) Berhenti 2.5.3 Syarat Kondisi Optimal 2.6 Software QM BAB 3 METODOLOGI PENELITIAN 3.1 Merumuskan Masalah 3.2 Studi Literatur dan Studi Kasus 3.3 Pengamatan dan Pengumpulan Data 3.3.1 Proses Produksi 3.3.2 Jenis-Jenis Celana 3.3.3 Bahan Baku dan Waktu Produksi Celana 3.3.4 Harga Jual, Biaya Produksi dan Keuntungan Penjualan Celana 3.4 Pengolahan Data 3.4.1 Memodelkan Permasalahan Menjadi fungsi Tujuan dan Fungsi Kendala di dalam Model



v



8 10 11 12 16 24 25 26 27 27 29



17 21 24 32 33 33 35 35 36



UNIVERSITAS SUMATERA UTARA



Matematika 3.4.2 Menghitung nilai variabel keputusan dengan menggunakan metode simpleks pada linear programming 3.4.3 Menghitung nilai variabel keputusan menggunakan Software QM 3.4.4 Mencari nilai optimal dengan metode Branch and Bound 3.5 Penarikan kesimpulan



38



43 46 47



BAB 4 HASIL DAN PEMBAHASAN 4.1 Perumusan Data ke dalam Model Matematika 4.2 Pengolahan Data 4.3 Analisis Metode Branch and Bound



48 49 50



BAB 5 KESIMPULAN DAN SARAN 5.1 Kesimpulan 5.2 Saran



59 59



DAFTAR PUSTAKA LAMPIRAN



60 61



vi



UNIVERSITAS SUMATERA UTARA



DAFTAR TABEL



Nomor



Judul



2.1 2.2 2.3 2.4



Contoh soal Metode Grafik Bentuk Tabel Simpleks Tabel Simpleks yang Pertama Tabel Simpleks : Pemilihan kolom kunci pada tabel pertama Tabel Simpleks : Cara mengubah nilai baris kunci Tabel Simpleks : Melanjjutkan Perbaikan Tabel Simpleks : Hasil Akhir Perbaikan Jenis Celana Jeans Data Bahan Baku Data Persediaan Bahan Baku Data Biaya Produksi, Harga Jual dan Keuntungan Penjualan Simbol Variabel Keputusan Tabel Simpleks pertama Tabel baru metode simpleks Tabel Akhir Metode Simpleks Iterasi I Metode Simpleks dengan Software QM Iterasi II Metode Simpleks dengan Software QM Iterasi III Metode Simpleks dengan Software QM Iterasi IV Metode Simpleks dengan Software QM Iterasi V Metode Simpleks dengan Software QM Iterasi VI Metode Simpleks dengan Software QM Iterasi VII Metode Simpleks dengan Software QM Solusi dari Hasil Iterasi dengan Software QM Hasil Akhir Metode Branch and Bound



2.5 2.6 2.7 3.1 3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10 3.11 3.12 3.13 3.14 3.15 4.1 4.2



Halaman



vii



13 18 20 20 21 23 24 33 33 34 35 36 39 42 42 43 43 43 44 44 45 45 48 35



UNIVERSITAS SUMATERA UTARA



DAFTAR GAMBAR



Nomor Judul 2.1 2.2 2.3 2.4 2.5 4.1



Halaman



Grafik Batasan Pertama Grafik Contoh Soal Grafik Fungsi Tujuan Langkah-langkah Metode Branch and Bound Diagram Metode Branch and Bound Diagram Branch and bound pada titik



viii



14 15 15 29 30 57



UNIVERSITAS SUMATERA UTARA



BAB 1 PENDAHULUAN



1.1 Latar Belakang Seiring dengan perkembangan zaman membuat persaingan di dunia industri semakin



meningkat. Industri



diantara



banyaknya



modern semakin



industri yang



banyak



yang



bermunculan,



bermunculan, cukup banyak industri yang



menghasilkan produk-produk yang sejenis. Untuk memenuhi tuntutan konsumen akan kebutuhan produk tersebut, maka setiap industri tentu akan terus berusaha untuk selalu berinovasi dalam mengembangkan produk mereka sesuai dengan permintaan



dari para konsumen. Suatu



perusahaan dituntut untuk memiliki



keunggulan kompetitif agar dapat bertahan di tingkat nasional maupun internasional. Dengan strategi



perencanaan



produksi perusahaan yang



tepat menjadikan



perusahaan yang maju serta memiliki keuntungan maksimal. Aspek produksi merupakan salah satu aspek paling penting dalam suatu perusahaan. Besar kecilnya keuntungan yang diterima oleh suatu



perusahaan



tergantung pada seberapa besar suatu produk mampu dihasilkan oleh perusahaan yang bersangkutan. Peningkatan produksi dan melaksanakan kegiatan produksi yang efisien



penting dilakukan oleh setiap perusahaan dengan memiliki perencanaan



produksi. Perencanaan produksi berhubungan dengan penentuan volume produksi, ketetapan waktu penyelesaian dan pemanfaatan sumber daya yang tersedia. Perencanaan produksi merupakan perencanaan tentang produk apa saja dan berapa jumlah yang akan diproduksi oleh perusahaan dalam waktu satu periode yang akan datang. Perencanaan produksi bertujuan untuk optimasi produksi sehingga dapat memaksimalkan keuntungan. CV. Ridho Mandiri adalah sebuah perusahaan nasional yang bergerak di industri tekstil. CV. Ridho Mandiri telah berproduksi sejak Agustus 1990, CV. Ridho Mandiri



memproduksi dua produk celana jeans(panjang dan pendek) dengan



berbagai macam warna dan ukuran, Perusahaan ini menggunakan bahan utama yaitu full catoon, stretch, polyester, aksesoris serta memiliki pewarnaan dengan 12 warna..



UNIVERSITAS SUMATERA UTARA



2



Dengan berbekal pengalaman selama 27 tahun, CV. Ridho Mandiri memahami dan mengerti hal–hal terbaik untuk membuat celana dengan kualitas yang unggul. Produk-produk ini di pasarkan ke beberapa provinsi yang ada di Indonesia. CV. Ridho Mandiri memproduksi satu merk yaitu LOOK OUT. Perusahaan perlu membuat perencanaan produksi yang optimal untuk dapat bersaing di pasar nasional maupun internasional. Setiap pelaku usaha atau pelaku ekonomi pasti melakukan apa yang disebut dengan prinsip ekonomi, yaitu dengan usaha atau modal yang sedikit mampu menghasilkan keuntungan yang banyak, sehingga muncul masalah optimisasi. Masalah optimisasi tersebut meliputi meminimumkan biaya atau memaksimumkan keuntungan dengan kapasitas sumber daya yang ada agar mampu mendapatkan hasil yang optimal. Optimalisasi merupakan proses mencari solusi optimal dari sebuah permasalahan dengan menggunakan model matematis dan pemecahannya dapat menggunakan program linier. Program linier pertama kali diperkenalkan oleh George Dantzig (1947) yang pada awalnya banyak dipakai pada bidang perencanaan militer, khususnya dalam perang dunia II oleh angkatan bersenjata Amerika Serikat dan Inggris. Metode pengerjaan program linier umumnya menggunakan metode grafik dan metode simpleks. Program linier adalah suatu teknik penyelesaian optimal atas suatu problema keputusan dengan cara menentukan terlebih dahulu fungsi tujuan dan fungsi kendala yang ada ke dalam model matematik persamaan linier dan dengan tujuan menemukan beberapa kombinasi alternatif pemecahan optimum. Program bilangan bulat atau program integer adalah sebuah program linier dengan persyaratan tambahan bahwa semua variabelnya merupakan bilanganbilangan bulat. Dalam hal ini, metode penyelesaian masalah yang digunakan adalah metode Cabang dan Batas (Branch and Bound). Berdasarkan penelitian sebelumnya di perusahaan furniture PT. Putra Jepara memiliki hasil perhitungan matematis dari model atau permasalahan yang telah diberikan, dengan menggunakan metode simpleks diperoleh hasil 2 unit lemari pakaian, 45.5 set meja makan, dan 3 unit lemari jam, serta 1 set kursi tamu yang memberikan nilai 𝑍 sebesar Rp. 107.496.000,-. Berdasarkan hasil penelitian tersebut untuk mecapai hasil yang optimal sebagaimana yang di tujukan dengan harus memproduksi 45.5 set meja makan, namun bahwa hasil tersebut tidak rasional, dalam



UNIVERSITAS SUMATERA UTARA



3



kasus ini 45,5 set meja harus diselesaikan dengan 45 atau 46 (bukan 45.5). dalam hal ini digunakan metode branch and bound. Dari hasil perhitungan dengan metode branch and bound diperoleh 2 unit lemari pakaian, 46 set meja makan, 2 unit lemari jam dan 1 set kursi tamu yang memberikan nilai 𝑍 sebesar Rp. 107.087.000,- dan semua variabel keputusannya bernilai bulat dan memiliki keuntungan yang maksimal. Permasalahan seperti ini biasanya menuntut solusi yang optimum agar dapat diperoleh keuntungan yang sebesar-besarnya. Salah satu model untuk mempresentasikan suatu permasalahan adalah Program Linear. Salah satu dari program linear yaitu integer programming. Integer Programming adalah sebuah model matematis yang memungkinkan hasil penyelesaian kasus pada pemrograman linear yang berupa bilangan bulat. Metode untuk menyelesaikan persoalan integer programming adalah metode Branch and bound dan metodei ini ialah metode yang paling efisien dari semua metode di integer programming. Dengan metode ini akan dibuat percabangan dan perpotongan yang akan menghasilkan pemecahan optimum dari masalah program linear untuk bergerak ke arah pemecahan integer atau mixed integer yang diinginkan. Metode branch and bound adalah salah satu metode untuk menghasilkan penyelesaian optimal program linear yang menghasilkan variabel-variabel keputusan bilangan bulat. Prinsip kerja metode branch and bound adalah mencabangkan variabel keputusan yang tidak memiliki penyelesain bulat, percabangan dilakukan terus hingga diperoleh penyelesaian bulat sehingga semua variabel keputusannya bernilai bulat dan menghasilkan keuntungan maksimal bagi perusahaan. Berdasarkan



persoalan



tersebut



peneliti



ingin



meneliti



tentang



“Implementasi Metode Branch and Bound Dalam Mengoptimalkan Jumlah Produk Guna Memaksimalkan Keuntungan (Studi Kasus : CV. Ridho Mandiri)”. 1.2 Perumusan Masalah Permasalahan yang akan dibahas dalam penelitian ini adalah cara untuk mengoptimalkan bahan baku yang tidak digunakan dengan menggunakan metode branch and bound sehingga perusahaan dapat memperoleh keuntungan yang maksimal.



UNIVERSITAS SUMATERA UTARA



4



1.3 Batasan Masalah



Agar penelitian yang dilakukan dapat menghasilkan penelitian yang fokus dan akurat, maka diberikan batasan masalah sebagai berikut: 1. Dipilih 6 produk celana yaitu : celana jeans panjang ukuran kecil, celana jeans panjang ukuran big size, celana jeans panjang ukuran super jumbo, celana jeans pendek ukuran kecil, celana jeans pendek ukuran big size, celana jeans pendek ukuran super jumbo. 2. Dalam menyelesaikan produksi, harga bahan baku dianggap konstan. 3. Kondisi perusahaan dianggap dalam keadaan normal (kebijakan perusahaan tidak berubah selama jangka waktu pemecahan masalah).



1.4 Tujuan Penelitian Tujuan utama dari penelitian ini adalah untuk memperlihatkan bahwa



metode



Branch and Bound pada linear programming merupakan salah satu alternatif yang dapat digunakan untuk mengoptimalkan bahan baku pembuatan celana jeans di CV. Ridho Mandiri.



1.5 Manfaat Penelitian Manfaat dari penelitian ini adalah sebagai berikut: 1) Bagi Perusahaan Penelitian ini dapat dijadikan sebagai salah satu bahan acuan untuk meningkatkan keuntungan dari produksi tekstil di CV. Ridho Mandiri. 2) Bagi Peneliti Peneliti mendapatkan pengalaman dalam mengaplikasikan ilmu pengetahuan yang diperoleh tentang mengoptimalkan jumlah produksi. 3) Bagi Universitas Menambah kepustakaan universitas yang sudah ada, khususnya mengenai pengoptimalan produksi dengan menggunakan linear programming.



UNIVERSITAS SUMATERA UTARA



5



1.6 Tinjauan Pustaka Program linier adalah suatu teknik penyelesaian optimal atas suatu problem keputusan dengan cara menentukan terlebih dahulu fungsi tujuan (memaksimumkan atau meminimumkan) dan kendala-kendala yang ada ke dalam model matematik persamaan linier. Program linier sering digunakan dalam menyelesaikan problem alokasi sumber daya (Parlin Sitorus, 1997). Pemrograman linier menggunakan model matematika untuk menggambarkan suatu masalah. Sifat linier di sini berarti semua fungsi matematika harus berupa fungsi linier. Kata pemrograman di sini berarti melainkan perencanaan. Pemrograman linier meliputi perencanaan aktivitas untuk mendapatkan hasil maksimal, yaitu sebuah hasil yang mencapai tujuan terbaik (menurut model matematika) di antara semua kemungkinan alternatif yang ada. Model merupakan suatu penyederhanaan dari permasalahan yang kompleks menjadi lebih sederhana. Ada beberapa klasifikasi model dalam riset operasi, yaitu model ikonik, model analog, model matematik, model simulasi dan model heuristic (Faigiziduhu Bu’lölö, 2016). Metode analisis yang paling bagus untuk menyelesaikan persoalan alokasi sumber ialah metode program linier. Pokok pikiran yang utama dalam menggunakan program linier ialah merumuskan masalah dengan jelas dengan menggunakan sejumlah informasi yang tersedia. Sesudah masalah terumuskan dengan baik, maka langkah berikut ialah menerjemahkan masalah ini ke dalam bentuk model matematika, yang mempunyai cara pemecahan yang lebih mudah dan rapi guna menemukan jawaban terhadap masalah yang dihadapi. Metode simpleks dikembangkan oleh George Dantzig dalam tahun 1947. Dan telah terbukti sebagai metode yang sangat efisien yang dipakai secara rutin untuk menyelesaikan masalah-masalah besar dengan komputer masa kini (Frederick S.Hillier 1994). Metode simpleks berbeda dengan metode grafik karena hanya dapat menyelesaikan kasus dengan variabel keputusan sama dengan 2 sedangkan metode simpleks dapat digunakan untuk memecahkan kasus dengan banyak variabel keputusan. Adapun proses penyusunan model matematik untuk fungsi tujuan dan kendala pada metode simpleks sama dengan proses pada metode grafik. Namun,



UNIVERSITAS SUMATERA UTARA



6



proses perhitungan pada metode simpleks dilakukan secara rutin (berulang) dengan menggunakan pola yang sistematik hingga penyelesaian terbaik dicapai. Proses perhitungan yang rutin ini menunjukkan nilai fungsi tujuan akan sama atau lebih besar dari penyelseaian pada iterasi sebelumnya. Hal ini memberi jaminan bahwa proses ini bergerak kearah penyelesaian optimal. Metode Branch and Bound pertama kali diperkenalkan oleh A.H Land dan A.G. Doig dan dikembangkan lebih lanjut oleh peneliti-peneliti lain. Teknik ini dapat diterapkan baik untuk masalah pure maupun mixed integer programming (Sri Mulyono, 2017). Metode branch and bound adalah salah satu metode untuk menghasilkan penyelesaian optimal program linear yang menghasilkan variabelvariabel keputusan bilangan bulat. Sesuai dengan namanya metode ini membatasi penyelesaian optimum yang akan menghasilkan bilangan pecahan dengan cara membuat cabang atas atau bawah bagi masing-masing variabel keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru (Widi Hartono, 2014). Pencabangan (branching) berarti memecah soal menjadi 2 soal baru (masing-masing ditambah dengan kendala baru) dan menyelesaikan keduanya (Jong Jek Siang, 2014).



1.7 Lokasi Penelitian Penelitian dilakukan di CV. Ridho Mandiri , yang beralamat di Jalan Bromo Gang Sederhana No. 14 Medan. 1.8 Metodologi Penelitian Penelitian disusun dengan langkah-langkah sebagai berikut: 1. Studi Pendahuluan Mengumpulkan dan mempelajari berbagai informasi berupa buku-buku ataupun jurnal-jurnal, maupun makalah yang berkaitan dengan penelitian. 2. Pengumpulan Data Data yang diperoleh dari perusahaan adalah jumlah produksi, data bahan baku, data biaya produksi, waktu penyelesain produksi, jumlah tenaga kerja dan data harga penjualan setiap jenis celana jeans.



UNIVERSITAS SUMATERA UTARA



7



3. Pengolahan Data Tahapan yang dilakukan dalam pengolahan data adalah sebagai berikut: 1. Formulasi Fungsi a. Perumusan Fungsi Tujuan Dalam penelitian



ini yang dijadikan sebagai fungsi tujuannya adalah



maksimasi keuntungan penjualan celana jeans pendek (ukuran kecil, big size, super jumbo) , celana jeans panjang (ukuran kecil, big size, super jumbo). Koefisien dari variabel keputusannya ialah keuntungan dari penjualan masing-masing jenis produk celana jeans. b. Perumusan Fungsi Kendala Fungsi kendala dirumuskan berdasarkan persediaan bahan baku ( full cotton, pewarna, resleting, kancing paku, kancing rivet, Mr. kertas, Stn.kt.belakang, Stn.kt.depan, Stn.cara cuci, Stn.nomor celana, kulit pinggang, pantasi Kt.belakang, pantasi Kt.depan, sticker, pembungkus, saten pinggang , merk). 2. Penyelesaian Model a. Menghitung nilai variabel keputusan dengan menggunakan Software QM. b. Mencari nilai optimal dengan menggunakan metode Branch and Bound. 3. Membuat Kesimpulan Membuat kesimpulan dari hasil perhitungan dan saran yang dapat menjadi masukan bagi pihak perusahaan.



UNIVERSITAS SUMATERA UTARA



BAB 2 LANDASAN TEORI



2.1 Program Linier Program linier merupakan model matematik untuk mendapatkan alternatif penggunaan terbaik atas sumber-sumber organisasi. Kata sifat linier digunakan untuk menunjukkan fungsi-fungsi matematik yang digunakan dalam bentuk linier dalam arti hubungan langsung dan persis proporsional. Program menyatakan penggunaan teknik matematik tertentu. Jadi pengertian program linier adalah suatu teknik perencanaan yang bersifat analitis yang analisisnya menggunakan model matematis, dengan tujuan menemukan beberapa kombinasi alternatif pemecahan optimum terhadap persoalan (Aminudin, 2005). Program linier adalah suatu teknik penyelesaian optimal atas suatu problema keputusan dengan cara menentukan terlebih dahulu fungsi tujuan (memaksimalkan atau meminimalkan) dan kendala-kendala yang ada ke dalam model matematik persamaan linier. Program linier sering digunakan dalam penyelesaian problemaproblema alokasi sumber daya, seperti dalam bidang manufacturing, pemasaran, keuangan, personalia, administrasi, dan lain sebagainya (Sitorus, 1997). Siagian (1987) mengemukakan bahwa pokok pikiran yang paling utama dalam menggunakan program linier adalah merumuskan masalah dengan jelas menggunakan sejumlah informasi yang tersedia. Kemudian menerjemahkan masalah tersebut ke dalam model matematis, yang cara pemecahan masalahnya lebih mudah dan terstruktur agar didapatkan solusinya. Suatu masalah dikatakan sebagai masalah program linier apabila : 1. Tujuan (objective) yang akan dicapai harus dapat dinyatakan dalam bentuk fungsi linier yang disebut sebagai fungsi tujuan (objective function). 2. Harus ada alternatif pemecahan. Pemecahan yang membuat fungsi tujuan optimum (laba yang maksimum, biaya yang minimum, dan sebagainya) yang harus dipilih. 3. Sumber-sumber tersedia dalam jumlah yang terbatas (bahan mentah terbatas, modal terbatas, ruangan untuk menyimpan barang terbatas, dan sebagainya).



UNIVERSITAS SUMATERA UTARA



9



Pembatasan-pembatasan harus dinyatakan di dalam ketidaksamaan yang linier (linear inequality). Pokok pikiran yang utama dalam menggunakan program linier adalah merumuskan masalah dengan jelas dengan menggunakan sejumlah informasi yang tersedia. Sesudah masalah dirumuskan dengan baik, maka langkah berikutnya adalah menerjemahkan masalah ini ke dalam bentuk model matematika, yang mempunyai cara pemecahan yang lebih mudah dan terstruktur guna menemukan solusi terhadap masalah yang dihadapi. Menurut Mulyono (2004), setelah masalah diidentifikasikan, tujuan ditetapkan, langkah selanjutnya adalah formulasi model matematik yang meliputi: 1. Tentukan variabel yang tidak diketahui (variabel keputusan) dan nyatakan dalam simbol matematik. 2. Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier (bukan perkalian) dari variabel keputusan. 3. Menentukan semua kendala masalah tersebut dan mengekspresikan dalam persamaan atau pertidaksamaan yang juga merupakan hubungan linier dari variabel keputusan yang mencerminkan keterbatasan sumber daya masalah tersebut. 2.1.1 Model Program Linier Model persamaan umum dalam program linier dapat dirumuskan sebagai berikut (Aminudin, 2005): Maksimalkan atau minimumkan : 𝑍



∑



Dengan kendala : ∑



Untuk



UNIVERSITAS SUMATERA UTARA



10



Atau dapat ditulis secara lengkap sebagai berikut : Maksimalkan atau minimumkan : 𝑍 Dengan kendala :



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



.



untuk Keterangan : 𝑍



= Fungsi tujuan yang harus dicari nilai optimalnya (maksimal atau minimal) = tingkat kegiatan ke- j = Kenaikan nilai Z terjadi apabila ada pertambahan tingkat kegiatan dengan satu satuan unit atau sumbangan setiap satuan keluaran kegiatan Z terhadap j = Banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit keluaran kegiatan j = Kapasitas sumber i yang tersedia untuk dialokasikan ke setiap unit kegiatan = macam kegiatan yang menggunakan sumber atau fasilitas yang tersedia = macam batasan sumber atau fasilitas yang tersedia



2.1.2 Terminologi Umum dan Asumsi-Asumsi Dasar Program Linier Terminologi umum untuk model program linier dapat dirangkum sebagai berikut: 1. Fungsi yang akan dicari nilai optimalnya (Z) disebut sebagai fungsi tujuan (objective function). 2. Fungsi-fungsi batasan dapat dikelompokkan menjadi dua macam, yaitu : a. Fungsi batasan fungsional, yaitu fungsi-fungsi batasn sebanyak m. b. Fungsi batasan non-negatif (non-negative constrains) yaitu variabel . 3. Variabel-variabel



disebut sebagai variabel keputusan (decision variables).



UNIVERSITAS SUMATERA UTARA



11



4. Parameter model yaitu masukan konstan



,



, dan .



Agar penggunaan model program linier di atas memuaskan tanpa terbentur pada berbagai hal, makan diperlukan asumsi-asumsi dasar program linier sebagai berikut : 1. Proportionality, asumsi ini berarti naik turunnya nilai Z dan penggunaan sumber atau fasilitas yang tersedia akan berubah secara sebanding dengan perubahan tingkat kegiatan. Misal : a. 𝑍 Setiap pertambahan 1 unit pertambahan 1 unit



akan menaikkan Z sebesar



akan menaikkan Z sebesar



Setiap



, dan seterusnya.



b. Setiap pertambahan 1 unit atau fasilitas ke 1 sebesar



akan menaikkan penggunaan sumber daya Dengan kata lain, setiap ada kenaikan



kapasitas riil tidak perlu ada biaya persiapan. 2. Additivity, berarti nilai tujuan tiap kegiatan tidak saling mempengaruhi, atau dalam program linier dianggap bahwa kenaikan suatu kegiatan dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari kegiatan lain. Misal : 𝑍 Di mana



;



Sehingga Z = 120 + 140 = 260 Andaikan



bertambah 1 unit, maka sesuai dengan asumsi pertama, nilai Z



menjadi 260 + 4 = 264. Jadi, nilai 4 karena kenaikan



dapat langsung



ditambahkan pada nilai Z mula-mula tanpa mengurangi bagian Z yang diperoleh dari kegiatan ke 2 ( dan



. Dengan kata lain, tidak ada korelasi antara



.



3. Divisibility, berarti keluaran yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Misal : 𝑍



UNIVERSITAS SUMATERA UTARA



12



4. Deterministic (certainty), berarti bahwa semua parameter (



,



, dan



)



yang terdapat pada program linier dapat diperkirakan dengan pasti, meskipun dalam kenyataannya tidak sama persis. Umumnya masalah program linier dapat diselesaikan dengan menggunakan 2 metode, yaitu metode grafik dan metode simpleks.



2.2. Metode Grafik Masalah program linier dapat diilustrasikan dan dipecahkan secara grafik jika ia hanya memiliki dua variabel keputusan. Meski masalah-masalah dengan dua variabel jarang terjadi dalam dunia nyata, penafsiran geometris dari metode grafis ini sangat bermanfaat. Untuk mencari penyelesaian optimal, dilakukan dengan cara mencari titik penyelesaian optimal yang terdapat di dalam daerah kelayakan. Langkah-langkah penggunaan metode grafik dapat ditunjukkan secara ringkas. sebagai berikut : 1. Menentukan fungsi tujuan dan memformulasikannya dalam bentuk matematis. 2. Mengidentifikasi batasan-batasan yang berlaku dan memformulasikannya dalam bentuk matematis. 3. Menggambarkan masing-masing garis fungsi batasan dalam satu sistem salip sumbu. 4. Mencari titik yang paling menguntungkan (optimal) dihubungkan dengan fungsi tujuan.



Diberikan suatu permasalahan yang akan diselesaikan dengan mwtode grafik sebagi berikut: Contoh 2.1 Perusahaan sepatu SENTOSA membuat 2 macam sepatu. Macam pertama merek I 1, dengan sol dari karet, dan macam kedua merek I2 dengan sol dari kulit. Untuk membuat sepatu-sepatu itu perusahaan memiliki 3 macam mesin. Mesin 1 khusus membuat sol dari karet, mesin 2 khusus membuat sol dari kulit, dan mesin 3 membuat bagian atas sepatu dan melakukan assembling bagian atas dengan sol.



UNIVERSITAS SUMATERA UTARA



13



Setiap lusin sepatu merk I1 mula-mula dikerjakan di mesin 1 selama 2 jam, kemudian tanpa melalui mesin 2 terus dikerjakan di mesin 3 selama 6 jam. Sedangkan untuk sepatu merek I2 tidak diproses di mesin 1, tetapi pertama kali dikerjakan di mesin 2 selama 3 jam kemudian di mesin 3 selama 5 jam. Jam kerja maksimum setiap hari untuk mesin 1 = 8 jam, mesin 2 = 15 jam, dan mesin 3 = 30 jam. Sumbangan terhadap laba untuk setiap lusin sepatu merek I1 = Rp. 30.000 sedangkan merek I2 = Rp. 50.000. Masalahnya adalah menentukan berapa lusin sebaiknya sepatu merek I1 dan merek I2 yang dibuat agar bisa memaksimumkan laba. Data di atas dapat disusun kedalam tabel sebagai berikut : Tabel 2.1 Contoh Soal Metode Grafik Merek



Kapasitas



I1



I2



1



2



0



8



2



0



3



15



3



6



5



30



3



5



Mesin



Maksimum



Sumbangan terhadap laba (Rp.10.000)



Untuk melakukan formulasi masalah di atas, maka pertama-tama tentukan simbolsimbol yang akan dipakai : X1 = jumlah sepatu merk I1 yang akan di buat setiap hari X2 = jumlah sepatu merk I2 yang akan di buat setiap hari Z = jumlah keuntungan seluruh sepatu merk I1 dan merk I2 yang akan diperoleh. Masalah tersebut dapat dipecahkan dengan metode grafik dalam LP dengan langkah-langkah dan persyaratan-persyaratan penggunaannya seperti di atas. Secara grafis akan digambarkan sumbu mendatar X1 untuk produk 1 dan sumbu vertikal X2 untuk produk 2, jumlah n = 2, yaitu produk 1 (sepatu merek I1) dan produk 2 (sepatu merek I2). Tujuan kita adalah akan memaksimumkan keuntungan yang akan diperoleh. keuntungan tiap lusin sepatu merek I1 = Rp. 30.000, sedangkan merek I2 = Rp. 50.000.



UNIVERSITAS SUMATERA UTARA



14



Oleh karena itu dapat kita formulasikan fungsi tujuannya (dalam puluhan ribu rupiah) sebagai berikut: Maksimumkan :



Z = 3X1 + 5X2



Dengan Kendala : 1)



≤8



2X1



2)



3X2



≤ 15



3)



6X1 + 5X2



≤ 30



Keterangan : Batasan 1 adalah batasan mesin 1 yang berarti 2 jam x jumlah sepatu merek I 1 yang dibuat (2X1) tidak dapat lebih dari 8 jam. Batasan 2 berarti 3 jam x jumlah sepatu merek I2 yang dibuat (3X2) tidak dapat lebih dari 15 jam. Batasan 3 berarti bahwa 6 jam x nilai X1 + 5 jam x nilai X2 tidak dapat lebih dari 30 jam. Selain itu perlu pula diperhatikan batasan-batasan “non-negatif”, yaitu X1 ≥ 0 dan X2 ≥ 0. Artinya kombinasi X1 dan X2 nanti hanya akan terletak pada kuadran pertama, yaitu kuadran yang memuat nilai-nilai positif bagi X1 dan X2.



Gambar 2.1 Grafik Batasan Pertama Bagian yang diarsir pada gambar diatas merupakan bagian yang memenuhi batasan-batasan : X1 ≥ 0 ,X2 ≥ 0 dan 2X1 ≤ 8. Dengan cara yang sama fungsi batasan yang kedua (3X2 ≤ 15) dan batasan ketiga (6X1 + 5X2 ≤ 30) dapat digambar untuk mencari titik perpotongan garis 6X1 + 5X2 ≤ 30 dengan sumber X1 dan X2. Secara lengkap dapat dilihat di bawah ini :



UNIVERSITAS SUMATERA UTARA



15



Gambar 2.2 Grafik Contoh Soal Bagian yang diarsir (disebut daerah feasible) pada gambar di atas menunjukkan bagian yang memenuhi “persyaratan” yang ditetapkan oleh ketiga fungsi-fungsi batasan , atau merupakan daerah kemungkinan-kemungkinan kombinasi (X1, X2) yang memenuhi batasan-batasan. Langkah terakhir pendekatan ini adalah mencari suatu titik (kombinasi X 1 dan X2) yang terletak pada daerah feasible yang dapat memaksimumkan nilai Z. Hal ini dapat dilakukan dengan 2 cara: dengan menggambarkan fungsi tujuan (disebut sebagai cara trial and error) dan dengan membandingkan nilai Z pada tiap-tiap alternatif. a.



Dengan menggambarkan fungsi tujuan. Misal digambarkan Z = 10 = 3X1 + 5X2 (garis P pada gambar di bawah).



Untuk mengetahui apakah ada nilai (X1, X2) di dalam daerah feasible yang akan mendapatkan Z=10.



Gambar 2.3 Grafik Fungsi Tujuan Ternyata dengan menggambarkan 3X1 + 5X2 = 10 tampak bahwa terdapat lebih dari satu titik pada garis tersebut yang terletak di dalam daerah feasible. Sehingga garis Z = 3X1 + 5X2 perlu digeser ke kanan agar lebih menjauhi titik origin atau agar Z lebih besar.



UNIVERSITAS SUMATERA UTARA



16



Umpama garis tersebut digeser menjadi 3X1 + 5X2 = 20 (garis q). Tampak bahwa masih terdapat lebih dari satu titik pada garis tersebut yang terletak di dalam daerah feasible. Artinya belum ditemukan satu titik (X 1 , X2) yang menghasilkan Z tertinggi. Garis Z = 3X 1 + 5X2 digeser lebih jauh ke kanan, sampai akhirnya ditemukan garis 3X1 + 5X2 = 27 1/2 , yang menyinggung daerah feasible di titik C (5/6 , 5). Berarti kombinasi optimal adalah : X 1 = 5/6 dan X2 = 5, dengan Z maksimal sebesar 27 1/2 .



b. Dengan membandingkan nilai Z pada tiap-tiap alternatif Apabila cara diatas terasa rumit, dapat dilakukan cara lain yang lebih sederhana yakni dengan membandingkan berbagai alternatif kombinasi X 1 dan X2. Atau dengan kata lain dengan membandingkan nilai Z yang diperoleh pada berbagai titik kombinasi X1 dan X2 di daerah feasible. Tentu saja nilai Z makin tinggi bila makin jauh dari titik origin (O). Sehingga sebaiknya yang membandingkan adalah titik-titik yang ada di sudut-sudut daerah feasible. Titik O : Pada titik ini nilai X1 = 0 , X2 = 0. Tentu saja Z = 0. Titik A : Pada titik ini, nilai X1 = 4, X2 = 0. Sehingga Z = 3(4) + 0 = 12 Titik B : Pada titik ini nilai X1 = 4. Substitusikan nilai ini pada persamaan batasan (3), maka 6(4) + 5X2 = 30. Jadi nilai X2 = (30-24)/5 = 6/5. Nilai Z = 3(4) + 5(6/5) = 18. Titik C : Pada titik ini nilai X2 = 5. Substitusikan nilai ini pada persamaan batasan (3), menjadi 6X1 + 5(5) = 30. Jadi nilai X1 = (30 – 25)/6 = 5/6. Nilai Z = 3(5/6) + 5(5) = 27 ½. Titik D : Pada titik ini nilai X2 = 5 dan nilai X1 = 0. Nilai Z = 3(0) + 5(5) = 25. Diantara kelima alternatif tersebut di atas yang mempunyai nilai Z terbesar adalah alternatif C, sebesar 27 1/2. Jadi titik inilah yang paling optimal. Keputusannya sepatu merek I1 dibuat 5/6 lusin dan sepatu merek I2 dibuat 5 lusin setiap hari, dengan laba setiap hari sebesar Rp. 275.000.



UNIVERSITAS SUMATERA UTARA



17



2.3



Metode simpleks



Metode ini dapat digunakan untuk jumlah variabel keputusannya 2 atau lebih dan jumlah kendalanya 2 atau lebih. Metode simpleks adalah suatu prosedur ulang yang bergerak dari satu jawab layak basis ke jawab berikutnya sedemikian rupa hingga harga fungsi tujuan terus menaik (dalam persoalan maksimasi) dan akan berkelanjutan sampai dicapai jawab optimal (kalau ada) yang memberi harga maksimum. Cara yang paling sederhana unrtuk menyelesaikan permasalahan program linier adalah dengan pendekatan grafikal. Namun cara tersebut hanya bisa diterapkan untuk program linier dengan dua variabel keputusan. Pada kenyataannya sebagian besar permasalahan program linier mempunyai lebih dari dua variabel keputusan. Hal ini tentu sulit untuk menerapkan pendekatan grafikal untuk memperoleh penyelesaian dari permasalahan tersebut. Oleh karena itu, pada tahun 1947 George Dantzig mengajukan suatu metode yang tepat untuk menyelesaikan permasalahan program linier yang disebut metode simpleks. Metode simpleks merupakan prosedur aljabar yang bersifat iteratif yang bergerak selangkah demi selangkah, dimulai dari titik ekstrim pada daerah feasible (ruang sousi) menuju titik ekstrim yang optimum. Berikut langkah-langkah dalam menyelesaikan permasalahan program linier dengan metode simpleks (Handayani, 2014): 1. Konversikan formulasi persoalan ke dalam bentuk standar. Agar persamaan garis batasan memenuhi persyaratan penyelesaian daerah kelayakan (feasible) maka semua pertidaksamaan diubah menjadi persamaan dengan cara menambahkan variabel slack, surplus dan variabel buatan (artifisial variabel) pada tiap batasan (constraint) serta member harga nol pada setiap koefisien tujuannya. Batasan dapat dimodifikasi sebagai berikut: a. Untuk batasan bernotasi (≤) diubah ke dalam bentuk persamaan dengan menambahkan variabel slack. b. Untuk batasan bernotasi (≥) atau (=) diselesaikan dengan menambahkan variabel surplus dan variabel buatan. Dengan penambahan variabel buatan ini akan merusak sistem batasan, hal ini dapat diatasi dengan membuat suatu bilangan penalty M (M bilangan positif yang sangan besar) sebagai harga



UNIVERSITAS SUMATERA UTARA



18



dari variabel buatan tersebut dalam fungsi tujuan. Untuk kasus maksimasi maka dibuat –M sebagai harga dari variabel buatan dan untuk kasus minimasi dibuat +M sebagai harga dari variabel buatan. Cara pendekatan ini dikenal dengan metode M besar (Big M method). 2. Susun persamaan-persamaan ke dalam tabel simpleks Tabel 2.2 Bentuk Tabel Simpleks



3. Pilih kolom kunci, yaitu kolom yang memiliki nilai (𝑍 untuk kasus maksimasi atau yang memiliki nilai (𝑍 -



) yang paling positif ) yang paling negatif



untuk kasus minimasi. 4. Pilih baris kunci yang memiliki nilai indeks terkecil. Nilai indeks adalah perbandingan nilai kanan dengan kolom kunci. 5. Tentukan nilai elemen cell, yaitu nilai perpotongan antara kolom kunci dan baris kunci. 6. Lakukan iterasi dengan menentukan baris kunci baru, baris Z baru, dan baris variabel-variabel slack baru. a.



Baris kunci baru ditentukan dengan membagi baris kunci lama dengan elemen cell.



b.



Baris Z baru dan baris-baris lainnya ditentukan dengan cara: Baris lama – (nilai kolom kunci baris yang sesuai × baris kunci baru)



c. Letakkan nilai-nilai baris yang baru diperoleh ke dalam tabel. 7. Lakukan uji optimalisasi. Jika semua koefisien pada baris (𝑍 -



) sudah tidak



ada lagi yang bernilai positif (untuk kasus maksimasi) atau sudah tidak ada lagi yang bernilai negatif (untuk kasus minimasi) berarti sudah optimal. Jika kriteria belum terpenuhi, diulangi dari langkah 3.



UNIVERSITAS SUMATERA UTARA



19



Metode simpleks didasarkan pada langkah seperti berikut : a.



Dimulai pada suatu titik pojok yang layak, biasanya titik asal ( yang disebut sebagai solusi awal).



b.



Bergerak dari satu titik pojok layak ke titik pojok layak lain yang berdekatan. Pergerakan ini akan menghasilkan nilai fungsi tujuan yang lebih baik (meningkat untuk masalah maksimasi dan menurun untuk masalah minimasi). Jika solusi yang lebih baik telah diperoleh, prosedur simpleks dengan sendirinya akan menghilangkan semua solusi-solusi lain yang kurang baik.



c.



Proses ini diulang-ulang sampai suatu solusi yang lebih baik tak dapat ditemukan. Proses simpleks kemudian berhenti dan solusi optimum diperoleh. Diberikan suatu permasalahan yang akan diselesaikan dengan metode



simpleks sebagai berikut: Contoh 2.2 Maksimumkan



Z = 3X1 + 5X2



Batasan (constraint) (1) (2) (3)



8



2X1



 15



3X2



 30



6X1 + 5X2



Langkah 1 : Mengubah fungsi tujuan dan batasan-batasan Mengubah fungsi tujuan dan batasan-batasan Fungsi tujuan Z = 3X1 + 5X2 diubah menjadi Z - 3X1 - 5X2 = 0. Fungsi batasan (diubah menjadi kesamaan & di + slack variabel) (1) 2X1



 8 menjadi 2X1



(2) 3X2



 15 menjadi



+ X3 3X2



(3) 6X1 + 5X2  30 menjadi 6X1 + 5X2



= 8 + X4



= 15 + X5 = 30



Langkah 2: Menyusun persamaan-persamaan di dalam tabel NK adalah nilai kanan persamaan, yaitu nilai di belakang tanda sama dengan ( = ). Untuk batasan 1 sebesar 8, batasan 2 sebesar 15, dan batasan 3 sebesar 30.



UNIVERSITAS SUMATERA UTARA



20



Variabel dasar adalah variabel yang nilainya sama dengan sisi kanan dari persamaan. Pada persamaan 2X1 + X3 = 8, kalau belum ada kegiatan apa-apa, berarti nilai X1 = 0, dan semua kapasitas masih menganggur, maka pengangguran ada 8 satuan, atau nilai X3 = 8. Pada tabel tersebut nilai variabel dasar (X 3, X4, X5) pada fungsi tujuan pada tabel permulaan ini harus 0, dan nilainya pada batasan-batasan bertanda positif. Tabel 2.3 Tabel simpleks yang pertama Variabel Dasar



Z



X1



X2



X3



X4



X5



NK



Z



1



-3



-5



0



0



0



0



X3



0



2



0



1



0



0



8



X4



0



0



3



0



1



0



15



X5



0



6



5



0



0



1



30



Langkah 3: Memilih kolom kunci Kolom kunci adalah kolom yang merupakan dasar untuk mengubah tabel simplek. Pilihlah kolom yang mempunyai nilai pada garis fungsi tujuan yang bernilai negatif dengan angka terbesar. Dalam hal ini kolom X2 dengan nilai pada baris persamaan tujuan –5. Berilah tanda segi empat pada kolom X2, seperti tabel berikut : Tabel 2.4 Tabel simpleks: pemilihan kolom kunci pada tabel pertama Variabel Dasar



Z



X1



X2



X3



X4



X5



NK



Z



1



-3



-5



0



0



0



0



X3



0



2



0



1



0



0



8



X4



0



0



3



0



1



0



15



X5



0



6



5



0



0



1



30



Keterangan (Indeks)



Jika suatu tabel sudah tidak memiliki nilai negatif pada baris fungsi tujuan, berarti tabel itu tidak bisa dioptimalkan lagi (sudah optimal).



UNIVERSITAS SUMATERA UTARA



21



Langkah 4: Memilih baris kunci Baris kunci adalah baris yang merupakan dasar untuk mengubah tabel simplek, dengan cara mencari indeks tiap-tiap baris dengan membagi nilai-nilai pada kolom NK dengan nilai yang sebaris pada kolom kunci. Indeks = (Nilai Kolom NK) / (Nilai kolom kunci) Untuk baris batasan 1 besarnya indeks = 8/0 = , baris batasan 2 = 15/3 = 5, dan baris batasan 3 = 30/5 = 6. Pilih baris yang mempunyai indeks positif dengan angka terkecil. Dalam hal ini batasan ke-2 yang terpilih sebagai baris kunci. Beri tanda segi empat pada baris kunci. Nilai yang masuk dalam kolom kunci dan juga masuk dalam baris kunci disebut angka kunci.



Langkah 5: Mengubah nilai-nilai baris kunci Nilai baris kunci diubah dengan cara membaginya dengan angka kunci, seperti tabel 3. bagian bawah (0/3 = 0; 3/3 = 1; 0/3 = 0; 1/3 = 1/3; 0/3 = 0; 15/3 = 5). Gantilah variabel dasar pada baris itu dengan variabel yang terdapat di bagian atas kolom kunci ( ). Tabel 2.5 Simpleks: Cara mengubah nilai baris kunci Variabel Dasar



Z



X1



X2



X3



X4



X5



NK



Keterangan (Indeks)



Z



1



-3



-5



0



0



0



0



X3



0



2



0



1



0



0



8



8/0 = ∞



X4



0



0



3



0



1



0



15



15/3 = 5



X5



0



6



5



0



0



1



30



30/5 = 6



Z X3 X2



0



0



1



0



⁄



0



5



X5



UNIVERSITAS SUMATERA UTARA



22



Langkah 6: Mengubah nilai-nilai selain pada baris kunci Rumus : Baris baru = baris lama – (koefisien pada kolom kunci) x nilai baru baris kunci Baris pertama (Z)



Nilai baru



[-3



-5



0



0



0,



0]



(-5)



[0



1



0



1/3



0,



5]



=



[-3



0



0



5/3



0,



25]



[2



0



1



0



0,



8]



(0)



[0



1



0



1/3



0,



5]



=



[2



0



1



0



0,



8]



[6



5



0



0



1,



30 ]



(5)



[0



1



0



1/3



0,



5 ]



=



[6



0



0



-5/3



1,



5 ]



(-)



Baris ke-2 (batasan 1)



Nilai baru



(-)



Baris ke-4 (batasan 3)



Nilai baru



(-)



Langkah 7: Melanjutkan perbaikan Ulangilah langkah-langkah perbaikan mulai langkah 3 sampai langkah ke-6 untuk memperbaiki tabel-tabel yang telah diubah/diperbaiki nilainya. Perubahan baru berhenti setelah pada baris pertama (fungsi tujuan) tidak ada yang bernilai negatif.



UNIVERSITAS SUMATERA UTARA



23



Tabel 2.6 Tabel Simpleks : Melanjutkan Perbaikan Variabel Dasar



Z



X1



X2



X3



X4



X5



NK



Z



1



-3



0



0



5/3



0



25



X3



0



2



0



1



0



0



8



X4



0



0



1



0



1/3



0



5



X5



0



6



0



0



-5/3



1



5



Z



1



X3



0



X2



0



X1



0



6/6



0



0



-5/18



1/6



5/6



Keterangan (Indeks)



= 8/2 = 4



= 5/6 (minimum)



Baris ke-1



Nilai baru



[-3



0



0



5/3



0,



25 ]



(-3)



[1



0



0



-5/18



1/6,



5/6]



=



[0



0



0



5/6



½,



27 /2]



[2



0



1



0



0,



8]



(2)



[1



0



0



-5/18



1/6,



5/6]



=



0



0



1



5/9



-1/3,



6 /3]



(-)



1



Baris ke-2 (batasan 1)



Nilai baru



(-)



1



Baris ke-3 tidak berubah karena nilai pada kolom kunci = 0



Nilai baru



[0



1



0



1/3



0,



5]



(0)



[1



0



0



-5/18



1/6,



5/6]



=



0



1



0



1/3



0,



5]



(-)



UNIVERSITAS SUMATERA UTARA



24



Tabel 2.7 Hasil Akhir Perbaikan Variabel Dasar



Z



X1



X2



X3



X4



X5



NK



Z



1



0



0



0



5/6



½



27 /2



X3



0



0



0



1



5/9



-1/3



6 /3



X2



0



0



1



0



1/3



0



5



X1



0



1



0



0



-5/18



1/6



5/6



1



1



Baris pertama (Z) tidak ada lagi yang bernilai negatif. Sehingga tabel tidak dapat dioptimalkan lagi dan tabel tersebut merupakan hasil optimal. Dari tabel final didapat : X1 = 5/6, X2 = 5 dengan Zmaksimum = 271/2 2.4



Program Integer



Menurut Sitorus (1997), program linier bilangan bulat atau disebut juga sebagai program integer merupakan suatu model program linier yang khusus digunakan untuk menyesuaikan suatu masalah program linier dimana nilai variabel-variabel keputusan dalam menyelesaikan optimal harus merupakan bilangan integer (bulat). Karakteristik model matematika program linier integer adalah sama dengan model linier biasa, kecuali dalam program linier integer harus ada memuat suatu persyaratan bahwa variabel keputusan tertentu harus bilangan integer.



Apabila



dalam Program Linier integer mensyaratkan bahwa : 1. Semua keputusan harus merupakan bilangan integer disebut All integer linear programming (AILP). 2. Hanya sebagian keputusan yang merupakan bilangan integer disebut Mixed integer linear programing (MILP). 3. Jika variabel keputusan harus bernilai 0 dan 1 disebut Zero one integer linear programming (ZOILP).



UNIVERSITAS SUMATERA UTARA



25



Ada banyak kasus dalam masalah program integer yang membatasi variabel model bernilai nol atau satu. Dalam kasus demikian, pengambil keputusan hanya memiliki dua pilihan yaitu menerima atau menolak suatu usulan kegiatan. Penerimaan atau penolakan yang sifatnya parsial (sebagian) tidak diperbolehkan. Jika variabel keputusan bernilai satu, kegiatan diterima. Dan jika variabel berilai nol, kegiatan ditolak. (Mulyono, 2004). Bentuk umum program integer dapat dirumuskan sebagai berikut : Maksimumkan atau minimumkan : 𝑍



∑



Dengan kendala : ∑



(



Untuk



Keterangan: 𝑍



= =



= = = = =



Fungsi tujuan yang harus dicari nilai optimalnya (maksimal atau minimal) tingkat kegiatan ke- j Kenaikan nilai Z terjadi apabila ada pertambahan tingkat kegiatan dengan satu satuan unit atau sumbangan setiap satuan keluaran kegiatan Z terhadap j Banyaknya sumber i yang diperlukan untuk menghasilkan setiap unit keluaran kegiatan j Kapasitas sumber i yang tersedia untuk dialokasikan ke setiap unit kegiatan macam kegiatan yang menggunakan sumber atau fasilitas yang tersedia macam batasan sumber atau fasilitas yang tersedia



2.5 Metode Branch and Bound (Pencabangan dan Pembatasan) Metode Branch and Bound pertama kali diperkenalkan oleh Land dan Doig (1960). Ide dasarnya adalah untuk membagi daerah solusi fisibel menjadi daerah solusi fisibel yang lebih kecil. Ini merupakan prosedur sederhana yang menetapkan batasan yang lebih tinggi dan rendah menjadi solusi saat menyelesaikan sub masalah secara



UNIVERSITAS SUMATERA UTARA



26



sistematis. Kemudian metode ini dimodifikasi oleh Dakin (1965) dan dengan sukses menerapkannya di dalam kitab undang-undang hukum dagang banyak orang dalam memecahkan persoalan program integer. Dengan menggunakan metode Branch and Bound, Widi Hartono (2014) dapat menganalisis permasalahan optimasi sisa material besi pada plat lantai. Dimana perbandingan jumlah besi tulangan yang berdiameter 12 cm dan 10 cm terjadi penghematan sebesar 1,5449% dan 4,0399%. Metode Branch and Bound merupakan salah satu metode untuk menghasilkan penyelesaian optimal program linear yang menghasilkan variabel – variabel keputusan bilangan bulat. Sesuai dengan namanya, metode ini membatasi penyelesaian optimum yang akan menghasilkan bilangan pecahan dengan cara membuat cabang atas atau bawah bagi masing-masing variabel keputusan yang bernilai pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang baru (Hartono, 2014). Metode ini sering digunakan untuk menyelesaikan suatu masalah program integer karena hasil yang diperoleh dalam penyelesaian optimal lebih teliti dan lebih baik dari kedua metode lainnya. Kelemahan pokok metode ini adalah prosedur untuk mencapai hasil optimal sangat panjang. Prinsip dasar metode ini adalah memecah daerah fisibel layak suatu masalah program linier dengan membuat submasalah. Ada dua konsep dasar dalam metode branch and bound: a. Branching adalah proses membagi-bagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi. b. Bounding adalah suatu proses untuk mencari/menghitung batas atas dan batas bawah untuk solusi optimal pada subproblem yang mengarah ke solusi.



2.5.1. Langkah-Langkah Metode Branch and Bound 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.



UNIVERSITAS SUMATERA UTARA



27



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).



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.



2.5.2 Syarat Pencabangan (Fathoming) Berhenti Pencabangan atau pencarian solusi pada suatu sub masalah dihentikan jika: 1. Infeasible atau tidak mempunyai daerah layak. 2. Semua variabel keputusan yang harus bernilai integer sudah bernilai integer 3. Pada masalah memaksimalkan, penghentian pencabangan pada suatu sub masalah dilakukan jika batas atas dari sub masalah tersebut tidak lebih besar atau sama dengan batas bawah.



UNIVERSITAS SUMATERA UTARA



28



4. Pada masalah meminimumkan penghentian pencabangan pada suatu sub masalah dilakukan jika batas bawah tidak lebih lebih kecil atau sama dengan batas atas.



2.5.3. Syarat Kondisi Optimal Kondisi optimal pada Branch and bound antara lain : 1. Jika tidak ada lagi sub masalah yang perlu dicabangkan lagi maka solusi optimal sudah diperoleh. 2. Pada masalah memaksimalkan solusi optimal merupakan solusi submasalah yang saat ini menjadi batas bawah (lower bound) 3. Pada masalah meminimumkan solusi optimal merupakan solusi submasalah yang saat ini menjadi batas atas (upper bound).



UNIVERSITAS SUMATERA UTARA



29



Langkah-langkah pengerjaan metode Branch and Bound adalah sebagai berikut:



Masalah Linear Programming diselesaikan dengan metode simpleks tanpa pembatasan bilangan bulat



Teliti solusi optimumnya



Salah satu variabel basis yang diharapkan tidak bulat



Variabel basis yang diharapkan bilangan bulat



Solusi bilangan bulat tercapai



Nilai solusi pecah yang layak dicabangkan (branch) ke dalam sub-sub masalah



Pencabangan dilakukan dengan kendala baru yang saling berhubungan



Cari solusi optimumnya dengan simpleks menggunakan pembatas bilangan bulat



Gambar 2.4 Langkah-Langkah Metode Branch and Bound



UNIVERSITAS SUMATERA UTARA



30



.



Solusi awal



Gambar 2.5 Diagram Metode Branch and Bound



Walaupun metode Branch and Bound memiliki kekurangan, dapat dikatakan bahwa sampai sekarang, ini adalah metode yang paling efektif dalam memecahkan program-program integer dengan ukuran praktis. Pada kenyataannya, semua program komersial yang tersedia didasari oleh metode Branch and Bound. Tetapi, ini tidak berarti bahwa setiap program integer dapat dipecahkan dengan metode Branch and Bound. Ini hanya berarti bahwa ketika pilihannya adalah metode pemotongan (cutting plane) dan metode Branch and Bound, metode terakhir ini umumnya terbukti lebih baik (Taha, 1996). 2.6 Software QM Software POM/QM for Windows adalah sebuah software yang dirancang untuk melakukan perhitungan yang diperlukan pihak manajemen untuk mengambil keputusan di bidang produksi dan pemasaran. Software ini dirancang hanya untuk membantu perhitungannya saja jadi kita harus dapat menginterpretasikan masalah dan teori programasi linier. Software ini dirancang oleh Howard J. Weiss tahun 1996 untuk membantu menejer produksi khususnya dalam menyusun prakiraan dan anggaran untuk produksi bahan baku menjadi produk jadi atau setengah jadi dalam proses pabrikasi.



UNIVERSITAS SUMATERA UTARA



31



Software QM berguna untuk membantu pengambilan keputusan seperti misalnya menentukan kombinasi produksi yang sesuai agar memperoleh keuntungan sebesar-besarnya, menentukan order pembelian barang agar biaya perawatan menjadi seminimal mungkin, menentukan penugasan karyawan terhadap suatu pekerjaan agar dicapai hasil yang maksimal, dan lain sebagainya. Program ini menyediakan beberapa modul berbeda, yaitu: Aggregate Planning, Assembly Line Balancing, Assignment, Break Even/Cost-Volume Analysis, Capital Investment, Decission Analysis, Forecasting, Game Theory, Goal Programming, Integer And Mixed Integer Programming, Inventory, Job Shop Sceduling, Layout, Learning Curve, Linear Programming, Location, Lot Sizing, Markov Analysis, Material Requirements Planning, Networks, Productivity, Project Management (PERT/CPM), Quality Control, Reliability, Simulation, Statistics, Transportation, Waiting Lines, Work Measurement. Langkah – langkah pengoperasiannya software QM adalah sebagai berikut: 1. Buka aplikasi software QM. 2. Buka module lalu pilih module linier programming. 3. Selanjutnya, klik file lalu pilih new maka akan tampil kotak create data set for linier programming. 4. Siapkan formula masalahnya. Tentukan jumlah constraints (kendala). Tentukan jumlah variabel. 5. Masukkan masalah tersebut ke dalam tabel. -



Fungsi tujuan (maximize) diisikan dengan data pada fungsi tujuan kasus 
linier programming tersebut.



-



Constraint dan Variabel diisikan dengan data pada fungsi kendala kasus 
linier programming tersebut.



-



Untuk tanda