PERBANDINGAN WAKTU EKSEKUSI METODE SIMPLEKS DAN METODE TITIK INTERIOR DALAM MENYELESAIKAN MASALAH OPTIMASI LINEAR MENGGUNAKAN MATHEMATICA

PERBANDINGAN WAKTU EKSEKUSI METODE SIMPLEKS DAN METODE TITIK INTERIOR DALAM MENYELESAIKAN MASALAH OPTIMASI LINEAR MENGGUNAKAN MATHEMATICA

ROCHMAT FERRY SANTO

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014

PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Perbandingan Waktu Eksekusi Metode Simpleks dan Metode Titik Interior dalam Menyelesaikan Masalah Optimasi Linear Menggunakan Mathematica adalah benar karya saya dengan arahan dari komisi pembimbing dan belum diajukan dalam bentuk apa pun kepada perguruan tinggi mana pun. Sumber informasi yang berasal atau dikutip dari karya yang diterbitkan maupun tidak diterbitkan dari penulis lain telah disebutkan dalam teks dan dicantumkan dalam Daftar Pustaka di bagian akhir disertasi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Mei 2014 Rochmat Ferry Santo NIM G54090063

ABSTRAK ROCHMAT FERRY SANTO. Perbandingan Waktu Eksekusi Metode Simpleks dan Metode Titik Interior dalam Menyelesaikan Masalah Optimasi Linear Menggunakan Mathematica. Dibimbing oleh BIB PARUHUM SILALAHI dan PRAPTO TRI SUPRIYO. Terdapat dua metode yang umum digunakan untuk menyelesaikan masalah optimasi linear, yaitu metode simpleks dan metode titik interior. Pada metode simpleks untuk mencari solusi optimal, algoritme berpindah dari verteks ke verteks. Sementara itu pada metode titik interior, algoritme bergerak di dalam interior daerah fisibel dari masalah optimasi linear. Pada karya ilmiah ini, dilakukan perbandingan waktu eksekusi metode simpleks dan metode titik interior dalam menyelesaikan masalah optimasi linear dengan menggunakan sebuah perangkat lunak matematika, yaitu Mathematica. Ukuran dari masalah optimasi linear dipilih bervariasi dari ukuran yang relatif kecil ke ukuran yang relatif besar. Hasil utama yang diperoleh adalah metode titik interior lebih cepat dibandingkan metode simpleks untuk masalah-masalah optimasi linear yang berukuran besar. Kata kunci: metode simpleks, metode titik interior, optimasi linear, waktu eksekusi

ABSTRACT ROCHMAT FERRY SANTO. Execution Time Comparation Between Simplex Method and Interior Point Method in Solving Linear Optimization Problems Using Mathematica. Supervised by BIB PARUHUM SILALAHI and PRAPTO TRI SUPRIYO. There are two famous methods for solving linear optimization problems, namely simplex method and interior point method. In the simplex method, to find an optimal solution, the algorithm moves from vertex to vertex. While in the interior point method, the algorithm moves in the interior of the feasible region of the problem. In this paper we compare the execution time of the simplex method and the interior point method in solving several linear optimization problems by using a mathematical software, that is Mathematica. The size of problems are chosen from small to relatively big. The main result is that the interior point method is faster than the simplex method for big size problems. Keywords: simplex method, interior point method, linear optimization, execution time

PERBANDINGAN WAKTU EKSEKUSI METODE SIMPLEKS DAN METODE TITIK INTERIOR DALAM MENYELESAIKAN MASALAH OPTIMASI LINEAR MENGGUNAKAN MATHEMATICA

ROCHMAT FERRY SANTO

Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika

DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2014

Judul Skripsi : Perbandingan Waktu Eksekusi Metode Simpleks dan Metode Titik Interior dalam Menyelesaikan Masalah Optimasi Linear Menggunakan Mathematica Nama : Rochmat Ferry Santo NIM : G54090063

Disetujui oleh

Dr Ir Bib Paruhum Silalahi, MKom Pembimbing I

Drs Prapto Tri Supriyo, MKom Pembimbing II

Diketahui oleh

Dr Toni Bakhtiar, MSc Ketua Departemen

Tanggal Lulus:

PRAKATA Puji dan syukur penulis panjatkan kepada Allah subhanahu wa ta’ala atas segala karunia-Nya sehingga karya ilmiah ini berhasil diselesaikan. Tema yang dipilih dalam penelitian yang dilaksanakan sejak bulan Februari 2013 ini ialah optimasi linear, dengan judul Perbandingan Waktu Eksekusi Metode Simpleks dan Metode Titik Interior dalam Menyelesaikan Masalah Optimasi Linear Menggunakan Mathematica. Terima kasih penulis ucapkan kepada Bapak Dr Ir Bib Paruhum Silalahi, MKom dan Bapak Drs Prapto Tri Supriyo, MKom selaku pembimbing, serta Bapak Ir Ngakan Komang Kutha Ardana, MSc yang telah banyak memberi saran, motivasi, dan bimbingan dalam penulisan karya ilmiah ini, serta kepada seluruh staf Departemen Matematika. Ungkapan terima kasih dan penghargaan disampaikan kepada Papah, Mamah, Pa Raden, Mamah Ray, serta seluruh keluarga, atas segala doa dan kasih sayangnya. Di samping itu, ucapan terima kasih juga penulis berikan kepada Syukrio Idaman, Rudy Hariono, Qowiyyul Siregar, Hidayattul Kamil, seluruh mahasiswa Departemen Matematika Angkatan 45, 46, 47, dan 48 serta teman-teman sekalian di luar Departemen Matematika baik di dalam Institut Pertanian Bogor maupun di luar Institut Pertanian Bogor atas kritik, saran dan doanya selama pembuatan karya ilmiah ini. Penulis menyadari bahwa dalam kaya ilmiah ini masih jauh dari kesempurnaan. Kritik dan saran berupa masukan yang bersifat membangun sangat diharapkan penulis demi penyempurnaan di masa mendatang. Semoga karya ilmiah ini dapat memberikan informasi yang bermanfaat bagi pembaca. Semoga karya ilmiah ini bermanfaat.

Bogor, Mei 2014 Rochmat Ferry Santo

DAFTAR ISI DAFTAR TABEL

vi

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vi

PENDAHULUAN

1

Latar Belakang

1

Tujuan Penelitian

1

TINJAUAN PUSTAKA

2

Optimasi Linear

2

Bentuk Standar Primal dan Bentuk Standar Dual

2

Metode Pengali Lagrange

3

Metode Newton

3

Wolfram Mathematica

4

HASIL DAN PEMBAHASAN Metode Simpleks

5 5

Metode Titik Interior

10

Studi Kasus

16

SIMPULAN

22

DAFTAR PUSTAKA

22

LAMPIRAN

24

RIWAYAT HIDUP

41

DAFTAR TABEL 1 2 3 4

Ilustrasi tabulasi simpleks Tabulasi simpleks Tabulasi simpleks kolom kunci dan baris kunci Waktu eksekusi metode simpleks dan metode titik interior dengan lima kali pengulangan 5 Waktu eksekusi rata-rata metode simpleks dan metode titik interior serta perbandingan waktu eksekusi metode simpleks : metode titik interior

8 9 10 19

21

DAFTAR GAMBAR 1 Perbandingan waktu eksekusi metode simpleks : metode titik interior

21

DAFTAR LAMPIRAN 1 2 3 4 5 6 7

Studi kasus 4 masalah OL dengan 50 kendala dan 50 variabel Studi kasus 5 masalah OL dengan 100 kendala dan 100 variabel Studi kasus 6 masalah OL dengan 100 kendala dan 200 variabel Studi kasus 7 masalah OL dengan 200 kendala dan 200 variabel Studi kasus 8 masalah OL dengan 500 kendala dan 500 variabel Studi kasus 9 masalah OL dengan 500 kendala dan 1000 variabel Studi kasus 10 masalah OL dengan 100 kendala dan 200000 variabel

24 25 27 29 31 35 40

PENDAHULUAN Latar Belakang Optimasi adalah bagian dari matematika terapan yang mempelajari masalahmasalah dengan tujuan mencari nilai minimum atau maksimum suatu fungsi terhadap kendala-kendala yang ada. Optimasi dalam matematika mengacu pada pemilihan elemen terbaik dari beberapa himpunan alternatif yang tersedia. Bagian dari optimasi adalah optimasi linear (linear optimization) di mana fungsi tujuan dinyatakan dalam fungsi linear dan kendala-kendala dinyatakan dalam bentuk persamaan/pertidaksamaan linear. Optimasi Linear (OL) muncul menjadi model matematika setelah perang dunia ke-2, yaitu ketika Dantzig memaparkan metode simpleks untuk menyelesaikan masalah optimasi linear. Untuk memperoleh solusi optimal, metode simpleks bergerak dari verteks ke verteks. Metode ini dirancang sedemikian rupa yang dalam pergerakannya dari satu verteks ke verteks, nilai fungsi tujuan berubah secara monoton menuju nilai optimal. Terobosan yang sangat efektif untuk menyelesaikan masalah OL terjadi pada tahun 1984, ketika Karmarkar mengusulkan menggunakan metode titik interior untuk menyelesaikan masalah OL dan memulai revolusi dalam bidang optimasi. Tidak seperti metode simpleks yang bergerak dari verteks ke verteks, metode titik interior bergerak di dalam interior dari domain secara monoton menuju solusi optimal (Silalahi 2011). Setelah periode 1960-an dengan digunakannya komputer, optimasi linear tersebut dapat diformulasikan dalam perangkat lunak komputer yang menjadikan optimasi linear sebagai alat canggih dalam optimasi untuk memperoleh keputusan-keputusan yang optimum dengan cepat dan tepat. Perangkat lunak komputasi yang dapat digunakan untuk menyelesaikan optimasi linear dalam sistem persamaan linear antara lain Mathematica, Matlab, Maple, dan Mathcad.

Tujuan Penelitian Penulisan karya ilmiah ini bertujuan untuk menunjukkan perbandingan waktu eksekusi antara metode simpleks dan metode titik interior dalam menyelesaikan masalah optimasi linear (OL) yang dilakukan terhadap beberapa studi kasus permasalahan optimasi linear yang bervariasi dengan memuat fungsi tujuan dan kendala yang dimulai dari ukuran sederhana sampai berukuran besar, dengan menggunakan perangkat lunak Mathematica.

TINJAUAN PUSTAKA Optimasi Linear Optimasi linear adalah proses untuk mendapatkan hasil yang optimum. Model optimasi linear (OL) meliputi pengoptimuman suatu fungsi linear terhadap kendala linear (Nash dan Sofer 1996). Optimasi linear khusus mempelajari hal-hal yang berkaitan dengan meminimumkan atau memaksimumkan fungsi-fungsi linear, dengan kendala yang juga berbentuk linear (berupa persamaan atau pertidaksamaan). Dikatakan sebuah fungsi linear, jika suatu fungsi f dalam variabel-variabel 𝑥1 , 𝑥2 , … , 𝑥𝑛 adalah suatu fungsi linear jika dan hanya jika untuk suatu himpunan konstanta 𝑐1 , 𝑐2 , … , 𝑐𝑛 , fungsi f dapat ditulis sebagai 𝑓( 𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑐1 𝑥1 + 𝑐2 𝑥2 + … + 𝑐𝑛 𝑥𝑛 = 𝑏 (Winston 2004). Misalkan contoh sebagai berikut: 𝑓( 𝑥1 , 𝑥2 , 𝑥3 ) = 2𝑥1 + 𝑥2 + 𝑥3 merupakan fungsi linear, 𝑓( 𝑥1 , 𝑥2 ) = 𝑥1 2 + 𝑥2 bukan fungsi linear. Suatu persamaan linear dalam n variabel adalah persamaan untuk sembarang fungsi linear f dan sembarang bilangan b persamaan 𝑓( 𝑥1 , 𝑥2 , … , 𝑥𝑛 ) = 𝑏 merupakan persamaan linear. Untuk sembarang fungsi linear f dan sembarang bilangan b suatu pertidaksamaan 𝑓( 𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ≤ 𝑏 dan 𝑓( 𝑥1 , 𝑥2 , … , 𝑥𝑛 ) ≥ 𝑏 adalah pertidaksamaan linear. Suatu optimasi linear dikatakan berbentuk standar jika dapat ditulis sebagai berikut: minimumkan/maksimumkan: z = cTx terhadap 𝐴𝐱 = 𝐛, x ≥ 0, dengan x dan c berupa vektor berukuran 𝑛 × 1 , vektor b berukuran 𝑚 × 1 , sedangkan 𝐴 berupa matriks berukuran m × n, yang disebut juga sebagai matriks kendala (Nash & Sofer 1996). Dalam masalah maksimisasi, solusi optimal pada optimasi linear adalah suatu titik pada daerah fisibel dengan nilai fungsi objektif paling besar. Untuk minimisasi, solusi optimal suatu optimasi linear adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil (Winston 2004). Daerah fisibel suatu optimasi linear adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada optimasi linear tersebut (Winston 2004). P

Bentuk Standar Primal dan Bentuk Standar Dual Masalah optimasi linear dalam bentuk standar diberikan sebagai berikut: {𝐜 𝑇 𝐱 ∶ 𝐴𝐱 = 𝐛, 𝐱 ≥ 𝟎} min (𝑃) dengan vektor 𝐜, 𝐱 ∈ ℝ𝑛 , 𝐛 ∈ ℝ𝑚 , serta 𝐴 ∈ ℝ𝑚×𝑛 adalah matriks berpangkat baris penuh. Masalah (𝑃) disebut masalah primal. Masalah dual dari masalah primal (𝑃) diberikan sebagai berikut: maks {𝐛𝑇 𝐲 ∶ 𝐴𝑇 𝐲 + 𝐬 = 𝐜, 𝐬 ≥ 𝟎} (𝐷) dengan 𝐬 ∈ ℝ𝑛 dan 𝐲 ∈ ℝ𝑚 . Masalah (𝐷) disebut masalah dual. Daerah fisibel dari masalah (𝑃) didefinisikan sebagai berikut: 𝒫 ={𝐱 ∶ 𝐴𝐱 = 𝐛, 𝐱 ≥ 𝟎}

3 sedangkan daerah fisibel dari (𝐷) didefinisikan sebagai berikut: 𝒟 = {(𝐲, 𝐬): 𝐴𝑇 𝐲 + 𝐬 = 𝐜, 𝐬 ≥ 𝟎}. Daerah interior masalah (𝑃) didefinisikan sebagai berikut: 𝒫 0 ={𝐱 ∶ 𝐴𝐱 = 𝐛, 𝐱 > 𝟎} sedangkan daerah interior dari masalah (𝐷) didefinisikan sebagai berikut: 𝒟 0 = {(𝐲, 𝐬): 𝐴𝑇 𝐲 + 𝐬 = 𝐜, 𝐬 > 𝟎} (Silalahi 2011). Metode Pengali Lagrange Metode pengali Lagrange adalah suatu prosedur untuk menentukan minimum atau maksimum fungsi objektif terhadap kendala persamaan. Misalkan diberikan masalah pengoptimuman sebagai berikut: maks 𝑓(𝐱) terhadap 𝑔𝑖 (𝐱) = 0, 𝑖 = 1, … , 𝑚 dengan 𝑓(𝐱) dan 𝑔𝑖 (𝐱) adalah fungsi dari vektor 𝐱 berukuran 𝑛. Fungsi Lagrange dari masalah ini ialah 𝑛

𝐿(𝐱, 𝛑) = 𝑓(𝐱) − � 𝜋𝑖 𝑔𝑖 (𝐱) 𝑗=1

dengan variabel 𝛑 = (𝜋1 , 𝜋2 , … , 𝜋𝑚 ) adalah pengali Lagrange. Syarat perlu untuk titik stasioner dari 𝑓(𝐱) adalah turunan parsial pertama dari fungsi Lagrange sama dengan nol 𝜕𝐿 = 0, 𝑖 = 1, … , 𝑛 𝜕𝑥𝑗 𝜕𝐿 = 0, 𝑗 = 1, … , 𝑚 𝜕𝜋𝑖 (Jensen & Bard 2002). Metode Newton Metode Newton adalah salah satu prosedur iteratif untuk menyelesaikan masalah taklinear. Misalkan persamaan 𝑓(𝑦) = 0 adalah persamaan taklinear dengan 𝑦 merupakan penyelesaian dari persamaan tersebut. Fungsi 𝑓 adalah fungsi yang kontinu dan terturunkan. Pada solusi eksak 𝑦 ∗ , nilai fungsi dapat dinyatakan sebagai 𝑓(𝑦 𝑘 ) dan nilai dari fungsi turunan pertama adalah 𝑓′(𝑦 𝑘 ). Nilai 𝑦 𝑘 adalah solusi 𝑦 yang diperoleh pada iterasi ke-𝑘. Misalkan 𝑧 = 𝑓(𝑦), turunan dapat diartikan sebagai laju perubahan 𝑧 terhadap 𝑦. Andaikan 𝑦 berubah dari 𝑦 𝑘 ke 𝑦 𝑘+1 maka perubahan pada 𝑦 adalah ∆= 𝑦 𝑘+1 − 𝑦 𝑘 . Perubahan ∆ ini diperlukan untuk mengubah nilai fungsi 𝑓 menuju nol. Selanjutnya, metode Newton dapat diturunkan dari ekspansi deret Taylor orde pertama dari 𝑓(𝑦) di sekitar 𝑦 𝑘 , sebagai berikut: 𝑓′(𝑦 𝑘 ) 𝑓(𝑦 𝑘+1 ) ≈ 𝑓(𝑦 𝑘 ) + (𝑦 𝑘+1 − 𝑦 𝑘 ) 1! sehingga

4 𝑓(𝑦 𝑘+1 ) ≈ 𝑓(𝑦 𝑘 ) + ∆𝑓 ′ (𝑦 𝑘 ). Tetapkan pendekatan 𝑓(𝑦 𝑘+1 ) sama dengan 0 sehingga didapat −𝑓(𝑦 𝑘 ) ∆= ′ 𝑘 . 𝑓 (𝑦 ) 𝑘+1 𝑘 Titik 𝑦 = 𝑦 + ∆ adalah solusi pendekatan fungsi 𝑓(𝑦) . Jika titik awal 𝑦 0 cukup dekat dengan 𝑦 ∗ maka nilai dari 𝑦 𝑘 akan mendekati 𝑦 ∗ dengan 𝑘 → ∞. Metode Newton dapat juga digunakan untuk mengubah bentuk suatu fungsi taklinear menjadi bentuk fungsi linear dari fungsi multivariabel. Misalkan persamaan 𝑓(𝐲) = 0 adalah persamaan taklinear dengan vektor 𝐲 ∗ dari persamaan multivariabel tersebut dan matriks Jacobi J pada 𝐲 𝑘 dinyatakan sebagai berikut: 𝜕𝑓1 𝜕𝑓1 𝜕𝑓1 ⋯ 𝜕𝑦𝑛 ⎞ ⎛𝜕𝑦1 𝜕𝑦2 𝜕𝑓2 ⎟ ⎜ 𝜕𝑓2 𝜕𝑓2 𝐽(𝐲 𝑘 ) = ⎜𝜕𝑦1 𝜕𝑦2 ⋯ 𝜕𝑦𝑛 ⎟ ⎜ ⎟ ⋮ ⋱ ⋮ ⎟ ⎜ ⋮ 𝜕𝑓𝑛 𝜕𝑓𝑛 𝜕𝑓𝑛 ⋯ 𝜕𝑦𝑛 ⎠ ⎝𝜕𝑦1 𝜕𝑦2 kemudian dengan menggunakan deret Taylor orde pertama di sekitar titik 𝐲 𝑘 dan dengan menetapkan 𝑓(𝐲 𝑘+1 ) = 0 diperoleh 𝑓(𝐲 𝑘+1 ) = 𝑓(𝐲 𝑘 ) + 𝐽(𝐲 𝑘 )𝐝 = 0 𝑓(𝐲 𝑘 ) + 𝐽(𝐲 𝑘 )𝐝 = 0 dengan 𝐝 = 𝐲 𝑘+1 − 𝐲 𝑘 dan 𝑘 = 0,1,2, … , 𝑛 . Titik 𝐲 𝑘+1 = 𝐲 𝑘 + 𝐝 adalah solusi pendekatan fungsi 𝑓(𝐲). Jika titik 𝐲 0 cukup dekat dengan titik 𝐲 ∗ maka nilai dari 𝐲 𝑘 akan mendekati 𝐲 ∗ dengan 𝑘 → ∞ (Jensen & Bard 2002). Wolfram Mathematica Mathematica merupakan suatu sistem aljabar komputer (CSA, Computer Algebra System) yang mengintegrasikan kemampuan komputasi (simbolik, numerik), visualisasi (grafik), bahasa pemrograman, dan pengolahan kata (word processing) ke dalam suatu lingkungan yang mudah digunakan (Ardana 2002). Mathematica pertama kali diperkenalkan pada tahun 1988. Pada saat ini Mathematica merupakan salah satu aplikasi pilihan dalam pendidikan dan penelitian, khususnya untuk melakukan komputasi matematik baik simbolik maupun numerik, pengembangan algoritme dan aplikasi, pemodelan dan simulasi, serta eksplorasi, analisis, dan visualisasi data. Mathematica merupakan program aplikasi Wolfarm Research yang handal dengan fasilitas terintegrasi lengkap untuk menyelesaikan beragam masalah matematika yang meliputi komputasi numerik, simbolik, dan visualisasi grafik. Mathematica dapat menyelesaikan beragam kasus komputasi matematika, mulai dari komputasi yang paling sederhana hingga yang paling rumit dapat diselesaikan dengan mudah, ringkas, cepat, dan tepat. Mathematica memiliki fasilitas fungsi (built in Mathematics functions) yang menjadikan sintaks programnya dapat dinyatakan dalam satu atau beberapa baris sederhana . Dilengkapi dengan fasilitas terintegrasi Mathematica mampu mengerjakan beragam perhitungan matematika, salah satunya adalah menyelesaikan masalah

5 optimasi linear (linear optimization). Mathematica dapat dengan mudah menyelesaikan masalah optimasi linear untuk mencari nilai optimum dari suatu fungsi objektif dan kedala yang berbentuk linear dalam masalah optimasi linear yang berkaitan dengan meminimumkan atau memaksimumkan. Mathematica mempunyai beragam algoritme untuk menyelesaikan suatu masalah optimasi dengan variabel real yang dapat diformulasikan dalam bentuk fungsi Mathematica, seperti: LinearProgramming, FindMinimum, FindMaximum, Nminimize, Nmaximize, dan Maximize. Sintaks LinearProgramming memberikan perintah untuk mengakses ke penyelesaian optimasi linear, dengan sangat mudah menyesuaikan untuk menentukan berbagai metode yang akan digunakan, dan sangat efisien untuk menyelesaikan masalah optimasi linear yang berukuran besar. Bentuk umum untuk optimasi linear pada Mathematica, yaitu: 1.

LinearProgramming[c, m, b]

Implementasi dari sintaks di atas ialah untuk menemukan suatu nilai vektor x yang meminimumkan jumlah nilai 𝐜𝐱 pada fungsi objektif, dengan kendala 𝑚𝐱 ≥ 𝐛 dan 𝐱 ≥ 𝟎. Di mana c adalah konstanta dari fungsi objektif, m adalah konstanta (nilai ruas kiri) dalam kendala, dan b adalah nilai dari suatu kendala (nilai ruas kanan). 2. LinearProgramming[c, m, {{𝑏1 , 𝑠1 }, {𝑏2 , 𝑠2 },……}] Implementasi dari sintaks di atas ialah untuk menemukan nilai vektor x yang meminimumkan fungsi objektif 𝐜𝐱 dengan kendala 𝑚𝐱 ≥ 𝐛 untuk 𝐱 ≥ 𝟎 , dan kendala berupa linear dengan matriks m yang berpasangan {𝑏𝑖 , 𝑠𝑖 }. Untuk setiap baris 𝑚𝑖 dari m, sesuai dengan kendala jika 𝑚𝑖 𝐱 ≥ 𝑏𝑖 maka 𝑠𝑖 == 1 , atau jika 𝑚𝑖 𝐱 == 𝑏𝑖 maka 𝑠𝑖 == 0 , atau jika 𝑚𝑖 𝐱 ≤ 𝑏𝑖 maka 𝑠𝑖 == −1. Untuk menyelesaikan optimasi linear yang lebih kompleks pada Mathematica dapat dikerjakan dengan metode yang lebih spesifik, yaitu dengan menggunakan perintah “Simplex”, ”RevisedSimplex”, dan “InteriorPoint”. Secara otomatis Mathematica akan mengerjakan masalah optimasi linear dengan algoritme yang dipilih sesuai pada perintah sintaks dan berdasarkan ukuran masalah dan tingkat ketelitian.

HASIL DAN PEMBAHASAN Penelitian ini membahas perbandingan waktu eksekusi metode simpleks dan metode titik interior dalam menyelesaikan masalah optimasi linear yang dilakukan terhadap beberapa kasus, menggunakan bantuan perangkat lunak Mathematica.

Metode Simpleks Metode simpleks adalah sebuah cara untuk menyelesaikan masalah optimasi linear, dengan melakukan pengulangan pada pengujian titik-titik sudut hingga menemukan penyelesaian optimal (Siswanto 2007). Algoritme simpleks merupakan prosedur berulang, berarti cara yang sama digunakan di dalam

6 pengujian setiap titik sudut hingga ditemukan penyelesaian optimal, yaitu penyelesaian yang memenuhi seluruh kendala dan menghasilkan nilai tujuan. Dalam model optimasi linear, titik sudut adalah perpotongan antara paling sedikit dua garis kendala. Selain membentuk titik sudut, juga akan membentuk sebuah daerah fisibel dengan kemungkinan nilai optimal pada seluruh koordinat yang memenuhi kendala-kendala yang ada. Adapun istilah-istilah yang terdapat dalam algoritme simpleks, yaitu: 1 Variabel Slack Variabel slack adalah variabel basis yang berfungsi untuk menampung sisa kapasitas pada kendala yang berupa pembatas (Siswanto 2007). 2 Variabel Surplus Variabel surplus adalah variabel yang berfungsi untuk menampung kelebihan nilai ruas kiri pada kendala yang berupa syarat (Siswanto 2007). 3 Variabel Artificial Variabel artificial adalah variabel yang bernilai positif, berfungsi untuk memulai penyelesaian dan harus dijadikan nol pada solusi akhir. Variabel ini digunakan untuk setiap persamaan yang tidak memiliki variabel basis. 4 Variabel Basis dan Nonbasis Variabel basis (basic variable) dan variabel nonbasis (nonbasic variable) merupakan dua terminologi penting yang akan selalu digunakan di dalam algoritme simpleks. Variabel basis adalah variabel yang bernilai positif, dan variabel nonbasis adalah variabel yang bernilai nol (Siswanto 2007). Algoritme simpleks memerlukan sebuah tabel simpleks atau yang biasa dikenal dengan tabulasi simpleks pada pengujian suatu titik sudut untuk menentukan apakah variabel keputusan pada titik sudut itu telah menghasilkan nilai tujuan yang optimal. Di dalam tabulasi simpleks menghendaki suatu bangun matematik tertentu agar pengujian titik-titik sudut tersebut bisa dilakukan. Bangun matematik tersebut dikenal sebagai bangun metematik yang sudah tereduksi lengkap, di dalam bangun tersebut terdapat sebuah bangun matriks simetri di mana elemen-elemen diagonalnya bernilai “+1” yang disebut sebagai matriks identitas. Untuk membentuk bangun matematik yang sudah tereduksi lengkap membutuhkan peranan kehadiran variabel slack, variabel surplus, dan variabel artificial. Peranan variabel slack, variabel surplus, dan variabel artificial adalah untuk menampung selisih antara nilai ruas kiri dengan nilai ruas kanan pada kendala yang berbentuk pertidaksamaan sehingga dapat diubah menjadi bentuk persamaan yang sesuai dengan bangun matriks identitas. Bangun matriks identitas adalah syarat agar sebuah model matematis optimasi linear dapat dituangkan ke dalam tabulasi simpleks dan selanjutnya diselesaikan. Selain itu bangun matriks identitas juga akan menandai variabel-variabel basis pada setiap koordinat yang diuji. Variabel Basis pada Tabel Simpleks Seperti yang telah diketahui, algoritme simpleks menghendaki suatu bangun matematik yang tereduksi. Bangun ini kemudian dituangkan ke dalam tabulasi simpleks. Perhatikan bangun matematik optimasi linear yang siap dituangkan ke dalam tabulasi simpleks pada ilustrasi sistem persamaan (1) berikut ini:

7 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 + 1 + 0 + ⋯ + 0 = 𝑏1 , 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 + 0 + 1 + ⋯ + 0 = 𝑏2 , ⋮ 𝑎m1 𝑥1 + 𝑎m2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 + 0 + 0 + ⋯ + 1 = 𝑏m .

(1)

Kendala Pembatasan Membentuk Matriks Identitas Bangun matriks identitas yang ada pada ilustrasi sistem persamaan (1) di atas dapat dibentuk dengan cara menghadirkan variabel slack pada kendala. Pertidaksamaan kendala: 𝑛

diubah menjadi

� 𝑎𝑖𝑗 𝑥𝑗 ≤ 𝑏𝑖 , ∀𝑖 = 1, 2, … , 𝑚 𝑗=1

𝑛

� 𝑎𝑖𝑗 𝑥𝑗 + 𝑠𝑖 = 𝑏𝑖 𝑗=1

di mana, 𝑥𝑗 : variabel keputusan ke-j 𝑎𝑖𝑗 : koefisien kendala ke-i variabel keputusan ke-j 𝑠𝑖 : variabel slack kendala ke-i 𝑏𝑖 : nilai ruas kanan kendala ke-i Bentuk standar kendala yang siap diolah dalam algoritme simpleks tampak seperti ilustrasi sistem persamaan (2) berikut ini: 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 + 𝑠1 + 0 + ⋯ + 0 = 𝑏1 , (2) 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 + 0 + 𝑠1 + ⋯ + 0 = 𝑏2 , ⋮ 𝑎m1 𝑥1 + 𝑎m2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 + 0 + 0 + ⋯ + 𝑠𝑚 = 𝑏m .

Kendala Syarat Membentuk Matriks Identitas Bangun matematik yang memuat matriks identitas seperti pada ilustrasi sistem persamaan (1) dan ilustrasi sistem persamaan (2) tidak mungkin dapat dibentuk secara langsung pada kendala-kendala syarat yang menampung kelebihan nilai ruas kiri, karena karakteristiknya memiliki koefisien “-1” pada variabel surplus. Hal ini akan menyebabkan kendala tidak akan diperhitungkan oleh algoritme simpleks. Karena variabel surplus mempunyai koefisien “-1”, maka kondisi di mana kendala harus mempunyai satu varibel yang memiliki koefisien “+1” menjadi tidak terpenuhi. Oleh karena itu, pada setiap kendala syarat harus ditambahkan sebuah variabel yang berkoefisien “+1” yaitu variabel artificial dengan notasi “ 𝑣𝑖 ” di samping variabel surplus, agar kendala itu memiliki variabel basis sehingga dapat dituangkan ke dalam tabulasi simpleks. Variabel artificial harus bernilai nol di dalam penyelesaian optimal agar kehadirannya tidak mempengaruhi hasil penyelesaian. Pertidaksamaan kendala syarat: 𝑛

diubah menjadi

� 𝑎𝑖𝑗 𝑥𝑗 ≥ 𝑏𝑖 , ∀𝑖 = 1, 2, … , 𝑚 𝑗=1

8 𝑛

� 𝑎𝑖𝑗 𝑥𝑗 − 𝑠𝑖 + 𝑣𝑖 = 𝑏𝑖 𝑗=1

di mana, 𝑥𝑖 : variabel keputusan ke-j 𝑎𝑖𝑗 : koefisien kendala ke-i variabel keputusan ke-j 𝑠𝑖 : variabel surplus kendala ke-i 𝑣𝑖 : variabel artificial kendala ke-i 𝑏𝑖 : nilai ruas kanan kendala ke-i Bentuk standar kendala syarat yang siap diolah oleh algoritme simpleks tampak seperti yang ditampilkan oleh ilustrasi sistem persamaan (3) berikut ini: 𝑎11 𝑥1 + 𝑎12 𝑥2 + ⋯ + 𝑎1𝑛 𝑥𝑛 − 𝑠1 + 𝑣1 + 0 + ⋯ + 0 = 𝑏1 , (3) 𝑎21 𝑥1 + 𝑎22 𝑥2 + ⋯ + 𝑎2𝑛 𝑥𝑛 + 0 − 𝑠2 + 𝑣2 + ⋯ + 0 = 𝑏2 , ⋮ 𝑎m1 𝑥1 + 𝑎m2 𝑥2 + ⋯ + 𝑎𝑚𝑛 𝑥𝑛 + 0 + 0 + ⋯ − 𝑠𝑚 + 𝑣𝑚 = 𝑏m . Seperti yang sudah dijelaskan di atas, bentuk umum masalah optimasi linear harus diubah ke dalam bentuk standar atau bentuk persamaan, sehingga dalam matriks A terbentuk matriks identitas dan dapat dituangkan ke dalam tabulasi simpleks. Berikut ini merupakan ilustrasi tabulasi simpleks: Table 1 Ilustrasi Tabulasi Simpleks 𝑐𝑖 𝑐1 𝑐2 ⋮ 𝑐𝑚

𝑐𝑗 Basis

𝑧𝑗 𝑧𝑗 − 𝑐𝑗

𝑐1 𝑥1 𝑎11 𝑎21 ⋮ 𝑎𝑚1 𝑧1 𝑧1 − 𝑐1

𝑐2 𝑥2 𝑎12 𝑎22 ⋮ 𝑎𝑚2 𝑧2 𝑧2 − 𝑐2

… … … … … … … …

𝑐𝑛 𝑥𝑛 𝑎1𝑛 𝑎2𝑛 ⋮ 𝑎𝑚𝑛 𝑧𝑛 𝑧𝑛 − 𝑐𝑛

0 𝑠1

0 … M 𝑠2 … 𝑣1 … … … …

𝑏𝑖 𝑏1 𝑏2 ⋮ 𝑏𝑚

Keterangan: a. Baris 𝑐𝑗 diisi dengan koefisien fungsi tujuan. b. Kolom 𝑐𝑖 diisi dengan koefisien variabel yang menjadi basis. c. Kolom basis diisi dengan nama-nama variabel yang menjadi basis (variabel yang menyusun matriks identitas). d. Kolom 𝑏𝑖 diisi dengan nilai ruas kanan dari kendala. e. Baris 𝑧𝑗 diisi dengan rumus 𝑧𝑗 = ∑𝑛𝑗=1 𝑐𝑖 𝑎𝑖𝑗 , j = 1, …, n.

1

Berikut ini akan diberikan proses algoritme simpleks, yaitu: Mengubah terlebih dahulu masalah optimasi linear ke bentuk standar, fungsi tujuan dan kendala-kendala diubah ke dalam bentuk persamaan. Seperti yang sudah dijelaskan di atas, dengan menambahkan variabel slack, variabel surplus, dan variabel artificial terhadap kendala yang berbentuk pertidaksamaan. Untuk fungsi tujuan, tambahkan variabel slack (dengan koefisien 0), variabel surplus (dengan koefisien 0), dan variabel artificial (dengan koefisien M untuk masalah meminimumkan dan –M untuk masalah memaksimumkan, M adalah bilangan yang cukup besar). Perhatikan contoh sebagai berikut:

9 𝑧 = 2𝑥1 + 3𝑥2 5𝑥1 + 6𝑥2 ≤ 60, 𝑥1 + 2𝑥2 ≤ 16, 𝑥1 ≤ 10, 𝑥2 ≤ 6.

maksimumkan terhadap

2

Bentuk standar: maksimumkan 𝑧 − 2𝑥1 − 3𝑥2 + 0𝑠1 + 0𝑠2 + 0𝑠3 + 0𝑠4 = 0 terhadap 5𝑥1 + 6𝑥2 + 𝑠1 = 60, 𝑥1 + 2𝑥2 + 𝑠2 = 16, 𝑥1 + 𝑠3 = 10, 𝑥2 + 𝑠4 = 6. Memasukkan bentuk standar masalah optimasi ke dalam tabulasi simpleks yang terdiri dari kolom basis, kolom variabel keputusan, kolom nilai ruas kanan, dan baris 𝑧𝑗 − 𝑐𝑗 (untuk tujuan meminimumkan atau memaksimumkan). Bentuk tabulasi sebagai berikut: Table 2 Tabulasi Simpleks

𝑐𝑖 0 0 0 0

3

4

𝑐𝑗 Basis 𝑠1 𝑠2 𝑠3 𝑠4 𝑧𝑗 𝑧𝑗 − 𝑐𝑗

3 𝑥2 6 2 0 1 0 -3

0 𝑠1 1 0 0 0 0 0

0 𝑠2 0 1 0 0 0 0

0 𝑠3 0 0 1 0 0 0

0 𝑠4 0 0 0 1 0 0

𝑏𝑖 60 16 10 6 0 0

Menentukan kolom kunci (variabel masuk), yaitu untuk masalah maksimum memilih 𝑧𝑗 − 𝑐𝑗 yang terkecil, sedangkan untuk masalah minimum memilih 𝑧𝑗 − 𝑐𝑗 yang terbesar. Menentukan baris kunci (variabel keluar), yaitu dari nilai rasio antara nilai ruas kiri ( 𝑏𝑖 ) dengan koefisien kolom kunci, pilih yang terkecil (untuk masalah minimum atau maksimum). Rasio =

5

2 𝑥1 5 1 1 0 0 -2

𝑏𝑖

𝑎𝑖𝑗

, j adalah kolom baris, di mana rasio > 0.

Menentukan pivot dari perpotongan antara kolom kunci dan baris kunci yang dinamakan elemen kunci atau elemen penentu iterasi algoritme simpleks dan akan diubah nilainya menjadi 1. Perhatikan contoh berikut:

10 Table 3 Tabulasi Simpleks Kolom Kunci dan Baris Kunci 𝑐𝑖 0 0 0 0

𝑐𝑗 Basis 𝑠1 𝑠2 𝑠3 𝑠4 * 𝑧𝑗 𝑧𝑗 − 𝑐𝑗

2 𝑥1 5 1 1 0 0 -2

3 𝑥2 * 6 2 0 1 0 -3

0 𝑠1 1 0 0 0 0 0

0 𝑠2 0 1 0 0 0 0

0 𝑠3 0 0 1 0 0 0

0 𝑠4 0 0 0 1 0 0

𝑏𝑖 60 16 10 6

Rasio 10 8 6

Keterangan: 𝑥2 ∗ adalah kolom kunci dengan nilai baris 𝑧𝑗 − 𝑐𝑗 terkecil, yaitu 𝑧𝑗 − 𝑐𝑗 = −3 dan 𝑠4 ∗ adalah kolom baris dengan nilai rasio terkecil, yaitu 6. Pivot berada pada elemen (4;2) dengan nilai elemennya adalah 1.

6

7

Selanjutnya melakukan operasi baris dasar (OBD) berdasarkan pivot untuk baris lainnya, termasuk baris 𝑧𝑗 − 𝑐𝑗 dengan nilai elemen-elemen yang termasuk di dalam kolom kunci dijadikan nol (selain elemen yang dijadikan pivot). Proses iterasi untuk masalah maksimum berhenti jika semua nilai pada baris 𝑧𝑗 − 𝑐𝑗 ≥ 0 berarti solusi sudah optimal, apabila masih ada 𝑧𝑗 − 𝑐𝑗 < 0 (negatif) maka iterasi metode simpleks masih berlanjut. Untuk masalah minimum berhenti jika semua nilai pada baris 𝑧𝑗 − 𝑐𝑗 ≤ 0, apabila masih ada 𝑧𝑗 − 𝑐𝑗 > 0 (positif) maka iterasi algoritme simpleks masih berlanjut.

Fungsi Mathematica untuk Metode Simpleks Mathematica dengan fasilitas terintegrasi lengkap, mampu memberikan perintah untuk menyelesaikan masalah optimasi linear sesuai metode yang diinginkan dan memberikan waktu eksekusi dalam menyelesaikannya. Fasilitas yang unik dari implementasi ini adalah: LinearProgramming[c,{m},{{b}}Method →”Simplex”]//Timing

dengan c merupakan nilai konstanta pada fungsi tujuan, m merupakan nilai konstanta (nilai ruas kiri) pada kendala, dan b merupakan nilai ruas kanan pada kendala. Sintaks Method → ”Simplex” adalah perintah untuk mengakses ke algoritme simpleks dalam menyelesaikan masalah optimasi linear dan Timing untuk memberikan waktu eksekusi dalam penyelesaian.

Metode Titik Interior Perkembangan baru dalam masalah optimasi linear adalah penemuan metode titik interior yang berhasil mengembangkan algoritme baru dengan pendekatan titik interior untuk menyelesaikan masalah optimasi linear. Metode titik interior adalah metode yang dibangun dari beberapa metode iterasi, di mana algoritme titik interior bergerak dengan menentukan titik-titik interior yang masuk di dalam interior daerah solusi penyelesaian atau daerah fisibel. Algoritme titik interior berbeda dengan algoritme simpleks, di mana dalam algoritme simpleks iterasinya menggunakan titik ekstrim yaitu bergerak dari verteks ke verteks untuk menentukan solusi daerah fisibel.

11 Algoritme titik interior digunakan untuk menyelesaikan masalah optimasi linear yang kompleks, dalam artian memiliki kendala dan variabel keputusan dengan jumlah yang besar. Karena algoritme titik interior membutuhkan jumlah iterasi yang sedikit dengan mempertimbangkan waktu hitung rata-rata dalam iterasinya, sehingga penyelesaian teknik komputasi algoritme titik interior umumnya membutuhkan waktu penyelesaian yang lebih sedikit, maka waktu eksekusi penyelesaian yang dibutuhkan untuk menyelesaikan masalah optimasi linear tersebut sering kali lebih cepat dibandingkan dengan metode simpleks, terutama jika dipakai untuk menyelesaikan permasalahan yang kompleks serta memiliki banyak kendala dan variabel yang harus diselesaikan untuk masalah dengan ukuran yang sama (Mitchell 1998). Penyelesaian masalah optimasi linear metode titik interior berkaitan dengan pendekatan metode barrier, metode pengali Lagrange serta metode Newton, baik itu pada bentuk primal ataupun bentuk dual (Vanderbei 2001). Pendekatan metode barrier diperkenalkan oleh Frisch pada tahun 1955 (Roos et al. 2006). Metode ini bermula dari suatu titik di interior dari pertidaksamaan 𝐱 > 𝟎 dan 𝐬 > 𝟎 , lalu dikonstruksi barrier sedemikian rupa sehingga variabel tidak menyentuh batas daerah fisibel. Penambahan ln 𝐱 ke fungsi objektif merupakan salah satu cara dari pendekatan barrier. Penambahan ln 𝐱 menyebabkan nilai fungsi objektif mengalami kenaikan atau penurunan tanpa batas (apabila 𝐱 → 𝟎 atau 𝐬 → 𝟎 ). Kesulitan ini ialah jika titik optimal berada pada batas, misalnya satu atau lebih 𝑥𝑖 = 0. Untuk mengatasi kesulitan ini, digunakan parameter 𝜇 untuk menentukan nilai minimum atau maksimum fungsi objektif dari bentuk barrier. Berdasarkan definisi bentuk standar masalah optimasi linear dengan fungsi tujuan serta kendala berbentuk linear, dalam penyelesaian masalah optimasi linear dengan menggunakan metode titik interior perlu ditentukan batasan masalah, dengan fungsi tujuan meminimumkan sehingga diperoleh bentuk optimasi linear dalam model matematik sebagai berikut: minimumkan 𝐜T𝐱 terhadap 𝐴𝐱 = 𝐛, (4) 𝐱≥𝟎 dengan 𝑥1 𝑐1 𝑏1 𝑥2 𝑐2 𝑏 𝐱 = � ⋮ �, 𝐜 = � ⋮ �, 𝐛 = � 2�, ⋮ 𝑥𝑛 𝑐𝑛 𝑏𝑚 dan 𝑎11 𝑎12 ⋯ 𝑎1𝑛 𝑎21 𝑎22 ⋯ 𝑎2𝑛 𝐴 =� ⋮ ⋮ ⋱ ⋮ �. 𝑎𝑚1 𝑎𝑚2 ⋯ 𝑎𝑚𝑛 Jika x dan c merupakan vektor berukuran 𝑛 × 1, dan b adalah vector berukuran 𝑚 × 1, maka A dapat dikatakan sebagai fungsi metode barrier dengan model masalah primal-barrier ditulis sebagai berikut: minimumkan 𝐜 T 𝐱 − 𝜇 ∑𝑛𝑗=1 ln�𝑥𝑗 � …(5.1) terhadap 𝐴𝐱 = 𝐛, …(5.2) (5) 𝐱 ≥ 𝟎. …(5.3)

12 Di mana 𝜇 adalah parameter suatu konstanta positif. lim ln(𝑥𝑖 ) = −∞ x→0

(6) (7)

Oleh karena itu, logaritme dalam fungsi objektif merupakan model barrier yang memberikan solusi negatif. Pada dasarnya ini akan menunjukkan solusi optimal yang memenuhi pertidaksamaan 𝐱 ≥ 𝟎, karena fungsi tujuan meminimumkan persamaan (5.1). Berdasarkan keadaan tersebut maka didapat pertidaksamaan pada kendala 𝐱 > 𝟎 persamaan (5.3) yang membuat masalah optimasi tidak linear, sehingga dapat diselesaikan dengan metode pengali Lagrange untuk 𝜇 > 0 definisi (6). Misalkan 𝐿𝑃(𝐱,𝐲) adalah fungsi Lagrange masalah primal, dapat ditulis sebagai berikut: 𝑛

𝐿𝑃(𝐱,𝐲) = 𝐜 T 𝐱 − 𝜇 � ln�𝑥𝑗 � − 𝐲 T (𝐴𝐱 − 𝐛) 𝑗=1

di mana 𝐲 ∈ 𝑅 𝑚 merupakan pengali Lagrange sesuai dengan sistem persamaan (4). Fungsi 𝐿𝑃(𝐱,𝐲) diturunkan sesuai aturan pengali Lagrange secara parsial terhadap 𝑥𝑗 dan 𝑦𝑗 dengan 𝑗 = 1, … , 𝑛. Pertama fungsi 𝐿𝑃(𝐱,𝐲) diturunkan terhadap 𝑥𝑗 dengan 𝑗 = 1, … , 𝑛. 𝜕𝐿𝑃(𝐱,𝐲) =0 𝜕𝑥𝑗

𝑚

𝜇 ⇔ 𝑐𝑗 − − � 𝑎𝑖𝑗 𝑦𝑗 = 𝟎 𝑥𝑗 𝑖=1 𝜕𝐿𝑃(𝐱,𝐲) ⇔ = 𝑐𝑗 − 𝜇𝑥𝑗 −1 − 𝐴𝑗 𝐲 = 𝟎 𝜕𝑥𝑗

(8)

𝑥1 0 ⋯ 0 0𝑥 ⋯0 dengan pemisalan 𝑋 ∶= diag (𝑥) = � ⋮ 2 ⋱ ⋮ �, 𝐞 ∶= (1, … , 1)𝑇 , dan simbol 𝟎 ⋮ 0 0 ⋯𝑥𝑛 adalah vektor nol. Persamaan (8) dalam notasi vektor: ⇔ ∇𝑥 𝜕𝐿𝑃(𝐱,𝐲) = 𝐜 − 𝜇𝑋 −1 𝐞 − 𝐴𝑇 𝐲 = 𝟎.

(9)

Selain itu, dengan pemisalan 𝐬 = 𝜇𝑋 −1 𝐞 subtitusikan ke dalam persamaan (9), didapat ⇔ 𝐜 − 𝐬 − 𝐴𝑇 𝐲 = 𝟎 ⇔ 𝐴𝑇 𝐲 + 𝐬 = 𝐜.

(10)

Kemudian fungsi 𝐿𝑃(𝐱,𝐲) diturunkan terhadap 𝑦𝑗 dengan 𝑗 = 1, … , 𝑛. 𝜕𝐿𝑃(𝐱,𝐲) =0 𝜕𝑦𝑗

⇔

𝜕𝐿𝑃(𝐱,𝐲) = 𝐛 − 𝐴𝐱 = 𝟎 𝜕𝑦𝑗

⇔ 𝐴𝐱 = 𝐛.

(11)

13 Dari bentuk standar optimasi linear pada sistem persamaan (4), dapat dibentuk masalah dual-barrier dengan daerah fisibel masalah dual dan juga daerah interior dual. Masalah dual-barrier ditulis sebagai berikut: 𝐛𝑇 𝐲 + 𝜇 ∑𝑛𝑗=1 ln�𝑠𝑗 � 𝐴𝑇 𝐲 + 𝐬 = 𝐜, 𝐬 ≥ 𝟎.

maksimumkan terhadap

…(12.1) …(12.2) …(12.3)

(12)

Persamaan dual dalam fungsi Lagrange: T

𝑛

𝐿𝐷(𝑥,𝑦,𝑠) = 𝐛 𝐲 + 𝜇 � ln�𝑠𝑗 � − (𝐴𝑇 𝐲 + 𝐬 − 𝐜)𝐱. 𝑗=1

Fungsi 𝐿𝐷(𝑥,𝑦,𝑠) diturunkan secara parsial terhadap 𝑥𝑗 , 𝑦𝑗 dan 𝑠𝑗 dengan 𝑗 = 1, … , 𝑛. Pertama fungsi 𝐿𝐷(𝑥,𝑦,𝑠) diturunkan terhadap 𝑥𝑗 dengan 𝑗 = 1, … , 𝑛. 𝜕𝐿𝐷(𝑥,𝑦,𝑠) =0 𝜕𝑥𝑗 𝑚

⇔ � 𝑎𝑖𝑗 𝑦𝑗 − 𝑠𝑗 = 𝑐𝑖 𝑖=1 𝑇

⇔ 𝐴 𝐲 + 𝐬 = 𝐜.

(13)

Kemudian fungsi 𝐿𝐷(𝑥,𝑦,𝑠) diturunkan terhadap 𝑦𝑗 dengan 𝑗 = 1, … , 𝑛. 𝜕𝐿𝐷(𝑥,𝑦,𝑠) =0 𝜕𝑦𝑗 𝑛

⇔ � 𝑎𝑖𝑗 𝑥𝑗 = 𝑏𝑖 𝑖=1

⇔ 𝐛 − 𝐴𝐱 = 𝟎 ⇔ 𝐴𝐱 = 𝐛.

(14)

Selanjutnya fungsi 𝐿𝐷(𝑥,𝑦,𝑠) diturunkan terhadap 𝑠𝑗 dengan 𝑗 = 1, … , 𝑛.

𝜕𝐿𝐷(𝑥,𝑦,𝑠) =0 𝜕𝑠𝑗 𝜇 ⇔ − 𝑥𝑗 = 𝟎 𝑠𝑗 𝜇 ⇔ 𝑥𝑗 = 𝑠𝑗 ⇔ 𝑥𝑗 𝑠𝑗 = 𝜇.

(15) Variabel dual 𝐲 merupakan pengali Lagrange untuk masalah primal dan variabel primal 𝐱 merupakan pengali Lagrange untuk masalah dual. Kendala pelengkap diganti menjadi 𝐱𝐬 = 𝜇𝐞, agar solusi sistem dari sistem yang baru mendekati solusi sistem persamaan (5), dengan parameter 𝜇 adalah sembarang bilangan positif dan 𝐞 adalah vektor yang semua unsurnya bernilai satu. Kendala 𝐱𝐬 = 𝜇𝐞 ini disebut juga kondisi-pemusat pada 𝜇 (Silalahi 2011).

14 Melihat sistem persamaan (4) kondisi primal dan sistem persamaan (12) dalam kondisi dual, dengan melakukan pendekatan metode barrier dan melakukan iterasi menggunakan metode pengali Lagrange dari kedua sistem persamaan tersebut diperoleh daerah titik interior sebagai sistem persamaan yang baru, yaitu: …(16.1) 𝐴𝐱 = 𝐛, 𝐱 ≥ 𝟎, …(16.2) (16) 𝐬 ≥ 𝟎, 𝐴𝑇 𝐲 + 𝐬 = 𝐜, …(16.3) 𝐱𝐬 = 𝜇𝐞 𝑛 dengan vektor-vektor 𝐜, 𝐱, 𝐬 ∈ ℝ , sedangkan vektor-vektor 𝐛, 𝐲 ∈ ℝ𝑚 , serta matriks 𝐴 ∈ ℝ𝑚×𝑛 adalah matriks berpangkat baris penuh. Vektor 𝐞 adalah vektor yang semua unsurnya bernilai satu dengan 𝐞 ∈ ℝ𝒏 . Sistem ini merupakan kondisi optimal untuk masalah minimisasi (Silalahi 2011). Jika sistem persamaan (16) memiliki solusi untuk beberapa nilai positif dari parameter 𝜇 maka daerah fisibel primal mengandung vektor 𝐱 positif, dan daerah fisibel dual mengandung pasangan (𝐲, 𝐬) dengan vektor 𝐬 positif sehingga daerah fisibel primal dan daerah fisibel dual mengandung vektor positif. Hal tersebut merupakan kondisi fisibel titik interior. Demikian juga sebaliknya, jika daerah fisibel primal dan dual mengandung vektor positif maka sistem persamaan (16) memiliki solusi untuk setiap 𝜇 positif. Hal ini merupakan konsekuensi dari teorema berikut.

Teorema 1 Misalkan 𝜇 > 0 . Daerah fisibel primal ( 𝒫) dan dual (𝒟) mengandung vektor positif jika dan hanya jika sistem persamaan (16) memiliki solusi yang tunggal (Roos et al. 2006). Iterasi dari algoritme titik interior dalam menyelesaikan masalah optimasi linear dilanjutkan dengan tahapan Newton, yaitu untuk mencari nilai solusi optimalnya. Tahap ini dikenal dengan tahap prediksi nilai solusi optimal yang layak. Langkah selanjutnya yaitu menentukan sistem persamaan baru yang sesuai dengan sistem persamaan (16), serta dapat menentukan nilai matriks Jacobi J(y) sebagai berikut: …(17.1) 𝐴𝐱 − 𝐛 = 𝟎, 𝑇 …(17.2) (17) 𝐴 𝐲 + 𝐬 − 𝐜 = 𝟎, …(17.3) 𝐱𝐬 − 𝜇𝐞 = 𝟎. Sistem persamaan (17) merupakan persamaan f(y) dengan matriks Jacobi J(y): 𝐴 0 0 𝐽(𝐲) = � 0 𝐴𝑇 𝐼 �. 𝐬 0 𝐱 0 0 0 Asumsi titik awal ( 𝐱 , 𝐲 , 𝐬 ) memenuhi 𝐱 0 > 0 dan 𝐬0 > 0 terhadap kendala awal persamaan primal-dual dinotasikan sebagai sistem berikut: 𝛿𝑃 = 𝐛 + 𝐴𝐱 0 𝛿𝐷 = 𝐜 − 𝐴T 𝐲 0 − 𝐬0 Kondisi optimal dapat ditulis sebagai berikut:

dengan 𝐝 = (𝐝𝑥 , 𝐝𝑦 , 𝐝𝑠 ), adalah

𝐽(𝐲)𝐝 = −𝑓(𝐲),

15 𝐴 �0 𝐬

0 𝐴𝑇 0

𝛿𝑃 0 𝐝𝑥 𝐝 𝐼 � � 𝑦 � = � 𝛿𝐷 � 𝜇𝐞 − 𝐱𝐬 𝐱 𝐝𝑠 ⇔ 𝐴𝐝𝑥 = 𝛿𝑃 , 𝑇 𝐴 𝐝𝑦 + 𝐝𝑠 = 𝛿𝐷 ,

𝐬𝐝𝑥 + 𝐱𝐝𝑠 = 𝜇𝐞 − 𝐱𝐬,

dengan manipulasi aljabar untuk menentukan 𝐝 = (𝐝𝑥 , 𝐝𝑦 , 𝐝𝑠 ) didapat

1. 2. 3.

𝐝𝑦 = (𝐴𝐱𝐬−1 𝐴𝑇 )−1 (𝐛 − 𝜇𝐴𝐬 −𝟏 ) 𝐝𝑠 = −𝛿𝐷 − 𝐴𝑇 𝐝𝑦 𝐝𝑥 = 𝐬 −1 (𝜇𝐞 − 𝐱𝐬 − 𝐱𝐝𝑠 ).

Proses iterasi algoritme titik interior primal-dual selanjutnya, yaitu: Menentukan solusi fisibel awal 𝒙(0) > 0 , 𝐬 (0) > 0 , 𝐲 (0) > 0 , dengan 𝑘 = 0 toleransi optimal 𝜀 > 0, dan parameter 0 < 𝜃 < 1. Tes optimalisasi, selama (𝒙𝑘 )𝑇 𝒔𝑘 ≥ 𝜀 lanjut ke langkah berikutnya. Jika (𝒙𝑘 )𝑇 𝒔𝑘 < 𝜀, iterasi berhenti. Hitung langkah Newton-penuh, dan perbarui solusi 𝒙(𝑘+1) = 𝒙(𝑘) + 𝛼𝑃 𝐝𝑘𝑥 𝒚(𝑘+1) = 𝒚(𝑘) + 𝛼𝐷 𝐝𝑘𝑦 𝒔(𝑘+1) = 𝒔(𝑘) + 𝛼𝐷 𝐝𝑘𝑠

−𝑥𝑗

dengan 𝛼𝑃 = 𝜃 min𝑗 �(𝐝

𝑥 )𝑗

4.

−𝑠𝑗

; (𝐝𝑥 )𝑗 < 0� , 𝛼𝐷 = 𝜃 min𝑗 �(𝐝

𝑠 )𝑗

adalah nilai pendekatan dengan 𝜃 sebagai parameter pembatas.

Selanjutnya 𝑘 ← 𝑘 + 1, kembali ke Langkah 2.

; (𝐝𝑠 )𝑗 < 0�

Nilai akhir yang diperoleh menyatakan nilai objektif dari fungsi optimasi linear yang telah dicari solusinya, sehingga tahapan-tahapan koreksi yang dilakukan memperoleh titik interior sebagai daerah jawab terutama setelah melakukan beberapa iterasi sampai memperoleh titik optimum sebagai solusi penyelesaian dari masalah optimasi linear. Fungsi Mathematica untuk Metode Titik Interior Mathematica dengan fasilitas terintegrasi lengkap, mampu memberikan perintah untuk menyelesaikan masalah optimasi linear sesuai metode yang diinginkan dan memberikan waktu eksekusi dalam menyelesaikannya. Mathematica mengimplementasikan algoritme titik interior dengan menggunakan fasilitas yang unik, yaitu: LinearProgramming[c,{m},{{b}}Method → ”InteriorPoint”]//Timin g, dengan c merupakan konstanta pada fungsi tujuan, m merupakan konstanta

kendala,

dan

b

merupakan

nilai

ruas

kanan pada kendala. Sintaks untuk menyelesaikan masalah optimasi linear dengan metode titik interior dan Timing untuk memberikan waktu eksekusi dalam penyelesaian. Method →”InteriorPoint” adalah perintah

16 Melihat secara teoritis iterasi antara metode simpleks dan metode titik interior sangat berbeda, seperti yang telah dijelaskan di atas. Untuk melihat perbedaan waktu dalam menyelesaikan masalah optimasi linear, dilihat dari perbandingan waktu eksekusi penyelesaian antara kedua metode tersebut. Perbandingan dilakukan terhadap studi kasus dengan bantuan perangkat lunak Mathematica, dan ukuran masalah optimasi linear dipilih bervariasi secara kontinu dari masalah optimasi linear yang sederhana (berukuran kecil) sampai masalah optimasi linear yang kompleks dengan kendala dan variabel berukuran besar.

Studi Kasus Kasus 1: Masalah optimasi linear dengan 2 kendala dan 2 variabel min x + 2y kendala x + 2y ≥ 3, x + y ≤ 2, x, y ≥ 0. Penyelesaian komputasi dengan metode simpleks: input: LinearProgramming[{1.,2},{{1,2},{1,1}},{{3,1},{2,output: input: output: input: input: output: input: output:

1}},Method →”Simplex”]//Timing {0.,{0., 1.5}} First[%]<$TimeUnit True reps=100000; {time,res}= Timing[Do[LinearProgramming[{1.,2},{{1,2},{1,1}},{ {3,1},{2,-1}},Method →"Simplex"],{reps}]] {2.574,Null} time/reps 0.00002574

Penyelesaian komputasi dengan metode titik interior: input: LinearProgramming[{1.,2},{{1,2},{1,1}},{{3,1},{2,output: input: output: input: input: output: input: output:

1}},Method →”InteriorPoint”]//Timing {0.,{0.00940398,1.4953}} First[%]<$TimeUnit True reps=100000; {time,res}= Timing[Do[LinearProgramming[{1.,2},{{1,2},{1,1}},{ {3,1},{2,-1}},Method →"InteriorPoint"],{reps}]] {59.046,Null} time/reps 0.00059046

17 Kasus 2: Masalah optimasi linear dengan 5 kendala dan 5 variabel maks 2𝑥1 + 𝑥2 + 𝑥3 + 2𝑥4 + 𝑥5 kendala 2𝑥1 + 𝑥2 + 𝑥3 + 𝑥4 + 𝑥5 = 8, 𝑥1 + 2𝑥2 − 3𝑥3 + 𝑥4 + 2𝑥5 ≥ 6, 𝑥1 − 𝑥2 + 2𝑥3 + 𝑥4 = 3, 𝑥1 + 𝑥2 + 𝑥4 + 𝑥5 ≤ 6, 𝑥1 + 𝑥2 + 𝑥3 + 𝑥5 = 5, 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 , 𝑥5 ≥ 0.

Penyelesaian komputasi dengan metode simpleks: input: LinearProgramming[{-2,-1,-1,-2,-1},{{2,1,1,1,1},

output: input: output: input: input:

output: input: output:

{1,2,-3,1,2},{1,-1,2,1,0},{1,1,0,1,1},{1,1,1,0, 1}},{{8,0},{6,1},{3,0},{6,-1},{5,0}},Method →”Simplex”]//Timing {0.,{1,2,1,2,1}} First[%]<$TimeUnit True reps=100000; {time,res}= Timing[Do[LinearProgramming[{-2,-1,-1,-2,-1},{{2, 1,1,1,1},{1,2,-3,1,2},{1,-1,2,1,0},{1,1,0,1,1},{1, 1,1,0,1}},{{8,0},{6,1},{3,0},{6,-1},{5,0}},Method →"Simplex"],{reps}]] {22.09,Null} time/reps 0.0002209

Penyelesaian komputasi dengan metode titik interior: input: LinearProgramming[{-2,-1,-1,-2,-1},{{2,1,1,1,1},{1,

output: input: output: input: input:

output: input: output:

2,-3,1,1},{1,-1,2,1,0},{1,1,0,1,1},{1,1,1,0,1}}, {{8,0},{6,1},{3,0},{6,-1},{5,0}},Method →”InteriorPoint”]//Timing {0.,{1,2,1,2,1}} First[%]<$TimeUnit True reps=100000; {time,res}= Timing[Do[LinearProgramming[{-2,-1,-1,-2,-1},{{2, 1,1,1,1},{1,2,-3,1,2},{1,-1,2,1,0},{1,1,0,1,1},{1, 1,1,0,1}},{{8,0},{6,1},{3,0},{6,-1},{5,0}},Method →"InteriorPoint"],{reps}]] {301.784,Null} time/reps 0.00301784

Pada studi kasus di atas terdapat sintaks tambahan, yaitu reps. Pengertian reps adalah bentuk perintah dalam perangkat lunak Mathematica sebagai variabel

18 tambahan untuk melakukan pengulangan. Fungsi dari reps = n yaitu melakukan pengulangan sebanyak n kali terhadap masalah optimasi linear yang bertujuan untuk mengetahui satuan waktu terkecil dengan memunculkan angka di belakang koma dalam waktu eksekusi. Melihat studi kasus yang dilakukan di atas, waktu eksekusi awal yang diperoleh dari masalah optimasi linear hanya muncul nilai nol saja. Oleh karena itu, diberikan sintaks tambahan reps untuk melakukan pengulangan sehingga memperoleh waktu eksekusi yang lebih jelas dengan adanya angka di belakang koma. Untuk mendapatkan eksekusi yang sebenarnya dari masalah optimasi linear, selanjutnya membagi waktu yang diperoleh dari pengulangan dengan banyaknya pengulangan (time/reps) sehingga mendapatkan waktu eksekusi rata-rata yang merupakan waktu eksekusi sebenarnya dari masalah optimasi linear. Untuk menganalisis waktu eksekusi dalam mencari nilai optimum suatu fungsi objektif dari masalah optimasi linear yang berukuran besar digunakan fasilitas SparseArray dan Band pada Mathematica. SparseArray merupakan salah satu fasilitas Mathematica untuk membuat matriks dengan nilai-nilai hanya pada posisi tertentu atau pada elemen tertentu dalam list data tersebut, dengan nilai elemen yang lain dianggap nol. Band berfungsi untuk menentukan nilai pada posisi tertentu dengan elemen yang berbentuk diagonal di dalam list data SparseArray. Bentuk Band[𝑖𝑚𝑖𝑛 , 𝑗𝑚𝑖𝑛 ] merupakan urutan posisi pada diagonal yang dimulai dengan indeks {i, j} dalam matriks SparseArray. Contoh membuat matriks dengan SparseArray dan Band sebagai berikut: input: SparseArray[{Band[{1,1}]→x,Band[{2,1}]→y},{3,3}] //MatrixForm

output:

𝑥 �𝑦 0

0 𝑥 𝑦

0 0� 𝑥

Kasus 3: Masalah OL dengan 10 kendala dan 10 variabel ( 𝑥𝑖 ≥ 0, i = 1, 2, 3, …., 10). min 𝑥1 + 2𝑥2 + 3𝑥3 + 4𝑥4 + 5𝑥5 + 6𝑥6 + 7𝑥7 + 8𝑥8 + 9𝑥9 + 10𝑥10 kendala 3𝑥1 + 𝑥2 = 1, 3𝑥7 + 𝑥8 = 7, 3𝑥2 + 𝑥3 = 2, 3𝑥8 + 𝑥9 = 8, 3𝑥3 + 𝑥4 = 3, 3𝑥9 + 𝑥10 = 9, 3𝑥4 + 𝑥5 = 4, 3𝑥10 = 10, 3𝑥5 + 𝑥6 = 5, 𝑥𝑖 ≥ 0, i = 1, 2, 3, …., 10. 3𝑥6 + 𝑥7 = 6, Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[10],SparseArray

output: input: output: input:

[{Band[{1,1}]→3.,Band[{1,2}]→1.},{10,10}],Range[10] ,Method→”Simplex”]] {0.,{0.187454,0.437637,0.68709,0.938729,1.18381, 1.44856,1.65432,2.03704,1.88889,3.33333}} First[%]<$TimeUnit True reps=100000;

19 input:

output: input: output:

{time,res}= Timing[Do[LinearProgramming[Range[10],SparseArray[{ Band[{1,1}] → 3.,Band[{1,2}] → 1.},{10,10}],Range[10] ,Method →"Simplex"],{reps}]] {48.797,Null} time/reps 0.00048797

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[10],SparseArray

output: input: output: input: input:

output: input: output:

[{Band[{1,1}]→3.,Band[{1,2}]→1.},{10,10}],Range[10] ,Method→”InteriorPoint”]] {0,{0.187454,0.437637,0.68709,0.938729,1.18381, 1.44856,1.65432,2.03704,1.88889,3.33333}} First[%]<$TimeUnit True reps=100000; {time,res}= Timing[Do[LinearProgramming[Range[10],SparseArray[{ Band[{1,1}] → 3.,Band[{1,2}] → 1.},{10,10}],Range[10] ,Method →"InteriorPoint"],{reps}]] {177.217,Null} time/reps 0.00177217

Di atas telah diberikan 3 studi kasus, dari 10 studi kasus yang dilakukan. Untuk studi kasus yang lainnya terlampir pada Lampiran 1 sampai Lampiran 7. Perbedaan waktu eksekusi antara metode simpleks dan metode titik interior dalam menyelesaikan masalah optimasi linear yang dilakukan terhadap beberapa studi kasus, dapat dilihat pada Tabel 4. Tabel 4 Waktu eksekusi metode simpleks dan metode titik interior dengan lima kali pengulangan Waktu Eksekusi Studi Kasus Ukuran 𝑚 × 𝑛 Percobaan Metode Metode Titik Simpleks Interior I 0.00002574 0.00059046 II 0.00002480 0.00057673 1 III 0.00002480 0.00063009 2×2 IV 0.00002559 0.00063118 V 0.00002605 0.00063945 I 0.00022090 0.00301784 II 0.00022121 0.00299897 2 III 0.00022121 0.00301816 5×5 IV 0.00022121 0.00302673 V 0.00021996 0.00302252

20

3

10 × 10

4

50 × 50

5

100 × 100

6

100 × 200

7

200 × 200

8

500 × 500

9

500 × 1000

10

100 × 200000

I II III IV V I II III IV V I II III IV V I II III IV V I II III IV V I II III IV V I II III IV V I II III IV V

0.00048797 0.00049187 0.00049234 0.00049031 0.00049203 0.01600000 0.03100000 0.01500000 0.01600000 0.01600000 0.12500000 0.12500000 0.14000000 0.12500000 0.14000000 0.25000000 0.24900000 0.25000000 0.24900000 0.25000000 0.95200000 0.93600000 0.93600000 0.96700000 0.95200000 14.2430000 14.2740000 14.4140000 14.2900000 14.4770000 28.0170000 27.9550000 28.0800000 28.1580000 28.0180000 227.808000 227.496000 227.652000 229.103000 227.028000

0.00177217 0.00177810 0.00177295 0.00176812 0.00177310 0.00417630 0.00417849 0.00417630 0.00418036 0.00417786 0.00701146 0.00700461 0.00700804 0.00700695 0.00699259 0.00715202 0.00713127 0.00720849 0.00714531 0.00714063 0.01500000 0.03100000 0.03200000 0.01500000 0.01600000 0.03100000 0.03100000 0.03100000 0.04700000 0.04700000 0.03100000 0.03200000 0.04700000 0.04700000 0.04600000 0.12400000 0.14100000 0.12400000 0.12400000 0.14100000

Pada Tabel 4 di atas, dalam satu studi kasus dilakukan lima kali pengulangan eksekusi pada satu kasus yang sama, dan didapatkan hasil yang berbeda-beda. Hal tersebut dipengaruhi oleh keadaan kinerja komputer pada saat melakukan komputasi. Adanya perbedaan hasil waktu eksekusi tersebut (yang tercantum dalam Tabel 4), selanjutnya diambil nilai rata-rata waktu eksekusi untuk mempermudah menganalisis perbedaan waktu eksekusi penyelesaian masalah

21 optimasi linear. Perbedaan waktu eksekusi rata-rata antara metode simpleks dan metode titik interior dengan mengunakan perangkat lunak Mathematica, dapat dilihat pada Tabel 5. Tabel 5 Waktu eksekusi rata-rata metode simpleks dan metode titik interior serta perbandingan waktu eksekusi metode simpleks : metode titik interior Waktu Eksekusi Perbandingan Studi Ukuran 𝑚 × 𝑛 Metode Metode Titik Waktu Eksekusi Kasus (i : ii) Simpleks (i) Interior (ii) 1 0.000025390 0.000613582 0.041380 : 1 2×2 2 0.000220898 0.003016843 0.073222 : 1 5×5 3 0.000490904 0.001772888 0.276895 : 1 10 × 10 4 0.018800000 0.004177862 4.499909 : 1 50 × 50 5 0.131000000 0.007004730 18.70165 : 1 100 × 100 6 0.249600000 0.007155544 34.88204 : 1 100 × 200 7 0.948600000 0.021800000 43.51376 : 1 200 × 200 8 14.33960000 0.037400000 383.4118 : 1 500 × 500 9 28.04560000 0.040600000 690.7783 : 1 500 × 1000 10 1741.723 : 1 100 × 200000 227.8174000 0.130800000 Keterangan: Perbandingan waktu eksekusi metode simpleks : metode titik interior

Penyajian dari Tabel 5 perbandingan waktu eksekusi metode simpleks : metode titik interior dalam bentuk grafik, ditunjukkan pada Gambar 1 sebagai berikut: 2000 1800 1600

Waktu Eksekusi

1400 1200 1000 800 600 400 200 0

Banyaknya Kendala dan Variabel

Gambar 1 Perbandingan waktu eksekusi metode simpleks : metode titik interior

22 Pada studi kasus yang telah dilakukan dengan melihat Tabel 5 dan Gambar 1 di atas, terlihat perbedaan waktu eksekusi antara metode simpleks dan metode titik interior dalam menyelesaikan masalah optimasi linear. Pada studi kasus masalah optimasi linear yang berukuran sederhana dengan variabel keputusan dan kendala yang berukuran kecil, seperti yang terlihat pada studi kasus 1 sampai studi kasus 3 metode simpleks dan metode titik interior mempunyai waktu eksekusi yang sama kecil dengan perbedaan yang tidak terlalu menonjol. Waktu eksekusi metode simpleks mulai terlihat semakin naik pada studi kasus 4 dengan masalah optimasi linear yang berukuran 50 × 50. Sebaliknya, metode titik interior belum mengalami kenaikan yang drastis. Pada studi kasus selanjutnya, waktu eksekusi metode simpleks semakin besar dibandingkan dengan waktu eksekusi metode titik interior. Hal tersebut terlihat jelas perbedaannya pada studi kasus 8 dengan masalah optimasi linear yang berukuran 500 × 500, metode simpleks memiliki waktu eksekusi 14.3396 detik, sedangkan waktu eksekusi metode titik interior adalah 0.0374 detik. Hal ini menunjukkan bahwa untuk menyelesaikan masalah optimasi linear yang berukuran besar metode titik interior lebih cepat dibandingkan dengan metode simpleks.

SIMPULAN Berdasarkan studi kasus yang dilakukan terhadap permasalahan optimasi linear yang bervariasi, hasil perbandingan waktu eksekusi dalam menyelesaikan masalah optimasi linear untuk mencari nilai optimum dengan menggunakan bantuan perangkat lunak Mathematica menunjukkan bahwa metode titik interior lebih cepat untuk mencari nilai optimum pada masalah optimasi linear yang berukuran relatif besar dibandingkan metode simpleks.

DAFTAR PUSTAKA Ardana NKK. 2002. Panduan Penggunaan Mathematica. Buku ke-1. Bogor (ID): Departemen Matematika Fakultas MIPA – IPB. Jensen PA, Bard JF. 2003. Operations Research Models and Methods. New York (US): J Wiley. Mitchell JE, Pardalos PM, Resende MGC. 1998. Interior Point Methods for Combinatorial Optimazation. New York (US): Kluwer Academic Publishers. Nash SG, Sofer A. 1996. Linear and Nonlinear Programming. New York (US): McGraw-Hill. Roos C, Terlaky T, Vial JP. 2006. Interior Point Methods for Linear Optimization. New York (US): Springer Publishing. Silalahi BP. 2011. On the Central Path of Redundant Klee-Minty Problems. PhD thesis. Roos C (promotor). Delft University of Technology. The Netherlands (NL): TU Delft. Siswanto. 2007. Operations Research. Jilid ke-1. Jakarta(ID): Erlangga.

23 Vanderbei R. 2001. Linear Programming Foundations and Extensions. New York (US): Springer - Verlag. Winston WL. 2004. Operations Research Application and Algorithm. Edisi ke-4. New York (US): Duxbury.

24 Lampiran 1 Studi kasus 4 dengan menggunakan Mathematica Kasus 4: Masalah OL dengan 50 kendala dan 50 variabel (𝑥𝑖 ≥ 0, i = 1, 2, 3, ..., 50)

Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[50],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{50,50}],Range[5 0],Method→”Simplex”]] {0.016,{0.1875,0.4375,0.6875,0.9375,1.1875,1.437 5,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1875 ,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.9375, 5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875,6 .9375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375,8. 6875,8.9375,9.1875,9.43751,9.68748,9.93757,10.1873 ,10.4381,10.6856,10.9433,11.1701,11.4897,11.5309,1 2.4074,10.7778,16.6667}}

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[50],SparseArray

output:

input: output: input: input:

output: input: output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{50,50}],Range[5 0],Method→”InteriorPoint”]] {0.,{0.1875,0.4375,0.6875,0.9375,1.1875,1.4375, 1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1875,3 .4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.9375,5. 1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875,6.9 375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375,8.68 75,8.9375,9.1875,9.43751,9.68748,9.93757,10.1873,1 0.4381,10.6856,10.9433,11.1701,11.4897,11.5309,12. 4074,10.7778,16.6667}} First[%]<$TimeUnit True reps=100000; {time,res}= Timing[Do[LinearProgramming[Range[50],SparseArray[{ Band[{1,1}]→1.,Band[{1,2}]→2.},{50,50}],Range[50],M ethod→"InteriorPoint"],{reps}]] {417.63,Null} time/reps 0.0041763

25 Lampiran 2 Studi kasus 5 dengan menggunakan Mathematica Kasus 5: Masalah OL dengan 100 kendala dan 100 variabel ( 𝑥𝑖 ≥ 0, i = 1, 2, 3, ..., 100) Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[100],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{100,100}],Range [100],Method→”Simplex”]] {0.125,{0.1875,0.4375,0.6875,0.9375,1.1875,1.4 375,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.18 75,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.937 5,5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875 ,6.9375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375, 8.6875,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875, 10.4375,10.6875,10.9375,11.1875,11.4375,11.6875,11 .9375,12.1875,12.4375,12.6875,12.9375,13.1875,13.4 375,13.6875,13.9375,14.1875,14.4375,14.6875,14.937 5,15.1875,15.4375,15.6875,15.9375,16.1875,16.4375, 16.6875,16.9375,17.1875,17.4375,17.6875,17.9375,18 .1875,18.4375,18.6875,18.9375,19.1875,19.4375,19.6 875,19.9375,20.1875,20.4375,20.6875,20.9375,21.187 5,21.4375,21.6875,21.9375,22.1875,22.4376,22.6871, 22.9388,23.1837,23.449,23.6529,24.0412,23.8765,25. 3704,21.8889,33.3333}}

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[100],SparseArray

output:

input: output: input: input:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{100,100}],Range [100],Method→”InteriorPoint”]] {0.,{0.1875,0.4375,0.6875,0.9375,1.1875,1.4375, 1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1875,3 .4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.9375,5. 1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875,6.9 375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375,8.68 75,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875,10.4 375,10.6875,10.9375,11.1875,11.4375,11.6875,11.937 5,12.1875,12.4375,12.6875,12.9375,13.1875,13.4375, 13.6875,13.9375,14.1875,14.4375,14.6875,14.9375,15 .1875,15.4375,15.6875,15.9375,16.1875,16.4375,16.6 875,16.9375,17.1875,17.4375,17.6875,17.9375,18.187 5,18.4375,18.6875,18.9375,19.1875,19.4375,19.6875, 19.9375,20.1875,20.4375,20.6875,20.9375,21.1875,21 .4375,21.6875,21.9375,22.1875,22.4376,22.6871,22.9 388,23.1837,23.449,23.6529,24.0412,23.8765,25.3704 ,21.8889,33.3333}} First[%]<$TimeUnit True reps=100000; {time,res}=

26

output: input: output:

Timing[Do[LinearProgramming[Range[100],SparseArray[ {Band[{1,1}]→1.,Band[{1,2}]→2.},{100,100}],Range[10 0],Method→"InteriorPoint"],{reps}]] {701.146,Null} time/reps 0.00701146

27 Lampiran 3 Studi kasus 6 dengan menggunakan Mathematica Kasus 6: Maslah OL dengan 100 kendala dan 200 variabel ( 𝑥𝑖 ≥ 0, i = 1, 2, 3, ..., 200)

Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[200],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{100,200}],Range [100],Method→”Simplex”]] {0.25,{0.1875,0.4375,0.6875,0.9375,1.1875,1.43 75,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.187 5,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.9375 ,5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875, 6.9375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375,8 .6875,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875,1 0.4375,10.6875,10.9375,11.1875,11.4375,11.6875,11. 9375,12.1875,12.4375,12.6875,12.9375,13.1875,13.43 75,13.6875,13.9375,14.1875,14.4375,14.6875,14.9375 ,15.1875,15.4375,15.6875,15.9375,16.1875,16.4375,1 6.6875,16.9375,17.1875,17.4375,17.6875,17.9375,18. 1875,18.4375,18.6875,18.9375,19.1875,19.4375,19.68 75,19.9375,20.1875,20.4375,20.6875,20.9375,21.1875 ,21.4375,21.6875,21.9375,22.1875,22.4376,22.6871,2 2.9388,23.1837,23.449,23.6529,24.0412,23.8765,25.3 704,21.8889,33.3333,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.}}

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[200],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{100,200}],Range [100],Method→”InteriorPoint”]] {0.,{0.1875,0.4375,0.6875,0.9375,1.1875,1.4375, 1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1875,3 .4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.9375,5. 1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875,6.9 375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375,8.68 75,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875,10.4 375,10.6875,10.9375,11.1875,11.4375,11.6875,11.937 5,12.1875,12.4375,12.6875,12.9375,13.1875,13.4375, 13.6875,13.9375,14.1875,14.4375,14.6875,14.9375,15 .1875,15.4375,15.6875,15.9375,16.1875,16.4375,16.6 875,16.9375,17.1875,17.4375,17.6875,17.9375,18.187 5,18.4375,18.6875,18.9375,19.1875,19.4375,19.6875, 19.9375,20.1875,20.4375,20.6875,20.9375,21.1875,21 .4375,21.6875,21.9375,22.1875,22.4376,22.6871,22.9 388,23.1837,23.449,23.6529,24.0412,23.8765,25.3704 ,21.8889,33.3333,2.72537*10^-10,0.,

28

input: output: input: input:

output: input: output:

0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.}} First[%]<$TimeUnit True reps=100000; {time,res}= Timing[Do[LinearProgramming[Range[200],SparseArray[ {Band[{1,1}]→3.,Band[{1,2}]→1.},{100,200}],Range[10 0],Method→"InteriorPoint"],{reps}]] {715.202,Null} time/reps 0.00715202

29 Lampiran 4 Studi kasus 7 dengan menggunakan Mathematica Kasus 7: Masalah OL dengan 200 kendala dan 200 variabel ( 𝑥𝑖 ≥ 0, i = 1, 2, 3, ..., 200) Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[200],SparseArra

output:

y[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{200,200}],Rang e[200],Method→”Simplex”]] {0.952,{0.1875,0.4375,0.6875,0.9375,1.1875,1.4 375,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.18 75,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.937 5,5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875 ,6.9375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375, 8.6875,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875, 10.4375,10.6875,10.9375,11.1875,11.4375,11.6875,11 .9375,12.1875,12.4375,12.6875,12.9375,13.1875,13.4 375,13.6875,13.9375,14.1875,14.4375,14.6875,14.937 5,15.1875,15.4375,15.6875,15.9375,16.1875,16.4375, 16.6875,16.9375,17.1875,17.4375,17.6875,17.9375,18 .1875,18.4375,18.6875,18.9375,19.1875,19.4375,19.6 875,19.9375,20.1875,20.4375,20.6875,20.9375,21.187 5,21.4375,21.6875,21.9375,22.1875,22.4375,22.6875, 22.9375,23.1875,23.4375,23.6875,23.9375,24.1875,24 .4375,24.6875,24.9375,25.1875,25.4375,25.6875,25.9 375,26.1875,26.4375,26.6875,26.9375,27.1875,27.437 5,27.6875,27.9375,28.1875,28.4375,28.6875,28.9375, 29.1875,29.4375,29.6875,29.9375,30.1875,30.4375,30 .6875,30.9375,31.1875,31.4375,31.6875,31.9375,32.1 875,32.4375,32.6875,32.9375,33.1875,33.4375,33.687 5,33.9375,34.1875,34.4375,34.6875,34.9375,35.1875, 35.4375,35.6875,35.9375,36.1875,36.4375,36.6875,36 .9375,37.1875,37.4375,37.6875,37.9375,38.1875,38.4 375,38.6875,38.9375,39.1875,39.4375,39.6875,39.937 5,40.1875,40.4375,40.6875,40.9375,41.1875,41.4375, 41.6875,41.9375,42.1875,42.4375,42.6875,42.9375,43 .1875,43.4375,43.6875,43.9375,44.1875,44.4375,44.6 875,44.9375,45.1875,45.4375,45.6875,45.9375,46.187 5,46.4375,46.6875,46.9375,47.1874,47.4378,47.6867, 47.94,48.1799,48.4604,48.6187,49.144,48.5679,51.29 63,44.1111,66.6667}}

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[200],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{200,200}],Range [200],Method→”InteriorPoint”]] {0.015,{0.1875,0.4375,0.6875,0.9375,1.1875,1.4 375,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.18 75,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.937 5,5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875 ,6.9375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375, 8.6875,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875,

30 10.4375,10.6875,10.9375,11.1875,11.4375,11.6875,11 .9375,12.1875,12.4375,12.6875,12.9375,13.1875,13.4 375,13.6875,13.9375,14.1875,14.4375,14.6875,14.937 5,15.1875,15.4375,15.6875,15.9375,16.1875,16.4375, 16.6875,16.9375,17.1875,17.4375,17.6875,17.9375,18 .1875,18.4375,18.6875,18.9375,19.1875,19.4375,19.6 875,19.9375,20.1875,20.4375,20.6875,20.9375,21.187 5,21.4375,21.6875,21.9375,22.1875,22.4375,22.6875, 22.9375,23.1875,23.4375,23.6875,23.9375,24.1875,24 .4375,24.6875,24.9375,25.1875,25.4375,25.6875,25.9 375,26.1875,26.4375,26.6875,26.9375,27.1875,27.437 5,27.6875,27.9375,28.1875,28.4375,28.6875,28.9375, 29.1875,29.4375,29.6875,29.9375,30.1875,30.4375,30 .6875,30.9375,31.1875,31.4375,31.6875,31.9375,32.1 875,32.4375,32.6875,32.9375,33.1875,33.4375,33.687 5,33.9375,34.1875,34.4375,34.6875,34.9375,35.1875, 35.4375,35.6875,35.9375,36.1875,36.4375,36.6875,36 .9375,37.1875,37.4375,37.6875,37.9375,38.1875,38.4 375,38.6875,38.9375,39.1875,39.4375,39.6875,39.937 5,40.1875,40.4375,40.6875,40.9375,41.1875,41.4375, 41.6875,41.9375,42.1875,42.4375,42.6875,42.9375,43 .1875,43.4375,43.6875,43.9375,44.1875,44.4375,44.6 875,44.9375,45.1875,45.4375,45.6875,45.9375,46.187 5,46.4375,46.6875,46.9375,47.1874,47.4378,47.6867, 47.94,48.1799,48.4604,48.6187,49.144,48.5679,51.29 63,44.1111,66.6667}}

31 Lampiran 5 Studi kasus 8 dengan menggunakan Mathematica Kasus 8: Masalah OL dengan 500 kendala dan 500 variabel ( 𝑥𝑖 ≥ 0, i = 1, 2, 3, ..., 500) Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[500],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{500,500}],Range [500],Method→”Simplex”]] {14.243,{0.1875,0.4375,0.6875,0.9375,1.1875,1. 4375,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1 875,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.93 75,5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.687 5,6.9375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375 ,8.6875,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875 ,10.4375,10.6875,10.9375,11.1875,11.4375,11.6875,1 1.9375,12.1875,12.4375,12.6875,12.9375,13.1875,13. 4375,13.6875,13.9375,14.1875,14.4375,14.6875,14.93 75,15.1875,15.4375,15.6875,15.9375,16.1875,16.4375 ,16.6875,16.9375,17.1875,17.4375,17.6875,17.9375,1 8.1875,18.4375,18.6875,18.9375,19.1875,19.4375,19. 6875,19.9375,20.1875,20.4375,20.6875,20.9375,21.18 75,21.4375,21.6875,21.9375,22.1875,22.4375,22.6875 ,22.9375,23.1875,23.4375,23.6875,23.9375,24.1875,2 4.4375,24.6875,24.9375,25.1875,25.4375,25.6875,25. 9375,26.1875,26.4375,26.6875,26.9375,27.1875,27.43 75,27.6875,27.9375,28.1875,28.4375,28.6875,28.9375 ,29.1875,29.4375,29.6875,29.9375,30.1875,30.4375,3 0.6875,30.9375,31.1875,31.4375,31.6875,31.9375,32. 1875,32.4375,32.6875,32.9375,33.1875,33.4375,33.68 75,33.9375,34.1875,34.4375,34.6875,34.9375,35.1875 ,35.4375,35.6875,35.9375,36.1875,36.4375,36.6875,3 6.9375,37.1875,37.4375,37.6875,37.9375,38.1875,38. 4375,38.6875,38.9375,39.1875,39.4375,39.6875,39.93 75,40.1875,40.4375,40.6875,40.9375,41.1875,41.4375 ,41.6875,41.9375,42.1875,42.4375,42.6875,42.9375,4 3.1875,43.4375,43.6875,43.9375,44.1875,44.4375,44. 6875,44.9375,45.1875,45.4375,45.6875,45.9375,46.18 75,46.4375,46.6875,46.9375,47.1875,47.4375,47.6875 ,47.9375,48.1875,48.4375,48.6875,48.9375,49.1875,4 9.4375,49.6875,49.9375,50.1875,50.4375,50.6875,50. 9375,51.1875,51.4375,51.6875,51.9375,52.1875,52.43 75,52.6875,52.9375,53.1875,53.4375,53.6875,53.9375 ,54.1875,54.4375,54.6875,54.9375,55.1875,55.4375,5 5.6875,55.9375,56.1875,56.4375,56.6875,56.9375,57. 1875,57.4375,57.6875,57.9375,58.1875,58.4375,58.68 75,58.9375,59.1875,59.4375,59.6875,59.9375,60.1875 ,60.4375,60.6875,60.9375,61.1875,61.4375,61.6875,6 1.9375,62.1875,62.4375,62.6875,62.9375,63.1875,63. 4375,63.6875,63.9375,64.1875,64.4375,64.6875,64.93 75,65.1875,65.4375,65.6875,65.9375,66.1875,66.4375 ,66.6875,66.9375,67.1875,67.4375,67.6875,67.9375,6 8.1875,68.4375,68.6875,68.9375,69.1875,69.4375,69.

32 6875,69.9375,70.1875,70.4375,70.6875,70.9375,71.18 75,71.4375,71.6875,71.9375,72.1875,72.4375,72.6875 ,72.9375,73.1875,73.4375,73.6875,73.9375,74.1875,7 4.4375,74.6875,74.9375,75.1875,75.4375,75.6875,75. 9375,76.1875,76.4375,76.6875,76.9375,77.1875,77.43 75,77.6875,77.9375,78.1875,78.4375,78.6875,78.9375 ,79.1875,79.4375,79.6875,79.9375,80.1875,80.4375,8 0.6875,80.9375,81.1875,81.4375,81.6875,81.9375,82. 1875,82.4375,82.6875,82.9375,83.1875,83.4375,83.68 75,83.9375,84.1875,84.4375,84.6875,84.9375,85.1875 ,85.4375,85.6875,85.9375,86.1875,86.4375,86.6875,8 6.9375,87.1875,87.4375,87.6875,87.9375,88.1875,88. 4375,88.6875,88.9375,89.1875,89.4375,89.6875,89.93 75,90.1875,90.4375,90.6875,90.9375,91.1875,91.4375 ,91.6875,91.9375,92.1875,92.4375,92.6875,92.9375,9 3.1875,93.4375,93.6875,93.9375,94.1875,94.4375,94. 6875,94.9375,95.1875,95.4375,95.6875,95.9375,96.18 75,96.4375,96.6875,96.9375,97.1875,97.4375,97.6875 ,97.9375,98.1875,98.4375,98.6875,98.9375,99.1875,9 9.4375,99.6875,99.9375,100.188,100.438,100.688,100 .937,101.187,101.438,101.687,101.938,102.188,102.4 38,102.687,102.938,103.188,103.437,103.688,103.938 ,104.188,104.437,104.688,104.937,105.188,105.438,1 05.687,105.938,106.187,106.438,106.688,106.938,107 .188,107.438,107.687,107.938,108.188,108.438,108.6 87,108.938,109.188,109.437,109.688,109.937,110.187 ,110.438,110.688,110.938,111.188,111.438,111.687,1 11.938,112.187,112.438,112.688,112.938,113.188,113 .438,113.687,113.938,114.187,114.437,114.687,114.9 38,115.188,115.437,115.687,115.937,116.187,116.438 ,116.687,116.938,117.187,117.438,117.687,117.938,1 18.187,118.438,118.687,118.938,119.187,119.438,119 .687,119.938,120.187,120.438,120.687,120.938,121.1 87,121.438,121.687,121.938,122.187,122.438,122.685 ,122.944,123.168,123.495,123.516,124.453,122.642,1 29.074,110.778,166.667}}

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[500],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{500,500}],Range [500],Method→”InteriorPoint”]] {0.031,{0.187525,0.437503,0.687504,0.937505,1. 1875,1.4375,1.6875,1.9375,2.1875,2.4375,2.6875,2.9 375,3.1875,3.4375,3.6875,3.9375,4.1875,4.4375,4.68 75,4.9375,5.1875,5.4375,5.6875,5.9375,6.1875,6.437 5,6.6875,6.9375,7.1875,7.4375,7.6875,7.9375,8.1875 ,8.4375,8.6875,8.9375,9.1875,9.4375,9.6875,9.9375, 10.1875,10.4375,10.6875,10.9375,11.1875,11.4375,11 .6875,11.9375,12.1875,12.4375,12.6875,12.9375,13.1 875,13.4375,13.6875,13.9375,14.1875,14.4375,14.687 5,14.9375,15.1875,15.4375,15.6875,15.9375,16.1875, 16.4375,16.6875,16.9375,17.1875,17.4375,17.6875,17 .9375,18.1875,18.4375,18.6875,18.9375,19.1875,19.4

33 375,19.6875,19.9375,20.1875,20.4375,20.6875,20.937 5,21.1875,21.4375,21.6875,21.9375,22.1875,22.4375, 22.6875,22.9375,23.1875,23.4375,23.6875,23.9375,24 .1875,24.4375,24.6875,24.9375,25.1875,25.4375,25.6 875,25.9375,26.1875,26.4375,26.6875,26.9375,27.187 5,27.4375,27.6875,27.9375,28.1875,28.4375,28.6875, 28.9375,29.1875,29.4375,29.6875,29.9375,30.1875,30 .4375,30.6875,30.9375,31.1875,31.4375,31.6875,31.9 375,32.1875,32.4375,32.6875,32.9375,33.1875,33.437 5,33.6875,33.9375,34.1875,34.4375,34.6875,34.9375, 35.1875,35.4375,35.6875,35.9375,36.1875,36.4375,36 .6875,36.9375,37.1875,37.4375,37.6875,37.9375,38.1 875,38.4375,38.6875,38.9375,39.1875,39.4375,39.687 5,39.9375,40.1875,40.4375,40.6875,40.9375,41.1875, 41.4375,41.6875,41.9375,42.1875,42.4375,42.6875,42 .9375,43.1875,43.4375,43.6875,43.9375,44.1875,44.4 375,44.6875,44.9375,45.1875,45.4375,45.6875,45.937 5,46.1875,46.4375,46.6875,46.9375,47.1875,47.4375, 47.6875,47.9375,48.1875,48.4375,48.6875,48.9375,49 .1875,49.4375,49.6875,49.9375,50.1875,50.4375,50.6 875,50.9375,51.1875,51.4375,51.6875,51.9375,52.187 5,52.4375,52.6875,52.9375,53.1875,53.4375,53.6875, 53.9375,54.1875,54.4375,54.6875,54.9375,55.1875,55 .4375,55.6875,55.9375,56.1875,56.4375,56.6875,56.9 375,57.1875,57.4375,57.6875,57.9375,58.1875,58.437 5,58.6875,58.9375,59.1875,59.4375,59.6875,59.9375, 60.1875,60.4375,60.6875,60.9375,61.1875,61.4375,61 .6875,61.9375,62.1875,62.4375,62.6875,62.9375,63.1 875,63.4375,63.6875,63.9375,64.1875,64.4375,64.687 5,64.9375,65.1875,65.4375,65.6875,65.9375,66.1875, 66.4375,66.6875,66.9375,67.1875,67.4375,67.6875,67 .9375,68.1875,68.4375,68.6875,68.9375,69.1875,69.4 375,69.6875,69.9375,70.1875,70.4375,70.6875,70.937 5,71.1875,71.4375,71.6875,71.9375,72.1875,72.4375, 72.6875,72.9375,73.1875,73.4375,73.6875,73.9375,74 .1875,74.4375,74.6875,74.9375,75.1875,75.4375,75.6 875,75.9375,76.1875,76.4375,76.6875,76.9375,77.187 5,77.4375,77.6875,77.9375,78.1875,78.4375,78.6875, 78.9375,79.1875,79.4375,79.6875,79.9375,80.1875,80 .4375,80.6875,80.9375,81.1875,81.4375,81.6875,81.9 375,82.1875,82.4375,82.6875,82.9375,83.1875,83.437 5,83.6875,83.9375,84.1875,84.4375,84.6875,84.9375, 85.1875,85.4375,85.6875,85.9375,86.1875,86.4375,86 .6875,86.9375,87.1875,87.4375,87.6875,87.9375,88.1 875,88.4375,88.6875,88.9375,89.1875,89.4375,89.687 5,89.9375,90.1875,90.4375,90.6875,90.9375,91.1875, 91.4375,91.6875,91.9375,92.1875,92.4375,92.6875,92 .9375,93.1875,93.4375,93.6875,93.9375,94.1875,94.4 375,94.6875,94.9375,95.1875,95.4375,95.6875,95.937 5,96.1875,96.4375,96.6875,96.9375,97.1875,97.4375, 97.6875,97.9375,98.1875,98.4375,98.6875,98.9375,99 .1875,99.4375,99.6875,99.9375,100.188,100.438,100. 688,100.938,101.188,101.438,101.688,101.938,102.18

34 8,102.438,102.688,102.938,103.188,103.438,103.688, 103.938,104.188,104.438,104.688,104.938,105.188,10 5.438,105.688,105.938,106.188,106.438,106.688,106. 938,107.188,107.438,107.688,107.938,108.188,108.43 8,108.688,108.938,109.188,109.438,109.688,109.938, 110.188,110.438,110.688,110.938,111.188,111.438,11 1.688,111.938,112.188,112.438,112.688,112.938,113. 188,113.438,113.688,113.938,114.188,114.438,114.68 8,114.938,115.188,115.438,115.688,115.938,116.188, 116.438,116.688,116.938,117.188,117.438,117.688,11 7.938,118.188,118.438,118.688,118.938,119.188,119. 438,119.688,119.938,120.188,120.438,120.687,120.93 8,121.187,121.438,121.687,121.938,122.187,122.438, 122.685,122.944,123.168,123.495,123.516,124.453,12 2.642,129.074,110.778,166.667}}

35 Lampiran 6 Studi kasus 9 dengan menggunakan Mathematica Kasus 9: Masalah OL dengan 500 kendala dan 1000 variabel ( 𝑥𝑖 ≥ 0, i = 1, 2, 3, ..., 1000) Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[1000],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{500,1000}],Rang e[500],Method→”Simplex”]] {28.017,{0.1875,0.4375,0.6875,0.9375,1.1875,1.437 5,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1875 ,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.9375, 5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.6875,6 .9375,7.1875,7.4375,7.6875,7.9375,8.1875,8.4375,8. 6875,8.9375,9.1875,9.4375,9.6875,9.9375,10.1875,10 .4375,10.6875,10.9375,11.1875,11.4375,11.6875,11.9 375,12.1875,12.4375,12.6875,12.9375,13.1875,13.437 5,13.6875,13.9375,14.1875,14.4375,14.6875,14.9375, 15.1875,15.4375,15.6875,15.9375,16.1875,16.4375,16 .6875,16.9375,17.1875,17.4375,17.6875,17.9375,18.1 875,18.4375,18.6875,18.9375,19.1875,19.4375,19.687 5,19.9375,20.1875,20.4375,20.6875,20.9375,21.1875, 21.4375,21.6875,21.9375,22.1875,22.4375,22.6875,22 .9375,23.1875,23.4375,23.6875,23.9375,24.1875,24.4 375,24.6875,24.9375,25.1875,25.4375,25.6875,25.937 5,26.1875,26.4375,26.6875,26.9375,27.1875,27.4375, 27.6875,27.9375,28.1875,28.4375,28.6875,28.9375,29 .1875,29.4375,29.6875,29.9375,30.1875,30.4375,30.6 875,30.9375,31.1875,31.4375,31.6875,31.9375,32.187 5,32.4375,32.6875,32.9375,33.1875,33.4375,33.6875, 33.9375,34.1875,34.4375,34.6875,34.9375,35.1875,35 .4375,35.6875,35.9375,36.1875,36.4375,36.6875,36.9 375,37.1875,37.4375,37.6875,37.9375,38.1875,38.437 5,38.6875,38.9375,39.1875,39.4375,39.6875,39.9375, 40.1875,40.4375,40.6875,40.9375,41.1875,41.4375,41 .6875,41.9375,42.1875,42.4375,42.6875,42.9375,43.1 875,43.4375,43.6875,43.9375,44.1875,44.4375,44.687 5,44.9375,45.1875,45.4375,45.6875,45.9375,46.1875, 46.4375,46.6875,46.9375,47.1875,47.4375,47.6875,47 .9375,48.1875,48.4375,48.6875,48.9375,49.1875,49.4 375,49.6875,49.9375,50.1875,50.4375,50.6875,50.937 5,51.1875,51.4375,51.6875,51.9375,52.1875,52.4375, 52.6875,52.9375,53.1875,53.4375,53.6875,53.9375,54 .1875,54.4375,54.6875,54.9375,55.1875,55.4375,55.6 875,55.9375,56.1875,56.4375,56.6875,56.9375,57.187 5,57.4375,57.6875,57.9375,58.1875,58.4375,58.6875, 58.9375,59.1875,59.4375,59.6875,59.9375,60.1875,60 .4375,60.6875,60.9375,61.1875,61.4375,61.6875,61.9 375,62.1875,62.4375,62.6875,62.9375,63.1875,63.437 5,63.6875,63.9375,64.1875,64.4375,64.6875,64.9375, 65.1875,65.4375,65.6875,65.9375,66.1875,66.4375,66 .6875,66.9375,67.1875,67.4375,67.6875,67.9375,68.1 875,68.4375,68.6875,68.9375,69.1875,69.4375,69.687

36 5,69.9375,70.1875,70.4375,70.6875,70.9375,71.1875, 71.4375,71.6875,71.9375,72.1875,72.4375,72.6875,72 .9375,73.1875,73.4375,73.6875,73.9375,74.1875,74.4 375,74.6875,74.9375,75.1875,75.4375,75.6875,75.937 5,76.1875,76.4375,76.6875,76.9375,77.1875,77.4375, 77.6875,77.9375,78.1875,78.4375,78.6875,78.9375,79 .1875,79.4375,79.6875,79.9375,80.1875,80.4375,80.6 875,80.9375,81.1875,81.4375,81.6875,81.9375,82.187 5,82.4375,82.6875,82.9375,83.1875,83.4375,83.6875, 83.9375,84.1875,84.4375,84.6875,84.9375,85.1875,85 .4375,85.6875,85.9375,86.1875,86.4375,86.6875,86.9 375,87.1875,87.4375,87.6875,87.9375,88.1875,88.437 5,88.6875,88.9375,89.1875,89.4375,89.6875,89.9375, 90.1875,90.4375,90.6875,90.9375,91.1875,91.4375,91 .6875,91.9375,92.1875,92.4375,92.6875,92.9375,93.1 875,93.4375,93.6875,93.9375,94.1875,94.4375,94.687 5,94.9375,95.1875,95.4375,95.6875,95.9375,96.1875, 96.4375,96.6875,96.9375,97.1875,97.4375,97.6875,97 .9375,98.1875,98.4375,98.6875,98.9375,99.1875,99.4 375,99.6875,99.9375,100.188,100.438,100.688,100.93 7,101.187,101.438,101.687,101.938,102.188,102.438, 102.687,102.938,103.188,103.437,103.688,103.938,10 4.188,104.437,104.688,104.937,105.188,105.438,105. 687,105.938,106.187,106.438,106.688,106.938,107.18 8,107.438,107.687,107.938,108.188,108.438,108.687, 108.938,109.188,109.437,109.688,109.937,110.187,11 0.438,110.688,110.938,111.188,111.438,111.687,111. 938,112.187,112.438,112.688,112.938,113.188,113.43 8,113.687,113.938,114.187,114.437,114.687,114.938, 115.188,115.437,115.687,115.937,116.187,116.438,11 6.687,116.938,117.187,117.438,117.687,117.938,118. 187,118.438,118.687,118.938,119.187,119.438,119.68 7,119.938,120.187,120.438,120.687,120.938,121.187, 121.438,121.687,121.938,122.187,122.438,122.685,12 2.944,123.168,123.495,123.516,124.453,122.642,129. 074,110.778,166.667,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0

37 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.}}

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[1000],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{500,1000}],Rang e[500],Method→”InteriorPoint”]] {0.031,{0.187633,0.437506,0.687502,0.937502,1. 1875,1.4375,1.6875,1.9375,2.1875,2.4375,2.6875,2.9 375,3.1875,3.4375,3.6875,3.9375,4.1875,4.4375,4.68 75,4.9375,5.1875,5.4375,5.6875,5.9375,6.1875,6.437 5,6.6875,6.9375,7.1875,7.4375,7.6875,7.9375,8.1875 ,8.4375,8.6875,8.9375,9.1875,9.4375,9.6875,9.9375, 10.1875,10.4375,10.6875,10.9375,11.1875,11.4375,11 .6875,11.9375,12.1875,12.4375,12.6875,12.9375,13.1 875,13.4375,13.6875,13.9375,14.1875,14.4375,14.687 5,14.9375,15.1875,15.4375,15.6875,15.9375,16.1875, 16.4375,16.6875,16.9375,17.1875,17.4375,17.6875,17 .9375,18.1875,18.4375,18.6875,18.9375,19.1875,19.4 375,19.6875,19.9375,20.1875,20.4375,20.6875,20.937 5,21.1875,21.4375,21.6875,21.9375,22.1875,22.4375, 22.6875,22.9375,23.1875,23.4375,23.6875,23.9375,24 .1875,24.4375,24.6875,24.9375,25.1875,25.4375,25.6 875,25.9375,26.1875,26.4375,26.6875,26.9375,27.187 5,27.4375,27.6875,27.9375,28.1875,28.4375,28.6875, 28.9375,29.1875,29.4375,29.6875,29.9375,30.1875,30 .4375,30.6875,30.9375,31.1875,31.4375,31.6875,31.9 375,32.1875,32.4375,32.6875,32.9375,33.1875,33.437 5,33.6875,33.9375,34.1875,34.4375,34.6875,34.9375, 35.1875,35.4375,35.6875,35.9375,36.1875,36.4375,36 .6875,36.9375,37.1875,37.4375,37.6875,37.9375,38.1 875,38.4375,38.6875,38.9375,39.1875,39.4375,39.687 5,39.9375,40.1875,40.4375,40.6875,40.9375,41.1875, 41.4375,41.6875,41.9375,42.1875,42.4375,42.6875,42 .9375,43.1875,43.4375,43.6875,43.9375,44.1875,44.4 375,44.6875,44.9375,45.1875,45.4375,45.6875,45.937 5,46.1875,46.4375,46.6875,46.9375,47.1875,47.4375, 47.6875,47.9375,48.1875,48.4375,48.6875,48.9375,49 .1875,49.4375,49.6875,49.9375,50.1875,50.4375,50.6 875,50.9375,51.1875,51.4375,51.6875,51.9375,52.187 5,52.4375,52.6875,52.9375,53.1875,53.4375,53.6875, 53.9375,54.1875,54.4375,54.6875,54.9375,55.1875,55

38 .4375,55.6875,55.9375,56.1875,56.4375,56.6875,56.9 375,57.1875,57.4375,57.6875,57.9375,58.1875,58.437 5,58.6875,58.9375,59.1875,59.4375,59.6875,59.9375, 60.1875,60.4375,60.6875,60.9375,61.1875,61.4375,61 .6875,61.9375,62.1875,62.4375,62.6875,62.9375,63.1 875,63.4375,63.6875,63.9375,64.1875,64.4375,64.687 5,64.9375,65.1875,65.4375,65.6875,65.9375,66.1875, 66.4375,66.6875,66.9375,67.1875,67.4375,67.6875,67 .9375,68.1875,68.4375,68.6875,68.9375,69.1875,69.4 375,69.6875,69.9375,70.1875,70.4375,70.6875,70.937 5,71.1875,71.4375,71.6875,71.9375,72.1875,72.4375, 72.6875,72.9375,73.1875,73.4375,73.6875,73.9375,74 .1875,74.4375,74.6875,74.9375,75.1875,75.4375,75.6 875,75.9375,76.1875,76.4375,76.6875,76.9375,77.187 5,77.4375,77.6875,77.9375,78.1875,78.4375,78.6875, 78.9375,79.1875,79.4375,79.6875,79.9375,80.1875,80 .4375,80.6875,80.9375,81.1875,81.4375,81.6875,81.9 375,82.1875,82.4375,82.6875,82.9375,83.1875,83.437 5,83.6875,83.9375,84.1875,84.4375,84.6875,84.9375, 85.1875,85.4375,85.6875,85.9375,86.1875,86.4375,86 .6875,86.9375,87.1875,87.4375,87.6875,87.9375,88.1 875,88.4375,88.6875,88.9375,89.1875,89.4375,89.687 5,89.9375,90.1875,90.4375,90.6875,90.9375,91.1875, 91.4375,91.6875,91.9375,92.1875,92.4375,92.6875,92 .9375,93.1875,93.4375,93.6875,93.9375,94.1875,94.4 375,94.6875,94.9375,95.1875,95.4375,95.6875,95.937 5,96.1875,96.4375,96.6875,96.9375,97.1875,97.4375, 97.6875,97.9375,98.1875,98.4375,98.6875,98.9375,99 .1875,99.4375,99.6875,99.9375,100.188,100.438,100. 688,100.938,101.188,101.438,101.688,101.938,102.18 8,102.438,102.688,102.938,103.188,103.438,103.688, 103.938,104.188,104.438,104.688,104.938,105.188,10 5.438,105.688,105.938,106.188,106.438,106.688,106. 938,107.188,107.438,107.688,107.938,108.188,108.43 8,108.688,108.938,109.188,109.438,109.688,109.938, 110.188,110.438,110.688,110.938,111.188,111.438,11 1.688,111.938,112.188,112.438,112.688,112.938,113. 188,113.438,113.688,113.938,114.188,114.438,114.68 8,114.938,115.188,115.438,115.688,115.938,116.188, 116.438,116.688,116.938,117.188,117.438,117.688,11 7.938,118.188,118.438,118.688,118.938,119.188,119. 438,119.688,119.938,120.188,120.438,120.687,120.93 8,121.187,121.438,121.687,121.938,122.187,122.438, 122.685,122.944,123.168,123.495,123.516,124.453,12 2.642,129.074,110.778,166.667,1.33199*10^7,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.

39 ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0 .,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.}}

40 Lampiran 7 Studi kasus 10 dengan menggunakan Mathematica Kasus 10: Masalah OL dengan 100 kendala dan 200000 variabel ( 𝑥𝑖 ≥ 0, i = 1, 2, 3, ..., 200000) Penyelesaian komputasi dengan metode simpleks: input: Timing[LinearProgramming[Range[200000],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{100,200000}],Ra nge[100],Method→”Simplex”]] {227.808,{0.1875,0.4375,0.6875,0.9375,1.1875,1. 4375,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1 875,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.93 75,5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,6.687 5,6.9375,7.1875,7.4375,7.6875,<<199938>>,0.,0.,0., 0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.}}

Penyelesaian komputasi dengan metode titik interior: input: Timing[LinearProgramming[Range[200000],SparseArray

output:

[{Band[{1,1}] → 3.,Band[{1,2}] → 1.},{100,200000}],Ra nge[100],Method→”InteriorPoint”]] {0.124,{0.1875,0.4375,0.6875,0.9375,1.1875,1.437 5,1.6875,1.9375,2.1875,2.4375,2.6875,2.9375,3.1875 ,3.4375,3.6875,3.9375,4.1875,4.4375,4.6875,4.9375, 5.1875,5.4375,5.6875,5.9375,6.1875,6.4375,<<199948 >>,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0.,0. ,0.,0.,0.,0.,0.,0.,0.,0.}}

41

RIWAYAT HIDUP Penulis lahir di Cirebon tanggal 13 Juli 1991, putra pertama dari Bapak Sanija dan Ibu Rokani. Penulis menempuh pendidikan pertama di TK Nira Indria Palimanan Barat Cirebon selama 2 tahun dari tahun 1995 sampai 1997. Selanjutnya masuk Sekolah Dasar Palimanan Timur 3 pada tahun 1997 sampai 2003. Penulis masuk Sekolah Menengah Pertama Negeri 1 Palimanan pada tahun 2003 hingga 2006, kemudian melanjutkan pendidikan di Sekolah Menengah Atas Negeri 1 Palimanan pada tahun 2006 yang diselesaikan pada tahun 2009. Pada tingkat Sekolah Menengah Atas pernah mengikuti Olimpiade Matematika tingkat Kabupaten dan Kota. Penulis melanjutkan pendidikan di Perguruan Tinggi Negeri pada tahun 2009 diterima di Institut Pertanian Bogor melalui jalur Undangan Seleksi Masuk IPB (USMI) dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Selama kuliah penulis aktif dalam organisasi kemahasiswaan Himpunan Profesi Gumatika sebagai Staf Divisi Pemberdayaan Sumber Daya Manusia pada tahun 2010-2011 dan Staf Divisi Math Event pada tahun 2011-2012, dan juga organisasi UKM Musik Agriculture Expression, serta organisasi daerah Ikatan Keluarga Cirebon sebagai Staf Departemen Sosial dan Kesejahteraan tahun 2010-2011 dan Kepala Departemen Sosial dan Kesejahteraan pada tahun 2011-2012. Penulis aktif sebagai pengajar Tingkat Persiapan Bersama dan Sekolah Menengah Atas tahun 2010-2011. Penulis juga aktif dalam kepanitian dan koordinator di berbagai acara kemahasiswaan, diantaranya Masa Perkenalan Kampus Mahasiswa Baru, IPB Mathematics Challenges, Matematika Ria, Masa Perkenalan Departemen. Penulis pernah menjadi ketua acara “Ramah Tamah Civitas Matematika” pada tahun 2012. Penulis pernah menjadi pemakalah Seminar Nasional SEMIRATA 2014 Bidang MIPA BKS-PTN Barat.