BAB 2
LANDASAN TEORI
2.1 Matriks
2.1.1 Pengertian Matriks
Matriks adalah susunan segi empat siku-siku dari bilangan bilangan. Bilanganbilangan dalam susunan tersebut dinamakan entri dalam matriks (Anton, 1988: 22). Jika
adalah sebuah matriks, maka akan menggunakan
menyatakan entri yang terdapat di dalam baris
dan kolom
untuk
dari matriks
.
Secara umum matriks dituliskan sebagai berikut:
Matriks di atas disebut matriks berukuran memiliki
baris dan
kali
(ditulis
) karena
kolom.
Contoh :
A
, matriks A berukuran 2 x 3.
Universitas Sumatera Utara
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). Contoh : Misalkan A =
dan B =
Maka A + B =
2.1.3 Perkalian Matriks
adalah matriks m x r dan
Jika
matriks
adalah matriks r x n maka hasil kali
adalah
yang entri-entrinya ditentukan sebagai berikut. Untuk mencari
entri dalam baris- dan kolom- dari kolom- dari matriks
, pilihlah baris- dari matriks
dan
. Kalikanlah entri-entri yang bersesuaian dari baris dan
kolom tersebut bersama-sama dan kemudian tambahkanlah hasil kali yang dihasilkan. Contoh : Diketahui
, dan
Tinjaulah perkalian matriks dan
dan
adalah matriks berukuran
. Karena
adalah matriks berukuran
maka hasil kali
adalah matriks
. Perhitungan-perhitungan untuk hasil kali adalah:
Universitas Sumatera Utara
.
Jadi, diperoleh
2.1.4 Perkalian Matriks Dengan Bilangan
Jika
adalah suatu matriks dan
adalah suatu bilangan, maka hasil kali (product)
adalah matriks yang diperoleh dengan mengalikan masing-masing entri dari oleh . Dalam hal ini ditulis negatif dari
. Khususnya dengan
, diartikan matriks yang diperoleh dari
setiap elemennya dengan
yang disebut
dengan cara mengalikan
atau cukup dengan mengubah tanda semua
elemennya. Contoh :
Diketahui matriks A =
Maka 2A =
2.2
dan (-1)A =
Persoalan Optimasi dan Program Linier
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.
Universitas Sumatera Utara
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 aktivitasaktivitas tersebut. Beberapa contoh situasi dari uraian di atas antara lain adalah pengalokasian fasilitas produksi, persoalan pengalokasian sumber daya nasional untuk kebutuhan domestik, 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)
4.
Menafsirkan jawaban model menjadi jawaban atas masalah yang nyata.
Universitas Sumatera Utara
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. N. Soemartojo (1994 : 71) menyatakan bahwa rumusan umum bentuk
baku suatu program linear dapat dinyatakan sebagai berikut: Carilah nilai
,
,
yang dapat menghasilkan berbagai kombinasi optimum
(maksimum atau minimum). Z=
+
+
+
Pembatas + …
+ …
+ …
… +
…
… +
≤ atau ≥
+
… +
≤ atau ≥
+
… +
≤ atau ≥
+
… +
+
≤ atau ≥
Universitas Sumatera Utara
Syarat variable
≥ 0 untuk j = 1, 2, …, n.
Dengan menggunakan notasi sigma : Fungsi Tujuan
Z=
, untuk j = 1, 2, ..., n
Syarat ikatan Untuk i = 1, 2, ..., m Dan
.
Dengan : = koefisien harga variable pengambilan keputusan dalam fungsi tujuan atau parameter yang dijadikan criteria optimasi. = variable pengambilan keputusan yang harus dicari atau variable aktivitas (keluaran atau output). = Konstanta variable aktivitas ke-j dalam pembatasan (kendala) ke-i. = Sumber daya yang terbatas atau konstanta (nilai sebelah kanan) dari pembatas ke-i, yang membatasi aktivitas berkaitan dengan usaha mengoptimalkan fungsi tujuan, Z
juga disebut sebagai masukan (input).
= Nilai skalar yang berkaitan dengan criteria pengambilan keputusan fungsi tujuan.
2.3 Model Matematika
Model matematika merupakan ungkapan suatu masalah dalam bahasa matematika (Hardi Suyitno, 1997 : 4). Suatu model matematika menggambarkan masalah melalui cara yang lebih singkat dengan menerjemahkan tiap masalah yang di hadapi ke dalam simbol-simbol yang menunjang proses analisis memudahkan menghadapi masalah secara keseluruhan dan mempertimbangkan semua hubungan yang saling terkait secara simultan. Model matematika merupakan
Universitas Sumatera Utara
jembatan bagi pemakaian tehnik-tehnik matematika dan komputer yang canggih untuk menganalisa masalah. Tahapan dalam penyusunan model matematika suatu program linear adalah: 1. Menentukan tipe dari masalah a. Masalah maksimum atau minimum. b. Jika masalahnya menyangkut informasi tentang keuntungan, biasanya masalah memaksimumkan. c. Jika masalahnya berkaitan dengan biaya, biasanya masalah meminimumkan. 2. Mengidentifikasikan variabel keputusan 3. Merumuskan fungsi tujuan: mengkombinasikan informasi ke rumusan fungsi tujuan. 4. Merumuskan kendala. Ada dua pendekatan dasar yaitu: a. Pendekatan ruas kanan. Nilai ruas kanan ( ) dalam daftar informasi merupakan besar maksimum atau minimum dari sumber daya yang tersedia dalam masalah maksimum atau minimum. Arah tanda ketidaksamaan didasarkan pada nilai
maksimum atau minimum sumberdaya.
b. Pendekatan ruas kiri. Dengan
meletakkan semua nilai sebagai koefisien teknis dan
daftarnya dalam baris dan kolom. Baris-baris akan merupakan koefisian teknis dari satu variabel keputusan (Hardi Suyitno, 1997 : 4). 5. Persyaratan nonnegatif
Universitas Sumatera Utara
Pada setiap variabel diberikan nilai nonnegatif , sebab variabel keputusan biasanya mewakili banyaknya unit dari beberapa produksi atau sesuatu untuk doproduksi atau sesuatu untuk diproduksi atau suatu pelayanan tertentu.
2.4 Metode Hungari
Masalah penugasan/penetapan tugas (assignment problem) adalah suatu masalah mengenai pengaturan pada individu (objek) untuk melaksanakan tugas (kegiatan), sehingga dengan demikian biaya/waktu/jarak yang digunakan untuk pelaksanaan tugas tersebut dapat diminimalkan (N. Soemartojo, 1994 : 309).
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).(n-2)…3.2.1 = n! penetapan yang mungkin.
Diantara ke n! penetapan-penetapan yang mungkin ini, harus dicari satu penetapan yang optimal. Untuk mendefinisikan penetapan yang optimal secara tepat, maka akan diperkenalkan 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, detik, dan lain-lain, satuan apapun yang sesuai dengan masalahnya. Didefinisikan matriks biaya (cost matrix) sebagai matriks n x n :
Universitas Sumatera Utara
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 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 penugasan adalah untuk mencari penetapan optimal dalam sebuah matriks biaya. Misalnya dalam menetapkan n tugas kepada n petugas, maka cij dapat merupakan waktu digunakan tugas ke-i oleh petugas ke-j. Sebuah penetapan optimal adalah penetapan untuk mana waktu seluruhnya yang ditempuh untuk menyelesaikantugas tersebut supaya minimum (Howard Anton, 1988 : 60).
Secara mendetail model untuk masalah penugasan dapat ditulis dalam suatu bentuk program linear sebagai berikut:
Universitas Sumatera Utara
Meminimumkan
Z=
Dengan batasan:
Dimana:
Z
= fungsi tujuan problema
xij
= variabel keputusan
cij
= nilai kontribusi objek i terhadap tugas j
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
Langkah – langkah penyelesaian dengan metode Hungari adalah sebagai berikut: 1. Menyusun matriks biaya. 2. Mengurangkan elemen-elemen pada setiap baris dengan elemen terkecil pada baris yang sama. 3. Menggurangkan 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.
Universitas Sumatera Utara
5. Cari bilangan terkecil dari bilangan-bilangan yang tak tertutup garis, misalkan e. Selanjutnya:
Semua elemen yang tak tertutup garis dikurangi e.
Semua elemen yang yang tertutup oleh satu garis tidak diubah.
Semua elemen yang tertutup oleh dua garis ditambah dengan e.
Setelah diperoleh tabel baru kembali ke langkah – 4.
2.5 Analisis Sensitivitas pada Metode Hungari
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. nilai sebelah kanan (NSK) fungsi kendala adalah 1. 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:
n
∑X i =1
ij
=1
ij
=1
n
∑X j =1
Universitas Sumatera Utara
Ini berarti nilai sebelah kanan untuk persamaan kendala telah ditetapkan adalah 1. Ciri ini 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. Jadi, sangat tidak mungkin kalau dianalisis nilai sebelah kanan, yang biasa dianalisis pada masalah transportasi.
Pada bagian fungsi objektif, bentuk umumnya adalah:
n
Z = ∑ cij xij i =1 n
Z = ∑ Cij X ij j =1
Sebagai contoh 35 X 11 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 berjalannya waktu dan semakin ahlinya suatu pekerja dalam mengerjakan pekerjaannya, bisa saja pekerja meminta kenaikan upah. 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
Universitas Sumatera Utara
pengaruh 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 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 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 hungari 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.
Universitas Sumatera Utara
