Seminar Nasional MATEMATIKA VOL. 10 TH. 2015 ISSN 1907-3909
UNIVERSITAS KATOLIK PARAHYANGANPARAHYANGAN
Seminar Nasional MATEMATIKA VOL. 10 TH. 2015 ISSN 1907-3909
REVIEWERS
Alamat Redaksi:
KATA PENGANTAR Puji syukur kami panjatkan ke hadirat Tuhan Yang Maha Esa atas terselenggaranya Seminar Nasional Matematika Unpar 2015. Seminar ini merupakan kegiatan rutin tahunan yang diselenggarakan oleh Jurusan Matematika, Universitas Katolik Parahyangan, yang dimulai sejak tahun 2005 dan tahun ini merupakan tahun ke-11 penyelenggaraannya. Seminar Nasional Matematika UNPAR ini merupakan wadah pertemuan ilmiah antara matematikawan, guru, peneliti, dan praktisi yang tidak hanya terbatas di bidang matematika saja, melainkan juga penerapannya dalam berbagai bidang ilmu, antara lain dunia medis, ekonomi lingkungan hidup, dan gejala alam.
Seminar tahun ini mengambil tema “PERAN MATEMATIKA DALAM MENGHADAPI MASYARAKAT EKONOMI ASEAN (MEA)”. Pemilihan tema ini dilatarbelakangi oleh kesepakatan para pemimpin ASEAN yang tertuang dalam “Deklarasi Cebu: Untuk Mempercepat Pembangunan Masyarakat ASEAN Sebelum 2015” yang ditandatangani oleh pemimpin ASEAN pada KTT ASEAN ke-12 bulan Januari 2007. Menurut rencana, ASEAN akan membangun sebuah masyarakat bersama sebelum tahun 2015 yang mencakup tiga bagian, yaitu masyarakat ekonomi, masyarakat keamanan dan masyarakat sosial budaya. Melalui seminar ini diharapkan para peserta dapat saling berbagi pengetahuan dan informasi terbaru sehingga berdampak pada kesiapan yang lebih baik dari Indonesia dalam menghadapi tantangan ini.
Seminar kali ini mengundang tiga orang pembicara dari kalangan akademisi dan praktisi yang akan berbagi pengalaman, gagasan dan pikiran. Pada sesi pararel, akan dipresentasikan 58 makalah yang merupakan hasil karya dosen, peneliti, dan mahasiswa dari berbagai instansi di tanah air.
Kami atas nama panitia Seminar Nasional Matematika Unpar 2015 mengucapkan terima kasih atas partisipasinya, semoga bermanfaat bagi semua pihak.
Bandung, September 2015 Ketua Panitia
Liem Chin, M.Si.
i
DAFTAR ISI Kata Pengantar Daftar Isi
...i ...iii-ix
ALJABAR DAN ANALISIS KARAKTERISTIK FUNGSIONAL DARI RUANG ATSUJI Suarsih Utama dan Nora Hariadi – Universitas Indonesia
...AA 1-6
SIFAT SUBHIMPUNAN DI RUANG ATSUJI Suarsih Utama dan Nora Hariadi – Universitas Indonesia
...AA 7-11
KARAKTERISTIK DIFERENSIAL SATU ROUND BARU PADA INTERNATIONAL DATA ENCRYPTION ALGORITHM (IDEA) Sari Agustini Hafman
...AA 12-18
STATISTIKA APLIKASI ANALISIS STATISTIK DESKRIPTIF SPHERICAL PADA DATA GEMPA BENGKULU Pepi Novianti – Universitas Bengkulu
...ST 1-6
ANALISIS STATISTIKA DESKRIPTIF DALAM PEMETAAN KEMISKINAN DI KOTA BENGKULU Dian Agustina, Pepi Novianti, Idhia Sriliana, dan Etis Sunandi – Universitas Bengkulu
...ST 7-18
PERBANDINGAN METODE PERAMALAN ANTARA ARIMA DAN SARIMA DALAM MEMODELKAN FLUKTUASI DEBIT AIR (Studi Kasus : Data Debit Air Pembangkit Listrik Tenaga Air Musi) Jose Rizal – Universitas Bengkulu
…ST 19-26
PEMILIHAN MODEL SEMIVARIOGRAM TERBAIK PADA DATA SPATIAL DENGAN APLIKASI METODE PROGRAM LINIER (Studi Kasus : Data Kejadian Gempa di Wilayah Pesisir Bengkulu) Fachri Faisal – Universitas Bengkulu
...ST 27-37
iii
ESTIMASI MODEL JUMLAH LEUKOSIT PENDERITA LEUKIMIA MENGGUNAKAN PENDEKATAN REGRESI SPLINE TRUNCATED DENGAN KUADRAT TERKECIL TERBOBOTI Idhia Sriliana – Universitas Bengkulu …ST 38-44 PELUANG SUATU TIM UNTUK MENCAPAI PERINGKAT TERTENTU DALAM SUATU TURNAMEN : STUDI KASUS SEPAKBOLA LIGA INGGRIS MUSIM KOMPETISI 2011/2012 Liem Chin dan Benny Yong – Universitas Katolik Parahyangan
…ST 45-54
KKN PPM STATISTIKA PEMERINTAHAN Neva Satyahadewi, Mariatul Kiftiah, dan Dadan Kusnandar – Universitas Tanjungpura
...ST 55-60
MATEMATIKA PENDIDIKAN EKSPLORASI PENGETAHUAN MATEMATIKA MASYARAKAT MELALUI RANCANGAN DAN IMPLEMENTASI TUGAS TEMATIK Patricia VJ Runtu dan Christophil Medellu – Universitas Negeri Manado ...MP 1-10 DISPOSISI MATEMATIS MAHASISWA CALON GURU MATEMATIKA Dadang Juandi, Eyus Sudihartinih, dan Ririn Sispiyati – Universitas Pendidikan Indonesia
...MP 11-18
VALIDASI MODUL APLIKASI KOMPUTER DENGAN PROGRAM WINGEOM PADA MATERI GEOMETRI Tika Septia dan Merina Pratiwi – STKIP PGRI Sumatera Barat
...MP 19-26
PENINGKATAN KEMAMPUAN PEMAHAMAN MATEMATIK DENGAN PENDEKATAN HANDS-ON ACTIVITY (Penelitian Kuasi Eksperimen Pada Siswa SMP Kelas VIII di Kota Bandung) Jarnawi Afgani Dahlan – Universitas Pendidikan Indonesia
...MP 27-34
PENCAPAIAN KEMAMPUAN BERPIKIR KRITIS SISWA SMP DALAM PEMBELAJARAN MATEMATIKA DENGAN STRATEGI REACT Nia Yuni Saputri, Tatang Herman, dan Kusnandi – Universitas Pendidikan Indonesia
...MP 35-45
iv
MENINGKATKAN HASIL BELAJAR MAHASISWA DENGAN MODEL PEMBELAJARAN AIR PADA MATA KULIAH EVALUASI PEMBELAJARAN MATEMATIKA Putu Suarniti Noviantari dan I Made Dharma Atmaja – Universitas Mahasaraswati Denpasar
...MP 46-50
PENINGKATAN KEMAMPUAN PEMECAHAN MASALAH MATEMATIS MAHASISWA BERDASARKAN MODEL PEMBELAJARAN KOOPERATIF TIPE TEAM ASSISTED INDIVIDUALIZATION (TAI) PADA MATA KULIAH TEORI PELUANG Georgina Maria Tinungki – Universitas Hasanuddin
...MP 51-60
PENGEMBANGAN MEDIA KATROL BILANGAN UNTUK PEMBELAJARAN BILANGAN BULAT DI SEKOLAH DASAR Haris Wisudiatma, Sri Harmini, dan Endang Setyo Winarni – Universitas Negeri Malang
...MP 61-69
ANALISIS PENGEMBANGAN MODUL TRIGONOMETRI Villia Anggraini dan Hamdunah – STKIP PGRI Sumatera Barat
...MP 70-74
PENGEMBANGAN STRATEGI AJAR KEMAMPUAN BERPIKIR LOGIS MATEMATIS MAHASISWA PADA PENERAPAN MATERI TRANSPORTASI DAN PEMODELAN MATA KULIAH RISET OPERASI TERHADAP PEMBERLAKUAN KEBIJAKAN ASEAN TRADE IN GOODS AGREEMENT (ATIGA) (Studi Kasus Pemodelan dan Transportasi Pada Komuditas Batu Alam dan Rotan Diantara Negara Anggota MEA) Alif Ringga Persada – IAIN Syekh Nurjati Cirebon
...MP 75-82
DESAIN DIDAKTIS KONSEP LUAS DAERAH BELAH KETUPAT PADA PEMBELAJARAN MATEMATIKA SMP Alin Meilina dan Rosita Mahmudah – Universitas Pendidikan Indonesia
...MP 83-91
JARINGAN SYARAF TIRUAN METODE BACK PROPAGATION UNTUK PENJURUSAN SISWA SMA Ulfasari Rafflesia – Universitas Bengkulu
...MP 92-98
KAJIAN MODEL PEMBELAJARAN : PENDEKATAN COGNITIVE APPRENTICESHIP MODEL CASE BASED REASONING DALAM PEMBELAJARAN MATEMATIKA Rina Oktaviyanthi – Universitas Serang Raya
...MP 99-107
v
MATEMATIKA TERAPAN ANALISIS PERBANDINGAN BARISAN BIT PSEUDORANDOM YANG DIHASILKAN ALGORITMA SOSEMANUK DAN HC-128 TERHADAP KESERAGAMAN DISTRIBUSI P-VALUE UJI NIST Desi Wulandari – Lembaga Sandi Negara
...MT 1-6
ESTIMASI VOLATILITAS DAN VALUE AT RISK INDEKS LQ45 DENGAN GENERALIZED PARETO DISTRIBUTION Yunita Wijaya, Kie Van Ivanky Saputra, dan Kim Sung Suk – Universitas Pelita Harapan
...MT 7-14
SINGLE-OBJEKTIF DAN MULTI-OBJEKTIF OPTIMISASI PORTOFOLIO DENGAN UKURAN RESIKO MEAN-VARIANCE MENGGUNAKAN DIFFERENTIAL EVOLUTION Yohanis Ndapa Deda – Institut Teknologi Bandung, Universitas Nusa Cendana, Kupang Kuntjoro Adji Sidarto – Institut Teknologi Bandung
...MT 15-20
GUESSING ATTACK PADA PROTOKOL KRITOGRAFI Arif Fachru Rozi
…MT 21-24
SUB-BLOK AKTIF SPN TERBAIK UNTUK SERANGAN KRIPTANALISIS DIFERENSIAL Arif Fachru Rozi
…MT 25-31
APLIKASI MATEMATIKA DALAM PEMODELAN RISIKO BENCANA TSUNAMI Yulian Fauzi – Universitas Bengkulu
...MT 32-36
PENGKLASTERAN DATA DENGAN MENGGUNAKAN METODE MONOTETIS (STUDI KASUS PADA DATA KELUARGA) Kania Sawitri – ITENAS
...MT 37-42
KONTROL OPTIMAL PADA MODEL EPIDEMIOLOGI TIPE SVIR DENGAN MEMPERHATIKAN REINFEKSI Jonner Nainggolan – Universitas Cenderawasih Jayapura
...MT 43-49
IMPLEMENTASI MODEL HARGA OPSI BASKET BERBASIS COPULA LEVY Syofia Rani, Bevina D. Handari, dan Hendri Murfi – Universitas Indonesia
...MT 50-56
vi
PENENTUAN PREMI TUNGGAL BERSIH UNTUK ASURANSI JIWA BERJANGKA UNIT LINK DENGAN GARANSI Siska Yosmar dan Syahrul Akbar – Universitas Bengkulu
...MT 57-63
BIFURKASI SADDLE-NODE PADA MODEL SIR DENGAN LAJU INSIDENSI YANG TAK LINEAR DAN ADANYA PERAWATAN Marsha Ad Georli, Livia Owen, dan Benny Yong – Universitas Katolik Parahyangan
...MT 64-74
MODEL MATEMATIKA PENYEBARAN INFEKSI HIV PADA KOMUNITAS INJECTING DRUG USERS Iffatul Mardhiyah – Universitas Gunadarma Hengki Tasman – Universitas Indonesia
...MT 75-82
SYARAT CUKUP BEROSILASI DAN TIDAK BEROSILASI PERSAMAAN DIFERENSIAL LINIER HOMOGEN ORDE DUA Maulana Malik – Universitas Gunadarma
...MT 83-89
IMPLEMENTASI ALGORITMA PARTICLE SWARM OPTIMIZATION PADA KALIBRASI MODEL HARGA OPSI HESTON Ilham Falani, Bevina D. Handari, dan Gatot F. Hertono – Universitas Indonesia ...MT 90-96 SPN CIPHER MODIFIKASI Sari Agustini Hafman dan Khairun Nisa
...MT 97-101
MODEL TRINOMIAL HARGA OPSI EROPA Fitriani Agustina dan Entit Puspita – Universitas Pendidikan Indonesia
...MT 102-106
ANALISIS PERKEMBANGAN OTAK JANIN DENGAN MENGGUNAKAN METODE ISOMAP Rifki Kosasih dan Achmad Fahrurozi – Universitas Gunadarma
...MT 107-113
MAHASISWA PEMODELAN FAKTOR YANG MEMPENGARUHI PERSENTASE PENDUDUK MISKIN PROVINSI PAPUA MENGGUNAKAN REGRESI SEMIPARAMETRIK SPLINE DALAM RANGKA MENGHADAPI ASEAN ECONOMIC COMMUNITY 2015 Eka Oktaviana Romaji, Wahyu Kurnia Dewi Nastiti, Zahrotun Nisaa’, Avinia Aisha Widhesaputri, dan Reta Noorina Prastika – Institut Teknologi Sepuluh Nopember
vii
…MS 1-8
TAKSIRAN JACKKNIFE RIDGE REGRESSION SEBAGAI TAKSIRAN PARAMETER MODEL REGRESI LINIER BERGANDA PADA KASUS MULTIKOLINIERITAS Effrida Betzy Stephany, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia
…MS 9-16
DISTRIBUSI GAMMA-HALF NORMAL Kania Rianti, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia
...MS 17-25
PENGGUNAAN METODE BAYES DALAM PENAKSIRAN UKURAN POPULASI YANG MEMPUNYAI NOMOR SERIAL Mario Valentino Nara, Ida Fithriani, dan Siti Nurrohmah – Universitas Indonesia
...MS 26-32
KAJIAN SKEMA E-VOTING DALAM APLIKASI SKEMA SECRET SHARING BERBASIS CHINESE REMAINDER THEOREM (CRT) DENGAN MENGGUNAKAN BARISAN MIGNOTTE Widuri Lisu dan Kiki Ariyanti Sugeng – Universitas Indonesia
...MS 33-40
IMPLEMENTASI ATURAN KUADRATUR NEWTON-COTES DENGAN KOREKSI PADA BATAS DAN MODIFIKASINYA Bevina Desjwiandra H., Gatot Fatwanto Hertono, dan Yola Fowell – Universitas Indonesia
...MS 41-48
OPTIMASI PORTOFOLIO DENGAN KENDALA BUY-IN THRESHOLD Erwin Natali Susanto dan Liem Chin – Universitas Katolik Parahyangan
...MS 49-54
MEMINIMUMKAN RISIKO PORTOFOLIO DENGAN TARGET RETURN MENGGUNAKAN METODE NEWTON Andris Rachardi, Liem Chin, dan Erwinna Chendra – Universitas Katolik Parahyangan
...MS 55-61
PREDIKSI KEBERHASILAN INDONESIA PADA POST FINAL DAN PASCA MDGs (MILLENNIUM DEVELOPMENT GOALS) 2015 DALAM PENANGGULANGAN KEMISKINAN DAN KELAPARAN DENGAN METODE PERAMALAN Indah Tri Wulandari, Joshua Bonasuhul, Riskha Tri Oktaviani, Akhmad Rayzha Naufal, dan Sutikno – Institut Teknologi Sepuluh Nopember …MS 62-70
viii
STUDI DAMPAK UNDANG-UNDANG MINERAL DAN BATUBARA (UU MINERBA) TERHADAP KEBERHASILAN EKSPOR INDONESIA MENGGUNAKAN METODE ANALISIS FAKTOR DAN CHERNOFF FACE Fefy D. S., Indah T. W., Avinia A. W., Rya S. A., Epa Suryanto, dan Mutiah Salamah – Institut Teknologi Sepuluh Nopember
...MS 71-78
SIFAT SUBHIMPUNAN LENGKAP DAN COMPLETELY DISCRETE DALAM RUANG YANG MEMILIKI ATSUJI COMPLETION Muhammad Ihsan Prasetio, Nora Hariadi, dan Suarsih Utama – Universitas Indonesia
...MS 79-86
PENYELESAIAN LINEAR FRACTIONAL PROGRAMMING DENGAN MENGGUNAKAN METODE CRISS CROSS Anggela Irene Wijaya, Taufik Limansyah, dan Dharma Lesmono – Universitas Katolik Parahyangan
...MS 87-93
DISTRIBUSI GAMMA-PARETO Ira Rosianal Hikmah, Siti Nurrohmah, dan Ida Fithriani – Universitas Indonesia
...MS 94-102
EFEKTIFITAS MENCATAT DAN PRAKTIK MENGGUNAKAN KOMPUTER SECARA LANGSUNG TERHADAP PRESTASI BELAJAR MAHASISWA MATA KULIAH EKSPLORASI SOFTWARE MATEMATIKA DI STKIP SURYA Hendy Halyadi, Titi Mellyani, Aprilita, dan Johannes H. Siregar – STKIP Surya
…MS 103-107
PENENTUAN RISIKO RELATIF UNTUK PENYEBARAN PENYAKIT DEMAN DENGUE DI KOTA BANDUNG PADA TAHUN 2013 DENGAN MENGGUNAKAN MODEL SMR Robyn Irawan, Benny Yong dan Farah Kristiani – Universitas Katolik Parahyangan
…MS 108-115
VALUASI VALUE AT RISK MENGGUNAKAN METODE COPULA Felivia dan Ferry Jaya Permana – Universitas Katolik Parahyangan ...MS 116-122
ix
PENYELESAIAN LINEAR FRACTIONAL PROGRAMMING DENGAN MENGGUNAKAN METODE CRISS CROSS Anggela Irene Wijaya1, Taufik Limansyah2, dan Dharma Lesmono3 1,2,3
Universitas Katolik Parahyangan email :
[email protected],
[email protected],
[email protected] 1
Abstrak. Di dalam Penelitian Operasional terdapat berbagai jenis model matematika, diantaranya pemrograman linear dan pemrograman non-linear yang digunakan dalam memodelkan masalah yang ada untuk memperoleh hasil yang optimal. Pada makalah ini akan dibahas kasus khusus dalam pemrograman non-linear yaitu pemrograman pecahan linear (Linear Fractional Programming atau LFP) yang nantinya dapat disederhanakan menjadi model pemrograman linear. Selain itu, makalah ini juga akan membahas dua metode yang digunakan untuk menyelesaikan masalah LFP yang telah disederhanakan, yaitu metode simpleks dan metode Criss Cross. Kata kunci : Pemrograman Linear, Metode Criss Cross, Linear Fractional Programming
1. PENDAHULUAN Banyak model yang digunakan untuk menyelesaikan masalah yang berkaitan dengan Penelitian Operasional. Salah satu model yang paling efektif adalah Pemrograman Linear (Linear Programming atau LP). Dalam model LP semua fungsi yang ada berupa fungsi linear. Banyak pengembangan metode yang dilakukan untuk menyelesaikan masalah LP. Salah satu metode yang terkenal adalah metode simpleks (George Dantzig – 1947). Selain metode simpleks, masih banyak metode lain yang digunakan untuk menyelesaikan masalah LP dan pada makalah ini akan dibahas metode yang diperkenalkan oleh Sanley Zionts pada tahun 1969 yaitu metode Criss Cross. Selain model LP, dalam Penelitian Operasional juga terdapat model lain yaitu pemrograman non-linear. Dalam pemrograman non-linear terdapat salah satu model yang membahas mengenai masalah optimasi perbandingan dari suatu fungsi objektif yaitu Fractional Programming (FP). Dalam model FP terdapat kasus khusus yang membahas mengenai Linear Fractional Programming (LFP). Masalah yang dibahas dalam model LFP adalah menentukan alokasi sumber daya yang dibutuhkan sehingga dapat memaksimumkan atau meminimumkan fungsi objektif yang berupa perbandingan. Dalam model ini tiap variabel dari fungsi kendala berupa fungsi linear dan fungsi objektif berupa perbandingan antara dua fungsi linear. Jika pada penyebut dari fungsi objektif masalah LFP adalah konstan, maka masalahnya dapat diubah menjadi model LP. Oleh sebab itu, LFP dapat disederhanakan bentuknya menjadi masalah LP melalui metode yang diperkenalkan oleh Charnes dan Cooper [3]. Metode penyederhanaan LFP menjadi LP dan penyelesaiannya menjadi pokok bahasan dari makalah ini. 2. METODE CRISS CROSS Metode simpleks, untuk masalah primal maupun dual, memerlukan solusi dasar (primal atau dual) yang fisibel. Permasalahannya sekarang, tidak ada yang dapat menjamin bahwa solusi dasar fisibel tersebut dapat diselesaikan hanya dengan menambahkan variabel buatan. Pada penambahan variabel buatan, solusi optimal tercapai hanya jika variabel buatannya bernilai nol. Dalam jurnal yang berjudul "The Criss Cross Method For Solving Linear Programming Problems" [1] diperkenalkan metode Criss Cross yang menghindari metode dua fase pada metode simpleks dalam menyelesaikan masalah LP standar. Metode Criss Cross adalah sebuah MS - 87
algoritma dengan menggabungkan masalah primal-dual dalam menyelesaikan masalah LP. Cara kerja metode ini adalah melihat penyelesaian dasar (primal atau dual fisibel) yang terkait dan setelah itu akan secara bergantian dilakukan iterasi (primal atau dual) hingga didapatkan penyelesaian optimumnya. Bentuk umum dari masalah primal dan dual yang berkaitan dengan penyelesaian menggunakan metode Criss Cross dirumuskan sebagai berikut. Primal :[2] 𝑛
Maksimumkan 𝑍 = ∑ 𝑐𝑗 𝑋𝑗 𝑗=1
dengan fungsi kendala :
𝑛
∑ 𝑎𝑖𝑗 𝑋𝑗 = 𝑏𝑖 ; 𝑖 = 1,2, … , 𝑚 𝑗=1
𝑋𝑗 ≥ 0 ; 𝑗 = 1,2, … , 𝑛
Dual :
𝑛
Minimumkan 𝑊 = ∑ 𝑏𝑖 𝑌𝑖 𝑖=1
dengan fungsi kendala :
𝑛
∑ 𝑎𝑖𝑗 𝑌𝑖 = 𝑏𝑖 ; 𝑗 = 1,2, … , 𝑛 𝑖=1
𝑌𝑖 ≥ 0 ; 𝑖 = 1,2, … , 𝑚
Berikut adalah contoh permasalahan yang akan diselesaikan dengan menggunakan metode Criss Cross. Minimumkan 𝑍 = −3𝑋1 + 4𝑋2 dengan kendala : 𝑋1 + 2𝑋2 ≥ 2 3𝑋1 + 𝑋2 ≥ 4 𝑋1 − 𝑋2 ≤ 1 𝑋1 + 𝑋2 ≤ 8 dan 𝑋1 , 𝑋2 ≥ 0. Solusi : Mengubah kendala pertama dan kedua menjadi pertidaksamaan ≤ sehingga diperoleh −𝑋1 − 2𝑋2 ≤ −2 −3𝑋1 − 𝑋2 ≤ −4 Tabel awal permasalahan di atas : Solusi 𝑋1 𝑋2 𝑍 −3 −4 0 𝑆1 −1 −2 −2 𝑆2 −3 −1 −4 𝑆3 1 −1 1 𝑆4 1 1 8 Karena ruas kanan (kolom solusi) fungsi kendala dan koefisien fungsi tujuan (baris 𝑍) masih ada yang bernilai negatif, maka untuk iterasi pertama bebas dipilih apakah ingin menggunakan iterasi dengan kriteria primal atau dual. Akan digunakan kriteria dual terlebih dahulu dan selanjutnya secara bergantian akan digunakan kriteria primal hingga mencapai kondisi yang optimum.
MS - 88
Iterasi I Pada kriteria dual langkah awal adalah mencari baris pivot dengan nilai ruas kanan (kolom solusi) yang paling negatif. Selanjutnya akan dicari kolom pivot dengan melihat rasio antara elemen pada baris 𝑍 yang bernilai positif dengan nilai mutlak elemen pada baris pivot. Solusi 𝑋1 𝑋2 𝑍 −3 −4 0 -2 𝑆1 −1 −2 𝑆2 −3 −1 −4 𝑆3 1 −1 1 𝑆4 1 1 8 Rasio − 4 − Selanjutnya, tukar posisi 𝑆2 dan 𝑋2 sebagai pertukaran antara variabel dasar dengan variabel bukan dasar. Setelah itu, akan ditentukan elemen pivot yang baru yaitu 1/(elemen pivot lama). Pada baris yang memuat elemen pivot, nilainya dikalikan dengan elemen pivot baru, sedangkan untuk kolom yang memuat elemen pivot, nilainya dikalikan dengan –(elemen pivot baru). Solusi 𝑋1 𝑆2 𝑍 4 𝑆1 2 𝑋2 3 −1 4 𝑆3 1 𝑆4 −1 Untuk pengisian entri yang lain, akan digunakan metode Gauss-Jordan. yaitu: 𝑃𝑒𝑟𝑠𝑎𝑚𝑎𝑎𝑛 𝑏𝑎𝑟𝑢 = 𝑝𝑒𝑟𝑠𝑎𝑚𝑎𝑎𝑛 𝑙𝑎𝑚𝑎 − (𝑘𝑜𝑒𝑓𝑖𝑠𝑖𝑒𝑛 𝑘𝑜𝑙𝑜𝑚 𝑝𝑖𝑣𝑜𝑡 𝑙𝑎𝑚𝑎 × 𝑝𝑒𝑟𝑠𝑎𝑚𝑎𝑎𝑛 𝑏𝑎𝑟𝑢) Sehingga diperoleh tabel baru Solusi 𝑋1 𝑋2 𝑍 −15 4 −16 6 𝑆1 5 2 𝑋2 3 −1 4 𝑆3 −2 1 −1 𝑆4 4 −1 5 Iterasi II Karena solusi dari iterasi I masih belum optimal (baik primal maupun dual), maka iterasi II akan menggunakan kriteria yang berselingan dengan iterasi I yaitu kriteria primal. Langkah awal pada kriteria primal adalah menentukan kolom pivot dengan melihat elemen baris 𝑍 yang bernilai paling negatif. Selanjutnya akan dicari baris pivot dengan melihat rasio antara elemen pada ruas kanan (kolom solusi) yang bernilai positif dengan nilai mutlak elemen pada kolom pivot. Solusi Rasio 𝑋1 𝑆2 𝑍 −15 4 −16 − 𝑆1 5 2 6 6/5 𝑋2 3 −1 4 4/3 𝑆3 −2 1 −1 − 𝑆4 4 −1 5 5/4 Selanjutnya, tukar posisi 𝑆1 dan 𝑋1 sebagai pertukaran antara variabel dasar dengan variabel bukan dasar. Untuk pengisian entri baru, baik elemen pivot maupun yang lain, akan digunakan aturan yang sama dengan iterasi I sehingga diperoleh tabel baru Solusi 𝑆1 𝑆2 𝑍 3 −2 2 𝑋1 1/5 −2/5 6/5 MS - 89
𝑋2 𝑆3 𝑆4
−3/5 2/5 −4/5
1/5 1/5 3/5
2/5 7/5 1/5
Iterasi III Pada iterasi II seluruh ruas kanan kendala sudah bernilai positif, namun pada baris 𝑍 masih ada yang bernilai negatif sehingga akan dilanjutkan kembali iterasi dengan menggunakan kriteria primal. Dengan cara yang sama seperti iterasi II, dapat diperoleh baris dan kolom pivotnya sebagai berikut Solusi Rasio 𝑆1 𝑆2 𝑍 3 −2 2 − 𝑋1 1/5 −2/5 6/5 3 𝑋2 −3/5 1/5 2/5 2 𝑆3 2/5 1/5 7/5 7 𝑆4 −4/5 3/5 1/5 1/3 Selanjutnya, tukar posisi 𝑆4 dan 𝑆2 sebagai pertukaran antara variabel dasar dengan variabel bukan dasar. Untuk pengisian entri baru, baik elemen pivot maupun yang lain, akan digunakan aturan yang sama dengan iterasi I sehingga diperoleh tabel baru Solusi 𝑆1 𝑆4 10/3 𝑍 1/3 8/3 𝑋1 −1/3 2/3 4/3 𝑋2 −1/3 −1/3 1/3 𝑆3 2/3 −1/3 1/3 𝑆4 −4/3 5/3 1/3 Pada iterasi III telah diperoleh tabel optimal, sehingga solusi optimal dari masalah 1 1 2 tersebut yaitu 𝑋1 = 1 3 dan 𝑋2 = 3 dengan nilai optimal fungsi objektifnya 𝑍 = 2 3 .
3. PENYEDERHANAAN MODEL LFP Berikut ini akan dipaparkan metode dari Charnes dan Cooper [3] dalam mengubah kasus LFP menjadi LP. Misal diberikan masalah LFP sebagai berikut: Fungsi objektif : (maksimum atau minimum) 𝑎 𝑋 +⋯+𝑎 𝑋 +𝑎 𝑍 = 𝑐1 𝑋1 +⋯+𝑐 𝑛𝑋𝑛+𝑐 𝑛+1 1 1
dengan fungsi kendala :
𝑛 𝑛
(1)
𝑛+1
𝑛
∑ 𝐴𝑖𝑗 𝑋𝑗 ≤ 𝑏𝑖 𝑗=1
untuk 𝑖 = 1,2, … , 𝑚, dan syarat tak negatif : 𝑋𝑗 ≥ 0 ; untuk 𝑗 = 1,2, …,n Misal 𝑐1 𝑋1 + ⋯ + 𝑐𝑛 𝑋𝑛 + 𝑐𝑛+1 > 0 dan = 𝑐
1
1 𝑋1 +⋯+𝑐𝑛 𝑋𝑛 +𝑐𝑛+1
, kemudian disubtitusikan ke
persamaan (1), maka diperoleh : Fungsi objektif : (maksimum atau minimum) 𝑍 = 𝑎1 𝑋1 𝑊 + ⋯ + 𝑎𝑛 𝑋𝑛 𝑊 + 𝑎𝑛+1 𝑊 dengan fungsi kendala : 𝑐1 𝑋1 𝑊 + ⋯ + 𝑐𝑛 𝑋𝑛 𝑊 + 𝑐𝑛+1 𝑊 = 1 𝑛
∑ 𝐴𝑖𝑗 𝑋𝑗 𝑊 − 𝑏𝑖 𝑊 ≤ 0 𝑗=1
untuk 𝑖 = 1,2, … , 𝑚 dan syarat tak negatif : 𝑊 ≥ 0; 𝑋𝑗 ≥ 0; untuk 𝑗 = 1,2, … , 𝑛 MS - 90
(2)
Dengan memisalkan 𝑌𝑗 = 𝑋𝑗 𝑊 untuk 𝑗 = 1,2, … , 𝑛, maka persamaan (2) menjadi : Fungsi objektif : (maksimum atau minimum) 𝑍 = 𝑎1 𝑌1 + ⋯ + 𝑎𝑛 𝑌𝑛 + 𝑎𝑛+1 𝑊 dengan fungsi kendala : 𝑐1 𝑌1 + ⋯ + 𝑐𝑛 𝑌𝑛 + 𝑐𝑛+1 𝑊 = 1
(3)
𝑛
∑ 𝐴𝑖𝑗 𝑌𝑗 − 𝑏𝑖 𝑊 ≤ 0 𝑗=1
untuk 𝑖 = 1,2, … , 𝑚 dan syarat tak negatif : 𝑊 ≥ 0; 𝑌𝑗 ≥ 0; untuk 𝑗 = 1,2, … , 𝑛 Dengan hasil yang didapatkan pada persamaan (3) berupa masalah LP, masalah tersebut akan diselesaikan menggunakan metode simpleks dan pada bagian selanjutnya akan diselesaikan dengan menggunakan metode Criss Cross. 4. PENYELESAIAN LFP DENGAN METODE SIMPLEKS Berikut adalah contoh kasus LFP [4] yang akan diselesaikan dengan menggunakan metode simpleks. 10𝑋 + 20𝑋2 +10 Maksimumkan 𝑍 = 3X1+ 4X +20 1
2
dengan kendala : 𝑋1 + 3𝑋2 ≤ 50 3𝑋1 + 2𝑋2 ≤ 80
dan 𝑋1 , 𝑋2 ≥ 0.
Solusi: Penyederhanaan bentuk LFP menjadi LP. 1 Misal 𝑊 = 3X + 4X +20, maka fungsi objektifnya menjadi : 1
2
Maksimumkan 𝑍 = 10𝑋1 𝑊 + 20𝑋2 𝑊 + 10𝑊 dengan kendala : 3X1 W + 4X 2 W + 20W = 1 𝑋1 𝑊 + 3𝑋2 𝑊 − 50𝑊 ≤ 0 3𝑋1 𝑊 + 2𝑋2 𝑊 − 80𝑊 ≤ 0 dan 𝑊, 𝑋1 , 𝑋2 ≥ 0. Kemudian, misalkan kembali 𝑌𝑗 = 𝑋𝑗 𝑊 (𝑗 = 1,2), maka fungsi objektifnya: Maksimumkan 𝑍 = 10𝑌1 + 20𝑌2 + 10𝑊 dengan kendala : 3Y1 + 4Y2 + 20W = 1 𝑌1 + 3𝑌2 − 50𝑊 ≤ 0 3𝑌1 + 2𝑌2 − 80𝑊 ≤ 0 dan 𝑊, 𝑌1 , 𝑌2 ≥ 0.
Penyelesaian masalah LP. Karena kendala awal pada permasalahan di atas berupa persamaan, untuk penyelesaiannya akan digunakan metode dua fase sehingga solusi optimal dari masalah tersebut 5 3 2 yaitu 𝑌1 = 0, 𝑌2 = 26, dan 𝑊 = 260 atau 𝑋1 = 0 dan 𝑋2 = 16 3 dengan nilai optimal 25
fungsi objektifnya 𝑍 = 3 26 . 5. PENYELESAIAN LFP DENGAN METODE CRISS CROSS Akan digunakan kembali contoh dari masalah LFP sebelumnya yang sudah disederhanakan menjadi masalah LP. Maksimumkan 𝑍 = 10𝑌1 + 20𝑌2 + 10𝑊 dengan kendala : MS - 91
dan 𝑊, 𝑌1 , 𝑌2 ≥ 0.
3Y1 + 4Y2 + 20W = 1 𝑌1 + 3𝑌2 − 50𝑊 ≤ 0 3𝑌1 + 2𝑌2 − 80𝑊 ≤ 0
Solusi : Mengubah kendala permasalahan LP menjadi bentuk pertidaksamaan ≤ menjadi : 3Y1 + 4Y2 + 20W ≤ 1 −3Y1 − 4Y2 − 20W ≤ −1 𝑌1 + 3𝑌2 − 50𝑊 ≤ 0 3𝑌1 + 2𝑌2 − 80𝑊 ≤ 0 Tabel awal permasalahan di atas : Solusi 𝑌1 𝑌2 𝑊 𝑍 −10 −20 −10 0 𝑆1 3 4 20 1 𝑆2 −3 −4 −20 −1 𝑆3 1 3 −50 0 𝑆4 3 2 −80 0 Iterasi I Pada iterasi I akan digunakan kriteria primal terlebih dahulu dalam pemilihan baris dan kolom pivotnya sebagai berikut Solusi Rasio 𝑌1 𝑌2 𝑊 𝑍 −20 0 1/4 𝑆1 3 4 20 1 𝑆2 −4 −1 𝑆3 3 0 𝑆4 2 0 Selanjutnya tukar posisi 𝑆1 dan 𝑌2 sebagai pertukaran variabel dasar dan variabel bukan dasar. Untuk pengsian entri baru, baik elemen pivot maupun yang lain, akan digunakan aturan sesuai dengan metode Criss Cross sehingga diperoleh tabel iterasi I sebagai berikut Solusi 𝑌1 𝑆1 𝑊 90 𝑍 5 5 5 𝑌2 3/4 1/4 5 1/4 0 0 𝑆2 1 0 𝑆3 −5/4 −3/4 −65 −3/4 𝑆4 6/4 −1/2 −90 −1/2 Iterasi II Pada iterasi II akan digunakan kriteria dual dalam pemilihan baris dan kolom pivotnya sebagai berikut Solusi 𝑌1 𝑆1 𝑊 90 𝑍 𝑌2 5 0 𝑆2 𝑆3 −5/4 −3/4 −65 −3/4 𝑆4 −90 Rasio 4 20/3 90/65 − Selanjutnya tukar posisi 𝑆3 dan 𝑊 sebagai pertukaran variabel dasar dan variabel bukan dasar. Untuk pengsian entri baru, baik elemen pivot maupun yang lain, akan digunakan aturan sesuai dengan metode Criss Cross sehingga diperoleh tabel iterasi II sebagai berikut MS - 92
Solusi 𝑌1 𝑆1 𝑆3 18/13 𝑍 85/26 103/26 103/26 𝑌2 17/26 5/26 1/13 5/26 0 𝑆2 0 1 0 W 1/52 3/260 −1/65 3/260 𝑆4 42/13 7/13 −90 7/13 Pada iterasi II telah diperoleh tabel optimal, sehingga solusi optimal dari masalah 5 3 2 tersebut yaitu 𝑌1 = 0, 𝑌2 = 26, dan 𝑊 = 260 atau 𝑋1 = 0 dan 𝑋2 = 16 3 dengan nilai 25
optimal fungsi objektifnya 𝑍 = 3 26 . 6. KESIMPULAN Dari pembahasan pada makalah ini, diperoleh kesimpulan sebagai berikut: Metode Criss Cross merupakan kombinasi kriteria primal dan dual dalam mencari solusi optimum dari suatu permasalahan LP atau LFP. Metode Criss Cross merupakan salah satu metode alternatif dalam menyelesaikan masalah,baik LP maupun LFP, selain dengan menggunakan metode simpleks. Metode Criss Cross dapat menghindari penggunaan variabel buatan dalam mencari solusi dari masalah yang ada, sehingga penggunaan metode ini lebih sederhana dibandingkan dengan menggunakan metode simpleks, khususnya metode dua fase.
DAFTAR PUSTAKA [1] Zionts, S. (1969). “The Criss Cross Method For Solving Linear Programming Problems,” Management Science. Vol. 15, no. 7. Pg. 426–445. [2] Taha, H. A. (2007). Operations Research: An Introduction - 8th ed. Pearson Education, Inc. Upper Saddle River, New Jersey. [3] Charnes, A. dan Cooper, W. (1962). “Programming with linear fractional functions,” Naval Research Logistics Quarterly, Vol. 9. Pg. 181–186. [4] Hillier, F. S. dan Lieberman, G. J. (2001). Introduction to Operations Research - 9th ed. McGraw-Hill. New York.
MS - 93
Alamat Redaksi:Jurusan Matematika, FTIS - UNPARGedung 9, Lantai 1Jl. Ciumbule