BAB II LANDASAN TEORI

xvi

BAB II

LANDASAN TEORI

2.1

Matriks

2.1.1 Pengertian Matriks

Matriks adalah susunan elemen-elemen yang berbentuk persegi panjang yang terdiri dari baris dan kolom dan dibatasi dengan tanda [ ] atau ( ). Bilangan-bilangan dalam susunan tersebut dinamakan entri dalam matriks. Jika menggunakan

adalah sebuah matriks, maka akan

untuk menyatakan entri yang terdapat di dalam baris

dan kolom

dari

matriks . Secara umum matriks dituliskan sebagai berikut: =

Matriks di atas disebut matriks berukuran dan

kolom.

kali

(ditulis

× ) karena memiliki

baris

2.1.2 Penjumlahan Matriks

Jika

dan

adalah sebarang dua matriks yang ukurannya sama, maka jumlah

+ adalah

matriks yang diperoleh dengan menambahkan bersama-sama entri yang bersesuaian dalam

kedua matriks tersebut. Matriks-matriks yang ukurannya berbeda tidak dapat dijumlahkan (Howard Anton, 1988 : 23).

Universitas Sumatera Utara

xvii

2.1.3 Perkalian Matriks

Jika

× dan

adalah matriks

adalah matriks

× , maka hasil kali

adalah matriks

× yang entri-entrinya ditentukan sebagai berikut. Untuk mencari entri dalam baris- dan

kolom- dari

, pilihlah baris- dari matriks

dan kolom- dari matriks . Kalikanlah entri-

entri yang bersesuaian dari baris dan kolom tersebut bersama-sama dan kemudian tambahkanlah hasil kali yang dihasilkan (Anton, 1988 :25). Contoh : Diketahui

=

1 3 4 , dan 3 2 5

Tinjaulah perkalian matriks

2 4 =3 6 1 3

dan . Karena

matriks berukuran 3 × 2 maka hasil kali untuk hasil kali adalah:

adalah matriks berukuran 2 × 3 dan

adalah

adalah matriks 2 × 2. Perhitungan-perhitungan

(1.2) + (3.3) + (4.1) = 15 (1.4) + (3.6) + (4.3) = 34

(3.2) + (2.3) + (5.1) = 17

(3.4) + (2.6) + (5.3) = 39 =

Jadi, diperoleh

15 34 . 17 39

2.1.4 Perkalian Matriks Dengan Bilangan

Jika

adalah suatu matriks dan

adalah suatu bilangan, maka hasil kali (product)

matriks yang diperoleh dengan mengalikan masing-masing entri dari ditulis

= (

). Khususnya dengan

yang diperoleh dari

2.2

oleh . Dalam hal ini

yang disebut negatif dari

, diartikan matriks

dengan cara mengalikan setiap elemennya dengan

dengan mengubah tanda semua elemennya.

adalah

1 atau cukup

Persoalan Optimasi dan Program Linier


xviii

Richard Bronson (1996 : 1) menyatakan bahwa masalah optimasi merupakan masalah memaksimumkan atau meminimumkan sebuah besaran tertentu yang disebut tujuan objektif (objective) yang bergantung pada sejumlah berhingga variabel masukan (input variabels). Variabel-variabel ini dapat tidak saling bergantung, atau saling bergantung melalui satu atau lebih kendala (constrains). Persoalan optimasi merupakan persoalan mencari nilai numerik terbesar (maksimasi) atau nilai numerik terkecil (minimasi) yang mungkin dari sebuah fungsi pada sejumlah variabel tertentu.

Dalam sebuah persoalan optimasi, dicari nilai untuk variabel- variabel yang tidak melanggar (bertentangan) dengan kendala-kendala yang menyangkut variabel-variabel tersebut dan yang memberikan nilai optimum (maksimum atau minimum) pada fungsi yang hendak dioptimumkan. Dalam tulisan ini akan diperhatikan cara optimasi yang telah dipergunakan dalam memodel persoalan fisik, ekonomi, tehnik, dan segala macam persoalan bisnis yang sesuai. Cara ini disebut Program Linear.

Program linear yang diterjemahkan dari Linear Programming (LP) adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing, dengan cara yang terbaik yang mungkin dilakukan. Persoalan pengalokasian ini akan muncul manakala seseorang harus memilih tingkat aktivitas-aktivitas tertentu yang bersaing dalam hal penggunaan sumber daya langka yang dibutuhkan untuk melaksanakan aktivitas-aktivitas tersebut. Beberapa contoh situasi dari uraian di atas antara lain adalah pengalokasian fasilitas produksi, persoalan pengalokasian sumber daya nasional untuk kebutuhan domestic, penjadwalan produksi, solusi permainan (game), dan pemilihan pola pengiriman (shipping). Program Linear (PL) atau Linear Programming adalah suatu model dari penelitian operasional untuk memecahkan masalah optimasi. Program linier merupakan salah satu metode Penelitian Operasional yang banyak digunakan di bidang industri, transportasi, perdagangan, perkebunan, perikanan, tehnik, dan lain sebagainya.

Program linear merupakan matematika terapan dari aljabar linear dimana dalam memecahkan persoalan dunia nyata melalui tahap-tahap sebagai berikut: 1.

Memahami masalah di bidang yang bersangkutan

2.

Menyusun model matematika

3.

Menyelesaikan model matematika (mencari jawaban model)


xix

4.

Menafsirkan jawaban model menjadi jawaban atas masalah yang nyata.

Masalah optimasi tidak semuanya dapat diselesaikan dengan metode Program Linear. Prinsip-prinsip utama yang mendasari penggunaan metode Program Linear adalah: 1.

Adanya sasaran. Sasaran dalam model matematika masalah program linear berupa fungsi tujuan (fungsi objektif) yang akan dicari nilai optimalnya (maksimum / minimum).

2.

Ada tindakan alternatif, artinya nilai fungsi tujuan dapat diperoleh dengan berbagai cara dan diantaranya alternatif itu memberikan nilai.

3.

Adanya keterbatasan sumber daya. Sumber daya atau input dapat berupa waktu, tenaga, biaya, bahan, dan sebagainya. Pembatasan sumberdaya

disebut kendala

(constrains ) pembatas. 4.

Masalah harus dapat dituangkan dalam bahasa matematika yang disebut model matematika. Model matematika dalam program linear memuat fungsi tujuan dan kendala. Fungsi tujuan harus berupa fungsi linear dan kendala berupa pertidaksamaan atau persamaan linear.

5.

Antar variabel yang membentuk fungsi tujuan dan kendala ada keterikatan, artinya perubahan pada satu peubah akan mempengaruhi nilai peubah yang lain.

2.3

Masalah Transportasi

Model transportasi merupakan kasus khusus dari persoalan program linear dengan tujuan untuk “mengangkut” barang tunggal dari berbagai asal ke berbagai tujuan dengan biaya angkut serendah mungkin.

Adanya informasi tentang besar kapasitas tiap-tiap asal, permintaan total masingmasing tempat tujuan, dan biaya pengiriman per-unit barang untuk lintasan yang dimungkinkan, maka model transportasi digunakan untuk menentukan program pengiriman optimal yang melibatkan biaya pengiriman total yang minimum. Model transportasi adalah suatu kasus khusus dari persoalan program linear, berarti model transportasi memiliki ciri khas yang dimiliki pula oleh masalah program linear, yaitu : 1. Terdapat sejumlah sumber dan sejumlah tujuan tertentu.


xx

2. Kuantitas komoditas atau barang dan yang didistribusikan dari setiap sumber dan yang diminta oleh setiap tujuan, besarnya tertentu. 3. Komoditas yang dikirim atau diangkut dari suatu sumber ke suatu tujuan, besarnya sesuai dengan permintaan dan atau kapasitas sumber. 4. Ongkos pengangkutan komoditas dari suatu sumber ke suatu tujuan, besarnya tertentu. 5. Jumlah variabel dasar m + n - 1, dimana m adalah jumlah baris dan n adalah jumlah kolom. Apabila jumlah variabel dasar kurang dari m + n – 1 yang disebut dengan degenerasi, maka harus ditambahkan variabel dasar dengan nilai nol.

Dalam menggambarkan masalah transportasi, perlu digunakan istilah istilah yang tidak khusus karena masalah transportasi adalah masalah yang umum, yaitu pendistribusian berbagai komoditi dari berbagai kelompok pusat penerima yang disebut tujuan, sedemikian rupa sehingga meminimalisasi biaya distribusi total. Secara umum, sumber i (i = 1, 2, ..., m) mempunyai supply si unit yang akan didistribusikan ke tujuan-tujuan dan tujuan (j = 1, 2, ...,n) mempunyai permintaan di unit yang dikirim dari sumber-sumber. Asumsi dasar metode transportasi ini adalah biaya mendistribusikan unit-unit dari sumber i ke tujuan j berbanding langsung dengan jumlah yang akan didistribusikan, dimana c ij menyatakan biaya per unit yang didistribusikan. Apabila Z merupakan biaya distribusi total dan xij ( i = 1, 2, ..., m ; j = 1, 2, ..., n) adalah jumlah unit yang harus didistribusikan dari sumber i ke tujuan j, maka formulasi pemrograman linier masalah transportasi. Dari penjelasan di atas, maka rumus metode transportasi dapat diformulasikan sebagai berikut :

Meminimumkan

Dengan batasan

: =

: =

=

=0 ialah koefisien variabel struktur.

= 1,2,

= 1,2,

=1

,

,

(2.1)


xxi

Dalam arti sederhana, model transportasi berusaha menentukan rencana transportasi sebuah barang dari sejumlah sumber ke sejumlah tujuan. Data dalam model ini mencakup: a) Tingkat penawaran di setiap sumber dan jumlah permintaan di setiap tujuan. b) Biaya transportasi per unit barang dari setiap sumber ke setiap tujuan.

Karena hanya terdapat suatu barang, sebuah tujuan dapat menerima permintaannya dari suatu sumber atau lebih. Tujuan dari model ini adalah menentukan jumlah yang harus dikirim dari setia sumber ke setiap tujuan sedemikian rupa sehingga biaya transportasi total diminimumkan. Asumsi dasar dari model ini adalah bahwa biaya transportasi di sebuah rute tertentu adalah proporsional secara langsung dengan jumlah unit yang dikirimkan. Defenisi “unit transportasi” akan bervariasi bergantung pada jenis “barang” yang dikirimkan.

Gambar dibawah ini memperlihatkan sebuah model transportasi dari sebuah jaringan dengan

sumber dan

tujuan. Sebuah sumber dan tujuan diwakili dengan sebuah node.

Busur yang menghubungkan sebuah sumber dan sebuah tujuan mewakili rute pengiriman barang tersebut. Jumlah penawaran di sumber adalah Anggap

adalah

dan permintaan di tujuan

. Biaya unit transportasi antara sumber dan adalah

.

mewakili jumlah barang yang dikirimkan dari sumber ke tujuan , maka model

LP yang mewakili masalah transportasi ini diketahui secara umum sebagai berikut: Sumber

Tujuan :

1

Unit penawaran

1

2

2

m

:

unit permintaan

n

Gambar 1 Model Transportasi

Minimumkan:


xxii

= (2.2) Dengan batasan: = 1,2,

,

= 1,2,

=0

,

=1

Kelompok batasan pertama menetapkan bahwa jumlah pengiriman dari sebuah sumber tidak dapat melebihi penawarannya. Demikian pula kelompok batasan kedua mengharuskan bahwa jumlah pengiriman ke sebuah tujuan harus memenuhi permintaannya. Model yang baru digambarkan diatas menyiratkan bahwa jumlah penawaran setidaknya sama dengan jumlah permintaan jumlah permintaan (

=

harus

. Apabila jumlah penawaran sama dengan

), formulasi yang dihasilkan disebut Model Transportasi

Berimbang (balanced transportation model). Model ini berbeda dengan model di atas hanya dalam fakta bahwa semua batasan adalah persamaan yaitu:

=

,

= 1,2,

,

=

,

= 1,2,

,

=0 2.4

=1

(2.3)

Metode Hungarian

Masalah penetapan (assignment problem) adalah suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas (kegiatan), sehingga dengan demikian biaya yang dikeluarkan untuk pelaksanaan tugas tersebut dapat diminimalkan (N. Soemartojo, 1994 : 309).


xxiii

Masalah ini merupakan salah satu kasus khusus dari masalah transportasi yang penyelesaiannya menggunakan metode Hungarian. Metode Hungarian dikembangkan atas dasar pendekatan VAM ( Vogel’s Approximation Method), yaitu dengan cara meminimalkan biaya penalti( opportunity cost ) yang tidak memanfaatkan biaya sel termurah. Pendekatan VAM merupakan suatu metode yang menggunakan pendekatan dengan cara meminimalkan biaya penalti akibat gagal memilih pengisian sel yang memiliki alternatif terbaik.

Howard Anton (1988 : 59) menyatakan bahwa masalah penetapan tugas mensyaratkan bahwa fasilitas sama banyaknya dengan tugas, katakanlah sama dengan n. Dalam hal ini maka ada n! cara yang berlainan untuk menetapkan tugas kepada fasilitas berdasarkan penetapan satu-satu (one-to-one basic). Banyaknya penetapan ini adalah n! karena terdapat n cara untuk menetapkan tugas pertama, n-1 cara untuk menetapkan tugas kedua, n-2 cara untuk menetapkan tugas ketiga, dan seterusnya yang jumlah seluruhnya adalah: n.(n-1).(n2)…3.2.1 = n! penetapan yang mungkin.Diantara ke n! penetapan-penetapan yang mungkin ini kita harus mencari satu penetapan yang optimal.

Untuk mendefinisikan penetapan yang optimal secara tepat, maka kita akan memperkenalkan kuantitas – kuantitas berikut ini misalkan : cij = biaya untuk menetapkan tugas ke – j kepada fasilitas ke – i, untuk i, j = 1, 2,…, n. Satuan dari cij dapat berbentuk rupiah, dollar, mil, jam, dan lain-lain, satuan apapun yang sesuai dengan masalahnya.Kita mendefiinisikan matriks biaya (cost matrix) sebagai matriks n xn: C

=

Pernyataan bahwa sebuah tugas yang unik harus ditetapkan kepada setiap fasilitas berdasarkan satu – satu adalah ekuivalen dengan syarat bahwa tidak ada dua cij yang bersangkutan berasal dari baris yang sama atau kolom yang sama.

Definisi 1 Jika diketahui sebuah matriks biaya C yang berdimensi n x n maka penetapan (assignment) adalah sebuah himpunan dari n entri dimana tidak ada dua diantara


xxiv

entrinya yang berasal dari baris yang sama atau kolom yang sama (Howard Anton, 1988 : 60)

Maka sebuah penetapan optimal akan didefenisikan sebagai berikut: Definisi 2 n entri dari sebuah penetapan dinamakan biaya (cost) penetapan tersebut. Penetapan biaya yang paling kecil dinamakan penetapan optimal (optimal assignment) (Howard Anton, 1988 : 60).

Masalah penetapan adalah untuk mencari penetapan optimal dalam sebuah matriks biaya. Misalnya dalam menetapkan n peralatan kepada n tempat konstruksi, maka cij dapat merupakan jarak diantara peralatan ke-i dan tempat konstruksi ke-j. Sebuah penetapan optimal adalah penetapan untuk mana jarak seluruhnya yang ditempuh untuk memindahkan n peralatan tersebut adalah minimum (Howard Anton, 1988 : 60).

Secara mendetail model untuk masalah penetapan dapat ditulis dalam suatu bentuk program linear sebagai berikut:

= Dengan batasan:

di mana:

=0

= 1,

= 1,2,

,

= 1,

= 1,2,

,

(2.4)

=1

Z

= fungsi tujuan problema

xij

= variabel keputusan

cij

= nilai kontribusi objek i terhadap tugas j


xxv

m

= jumlah objek (individu atau sumber daya)

n

= jumlah tugas yang akan diselesaikan

xij

= 1, apabila objek i ditugaskan untuk tugas j

xij

= 0, apabila objek i tidak ditugaskan untuk tugas j

Andi Trio Sungkowo (2004: 31) mengatakan langkah – langkah dalam menjalankan metode Hungariannn adalah sebagai berikut: 1. Menyusun matriks biaya. 2. Mengurangkan elemen-elemen pada setiap baris dengan elemen terkecil pada baris yang sama. 3. Mengurangkan elemen-elemen pada setiap kolom dengan elemen terkecil pada kolom yang sama. Langkah ini akan menghasilkan Total Opportunity Cost (TOC). 4. Tutup elemen-elemen bernilai nol pada TOC dengan garis-garis mendatar atau tegak. Misalkan n adalah banyaknya baris atau kolom dan banyaknya garis penutup elemen nol sekurang-kurangnya k, maka: Jika k = n, berarti sudah diperoleh program optimal. Proses dihentikan dan susun penugasan Jika k < n, maka proses dilanjutkan dengan mengikuti langkah 5.

5. Cari bilangan terkecil dari bilangan-bilangan yang tak tertutup garis, misalkan e. Selanjutnya: a. Semua elemen yang tak tertutup garis dikurangi e. b. Semua elemen yang yang tertutup oleh satu garis tidak diubah. c. Semua elemen yang tertutup oleh dua garis ditambah dengan e. Setelah diperoleh tabel baru kembali ke langkah – 4.

2.5

Analisis Sensitivitas

Para analis jarang dapat menentukan parameter model Program Linier seperti (m, n, Cj, aij, bi) dengan pasti karena nilai parameter ini adalah fungsi dari beberapa uncontrolable variabel.

Sementara

itu

solusi

optimal

model

Program

Linier

didasarkan

pada

parameter tersebut. Akibatnya analis perlu mengamati pengaruh perubahan parameter


xxvi

tersebut terhadap solusi optimal. Analisa perubahan parameter dan pengaruhnya terhadap solusi Program Linier disebut Post Optimality Analisis.

Istilah post optimality menunjukkan bahwa analisa ini terjadi setelah diperoleh solusi optimal, dengan mengasumsikan seperangkat nilai parameter yang digunakan dalam model. Atau Analisis Postoptimal (disebut juga analisis pasca optimal atau optimal, usaha

atau untuk

analisis

kepekaan

mempelajari

dalam

nilai-nilai

suasana

dari

analisis

setelah

ketidaktahuan) merupakan

peubah-peubah

suatu

pengambilan keputusan

dalam suatu model matematika jika satu atau beberapa atau semua parameter model tersebut berubah atau menjelaskan pengaruh perubahan data terhadap penyelesaian optimal yang sudah ada.

Dapat diketahui bahwa dunia nyata yang diabstraksikan dan disimplifikasikan ke dalam model PL, tidak sederhana seperti rumusan Program Linier. Oleh karena itu dalam dan kehidupan dunia nyata, selalu dihadapkan pada pertanyaan- pertanyaan keragu-raguaan

seperti

“apa

yang

akan

terjadi,

jika”

ini

dan

itu

berubah?

Persoalan peluang dan ketidakpastiaan pertanyaan-pertanyaan tersebut harus dapat dijawab dalam rangka meyakinkan pendirian terhadap sesuatu yang akan diputuskan kelak. Dengan demikian hasil yang diharapkan tersebut adalah hasil yang memang ”paling mungkin“ dan ”paling mendekati”, atau “perkiraan yang paling tepat”. Uji kepekaan hasil dan pasca optimal (sebut saja selanjutnya analisis postoptimal) yang dapat memberikan jawaban terhadap persoalan-persoalan tersebut diatas. Analisis postoptimal sangat berhubungan erat

dengan atau mendekati apa yang disebut Program Parametrikal atau Analisis

Parametrisasi.

Perubahan atau variasi dalam suatu persoalan Program Linier yang bisaanya dipelajari melalui Post Optimality analysis dapat dipisahkan ke dalam tiga kelompok umum, yaitu : 1. Analisa yang berkaitan dengan perubahan diskrit parameter untuk melihat berapa besar perubahan dapat ditolerir sebelum solusi optimal mulai kehilangan optimalitasnya, ini dinamakan Analisa Sensitivitas. Jika suatu perubahan kecil dalam parameter menyebabkan perubahan drastis dalam solusi, dikatakan bahwa solusi adalah sangat sensitif terhadap nilai parameter itu. Sebaliknya, jika perubahan parameter tidak mempunyai pengaruh besar terhadap solusi dikatakan solusi relatif insensitif terhadap nilai parameter tersebut.


xxvii

2. Analisa yang berkaitan dengan perubahan struktural. Masalah ini muncul bila persoalan Program Linier dirumuskan kembali dengan menambahkan atau menghilangkan kendala dan atau variabel untuk menunjukkan operasi model alternatif. Perubahan struktural ini dapat dimasukkan dalam analisa sensitivitas. 3. Analisa yang berkaitan dengan perubahan kontinu parameter untuk menentukan urutan solusi dasar yang menjadi optimal jika perubahan ditambah lebih jauh, ini dinamakan Parametric-Programming.

Diketahui Model Matematika Persoalan Program Linear adalah sebagai berikut: Menentukan nilai dari X1, X2, X3, …, Xn sedemikian rupa sehingga:

Z = C1X1+C2X2+…+CjXj+…+CnXn =

( Optimal [maksimum/minimum] )

Yang kemudian disebut sebagai Fungsi Tujuan ( Objektive Function ) dengan pembatasan ( fungsi kendala/syarat ikatan): + .

+

.

+

, =,

+

.

.

.

,

, =,

,

.

.

. (2.5)

.

atau dan

.

.

+

+ 0,

, =,

0,

. , =,

,

(

0,

,

= 1, 2, 3, 0,

,

.

= 1, 2, 3, )

,

Berdasarkan Model Matematika Persoalan Program Linier di atas analisis sensitivitas dapat dikelompokkan berdasarkan perubahan-perubahan parameter: 1) Perubahan koefisien fungsi tujuan untuk variabel non basis. 2) Perubahan koefisien fungsi tujuan untuk variabel basis. 3) Perubahan Koefisien teknologi (koefisien input-output). 4) Perubahan Nilai-Sebelah-Kanan (NSK) fungsi kendala. 5) Adanya tambahan fungsi kendala baru (perubahan nilai m).


xxviii

6) Adanya tambahan perubahan (variabel) pengambilan keputusan (Xj) (perubahan nilai n).

2.6

Analisis Sensitivitas pada Metode Hungarian

Dalam persoalan assignment problem tidak semua parameter-parameter di atas dapat diterapkan. Seperti yang diketahui bahwa assignment problem memiliki ciri khusus yaitu: 1. Semua fungsi kendala bertanda ‘=’ 2. Semua nilai aij bernilai 1 atau 0 3. Semua nilai sebelah kanan (NSK) fungsi kendala adalah 1.

Telah dijelaskan sebelumnya bahwa ada 6 jenis analisis sensitivitas pada masalah program linier. Setiap permasalahan yang dapat dibentuk dalam program linier memiliki masalah analisis yang berbeda. Untuk itu, harus diteliti terlebih dahulu jenis analisis sensitivitas yang sesuai dengan Assignment problem.

Untuk mengetahui bagian mana pada Assignment problem yang harus dianalisis, harus diteliti dari bentuk umum Assignment problem itu sendiri. Dari bentuk umum Assignment problem dapat dilihat bahwa fungsi kendala diformulasikan dalam bentuk sebagai berikut: = 1,

= 1,2,

,

(2.6) = 1,

=0

= 1,2,

,

=1

Ini berarti nilai sebelah kanan untuk persamaan kendala telah ditetapkan adalah 1. Ciri ini lah yang membedakan antara masalah transportasi dengan assignment problem. Kalau pada masalah transportasi dikenal adanya permintaan dan persediaan dengan nilai yang berbeda, pada masalah Assignment problem persediaan dan permintaan harus bernilai 1.


xxix

Jadi, sangat tidak mungkin kalau dianalisis nilai sebelah kanan, yang biasa dianalisis pada masalah transportasi. Pada bagian fungsi objektif, bentuk umumnya adalah:

= Sebagai contoh 35 X 11

(2.7) artinya untuk pekerja pertama mengerjakan job pertama dengan biaya

35. Dalam dunia nyata biaya pengerjaan suatu job bisa berubah, baik naik ataupun turun. Selain finansial, biaya dalam hal ini bisa berarti lama waktu pengerjaan dan resiko dalam pengerjaan.

Misalnya suatu perusahan dengan 4 jenis job telah memiliki formula tertentu dalam memilih 4 pekerjanya sehingga semua pekerja dapat bekerja dengan optimal dan tentu saja dengan biaya minimal. Namun seiring berjalan nya waktu dan semakin ahlinya suatu pekerja dalam mengerjakan pekerjaannya, bisa saja pekerja meminta kenaikan upah nya. Akibatnya ada kenaikan biaya disini. Tidak efisien apabila harus merubah formula optimal sebelumnya. Tentu saja perusahaan harus menganalisis hal ini, sampai seberapa jauh perusahaan bisa menaikkan upah pekerja agar hasil tetap optimal dan tidak mengubah formula optimal sebelumnya. Jadi yang memungkinkan untuk melakukan analisis sensitivitas adalah pada parameter perubahan koefisien fungsi tujuan.

Perubahan kofisien fungsi tujuan dapat terjadi karena perubahan keuntungan atau ongkos suatu kegiatan. Misal, diinginkan untuk menentukan pegaruh perubahan keuntungan per unit produk 1 (C1). Pada suatu kasus dimana produk 1 menguntungkan untuk diproduksi, jika C1 turun di bawah nilai tertentu, maka dapat menyebabkan produk 1 yang akan diproduksi menjadi berkurang atau bahkan tidak menguntungkan untuk diproduksi. Sebaliknya jika C1 naik di atas nilai tertentu, dapat menyebabkan kenaikan jumlah produk 1 yang akan diproduksi.

Pada kasus lain lain bisa jadi produk 1 tidak menguntungkan untuk diproduksi karena keuntungan per unit (C1 nya) rendah. Jika C1 turun dapat dipastikan tidak akan berpengaruh terhadap solusi optimal yang ada, tetapi jika C1 naik melebihi nilai tertentu maka produk 1


xxx

menjadi menguntungkan untuk diproduksi. Dari uraian di atas, dapat disimpulkan bahwa terdapat suatu batas atas dan batas bawah (range) perubahan C1 dimana keputusan optimal tidak berpengaruh. Tabel optimal

yang telah didapat dengan metode Hungariannn

menunjukkan

variabel yang menjadi basis dan variabel non basis. Variabel yang koefisien pada tabel optimal adalah 0 merupakan variabel basis. Sebaliknya variabel yang koefisien pada tabel optimal bukan 0 merupakan variabel non basis.

2.6.1 Analisis Sensitivitas pada Variabel Non Basis

Cara yang lazim digunakan untuk menganalisis sensitivitas adalah dengan metode simpleks. Seiring berkembangnya ilmu pengetahuan ada beberapa cara yang dapat digunakan, salah satunya metode Arsham-Khan. Namun dasarnya masih menggunakan metode simpleks. Sama halnya dengan metode yang akan digunakan oleh penulis dalam menganalisis sensitivitas pada assignment problem ini, penulis akan mencoba dengan metode yang sedikit berbeda dan dengan formulasi yang berbeda pula.

Range koefisien dari variabel non basis adalah seberapa besar nilai koefisien variabel non basis dapat diturunkan atau pun dinaikkan sehingga hasil optimal sebelumnya tidak terganggu. Ini berarti ada 2 batasan yang akan dicari yaitu batas bawah dan batas atas range.

Ada beberapa notasi yang akan muncul pada pembahasan berikutnya, antara lain: Cij

= koefisien/ besar biaya karyawan ke-i untuk job ke-j pada tabel awal,

^

C ij

= koefisien/ besar biaya karyawan ke-i untuk job ke-j pada tabel optimal, Batas bawah koefisien variabel non basis adalah hasil pengurangan koefisien variabel

non basis pada tabel awal dengan koefisien pada tabel akhir. Artinya setiap koefisien non basis hanya bisa diturunkan sebesar koefisien pada tabel optimalnya. Hal ini dimaksudkan agar tabel optimal tidak terganggu. Apabila nilai koefisien diturunkan lebih besar dari koefisien tabel optimalnya maka kemungkinan variabel basis akan berubah yang berdampak berubah pula nilai optimalnya. Maka batas bawah range koefisien non basis dapat diformulasikan sebagai berikut:


xxxi ^

Xij = Cij – Cij (2.8) Sedangkan yang menjadi batas atas variabel non basis untuk kasus minimasi adalah adalah M atau bilangan yang sangat besar atau ∞ . Hal ini terjadi karena untuk kasus meminimasi biaya, variabel yang masuk non basis menunjukkan bahwa koefisiennya terlalu besar sehingga tidak ekonomis untuk dipakai. Sehingga andaikan koefisien dari variabel non basis dinaikkan seberapapun, tetap tidak akan mengganggu hasil optimal sebelumnya.

2.6.2 Analisis Sensitivitas pada Variabel Basis

Dalam mencari range untuk variabel basis ada beberapa langkah yang harus diperhatikan: 1. Perhatikan tabel optimal, cari nilai ambang batas yang menyebabkan tabel optimal tidak terganggu. Nilai ambang batas tersebut adalah nilai koefisien variabel non basis terkecil. Notasikan nilai ambang batas tersebut dengan .

2. Cari range variabel basis. Nilai batas bawah range variabel basis adalah: Xij = Cij Xij – (2.9) Dan nilai batas atas range variabel basis adalah: Xij = Cij Xij + (2.10) Sehingga didapat range koefisien variabel basis: (Cij Xij – )

Cij Xij (Cij Xij + ) (2.11)

3. Periksa hubungan suatu variabel basis dengan variabel lain yang satu kolom atau satu baris dengan variabel tersebut. Apakah penambahan

pada langkah sebelumnya telah

layak atau apakah mengganggu tabel optimal yang telah didapat. Ganti range apabila range tersebut tidak layak.


xxxii

2.7

Di

Perbedaan Analisis Sensitivitas dengan Metode Simplex dan Metode Hungarian

dalam

metode

Simplex,

analisis

sensitivitas

selain

digunakan

dalam

pengecekan/pengujian, analisis ini lebih bermanfaat untuk menghindari pengulangan perhitungan dari awal, apabila terjadi perubahan-perubahan pada masalah Linear Programmning Simplex.

Dalam Assignment problem, metode Simplex jarang digunakan dalam mencari nilai optimalitas, karena Assignment problem memiliki keistimewaan dari persoalan-persoalan Linear Programming lainnya. Untuk menemukan perbedaan analisis sensitivitas dengan metode Simplex dan metode Hungarian, akan dibahas sebuah kasus Linear Programming dengan metode Simplex beserta analisis sensitivitasnya, setelah itu akan dibandingkan dengan metode Hungarian.

Jadi yang dibahas dalam kasus ini adalah analisis sensitivitas terhadap koefisien fungsi tujuan meliputi penempatan kisaran pada nilai koefisien secara khusus pada koefisien variabel kontinu. Selama nilai aktual koefisien fungsi tujuan berada dalam kisaran optimalitas, solusi dasar layak sekarang akan tetap optimal. Jadi untuk variabel nonbasis, kisaran optimalitas menyatakan nilai koefisien untuk variabel yang akan tetap menjadi variabel nonbasis. Sebaliknya, kisaran optimalitas untuk variabel basis menyatakan nilai koefisen fungsi tujuan untuk variabel yang akan tetap menjadi bagian dari solusi layak dasar optimal saat ini. Contoh kasus: Maksimumkan :

Z = 60x1 + 30x2 + 20x3

Kendala

8 x1 + 6

x2 +

x3

48

4 x1 + 6

x2 + 1,5 x3

20

:

2 x1 + 1,5 x2 + 0,5 x3 x1, x2, x3

8

0

Konversikan dalam bentuk standar: Maksimumkan :

Z = 60x1 + 30x2 + 20x3

Kendala

8 x1 + 6

x2 +

x3 + x4

48

4 x1 + 6

x2 + 1,5 x3 +x5

20

:

2 x1 + 1,5 x2 + 0,5 x3 +x6 x1, x2, x3, x4, x5, x6

8

0


xxxiii

Iterasi 0 BV

C

x4 x5 x6

0 0 60

Zj - Cj

60 x1 8 4 2

30 x2 6 2 1,5

20 x3 1 1,5 0,5

0 x4 1 0 0

02 x5 0 1 0

03 x6 0 0 1

b 48 20 8

-60

-30

-20

0

0

0

0

1. Memilih kolom kunci Kolom Kunci adalah kolom yang mempunyai nilai pada baris Z yang bernilai negatif dengan angka terbesar. 2. Memilih baris kunci Baris Kunci adalah baris yang mempunyai indeks terkecil. Indeks = Nilai Kanan : Nilai Kolom Kunci. 3. Mengubah nilai-nilai baris kunci Baris Baru Kunci = Baris Kunci : Angka Kunci. 4. Mengubah nilai-nilai selain baris kunci sehingga nilai-nilai kolom kunci (selain baris kunci) = 0 Baris baru = baris lama – (koefisien angka kolom kunci x nilai baris baru kunci) Iterasi 1 BV

C

x4 x5 x1

0 0 60

Zj - Cj

60 x1 0 0 1

30 x2 0 -1 0,75

20 x3 -1 0,5 0,25

0 x4 1 0 0

02 x5 0 1 0

03 x6 -4 -2 0,5

b 16 4 4

0

15

-5

0

0

30

240

60 x1 0 0 1

30 x2 -2 -2 1,25

20 x3 0 1 0

0 x4 1 0 0

02 x5 2 2 -0,5

03 x6 -8 -4 1,5

b 24 8 2

0

15

0

0

10

10

280

Iterasi 2 ( Tabel Optimal ) BV

C

x4 x3 x1

0 20 60

Zj - Cj

Dari tabel ini dapat didefinisikan beberapa hal sebagai berikut: BV = { x4, x3, x1} ; NBV = { x2, x5, x6}


xxxiv

1 = 0

2 8 2 4 0,5 1,5

2.7.1 Perubahan Koefisien Fungsi Tujuan Untuk Variabel Nonbasis

Kasus ini terjadi karena adanya perubahan, baik pada kontribusi keuntungan maupun pada kontribusi ongkos dari kegiatan yang direpresentasikan oleh variabel nonbasis. Pada contoh kasus di atas, satu-satunya variabel keputusan nonbasis adalah x2. Saat ini koefisien fungsi tujuan x2 adalah c2 = 30. Jika c2 berubah dari 30 menjadi ( 30 + ruas kanan untuk variabel basis (VB), yaitu

) tidak mengubah harga

dan b. Karena itu

b, tidak akan berubah sehingga variabel basis

tetap fisibel. Karena c2 adalah variabel nonbasis, maka CBV juga tidak akan berubah. Satusatunya yang koefisien baris ( zj-cj )nya akan berubah karena perubahan c2 ini adalah x2. Dengan demikian, BV akan tetap optimal jika suboptimal jika

0, dan BV akan menjadi

0. Dalam hal terakhir ini, harga z mungkin dapat diperbaiki dengan

memasukkan x2 ke dalam basis. Dari contoh kasus diketahui bahwa:

. Sehingga

= [0 10 10]

6 2 1,5

1 = [0 20 60] 0 (30 +

2 8 2 4 0,5 1,5

)

= 35 – 30 - = 5 Agar 0 jika

0 dan BV tetap optimal, maka ( 5 -

) harus

0 atau

5. Sebaliknya,

akan <

> 5 sehingga BV tidak lagi optimal. Artinya, jika harga c2 naik atau turun sebesar 5

atau kurang, maka BV akan tetap optimal, tetapi jika naik atau turunnya lebih besar dari 5, maka BV tidak lagi optimal.Misalnya jika c2 = 40, solusi basis saat ini akan menjadi suboptimal karena

= -5 sehingga x2 akan menjadi entering variable.


xxxv

2.7.2 Perubahan Koefisien Fungsi Tujuan Untuk Variabel Basis

Mengubah koefisien fungsi tujuan variabel basis (BV) artinya mengubah cBV sehingga beberapa koefisien pada baris 0 (baris zj – cj) dari tabel optimal akan berubah. Misalkan c1 berubah dari 60 menjadi (60 + ). Maka cBV yang baru adalah [ 0 20 60+ ] sehingga: 1 = [0 20 (60 + )] 0

.

=[ 0

10 - 0,5

2 8 2 4 0,5 1,5

10 + 1,5 ]

Koefisien baris 0 (baris zj – cj) menjadi:

=

.

=

.

=[ 0

10 - 0,5

= 5 + 1,25 Karena

0, maka 5 + 1,25

.

.

6 10 + 1,5 ] 2 - 30 1,5 0 -4

=

=[ 0

.

.

10 - 0,5

= 10 - 0,5 Karena

0, maka 10 - 0,5

0 10 + 1,5 ] 1 - 0 0 0 20

=

=[ 0

.

.

10 - 0,5

0 10 + 1,5 ] 0 - 0 1 Universitas Sumatera Utara

xxxvi

= 10 + 0,5 Karena

0, maka 10 + 0,5

0

Dari hasil di atas menunjukkan bahwa penyelesaian basis saat ini akan tetap optimal sepanjang optimal jika -4

-4,

20,

. Dengan kata lain penyelesaian basis saat ini akan tetap

20. Artinya, jika c1 turun sebesar 4 atau kurang, atau c1 naik hingga 20,

maka penyelesaian basis saat ini akan tetap optimal. Dari contoh kasus diatas dapat kita ambil kesimpulan bahwa: 1. Pengerjaan analisis sensitivitas dengan metode Simplex lebih memakan waktu yang lama dibandingkan dengan analisis sensitivitas dengan metode Hungarian. 2. Analisis sensitivitas dengan metode Hungarian hanya dapat dipakai untuk penyelesaian kasus penugasan saja dan hanya terbatas pada analisis koefisien fungsi tujuan, sedangkan metode simplex dapat digunakan untuk masalah program linier selain assignment problem dan dapat menganalisis parameter – parameter dalam program linier tersebut.


BAB II LANDASAN TEORI

Recommend Documents