PERBANDINGAN ANALISIS SENSITIVITAS MENGGUNAKAN PARTISI OPTIMAL DAN BASIS OPTIMAL PADA OPTIMASI LINEAR MIRNA SARI DEWI

PERBANDINGAN ANALISIS SENSITIVITAS MENGGUNAKAN PARTISI OPTIMAL DAN BASIS OPTIMAL PADA OPTIMASI LINEAR

MIRNA SARI DEWI

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

PERNYATAAN MENGENAI SKRIPSI DAN SUMBER INFORMASI SERTA PELIMPAHAN HAK CIPTA Dengan ini saya menyatakan bahwa skripsi berjudul Perbandingan Analisis Sensitivitas Menggunakan Partisi Optimal dan Basis Optimal pada Optimasi Linear 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 skripsi ini. Dengan ini saya melimpahkan hak cipta dari karya tulis saya kepada Institut Pertanian Bogor. Bogor, Desember 2013 Mirna Sari Dewi NIM G54090042

ABSTRAK MIRNA SARI DEWI. Perbandingan Analisis Sensitivitas Menggunakan Partisi Optimal dan Basis Optimal pada Optimasi Linear. Dibimbing oleh BIB PARUHUM SILALAHI dan PRAPTO TRI SUPRIYO. Analisis sensitivitas menjelaskan sampai sejauh mana pengaruh perubahan parameter-parameter model optimasi linear, yaitu koefisien fungsi tujuan dan nilai ruas kanan kendala, terhadap penyelesaian optimal. Analisis sensitivitas yang biasa digunakan adalah dengan pendekatan basis optimal berdasarkan metode simpleks. Pada karya ilmiah ini dibahas analisis sensitivitas dengan pendekatan lain yaitu analisis menggunakan partisi optimal yang unik berdasarkan metode interior point untuk menentukan range dan shadow price. Tujuan penelitian ini adalah memaparkan analisis sensitivitas menggunakan partisi optimal berdasarkan buku acuan yang berjudul Interior Point Methods for Linear Optimization pada subbab Sensitivity Analysis yang disusun oleh C. Roos, T. Terlaky, dan J. PH. Vial sehingga dapat ditentukan nilai shadow price dan range serta membandingkan hasil yang diperoleh dengan yang dihasilkan oleh metode simpleks dengan bantuan perangkat lunak LINDO 6.1. Hasil analisis sensitivitas yang diperoleh dengan pendekatan partisi optimal juga lebih akurat dari pada menggunakan pendekatan basis optimal (metode simpleks) terutama untuk kasus yang memiliki solusi optimal primal atau dual yang tidak unik. Namun saat masalah primal dan masalah dual memiliki solusi optimal yang unik, metode simpleks dan pendekatan partisi optimal menghasilkan informasi yang persis sama. Kata kunci: analisis sensitivitas, partisi optimal, range, shadow price ABSTRACT MIRNA SARI DEWI. Comparing Optimal Partitions and Optimal Bases of Sensitivity Analysis on Linear Optimizations. Supervised by BIB PARUHUM SILALAHI and PRAPTO TRI SUPRIYO. Sensitivity analysis is studying the effect of parameters of the linear optimization model, i.e. the coefficients of objective function and right-hand side value constraints to the optimal solution. Sensitivity analysis used in the classical approach (the simplex method) is based on the optimal basis. This paper presents briefly sensitivity analysis by using the unique optimal partition based on the interior point method to determine the range and shadow price. The purpose of this study is to present the sensitivity analysis of the optimal partition based on a reference book entitled Interior Point Methods for Linear Optimization in Section Sensitivity Analysis prepared by C. Roos, T. Terlaky, and J. PH. Vial so that can be determined the shadow price and range value and compare the obtained results with those produced by the simplex method with the help of software LINDO 6.1. Sensitivity analysis obtained results with the optimal partition approach is also more accurate than using the optimal bases approach (simplex method), especially for cases that have a primal or dual optimal solution is not unique. But when the primal and the dual has a unique optimal solution, simplex method and optimal partition approach produces the same information Keywords: sensitivity analysis, optimal partition, range, shadow price

PERBANDINGAN ANALISIS SENSITIVITAS MENGGUNAKAN PARTISI OPTIMAL DAN BASIS OPTIMAL PADA OPTIMASI LINEAR

MIRNA SARI DEWI

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 2013

Judul Skripsi : Perbandingan Analisis Sensitivitas Menggunakan Partisi Optimal dan Basis Optimal pada Optimasi Linear Nama : Mirna Sari Dewi NIM : G54090042

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 Januari 2013 ini ialah analisis sensitivitas, dengan judul Perbandingan Analisis Sensitivitas Menggunakan Partisi Optimal dan Basis Optimal pada Optimasi Linear. Terima kasih penulis ucapkan kepada Bapak Dr Ir Bib Paruhum Silalahi, MKom dan Drs Prapto Tri Supriyo, MKom selaku pembimbing, serta Ibu Dra Farida Hanum, MSi selaku dosen penguji yang telah banyak memberi saran, motivasi dan bimbingan dalam penulisan karya ilmiah ini. Ucapan terima kasih juga penulis berikan kepada seluruh mahasiswa Matematika angkatan 44, 45, 46, 47, 48, dan 49 serta teman-teman 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. Terima kasih juga penulis berikan kepada seluruh staf Departemen Matematika dan staf Fakultas Matematika dan Ilmu Pengetahuan Alam. Ungkapan terima kasih juga tak lupa penulis sampaikan kepada ayah, ibu, serta seluruh keluarga, atas segala doa dan kasih sayangnya. Semoga karya ilmiah ini bermanfaat.

Bogor, Desember 2013 Mirna Sari Dewi

DAFTAR ISI DAFTAR TABEL

vi

DAFTAR GAMBAR

vi

DAFTAR LAMPIRAN

vi

I PENDAHULUAN

1

1.1 Latar Belakang

1

1.2 Tujuan Penelitian

1

1.3 Metode Penelitian

1

II TINJAUAN PUSTAKA

2

2.1 Masalah Optimasi Linear

2

2.2 Analisis Sensitivitas

3

2.3 Makna Simbol

3

2.4 Bentuk Khusus

4

III PEMBAHASAN

4

3.1 Primal Dual

4

3.2 Primal-Dual dengan Pendekatan Partisi Optimal

5

3.3 Ranges dan Shadow Prices

6

3.4 Analisis Sensitivitas dengan Pendekatan Klasik

7

IV STUDI KASUS

8

V SIMPULAN

15

DAFTAR PUSTAKA

15

LAMPIRAN

16

RIWAYAT HIDUP

21

DAFTAR TABEL 1 2 3 4 5 6

Range dan shadow price yang diperoleh dari hasil perhitungan (Kasus I) Range dan shadow price yang diperoleh dari LINDO (Kasus I) Range dan shadow price yang diperoleh dari hasil perhitungan (Kasus II) Range dan shadow price yang diperoleh dari LINDO (Kasus II) Range dan shadow price yang diperoleh dari hasil perhitungan (Kasus III) Range dan shadow price yang diperoleh dari LINDO (Kasus III)

11 11 12 13 14 14

DAFTAR GAMBAR 1 2 3 4 5

Contoh daerah fisibel Fungsi nilai optimal untuk 𝑐𝑗 Daerah fisibel (D) kasus I Daerah fisibel (D) kasus II Daerah fisibel (D) kasus III

2 6 8 12 13

DAFTAR LAMPIRAN 1 Studi kasus I dengan menggunakan LINDO 2 Studi kasus II dengan menggunakan LINDO 3 Studi kasus III dengan menggunakan LINDO

16 17 19

1

I PENDAHULUAN 1.1 Latar Belakang Saat ini manfaat optimasi sangat terasa dan diterima secara luas sebagai alat yang berguna dalam berbagai masalah kehidupan. Sebagian besar perusahaan menggunakan pemodelan untuk memecahkan berbagai masalah praktis; sebagai contoh masalah transportasi, perencanaan produksi, masalah keputusan investasi, masalah pencampuran, masalah lokasi dan alokasi, dan masih banyak lagi. Salah satu jenis optimasi adalah optimasi linear. Secara matematis penyelesaian optimal sebuah kasus optimasi linear selalu berhubungan dengan penyelesaian optimal sebuah kasus optimasi linear yang lain. Bentuk hubungan ini dikenal sebagai dualitas di dalam optimasi linear. Penyelesaian optimal kasus optimasi linear dengan algoritme simpleks pada dasarnya mengandung informasi yang sangat berharga berkaitan dengan perubahan parameter-paremeter dan variabel-variabel yang digunakan. Sejauh mana perubahan itu berperan terhadap penyelesaian optimal adalah informasi yang sangat berharga guna menurunkan alternatif-alternatif keputusan selain keputusan optimal. Informasi ini dapat diperoleh dengan cara analisis sensitivitas. Analisis sensitivitas menjelaskan sampai sejauh mana pengaruh perubahan parameter-parameter model optimasi linear, yaitu koefisien fungsi tujuan dan nilai ruas kanan kendala, terhadap penyelesaian optimal. Analisis sensitivitas yang biasa digunakan adalah dengan pendekatan klasik (metode simpleks) berdasarkan basis optimal. Pada karya ilmiah ini dibahas analisis sensitivitas dengan pendekatan lain yaitu analisis menggunakan partisi optimal yang unik berdasarkan metode interior point. 1.2 Tujuan Karya ilmiah ini bertujuan: 1 memaparkan analisis sensitivitas dengan partisi optimal berdasarkan buku acuan yang berjudul Interior Point Methods for Linear Optimization pada subbab Sensitivity Analysis yang disusun oleh C. Roos, T. Terlaky dan J. PH. Vial, kemudian menentukan nilai shadow price dan range, 2 untuk masalah yang sama dilakukan juga analisis sensitivitas menggunakan metode simpleks dengan bantuan perangkat lunak LINDO 6.1, 3 membandingkan hasil yang diperoleh dengan kedua pendekatan. 1.3 Metode Penelitian Metode yang digunakan dalam penulisan karya ilmiah ini adalah dengan dua pendekatan: 1 studi literatur, 2 penyelesaian masalah-masalah optimasi linear menggunakan perangkat lunak LINDO.

2

II TINJAUAN PUSTAKA 2.1 Masalah Optimasi Linear Model optimasi linear meliputi tiga unsur utama yaitu: 1 fungsi tujuan 2 variabel keputusan 3 kendala Optimasi linear merupakan sebuah model untuk menemukan suatu nilai variabel keputusan yang optimal dengan cara memaksimumkan atau meminimumkan fungsi tujuan terhadap kendala-kendala (Winston 2004). Dalam model optimasi linear, tujuan yang hendak dicapai harus diwujudkan ke dalam sebuah fungsi linear. Selanjutnya fungsi itu dimaksimumkan atau diminimumkan terhadap kendala-kendala yang ada sehingga fungsi linear tersebut dapat dikatakan sebagai fungsi tujuan. Variabel keputusan adalah variabel persoalan yang akan memengaruhi nilai tujuan yang hendak dicapai. Cara untuk menentukan variabel-variabel keputusan ini adalah dengan mengajukan pertanyaan: keputusan apa yang harus dibuat agar nilai fungsi tujuan menjadi maksimum atau minimum. Misalkan, 𝑥 adalah jumlah bangku yang harus diproduksi, maka 𝑥 adalah variabel keputusan (Siswanto 2007). Pembatasan terhadap nilai-nilai variabel keputusan disebut kendala. Misalkan, 𝑥 harus berada antara 1 dan 5, maka kendalanya dapat dituliskan menjadi 𝑥 ≥ 1 dan 𝑥 ≤ 5 (Winston 2004). Untuk masalah maksimisasi, solusi optimal pada optimasi linear adalah suatu titik pada daerah fisibel dengan nilai fungsi tujuan paling besar sedangkan untuk masalah minimisasi, solusi optimal pada optimasi linear adalah suatu titik pada daerah fisibel dengan nilai fungsi tujuan paling kecil. Daerah fisibel adalah himpunan titik-titik yang memenuhi semua kendala dan pembatasan tanda pada optimasi linear tersebut (Winston 2004). Contoh: maksimumkan 𝑧 = 2𝑥 + 2𝑦 dengan kendala 𝑥 + 2𝑦 ≤ 4 3𝑥 + 2𝑦 ≤ 6 𝑥, 𝑦 ≥ 0. Daerah fisibel dari masalah optimasi linear tersebut dapat dilihat pada Gambar 1.

Gambar 1 Contoh daerah fisibel

3

Dalam menentukan solusi optimal pada optimasi linear, kendala pada model optimasi linear haruslah berbentuk standar, yaitu dengan menambahkan variabel slack dan variabel surplus. Variabel slack adalah variabel yang berfungsi untuk menampung sisa kapasitas pada kendala yang berupa pembatas. Misalkan, kendala suatu masalah optimasi linear adalah 2𝑥 + 𝑦 ≤ 2. Bentuk standarnya yaitu 2𝑥 + 𝑦 + 𝑠 = 2, dengan 𝑠 adalah variabel slack. Variabel surplus adalah variabel yang berfungsi untuk menampung kelebihan nilai ruas kiri pada kendala yang berupa syarat. Misalkan, kendala suatu masalah optimasi linear adalah 2𝑥 + 𝑦 ≥ 2. Bentuk standarnya yaitu 2𝑥 + 𝑦 − 𝑠 = 2, dengan 𝑠 adalah variabel surplus (Siswanto 2007). Metode simpleks menghasilkan solusi basis pada optimasi linear. Solusi basis untuk 𝐴𝑥 = 𝑏 (dengan 𝑚 persamaan linear dan 𝑛 variabel 𝑛 ≥ 𝑚) diperoleh dengan menetapkan 𝑛 − 𝑚 variabel (variabel nonbasis) sama dengan nol dan memecahkan nilai-nilai dari 𝑚 variabel (variabel basis) yang tersisa. Jika 𝑛 − 𝑚 variabel sama dengan nol maka akan menghasilkan nilai yang unik untuk 𝑚 variabel yang tersisa, dengan kata lain, kolom-kolom untuk 𝑚 variabel yang tersisa adalah bebas linear. Solusi basis yang semua variabelnya taknegatif disebut basic feasible solution (Winston 2004). Dua buah vektor taknegatif 𝑥 dan 𝑠 dalam ℝ𝑛 dikatakan complementary vector jika 𝑥 𝑇 𝑠 = 0. Jika berlaku juga 𝑥 + 𝑠 > 0, maka 𝑥 dan 𝑠 disebut strictly complementary vector (Roos et al. 2006). 2.2 Analisis Sensitivitas Analisis sensitivitas menjelaskan sampai sejauh mana pengaruh perubahan parameter-parameter model optimasi linear, yaitu koefisien fungsi tujuan dan nilai ruas kanan kendala, terhadap penyelesaian optimal. Analisis sensitivitas parameter koefisien fungsi tujuan adalah persoalan penentuan batas atas dan batas bawah nilai koefisien fungsi tujuan dimana pada interval itu solusi optimal variabel keputusan tidak berubah. Analisis sensitivitas parameter nilai ruas kanan kendala adalah persoalan penentuan batas atas dan batas bawah nilai ruas kanan kendala dimana pada interval itu nilai dual price atau shadow price tidak berubah. Shadow price, disebut juga dual price, merupakan tambahan nilai fungsi tujuan yang terjadi karena tambahan satu unit nilai ruas kanan kendala (Siswanto 2007). Hubungan kenaikan suatu nilai fungsi tujuan dan suatu nilai shadow price ini bersifat linear dan hanya valid dalam interval (range) tertentu. 2.3 Makna Simbol Simbol cT 𝑥 𝑦 𝑠 𝑚 ×𝑛 ℝ

Makna vektor baris dari 𝑐 vektor kolom dari 𝑥 vektor kolom dari 𝑦 vektor kolom dari 𝑠 himpunan matriks berukuran 𝑚 × 𝑛 dengan entri bilangan real

4

Vektor baris adalah suatu matriks berukuran 1 × 𝑛, dengan n adalah bilangan-bilangan real, sedangkan vektor kolom adalah suatu matriks berukuran 𝑥1 𝑥2 𝑛 × 1, dengan n adalah bilangan-bilangan real (Leon 1998). Misalkan 𝑥 = ⋮ , 𝑥𝑛 maka 𝑥 adalah vektor kolom. 2.4 Bentuk Khusus Penyelesaian kasus optimasi linear dapat menyimpang dari perilaku umum. Hasil penyelesaian yang menyimpang ini dikelompokkan ke dalam kasus-kasus khusus optimasi linear. Kasus-kasus tersebut ialah degenerasi, solusi optimal jamak, tidak fisibel (infeasible), dan tidak terbatas. Sebuah optimasi linear (OL) dikatakan degenerasi jika memiliki setidaknya satu basic feasible solution dengan satu variabel basis yang bernilai nol (Winston 2004). Solusi optimal jamak adalah penyelesaian sebuah kasus optimasi linear di mana titik sudut ekstrem yang menghasilkan nilai optimal fungsi tujuan terdapat lebih dari satu titik (Siswanto 2007). Kendala pada kasus OL pada umummya membentuk suatu daerah fisibel, namun jika kendala pada kasus OL tidak membentuk suatu daerah fisibel atau daerah fisibelnya adalah himpunan kosong maka kasus tersebut dikatakan tidak fisibel (infeasible). Kasus nilai fungsi tujuan tidak terbatas terjadi bila susunan kendala membentuk sebuah daerah fisibel terbuka yang memiliki luas tidak terbatas. Untuk masalah maksimisasi, kasus nilai fungsi tujuan tidak terbatas terjadi jika daerah fisibel terbuka ke atas dan fungsi tujuan dimaksimumkan terhadap daerah fisibel ini. Sedangkan untuk masalah minimisasi, kasus nilai fungsi tujuan tidak terbatas terjadi jika daerah fisibel terbuka ke bawah dan fungsi tujuan diminimumkan terhadap daerah fisibel ini (Winston 2004).

III PEMBAHASAN 3.1 Primal-Dual Setiap masalah OL dapat dimodelkan secara matematis ke suatu bentuk yang disebut bentuk primal dan bentuk dual. Format standar bentuk masalah primal (P) dan masalah dual (D) dari suatu OL adalah sebagai berikut: (P) min { 𝑐 𝑇 𝑥 ∶ 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 }, (D) max { 𝑏𝑇 𝑦 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠 ≥ 0 }, dengan 𝑚 persamaan linear dan 𝑛 variabel, c, x, s ∈ ℝn dan b, y ∈ ℝm, A adalah matriks di ℝ𝑚 × 𝑛 dengan pangkat m. Misalkan nilai optimal (P) dan (D) berturut-turut dilambangkan dengan 𝑣 𝑐 = min { 𝑐 𝑇 𝑥 ∶ 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 }, 𝑣 𝑏 = max { 𝑏𝑇 𝑦 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠 ≥ 0 }.

5

Misalkan daerah fisibel masalah (P) dan masalah (D) dilambangkan dengan P ≔ { 𝑥 ∈ ℝ𝑛 ∶ 𝐴𝑥 = 𝑏, 𝑥 ≥ 0 }, D ≔ {(𝑦, 𝑠) ∈ ℝ𝑚 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠 ≥ 0 }. Jika (P) dan (D) keduanya fisibel maka solusi optimal dari (P) dan (D) dapat dilambangkan oleh 𝑃 ∗ dan 𝐷∗ , dengan 𝑃∗ ≔ 𝑥 ∈ 𝑃 ∶ 𝑐𝑇 𝑥 = 𝑣 𝑐 , 𝐷∗ ≔ { 𝑦, 𝑠 ∈ 𝐷 ∶ 𝑏𝑇 𝑦 = 𝑣 𝑏 }. 3.2 Primal-Dual dengan Pendekatan Partisi Optimal Berikut adalah teorema yang mendasari pembentukan partisi optimal. Teorema 1 (Teorema Dualitas) Jika (P) dan (D) fisibel maka kedua masalah memiliki solusi optimal. Kemudian, 𝑥 ∈ 𝑃 dan (𝑦, 𝑠) ∈ 𝐷, ini adalah solusi yang optimal jika dan hanya jika 𝑥 𝑇 𝑠 = 0. Jika tak satu pun dari dua masalah memiliki solusi yang optimal, maka keduanya (P) dan (D) tidak fisibel atau salah satu dari dua masalah adalah tidak fisibel dan yang lain tak terbatas (Roos et al. 2006). Teorema 2 (Teorema Goldman-Tucker) Jika (P) dan (D) fisibel maka terdapat strictly complementary optimal solution, yaitu suatu pasangan solusi optimal (𝑥, 𝑠) dengan 𝑥 + 𝑠 > 0 (Roos et al. 2006). Berdasarkan teorema tersebut, maka dapat didefinisikan partisi optimal dari (P) dan (D), yakni 𝐵 ∶= {𝑖 ∶ 𝑥𝑖 > 0 untuk suatu 𝑥 ∈ 𝑃∗ }, ∶= {𝑖 ∶ 𝑠𝑖 > 0 untuk suatu (𝑦, 𝑠) ∈ 𝐷∗ }. 𝑁 Teorema Dualitas (Teorema 1) berimplikasi bahwa 𝐵 ∩ 𝑁 = ∅, dan teorema Goldman-Tucker (Teorema 2) berimplikasi 𝐵 ∪ 𝑁 = {1, 2, … , 𝑛}. Berikut adalah lema tentang partisi optimal. Notasi 𝑥𝐵 dan 𝑥𝑁 mengacu pada pembatasan vektor 𝑥 ∈ ℝ𝑛 dengan indeks 𝑥 masing-masing adalah anggota himpunan 𝐵 dan 𝑁. 𝐴𝐵 melambangkan pembatasan 𝐴 terhadap kolom dengan indeks anggota himpunan 𝐵, dan 𝐴𝑁 pembatasan 𝐴 terhadap kolom dengan indeks anggota himpunan 𝑁. Lema 1 Misalkan 𝑥 ∗ ∈ 𝑃∗ dan (𝑦 ∗ , 𝑠 ∗ ) ∈ 𝐷∗ . Diperoleh 𝑃∗ = {𝑥 ∶ 𝑥 ∈ 𝑃, 𝑥 𝑇 𝑠 ∗ = 0}, 𝐷∗ = 𝑦, 𝑠 : 𝑦, 𝑠 ∈ 𝐷, 𝑠 𝑇 𝑥 ∗ = 0 (Roos et al. 2006). Lema 2 Diberikan partisi optimal (𝐵, 𝑁) dari (P) dan (D), himpunan solusi optimal dari kedua masalah tersebut adalah 𝑃∗ = {𝑥 ∶ 𝑥 ∈ 𝑃, 𝑥𝑁 = 0}, ∗ 𝐷 = 𝑦, 𝑠 : 𝑦, 𝑠 ∈ 𝐷, 𝑠𝐵 = 0 (Roos et al. 2006).

6

Berdasarkan Lema 2 maka sekarang 𝑃 ∗ dan 𝐷∗ , dapat dinyatakan dengan syarat-syarat partisi optimal menjadi, 𝑃∗ = {𝑥 ∶ 𝐴𝑥 = 𝑏, 𝑥𝐵 ≥ 0, 𝑥𝑁 = 0}, ∗ 𝐷 = 𝑦, 𝑠 : 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠𝐵 = 0, 𝑠𝑁 ≥ 0 . 3.3 Ranges dan Shadow Prices Analisis sensitivitas ialah suatu analisis untuk menentukan shadow price dan range dari semua koefisien 𝑏 (nilai dari ruas kanan kendala primal) dan 𝑐 (nilai dari ruas kanan kendala dual). Pada suatu kasus, nilai koefisien 𝑏 atau 𝑐 mungkin saja merupakan break point (titik patahan). Jika koefisien tersebut adalah break point, maka koefisien tersebut memiliki dua shadow price: shadow price kiri dan shadow price kanan. Namun jika koefisien tersebut bukan suatu break point, maka terdapat sebuah shadow price yang berada pada suatu interval linearitas terbuka dan range dari koefisien berada pada interval linearitas tersebut. Gambar 2 berikut memperlihatkan suatu contoh perubahan nilai optimal untuk perubahan nilai 𝑐𝑗 .

Gambar 2 Fungsi nilai optimal untuk cj Dari Gambar 2 jika 𝑐𝑗 bernilai 1 atau 2 maka 𝑐𝑗 merupakan suatu break point terhadap nilai optimalnya sehingga 𝑐𝑗 memiliki dua nilai shadow price, sedangkan jika 𝑐𝑗 bukan suatu break point terhadap nilai optimalnya maka 𝑐𝑗 memiliki satu nilai shadow price (Jansen et al. 1997). Misalkan 𝑥 ∗ adalah solusi optimal dari (P) dan (𝑦 ∗ , 𝑠 ∗ ) adalah solusi optimal dari (D). Berdasarkan pendekatan partisi optimal range 𝑏𝑖 didapat dengan meminimumkan dan memaksimumkan 𝑏𝑖 (Roos et al. 2006) dengan {𝑏𝑖 ∶ 𝐴𝑥 = 𝑏, 𝑥 ≥ 0, 𝑥 𝑇 𝑠 ∗ = 0}. (1) Shadow price kiri dan kanan dari 𝑏𝑖 ditentukan dengan meminimumkan dan memaksimumkan 𝑦𝑖 dengan 𝑦𝑖 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠 ≥ 0, 𝑠 𝑇 𝑥 ∗ = 0 . (2) Untuk range 𝑐𝑗 diperoleh dengan meminimumkan dan memaksimumkan nilai 𝑐𝑗 dengan 𝑐𝑗 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠 ≥ 0, 𝑠 𝑇 𝑥 ∗ = 0 . (3)

7

Shadow price kiri dan kanan dari 𝑐𝑗 ditentukan dengan meminimumkan dan memaksimumkan 𝑥𝑗 dengan (4) {𝑥𝑗 ∶ 𝐴𝑥 = 𝑏, 𝑥 ≥ 0, 𝑥 𝑇 𝑠 ∗ = 0}. Jika (P) dan (D) fisibel maka formula untuk range dan shadow price koefisien 𝑏 dan 𝑐 dapat disederhanakan sebagai berikut. Formula (1) dapat dirumuskan menjadi {𝑏𝑖 ∶ 𝐴𝑥 = 𝑏, 𝑥𝐵 ≥ 0, 𝑥𝑁 = 0} (5) dan (2) menjadi 𝑦𝑖 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠𝐵 = 0, 𝑠𝑁 ≥ 0 . (6) Hal yang sama berlaku untuk (3) yang dapat dirumuskan menjadi 𝑐𝑗 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠𝐵 = 0, 𝑠𝑁 ≥ 0 , (7) dan (4) menjadi {𝑥𝑗 ∶ 𝐴𝑥 = 𝑏, 𝑥𝐵 ≥ 0, 𝑥𝑁 = 0}. (8) 3.4 Analisis Sensitivitas dengan Pendekatan Klasik Analisis sensitivitas dengan pendekatan klasik menggunakan metode simpleks dalam menyelesaikan masalah optimasi linear. Metode simpleks menghasilkan solusi basis dari masalah optimasi linear, sehingga solusi dengan pendekatan klasik ini ditentukan dengan sebuah basis optimal. Diasumsikan bahwa matriks 𝐴 berukuran 𝑚 × 𝑛 dan pangkat (𝐴) = 𝑚, indeks variabel basis dari 𝐴 yang berjumlah 𝑚 dinotasikan dengan 𝐵’, sehingga 𝐵’ adalah submatriks 𝐴𝐵′ berukuran 𝑚 × 𝑚 yang nonsingular dari 𝐴 dengan 𝐴𝐵′ 𝑥𝐵′ = 𝑏, 𝑥𝑁′ = 0 dengan 𝑁’ adalah indeks variabel nonbasis dari 𝐴. Solusi basis primal 𝑥 dapat ditentukan dengan −1 𝑥 = 𝑥𝑥𝐵 ′ ∶= 𝐴𝐵0′ 𝑏 (9) 𝑁′ dan solusi basis dual dapat ditentukan dengan 𝑠𝐵 ′ 0 𝑦 = 𝐴−𝑇 ∶= 𝑐 −𝐴 (10) 𝑇 𝑦 . 𝐵′ 𝑐𝑩′ , 𝑠 = 𝑠 𝑁′

𝑁′

𝑁′

Jika 𝑥𝐵′ ≥ 0 maka 𝐵’ adalah basis fisibel primal, jika 𝑠𝑁′ ≥ 0 maka 𝐵’ adalah basis fisibel dual. 𝐵’ basis optimal jika primal dan dual fisibel. Sebuah basis dikatakan optimal primal jika solusi basis primal tersebut optimal di (P), dan sebuah basis dikatakan optimal dual jika solusi basis dual tersebut optimal di (D). Analisis sensitivitas dengan pendekatan klasik juga menggunakan formula (5) - (8) untuk menentukan range dan shadow price, tetapi dengan partisi basis optimal (𝐵’, 𝑁’) sebagai ganti (𝐵, 𝑁). (P) dan (D) mungkin saja memiliki basis optimal lebih dari satu, dan pendekatan klasik ini juga mungkin memberikan range dan shadow price yang berbeda (Jansen et al. 1997).

8

IV STUDI KASUS Pada bagian ini akan disajikan studi kasus analisis sensitivitas masalah optimasi linear. Hasil analisis sensitivitas yang diperoleh dengan menggunakan partisi optimal akan dibandingkan dengan hasil yang diperoleh dengan bantuan perangkat lunak LINDO. Kasus yang diamati adalah sebagai berikut : 1 solusi optimal masalah primal unik, dan solusi optimal masalah dual tidak unik, 2 solusi optimal masalah primal unik, dan solusi optimal masalah dual unik, 3 solusi optimal masalah primal tidak unik, dan solusi optimal masalah dual unik. 4.1 Kasus I Misalkan masalah primal (P) didefinisikan sebagai berikut min 4𝑥1 − 5𝑥2 + 11𝑥3 terhadap −𝑥2 + 3𝑥3 = 0 𝑥1 − 𝑥2 − 𝑥3 = 1 𝑥1 , 𝑥2 , 𝑥3 ≥ 0. Masalah dualnya (D) adalah max 𝑦2 terhadap 𝑦2 ≤ 4 − 𝑦1 − 𝑦2 ≤ −5 3𝑦1 − 𝑦2 ≤ 11. Masalah dual (D) dapat diselesaikan secara grafik, dan daerah fisibelnya yang dapat dilihat di Gambar 3.

Gambar 3 Daerah fisibel (D) Kasus I Dari Gambar 3 dapat ditentukan himpunan solusi optimalnya adalah 𝐷∗ = {(𝑦1 , 𝑦2 ): 1 ≤ 𝑦1 ≤ 5, 𝑦2 = 4} dan nilai optimalnya adalah 4. Variabel slack dari setiap kendala dual masing-masing ialah

9

 𝑠1 = 4 − 𝑦2 𝑦2 + 𝑠1 = 4 −𝑦1 − 𝑦2 + 𝑠2 = −5  𝑠2 = −5 + 𝑦1 + 𝑦2 3𝑦1 – 𝑦2 + 𝑠3 = 11  𝑠3 = 11 − 3𝑦1 + 𝑦2 Dengan memasukkan nilai 1 ≤ 𝑦1 ≤ 5, 𝑦2 = 4 maka akan diperoleh nilai untuk setiap variabel slack dan dapat disimpulkan bahwa semua variabel slack dapat menjadi positif pada solusi optimal kecuali variabel slack pada konstrain 𝑦2 ≤ 4, yaitu 𝑠1 = 0. Karena di dual 𝑠1 = 0 maka di primalnya hanya variabel 𝑥1 yang dapat menjadi positif, sehingga dapat ditentukan partisi optimalnya (𝐵, 𝑁), dengan 𝑁 = {2, 3} dan 𝐵 = {1}. Dari Lema 2 diperoleh: 𝑃∗ = {𝑥 ∈ 𝑃: 𝑥2 = 𝑥3 = 0} dan (P) memiliki solusi yang unik: 𝑥 = (1, 0, 0). Range dan Shadow Price untuk 𝒃𝟏 = 𝟎 Dengan menggunakan formula (5) range 𝑏1 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑏1 {𝑏𝑖 ∶ 𝐴𝑥 = 𝑏, 𝑥𝐵 ≥ 0, 𝑥𝑁 = 0}. (5) Dari perkalian matriks 𝐴𝑥 = 𝑏 0 1

−1 3 −1 −1

𝑥1 𝑥2 = 𝑏1 1 𝑥3

diperoleh 0 = 𝑏1 𝑥1 = 1 sehingga range untuk 𝑏1 adalah interval [0, 0]. Maka 𝑏1 = 0 adalah break point. Dengan menggunakan formula (6) shadow price untuk 𝑏1 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑦1 𝑦𝑖 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠𝐵 = 0, 𝑠𝑁 ≥ 0 (6) karena 𝑦 ∈ 𝐷 ∗ , nilai minimum 𝑦1 adalah 1 dan nilai maksimum 𝑦1 adalah 5, jadi shadow price untuk 𝑏1 adalah [1, 5]. Range dan Shadow Price untuk 𝒃𝟐 = 𝟏 Dengan menggunakan formula (5) range 𝑏2 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑏2 . Dari perkalian matriks 𝐴𝑥 = 𝑏 0 1

−1 3 −1 −1

𝑥1 0 𝑥2 = 𝑏 2 𝑥3

diperoleh 0=0 𝑥1 = 𝑏2 . Karena 𝑥1 ≥ 0, maka 𝑏2 ≥ 0, maka range untuk 𝑏2 adalah interval [0, ∞). Dengan menggunakan formula (6) shadow price untuk 𝑏2 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑦2 . Berdasarkan 𝑦 ∈ 𝐷∗ , nilai 𝑦2 adalah 4, jadi shadow price untuk 𝑏2 adalah 4.

10

Range dan Shadow Price untuk 𝒄𝟏 = 𝟒 Dengan menggunakan formula (7) range 𝑐1 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑐1 . 𝑐𝑗 ∶ 𝐴𝑇 𝑦 + 𝑠 = 𝑐, 𝑠𝐵 = 0, 𝑠𝑁 ≥ 0 (7) 𝑇 Perkalian matriks 𝐴 𝑦 + 𝑠 = 𝑐: 0 −1 3

1 −1 −1

𝑠1 𝑐1 𝑦1 𝑠 𝑦2 + 2 = −5 𝑠3 11

Berdasarkan Gambar 3 jika kendala (1) dihilangkan maka 𝑦2 berada pada interval [1, ∞). Dengan memasukkan nilai 𝑠1 = 0 dan 𝑦2 ke persamaan kendala (1) diperoleh 𝑦2 = 𝑐1 , maka akan diperoleh 𝑐1 ≥ 1, sehingga range 𝑐1 adalah interval [1, ∞). Dengan menggunakan formula (8) shadow price untuk 𝑐1 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑥1 {𝑥𝑗 ∶ 𝐴𝑥 = 𝑏, 𝑥𝐵 ≥ 0, 𝑥𝑁 = 0}. (8) Karena 𝑥1 = 1, maka shadow price untuk 𝑐1 adalah 1. Range dan Shadow Price untuk 𝒄𝟐 = −𝟓 Dengan menggunakan formula (7) range 𝑐2 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑐2 . Perkalian matriks 𝐴𝑇 𝑦 + 𝑠 = 𝑐: 0 −1 3

1 −1 −1

𝑠1 4 𝑦1 𝑠2 = 𝑐2 + 𝑦2 𝑠3 11

Meminimumkan dan memaksimumkan 𝑐2 pada sistem di atas adalah sama dengan mencari nilai minimum dan maksimum −𝑦1 − 𝑦2 + 𝑠2 , 𝑠2 ≥ 0 agar sistem tetap fisibel. Berdasarkan Gambar 3 akan diperoleh 𝑐2 ≥ −9, sehingga range 𝑐2 adalah interval [−9, ∞). Dengan menggunakan formula (8), shadow price untuk 𝑐2 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑥2 . Karena 𝑥2 = 0, maka shadow price untuk 𝑐2 adalah 0. Range dan Shadow Price untuk 𝒄𝟑 = 𝟏𝟏 Dengan menggunakan formula (7) range 𝑐3 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑐3 pada perkalian matriks 𝐴𝑇 𝑦 + 𝑠 = 𝑐 berikut: 0 −1 3

1 −1 −1

𝑠1 4 𝑦1 𝑠 𝑦2 + 2 = −5 𝑠3 𝑐3

11

Dengan menggunakan Gambar 3, akan dicari nilai minimum dan maksimum 𝑐3 = 3𝑦1 − 𝑦2 + 𝑠3 , 𝑠3 ≥ 0 sehingga sistem tetap fisibel. Diperoleh 𝑐3 ≥ −1, sehingga range 𝑐3 adalah interval [−1, ∞). Shadow price untuk 𝑐3 dapat ditentukan dengan meminimumkan dan memaksimumkan 𝑥3 , menggunakan formula (8). Karena 𝑥3 = 0, maka shadow price untuk 𝑐3 adalah 0. Tabel 1 Range dan shadow price yang diperoleh dari hasil perhitungan (Kasus I) Koefisien Range Shadow price 0 [1, 5] 𝑏1 = 0 4 [0, ∞) 𝑏2 = 1 1 [1, ∞) 𝑐1 = 4 0 [−9, ∞) 𝑐2 = −5 0 [−1, ∞) 𝑐3 = 11 Tabel 2 Range dan shadow price yang diperoleh dari LINDO (Kasus I) Koefisien Range Shadow price 1 (−∞, 0] 𝑏1 = 0 4 [0, ∞) 𝑏2 = 1 1 [1, ∞) 𝑐1 = 4 0 [−9, ∞) 𝑐2 = −5 0 [−1, ∞) 𝑐3 = 11 Dari Tabel 1 dan Tabel 2 dapat dilihat bahwa terdapat perbedaan hasil range dan shadow price pada koefisien 𝑏1 = 0. Analisis sensitivitas dengan metode simpleks (LINDO) tidak mendeteksi bahwa 𝑏1 = 0 merupakan break point. Sedangkan analisis sensitivitas dengan pendekatan partisi optimal mendeteksi bahwa 𝑏1 = 0 merupakan break point, sehingga koefisien 𝑏1 memiliki dua nilai shadow price, yaitu shadow price kiri yang bernilai 1 dan shadow price kanan yang bernilai 5. Shadow price kiri digunakan ketika nilai koefisien 𝑏1 diturunkan dari nilai awalnya, sedangkan Shadow price kanan digunakan ketika nilai koefisien 𝑏1 dinaikkan dari nilai awalnya. Misalkan jika nilai koefisien 𝑏1 diturunkan satu satuan dari nilai awalnya menjadi 𝑏1 = −1 maka nilai optimalnya menjadi 3, dan jika nilai koefisien 𝑏1 dinaikkan satu satuan dari nilai awalnya menjadi 𝑏1 = 1 maka nilai optimalnya menjadi 9. 4.2 Kasus II Misalkan masalah primal (P) didefinisikan sebagai berikut min 31𝑥1 − 5𝑥2 + 11𝑥3 terhadap 3𝑥1 − 𝑥2 + 3𝑥3 = 0 7𝑥1 − 𝑥2 − 𝑥3 = 1 𝑥1 , 𝑥2 , 𝑥3 ≥ 0.

12

Masalah dualnya (D) adalah max 𝑦2 terhadap 3𝑦1 + 7𝑦2 ≤ 31 −𝑦1 − 𝑦2 ≤ −5 3𝑦1 − 𝑦2 ≤ 11. Masalah dual (D) dapat diselesaikan secara grafik, dan daerah fisibelnya dapat dilihat di Gambar 4.

Gambar 4 Daerah fisibel (D) Kasus II Dari Gambar 4 dapat ditentukan himpunan solusi optimalnya adalah 𝐷∗ = {(𝑦1 , 𝑦2 ): 𝑦1 = 1, 𝑦2 = 4} dan nilai optimalnya adalah 4. Variabel slack dari setiap kendala dual masing-masing ialah 3𝑦1 + 7𝑦2 + 𝑠1 = 31  −𝑦1 − 𝑦2 + 𝑠2 = −5  3𝑦1 − 𝑦2 + 𝑠3 = 11 

𝑠1 = 31 − 3𝑦1 − 7𝑦2 𝑠2 = −5 + 𝑦1 + 𝑦2 𝑠3 = 11 − 3𝑦1 + 𝑦2

Dengan memasukkan nilai 𝑦1 = 1 dan 𝑦2 = 4 maka akan diperoleh nilai untuk setiap variabel slack dan dapat disimpulkan bahwa semua variabel slack dapat menjadi positif pada solusi optimal kecuali variabel slack pada konstrain 3𝑦1 + 7𝑦2 ≤ 31 dan −𝑦1 − 𝑦2 ≤ −5 yaitu 𝑠1 = 𝑠2 = 0. Karena di dual 𝑠1 = 𝑠2 = 0 maka di primalnya hanya variabel 𝑥1 dan 𝑥2 yang dapat menjadi positif, sehingga dapat ditentukan partisi optimalnya (𝐵, 𝑁), dengan 𝑁 = {3} dan 𝐵 = {1, 2}. Dari Lema 2 diperoleh: ∗ 𝑃 = {𝑥 ∈ 𝑃: 𝑥3 = 0} dan (P) memiliki solusi yang unik: 𝑥 = (1 4 , 3 4 , 0). Dengan menggunakan perhitungan seperti pada Kasus I diperoleh range dan shadow price dengan menggunakan partisi optimal pada Tabel 3. Tabel 3 Range dan shadow price yang diperoleh dari hasil perhitungan (Kasus II) Koefisien Range Shadow price 3 𝑏1 = 0 (−∞, 7 ] 1 𝑏2 = 1 4 [0, ∞) 1 𝑐1 = 31 [19, ∞) 4 3 4 𝑐2 = −5 [−7, ∞) 0 𝑐3 = 11 [−1, ∞)

13

Tabel 4 Range dan shadow price yang diperoleh dari LINDO (Kasus II) Koefisien Range Shadow price 3 𝑏1 = 0 (−∞, 7] 1 𝑏2 = 1 4 [0, ∞) 1 𝑐1 = 31 [19, ∞) 4 3 4 𝑐2 = −5 [−7, ∞) 0 𝑐3 = 11 [−1, ∞) Dari Tabel 3 dan Tabel 4 dapat dilihat bahwa terdapat hasil range dan shadow price yang sama antara perhitungan dengan pendekatan partisi optimal dan metode simpleks. 4.3 Kasus III Misalkan masalah primal (P) didefinisikan sebagai berikut min 4𝑥1 + 31𝑥2 − 5𝑥3 + 11𝑥4 terhadap 3𝑥2 − 𝑥3 + 3𝑥4 = 0 𝑥1 + 7𝑥2 − 𝑥3 − 𝑥4 = 1 𝑥1 , 𝑥2 , 𝑥3 , 𝑥4 ≥ 0. Masalah dualnya (D) adalah max 𝑦2 terhadap 𝑦2 ≤ 4 3𝑦1 + 7𝑦2 ≤ 31 −𝑦1 − 𝑦2 ≤ −5 3𝑦1 − 𝑦2 ≤ 11. Masalah dual (D) dapat diselesaikan secara grafik, dan daerah fisibelnya dapat dilihat di Gambar 5.

Gambar 5 Daerah fisibel (D) Kasus III Dari Gambar 5 dapat ditentukan himpunan solusi optimalnya adalah 𝐷∗ = {(𝑦1 , 𝑦2 ): 𝑦1 = 1, 𝑦2 = 4} dan nilai optimalnya adalah 4. Variabel slack dari setiap kendala dual masing-masing ialah

14

𝑦2 + 𝑠1 = 4 3𝑦1 + 7𝑦2 + 𝑠2 = 31 −𝑦1 − 𝑦2 + 𝑠3 = −5 3𝑦1 − 𝑦2 + 𝑠4 = 11

   

𝑠1 𝑠2 𝑠3 𝑠4

= 4 − 𝑦2 = 31 − 3𝑦1 − 7𝑦2 = −5 + 𝑦1 + 𝑦2 = 11 − 3𝑦1 + 𝑦2

Dengan memasukkan nilai 𝑦1 = 1 dan 𝑦2 = 4 maka diperoleh nilai untuk setiap variabel slack sehingga variabel slack pada konstrain 𝑦2 ≤ 4, 3𝑦1 + 7𝑦2 ≤ 31 dan −𝑦1 − 𝑦2 ≤ −5 bernilai 0, yaitu 𝑠1 = 𝑠2 = 𝑠3 = 0, sehingga di primalnya hanya variabel 𝑥1 , 𝑥2 dan 𝑥3 yang dapat menjadi positif. Oleh karena itu diperoleh partisi optimal (𝐵, 𝑁), dengan 𝑁 = {4} dan 𝐵 = {1, 2, 3}. Dari Lema 2 diperoleh: ∗ 𝑃 = {𝑥 ∈ 𝑃: 𝑥4 = 0} dan (P) memiliki solusi yang tidak unik: {(𝑥1 , 𝑥2 , 𝑥3 ): 𝑎, ¼ − ¼ 𝑎, 3 ¼ − ¼ 𝑎 ; 0 ≤ 𝑎 ≤ 1}. Kemudian hasil perhitungan range dan shadow price disajikan pada Tabel 5. Tabel 5 Range dan shadow price yang diperoleh dari hasil perhitungan (Kasus III) Koefisien Range Shadow price 1 𝑏1 = 0 (−∞, 3 7] 4 𝑏2 = 1 [0, ∞) [1, 0] 𝑐1 = 4 4 [1 4, 0] 𝑐2 = 31 31 [3 4, 0] 𝑐3 = −5 −5 0 𝑐4 = 11 [−1, ∞) Tabel 6 Range dan shadow price yang diperoleh dari LINDO (Kasus III) Koefisien Range Shadow price 1 (−∞, 0] 𝑏1 = 0 4 [0, ∞) 𝑏2 = 1 1 [1, 4] 𝑐1 = 4 0 [31, ∞) 𝑐2 = 31 0 [−5, ∞) 𝑐3 = −5 0 [−1, ∞) 𝑐4 = 11 Pada Tabel 5 dan Tabel 6 dapat dilihat bahwa terdapat perbedaan range dan shadow price yang diperoleh dengan menggunakan partisi optimal dan metode simpleks. Pada koefisien 𝑏1 = 0, untuk shadow price yang sama, pendekatan partisi optimal mendeteksi range yang lebih besar. Kemudian pada koefisien 𝑐1 = 4, 𝑐2 = 31 dan 𝑐3 = −5 analisis dengan menggunakan metode simpleks tidak mendeteksi adanya break point, sehingga shadow price yang diperoleh dengan metode simpleks merupakan subset dari shadow price dengan pendekatan partisi optimal. Karena koefisien 𝑐1 , 𝑐2 dan 𝑐3 adalah break point maka koefisien 𝑐1 , 𝑐2 dan 𝑐3 memiliki dua nilai shadow price berturut-turut, yaitu shadow price kiri yang bernilai 1, 1 4, 3 4 dan shadow price kanan yang bernilai 0.

15

V SIMPULAN Analisis sensitivitas dengan metode simpleks (menggunakan pendekatan basis optimal) untuk kasus yang memiliki solusi optimal primal atau dual yang tidak unik, hasilnya akan mengalami ketaksempurnaan informasi. Sedangkan analisis sensitivitas dengan pendekatan partisi optimal untuk kasus yang memiliki solusi optimal primal atau dual yang tidak unik, menghasilkan informasi yang lebih akurat. Namun saat masalah primal dan masalah dual memiliki solusi optimal yang unik, metode simpleks dan pendekatan partisi optimal menghasilkan informasi yang persis sama.

DAFTAR PUSTAKA Jansen B, de Jong J.J, Roos C, Terlaky T. 1997. Sensitivity analysis in linear programming: just be careful!. European Journal of Operations Research. 101: 15-28.doi: 10.1016/S0377-2217(96)00172-5. Leon SJ. 1998. Linear Algebra with Applications. Ed ke-5. New Jersey (US): Prentice Hall. Roos C, Terlaky T, Vial J-Ph. 2006. Interior Point Methods for Linear Optimization. New York (US): Springer. Siswanto. 2007. Operations Research. Jilid 1. Jakarta (ID): Erlangga. Winston WL. 2004. Operations Research Applications and Algorithms. 4th edition. New York (US): Duxbury .

16

Lampiran 1 Studi kasus I dengan menggunakan LINDO Input Primal : min 4x1-5x2+11x3 subject to -x2+3x3=0 x1-x2-x3=1 end

Output Primal : LP OPTIMUM FOUND AT STEP

0

OBJECTIVE FUNCTION VALUE 1)

4.000000

VARIABLE X1 X2 X3 ROW 2) 3)

VALUE 1.000000 0.000000 0.000000 SLACK OR SURPLUS 0.000000 0.000000

NO. ITERATIONS=

REDUCED COST 0.000000 0.000000 12.000000 DUAL PRICES -1.000000 -4.000000

0

RANGES IN WHICH THE BASIS IS UNCHANGED: VARIABLE X1 X2 X3 ROW 2 3

Input Dual : max y2 subject to y2<=4 -y1-y2<=-5 3y1-y2<=11 end

CURRENT COEF 4.000000 -5.000000 11.000000 CURRENT RHS 0.000000 1.000000

OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 3.000000 INFINITY 4.000000 INFINITY 12.000000 RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 0.000000 INFINITY

ALLOWABLE DECREASE INFINITY 1.000000

17

Output Dual : LP OPTIMUM FOUND AT STEP

2

OBJECTIVE FUNCTION VALUE 1)

4.000000

VARIABLE Y2 Y1 ROW 2) 3) 4)

VALUE 4.000000 1.000000

REDUCED COST 0.000000 0.000000

SLACK OR SURPLUS 0.000000 0.000000 12.000000

NO. ITERATIONS=

DUAL PRICES 1.000000 0.000000 0.000000

2

RANGES IN WHICH THE BASIS IS UNCHANGED: VARIABLE Y2 Y1 ROW 2 3 4

CURRENT COEF 1.000000 0.000000 CURRENT RHS 4.000000 -5.000000 11.000000

OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 1.000000 0.000000 INFINITY RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 1.000000 1.000000 INFINITY

Lampiran 2 Studi kasus II dengan menggunakan LINDO Input Primal : min 31x1-5x2+11x3 subject to 3x1-x2+3x3=0 7x1-x2-x3=1 end

Output Primal : LP OPTIMUM FOUND AT STEP

0

OBJECTIVE FUNCTION VALUE 1) VARIABLE X1

4.000000 VALUE 0.250000

REDUCED COST 0.000000

ALLOWABLE DECREASE 3.000000 4.000000 12.000000

18

X2 X3 ROW 2) 3)

0.750000 0.000000

0.000000 12.000000

SLACK OR SURPLUS 0.000000 0.000000

NO. ITERATIONS=

DUAL PRICES -1.000000 -4.000000

0

RANGES IN WHICH THE BASIS IS UNCHANGED: VARIABLE

CURRENT COEF 31.000000 -5.000000 11.000000

X1 X2 X3 ROW

CURRENT RHS 0.000000 1.000000

2 3

OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 12.000000 INFINITY 2.000000 INFINITY 12.000000 RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 0.428571 INFINITY

Input Dual : max y2 subject to 3y1+7y2<=31 -y1-y2<=-5 3y1-y2<=11 end

Output Dual : LP OPTIMUM FOUND AT STEP

2

OBJECTIVE FUNCTION VALUE 1)

4.000000

VARIABLE Y2 Y1 ROW 2) 3) 4)

VALUE 4.000000 1.000000 SLACK OR SURPLUS 0.000000 0.000000 12.000000

NO. ITERATIONS=

2

REDUCED COST 0.000000 0.000000 DUAL PRICES 0.250000 0.750000 0.000000

ALLOWABLE DECREASE INFINITY 1.000000

19

RANGES IN WHICH THE BASIS IS UNCHANGED: VARIABLE

CURRENT COEF 1.000000 0.000000

Y2 Y1 ROW

CURRENT RHS 31.000000 -5.000000 11.000000

2 3 4

OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 1.000000 0.428571 INFINITY RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 4.000000 0.571429 INFINITY

ALLOWABLE DECREASE 12.000000 2.000000 12.000000

Lampiran 3 Studi kasus III dengan menggunakan LINDO Input Primal :

min 4x1+31x2-5x3+11x4 subject to 3x2-x3+3x4=0 x1+7x2-x3-x4=1 end

Output Primal :

LP OPTIMUM FOUND AT STEP

1

OBJECTIVE FUNCTION VALUE 1)

4.000000

VARIABLE X1 X2 X3 X4 ROW 2) 3)

VALUE 1.000000 0.000000 0.000000 0.000000

REDUCED COST 0.000000 0.000000 0.000000 12.000000

SLACK OR SURPLUS 0.000000 0.000000

NO. ITERATIONS=

DUAL PRICES -1.000000 -4.000000

1

RANGES IN WHICH THE BASIS IS UNCHANGED: VARIABLE X1 X2 X3 X4

OBJ COEFFICIENT RANGES CURRENT ALLOWABLE COEF INCREASE 4.000000 0.000000 31.000000 INFINITY -5.000000 INFINITY 11.000000 INFINITY

ALLOWABLE DECREASE 3.000000 0.000000 0.000000 12.000000

20

ROW 2 3

RIGHTHAND SIDE RANGES CURRENT ALLOWABLE RHS INCREASE 0.000000 0.000000 1.000000 INFINITY

ALLOWABLE DECREASE INFINITY 1.000000

Input Dual : max y2 subject to y2<=4 3y1+7y2<=31 -y1-y2<=-5 3y1-y2<=11 end

Output Dual : LP OPTIMUM FOUND AT STEP

2

OBJECTIVE FUNCTION VALUE 1)

4.000000

VARIABLE Y2 Y1 ROW 2) 3) 4) 5)

VALUE 4.000000 1.000000 SLACK OR SURPLUS 0.000000 0.000000 0.000000 12.000000

NO. ITERATIONS=

REDUCED COST 0.000000 0.000000 DUAL PRICES 1.000000 0.000000 0.000000 0.000000

2

RANGES IN WHICH THE BASIS IS UNCHANGED: VARIABLE Y2 Y1 ROW 2 3 4 5

CURRENT COEF 1.000000 0.000000 CURRENT RHS 4.000000 31.000000 -5.000000 11.000000

OBJ COEFFICIENT RANGES ALLOWABLE ALLOWABLE INCREASE DECREASE INFINITY 1.000000 0.000000 INFINITY RIGHTHAND SIDE RANGES ALLOWABLE INCREASE 0.000000 INFINITY 1.000000 INFINITY

ALLOWABLE DECREASE 3.000000 0.000000 0.000000 12.000000

21

RIWAYAT HIDUP Penulis lahir di Manado pada tanggal 11 Juni 1991 dari ayah Amir Kara dan ibu Siti Aminah. Penulis adalah putri ketiga dari tiga bersaudara. Penulis menyelesaikan pendidikan Sekolah Dasar pada tahun 2003 di SD Negeri Bekasi Jaya XI dan Sekolah Menengah Pertama pada tahun 2006 di SMP Negeri 1 Bekasi. Tahun 2009 penulis lulus dari SMA KORPRI Bekasi dan pada tahun yang sama penulis lulus seleksi masuk Institut Pertanian Bogor (IPB) melalui jalur Undangan Seleksi Masuk IPB dan diterima di Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis menjadi asisten Kalkulus 2 pada tahun ajaran 2011/2012 dan 2012/2013 serta asisten Pemrograman Linear pada tahun ajaran 2012/2013. Penulis juga pernah aktif pada kegiatan Agriaswara pada tahun 2009-2011 dan staf Kesekretariatan Agriaswara pada tahun 2011. Pada tahun 2011 penulis juga pernah aktif sebagai staf divisi Sosial Informasi dan Komunikasi dan sebagai staf divisi Public Relationship pada tahun 2012 di GUMATIKA IPB.