Modul ke:
Metodologi Penelitian PEMROGRAMAN LINIER
Fakultas
Program Pasca Sarjana Program Studi
Magister Teknik Elektro
Hamzah Hilal
13.1 UMUM Banyak keputusan manajemen dan atau riset operasi berkaitan dengan usaha untuk menggunakan sumber daya organisasi dengan cara yang paling efektif. Sumber daya biasanya meliputi permesinan (contohnya pesawat terbang, dalam kasus perusahaan penerbangan), tenaga kerja (pilot), uang, waktu dan bahan baku (bahan bakar), dan lain‐lain. Sumber daya ini dapat digunakan untuk menghasilkan produk (seperti mesin, mebel, makanan, pakajan), atau jasa (seperti jadwal penerbangan, kebijakan periklanan, atau keputusan investasi). Pemrograman linier (linear programming‐LP) adalah suatu teknik matematik yang didesain untuk membantu para manajer atau peneliti operasi dalam merencanakan dan membuat keputusan yang diperlukan untuk mengalokasikan sumber daya.
Beberapa contoh permasalahan di mana LP telah berhasil diterapkan dalam bidang operasi adalah : Penjadwalan bus sekolah untuk meminimalkan jarak perjalanan total untuk mengantar, dan menjemput para pelajar. Mengalokasikan unit‐unit jaga polisi ke daerah yang memiliki tingkat kejahatan tinggi untuk memaksimalkan waktu respons. Penjadwalan kasir untuk memenuhi kebutuhan harian, selagi meminimalkan total biaya tenaga kerja. Memilih bauran produk pada suatu pabrik untuk memanfaatkan penggunaan mesin dan jam kerja yang tersedia sebaik mungkin, selagi memaksimalkan laba perusahaan. Pemilihan bauran komposisi makanan untuk menghasilkan kombinasi makanan dengan biaya minimal. Menentukan sistem distribusi yang akan meminimalkan biaya pengiriman total dari beberapa gudang ke beberapa lokasi pasar. Membuat suatu jadwal produksi yang akan mencukupi permintaan di masa mendatang akan suatu produk perusahaan dan pada saat yang bersamaan meminimalkan biaya persediaan dan biaya produksi total. Mengalokasikan ruangan untuk para penyewa yang bercampur dalam pusat perbelanjaan baru untuk memaksimalkan pendapatan perusahaan penyewaan. Dan lain‐lain
13.2 PERSYARATAN SEBUAH PERSOALAN PEMROGRAMAN LINIER Semua persoalan LP mempunyai empat sifat umum: Persoalan LP bertujuan untuk memaksimalkan atau meminimalkan kuantitas (pada umumnya berupa laba atau biaya). Sifat umum ini disebut sebagai fungsi tujuan (objective function) dari suatu persoalan LP. Tujuan utama suatu perusahaan pada umumnya adalah untuk memaksimalkan keuntungan pada jangka panjang. Dalam kasus sistem distribusi suatu perusahaan angkutan atau penerbangan, tujuan pada umumnya berupa meminimalkan biaya. Adanya batasan (constraints) atau kendala, yang membatasi tingkat sampai di mana sasaran dapat dicapai. Sebagai contoh, keputusan untuk memproduksi berapa banyak unit tiap produk dalam suatu lini produk perusahaan, dibatasi oleh tenaga kerja dan permesinan tersedia. Oleh karena itu, memaksimalkan atau meminimalkan suatu kuantitas (fungsi tujuan) bergantung pada sumber daya yang jumlahnya terbatas
Harus ada beberapa alternatif tindakan yang dapat diambil. Sebagai contoh, jika suatu perusahaan menghasilkan tiga produk berbeda, manajemen dapat menggunakan LP untuk memutuskan bagaimana cara mengalokasikan sumber dayanya yang terbatas (tenaga kerja, permesinan, dan seterusnya). Jika tidak ada alternatif yang dapat diambil, maka LP tidak diperlukan. Tujuan dan batasan dalam permasalahan pemrograman linear harus dinyatakan hubungan dengan pertidaksamaan atau persamaan linear.
13.3 MEMFORMULAKAN PERSOALAN PEMROGRAMAN LINEAR Salah satu penerapan pemrograman linier yang paling umum adalah masalah bauran produk. Dua atau lebih produk pada umumnya diproduksi dengan menggunakan sumber daya yang terbatas. Perusahaan ingin menentukan berapa banyak unit dari tiap produk tersebut yang perlu dihasilkan untuk memaksimalkan laba keseluruhan dengan sumber dayanya yang terbatas. Berikut ini akan diberikan suatu contoh dari perusahaan Shader Electronics yang menghasilkan dua produk yaitu: Walkman, sebuah radio kaset portabel, dan Watch‐TV, sebuah televisi hitam putih seukuran jam tangan.
Proses produksi untuk masing‐masing produk serupa, dan keduanya memerlukan waktu tertentu untuk pengerjaan elektonis dan waktu tertentu dalam pengerjaan perakitan. Setiap Walkman membutuhkan waktu selama 4 jam untuk pengerjaan elektronik dan 2 jam untuk perakitan. Setiap Watch‐TV memerlukan waktu selama 3 jam untuk pengerjaan elektronik dan 1 jam untuk perakitan. Sepanjang periode produksi sekarang, tersedia waktu selama 240 jam waktu pengerjaan elektronik dan 100 jam waktu perakitan. Setiap Walkman menghasilkan laba $7; dan setiap Watch‐TV yang diproduksi menghasilkan laba $5. Permasalahan yang dihadapi Shader adalah bagaimana menentukan kombinasi terbaik antara jumlah Walkman dan Watch‐TV yang dibuat untuk mencapai laba yang maksimal.
Situasi bauran produk ini dapat diformulakan sebagai masalah pemrograman linier. Tabel 13.1 Waktu yang dibutuhkan untuk memproduksi 1 unit
Departemen
Walkman (X1)
Watch-TV (X2)
Jam kerja yang tersedia
Elektronis Perakitan Laba per unit
4 2 $7
3 1 $5
240 100
Dengan mengambil: X1 = jumlah Walkman yang akan diproduksi X2 = jumlah Watch-TV yang akan diproduksi,
maka fungsi tujuan LP dapat dibuat dalam kaitannya dengan X1 dan X2 adalah: Memaksimalkan laba = $7 X1 + $ 5X2
Membuat hubungan matematik untuk menentukan kedua batasan. Suatu hubungan yang umum adalah bahwa jumlah suatu sumber daya yang digunakan harus lebih kecil daripada atau sama dengan () jumlah sumber daya yang tersedia. Karena itu: Batasan pertama, yaitu: waktu elektronik yang diperlukan waktu elektronik yang tersedia, atau 4X1 + 3X2 240 (waktu pengerjaan elektronik). Batasan kedua, yaitu: waktu perakitan yang diperlukan waktu perakitan yang tersedia, atau 2X1 + 1X2 100 (waktu pengerjaan perakitan)
Kedua batasan ini mewakili adanya keterbatasan kapasitas produksi dan, tentu saja, mempengaruhi laba total. Sebagai contoh, Shader Electronics tidak dapat menghasilkan 70 Walkman sepanjang periode produksi, sebab jika X1 = 70, maka kedua batasan tadi akan dilanggar. Perusahaan juga tidak dapat membuat Walkman X1 = 50 dan Watch‐TV X2 = 10.
13.4 SOLUSI GRAFIS PERMASALAHAN PEMROGRAMAN LINIER Cara yang paling mudah untuk memecahkan suatu permasalahan LP yang kecil seperti pada persoalan perusahaan Shader Electronics adalah dengan menggunakan pendekatan solusi secara grafis (graphical solution approach). Prosedur grafis ini hanya dapat digunakan jika terdapat dua buah variabel keputusan (decision variables), seperti jumlah Walkman yang dihasilkan, X1 dan jumlah Watch‐TV yang dihasilkan, X2. Ketika terdapat lebih dari dua variabel, maka tidak mungkin memetakan solusi pada grafik dua dimensi, dan harus menggunakan pendekatan yang lebih rumit yang akan diuraikan kemudian pada bagaian lain.
13.4.1 Menggambarkan Batasan Secara Grafis Variabel X1 (pada contoh sebelumnya adalah Walkman) dipetakan sebagai sumbu horizontal grafik, dan variabel X2 (Watch‐TV) dipetakan sebagai sumbu vertikal. Permasalahan secara lengkap dapat dinyatakan ulang sebagai: Memaksimalkan laba = $7X1 + $5X2, dengan batasan: 4X1 + 3X2 240 (batasan waktu pengerjaan elektronik) 2X1 + 1X2 100 (batasan waktu pengerjaan perakitan) X1 0 (jumlah Walkman yang diproduksi lebih besar atau sama dengan 0) X2 0 (jumlah Watch‐TV yang diproduksi lebih besar atau sama dengan 0)
Langkah pertama yang dilakukan dalam memetakan batasan dari masaiah ini adalah mengubah pertidaksamaan batasan ini menjadi persamaan, sehingga: Batasan A: 4X1 + 3X2 = 240 Batasan B: 2X1 + 1X2 = 100 Kedua batasan diperlihatkan pada gambar berikut:
Gambar 13.2 Grafik kedua batasan secara bersamaan
13.4.2 Metode Solusi Garis Iso‐Profit Setelah daerah yang layak digambarkan, proses pencarian solusi yang optimal dapat dilanjutkan. Solusi yang optimal adalah suatu titik yang terletak dalam daerah yang layak yang menghasilkan laba yang paling tinggi. Bila daerah yang layak telah didapatkan, beberapa pendekatan dapat diambil untuk memecahkan solusi optimal tersebut. Satu cara yang paling cepat adalah metode garis iso‐profit (iso‐profit line method). Proses pencarian optimal dapat dimulai dengan menjadikan laba sama pada jumlah tertentu. Untuk permasalahan Shader Electronics, suatu laba senilai $210 dapat dipilih sebagai contoh. Tingkat laba ini bisa didapatkan secara mudah tanpa melanggar salah satu dari kedua batas yang ada. Fungsi tujuan dapat ditulis sebagai: $210 = $7X1 + $5X2.
Persamaan di atas merupakan sebuah garis, yang disebut sebagai garis iso‐profit. Garis ini mewakili semua kombinasi (dari X1 dan X2) yang akan menghasilkan total laba sebesar $210. Bila garis ini dipetakan, maka diperoleh: Untuk X1 = 0 akan menghasilkan X2 = 42 Watch‐TV. Untuk X2 = 0 akan menghasilkan X1= 30 Walkman. $420 tidak menyentuh daerah yang layak
Gambar iso profit $210
Gambar berbagai iso profit
Garis iso‐profit yang paling tinggi ditunjukkan pada gambar 13.4. Garis ini menyentuh ujung daerah yang layak pada titik sudut (X1 = 30, X2 = 40) dan menghasilkan laba senilai $410.
13.4.3 Metode Solusi Titik‐Sudut Pendekatan kedua untuk memecahkan permasalahan pemrograman linier adalah dengan menggunakan metode titik‐ sudut (corner‐point method). Teknik ini lebih sederhana dibandingkan dengan pendekatan garis iso‐profit, dengan cara membandingkan laba pada tiap‐tiap sudut daerah yang layak. Teori matematik di balik pemrograman linear menyatakan bahwa sebuah solusi yang optimal bagi setiap permasalahan (yakni nilai‐ nilai X1, X2 yang menghasilkan laba yang maksimal) berada pada suatu titik sudut, atau titik ekstrem, dari daerah yang layak tersebut. Oleh karena itu, yang diperlukan adalah mencari nilai variabel hanya pada titik sudut saja, karena laba yang maksimal atau solusi optimal akan terdapat pada salah satu di antara mereka. Sekali lagi dapat dilihat pada gambar 13.5 bahwa daerah yang layak untuk perusahaan Shader Electronics adalah suatu poligon dengan empat titik sudut atau titik ekstrem ini diberi label , , , dan .
Untuk dapat menemukan nilai‐nilai (X1, X2) yang menghasilkan laba yang maksimal, harus ditemukan terlebih dahulu koordinat setiap titik sudut, dan kemudian menentukan dan membandingkan laba pada titik‐titik tersebut sebagai berikut: Titik : (X1 = 0, X2= 0), laba $7(0) + $5(0) = $0 Titik : (X1 = 0, X2= 80), laba $7(0) + $5(80) = $400 Titik : (X1 = 50, X2= 0), laba $7(50) + $5(0) = $350 Titik diperoleh dari penyelesaian persamaan simultan kedua persamaan batasan: 2X1 + 1X2 = 100 (waktu perakitan) X1 + 3X2 = 240 (waktu pekerjaan elektronik) yang menghasilkan: X1 = 30, X2 = 40 dengan laba sebesar $ 410
13.5 ANALISIS SENSITIVITAS Para manajer operasi pada umumnya tertarik lebih dari sekadar solusi optimal bagi suatu permasalahan LP. Selain mengetahui nilai dari setiap variabel keputusan (Xis) dan nilai dari fungsi tujuan, mereka juga ingin mengetahui seberapa sensitif solusi yang didapatkan jika parameter yang ada berubah. Sebagai contoh, apa yang terjadi jika koefisien fungsi tujuan tidaklah tepat, atau jika mereka berubah sebesar 10% atau 15%? Apa yang terjadi jika nilai‐nilai disisi kanan batasan berubah? Oleh karena solusi didapatkan dengan berdasarkan pada asumsi bahwa parameter yang ada adalah tetap, maka analisis sensitivitas memainkan peranannya. Analisis sensitivitas (sensitivity analysis), atau analisis pascaoptimal, merupakan suatu penelitian seberapa sensitif solusi yang didapatkan jika parameter berubah. Untuk menentukan seberapa sensitif suatu solusi optimal akan adanya perubahan, maka dilakukan pemecahan masalah secara keseluruhan, biasanya dengan menggunakan komputer, pada setiap kali satu data item atau parameter input berubah.
13.5.1 Perubahan Pada Sumber Daya Perubahan pada sumber daya atau nilai sisi tangan kanan (RHS value) hambatan sering kali mewakili sumber daya yang tersedia bagi perusahaan. Sumber daya tersebut dapat berupa jam tenaga kerja langsung atau jam mesin atau mungkin uang atau bahan baku produksi yang tersedia. Pada contoh Shader Electronics, dua sumber daya yang tersedia adalah jumlah jam elektronik dan jam perakitan. Jika tersedia jam tambahan, total laba yang lebih tinggi bisa dicapai. Berapa yang bersedia dibayarkan oleh perusahaan untuk jam tambahan tersebut? Apakah menguntungkan bagi perusahaan untuk memiliki tambahan jam elektronik? Bersediakah perusahaan untuk membayar tambahan jam perakitan? Analisis sensitivitas mengenai sumber‐sumber daya ini akan membantu manajer atau peneliti menjawab pertanyaan‐pertanyaan tersebut.
Jika RHS hambatan berubah, maka daerah yang layak yang mungkin akan berubah (kecuali hambatannya berlebihan atau redundant), demikian juga halnya dengan solusi optimal. Pada contoh Shader, 100 jam perakitan tersedia setiap minggunya dan laba maksimum yang mungkin tercapai adalah $410. Jika jam perakitan yang tersedia naik menjadi 110 jam, maka akan muncul solusi optimal baru seperti yang ditunjukkan pada gambar yaitu (45,20) dan laba $415. Jadi, tambahan 10 jam akan menghasilkan kenaikan laba sebesar $5 atau $0,5 per jam.
Jika jam perakitan yang tersedia turun menjadi 90 jam seperti yang ditunjukkan pada gambar, solusi optimal baru adalah (15,60) dan laba $405. Jadi, penurunan 10 jam akan menurunkan laba sebesar $5 atau $0,5 per jam. Perubahan laba sebesar $0,5 per jam yang dihasilkan dari perubahan jam yang tersedia disebut sebagai harga bayangan (shadow price). Shadow price hambatan merupakan perbaikan nilai fungsi tujuan yang dihasilkan dari penambahan satu unit pada RHS hambatan.
13.5.2 Perubahan Pada Koefisien Fungsi Tujuan Sejalan dengan perubahan kontribusi laba per unit pada masing‐ masing produk, kemiringan (slope) dari garis iso‐profit yang telah dilihat pada gambar‐gambar sebelumnya juga berubah. Akan tetapi, ukuran daerah yang layak yang mungkin, tetap sama. Jadi, lokasi titik sudutnya tidak berubah. Batasan hingga sejauh mana koefisien laba dari Walkman atau Watch‐TV dapat berubah tanpa mempengaruhi optimalitas solusi saat ini dapat dihitung dengan cara coba‐coba. Jika laba per unit untuk Watch‐TV turun menjadi $4 (yaitu penurunan sebesar $1 dari nilai sekarang sebesar $5), maka masih tetap optimal untuk memproduksi 30 Walkman dan 40 Watch‐TV. Laba total akan turun menjadi $370 (dari $410) karena masing‐masing Watch‐TV kini menghasilkan laba lebih kecil (turun $1 per unitnya). Namun, jika laba per unit turun di bawah $3,50 per Watch‐TV (berarti penurunan lebih dari $1,50 dari laba sekarang sebesar $5), maka solusi saat ini sudah tidak lagi optimal. Oleh karena itu masalah LP harus dipecahkan kembali untuk menemukan titik sudut optimal yang baru.
13.6 MEMECAHKAN PERSOALAN MINIMISASI Banyak permasalahan pemrograman linear mencakup meminimalkan suatu tujuan seperti biaya sebagai pengganti dari proses memaksimalkan sebuah fungsi laba. Sebagai contoh, sebuah rumah makan, ingin membuat sebuah jadwal kerja untuk memenuhi kebutuhan karyawan, selagi meminimalkan jumlah karyawan total. Juga, sebuah perusahaan manufaktur mungkin ingin mendistribusikan produknya dari beberapa pabrik ke banyak gudangnya di daerah dengan cara yang meminimalkan biaya pengiriman total. Persoalan minimasi dapat dipecahkan dengan menggunakan grafik dengan cara menetapkan terlebih dahulu daerah yang layak, dan kemudian menggunakan salah satu di antara metode titik‐sudut ataupun pendekatan garis iso‐cost (yang sama dengan metode iso‐profit pada permasalahan memaksimalkan) untuk dapat menemukan nilai‐nilai X1 dan X2 yang menghasilkan biaya yang minimal. Contoh berikut menunjukkan bagaimana memecahkan suatu masalah meminimalkan.
Cohen Chemicals, Inc., menghasilkan dua jenis cairan kimia untuk mencetak yaitu: Bahan kimia untuk foto hitam putih, yang membebani Cohen $2.500 per ton. Bahan kimia untul foto berwarna, senilai $3.000 per ton.
Berdasarkan pada suatu analisis tingkat persediaan dan sisa pesanan saat ini, manajer produksi Cohen telah memutuskan bahwa paling sedikit 30 ton bahan kimia untuk foto hitam putih dan sedikitnya 20 ton bahan kimia untuk foto berwarna, harus diproduksi selama periode produksi di bulan depan. Sebagai tambahan, manajer mencatat bahwa bahan mentah yang ada sangat mudah rusak dan harus digunakan dalam jangka waktu 30 hari. Untuk menghindari adanya pemborosan bahan mentah yang berharga mahal, maka Cohen harus menghasilkan paling sedikit 60 ton bahan kimia untuk mencetak foto tersebut pada bulan depan.
Informasi di atas dapat diformulakan sebagai sebuah persoalan minimisasi LP dengan parameter: X1 = jumlah bahan kimia untuk foto hitam putih yang akan diproduksi (ton) X2 = jumlah bahan kimia untuk foto berwarna yang akan diproduksi (ton)
Batasan dapat dibuat sebagai berikut: X1 30 ton bahan kimia untuk foto hitam putih X2 20 ton bahan kimia untuk foto berwarna X1 + X2 60 ton total X1, X2 $0 persyaratan nonnegativitas
Untuk memecahkan permasalahan bahan kimia Cohen secara grafis, daerah yang layak harus ditentukan terlebih dahulu, seperti diilustrasikan pada gambar berikut.
Permasalahan minimisasi sering menjadi tak terhingga seperti ditunjukkan pada sisi kanan dan sisi atas dari grafik yang ada pada gambar, tetapi karakteristik ini tidak menyebabkan adanya masalah untuk memecahkan persoalan ini. Sepanjang daerah ini dibatasi ke dalam (yaitu pada sisi kiri dan sisi bawah), titik sudut dapat ditemukan. Solusi optimal akan terletak pada salah satu titik sudut tersebut. Pada kasus ini, hanya terdapat dua titik sudut, yaitu a dan b seperti ditunjukkan pada gambar. Sangat mudah untuk menentukan bahwa titik a (X1 = 40, X2 = 20), dan bahwa titik b (X1 = 30, X2 = 30).
Solusi optimal ditemukan pada titik yang menghasilkan biaya total paling rendah. Jadi, biaya total: Pada titik a = 2.500 X1 + 3.000X2 = 2.500(40) + 3.000(20) = $160.000 Pada titik b = 2.500 X1 + 3.000X2 = 2.500(30) + 3.000(30) = $165.000
Biaya yang paling rendah bagi perusahaan Cohen Chemicals adalah titik a. Oleh karena itu, manajer operasi seharusnya memproduksi 40 ton bahan kimia untuk foto hitam putih dan 20 ton bahan kimia untuk foto berwarna.
13.7 PENERAPAN PEMROGRAMAN LINEAR Bauran Produk Bauran Produk Penjadwalan Produksi Penjadwalan Tenaga Kerja
Terima Kasih Hamzah Hilal
