Optimalisasi Keuntungan Penjualan Roti Dengan Metode Branch and Bound (Studi Kasus: UD. Akbar Jaya) [PDF]

Citation preview

OPTIMALISASI KEUNTUNGAN PENJUALAN ROTI DENGAN METODE BRANCH AND BOUND (Studi Kasus: UD. Akbar Jaya)



SKRIPSI



DESI VITA SARI SINAGA 140803012



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



UNIVERSITAS SUMATERA UTARA



OPTIMALISASI KEUNTUNGAN PENJUALAN ROTI DENGAN METODE BRANCH AND BOUND (Studi Kasus: UD. Akbar Jaya)



SKRIPSI



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



DESI VITA SARI SINAGA 140803012



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



UNIVERSITAS SUMATERA UTARA



UNIVERSITAS SUMATERA UTARA



PERNYATAAN ORISINALITAS



OPTIMALISASI KEUNTUNGAN PENJUALAN ROTI DENGAN METODE BRANCH AND BOUND (Studi Kasus: UD. Akbar Jaya)



SKRIPSI



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



Medan,



April 2018



Desi Vita Sari Sinaga 140803012



UNIVERSITAS SUMATERA UTARA



i



PENGESAHAN SKRIPSI



Judul



:



Kategori Nama Nomor Induk Mahasiswa Program Studi Fakultas



: : : : :



Optimalisasi Keuntungan Penjualan Roti dengan Metode Branch and Bound ( Studi Kasus: UD. Akbar Jaya) Skripsi Desi Vita Sari Sinaga 140803012 Sarjana Matematika MIPA - 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



Drs. Agus Salim Harahap, M.Si NIP. 19540828 198103 1 004



i UNIVERSITAS SUMATERA UTARA



ii



OPTIMALISASI KEUNTUNGAN PENJUALAN ROTI DENGAN METODE BRANCH AND BOUND (Studi Kasus: UD. Akbar Jaya)



ABSTRAK



UD. Akbar Jaya merupakan suatu perusahaan yang bergerak dalam bidang pembuatan roti di Medan. Perusahaan ini memproduksi roti dengan berbaga jenis rasa. Dalam penelitian ini diambil 4 jenis rasa, yakni rasa coklat, rasa kelapa, rasa blueberry dan rasa kacang hitam. Masalah mengoptimalkan jumlah produksi akan dimodelkan ke dalam model matematika berupa program linear, kemudian dilanjutkan dengan program integer, dimana variabel keputusan harus berupa bilangan integer. Masalah program integer tersebut akan diselesaikan dengan metode branch and boundyang terlebih dahulu menghitung nilai variabel keputusan dengan menggunakan metode simpleks. Metode branch and bound merupakan metode yang digunakan untuk menyelesaikan masalah program linear yang menghasilkan berupa penyelesaian dalam bentuk bilangan bulat (integer). Dalam penelitian ini penulis menggunakan bantuan Softwere QM untuk menyeleaikan masalah program linear. Analisis metode branch and bounddiperoleh selesih nilai keuntungan penjualan sebesar 8.27% atau senilai Rp. 2.630.775,00dari perkiraan keuntungan perusahaan. Jumlah roti yang diproduksi dari bahan-bahan yang tersedia adalah 133.333 roti dimana Roti Blueberry diproduksi 36.666 roti,Roti Cokelat diproduksi 19.496 roti, Roti Kelapa diproduksi 44.444 roti dan Roti Kacang Hitam diproduksi 32.727 roti dengan keuntungan sebesar Rp. 34.431.500,00.



Kata Kunci: Program Linier, Metode Branch and Bound



ii UNIVERSITAS SUMATERA UTARA



iii



OPTIMIZATION OF SALES PROFITS BREAD WITH BRANCH AND BOUND METHOD (Case Study: UD Akbar Jaya)



ABSTRACT UD. Akbar Jaya is a company engaged in the field of bread making in Medan. The company produces bread with a variety of flavors. In this study were taken 4 types of flavors, namely chocolate flavor, coconut flavor, blueberry flavor and black bean flavor. The problem of optimizing production quantities will be modeled into a mathematical model of linear programming, followed by an integer program, where the decision variable must be an integer number. The problem of the integer program will be solved by the branch and bound method which first calculates the value of the decision variable by using the simplex method. The branch and bound method is a method used to solve linear programming problems that result in the form of completion in the form of integers. In this study, the author uses the help of Software QM to solve linear program problems. The analysis of branch and bound method is obtained as the value of sales profit of 8.27% or Rp. 2,630,775.00 of the estimated profits of the company. The amount of bread produced from the available ingredients is 133,333 loaves of bread where Blueberry bread is produced 36,666 loaves, Chocolate Bread is produced 19,496 loaves, Coconut bread is produced 44,444 loaves of bread and Black Peanuts is produced 32,727 loaves of bread with a profit of Rp. 34.431.500,00.



Keyword: Linear Programming, Branch and Bound Method



iii UNIVERSITAS SUMATERA UTARA



iv



PENGHARGAAN



Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa, atas limpahan karunia-Nya penulis dapat



menyelesaikan penyusunan skripsi ini dengan



judul“Optimalisasi Keuntungan Penjualan Roti dengan Metode Branch and Bound(Studi Kasus: UD. Akbar Jaya)”dengan baik,guna melengkapi syarat memperoleh gelar S1Matematika pada Fakultas Matematika dan Ilmu Pengetahuan Alam diUniversitas Sumatera Utara.



Dalam kesempatan ini, penulis ingin mengucapkan terima kasih yangsebesarbesarnya kepada semua pihak yang telah membantu dan membimbingpenulis dalam penyusunan skripsi ini, ucapan terima kasih penulis sampaikankepada:



1. Bapak Drs. Agus Salim Harap, M.Si selaku Dosen Pembimbing atassegala waktu dan arahan yang diberikan selama penyusunan skripsi ini.



2. Bapak Dr. Parapat Gultom, MSIE dan Bapak Drs. Rosman Siregar, M.Siselaku DosenPembanding atas segala saran dan masukan yang diberikan dalam penyelesaian skripsi ini.



3. Bapak Dr. Suyanto, M.Kom dan Bapak Drs. Rosman Siregar, M.Siselaku 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 pada Departemen Matematika FMIPA-USU dan pegawai di FMIPA-USU.



6. UD. Akbar Jaya yang bersedia membantu memberikan data riset kepada penulis sehingga penulis dapat menyelesaikan skripsi ini.



iv UNIVERSITAS SUMATERA UTARA



v



7. AyahandaF. Sinaga, Ibunda T. Gultom, S.Pd, Rosida Sinaga (kakak), Desimawati Sinaga (adik), Ridwanto H. Sinaga (adik), serta keluarga yang memberikan doa, pengertian, perhatian, kasih sayang, semangat dan dukungan yang luar biasa dan tiada hentinya bagi penulis.



8. Sahabat-sahabat penulis antara lain: anggota KAM (Bela, Giring, Pur), anggota KK (Efintya, Nadia, Santa, Winda, Yesi), anggota CCC(Inggrid, Irma, Juli), dan anggota Kediri Squad (Dian, Eby, Ani dan Mila)yang selalu mendukung penulis dalam penulisan skripsi ini, selalu ada di setiap suka dan duka serta selalu memotivasi penulis. 9. Apriandy Hasian Pasaribu yang selalu mendukung penulis dalam pengerjaan skripsi, memberikan semangat dan memberikan motivasi bagi penulis.



10. Seluruh teman jurusan Matematika khususnya stambuk 2014, adik-adik junior stambuk 2015, stambuk 2016, stambuk 2017 serta Abang danKakak alumni.



Penulis menyadari bahwa masih terdapat banyak kekurangan dalam penulisanskripsi ini. Maka dari itu, diperlukan kritik dan saran dari pembaca untukpenyempurnaan skripsi ini.



Medan, April 2018 Penulis



Desi Vita Sari Sinaga



v UNIVERSITAS SUMATERA UTARA



vi



DAFTAR ISI



Halaman i



PERSETUJUAN PERNYATAAN PENGHARGAAN ABSTRAK ABSTRACT DAFTAR ISI DAFTAR TABEL DAFTAR GAMBAR



ii iii v vi vii viii ix



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



1 2



3 3 5 5 5 5



BAB 2 LANDASAN TEORI 2.1 Program Linear 2.1.1 Model Program Linear 2.1.2 Karakteristik Program Linier 2.1.3 Terminologi Umum dan Asumsi-Asumsi Dasar Program Linier 2.2 Program Integer (Program Bilangan Bulat) 2.3 Metode Branch and Bound (Pencabangan dan Pembatasan) 2.3.1. Langkah-langkah metode Branch and Bound 2.3.2. Syarat Pencabangan (Fathoming) Berhenti 2.3.3. Syarat Kondisi Optimal 2.4 Software QM



BAB 3 HASIL DAN PEMBAHASAN 3.1 Pengumpulan Data 3.2 Pengolahan Data 3.3 Analisis Metode Branch and Bound 3.4 Mekanisme Perhitungan Solusi Secara Manual 3.5 Perbandingan Keuntungan 3.6 Pohon Penyelesaian Metode Branch and Bound



7 9 10 11 12 13 14 15 15 17



19 21 23 36 45 46



BAB 4 KESIMPULAN DAN SARAN vi UNIVERSITAS SUMATERA UTARA



vii



4.1 Kesimpulan 4.2 Saran



48 48



DAFTAR PUSTAKA LAMPIRAN



49



vii UNIVERSITAS SUMATERA UTARA



viii



DAFTAR TABEL



Nomor



Judul



3.1



Data Komposisi Bahan Baku untuk 1 Buah Roti dan Persediaan Bahan Baku4 Jenis Roti DataHarga Jual, Biaya Produksi dan Keuntungan Penjualan 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 Solusi dari Hasil Iterasi dengan Software QM Hasil Akhir Metode Branch and Bound Perbandingan Keuntungan Perusahaan dan Keuntungan dengan Menggunakan Metode Branch and Bound



3.2 3.3 3.4 3.5 3.6 3.7 3.8 3.9 3.10



Halaman 19 19 21 21 22 22 23 23 36 45



viii UNIVERSITAS SUMATERA UTARA



ix



DAFTAR GAMBAR



Nomor Judul 2.1 3.1



Halaman



Kerangka Kerja Metode Branch and Bound Diagram Penyelesaian dengan Metode Branch and Bound



15 46



ix UNIVERSITAS SUMATERA UTARA



1



BAB I PENDAHULUAN



1.1 Latar Belakang Penerapan ilmu mengenai operasi riset dalam kehidupan sehari-hari sangat banyak digunakan oleh manusia, misalnya pada bidang ekonomi. Faktor di bidang produksi semakin canggih, kebutuhan manusia yang semakin bertambah karena pertumbuhan penduduk yang semakin meningkat menyebabkan jumlah produksi barang-barang semakin meningkat pula sesuai dengan kebutuhan. Dalam suatu perusahaan industri besar keinginannya menjadi yang terdepan dan mencapai tujuan untuk mendapatkan hasil yang optimal dengan batasan-batasan yang ada berupa bahan baku, peralatan, mesin, waktu, biaya dan tenaga kerja. Dalam hal ini, Usaha Dagang (UD) Akbar Jaya adalah salah satu perusahaan produksi yang bergerak dalam bidang roti di Medan yang ingin mencapai tujuan untuk mendapatkan keuntungan maksimum. Usaha dagang adalah kegiatan membeli dan menjual kembali barang atau jasa dengan tujuan mencari keuntungan termasuk menjadi perantara dari kegiatan tersebut. Usaha dagang ingin memperoleh laba yang besar dengan biaya produksi yang kecil, dengan begitu sebuah perusahaan akan terus beroperasi dan berkembang. Dalam dunia nyata, banyak perusahaan yang tidak mampu mempertahanan laba bahkan meningkatkan laba (mengalami kerugian). Hal ini dapat disebabkan beberapa faktor, antara lain kurangnya pengelolahan dalam hal produksi (persediaan produk berlebihan atau produk yang diproduksi tidak memenuhi permintaan pasar). Pemanfaatan energi dan pemakaian bahan baku yang optimal sangat diperlukan dalam memaksimalkan jumlah produksi yang akan menghasilkan keuntungan yang lebih besar. Modal yang sedikit mampu menghasilkan keuntungan yang banyak, sehingga muncul masalah optimasi. Masalah optimasi meliputi meminimumkan biaya atau memaksimalkan keuntungan dengan kapasitas sumber daya yang ada agar mampu mendapatkan hasil yang optimal. Optimalisasi adalah proses mencari solusi optimal



UNIVERSITAS SUMATERA UTARA



2



dari



sebuah



permasalahan



dengan



menggunakan



model



matematis



dan



pemecahannya dapat menggunakan program linear. 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 grafik dan metode simpleks. Program linier adalah suatu teknik perencanaan yang bersifat analitis menggunakan model matematis dengan tujuan menemukan beberapa kombinasi alternatif pemecahan optimum terhadap suatu persoalan. Program bilangan bulat atau program integer adalah sebuah program linear dengan persyaratan tambahan bahwa semua nilai variabelnya merupakan bilanganbilangan bulat. Metode yang digunakan untuk menyelesaikan masalah yang ada adalah metode Cabang dan Batas (Branch and Bound). Metode branch and bound adalah salah satu metode untuk menghasilkan penyelesaian optimal program linier 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 (Widi Hartono, 2014).



1.2 Rumusan Masalah Berdasarkan latar belakang masalah diatas, permasalahan yang dibahas untuk menghasilkan keuntungan produksi yang besar adalah dengan mengoptimalkan jumlah bahan baku produksi serta meminimumkan biaya produksi.



UNIVERSITAS SUMATERA UTARA



3



1.3 Batasan Masalah Adapun yang menjadi batasan masalah dalam penulisan skripsi ini yaitu : 1. Permasalahan yang dibahas adalah 4 jenis roti. 2. Permasalahan yang dibahas adalah proses sekali produksi bahan baku. (Proses sekali produksi adalah proses penggunaan total bahan baku dalam satu periode). 3. Dalam menyelesaikan produksi, biaya bahan baku dianggap konstan. (Biaya bahan baku dianggap konstan adalah biaya pembelian bahan baku selama proses penelitian tidak mengalami perubahan). 4. Pengadaan bahan baku tetap tersedia.



1.4 Tinjauan Pustaka



Sebagai sumber pendukung teori dalam penulisan ini, penulis mengambil beberapa pustaka dan penelitian terdahulu yang memberikan kontribusi dalam penyelesaian skripsi ini. 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. Siagian P (1987) mengemukakan bahwa pokok pikiran yang paling utama dalam menggunakan program linier adalah merumuskan masalah dengan jelas menggunakan sejumlah informasi yang tersedia. Kemudian menterjemahkan 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 dapat dinyatakan dalam bentuk fungsi linier yang disebut sebagi fungsi tujuan (objective function).



UNIVERSITAS SUMATERA UTARA



4



2. Harus ada alernatif pemecahan. Pemecahan yang membuat fungsi tujuan optimum (laba maksimum, biaya 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). Pembatasan-pembatasan harus dinyatakan dalam ketidaksamaan yang linier (linear inequality). 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). Dalam setiap submasalah perlu mendapatkan batas (bound) mengenai seberapa jauh solusi layak terbaik dapat dicapai. Untuk submasalah baru, dapatkan upper bound dan lower bound kemudian bulatkan ke bawah nilai z nya untuk menghasilkan solusi yang optimal. Menghilangkan solusi kontinu yang tidak memenuhi persyaratan bilangan bulat dilakukan dengan membatasi (bounding) nilai solusi pecah yang layak, seberapa baik solusi terbaik dalam himpunan bagian dan kemudian menghilangkan himpunan bagian apabila batas mengindikasikan bahwa himpunan bagian tersebut tidak mungkin berisi solusi optimal untuk kasus awal. Dalam mengoptimalkan keuntungan perusahaan dapat diketahui dengan rumus: KEUNTUNGAN = HARGA JUAL – HARGA PRODUKSI Dengan menggunakan model di atas diasumsikan jumlah produksi=jumlah yang di jual, maka dapat diketahui keuntungan maksimal yang dicapai perusahaan.



UNIVERSITAS SUMATERA UTARA



5



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



metode



Branch and Bound merupakan salah satu alternatif yang dapat digunakan untuk mengoptimalkan keuntungan penjualan roti di UD. Akbar Jaya.



1.6 Manfaat Penelitian Manfaat dari penelitian ini adalah sebagai berikut: 1. Bagi Usaha Dagang Sebagai bahan pertimbangan dan masukan dalam mengoptimalkan keuntungan produksi dan dapat digunakan sebagai alternatif untuk menghasikan keuntungan yang besar. 2. Bagi Peneliti Peneliti mendapatkan pengalaman yang berharga melalui keterlibatannya secara langsung pada dunia kerja serta mengaplikasikan ilmu pengetahuan yang diperoleh



tentang



metode



Branch



and



Bound



dalam



menganalisa



pengoptimalisasian keuntungan produksi. 3. Bagi Universitas Menambah kepustakaan universitas yang sudah ada, khususnya mengenai pengoptimalisasian keuntungan produksi yang tepat.



1.7 Lokasi Penelitian Penelitian dilakukan di UD. Akbar Jaya, yang beralamat di Jalan Sempurna No.59 Sudirejo I, Teladan, 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 yang berhubungan dengan metode Branch and Bound.



UNIVERSITAS SUMATERA UTARA



6



2. Pengumpulan Data Data yang diperoleh ialah jenis bahan baku (tepung, mentega, gula pasir, garam, pengembang, bluberry, cokelat, kelapa, kacang hitam), biaya produksi dan harga jual produk. 3. Pengolahan Data a. Memodelkan fungsi tujuan dan fungsi kendala ke dalam bentuk program linier. b. Menghitung nilai variabel keputusan dengan menggunakan Software QM. c. Mencari nilai optimal dengan menggunakan metode Branch and Bound. 4. Membuat kesimpulan dan saran.



UNIVERSITAS SUMATERA UTARA



UNIVERSITAS SUMATERA UTARA



BAB I PENDAHULUAN



1.9 Latar Belakang Penerapan ilmu mengenai operasi riset dalam kehidupan sehari-hari sangat banyak digunakan oleh manusia, misalnya pada bidang ekonomi. Faktor di bidang produksi semakin canggih, kebutuhan manusia yang semakin bertambah karena pertumbuhan penduduk yang semakin meningkat menyebabkan jumlah produksi barang-barang semakin meningkat pula sesuai dengan kebutuhan. Dalam suatu perusahaan industri besar keinginannya menjadi yang terdepan dan mencapai tujuan untuk mendapatkan hasil yang optimal dengan batasan-batasan yang ada berupa bahan baku, peralatan, mesin, waktu, biaya dan tenaga kerja. Dalam hal ini, Usaha Dagang (UD) Akbar Jaya adalah salah satu perusahaan produksi yang bergerak dalam bidang roti di Medan yang ingin mencapai tujuan untuk mendapatkan keuntungan maksimum. Usaha dagang adalah kegiatan membeli dan menjual kembali barang atau jasa dengan tujuan mencari keuntungan termasuk menjadi perantara dari kegiatan tersebut. Usaha dagang ingin memperoleh laba yang besar dengan biaya produksi yang kecil, dengan begitu sebuah perusahaan akan terus beroperasi dan berkembang. Dalam dunia nyata, banyak perusahaan yang tidak mampu mempertahanan laba bahkan meningkatkan laba (mengalami kerugian). Hal ini dapat disebabkan beberapa faktor, antara lain kurangnya pengelolahan dalam hal produksi (persediaan produk berlebihan atau produk yang diproduksi tidak memenuhi permintaan pasar). Pemanfaatan energi dan pemakaian bahan baku yang optimal sangat diperlukan dalam memaksimalkan jumlah produksi yang akan menghasilkan keuntungan yang lebih besar. Modal yang sedikit mampu menghasilkan keuntungan yang banyak, sehingga muncul masalah optimasi. Masalah optimasi meliputi meminimumkan biaya atau memaksimalkan keuntungan dengan kapasitas sumber daya yang ada agar mampu mendapatkan hasil yang optimal. Optimalisasi adalah proses mencari solusi optimal



UNIVERSITAS SUMATERA UTARA



2



dari



sebuah



permasalahan



dengan



menggunakan



model



matematis



dan



pemecahannya dapat menggunakan program linear. 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 grafik dan metode simpleks. Program linier adalah suatu teknik perencanaan yang bersifat analitis menggunakan model matematis dengan tujuan menemukan beberapa kombinasi alternatif pemecahan optimum terhadap suatu persoalan. Program bilangan bulat atau program integer adalah sebuah program linear dengan persyaratan tambahan bahwa semua nilai variabelnya merupakan bilanganbilangan bulat. Metode yang digunakan untuk menyelesaikan masalah yang ada adalah metode Cabang dan Batas (Branch and Bound). Metode branch and bound adalah salah satu metode untuk menghasilkan penyelesaian optimal program linier 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 (Widi Hartono, 2014).



1.10



Rumusan Masalah



Berdasarkan latar belakang masalah diatas, permasalahan yang dibahas untuk menghasilkan keuntungan produksi yang besar adalah dengan mengoptimalkan jumlah bahan baku produksi serta meminimumkan biaya produksi.



UNIVERSITAS SUMATERA UTARA



3



1.11



Batasan Masalah



Adapun yang menjadi batasan masalah dalam penulisan skripsi ini yaitu : 5. Permasalahan yang dibahas adalah 4 jenis roti. 6. Permasalahan yang dibahas adalah proses sekali produksi bahan baku. (Proses sekali produksi adalah proses penggunaan total bahan baku dalam satu periode). 7. Dalam menyelesaikan produksi, biaya bahan baku dianggap konstan. (Biaya bahan baku dianggap konstan adalah biaya pembelian bahan baku selama proses penelitian tidak mengalami perubahan). 8. Pengadaan bahan baku tetap tersedia.



1.12



Tinjauan Pustaka



Sebagai sumber pendukung teori dalam penulisan ini, penulis mengambil beberapa pustaka dan penelitian terdahulu yang memberikan kontribusi dalam penyelesaian skripsi ini. 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. Siagian P (1987) mengemukakan bahwa pokok pikiran yang paling utama dalam menggunakan program linier adalah merumuskan masalah dengan jelas menggunakan sejumlah informasi yang tersedia. Kemudian menterjemahkan 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: 4. Tujuan (objective) yang akan dicapai dapat dinyatakan dalam bentuk fungsi linier yang disebut sebagi fungsi tujuan (objective function).



UNIVERSITAS SUMATERA UTARA



4



5. Harus ada alernatif pemecahan. Pemecahan yang membuat fungsi tujuan optimum (laba maksimum, biaya minimum dan sebagainya) yang harus dipilih. 6. Sumber-sumber tersedia dalam jumlah yang terbatas (bahan mentah terbatas, modal terbatas, ruangan untuk menyimpan barang terbatas dan sebagainya). Pembatasan-pembatasan harus dinyatakan dalam ketidaksamaan yang linier (linear inequality). 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). Dalam setiap submasalah perlu mendapatkan batas (bound) mengenai seberapa jauh solusi layak terbaik dapat dicapai. Untuk submasalah baru, dapatkan upper bound dan lower bound kemudian bulatkan ke bawah nilai z nya untuk menghasilkan solusi yang optimal. Menghilangkan solusi kontinu yang tidak memenuhi persyaratan bilangan bulat dilakukan dengan membatasi (bounding) nilai solusi pecah yang layak, seberapa baik solusi terbaik dalam himpunan bagian dan kemudian menghilangkan himpunan bagian apabila batas mengindikasikan bahwa himpunan bagian tersebut tidak mungkin berisi solusi optimal untuk kasus awal. Dalam mengoptimalkan keuntungan perusahaan dapat diketahui dengan rumus: KEUNTUNGAN = HARGA JUAL – HARGA PRODUKSI Dengan menggunakan model di atas diasumsikan jumlah produksi=jumlah yang di jual, maka dapat diketahui keuntungan maksimal yang dicapai perusahaan.



UNIVERSITAS SUMATERA UTARA



5



1.13



Tujuan Penelitian



Tujuan utama dari penelitian ini adalah untuk memperlihatkan bahwa



metode



Branch and Bound merupakan salah satu alternatif yang dapat digunakan untuk mengoptimalkan keuntungan penjualan roti di UD. Akbar Jaya.



1.14



Manfaat Penelitian



Manfaat dari penelitian ini adalah sebagai berikut: 4. Bagi Usaha Dagang Sebagai bahan pertimbangan dan masukan dalam mengoptimalkan keuntungan produksi dan dapat digunakan sebagai alternatif untuk menghasikan keuntungan yang besar. 5. Bagi Peneliti Peneliti mendapatkan pengalaman yang berharga melalui keterlibatannya secara langsung pada dunia kerja serta mengaplikasikan ilmu pengetahuan yang diperoleh



tentang



metode



Branch



and



Bound



dalam



menganalisa



pengoptimalisasian keuntungan produksi. 6. Bagi Universitas Menambah kepustakaan universitas yang sudah ada, khususnya mengenai pengoptimalisasian keuntungan produksi yang tepat.



1.15



Lokasi Penelitian



Penelitian dilakukan di UD. Akbar Jaya, yang beralamat di Jalan Sempurna No.59 Sudirejo I, Teladan, Medan.



1.16



Metodologi Penelitian



Penelitian disusun dengan langkah-langkah sebagai berikut: 5. Studi Pendahuluan Mengumpulkan dan mempelajari berbagai informasi berupa buku-buku ataupun jurnal-jurnal yang berhubungan dengan metode Branch and Bound.



UNIVERSITAS SUMATERA UTARA



6



6. Pengumpulan Data Data yang diperoleh ialah jenis bahan baku (tepung, mentega, gula pasir, garam, pengembang, bluberry, cokelat, kelapa, kacang hitam), biaya produksi dan harga jual produk. 7. Pengolahan Data d. Memodelkan fungsi tujuan dan fungsi kendala ke dalam bentuk program linier. e. Menghitung nilai variabel keputusan dengan menggunakan Software QM. f. Mencari nilai optimal dengan menggunakan metode Branch and Bound. 8. Membuat kesimpulan dan saran.



UNIVERSITAS SUMATERA UTARA



BAB 2 LANDASAN TEORI



2.1 Program Linier Program linier disusun oleh George Dantzig tahun 1947 pada saat memimpin Air Force Statistical Control’s Combat Analysis Branch di Pentagon. Saat Dantzig menganalisis masalah perencanaan Air Force dia menyadari dapat merumuskan sistem ketidaksamaan linier. Hal di atas merupakan awal pemberian nama untuk teknik “program dan struktur linier”, yang belakangan ini disederhanakan menjadi program linier (Taylor, 2001). 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). 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 berikutnyaadalah menerjemahkan masalah ini ke dalam bentuk model matematika, yang mempunyai cara pemecahan yang lebih mudah dan terstruktur guna menemukan solusi terhadap masalah yang dihadapi (Siagian, 1987). 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



8



Pembatasan-pembatasan harus dinyatakan di dalam ketidaksamaan yang linier (linear inequality). Umumnya masalah program linier dapat diselesaikan dengan menggunakan 2 metode, yaitu : 1. Metode grafik Metode ini digunakan apabila jumlah variabel keputusan hanya dua dan jumlah kendala dalam model relatif sedikit (umumnya tidak lebih dari 4 kendala). Apabila jumlah kendalanya relatif banyak (> 4 kendala), maka akan sukar untuk melukiskan garis kendalanya dalam grafik. 2. 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. 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.



UNIVERSITAS SUMATERA UTARA



9



2.1.1 Model Program Linier Model persamaan umum dalam program linier dapat dirumuskan sebagai berikut (Aminudin, 2005): Maksimalkan atau minimumkan : 𝑛



𝑍 = ∑ 𝑐𝑗 𝑥𝑗



(1)



𝑗=1



Dengan kendala : 𝑛



∑ 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑎𝑡𝑎𝑢 ≥ 𝑏𝑖



(2)



𝑗=1



𝑥𝑗 ≥ 0 Untuk𝑖 = 1, 2, 3, … , 𝑚 𝑗 = 1, 2, 3, … , 𝑛 Atau dapat ditulis secara lengkap sebagai berikut : Maksimalkan atau minimumkan : 𝑍 = 𝑐1 𝑥1 + 𝑐2 𝑥2 + 𝑐3 𝑥3 + … + 𝑐𝑛 𝑥𝑛



(3)



Dengan kendala : 𝑎11 𝑥1 + 𝑎12 𝑥2 + 𝑎13 𝑥3 + … + 𝑎1𝑛 𝑥𝑛 ≤ 𝑎𝑡𝑎𝑢 ≥ 𝑏1 𝑎21 𝑥1 + 𝑎22 𝑥2 + 𝑎23 𝑥3 + … + 𝑎2𝑛 𝑥𝑛 ≤ 𝑎𝑡𝑎𝑢 ≥ 𝑏2 . .



.



. .



.



.



.



.



.



.



..



.



.



.



.



.



.



. .



𝑎𝑚1 𝑥1 + 𝑎𝑚2 𝑥2 + 𝑎𝑚3 𝑥3 + … + 𝑎𝑚𝑛 𝑥𝑛 ≤ 𝑎𝑡𝑎𝑢 ≥ 𝑏𝑚 (4) 𝑥𝑗 ≥ 0



untuk 𝑗 = 1, 2, 3, … , 𝑛



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



UNIVERSITAS SUMATERA UTARA



10



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. Karakteristik Program Linier Karakteristik-karakteristik



dalam



program



linier



yang



biasa



digunakan



untukmemodelkan suatu masalah dan memformulasikannya secara matematik, yaitu(Siswanto, 2006): 1. Variabel Keputusan Variabel



keputusan



adalah



variabel



yang



secara



lengkap



menguraikankeputusan-keputusan yang akan dibuat. 2. Fungsi Tujuan Fungsi tujuan merupakanfungsi yang menggambarkan tujuan/sasaran di dalam permasalahan program linier yang berkaitan dengan pengaturan secara optimal, untuk memperoleh keuntungan maksimum atau biaya minimum. Pada umumnya nilai yang akan dioptimalkan dinyatakan sebagai Z. 3. Fungsi Kendala Fungsi kendala merupakan batasan-batasan dalam penyelesaian programlinier yang



harus



diperhatikan.



Kendala



diekspresikan



dalam



persamaan



danpertidaksamaan yang juga merupakan hubungan linier dari variabel keputusanyang mencerminkan keterbatasan sumber daya dalam suatu masalah.



UNIVERSITAS SUMATERA UTARA



11



2.1.3 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 𝑥𝑗 ≥ 0. 3. Variabel-variabel 𝑥𝑗 disebut sebagai variabel keputusan (decision variables). 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. 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. 3. Divisibility, berarti keluaran yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. 4. Deterministic (certainty), berarti bahwa semua parameter (𝑎𝑖𝑗 , 𝑏𝑖 , dan 𝑐𝑗 ) yang terdapat pada program linier dapat diperkirakan dengan pasti, meskipun dalam kenyataannya tidak sama persis.



UNIVERSITAS SUMATERA UTARA



12



2.2 Program Integer (Program Bilangan Bulat) Program integer adalah suatu bentuk dari program matematika. Program bilangan bulat merupakan suatu model program linier yangkhusus digunakan untuk menyesuaikan suatu problem program linier di mananilai-nilai variabel-variabel keputusan dalam penyelesaian optimal harusmerupakan bilangan bulat. Persyaratan bahwa nilai variabel keputusan harus bulatmengingat nilai tidak mungkin dalam bilangan pecahan, seperti rumah, pabrik,tugas, dan lain sebagainya (Sitorus, 1997). 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). 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 : 𝑛



𝑍 = ∑ 𝑐𝑗 𝑥𝑗



(5)



𝑗=1



Dengan kendala : 𝑛



∑ 𝑎𝑖𝑗 𝑥𝑗 (≥, =, ≤)𝑏𝑖



(6)



𝑗=1



𝑥𝑗 ≥ 0 semua bilangan cacah



UNIVERSITAS SUMATERA UTARA



13



Untuk 𝑖 = 1, 2, 3, … , 𝑚 𝑗 = 1, 2, 3, … , 𝑛



Keterangan: 𝑍 𝑥𝑗 𝑐𝑗 𝑎𝑖𝑗



𝑏𝑖 𝑛 𝑚



= Fungsi tujuan yang harus dicari nilai optimalnya (maksimal atau minimal) = Tingkat kegiatan ke- j = Kenaikan nilai Z terjadi apabila ada pertambahan tingkatkegiatan 𝑥𝑗 dengan satu satuan unit atau sumbangan setiapsatuan 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.3 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 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



UNIVERSITAS SUMATERA UTARA



14



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: 1. Branching adalah proses membagi-bagi permasalahan menjadi subproblemsubproblem yang mungkin mengarah ke solusi. 2. Bounding adalah suatu proses untuk mencari/menghitung batas atas dan batas bawah untuk solusi optimal pada subproblem yang mengarah ke solusi.



2.3.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. 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 kelangkah 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 dijadikanpencabangan ke dalam subsub 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



UNIVERSITAS SUMATERA UTARA



15



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.3.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. 4. Pada masalah meminimumkan penghentian pencabangan pada suatu sub masalah dilakukan jika batas bawah tidak lebih lebih kecil atau sama dengan batas atas.



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



16



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



Masalah Linear Programming diselesaikan dengan metode simpleks tanpa pembatasan bilangan bulat



Teliti solusi optimumnya



Variabel basis yang diharapkan bilangan bulat



Salah satu variabel basis yang diharapkan tidak 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.1. Kerangka Kerja Metode Branch and Bound



UNIVERSITAS SUMATERA UTARA



17



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



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



UNIVERSITAS SUMATERA UTARA



18



-



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