PEMROGRAMAN KOMPUTER KODE MODUL: TIN 202
MODUL III LINEAR PROGRAMMING DAN VISUALISASI
LABORATORIUM TEKNIK INDUSTRI FAKULTAS TEKNIK UNIVERSITAS MUHAMMADIYAH SURAKARTA 2013
MODUL II
LINEAR PROGRAMMING DAN VISUALISASI
I. TUJUAN: Modul ini bertujuan agar tiap-tiap siswa mampu memahami konsep pemrograman linear, menggunakan software Matlab dalam komputasi permasalahan pemrograman linear, mengintegrasikan komputasi, visualisasi, dan pemrograman. Hal ini dilakukan dengan memecahkan permasalahan teknis yang terkait dengan komputasi, yang menggunakan pendekatan matrix dan formulasi vektor. Item penilaian terdiri dari kebenaran mengerjakan soal dalam merumuskan persamaan linier, menggunakan software Matlab dan kemampuan individu dalam mengkomunikasikan hasil. II. PROSEDUR PELAKSANAAN ATAU LINGKUP MODUL III: Prosedur pelaksanaan dan penyelesaian modul 2 antara lain : 1. Sebelum memulai pelatihan modul dua, masing-masing siswa diminta mengumpulkan tugas pendahuluan modul 2 (tugas pendahuluan terlampir). Alokasi waktu 10 menit. 2. Dosen pengampu atau asisten yang ditunjuk oleh dosen pengampu memberikan penjelasan ringkas tentang pemrograman linear dan penggunaan software Matlab untuk penyelesaiaan masalah pemrograman linear. Alokasi waktu 15 menit. 3. Setiap kelompok diberikan satu kasus yang penyelesaian masalahnya dapat menggunakan persamaan pemrograman linear. Setiap kelompok diminta untuk merumuskan persamaanpersamaan linear yang sesuai dengan kasus yang diberikan. 4. Seluruh kelompok mengikuti sesi pelatihan software Matlab di ruang komputer yang menjelaskan secara detail mengenai penggunaan software Matlab dalam fungsi matematika umum, dan memunculkan visualisasi permasalahan 2 dimensi dan 3 dimensi menurut kasus yang telah diberikan. Catatan: tiap-tiap siswa harus mengerjakan latihan soal pada software Matlab. 5. Sesi pelatihan selanjutnya adalah software Matlab yang harus diikuti oleh semua siswa yang diselenggarakan di ruang komputer, meliputi: Merumuskan persamaan programa linear dari masing-masing kasus yang diberikan. Membuat visualisasi permasalahan dari kasus tersebut. Memberikan penjelasan penyelesaian masalah dari hasil visualisasi permasalahan tersebut. 6. Tahap selanjutnya, masing-masing siswa diminta mengerjakan soal latihan ada 10 soal tentang pemrograman linear dengan menggunakan software Matlab. 7. Komunikasikan hasil pengolahan latihan 1, 2, 3, 4 dan 5 dengan asisten dan dosen pengampu. 8. Kumpulkan portofolio hasil latihan tersebut kepada asisten.
MODUL III LINEAR PROGRAMMING DAN VISUALISASI I. Penjelasan Singkat Tentang Linear Programing Linear programming adalah suatu teknis matematika yang dirancang untuk membantu manajer dalam merencanakan dan membuat keputusan dalam mengalokasikan sumber daya yang terbatas untuk mencapai tujuan perusahaan. Tujuan perusahaan pada umumnya adalah memaksimalisasi keuntungan, namun karena terbatasnya sumber daya, maka dapat juga perusahaan meminimalkan biaya. Linear Programming memiliki empat ciri khusus yang melekat, yaitu : a. Penyelesaian masalah mengarah pada pencapaian tujuan maksimisasi atau minimalisasi. b. Kendala yang ada membatasi tingkat pencapaian tujuan. c. Ada beberapa alternatif penyelesaian. d. Hubungan matematis bersifat linear. 1. Karakteristik Pemrograman Linier a. Sifat linearitas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. b. Sifat proporsional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proporsional terhadap level nilai variabel. c. Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak akan ditemukan bentuk perkalian silang pada model. Sifat additivitas berlaku baik bagi fungsi tujuan maupun pembatas (kendala). d. Sifat divisibilitas berarti unit aktivitas dapat dibagi ke dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan. e. Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu. Keempat asumsi (sifat) ini dalam dunia nyata tidak selalu dapat dipenuhi. Untuk meyakinkan dipenuhinya keempat asumsi ini, dalam pemrograman linier diperlukan analisis sensitivitas terhadap solusi optimal yang diperoleh. 2. Formulasi Permasalahan Urutan pertama dalam penyelesaian adalah mempelajari sistem relevan dan mengembangkan pernyataan permasalahan yang dipertimbangakan dengan jelas. Penggambaran sistem dalam pernyataan ini termasuk pernyataan tujuan, sumber daya yang membatasi, alternatif keputusan yang mungkin (kegiatan atau aktivitas), batasan waktu pengambilan keputusan, hubungan antara bagian yang dipelajari dan bagian lain dalam perusahaan, dan lain-lain. Penetapan tujuan yang tepat merupakan aspek yang sangat penting dalam formulasi masalah. Untuk membentuk tujuan optimalisasi, diperlukan identifikasi
anggota manajemen yang benar-benar akan melakukan pengambilan keputusan dan mendiskusikan pemikiran mereka tentang tujuan yang ingin dicapai. 3. Pembentukan model matematik Tahap berikutnya yang harus dilakukan setelah memahami permasalahan optimasi adalah membuat model yang sesuai untuk analisis. Pendekatan konvensional riset operasional untuk pemodelan adalah membangun model matematik yang menggambarkan inti permasalahan. Kasus dari bentuk cerita diterjemahkan ke model matematik. Model matematik merupakan representasi kuantitatif tujuan dan sumber daya yang membatasi sebagai fungsi variabel keputusan. Model matematika permasalahan optimal terdiri dari dua bagian. Bagian pertama memodelkan tujuan optimasi. Model matematik tujuan selalu menggunakan bentuk persamaan. Bentuk persamaan digunakan karena kita ingin mendapatkan solusi optimum pada satu titik. Fungsi tujuan yang akan dioptimalkan hanya satu. Bukan berarti bahwa permasalahan optimasi hanya dihadapkan pada satu tujuan. Tujuan dari suatu usaha bisa lebih dari satu. Tetapi pada bagian ini kita hanya akan tertarik dengan permasalahan optimal dengan satu tujuan. Bentuk umum pemrograman linier adalah sebagai berikut : Fungsi tujuan : Maksimumkan atau minimumkan z = c1x1 + c2x2 + ... + cnxn Sumber daya yang membatasi : a11x1 + a12x2 + ... + a1nxn = /≤ / ≥ b1 a21x1 + a22x2 + … + a2nxn = /≤ / ≥ b2 …am1x1 + am2x2 + … + amnxn = /≤ / ≥ bm x1, x2, …, xn ≥ 0 Simbol x1, x2, ..., xn (xi) menunjukkan variabel keputusan. Jumlah variabel keputusan (xi) oleh karenanya tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk mencapai tujuan. Simbol c1,c2,...,cn merupakan kontribusi masingmasing variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematiknya. Simbol a11,...,a1n,...,amn merupakan penggunaan per unit variabel keputusan akan sumber daya yang membatasi, atau disebut juga sebagai koefisien fungsi kendala pada model matematiknya. Simbol b1,b2,...,bm menunjukkan jumlah masing-masing sumber daya yang ada. Jumlah fungsi kendala akan tergantung dari banyaknya sumber daya yang terbatas. Pertidaksamaan terakhir (x1, x2, …, xn ≥ 0) menunjukkan batasan non negatif. Membuat model matematik dari suatu permasalahan bukan hanya menuntut kemampuan matematik tapi juga menuntut seni permodelan. Menggunakan seni akan membuat permodelan lebih mudah dan menarik. Latihan 1: Tentukan harga x1 dan x2 yang memaksimumkan nilai x1+ x2, dengan syarat bahwa x1+x2 ≤10, -x1 + x2 ≤5, x1≥1, dan x2≥1.
Masalah diatas dapat dituliskan kedalam bentuk baku sebagai berikut: Maximize x1-x2 Subject to x1+x2 ≤10, -x1+x2 ≤5, x1≥1, and x2≥1.
(Gambar Penyelesaian Soal Latihan LP) II. Visualisasi Pada Matlab Terakhir, Matlab dapat dianggap sebagai sebuah kalkulator grafik. Yaitu, kemampuan untuk menampilkan hasil kalkulasinya dalam bentuk visual atau grafik. Matlab memiliki fasilitas yang memadai dan bervariasi untuk memperlihatkan fitur-fitur grafik secara mudah dan menarik. Selain grafik, tersedia pula fasilitias untuk menganimasikan grafik yang telah dihasilkan. 1. Iterpolasi Satu Dimensi Interpolasi fungsi merupakan satu permasalahan klasik dalam analisa numerik. Interpolasi satu dimensi dirumuskan sebagai berikut: diberikan sekumpulan n+1 titik {xk , yk}, 0
a. Plot Menampilkan semua bilangan acak.
(Gambar Grafik Plot) b. Steam
(Gambar Contoh Tampilan Grafik Dengan Perintah Stem) Labelling Kalian mungkin telah menyadari bahwa semua plot sebelumnya yang telah dibuat tidak memiliki label keterangan. Ada banyak cara member label, cara yang paling sering digunakan adalah menggunakan perintah labeling.
(Grafik Hasil Pelabelan) c. Histogram Menampilkan histogram dari bilangan acak
(Grafik Histogram) d. PDF(Probability Density Function) Menampilkan fungsi kepadatan probabilitas (probability density function) dari bilangan acak.
(Grafik PDF)
e. CDF(Cumulative Density Function) Menampilkan fungsi kepadatan kumulatif.
(Grafik CDF) 3. Interpolasi 3 Dimensi Pada intinya untuk membentuk grafik 3 dimensi diperlukan 3 vektor yaitu vektor X, Y dan Z. contoh:
(Gambar Grafik 3 Dimensi 1)
(Gambar Grafik 3 Dimensi 2) Tabel fungsi grafik 3 dimensi:
CONTOH SOAL Sebuah perusahaan ingin menentukan berapa banyak masing-masing dari tiga produk yang berbeda yang akan dihasilkan dengan tersedianya sumber daya yang terbatas agar diperoleh keuntungan yang maksimum. Kebutuhan buruh dan bahan mentah serta keuntungan masing-masing produk adalah sebagai berikut:
Produk
Kebutuhan Sumber Daya Buruh (jam/unit)
Bahan (kg/unit)
Keuntungan (Rp/unit)
A
2
3
50
B
3
2
60
Tersedia 180 jam kerja dan bahan mentah sebanyak 150 kg. Maka tentukanlah jumlah masing-masing produk agar keuntungan maksimum? Penyelesaian: a Variabel Keputusan Terdapat tiga variabel dalam masalah ini yaitu produk A dan B. Maka dapat diasumsikan sebagai: X1 = jumlah produk A X2 = jumlah produk B b Fungsi Tujuan Tujuan masalah kombinasi produk adalah memaksimumkan keuntungan total. Maka keuntungan adalah jumlah keuntungan yang diperoleh masing-masing produk. Keuntungan produk A adalah perkalian antara jumlah produk A dengan keuntungan per unit, begitu pula dengan produk B dan C, sehingga: Z = 50X1 + 60X2 c Fungsi Kendala Fungsi kendala pada buruh, produk A membutuhkan buruh sebanyak 2 jam/unit, sehingga jumlah buruh yang dibutuhkan produk A adalah 2X1, begitu pula untuk produk B. Sementara jumlah buruh yang tersedia adalah 240. Maka: 2X1 + 3X2 ≤ 180 Fungsi kendala pada bahan mentah, produk A membutuhkan bahan mentah sebanyak 3 kg/unit, sehingga jumlah bahan mentah yang dibutuhkan produk A adalah 3X1, begitu pula untuk produk B. Karena yang tersedia sebanyak 150 kg bahan mentah, maka: 3X1 + 2X2 ≤ 150 Masing-masing variabel yang tersedia juga harus dibatasi dengan nilai posisif, karena tidak mungkin untuk menghasilkan jumlah produk negatif. X1, X2 ≥ 0 Dari analisis diatas, maka penyelesaian dengan Matlabnya adalah sebagai berikut: >> Z=[-50 -60]; >> a=[2 3;3 2]; >> b=[180;150]; >> Hasil=linprog(Z,a,b) Optimization terminated. Hasil = 18.0000
48.0000 >> Zmax=-Z*Hasil Zmax = 3.7800e+003 Jadi, agar keuntungan mencapai maksimum yaitu Rp 3.780,- maka harus memproduksi produk A sebanyak 18 buah dan produk B sebanyak 48 buah.