MODEL INPUT-OUTPUT DALAM MASALAH NETWORK FLOW
DWI PUTRI EFESIA
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
ix
ABSTRAK DWI PUTRI EFESIA. Model Input-Output dalam Masalah Network Flow. Dibimbing oleh FARIDA HANUM dan RETNO BUDIARTI. Proses produksi adalah suatu proses yang dilakukan oleh dunia usaha untuk mengubah input menjadi output. Menurut jenis output dan aktivitasnya, dunia usaha dapat diklasifikasikan ke dalam berbagai sektor yang saling berkaitan. Untuk itu, diperlukan model yang mampu menganalisis keterkaitan antarsektor tersebut, yaitu model input-output (IO). Dalam model IO dikenal tabel IO yang menyajikan informasi tentang transaksi antara barang dan jasa yang terjadi antarsektor ekonomi yang disajikan dalam bentuk matriks dengan jumlah seluruh input harus sama dengan jumlah seluruh output. Pada karya ilmiah ini, ditunjukkan bahwa transaksi antarsektor yang terjadi dalam tabel IO dapat dianalisis dengan menggunakan network flow. Melalui teori network terbukti bahwa setiap sektor memiliki peranan baik sebagai produsen maupun konsumen. Keseluruhan sektor yang terkait dalam tabel IO dapat dianalisis dengan network flow. Melalui teori network flow terbukti bahwa jumlah seluruh input harus sama dengan jumlah seluruh output. Pada karya ilmiah ini, juga dibahas formulasi masalah meminimumkan biaya yang dikenal dengan masalah sirkulasi biaya minimum.
ix
ABSTRACT DWI PUTRI EFESIA. Input-Output Model in Network Flow Problem. Supervised by FARIDA HANUM and RETNO BUDIARTI. Production process is a process, which is done by industry, to transform input into output. According to the type of output and its activity, industry can be classified into various sectors, which are connected to each other. Therefore, a model to analyze the connection among sections is needed. The model is known as input-output model (IO model). IO model presents an IO table, which shows informations about the transaction between goods and services in each economic sector. Furthermore, the IO model also shows that the amount of all input is the same as the amount of all output. In this paper, the transaction of each economic sector in IO table is analyzed using network flow theory. The formulated network flow problem implies that each sector represents partly as a producer and also as a consumer. This paper also solves a minimum cost circulation problem.
ix
MODEL INPUT-OUTPUT DALAM MASALAH NETWORK FLOW
DWI PUTRI EFESIA
Skripsi sebagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPERTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2010
ix
Judul Skripsi : Model Input-output dalam Masalah Network Flow Nama : Dwi Putri Efesia NIM : G54053933
Menyetujui
Pembimbing I,
Pembimbing II,
Dra. Farida Hanum, M.Si. NIP: 19651019 199103 2 002
Ir. Retno Budiarti, MS. NIP: 19610729 198903 2 001
Mengetahui: Ketua Departemen,
Dr. Berlian Setiawaty, MS. NIP: 19650505 198903 2 004
Tanggal Lulus:
ix
KATA PENGANTAR Puji syukur penulis panjatkan kepada Tuhan Yesus Kristus atas berkat, rahmat dan kasih karunia-Nya baik sehat jasmani maupun rohani sehingga penulis mampu menyelesaikan karya ilmiah ini. Berbagai kendala dialami oleh penulis sehingga membutuhkan bantuan, dukungan, dan semangat orang-orang yang telah berkontribusi dalam pembuatan karya ilmiah ini. Oleh karena itu, dalam kesempatan ini penulis mengucapkan terima kasih kepada: 1.
2. 3. 4. 5. 6. 7. 8. 9.
10. 11.
12. 13. 14. 15.
keluarga tersayang: papa dan mama yang selalu memberikan waktu untuk mendengar cerita suka dan duka selama penulisan karya ilmiah ini, doa dan semangat yang diberikan. Untuk kak Eva, bang Ridho, Aam, Erma, Sutoyo, Rional, Jetro, bapatua dan inangtua Kaylla yang selalu mengingatkan untuk tetap berserah pada Yesus dan memotivasi untuk cepat-cepat lulus, serta sanak saudara lainnya; Dra. Farida Hanum, M.Si. selaku dosen pembimbing I yang telah meluangkan waktu dan pikiran dalam membimbing, memberi motivasi, ilmu, dan doa; Ir. Retno Budiarti, MS. selaku dosen pembimbing II yang telah memberikan ilmu, saran, dan motivasi; Dr. Toni Bakhtiar, M.Sc. selaku dosen penguji yang telah memberikan ilmu dan saran; semua dosen Departemen Matematika yang telah memberikan ilmu dan sarannya; staf Departemen Matematika: pak Yono, mas Heri, mas Deny, mas Bono, bu Ade, dan bu Susi yang selalu memberikan semangat dan doa; teman-teman satu bimbingan: Bima Saputra, Rian Wahyuni, Yusep Maulana, dan Nur Wahyuni; keluarga kecilku: Agnes, Ayu, Lisda, Nyoman, Ricken yang selalu memberikan waktu untuk mendengarkan cerita, memberi semangat, nasehat, doa dan persahabatnnya; teman-teman Matematika 42: Achy, Acuy, Ardi, Awi, Ayeep, Bayu, Boy, Danu, Dendy, Dewi, Die2, Djawa, Eko, Erlin, Ety, Eyyi, Fachri, Gita, Hapsari, Herry, Hesti, Hikmah, Idha, Ilie, Iput, Jane, Kinun, Lela, Lina, Luri, Mega, Mira, Mocco, Niken, Nofita, Nola, Oby, Otonk, Pipit, Rendi, Ridwan, Rima, Rita, Sapto, Septian, Siti, Tia, Titi, Vera, Vino, Vita, Warno, Wiwi, Yudi yang telah mewarnai kisah bahagia, sedih, susah selama tiga tahun berada di Departemen Matematika; teman Matematika 43: Kabil yang telah memberikan waktunya, ilmu, dan semangatnya; teman-teman kos Wisma Stevia: Ani, Anyez, Cece, Eboy, Mizz, Pola, Thesa, K’Valen, Sonya, Beatrix, Yori, Cathy, Poppy, Dian, mas Jay beserta pendamping hidupnya yang selalu tabah mendengar teriakan selama tiga tahun satu atap bersamaku, menyemangatiku, dan melakukan hal-hal yang belum pernah dilakukan serta doa yang dipanjatkan; bang Ico, bang Wastin, dan kak Ochie yang telah mengisi kehidupanku dan selalu memberikan semangat, hiburan, petuah, serta doa; temanku Kiki dan Miu yang senantiasa memberikanku semangat, menghibur, dan mengerti keadaanku; teman-teman panitia Natal CIVA 2008 yang telah mengajarkan arti berserah pada-Nya; semua pihak yang ikut membantu baik secara moril maupun materiil.
Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya bidang Matematika dan menjadi inspirasi bagi penelitian-penelitian selanjutnya.
Bogor, Januari 2010
Dwi Putri Efesia
ix
RIWAYAT HIDUP Penulis dilahirkan di Jakarta pada tanggal 25 Maret 1987 sebagai anak ketiga dari empat bersaudara, anak dari pasangan Drs. Osner Silalahi, S.Sos. dan Dorima Sihombing. Pada tahun 1999 penulis lulus dari SD San Fransisco Balige kemudian tahun 2002 lulus dari SLTP Putri Cahaya Medan. Tahun 2005 penulis lulus dari SMAN 1 Pangkalpinang dan pada tahun yang sama penulis lulus seleksi masuk IPB melalui jalur SPMB (Seleksi Penerimaan Mahasiswa Baru). Pada tahun 2006, penulis memilih jurusan Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam. Selama mengikuti perkuliahan, penulis menjadi asisten mata kuliah Kalkulus II tahun ajaran 2007/2008 dan asisten mata kuliah Metode Statistika tahun ajaran 2008/2009. Penulis juga aktif dalam organisasi kemahasiswaan di kampus, seperti organisasi keagamaan Keluarga Mahasiswa Katolik (KEMAKI) sebagai Koordinator bidang Komunikasi Eksternal tahun 2006/2007 dan organisasi himpunan profesi Departemen Matematika yang dikenal dengan GUMATIKA (Gugus Mahasiswa Matematika) sebagai Koordinator Departemen Kewirausahaan tahun 2006/2007. Selain itu, penulis juga terlibat dalam beberapa kegiatan, antara lain Anggota seksi Humas Politik Expose tahun 2005, Anggota seksi Dana dan Usaha (Danus) Natal Civa IPB 2006, Anggota seksi Dana dan Usaha Try Out SPMB se-Bogor 2007, Anggota Komdis (Komisi Kedisplinan) Ramah Tamah Civitas Matematika 2007, Peserta Pelatihan Penyegaran Materi Matematika Universitas 2007, Koordinator seksi Acara Natal Civa IPB 2008, Peserta Olimpiade Matematika Nasional Tingkat Mahasiswa 2008.
ix
DAFTAR ISI Halaman DAFTAR TABEL ................................................................................................................... ix DAFTAR GAMBAR ..............................................................................................................
ix
DAFTAR LAMPIRAN ...........................................................................................................
ix
I
PENDAHULUAN 1.1 Latar Belakang ......................................................................................................... 1.2 Tujuan ....................................................................................................................... 1.3 Metode Penulisan .....................................................................................................
1 2 2
LANDASAN TEORI 2.1 Matriks ...................................................................................................................... 2.2 Teori Pengali Lagrange ............................................................................................. 2.3 Graf ........................................................................................................................... 2.4 Pemrograman Linear ................................................................................................. 2.5 Dualitas Pemrograman Linear ...................................................................................
2 5 5 9 10
MODEL INPUT-OUPUT 3.1 Model Kuantitas ........................................................................................................ 3.2 Model Harga .............................................................................................................. 3.3 Kombinasi Model Kuantitas dan Model Harga ......................................................... 3.4 Model Input-Output dalam Teori Network ................................................................ 3.5 Model Input-Output dalam Network Flow ................................................................ 3.5.1 Dualitas Network Flow ..................................................................................... 3.5.2 Input-Output dan Sirkulasi Biaya Minimum ....................................................
15 17 18 20 23 24 26
SIMPULAN DAN SARAN 4.1 Simpulan .................................................................................................................. 4.2 Saran ........................................................................................................................
27 27
DAFTAR PUSTAKA ............................................................................................................
28
LAMPIRAN ...........................................................................................................................
29
II
III
IV
ix
DAFTAR TABEL 1 2 3 4
Halaman Hubungan antara variabel keputusan dan kendala pada masalah primal dan masalah dual ............................................................................................................ 11 Tabel input-output .......................................................................................................... 12 Matriks gabungan input-output ....................................................................................... 13 Contoh matriks gabungan input-output .......................................................................... 14
DAFTAR GAMBAR 1 2 3 4 5 6 7 8 9 10 11 12
Halaman Graf G = (V, E)................................................................................................................ 5 Graf D = (V, A) ............................................................................................................... 6 Sisi berarah menjauhi atau mendekati, suksesor, dan predesesor ................................... 6 Digraf D = (V, A) dengan loop di simpul c ..................................................................... 6 6 Multidigraf ...................................................................................................................... Pseudodigraf ................................................................................................................... 7 Source dan sink ............................................................................................................... 7 Network ........................................................................................................................... 7 8 Graf berarah dan matriks incidence ................................................................................ 8 Graf takberarah dan matriks incidence ........................................................................... 20 Graf berarah dari Tabel 4 ................................................................................................ Graf berarah dari Tabel 3 ................................................................................................ 23
DAFTAR LAMPIRAN 1 2 3 4 5 6 7 8 9
Halaman Pembuktian Teorema 1 beserta Beberapa Teorema yang Mendukung Pembuktian Tersebut ...................................................................................................... 30 Pembuktian Teorema 3 beserta Teorema yang Mendukung Pembuktian Tersebut ......... 31 Syntax Program LINDO 6.1 untuk Menyelesaikan Contoh 8 32 beserta Hasil yang Diperoleh .......................................................................................... Pembuktian Persamaan (3.11) ........................................................................................ 33 Syntax Program Mathematica 7.0 untuk Menyelesaikan Masalah Perubahan Vektor throughput pada Model Kuantitas beserta Hasil yang Diperoleh ....................... 34 Syntax Program Mathematica 7.0 untuk Menyelesaikan Masalah Perubahan Vektor throughput pada Model Harga beserta Hasil yang Diperoleh ............................. 34 Pembuktian Persamaan (3.21) beserta Beberapa Persamaan yang terkait dengan Pembuktian Tersebut .......................................................................................... 35 Syntax Program LINDO 6.1 untuk Menyelesaikan Masalah Primal 35 pada Contoh 12 beserta Hasil yang Diperoleh ................................................................ Syntax Program LINDO 6.1 untuk Menyelesaikan Masalah Dual pada Contoh 13 beserta Hasil yang Diperoleh ................................................................ 36
ix
1
I PENDAHULUAN 1.1 Latar belakang Proses produksi adalah suatu proses yang dilakukan oleh dunia usaha untuk mengubah input menjadi output. Contoh dunia usaha adalah pengusaha besar, seperti berbagai perusahaan yang banyak dikenal masyarakat, pengusaha kecil golongan ekonomi lemah yang menjajakan dagangan di kaki lima, pengusaha industri rumah tangga serta orangorang yang memproduksi komoditas barang dan jasa. Menurut jenis output dan aktivitasnya, dunia usaha dapat diklasifikasikan ke dalam berbagai sektor. Klasifikasi sektor yang paling umum adalah pembagian sektor ke dalam tiga sektor, yaitu sektor primer, sekunder, dan tersier. Suatu sektor dianggap memproduksi satu jenis komoditas yang sesungguhnya merupakan komoditas agregat dari berbagai jenis komoditas yang dikelompokkan ke dalam sektor yang bersangkutan. Output yang diproduksi oleh suatu sektor, misalkan saja sektor , didistribusikan ke dua pemakai. Pemakai pertama ialah pemakai yang menggunakan output untuk proses produksi lebih lanjut (menjadikan output sebagai bahan baku atau input-antara) sedangkan pemakai kedua adalah pelakupelaku ekonomi di dalam perekonomian. Pada umumnya terdapat empat pelaku ekonomi, yaitu rumah tangga, yang mendapatkan penerimaan rumah tangga dari upah dan gaji anggota rumah tangga serta memiliki pengeluaran berupa konsumsi rumah tangga; perusahaan, yang mendapatkan keuntungan usaha dan memiliki pengeluaran berupa investasi; pemerintah yang memperoleh pemasukan berupa pajak pemerintah dan memiliki pengeluaran berupa pengeluaran konsumsi pemerintah, investasi pemerintah, dan subsidi; dan pelaku ekonomi yang terakhir adalah luar negeri. Dunia perekonomian tidak saja dipandang dari segi distribusi output tetapi juga segi input. Input yang dibutuhkan dalam proses produksi sektor bukan hanya input-antara (bahan baku) melainkan membutuhkan inputprimer yang berupa faktor produksi, seperti tenaga kerja, modal, dan tanah. Penggunaan input-primer dalam proses produksi akan menghasilkan balas jasa faktor produksi, antara lain berupa gaji atau upah bila menggunakan input tenaga kerja. Balas jasa inilah yang disebut nilai tambah dari proses produksi tersebut.
Berdasarkan uraian di atas diperlukan suatu model yang mampu menganalisis keterkaitan antarsektor tersebut, yaitu model input-output (IO). Semenjak diperkenalkan oleh W. Leontief pada tahun 1930-an, model input-output (IO) telah berkembang menjadi salah satu alat analisis yang ampuh dalam melihat hubungan antarsektor dalam suatu perekonomian. Hubungan antarsektor ini mulai menjadi penting di pertengahan abad ini, sejak analisis pembangunan ekonomi tidak hanya mementingkan pertumbuhan ekonomi semata tetapi juga mulai melihat pembagian pertumbuhan di antara faktorfaktor produksi dan juga sumber-sumber pertumbuhan itu sendiri. Model IO Leontief didasarkan atas model keseimbangan umum (general equilibrium) (Nazara 2005). Beberapa kegunaan dari analisis IO, antara lain untuk memperkirakan dampak permintaan-akhir terhadap output, nilai tambah, impor, penerimaan pajak, dan penyerapan tenaga kerja di berbagai sektor produksi; melihat komposisi penyediaan dan penggunaan barang dan jasa terutama dalam analisis terhadap kebutuhan impor dan kemungkinan substitusinya; mengetahui sektor-sektor yang pengaruhnya paling dominan terhadap pertumbuhan ekonomi dan sektor-sektor yang sensitif terhadap pertumbuhan perekonomian; serta menggambarkan perekonomian suatu wilayah dan mengidentifikasi karakteristik struktural suatu perekonomian wilayah (Firdaus et al. 2007). Dalam model IO dikenal tabel IO yang menyajikan informasi tentang transaksi barang dan jasa yang terjadi antarsektor ekonomi yang disajikan dalam bentuk matriks dengan jumlah seluruh input harus sama dengan jumlah seluruh output. Tabel inputoutput menjadi dasar pembentukan tipe model input-output, yaitu model kuantitas dan model harga. Dalam karya ilmiah ini akan dibahas bahwa transaksi antarsektor yang terjadi dalam tabel IO dapat dianalisis dengan menggunakan teori network. Melalui teori network akan terlihat bahwa setiap sektor memiliki peranan baik sebagai produsen maupun konsumen. Keseluruhan sektor yang terkait dalam tabel IO dapat dianalisis dengan network flow. Melalui network flow akan terlihat pula bahwa jumlah seluruh input harus sama dengan jumlah seluruh output.
2
Transaksi tidak terlepas dari masalah biaya yang dikeluarkan untuk melakukan transaksi tersebut. Pada umumnya para pelaku ekonomi sangat memperhatikan masalah tersebut. Adapun contoh biaya yang biasanya dikeluarkan adalah biaya transportasi, biaya tambahan, dll. Untuk itu, karya ilmiah ini akan mengkaji bagaimana cara meminimumkan biaya tersebut dengan memformulasi masalah ke dalam pemrograman linear. Dalam hal ini, formulasi tersebut dikenal dengan istilah sirkulasi biaya minimum. Formulasi tersebut diharapkan dapat membantu para pelaku ekonomi untuk meminimumkan biaya sehingga mampu memaksimumkan kuantitas output yang dapat diproduksi.
1.2 Tujuan Adapun tujuan karya ilmiah ini meliputi: 1. menganalisis model IO sebagai salah satu contoh kasus khusus dalam teori network dan network flow, 2. memformulasikan model IO dalam network flow, yaitu sirkulasi biaya minimum. 1.3 Metode Penulisan Metode yang digunakan dalam penulisan karya ilmiah adalah studi literatur. Materi karya ilmiah ini diambil dari jurnal yang berjudul Input-output models, directed graphs and flows in network yang ditulis oleh J. Asger Olsen pada tahun 1992. Selain itu, bahan-bahan yang menunjang penulisan karya ilmiah ini diperoleh dari buku dan situs internet yang terkait dengan topik karya ilmiah ini.
II LANDASAN TEORI Untuk memahami masalah-masalah yang terjadi pada karya ilmiah ini diperlukan pengertian beberapa konsep berikut ini.
Definisi 3 (Matriks Identitas) Matriks identitas berukuran matriks dengan
2.1 Matriks
adalah
1 , jika
Definisi 1 (Matriks) Matriks adalah kumpulan angka (sering disebut elemen) yang disusun menurut baris dan kolom sehingga berbentuk persegi panjang dengan panjang dan lebarnya direpresentasikan oleh banyaknya baris dan kolom. yang berukuran Matriks dapat ditulis dalam bentuk berikut . (Supranto 1992)
. 0 , jika (Anton & Rorres 2004) Definisi 4 (Invers Matriks) berukuran Suatu matriks dikatakan memiliki invers atau dapat dibalik jika terdapat matriks sehingga . Matriks disebut invers dengan adalah matriks identitas. (Leon 2001) Teorema
1
(Matriks Invers dan Determinan) dapat dibalik atau memiliki Matriks jika dan hanya jika det . invers (Anton & Rorres 2004)
Definisi 2 (Matriks Diagonal) Matriks berukuran disebut matriks diagonal jika untuk . (Leon 2001)
Bukti: dapat dilihat di Lampiran 1
Berikut adalah contoh matriks diagonal
Matriks Partisi
.
Definisi 5 (Matriks Partisi) Matriks partisi adalah matriks yang dibagibagi menjadi beberapa matriks yang lebih
3
kecil dengan cara menggambar garis-garis horizontal antara baris-baris dan garis-garis vertikal antara kolom-kolom. (Leon 2001) Contoh 1 Misalkan diberikan matriks
.
Jika garis-garis digambarkan antara baris kedua dan baris ketiga serta antara kolom ketiga dan kolom keempat maka matriks akan terbagi menjadi empat submatriks, yaitu , , , dan sehingga bentuknya
.
Jadi
.
Contoh 3 dan
Misalkan Definisi 6 (Penjumlahan dan Pengurangan Matriks Partisi) dan matriks Misalkan matriks merupakan matriks partisi yang . Penjumlahan dapat berukuran dilakukan bila banyaknya baris dan kolom untuk dan harus sama besarnya, sehingga diperoleh bentuk umum penjumlahan matriks partisi sebagai berikut
Misalkan
dan
, Jadi
.
maka Definisi 7 (Perkalian Matriks Partisi) berukuran Misalkan matriks
.
(Supranto 1992) Contoh 2 Misalkan
dan
dan matriks berukuran merupakan matriks partisi. Perkalian dapat dilakukan jika banyaknya kolom matriks sama dengan banyaknya baris matriks sehingga diperoleh bentuk umum perkalian sebagai berikut
4
Misalkan
Jadi
dan
.
Teorema 2 (Invers Matriks Partisi) Misalkan matriks partisi
,
dan dengan
invers matriks partisi , maka
dengan .
, , dan merupakan matriks segi. Jika adalah submatriks tak singular dari matriks maka
(Supranto 1992) Contoh 4 Misalkan
dan
(Zhang 1999) Bukti: lihat Zhang 1999. Contoh 5 Misalkan diberikan matriks partisi
,
maka dari Teorema 2: , dengan
,
,
5
dengan yang merupakan fungsi kontinu dan terturunkan. Solusi masalah di atas dapat dihampiri dari solusi masalah takberkendala, yaitu untuk sehingga meminimumkan diperoleh fungsi Lagrange sebagai berikut , dengan skalar disebut pengali Lagrange. Misalkan merupakan minimizer dari , meminimumkan nilai , maka gradien fungsi Lagrange pada kondisi optimum sama dengan nol sedemikian sehingga
(Bertsekas 2003) 2.3 Graf Suatu graf adalah pasangan terurut dengan himpunan takkosong dan himpunan pasangan berhingga dan takterurut yang menghubungkan elemenelemen V, dinotasikan dengan . Elemen disebut verteks (node, simpul) sedangkan elemen disebut sisi (edge) dan dituliskan sebagai , yakni sisi yang menghubungkan simpul dengan simpul dengan . (Foulds 1992) Graf yang dimaksud pada definisi di atas disebut graf takberarah (undirected graph). Ilustrasi graf takberarah dapat dilihat pada Gambar 1 berikut. Jadi
b
.
e c
f
2.2 Teori Pengali Lagrange Misalkan diberikan masalah minimisasi berkendala persamaan sebagai berikut Minimumkan terhadap ,
a
d
Gambar 1 Graf Pada Gambar 1 diperlihatkan bahwa
.
6
dan . Definisi 8 (Incident dan Adjacent) Misalkan diberikan graf . Jika dengan maka dan dikatakan adjacent di dan incident dengan dan . (Chartrand et al. 1993) Pada Gambar 1, dan dikatakan adjacent di dengan dan .
maka incident
dan
Definisi 9 (Derajat Simpul) Derajat (degree) dari simpul , dinyatakan dengan deg , adalah banyaknya sisi yang incident dengan . (Chartrand et al. 1993) .
Pada Gambar 1, terlihat bahwa deg
Definisi 10 (Graf Berarah/Digraf) Graf berarah (digraph) adalah pasangan terurut dengan himpunan takkosong dan hingga dan himpunan pasangan terurut yang menghubungkan elemen-elemen di dinotasikan dengan . Elemenelemen dari disebut sisi berarah (arc) dan dituliskan sebagai dengan . (Foulds 1992) Ilustrasi graf berarah dapat dilihat pada Gambar 2 berikut.
e c f
Ilustrasi loop pada digraf dapat dilihat pada Gambar 4 berikut.
e c f d
Gambar 4 Digraf
dengan loop di simpul c.
Pada Gambar 4 diperlihatkan bahwa dan .
Ilustrasi multidigraf Gambar 5 berikut.
d
Gambar 2 Graf
Gambar 3 Sisi berarah menjauhi atau mendekati, suksesor dan predesesor. Definisi 12 (Loop) Loop adalah sisi, baik berarah maupun takberarah, yang incident dengan simpul yang sama. (Foulds 1992)
Definisi 13 (Multidigraf) Suatu digraf dikatakan multidigraf bila graf tersebut memiliki lebih dari satu sisi berarah yang incident dengan suatu pasang simpul. (Foulds 1992)
a
b
Misalkan diberikan digraf . Jika maka sisi berarah ini dikatakan menjauhi simpul dan mendekati simpul . Simpul disebut predesesor bagi simpul dan simpul disebut suksesor bagi simpul . (Foulds 1992) Ilustrasi suksesor dan predesesor dapat dilihat pada Gambar 3 berikut.
dapat
dilihat
.
Pada Gambar 2 diperlihatkan bahwa dan
a
b
c
d
. Definisi 11 (Sisi Berarah Menjauhi atau Mendekati, Suksesor, dan Predesesor)
pada
7
Gambar 7 Source dan sink.
Gambar 5 Multidigraf. Gambar 5 dikatakan multidigraf karena dan dihubungkan oleh dua sisi simpul berarah, yaitu sisi berarah dan . Definisi 14 (Pseudodigraf) Suatu digraf dikatakan pseudodigraf bila graf tersebut memiliki lebih dari satu sisi berarah yang incident dengan suatu pasang simpul dan memiliki loop. (Foulds 1992)
Ilustrasi pseudodigraf dapat dilihat pada Gambar 6 berikut.
a
Pada Gambar 7, simpul
sebagai source dan
simpul sebagai sink. Definisi 17 (Network) adalah suatu graf berarah Network dengan setiap sisi berarahnya memiliki kapasitas, menerima flow, dan jumlah flow tidak melebihi kapasitas sisi berarah . Suatu flow, misalnya dinotasikan dengan adalah fungsi bernilai integer yang didefinisikan pada himpunan sisi berarah pada suatu network sedemikian sehingga untuk setiap sisi berarah dengan menyatakan kapasitas sisi berarah bernilai taknegatif dan menyatakan flow sepanjang sisi berarah . (Balakrishnan 1997)
b
Ilustrasi network dapat dilihat pada Gambar 8 berikut. c
d 4,5
Gambar 6 Pseudodigraf.
s
Gambar 6 dikatakan pseudodigraf karena simpul dan dihubungkan dengan dua sisi berarah, yaitu sisi berarah dan dan terdapat loop di simpul . Definisi 15 (Source) Source adalah simpul dengan derajat masuk (indegree) nol. (Chartrand et al. 1993) Definisi 16 (Sink) Sink adalah simpul dengan derajat keluar (outdegree) nol. (Chartrand et al. 1993) Ilustrasi source dan sink dapat dilihat pada Gambar 7 berikut.
a t s c b
a
1,1
3,5 2,3
c
b
4,4 t
3,4 1,2
d
2,2
Gambar 8 Network. Pada Gambar 8, setiap sisi berarah memiliki dua buah bilangan. Bilangan pertama menunjukkan flow pada sisi berarah sedangkan bilangan kedua menunjukkan kapasitas. Misalkan, pada sisi berarah nilai flow adalah 3 sedangkan kapasitasnya sebanyak 5. Definisi 18 (Network Flow) Network flow merupakan suatu kasus dalam PL (Pemrograman Linear) yang memiliki struktur khusus dan menggunakan representasi graf. Bentuk suatu masalah network flow dikenal dengan sebutan masalah network flow biaya minimum (minimum cost network flow). Pada masalah ini, fungsi objektifnya berupa minimisasi biaya yang terkait pada sisi berarah dengan kendalakendala yang meliputi kendala konservasi flow dan kendala pembatasan flow. , biaya Misalkan network pengangkutan setiap unit flow komoditas pada dinyatakan dengan , sisi berarah
8
banyaknya unit flow komoditas melalui sisi berarah untuk setiap dinyatakan dengan , batas bawah dan batas atas banyaknya flow komoditas yang diangkut untuk setiap melalui sisi berarah berturut-turut dinyatakan dengan dan
, dan supply/demand pada simpul
dinyatakan dengan . Formulasi umum suatu masalah network flow diberikan sebagai berikut.
1, jika sisi berarah meninggalkan simpul -1, jika sisi berarah masuk simpul 0, lainnya untuk graf takberarah 1, jika sisi j incident dengan simpul
Min
0, lainnya
dengan kendala
merupakan simpul kedengan . (Thulasiraman & Swamy 1992) Ilustrasi matriks incidence pada graf berarah dapat dilihat pada Gambar 9 berikut.
Jika maka disebut supply pada simpul dan simpul disebut simpul supply. Jika maka disebut demand pada simpul dan simpul disebut simpul demand. Jika maka simpul disebut simpul transshipment. Batas atas, , disebut kapasitas sisi berarah. Kendala pertama menyatakan kendala konservasi flow, yaitu kendala yang menjaga keseimbangan flow pada suatu simpul (flow yang masuk ke simpul sama dengan flow yang keluar dari simpul). Kendala kedua menyatakan kendala pembatasan flow, yaitu kendala yang membatasi banyaknya flow yang dapat melewati sisi berarah. (Ahuja et al. 1993) Matriks pada Graf Graf dapat direpresentasikan dalam bentuk matriks. Untuk memahami masalah tersebut diperlukan pengertian beberapa konsep berikut. Definisi 19 (Matriks Incidence) dengan simpul Misalkan sebuah graf dan sisi (edge) maka matriks incidence dari graf yang terdiri atas baris untuk setiap simpul dan kolom untuk setiap sisi (edge) dengan elemen dari matriks
didefinisikan sebagai:
untuk graf berarah
e1
a e2
b
e3
e4
e5
c e6
d e7
e
Gambar 9 Graf berarah dan matriks incidence. Pada graf dalam Gambar 9, misalkan , , , dan .
,
Ilustrasi matriks incidence pada graf takberarah dapat dilihat pada Gambar 10 berikut. a
e1
b
e2
e4 e3 c e6
d
e5 e
e7
9
Sebagai merupakan
contoh, fungsi linear, sedangkan bukan fungsi linear. Jika fungsi linear dan sembarang bilangan maka merupakan persamaan linear.
Gambar 10 Graf takberarah dan matriks incidence. ,
Pada graf dalam Gambar 10, misalkan , , , dan .
Definisi 20 (Matriks Boole) Matriks Boole berukuran adalah matriks dengan elemen-elemennya hanya terdiri atas dua nilai, yaitu 1 0 Pada karya ilmiah ini, matriks Boole yang digunakan terdiri atas dua jenis, yaitu matriks masukan dan matriks keluaran. Matriks masukan didefinisikan sebagai 1, jika sisi berarah meninggalkan simpul 0, lainnya
Matriks keluaran didefinisikan sebagai 1, jika sisi berarah
masuk ke
simpul
0, lainnya
(Olsen 1992)
Definisi 22 (Pertidaksamaan Linear) Untuk sembarang fungsi linear dan sembarang bilangan , pertidaksamaan dan adalah pertidaksamaan linear. (Winston 2004) Pemrograman linear (PL) atau linear programming adalah suatu masalah optimisasi yang memenuhi ketentuan-ketentuan sebagai berikut. a) Tujuan masalah tersebut adalah memaksimumkan atau meminimumkan suatu fungsi linear dari sejumlah variabel keputusan. Fungsi yang akan dimaksimumkan atau diminimumkan disebut fungsi objektif. b) Nilai variabel-variabel keputusannya harus memenuhi suatu himpunan kendala. Setiap kendala harus berupa persamaan linear atau pertidaksamaan linear. c) Ada pembatasan tanda untuk setiap variabel dalam masalah ini. Untuk pembatasan tanda sembarang variabel menentukan harus taknegatif atau tidak dibatasi tandanya (unrestricted in sign). (Winston 2004) Solusi PL mempunyai bentuk standar seperti yang didefinisikan sebagai berikut.
2.4 Pemrograman Linear Salah satu konsep dasar yang harus dipahami terkait dengan konsep pemrograman linear di antaranya adalah fungsi linear dan pertidaksamaan linear.
Definisi 23 (Bentuk Standar PL) Pemrograman linear min terhadap
Definisi 21 (Fungsi Linear) menyatakan Misalkan suatu fungsi dalam variabel-variabel . Fungsi dikatakan linear jika dan hanya jika untuk suatu himpunan konstanta ,
dikatakan PL dalam bentuk standar, dengan dan vektor-vektor berukuran , vektor berukuran dan matriks berukuran yang disebut sebagai matriks kendala, dengan . (Nash & Sofer 1996)
. (Winston 2004)
(2.1)
10
Sebagai catatan, yang dimaksud dengan vektor berukuran adalah vektor yang memiliki dimensi (ukuran) .
Vektor disebut solusi basis fisibel jika merupakan solusi basis dan . (Nash & Sofer 1996)
Solusi Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai teknik, salah satunya adalah metode simpleks. Metode ini dapat menghasilkan satu solusi optimum bagi masalah PL dan telah dikembangkan oleh Dantzig sejak tahun 1963. Dalam pengembangannya, metode ini merupakan metode yang paling umum digunakan untuk menyelesaikan PL. Metode ini berupa metode iteratif untuk menyelesaikan PL berbentuk standar. yang Pada masalah PL (2.1), vektor memenuhi kendala disebut solusi PL (2.1). Misalkan matriks dapat dinyatakan sebagai , dengan adalah matriks taksingular berukuran yang elemennya berupa koefisien variabel basis dan merupakan matriks berukuran yang elemen-elemennya berupa koefisien variabel nonbasis pada matriks kendala. Dalam hal ini matriks disebut matriks basis PL (2.1). dapat dinyatakan sebagai Misalkan
Ilustrasi solusi basis dan solusi basis fisibel diberikan pada Contoh 6.
vektor
, dengan
variabel basis dan nonbasis maka sebagai
adalah vektor
adalah vektor variabel dapat dinyatakan
.
(2.2)
adalah matriks taksingular Karena matriks maka memiliki invers, sehingga dari (2.2) dapat dinyatakan sebagai
.
(2.3)
Definisi 24 (Solusi Basis) Solusi dari suatu PL disebut solusi basis jika memenuhi syarat berikut: i. solusi tersebut memenuhi kendala pada PL, ii. kolom-kolom dari matriks kendala yang berpadanan dengan komponen taknol dari solusi tersebut adalah bebas linear. (Nash & Sofer 1996) Definisi 25 (Solusi Basis Fisibel)
Contoh 6 Misalkan diberikan PL (2.4) berikut: Min terhadap (2.4) , maka dari PL (2.4) diperoleh dan
.
Misalkan dipilih dan maka matriks basisnya adalah
,
Nilai vektor variabel nonbasis ditentukan dengan vektor nol sehingga . Dengan menggunakan matriks basis di atas diperoleh (2.5) Solusi (2.5) merupakan solusi basis karena memenuhi kendala pada PL (2.4) dan kolomkolom pada matriks kendala yang berpadanan dengan komponen taknol dari (2.5), yaitu , bebas linear (kolom yang satu bukan merupakan kelipatan dari kolom yang lain). Solusi (2.5) juga merupakan solusi basis fisibel karena nilai-nilai variabelnya lebih dari atau sama dengan nol. Hal yang juga penting dalam konsep pemrograman linear adalah daerah fisibel dan solusi optimum yang didefinisikan sebagai berikut. Definisi 26 (Daerah Fisibel) Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi semua kendala dan pembatasan tanda pada PL tersebut. (Winston 2004) Definisi 27 (Solusi Optimum)
11
Pada masalah maksimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terbesar. Pada masalah minimisasi, solusi optimum suatu PL adalah suatu titik dalam daerah fisibel dengan nilai fungsi objektif terkecil. (Winston 2004) 2.5 Dualitas Pemrograman Linear Menurut Nemhauser & Wolsey (1999), dualitas pemrograman linear (PL) berkaitan dengan sepasang masalah PL dan hubungan antarsolusi keduanya. Salah satu dari sepasang masalah PL ini disebut masalah primal dan lainnya disebut masalah dual. Masalah dual dan primal berkaitan erat sedemikian sehingga solusi optimal dari salah satu masalah akan secara otomatis menghasilkan solusi optimal bagi masalah lainnya. Masalah dual adalah sebuah masalah PL yang diturunkan dari sebuah masalah PL primal dengan mengikuti kaidah-kaidah berikut. 1. Untuk setiap kendala masalah primal terdapat suatu variabel masalah dual. 2. Untuk setiap variabel masalah primal terdapat suatu kendala masalah dual. 3. Koefisien dari sebuah variabel pada kendala masalah primal membentuk koefisien yang terdapat pada ruas kiri kendala masalah dual yang bersesuaian dan koefisien fungsi objektif dan variabel terkait menjadi ruas kanan kendala masalah dual. (Taha 1996) Secara ringkas, hubungan antara variabelvariabel kendala pada masalah primal dan masalah dual diberikan dalam tabel berikut. Tabel 1 Hubungan antara variabel keputusan dan kendala pada masalah primal dan masalah dual PRIMAL Minimisasi
Kendala
DUAL Maksimisasi
tandanya tidak dibatasi
Variabel
tandanya tidak dibatasi
Keterangan:
Berikut ini diberikan ilustrasi tentang dualitas dengan menggunakan Tabel 1. Contoh 7 Misalkan diberikan masalah primal sebagai berikut: Min terhadap
,
Kendala
takterbatas, dan
maka dual dari masalah primal di atas adalah Max terhadap
,
, dan
takterbatas
Pada kondisi optimal, solusi masalah dual dan masalah primal akan menghasilkan nilai fungsi objektif yang sama. Hal ini disebutkan dalam teorema berikut. Teorema 3 (Teorema Dualitas Kuat) Misalkan diberikan pemrograman linear primal dalam bentuk standar dan masalah dualnya. Jika salah satu dari masalah primal atau masalah dual tersebut memiliki solusi optimal maka masalah lainnya juga memiliki solusi optimal dan nilai fungsi objektif optimalnya adalah sama. (Nash & Sofer 1996) Bukti: dapat dilihat di Lampiran 2. Berikut ini diberikan ilustrasi Teorema 3. Contoh 8 Misalkan diberikan masalah primal sebagai berikut max terhadap
Variabel
dan menyatakan suatu bilangan
12
,
primal adalah sebagai berikut
Masalah dualnya adalah sebagai berikut min terhadap
dan nilai fungsi objektifnya adalah . (Lampiran 3a). Dengan menggunakan program LINDO 6.1 juga diperoleh solusi optimal dari masalah , dual sebagai berikut , , , , , , dan . dan nilai fungsi objektifnya adalah (Lampiran 3b).
tidak dibatasi Dengan menggunakan program LINDO 6.1 diperoleh solusi optimal dari masalah
III MODEL INPUT-OUTPUT Model input-output pertama kali diperkenalkan oleh Prof. W. Leontief pada tahun 1930-an. Prinsip dasar model ini adalah bagaimana cara menentukan agar setiap sektor dalam prosedur ekonomi tepat memproduksi sejumlah jenis barang untuk dapat memenuhi permintaan dari sektor-sektor lain dan sisanya untuk keperluan masyarakat (permintaanakhir). Klasifikasi sektor yang paling umum adalah klasifikasi ke dalam tiga sektor, yaitu primer, sekunder, dan, tersier. Kegiatan yang termasuk dalam sektor primer adalah kegiatan yang mengusahakan sumber daya alam, seperti sektor pertanian dalam arti luas (pertanian, perikanan, dan kehutanan), sektor pertambangan, dan sektor penggalian. Pada Tabel 2 Tabel input-output Ke Dari Industri Input primer Jumlah input
Industri
umumnya sektor sekunder adalah sektor industri sedangkan sektor tersier adalah sektor yang menghasilkan komoditas jasa (Nazara 2005). Model input-output Leontief ini didasarkan atas model keseimbangan umum (general menunjukkan equilibrium). Input-output bahwa di dalam perekonomian secara keseluruhan terjadi saling keterhubungan dan saling ketergantungan. Input suatu industri merupakan output industri lainnya, demikian sebaliknya. Dasar dari model ini adalah tabel IO yang menyajikan informasi tentang transaksi barang dan jasa selama periode waktu yang diberikan seperti pada Tabel 2.
Permintaan akhir
Jumlah output
(Olsen 1992) Keterangan: : Matriks berukuran yang elemennya berupa transaksi input-ouput sektor industri. : Matriks berukuran yang elemennya berupa transaksi input-output antara sektor industri dan sektor permintaan-akhir. : Matriks berukuran yang elemennya berupa transaksi input-output antara sektor inputprimer dan sektor industri. : Matriks berukuran yang elemennya berupa transaksi input-output antara sektor inputprimer dan sektor permintaan-akhir.
14
:
Vektor kolom dengan elemen baris ke- , yaitu , merupakan elemen baris ke- matriks dengan elemen-elemen baris ke. : Vektor kolom dengan elemen baris ke- , yaitu , merupakan elemen baris ke- matriks dengan elemen-elemen baris ke. : Vektor baris dengan elemen kolom ke- , yaitu , merupakan
penjumlahan elemenmatriks , dengan penjumlahan elemenmatriks , dengan penjumlahan elemen-
dengan elemen-elemen kolom ke- matriks , dengan elemen kolom ke- matriks . : Vektor baris dengan elemen kolom ke- , yaitu , merupakan penjumlahan elemendengan elemen-elemen kolom ke- matriks elemen kolom ke- matriks . Tanda aksen menyatakan transpos dari suatu vektor.
, dengan
Baris dan kolom pada Tabel 2 (kecuali kolom ke-3 dan baris ke-3) menyatakan suatu transaksi. Pada Tabel 2, transaksi pada sektor industri merupakan transaksi-antara, yaitu transaksi yang terjadi antara sektor yang berperan sebagai konsumen (dinyatakan dengan kolom) dan sektor yang berperan sebagai produsen (dinyatakan dengan baris). Isian sepanjang baris tabel IO, seperti pada Tabel 2, menunjukkan pengalokasian output yang dihasilkan oleh suatu sektor untuk memenuhi permintaan-antara dan permintaanakhir. Permintaan-antara adalah pengalokasian output suatu sektor dalam memenuhi kebutuhan input sektor-sektor lain untuk keperluan produksi. Permintaan-akhir adalah permintaan atas barang dan jasa untuk keperluan konsumsi.
Isian sepanjang kolom tabel IO, seperti pada Tabel 2, menunjukkan struktur input yang digunakan oleh masing-masing sektor dalam proses produksi baik berupa inputantara maupun input-primer. Input-antara merupakan input yang berasal dari sektor produksi dan digunakan dalam proses produksi lebih lanjut. Sebagai contoh, bahan bakar minyak, yang merupakan output sektor penyulingan minyak, merupakan input bagi sektor lainnya dan input bagi sektor transportasi. Dalam hal ini bahan bakar minyak adalah input-antara. Input-primer adalah balas jasa atas pemakaian faktor-faktor produksi yang terdiri atas tenaga kerja, tanah, dan modal. Pada umumnya tabel IO dapat disajikan dalam bentuk matriks berikut.
Tabel 3 Matriks gabungan input-output Ke Input Industri Dari primer
Permintaan akhir
Lingkungan
Jumlah output
Input primer Industri Permintaan akhir Lingkungan Jumlah input (Olsen 1992) Keterangan: : Vektor kolom yang merupakan transaksi input-output antara sektor permintaan-akhir dan sektor lingkungan. : Vektor kolom yang merupakan transaksi input-output antara sektor lingkungan dan sektor input-primer. : Vektor baris yang merupakan transaksi input-output antara sektor lingkungan dan sektor input-primer. : Vektor baris yang merupakan transaksi input-output antara sektor permintaan-akhir dan sektor lingkungan.
13
: Matriks yang elemennya berupa angka nol artinya tidak terjadi transaksi input-output. Tanda aksen menyatakan transpos dari suatu vektor.
Misalkan matriks didefinisikan sebagai submatriks dari matriks pada Tabel 3: ,
(3.1)
dalam bentuk persamaan (3.5a). Hal ini dapat dilihat pada pembuktian di bawah ini dengan memperhatikan Definisi 6 dan Definisi 7. Berdasakan ruas kanan pada persamaan (3.5a) diperoleh
misalkan vektor didefinisikan sebagai input bagi sistem IO dengan ,
(3.2)
didefinisikan sebagai dan misalkan vektor output dari sistem IO dengan ,
(3.3)
maka dapat didefinisikan matriks . Karena jumlah total input pada setiap transaksi di suatu sistem IO harus sama dengan jumlah total output pada setiap transaksi di sistem tersebut (Olsen 1992) maka jumlah kolom dan jumlah baris pada matriks gabungan input-output (Tabel 3) adalah sama. Pada sistem IO dikenal juga vektor throughput, yaitu vektor yang berisi semua jumlah total output sistem IO (input-primer, industri, dan permintaan-akhir) yang didefinisikan sebagai .
(3.4)
Dari persamaan (3.1)-(3.3), vektor throughput dapat dinyatakan dalam bentuk persamaan lain, yaitu ,
(3.5a)
merupakan vektor kolom berukuran yang banyaknya baris sesuai dengan banyaknya kolom matriks berukuran serta semua elemennya bernilai satu. Dari persamaan (3.1), (3.2), (3.4), dan (3.5a). Persamaan (3.4) dapat dinyatakan
dengan
, merupakan jumlah elemen-elemen dengan kolom matriks , merupakan jumlah , elemen-elemen kolom matriks merupakan jumlah elemen-elemen kolom matriks , merupakan jumlah elemenelemen kolom matriks Selain dapat dinyatakan dalam bentuk persamaan (3.5a), vektor throughput pada persamaan (3.4) dapat dinyatakan dalam bentuk persamaan lain, yaitu ,
(3.5b)
dengan merupakan vektor kolom berukuran yang banyaknya baris sesuai dengan banyaknya kolom matriks berukuran serta semua elemennya bernilai satu. Dari persamaan (3.1), (3.2), (3.4), dan (3.5b). Persamaan (3.4) dapat dinyatakan dalam bentuk persamaan (3.5b). Hal ini dapat dilihat pada pembuktian di bawah ini dengan memperhatikan Definisi 6 dan Definisi 7. Berdasarkan ruas kanan pada persamaan (3.5b) diperoleh
14
jumlah elemen-elemen baris matriks , merupakan jumlah elemen-elemen baris matriks . Berikut ini diberikan contoh mengenai matriks gabungan input-output beserta penggunaan persamaan (3.5).
, merupakan jumlah elemen-elemen dengan baris matriks , merupakan jumlah elemen-elemen baris matriks , merupakan Tabel 4 Contoh matriks gabungan input-output Ke Input Primer Industri
Permintaan Akhir
Lingkungan
Jumlah Output
Dari Input Primer Pendapatan Impor
0 0
0 0
80 0
60 100
0 0
0 0
0 0
140 100
Industri Pertanian Pengolahan
0 0
0 0
120 80
40 0
120 30
0 90
0 0
280 200
Permintaan Akhir Konsumsi Investasi
0 0
0 0
0 0
0 0
0 0
0 0
150 90
150 90
140 140
100 100
0 280
0 200
0 150
0 90
0 240
240
Lingkungan Jumlah Input
(Olsen 1992) Keterangan: : Sektor pendapatan. : Sektor impor. : Sektor industri pertanian (agriculture). : Sektor industri pengolahan (manufacturing). : Sektor konsumsi. : Sektor investasi. : Sektor lingkungan (environment).
Contoh 9 Dari Tabel 4 dapat diperoleh matriks
berukuran Karena matriks vektor yang tepat adalah
,
sehingga dan vektor
.
maka
15
: total input sektor , untuk . (Tarigan 2005) Sebagai ilustrasi koefisien input, berarti bahwa untuk memproduksi satu unit output sektor 3 dibutuhkan input senilai 32 unit yang berasal dari sektor 2. Dalam model kuantitas matriks koefisien input , (3.7) diasumsikan stabil dan bebas terhadap perubahan .
dengan
menjadi dasar Tabel input-output pembentukan tipe model input-output, yaitu model kuantitas dan model harga. 3.1 Model Kuantitas Model kuantitas merupakan salah satu tipe model input-output yang memperhatikan banyaknya barang dan jasa yang keluar (kuantitas output). Pada model kuantitas, ditentukan dari vektor vektor throughput eksogen . Beberapa asumsi yang digunakan pada model kuantitas adalah sebagai berikut. 1. Semua harga sama dengan satu. 2. Semua flow pada setiap transaksi adalah proporsional (sama rata).
pada Dalam kasus ini tanda bar persamaan (3.7) merupakan matriks dari pada koefisien input sedangkan simbol vektor berukuran mendefinisikan proses diagonalisasi vektor menjadi matriks diagonal yang berukuran . Proses diagonalisasi yang dimaksud adalah proses pada vektor pengubahan elemen kethroughput menjadi elemen diagonal utama pada matriks . Sebagai contoh: Jika vektor throughput didiagonalisasi, maka akan diperoleh matriks .
Berikut ini diberikan ilustrasi penggunaan persamaan (3.7). Contoh 10 Dari Tabel 4 diketahui matriks
Koefisien input merupakan koefisien yang menggambarkan jumlah input yang digunakan untuk memproduksi satu unit output sektor yang berasal dari sektor (Nazara 2005). Koefisien input dihitung dengan menggunakan rumus sebagai berikut , (3.6) dengan : koefisien input, untuk . : penggunaan input oleh sektor sektor
,
untuk .
dan vektor throughput
dan dari dan
maka
,
16
Untuk memudahkan menyelesaikan masalah yang terjadi dalam model kuantitas dibutuhkan rumus yang seterusnya akan digunakan dalam karya ilmiah ini. Pada awal pembahasan model kuantitas dikatakan bahwa vektor throughput ditentukan dari vektor eksogen sehingga persamaan yang digunakan adalah persamaan (3.5b) (karena ) dan persamaan (3.7). terdapat unsur Berdasarkan persamaan (3.7) diperoleh lalu disubstitusikan ke dalam persamaan (3.5b) sehingga diperoleh , .
(3.8a) (3.8b)
Dari persamaan (3.8b) dapat diperoleh sehingga diperoleh matriks koefisien input
, dengan adalah matriks identitas.
(3.9)
Dari persamaan (3.7) diperoleh matriks
. dengan matriks bukan matriks Selanjutnya diperoleh juga matriks Nilai 0.29 pada matriks (Contoh 10) memiliki arti bahwa untuk menghasilkan satu output bagi sektor pertanian diperlukan input sebesar 0.29 yang berasal dari sektor pendapatan. Selanjutnya matriks
akan
dibuktikan
bahwa
selalu memiliki invers berupa . Hal ini dapat dilihat dari setiap elemen vektor throughput
tidak bernilai nol dengan , , dan merupakan vektor-vektor kolom yang elemennya berupa total transaksi input-output antarsektor yang terjadi pada tabel IO. Karena berupa matriks diagonal maka matriks det . Berdasarkan Teorema 1 maka matriks memiliki invers.
nol.
dengan matriks bukan matriks identitas sehingga matriks merupakan matriks taksingular (determinan taknol). Berdasarkan persamaan (3.9) diperoleh persamaan yang akan digunakan untuk menyelesaikan masalah yang terjadi dalam model kuantitas, yaitu ,
(3.10)
dengan
(3.11) Bukti persamaan (3.11) dapat dilihat di Lampiran 4.
17
Selanjutnya akan diberikan ilustrasi perubahan kuantitas yang terjadi pada model kuantitas. Bila terjadi perubahan kuantitas salah satu sektor pada tabel IO maka akan memengaruhi kuantitas pada sektor yang lain. Hal ini dapat dilihat pada contoh berikut. Perhatikan Tabel 4. Misalkan terjadi kenaikan sebesar 10% pada transaksi input-output sektor investasi dari nilai 90 menjadi 99. Kenaikan tersebut menyebabkan perubahan pada vektor
menjadi
dengan merupakan vektor throughput harga yang didefinisikan sebagai , dengan
merupakan harga pada sektor merupakan harga pada sektor
input-primer, industri, dan
merupakan harga pada sektor
yang permintaan-akhir. Simbol digunakan pada persamaan (3.12) menyatakan sebuah matriks atau vektor yang diukur pada harga yang berlaku sekarang. Karena persamaan (3.5a) juga harus berlaku pada harga sekarang, maka
.
Dengan menggunakan persamaan (3.10) dan program Mathematica 7.0 terlihat terjadi perubahan pada vektor throughput dari
menjadi
menjadi vektor throughput
,
(3.14a) .
(Lampiran 5).
Berdasarkan hasil vektor throughput yang baru, terlihatlah terjadi perubahan di sektor lain ketika terjadi penambahan kuantitas pada salah satu sektor. Salah satu sektor yang berubah adalah sektor pendapatan (dari 140 menjadi 146.057) artinya penambahan kuantitas pada salah satu sektor akan memengaruhi kuantitas sektor lain. 3.2 Model Harga Model harga merupakan salah satu tipe model input-output yang memperhatikan harga input yang terjadi dalam tabel IO. Pada model harga, vektor throughput yang dilambangkan dengan (vektor harga untuk tiap unit output) ditentukan dari vektor eksogen (vektor harga pada sistem input). Beberapa asumsi yang digunakan pada model kuantitas digunakan juga pada model harga dengan asumsi tambahan yang diperlukan adalah setiap vektor harga bernilai satu pada level awal. Menurut Olsen (1992), matriks sistem pada harga sekarang diasumsikan sebagai ,
(3.13)
(3.12)
(3.14b)
Menurut Olsen (1992), dalam model harga, vektor throughput harga sekarang pada sistem IO dan vektor eksogen harga sekarang didefinisikan sebagai ,
(3.15)
dan , (3.16) dengan merupakan vektor eksogen harga pada sistem input. Untuk memudahkan menyelesaikan masalah yang terjadi dalam model harga dibutuhkan rumus yang seterusnya akan digunakan dalam karya ilmiah ini. Dari persamaan (3.14b) yang kedua diperoleh ruasnya dikalikan ,
(3.17)
lalu berdasarkan persamaan (3.15) maka persamaan (3.17) dapat dinyatakan dalam bentuk ,
(3.18)
dengan sehingga persamaan (3.18) dapat dinyatakan dalam bentuk berikut
18
,
(3.19)
berupa matriks taksingular. dengan Berdasarkan persamaan (3.19) diperoleh persamaan yang akan digunakan untuk menyelesaikan masalah yang terjadi dalam model harga adalah sebagai berikut .
(3.20)
Selanjutnya akan diberikan ilustrasi perubahan harga yang terjadi pada model harga. Bila terjadi perubahan harga salah satu sektor pada tabel IO maka akan memengaruhi harga pada sektor yang lain. Hal ini dapat dilihat pada contoh berikut. Perhatikan Tabel 4. Berdasarkan asumsi tambahan pada model harga, diperoleh vektor harga input pada level . Misalkan awal terjadi kenaikan harga pada sektor impor sehingga terjadi perubahan pada vektor menjadi eksogen , maka dengan menggunakan persamaan (3.20) dan program Mathematica 7.0 terlihat bahwa perubahan menghasilkan vektor pada vektor throughput
(Lampiran 6). Hal ini membuktikan bahwa perubahan harga pada salah sektor akan memengaruhi harga pada sektor lain. 3.3 Kombinasi Model Kuantitas dan Model Harga Kombinasi kedua model ini dapat dilihat dari persamaan (3.10) pada model kuantitas dan persamaan (3.20) pada model harga yang bila digabungkan menghasilkan persamaan berikut .
(3.21)
Bukti persamaan (3.21) dapat dilihat di Lampiran 7. Persamaan (3.21) menyatakan bahwa jumlah total output pada harga sekarang (ruas kiri) sama dengan jumlah total input pada harga sekarang (ruas kanan). Dalam kombinasi model harga dan kuantitas akan ditemui masalah dualitas antara harga dan kuantitas. Masalah dualitas yang
terjadi adalah masalah memaksimumkan kuantitas output yang dihasilkan atau meminimumkan biaya input yang terjadi pada transaksi model input-output. Solusi yang dihasilkan dari masalah dualitas yang terjadi pada model input-ouput dapat diinterpretasikan dari solusi masalah pemrograman linear. Adapun bentuk masalah pemrograman linear tersebut adalah sebagai berikut Minimumkan dengan kendala
(3.22)
Dalam persamaan (3.22) terlihat bahwa dapat dinyatakan dalam bentuk lain, yaitu karena dalam karya ilmiah ini sektor input primer dilambangkan dengan . Bentuk masalah pemrograman linear pada persamaan (3.22) menyatakan bagaimana meminimumkan harga input yang terjadi dalam transaksi input-output dengan kendala seluruh permintaan-akhir terpenuhi dan asumsi bahwa koefisien input konstan atau stabil terhadap perubahan vektor throughput . Untuk menyelesaikan persamaan (3.22), digunakan metode pengali Lagrange. Didefinisikan fungsi Lagrange ,
(3.23)
merupakan vektor pengali dengan Lagrange. Dalam kondisi optimum gradien fungsi Lagrange sama dengan nol, sehingga diperoleh ,
(3.24) ,
(3.25)
. Persamaan (3.24) dan (3.25) dengan yang diperoleh dengan menggunakan gradien fungsi Lagrange saat kondisi optimum ternyata merupakan bentuk rumus model kuantitas (persamaan (3.10)) dan model harga (persamaan (3.20)). Berikut ini diberikan ilustrasi mengenai penggunaan persamaan (3.24) dan persamaan (3.25). Contoh 11 Dari Tabel 4 diperoleh
19
vektor
dan
vektor Berdasarkan Contoh 10 diperoleh
. dan
. Dengan menggunakan program Mathematica 7.0 diperoleh
Berdasarkan hasil vektor throughput yang diperoleh dengan menggunakan metode pengali Lagrange dan program Mathematica 7.0, terlihatlah perbedaan yang tidak terlalu signifikan dengan nilai vektor throughput yang ada pada Tabel 4, yaitu . Hal ini menunjukkan bahwa vektor dapat diperkirakan hasilnya throughput dengan menggunakan rumus pada kombinasi antara model kuantitas dan model harga, khususnya rumus pada persamaan (3.24). Persamaan (3.25)
Dalam kondisi optimum, gradien fungsi Lagrange pada persamaan (3.25) sama dengan nol sehingga diperoleh
.
(3.27)
Persamaan (3.24) dengan Lagrange. Dalam kondisi optimum, gradien fungsi Lagrange pada persamaan (3.24) sama dengan nol sehingga diperoleh
,
merupakan vektor pengali
Kedua ruas persamaan (3.27) dikali dengan sehingga diperoleh matriks
(3.26) lalu kedua ruas pada persamaan (3.26) dikali sehingga diperoleh dengan matriks
Berdasarkan hasil vektor harga yang diperoleh dengan menggunakan metode pengali Lagrange dan program Mathematica 7.0, terlihatlah perbedaan yang tidak terlalu signifikan dengan nilai vektor harga yang diasumsikan bernilai 1 pada level awal, yaitu . Hal ini
20
menunjukkan bahwa vektor harga dapat diperkirakan hasilnya dengan menggunakan rumus pada kombinasi antara model kuantitas dan model harga, khususnya rumus pada persamaan (3.25). 3.4 Model Input-Output dalam Teori Network Model input-output merupakan kasus khusus dari konsep umum teori network flow yang secara luas digunakan dalam bidang riset operasi dan electrical network. Umumnya, teori network dapat dipandang sebagai bentuk aljabar matriks. Dalam karya ilmiah ini, konsep penting teori network diperkenalkan pada contoh matriks gabungan input-output (Tabel 4). Pada contoh tersebut, graf berarah memiliki sisi berarah dan simpul yang didefinisikan sebagai berikut 1. himpunan simpul merupakan sekumpulan simpul berupa sektor yang melakukan transaksi pada tabel IO, berada dalam 2. sisi berarah jika terjadi sekumpulan sisi berarah transaksi dari simpul ke simpul .
1,140
Gambar 11 Graf berarah dari Tabel 4. Setiap sisi berarah pada Gambar 11 terdapat dua buah bilangan yang menyatakan urutan sisi berarah dan banyaknya transaksi yang dilakukan. Misalnya, pada sisi berarah terjadi transaksi dari simpul menuju simpul sebesar 30 dengan urutan sisi berarah ke-10. Hal yang perlu diperhatikan adalah urutan simpul dan sisi berarah tak perlu sama tergantung tujuan tertentu asalkan tepat kegunaannya. Gambar 11 merupakan salah satu contoh graf berarah yang diperoleh dari Tabel 4. Graf berarah dapat dinyatakan dalam bentuk matriks dengan berbagai cara. Dalam hal ini Gambar 11 dapat dinyatakan dalam dua bentuk matriks Boole, yaitu matriks masukan dan matriks keluaran .
Kedua
matriks
tersebut
dengan menyatakan berukuran banyaknya simpul dan menyatakan banyaknya sisi berarah yang didefinisikan dalam bentuk berikut
tersebut Ilustrasi graf berarah dapat dilihat pada Gambar 11 berikut.
1, jika sisi berarah
meninggalkan
simpul
12,150
0, lainnya
(3.28)
dan C
I
9,120
10,30
4,120
1, jika sisi berarah
11,90 13,90
simpul
8,40
Ag
F 5,80
3,80
6,60 Pn
masuk ke
7,100 2,100 M
Pada Gambar 11 diperoleh
En
0, lainnya (3.29)
21
dan
Keseluruhan sisi berarah yang incident dengan semua simpul yang ada pada Gambar 11 baik sisi berarah yang masuk ke simpul maupun sisi berarah yang keluar dari simpul dapat direpresentasikan dalam bentuk matriks incidence. Dalam hal ini matriks incidence dinyatakan dalam bentuk berukuran berikut
Seluruh kolom yang ada pada matriks tersebut bila per kolom dijumlahkan akan menghasilkan nilai nol. Hal ini menunjukkan bahwa setiap sisi berarah hanya memiliki satu simpul awal dan satu simpul akhir dengan asumsi bahwa nilai -1 berarti simpul bertindak sebagai simpul akhir dan nilai 1 berarti simpul bertindak sebagai simpul awal (Olsen 1992). Sebagai contoh, pada kolom pertama baris pertama bernilai -1 berarti simpul sebagai simpul akhir dan kolom pertama baris tujuh bernilai 1 berarti simpul sebagai simpul awal. Bila keduanya dijumlahkan akan menghasilkan nilai nol berarti sisi berarah memiliki satu simpul awal dan
.
(3.30)
, Dari Gambar 11 diperoleh matriks matriks , dan persamaan (3.30). Pada kasus ini diperoleh matriks adalah sebagai berikut.
satu simpul akhir, yaitu sebagai simpul sebagai simpul awal. akhir dan Matriks , , dan merupakan matriks keluaran, matriks masukan, dan matriks incidence yang mengikutsertakan simpul dalam network tersebut. lingkungan Simpul-simpul yang ikut dalam network pada , , , , matriks incidence, antara lain , , dan, . Simpul lingkungan diperbolehkan tidak diikutsertakan tanpa mengurangi informasi yang ada. Bila simpul tidak dikutsertakan dalam lingkungan network maka matriks incidence yang memiliki bentuk dilambangkan dengan sebagai berikut
22
Secara umum, matriks dinyatakan dalam bentuk matriks sebagai berikut.
,
(3.31)
dengan subscript merupakan bagian dari simpul input (simpul input-primer, yaitu ), merupakan bagian dari simpulantara (simpul industri, yaitu ), dan merupakan bagian dari simpul output (simpul ). permintaan-akhir, yaitu Demikian halnya dengan matriks , matriks diperbolehkan tidak mengikutsertakan simpul lingkungan dalam network sehingga diperoleh matriks masukan yang dilambangkan dengan dengan bentuk sebagai berikut
Secara umum, matriks dalam bentuk berikut
,
dapat dinyatakan
(3.32)
dengan subscript merupakan bagian dari simpul-antara (simpul industri, yaitu ) dan merupakan bagian dari simpul output (simpul permintaan-akhir, yaitu ). Selanjutnya, diperoleh pula matriks keluaran tanpa simpul lingkungan dilambangkan dengan dengan bentuk sebagai berikut
Matriks , , , , , dan yang telah diperoleh menunjukkan bahwa setiap sektor yang bertindak sebagai simpul dan sisi berarah dalam graf berarah memiliki hubungan satu sama lain. Inilah yang menunjukkan bahwa teori network dapat
diterapkan dalam model input-output, yaitu setiap simpul yang berupa sektor-sektor terjadi saling keterhubungan dan ketergantungan. Tidak hanya itu saja, setiap sisi berarah yang memiliki bobot dapat didefinisikan dalam bentuk matriks bobot serta yang dilambangkan dengan didefinisikan sebagai , jika sisi berarah
berada
dalam himpunan sisi berarah E 0, lainnya
(3.33)
diasumsikan sebagai bobot di dengan setiap sisi berarah . Dalam hal ini bobot setiap sisi berarah dapat dilihat pada Gambar 11 ataupun Tabel 4. Sisi berarah yang memiliki bobot pada dinyatakan dalam Gambar 11, yaitu yang bentuk vektor bobot berukuran dilambangkan dengan . Telah dikatakan bahwa matriks merupakan matriks bobot yang elemennya berupa semua bobot atau transaksi yang terjadi di setiap sisi berarah yang ada. Matriks dapat dinyatakan dalam bentuk lain yang di dalamnya melibatkan matriks keluaran dan masukan serta vektor bobot. Hal ini menunjukkan bahwa terjadi transaksi dari sejumlah bobot tertentu sebesar simpul menuju simpul yang secara umum matriks direpresentasikan dalam bentuk .
(3.34)
Bila matriks menggunakan matriks keluaran dan masukan tanpa mengikutsertakan simpul lingkungan diperoleh matriks bobot yang memiliki arti yang sama dengan matriks seperti pada persamaan (3.1), yaitu keseluruhan transaksi input-output yang terjadi pada model inputoutput dan bentuknya sebagai berikut .
(3.35)
3.5 Model Input-Output dalam Network Flow Dalam teori graf, network flow merupakan sebuah graf berarah dengan sisi berarahnya
23
memiliki kapasitas dan flow. Jumlah flow yang ada pada sisi berarah tidak boleh melebihi kapasitas sisi berarah tersebut. Sisi berarah pada network digunakan untuk mewakili network dengan kemampuan mengangkut flow, misalnya cairan, komoditas, manusia, uang atau elektron-elektron. Secara tipe, flow pada network ditetapkan dengan tiga sisi berarah berbobot yang masing-masing merepresentasikan jumlah flow pada sisi berarah, kapasitas sisi berarah maksimal, dan biaya per unit yang melalui sisi berarah. Pada umumnya, flow sebenarnya adalah peubah sedangkan kapasitas dan biaya unit adalah tetap (konstanta). Suatu peubah flow harus memenuhi kondisi kekekalan simpul pada network, yaitu setiap flow yang masuk ke simpul harus sama dengan setiap flow yang keluar dari simpul. Pada kasus model input-output, misalkan merupakan vektor yang mewakili semua flow pada sisi berarah dalam graf berarah maka kondisi kekekalan simpul yang harus dipenuhi adalah sebagai berikut
.
lingkungan diperoleh graf berarah seperti Gambar 11 sebagai berikut. 3, 1,
4,
2, 6,
5,
Gambar 12 Graf berarah dari Tabel 3. Berdasarkan Gambar 12 diperoleh matriks masukan, matriks keluaran, dan vektor sirkulasi sebagai berikut
(3.36)
Pada persamaan (3.36) terlihat bahwa diikutsertakan dalam simpul lingkungan kondisi kekekalan simpul. Namun bila simpul tidak diikutsertakan akan lingkungan diperoleh kondisi kekekalan simpul yang menyerupai persamaan throughput yang telah diperoleh pada persamaan (3.4) sebagai berikut ,
(3.37)
disebut sebagai vektor sirkulasi
dengan ,
merupakan flow atau nilai
transaksi yang terjadi pada sistem input, merupakan flow atau nilai transaksi yang terjadi pada sistem industri, dan merupakan flow atau nilai transaksi yang terjadi pada sistem output. Persamaan (3.37) dapat dibuktikan melalui matriks masukan, matriks keluaran, dan vektor sirkulasi berikut ini. Dari Tabel 3, simpul sektor input-primer, misalkan simpul sektor industri, simpul sektor permintaan-akhir, dan simpul sektor
Berdasarkan ruas kiri pada persamaan (3.37) diperoleh
24
Berdasarkan ruas tengah pada persamaan (3.37) diperoleh
3.5.1 Dualitas Network Flow Masalah primal dan dual berkaitan erat sedemikian sehingga solusi optimal dari salah satu masalah akan secara otomatis menghasilkan solusi optimal bagi masalah lainnya. Dalam praktiknya, masalah yang sering ditemukan adalah menentukan flow pada network, meminimumkan beberapa pada model fungsi dalam vektor sirkulasi input-output (seperti topik dalam karya ilmiah ini), dan sebagainya. Masalah meminimumkan berkaitan dengan kemampuan manusia untuk meminimumkan biaya atau pemborosan, misalnya meminimumkan pemborosan energi. Pada karya ilmiah ini akan dibahas masalah dualitas yang ada, yaitu masalah primal berupa meminimumkan biaya satu unit yang dikenal yang melewati sisi berarah dengan vektor sirkulasi dan masalah dual berupa memaksimumkan kuantitas output. Adapun bentuk masalah primal pada karya ilmiah ini adalah sebagai berikut Minimumkan dengan kendala (3.38)
dengan koefisien pada fungsi objektif merupakan biaya satu unit yang melewati sisi
berarah . Masalah pemrograman linear pada persamaan (3.38) dikenal dengan masalah flow maksimal, yaitu mencari flow maksimal pada network dengan meminimumkan biaya satu unit yang melewati sisi berarah . Kendala pertama pada persamaan (3.38) dikenal sebagai kondisi kekekalan simpul yang menunjukkan kendala keseimbangan primal (kendala sistem). Dari sudut pandang matematis, pembatasan berarti vektor sirkulasi tidak dapat dipilih secara bebas dari ruang vektor tetapi harus dipilih dari ruang bagian berdimensi . Hal ini menunjukkan bahwa vektor sirkulasi berukuran dengan menyatakan banyaknya sisi berarah yang mengandung flow tidak sembarangan dipilih harus sesuai dengan banyaknya sisi berarah yang ada pada matriks incidence . Kendala kedua pada persamaan (3.38) disebut kendala elemen network yang menunjukkan bahwa sifat berbagai sisi berarah berhubungan dengan flow yang terjadi atau dapat dikatakan bahwa kendala ini merupakan tambahan kendala-kendala lainnya yang berhubungan dengan fungsi objektif. Berikut ini salah satu contoh masalah primal seperti pada persamaan (3.38). Contoh 12
Misalkan vektor
,
25
vektor
, dan
Masalah primal di atas memiliki solusi optimal sebagai berikut , , , , , , , , , , , , dan fungsi objektif sebesar 460000 dengan menggunakan program LINDO 6.1 (Lampiran 8). vektor
Masalah primal pada persamaan (3.38) memiliki masalah dual sebagai berikut. Maksimumkan dengan kendala (3.39)
Dari Gambar 11 diperoleh matriks incidence . Nilai-nilai yang ada dalam vektor pada Contoh 12 berupa biaya satu unit yang yang ditentukan melewati sisi berarah sembarang. Namun sebenarnya, nilai-nilai tersebut sesuai dengan biaya vektor perkiraan yang dikeluarkan perusahaan saat periode tertentu.
Masalah dual pada persamaan (3.39) memiliki dua variabel, yaitu variabel simpul network yang menunjukkan kendala keseimbangan primal dan variabel slack yang menunjukkan kendala lainnya seperti pada masalah primal (persamaan (3.38)) berupa . Berikut ini contoh masalah dual dari masalah primal (persamaan (3.38)).
Misalkan diberikan masalah primal sebagai berikut min
Contoh 13 max
dengan kendala
dengan kendala
26
matriks keluaran matriks koefisien persamaan (3.7).
tak terbatas
maka akan diperoleh input seperti pada .
Masalah dual di atas memiliki solusi optimal sebagai berikut , , , , , , , , , , , , , , , , , , , ,
dan fungsi objektif sebesar 460000 dengan menggunakan program LINDO 6.1 (Lampiran 9). 3.5.2 Input-Output dan Sirkulasi Biaya minimum Pada pembahasan sebelumnya telah ditunjukkan bahwa model IO memenuhi kondisi network flow yaitu flow yang keluar sama dengan flow yang masuk dan model IO dapat dinyatakan dalam masalah dualitas (seperti Pembahasan 3.5.1). Selanjutnya, akan dibuktikan bahwa masalah model input-output dapat dinyatakan dalam bentuk masalah pemrograman linear, yaitu sirkulasi biaya minimum. Hal inilah yang penting untuk menjawab tujuan karya ilmiah ini. Namun hal tersebut agak sulit dibuktikan. Untuk itu, sebagai persediaan dari sektor dibutuhkan ke sektor atau dengan kata lain persediaan dari baris ke kolom pada tabel IO sehingga diperoleh , dengan persediaan
(3.42)
Dari ruas kiri dan tengah persamaan (3.42) diperoleh
Berdasarkan persamaan (3.35), yaitu dan persamaan (3.7) diperoleh . Masalah pemrograman linear pada persamaan (3.22) dapat dinyatakan dalam bentuk masalah sirkulasi biaya minimum yaitu bentuk permasalahan yang memperhatikan masalah biaya yang melewati setiap sisi berarah secara keseluruhan dengan bentuk sebagai berikut Minimumkan dengan kendala (3.43)
Berikut ini diberikan contoh masalah sirkulasi biaya minimum seperti pada persamaan (3.43). Contoh 14
Misalkan vektor
(3.40)
merupakan koefisien input dan merupakan vektor
throughput penerimaan dari transaksi . Seperti pada pembahasan sebelumnya mengenai model input-output bahwa semua koefisien input dapat digabungkan dalam sebuah matriks koefsien input. Dalam hal ini matriks koefisien input dinyatakan dalam bentuk sebagai berikut .
(3.41)
Berdasarakan persamaan (3.41). Bila ruas kiri persamaan (3.41) dikalikan dengan
dan vektor
.
Berdasarkan Tabel 4 dan persamaan (3.41) diperoleh
27
,
.
Berdasarkan persamaan (3.43) diperoleh bentuk pemrograman linear sebagai berikut Min dengan kendala , dan
Jadi nilai fungsi objektifnya adalah 240. IV SIMPULAN DAN SARAN 4.1 Simpulan Model input-output merupakan salah satu contoh kasus khusus konsep umum teori graf, yaitu network dan network flow. Adapun dasar model input-output merupakan tabel IO yang menyajikan informasi tentang transaksi barang dan jasa yang terjadi antarsektor disajikan dalam bentuk matriks dengan jumlah input sama dengan jumlah output. Melalui teori network terbukti bahwa setiap sektor yang ada dalam bidang perekonomian memiliki peranan baik sebagai produsen maupun sebagai konsumen. Tidak hanya itu saja melalui teori network flow yang mengatakan bahwa flow masuk sama dengan flow keluar dapat membuktikan bahwa dalam model input-output jumlah input harus sama dengan jumlah output.
Permasalahan yang sering dialami pelaku ekonomi dalam melakukan transaksi inputoutput adalah meminimumkan biaya yang terjadi. Berdasarkan konsep network flow ditemukan formulasi yang memudahkan pelaku ekonomi untuk meminimumkan biaya tersebut. Formulasi itu dikenal dengan sirkulasi biaya minimum. Dalam formulasi tersebut, hal yang akan diminimumkan adalah harga input pada sektor model input-output dengan memperhatikan kendala yang harus terpenuhi yaitu flow masuk sama dengan flow keluar. 4.2 Saran Pada karya ilmiah ini telah dibahas mengenai model input-output merupakan salah satu contoh kasus permasalahan dalam network flow yaitu sirkulasi biaya minimum.
28
Penulis menyarankan untuk selanjutnya dilakukan pembahasan mengenai model inputoutput dalam electrical network yang lebih
modern dibandingkan dengan teori graf yang sudah cukup lama dikenal.
DAFTAR PUSTAKA Ahuja RK, TL Magnanti, JB Orlin. 1993. Network Flows: Theory Algorithms and Applications. New Jersey: Prentice Hall.
Nash SG, Sofer A. 1996. Linear and Nonlinear Programming. New York: McGraw-Hill.
Anton H, Rorres C. 2004. Aljabar Linear Elementer Versi Aplikasi. Indriasari R dan Harmein I, penerjemah. Jakarta: Erlangga. Terjemahan dari: Elementary Linear Algebra Applications Version.
Nazara S. 2005. Analisis Input-Output. Ed ke2. Jakarta: Lembaga Penerbit Fakultas Ekonomi Universitas Indonesia.
Balakrishnan VK. 1997. Schaum’s Outlines: Graph Theory. New York: McGraw-Hill. Bertsekas DP. 2003. Nonlinear Programming. Ed ke-2. USA: Athena Scientific. Bertsimas D, J Tsitsiklis. 1997. Introduction to Linear Optimization. Massachussets: Athena Scientific. Chartrand G, Oellermann OR. 1993. Applied and Algorithmic Graph Theory. New York: McGraw-Hill.
Nemhauser G, Wolsey L. 1999. Integer and Combinatorial Optimization. New York: John Wiley & Sons. Olsen JA. 1992. Input-output Models, Directed Graphs and Flows in Networks. Economic Modelling 9(4):365-384. Supranto J. 1992. Pengantar Matriks. Jakarta: Lembaga Penerbit Fakultas Ekonomi Universitas Indonesia. Stein F. 1967. Introduction to Matrices and Determinants. California: Wadsworth Publishing Company Inc.
Dantzig GB. 1963. Linear Programming and Extensions. New Jersey: Princeton University Press.
Taha HA. 1996. Pengantar Riset Operasi. D, penerjemah. Jakarta: Wirajaya Binarupa Aksara. Terjemahan dari: Operations Research.
Firdaus M, Sahara, Priyarsono DS. 2007. Ekonomi Regional. Jakarta: Universitas Terbuka.
Tarigan R. 2005. Ekonomi Regional: Teori dan Aplikasi. Ed Revisi. Jakarta: Bumi Aksara.
Foulds LR. 1992. Graph Theory Applications. New York: Springer-Verlag.
Theil H. 1971. Applied Economic Forecasting Volume 4. New York: American Elsevier Publishing Company.
Harshbarger R. 1985. Mathematical Applications for Management, Life, and Social Sciences. Ed ke-2. New York: D.C.Heath and company. Leon S. 2001. Aljabar Linear dan Aplikasinya. Ed ke-5. Bondan A, Jakarta: Erlangga. penerjemah. Terjemahan dari: Linear Algebra with Applications. Fifth Edition.
Thirlwall A. 1983. Growth and Development with Special Reference to Developing Economies. Ed ke-3. London: Macmillan Education LTD. Thulasiraman K, Swamy MNS. 1992. Graphs: Theory and Algorithms. New York: John Wiley and Sons.
29
Winston WL. 2004. Operations Research: Applications and Algorithms. Ed ke-4. New York: Duxbury. Zhang F. 1999. Matrix Theory: Basic Results and Techniques. New York: SpringerVerlag.
30
LAMPIRAN
31
Lampiran 1 Pembuktian Teorema 1 beserta Beberapa Teorema yang Mendukung Pembuktian Tersebut Teorema 1 (Matriks Invers dan Determinan) Matriks dapat dibalik atau memiliki invers
jika dan hanya jika det
.
Sebelum membuktikan Teorema 1, terlebih dulu diperkenalkan teorema-teorema lainnya yang mendukung pembuktian. Teorema 4 (Matriks Identitas) maka terdapat dua kemungkinan, Jika adalah bentuk eselon baris tereduksi dari matriks yaitu memiliki satu baris bilangan nol atau merupakan matriks identitas . (Anton & Rorres 2004) Bukti: lihat Anton & Rorres 2004 Teorema 5 (Sifat-Sifat Determinan) Jika adalah matriks berukuran det det det
dan
adalah matriks elementer berukuran
maka
(Anton & Rorres 2004) Bukti: lihat Anton & Rorres 2004. Teorema 6 (Pernyataan-Pernyataan yang Ekuivalen) Jika maka pernyataan-pernyataan berikut adalah ekuivalen. dapat dibalik; a) hanya memiliki solusi trivial; b) c) Bentuk eselon baris tereduksi dari adalah ; d) dapat dinyatakan sebagai hasil kali dari matriks-matriks elementer; selalu mempunyai solusi untuk setiap matriks ; e) f) memiliki tepat satu solusi untuk setiap matriks . (Anton & Rorres 2004) Bukti: lihat Anton & Rorres 2004 Teorema 7 (Determinan Matriks Elementer) Misalkan adalah suatu matriks elementer berukuran a) Jika adalah hasil perkalian suatu baris dari dengan b) Jika adalah hasil pertukaran dua baris dari maka det c) Jika adalah hasil penjumlahan kelipatan satu baris dari Bukti: lihat Anton & Rorres 2004 Ilustrasi Determinan Matriks Elementer
a.
b.
. maka det ; ; ke baris lainnya maka det . (Anton & Rorres 2004)
32
c.
Bukti Teorema 1: Misalkan adalah bentuk eselon baris tereduksi dari matriks . Langkah awal yang dilakukan dan det keduanya adalah nol atau taknol. Misalkan adalah menunjukkan bahwa det adalah matriks-matriks elementer yang bersesuaian dengan operasi baris elementer yang menghasilkan dari maka diperoleh Menurut Teorema 5 diperoleh det det det Tetapi menurut Teorema 7 determinan matriks elementer semuanya taknol sehingga terbukti dan det keduanya nol atau taknol. Selanjutnya, Teorema 1 akan dibuktikan. bahwa det sehingga det dan Jika matriks dapat dibalik maka menurut Teorema 6 diperoleh . Sebaliknya, jika det maka det sehingga sebagai konsekuensinya det tidak dapat memiliki satu baris bilangan nol. Menurut Teorema 4 bahwa maka matriks dapat dibalik sesuai dengan Teorema 6. det
Lampiran 2 Pembuktian Teorema 3 beserta Teorema yang Mendukung Pembuktian Tersebut Teorema 3 (Teorema Dualitas Kuat) Misalkan diberikan pemrograman linear primal dalam bentuk standar dan masalah dualnya. Jika salah satu dari masalah primal atau masalah dual tersebut memiliki solusi optimal maka masalah lainnya juga memiliki solusi optimal dan nilai fungsi objektif optimalnya adalah sama. Sebelum membuktikan Teorema 3, terlebih dulu diperkenalkan teorema yang mendukung pembuktian. Teorema 8 (Teorema Dualitas Lemah) Misalkan diberikan pemrograman linear primal dalam bentuk standar dan masalah dualnya. Misalkan adalah solusi fisibel untuk masalah primal dan misalkan adalah solusi fisibel untuk masalah dual maka nilai fungsi objektif dari masalah primal selalu lebih besar atau sama dengan nilai fungsi objektif masalah dual. (Nash & Sofer 1996) Bukti: lihat Nash & Sofer 1996. Akibat dari Teorema 8 adalah sebagai berikut. Akibat 1 (Akibat Teorema Dualitas Lemah) Jika adalah solusi fisibel untuk masalah primal dalam bentuk standar, adalah solusi fisibel maka adalah solusi optimal untuk masalah primal dan untuk masalah dual, dan adalah solusi optimal untuk masalah dual. (Nash & Sofer 1996) Bukti Teorema 3: Untuk membuktikan Teorema 3 diperlukan Akibat 1 dan misalkan kasus PL primalnya berupa masalah maksimisasi. Misalkan diasumsikan masalah primal dalam bentuk standar dan mempunyai solusi yang merupakan solusi basis fisibel optimal dan vektor variabel basis dan
dinyatakan sebagai
, dengan
adalah vektor variabel nonbasis. Misalkan juga matriks
adalah dinyatakan
33
sebagai
dan vektor koefisien pada fungsi objektif
dinyatakan sebagai
.
Karena matriks adalah matriks taksingular maka matriks memiliki invers, sehingga dapat . dinyatakan sebagai Jika merupakan solusi optimal untuk PL maka biaya tereduksinya adalah atau (*) adalah vektor pengali simpleks yang berhubungan dengan solusi basis fisibel, Misalkan atau . Akan dibuktikan bahwa: dengan 1. nilai fungsi objektif masalah primal sama dengan nilai fungsi objektif masalah dual , adalah solusi optimal untuk masalah dual. 2. Bukti: 1. Untuk membuktikan nilai fungsi objektif masalah primal sama dengan nilai fungsi objekti dual, terlebih dahulu akan diperiksa kefisibelan dari :
sehingga dan untuk masalah primal
fisibel untuk masalah dual. Selanjutnya dihitung nilai fungsi objektif dan masalah dual adalah sebagai berikut
Jadi fisibel untuk masalah dual dan nilai fungsi objektif solusi ptimal dari masalah primal dan masalah dual mempunyai nilai yang sama. 2. Untuk membuktikan adalah solusi optimal untuk masalah dual diperlukan Akibat 1. Karena maka adalah solusi optimal untuk masalah dual.
Lampiran 3 Syntax Program LINDO 6.1 untuk Menyelesaikan Contoh 8 beserta Hasil yang Diperoleh Lampiran 3a Syntax program LINDO 6.1 pada Contoh 8 untuk masalah primalnya max 61x1+32x2+23x3+49x4+56x5 subject to x1+x2+x3=1 x1+x3+x4=1 x1+x4=1 x2+x3+x5=1 x2+x5=1 x1>=0 x2>=0 x3>=0 x4>=0 x5>=0 end
Hasil yang diperoleh LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) 117.0000 VARIABLE X1 X2 X3 X4 X5 ROW 2) 3) 4) 5) 6)
VALUE 1.000000 0.000000 0.000000 0.000000 1.000000
2
REDUCED COST 0.000000 24.000000 0.000000 12.000000 0.000000
SLACK OR PLUS DUAL PRICES 0.000000 0.000000 0.000000 0.000000 0.000000 61.000000 0.000000 23.000000 0.000000 33.000000
34
7) 8) 9) 10) 11)
1.000000 0.000000 0.000000 0.000000 1.000000
NO. ITERATIONS=
0.000000 0.000000 0.000000 0.000000 0.000000 2
Lampiran 3b Syntax program LINDO 6.1 pada Contoh 8 yang berupa masalah dualnya min y1'+y1"+y2'+y2"+y3'+y3"+y4'+y4"+y5'+y5" subject to y1'+y1"+y2'+y2"+y3'+y3"-s1=61 y1'+y1"+y4'+y4"+y5'+y5"-s2=32 y1'+y1"+y2'+y2"+y4'+y4"-s3=23 y2'+y2"+y3'+y3"-s4=49 y4'+y4"+y5'+y5"-s5=56 end Hasil yang diperoleh LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) 117.0000
5
VARIABLE VALUE REDUCED COST Y1' 12.000000 0.000000 Y1" 0.000000 0.000000 Y2' 0.000000 0.000000 Y2" 0.000000 0.000000 Y3' 0.000000 0.000000 Y3" 49.000000 0.000000 Y4' 0.000000 0.000000 Y4" 11.000000 0.000000 Y5' 0.000000 0.000000 Y5" 45.000000 0.000000 S1 0.000000 1.000000 S2 36.000000 0.000000 S3 0.000000 0.000000 S4 0.000000 0.000000 S5 0.000000 1.000000 Y3 0.000000 15.000000 ROW 2) 3) 4) 5) 6)
SLACK OR PLUS DUAL PRICES 0.000000 -1.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 -1.000000
NO. ITERATIONS=
5
Lampiran 4
Pembuktian Persamaan (3.11) dipartisi menjadi matriks
Misalkan matriks dengan
,
,
,
serta ,
, , dan
matriks partisi segi (banyaknya baris dan kolom sama). Misalnya
Jadi,
maka dari Teorema 2,
dengan
merupakan
35
Selanjutnya, akan ditentukan invers dari matriks ialah
. Menurut Teorema 2, invers matriks
dengan
Jadi,
Lampiran 5 Syntax Program Mathematica 7.0 untuk Menyelesaikan Masalah Perubahan Vektor throughput pada Model Kuantitas beserta Hasil yang Diperoleh i=(\[NoBreak]{ {1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1} }\[NoBreak]); Ttopi=(\[NoBreak]{ {0, 0, 0.29, 0.3, 0, 0}, {0, 0, 0, 0.5, 0, 0}, {0, 0, 0.43, 0.2, 0.8, 0}, {0, 0, 0.29, 0, 0.2, 1}, {0, 0, 0, 0, 0, 0},
{0, 0, 0, 0, 0, 0} }\[NoBreak]); S=i-Ttopi; P= Inverse[S]; tu=(\[NoBreak]{ {0}, {0}, {0}, {0}, {150}, {99} }\[NoBreak]); t=P.tu//MatrixForm (\[NoBreak]{
36
{146.057}, {105.791}, {284.766}, {211.582},
{150.}, {99.} }\[NoBreak])
Lampiran 6 Syntax Program Mathematica 7.0 untuk Menyelesaikan Masalah Perubahan Vektor throughput pada Model Harga beserta Hasil yang Diperoleh i=(\[NoBreak]{ {1, 0, 0, 0, 0, 0}, {0, 1, 0, 0, 0, 0}, {0, 0, 1, 0, 0, 0}, {0, 0, 0, 1, 0, 0}, {0, 0, 0, 0, 1, 0}, {0, 0, 0, 0, 0, 1} }\[NoBreak]); Ttopi=(\[NoBreak]{ {0, 0, 0.29, 0.3, 0, 0}, {0, 0, 0, 0.5, 0, 0}, {0, 0, 0.43, 0.2, 0.8, 0},
{0, 0, 0.29, 0, 0.2, 1}, {0, 0, 0, 0, 0, 0}, {0, 0, 0, 0, 0, 0} }\[NoBreak]); S=i-Ttopi; P= Inverse[S]; pi=(\[NoBreak]{ {1, 1.1, 0, 0, 0, 0} }\[NoBreak]); p=pi.P {{1.,1.1,1.04785,1.05957,1.0502,1.05957}}
Lampiran 7 Pembuktian Persamaan (3.21) beserta Beberapa Persamaan yang Terkait dengan Pembuktian Tersebut Beberapa persamaan yang terkait dengan pembuktian adalah sebagai berikut 1. Persamaan (3.10) 2. Persamaan (3.20) . Terlebih dulu kalikan kedua ruas persamaan (3.20) dengan sehingga
Kedua ruas dikali dengan matriks
sehingga diperoleh
Lampiran 8 Syntax Program LINDO 6.1 untuk Menyelesaikan Masalah Primal pada Contoh 12 beserta Hasil yang Diperoleh Syntax program LINDO 6.1 pada Contoh 12 min 200q1 + 400q2 + 600q3 + 800q4 + 100q5 + 120q6 + 140q7 + 160q8 + 180q9 + 200q10 + 220q11 + 240q12 + 260q13 subject to -q1 + q3 + q6 = 0
-q2 + q7 = 0 -q3 - q5 + q8 + q9 = 0 q5 - q6 - q7 - q8 + q10 + q11 = 0 -q9 - q10 + q12 = 0 -q11 + q13 = 0 q1 >= 150 q2 >= 120
37
q3 >= 100 q4 >= 150 q5 >= 100 q6 >= 80 q7 >= 120 q8 >= 60 q9 >= 150 q10 >= 50 q11 >= 120 q12 >= 170 q13 >= 120 end Hasil yang diperoleh: LP OPTIMUM FOUND AT STEP OBJECTIVE FUNCTION VALUE 1) 460000.0
Q10 Q11 Q12 Q13
16
VARIABLE VALUE REDUCED COST Q1 200.000000 0.000000 Q2 120.000000 0.000000 Q3 100.000000 0.000000 Q4 150.000000 0.000000 Q5 110.000000 0.000000 Q6 100.000000 0.000000 Q7 120.000000 0.000000 Q8 60.000000 0.000000 Q9 150.000000 0.000000
ROW 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14) 15) 16) 17) 18) 19) 20)
50.000000 120.000000 200.000000 120.000000
0.000000 0.000000 0.000000 0.000000
SLACK OR PLUS DUAL PRICES 0.000000 200.000000 0.000000 400.000000 0.000000 420.000000 0.000000 320.000000 0.000000 -240.000000 0.000000 540.000000 50.000000 0.000000 0.000000 0.000000 0.000000 -380.000000 0.000000 -800.000000 10.000000 0.000000 20.000000 0.000000 0.000000 -220.000000 0.000000 -260.000000 0.000000 -840.000000 0.000000 -760.000000 0.000000 0.000000 30.000000 0.000000 0.000000 -800.000000
NO. ITERATIONS=
16
Lampiran 9 Syntax Program LINDO 6.1 untuk menyelesaikan Masalah Dual pada Contoh 13 Beserta Hasil yang Diperoleh Syntax program LINDO 6.1 pada Contoh 13 max 150a7 + 120a8 + 100a9 + 150a10 + 100a11 + 80a12 + 120a13 + 60a14 + 150a15 + 50a16 + 120a17 + 170a18 + 120a19 subject to -a1' + a1" + a7 + s1 = 200 -a2' + a2" + a8 + s2 = 400 a1' - a1" - a3' + a3" + a9 + s3 = 600 a10 + s4 = 800 -a3' + a3" + a4' - a4" + a11 + s5 = 100 a1'- a1" - a4' + a4" + a12 + s6 = 120 a2' - a2" - a4' + a4" + a13 + s7 = 140 a3' - a3" - a4' + a4" + a14 + s8 = 160 a3' - a3" - a5' + a5" + a15 + s9 = 180 a4' - a4" - a5' + a5" + a16 + s10 = 200 a4' - a4" - a6' + a6" + a17 + s11 = 220 a5' - a5" + a18 + s12 = 240 a6' - a6" + a19 + s13 = 260 end Hasil yang diperoleh LP OPTIMUM FOUND AT STEP
0
OBJECTIVE FUNCTION VALUE 1) 460000.0 VARIABLE VALUE REDUCED COST A7 0.000000 50.000000 A8 220.000000 0.000000 A9 380.000000 0.000000 A10 800.000000 0.000000 A11 0.000000 10.000000 A12 0.000000 20.000000 A13 0.000000 0.000000 A14 260.000000 0.000000 A15 840.000000 0.000000 A16 760.000000 0.000000 A17 540.000000 0.000000 A18 0.000000 30.000000 A19 260.000000 0.000000 A1' 0.000000 0.000000 A1" 200.000000 0.000000 S1 0.000000 200.000000 A2' 0.000000 0.000000 A2" 180.000000 0.000000 S2 0.000000 120.000000
38
A3' A3" S3 S4 A4' A4" S5 S6 S7 S8 A5' A5" S9 S10 A6' A6" S11 S12 S13 ROW 2) 3) 4) 5) 6) 7) 8) 9) 10) 11) 12) 13) 14)
0.000000 420.000000 0.000000 0.000000 0.000000 320.000000 0.000000 0.000000 0.000000 0.000000 240.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
0.000000 0.000000 100.000000 150.000000 0.000000 0.000000 110.000000 100.000000 120.000000 60.000000 0.000000 0.000000 150.000000 50.000000 0.000000 0.000000 120.000000 200.000000 120.000000
SLACK OR PLUS DUAL PRICES 0.000000 200.000000 0.000000 120.000000 0.000000 100.000000 0.000000 150.000000 0.000000 110.000000 0.000000 100.000000 0.000000 120.000000 0.000000 60.000000 0.000000 150.000000 0.000000 50.000000 0.000000 120.000000 0.000000 200.000000 0.000000 120.000000
NO. ITERATIONS=
0
