PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
METODE KARMARKAR UNTUK MENYELESAIKAN MASALAH PROGRAM LINEAR
SKRIPSI
Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika
Oleh: Yohana Buragoran NIM: 09 3114 001
PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS SAINS DAN TEKNOLOGI UNIVERSITAS SANATA DHARMA YOGYAKARTA 2013
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
KARMARKAR METODE TO SOLVE THE PROBLEM LINEAR PROGRAM
THESIS
Presented As a Partial Fulfillment of the Requirements to Obtain The Sarjana Sains Degree In Mathematics
by: Yohana Buragoran Student Number: 09 3114 001
MATHEMATICS STUDY PROGRAM DEPARTMENT OF MATHEMATICS FACULTY OF SCIENCE AND TECHNOLOGY SANATA DHARMA UNIVERSITY YOGYAKARTA 2013
i
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
iii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
HALAMAN PERSEMBAHAN
Matius 21:22 “Dan apa saja yang kamu minta dalam doa dengan penuh kepercayaan, kamu akan menerimanya.”
Dengan penuh cinta karya ini ku persembahkan untuk: Bapak-Ibuku, Yakobus Bedatuan-Ariadne Trisnani Ketiga adikku, Imelda, Elis dan Valensia Kekasihku Benediktus Eki Prabowo
Terimakasih……….. Telah mendorongku untuk mempertahankan mimpi-mimpiku Menunjukkan padaku untuk tidak terpengaruh oleh rintangan Menghapuskan air mataku kala aku sedih Mengubah kebingunganku menjadi senyuman Mengubah keputus asaanku menjadi harapan
Terimakasih karena kalian memberikan semangat dan keceriaan untukku
iv
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
PERNYATAAN KEASLIAN KARYA
Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini tidak memuat karya atau bagian karya orang lain, kecuali yang telah disebutkan dalam kutipan dan daftar pustaka, sebagaimana layaknya karya ilmiah.
Yogyakarta,17 Oktober 2013
v
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ABSTRAK
Masalah dalam program linear adalah mengoptimumkan suatu fungsi linear yang terbatas oleh kendala-kendala berupa persamaan atau pertidaksamaan linear. Salah satu metode untuk menyelesaikan masalah dalam program linear, adalah metode Karmarkar yang merupakan salah satu kelas dari metode titikinterior. Untuk menyelesaikan masalah program linear dengan menggunakan metode Karmarkar, suatu masalah program linear dalam bentuk standar harus diubah dahulu ke dalam bentuk kanonik Karmarkar dengan menggunakan transformasi proyektif. Ide dasar metode Karmarkar, dimulai dengan memilih titik-interior awal di dalam ruang penyelesaian. Gradien fungsi tujuan di titik-interior awal adalah arah yang membuat fungsi tujuan meningkat dengan cepat. Jika satu titik sembarang ditempatkan di sepanjang gradien itu kemudian memproyeksikannya secara tegak lurus terhadap ruang penyelesaian, maka hasil transformasi titik-interior yang dipilih diposisikan lebih dekat dengan titik optimum. Hasil transformasi titikinterior yang dipilih dijalankan ke suatu titik-interior lain dengan arah layak dan besar langkah yang sesuai. Proses iterasi ini diulang hingga nilai fungsi sasaran sama dengan nol.
vi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ABSTRACT
The problem in linear programming is finding points that optimizing a linear function with linear constrained, in form of equalities or inequalities. One method to solve linear programming problems is the Karmakar method, which is one of a class of interior-point method. Using Karmakar method, a linear programming problem in standard form must be converted first into a canonical form using Karmarkar projective transformation. The basic idea of Karmarkar method, starts with choosing an interior-point early in the feasible space. Gradient of the objective function at the initial interior point is the direction that makes the objective function is increasing rapidly. If one is placed at an arbitrary point along the gradient, and then project it perpendicularly to a feasible space, then the result of the transformation of selected interior points positioned closer to the optimum point. The results of transformation chosen run to another interior with an appropriate direction and length of step. This iterative process is repeated until the objective function value equal to zero.
vii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
LEMBAR PERNYATAAN PERSETUJUAN PUBLIKASI KARYA ILMIAH UNTUK KEPERLUAN AKADEMIS Yang bertanda tangan di bawah ini, saya mahasiswa Universitas Sanata Dharma: Nama
: Yohana Buragoran
Nomor Mahasiswa : 09 3114 001 Demi mengembangkan ilmu pengetahuan, saya memberikan kepada perpustakaan Universitas Sanata Dharma karya ilmiah saya yang berjudul: “METODE KARMARKAR UNTUK MENYELESAIKAN MASALAH PROGRAM LINEAR” Beserta perangkat yang diperlukan. Dengan demikian saya memberikan kepada Perpustakaan Universitas Sanata Dharma hak untuk menyimpan, mengalihkan dalam bentuk media lain, mengelolanya dalam bentuk pangkalan data, mendistribusikan secara terbatas, dan mempublikasikannya di Internet atau media lain untuk kepentingan akademis tanpa perlu meminta izin dari saya maupun memberikan royalti kepada saya selama tetap mencantumkan nama saya sebagai penulis. Demikian pernyataan ini saya buat dengan sebenarnya. Yogyakarta, 17 Oktober 2013
viii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
KATA PENGANTAR Puji syukur penulis panjatkan kepada Tuhan Yesus Kristus atas segala kasih dan perlindungan-Nya sehingga penulisan skripsi ini dapat terselesaikan. Skripsi ini disusun dalam rangka melengkapi salah satu syarat untuk memperoleh gelar Sarjana Sains pada Program Studi Matematika, Fakultas Sains dan Teknologi, Universitas Sanata Dharma Yogyakarta. Penulisan skripsi ini tidak lepas dari bantuan dan dukungan dari berbagai pihak. Oleh karena itu, pada kesempatan ini penulis ingin menyampaikan ucapan terima kasih kepada: 1. Tuhan Yesus Kristus yang telah menyertai, membimbing dan menuntun penulis dalam menyelesaikan tugas akhir ini sehingga tugas akhir ini dapat selesai dengan baik. 2. Ibu Lusia Krismiyati, S.Si, M.Si sebagai dosen pembimbing akademik dan dosen pembimbing skripsi yang penuh perhatian dan kesabaran telah membimbing serta memberi saran dan kritik kepada penulis selama proses penulisan skripsi ini. 3. Ibu Any Herawati, S.Si, M.Si selaku dosen penguji yang telah memberikan saran dan kritik dalam skripsi ini. 4. Bapak Y.G.Hartono, S.Si, M.Sc, Ph.D selaku dosen penguji yang telah memberikan saran dan kritik dalam skripsi ini. 5. Bapak dan Ibu dosen di Program Studi Matematika yang telah membimbing dan mendidik penulis selama menuntut ilmu di Universitas Sanata Dharma
ix
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
sehingga penulis mendapatkan ilmu yang berguna untuk menyelesaikan tugas akhir ini. 6. Bapak dan Ibu karyawan Universitas Sanata Dharma, khususnya sekretariat Fakultas Sains dan Teknologi, dan perpustakaan Universitas Sanata Dharma atas segala bantuan dan fasilitas yang telah diberikan. 7. Keluargaku, Bapak Yakobus Bedatuan, Ibu Ariadne Trisnani, adik-adikku Imelda Memen Tokan, Elisabeth Hala Tokan, Valensia Ina Tokan, dan Kekasihku Benediktus Eki Prabowo yang selalu memberi dukungan, semangat dan mendoakan penulis. 8. Sahabat-sahabatku Mbak Ratih, Herta, Metri, Rina, Sefi, Lia, Berta, Ita, Nita, Ana, dan teman-teman kos yang telah memberikan dukungan, semangat, dan mendoakan penulis. 9. Temen-temen seperjuangan Yohanes Dimas, Faida, Rossi, Etik, Erlika, Dwi, Dimas, Sekar yang telah membantu dan mendukung penulis. 10. Semua pihak yang telah membantu penulis baik secara langsung maupun tidak langsung hingga selesainya penulisan skripsi ini. Penulis menyadari bahwa skripsi ini masih banyak kekurangannya. Oleh karena itu, penulis mengucapkan terima kasih bila ada kritik dan saran yang dapat membangun penulis. Penulis berharap semoga skripsi ini dapat bermanfaat dan menjadi referensi bagi pembaca. Yogyakarta,....Oktober 2013
Penulis
x
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR ISI
Halaman HALAMAN JUDUL ............................................................................................ i HALAMAN PERSETUJUAN PEMBIMBING ................................................... ii HALAMAN PENGESAHAN ............................................................................... iii HALAMAN PERSEMBAHAN ........................................................................... iv PERNYATAAN KEASLIAN KARYA ............................................................... v ABSTRAK ............................................................................................................ vi ABSTRACT .......................................................................................................... vii LEMBAR PERNYATAAN PERSETUJUAN ................................................... viii KATA PENGANTAR .......................................................................................... ix DAFTAR ISI ......................................................................................................... xi DAFTAR GAMBAR .......................................................................................... xiv BAB I PENDAHULUAN ................................................................................... 1 A. Latar Belakang .................................................................................. 1 B. Rumusan Masalah ............................................................................. 2 C. Tujuan Penulisan .............................................................................. 3
xi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
D. Batasan Masalah ............................................................................... 3 E. Manfaat Penulisan ............................................................................ 3 F. Metode Penulisan ............................................................................. 4 G. Sistematika Penulisan ....................................................................... 4 BAB II OPTIMISASI UNTUK PERSOALAN LINEAR ................................... 6 A. Matriks dan Sistem Persamaan Linear ............................................. 6 B. Ruang Vektor .................................................................................... 13 C. Masalah Program Linear .................................................................. 53 BAB III METODE KARMARKAR .................................................................... 60 A. Bentuk Kanonik Karmarkar .............................................................. 63 B. Asumsi-Asumsi dalam Masalah Karmarkar ..................................... 64 C. Transformasi Proyeksi ...................................................................... 64 D. Mengubah Masalah Program Linear Bentuk Umum ke Bentuk Kanonik Karmarkar .......................................................................... 82 E. Algoritma Karmarkar ........................................................................ 98 F. Aplikasi Metode Karmarkar dalam menyelesaikan masalah Program Linear ............................................................................................... 124 BAB IV KESIMPULAN .................................................................................... 128 A. Kesimpulan ...................................................................................... 128 B. Saran ................................................................................................ 129
xii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR PUSTAKA ......................................................................................... 130 LAMPIRAN ........................................................................................................ 131
xiii
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
DAFTAR GAMBAR
Halaman Gambar 2.1 –
....................................................................................... 44
Gambar 3.1 Ilustrasi algoritma Karmarkar ........................................................... 61
xiv
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB I PENDAHULUAN
A. Latar Belakang Masalah dalam program linear adalah mengoptimumkan suatu fungsi linear yang terbatas oleh kendala-kendala berupa persamaan dan pertidaksamaan linear. Untuk menyelesaikan masalah program linear terdapat beberapa metode yang umum digunakan, yaitu metode grafik dan metode simpleks. Metode grafik, hanya dapat digunakan untuk masalah dengan dua variabel saja, sehingga apabila masalah program linear memuat lebih dari dua variabel akan sulit penyelesaiannya. Meskipun dalam prakteknya masalah program linear jarang yang hanya memuat dua variabel, tetapi metode grafik mempermudah untuk memahami pengertianpengertian yang timbul dalam masalah program linear. Sedangkan metode simpleks adalah metode aljabar yang digunakan untuk menyelesaikan masalah program linear yang melibatkan lebih dari dua variabel dan pada prakteknya, lebih sesuai dilakukan dengan program komputer dengan ratusan atau ribuan variabel dan kendala. Ada metode lain yang dapat digunakan untuk menyelesaikan masalah program linear yaitu metode titik-interior. Perbedaan antara metode titikinterior dengan metode simpleks adalah pada metode simpleks penyelesaian dilakukan dengan meninjau setiap titik sudut pada batas dari daerah layak hingga dicapai titik optimum. Sedangkan pada metode titik-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2
interior penyelesaian dilakukan dengan meninjau titik-titik yang berada dalam daerah layak hingga dicapai titik optimum. Algoritma titik-interior dapat dibagi dalam empat kelas utama, yaitu affine scaling methods, metode proyektif atau lebih dikenal dengan metode Karmarkar, path-following methods, dan
potential-reduction methods.
Dalam tugas akhir ini akan dibahas metode Karmarkar. Disebut metode proyektif karena tranformasi yang digunakan adalah tranformasi proyektif. Ide dasar metode Karmarkar, yaitu dimulai dengan memilih titikinterior awal di dalam ruang penyelesaian. Gradien fungsi tujuan di titikinterior awal adalah arah yang membuat fungsi tujuan meningkat dengan cepat. Jika satu titik sembarang ditempatkan di sepanjang gradien itu dan lalu memproyeksikannya secara tegak lurus terhadap ruang penyelesaian, maka hasil transformasi titik-interior yang dipilih diposisikan lebih dekat dengan titik optimum. Hasil transformasi titik-interior yang dipilih dijalankan ke suatu titik-interior lain dengan arah layak dan besar langkah yang sesuai. Proses iterasi ini diulang hingga penyelesaian optimum dicapai.
B. Rumusan Masalah Berdasarkan uraian di atas, maka permasalahan yang akan dibahas dalam tugas akhir ini adalah: 1. Apa yang dimaksud dengan metode Karmarkar?
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
2. Bagaimana
menyelesaikan
masalah
program
linear
3
dengan
menggunakan metode Karmarkar? 3. Bagaimana aplikasi metode Karmarkar untuk menyelesaikan masalah program linear?
C. Tujuan Penulisan Bedasarkan rumusan masalah, tujuan dari penulisan tugas akhir ini adalah: 1. Memahami apa yang dimaksud dengan metode Karmarkar. 2. Dapat menyelesaikan masalah program linear dengan menggunakan metode Karmarkar. 3. Dapat menyelesaikan aplikasi metode Karmarkar untuk menyelesaikan masalah program linear.
D. Batasan Masalah Agar penulisan mencapai tujuan yang dimaksud, maka perlu ada batasan mengenai permasalahan yang diangkat. Adapun batasan masalahnya, yaitu penulis akan membahas masalah program linear dalam bentuk standar meminimumkan.
E. Manfaat Penulisan Adapun manfaat yang diharapkan penulis dalam tugas akhir ini adalah dapat menambah referensi tentang penyelesaian masalah program linear dengan menggunakan metode Karmarkar.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
4
F. Metode Penulisan Metode yang digunakan penulis adalah metode studi pustaka, yaitu dengan mempelajari buku-buku yang berkaitan dengan metode Karmarkar untuk menyelesaikan masalah program linear.
G. Sistematika Penulisan Sistematika penulisan tugas akhir ini adalah sebagai berikut : BAB I Pendahuluan A. Latar Belakang B. Rumusan Masalah C. Tujuan Penulisan D. Batasan Masalah E. Manfaat Penulisan F. Metode Penulisan G. Sistematika Penulisan BAB II Optimisasi untuk Persoalan Linear A. Matriks dan Sistem Persamaan Linear B. Ruang Vektor C. Masalah Program Linear BAB III Metode Karmarkar A. Bentuk Kanonik Karmarkar B. Asumsi-Asumsi dalam Masalah Karmarkar
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
5
C. Transformasi Proyeksi D. Mengubah Masalah Program Linear Bentuk Umum ke Bentuk Kanonik Karmarkar E. Algoritma Karmarkar F. Aplikasi Metode Karmarkar dalam menyelesaikan masalah Program Linear BAB IV Penutup A. Kesimpulan B. Saran
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB II RUANG VEKTOR DAN MASALAH PROGRAM LINEAR
A. Matriks dan Sistem Persamaan Linear Definisi 2.1 Matriks Diagonal Suatu matriks A berorde
disebut matriks diagonal jika
untuk
, yaitu
(2.1)
Teorema 2.1: Sifat Transpos Jika ukuran matriks
adalah matriks dengan sedemikian sehingga
operasi berikut dapat dilakukan, maka 1. 2.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
7
Bukti:
Misalkan
, dengan
, dengan
1. 2.
i)
ii)
dan misalkan
. Akan dibuktikan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
8
Teorema 2.2 Jika matriks A adalah sebuah matriks
dan
, maka
persamaan matriks (2.2) (2.3) Persamaan (2.2) dan (2.3) mempunyai penyelesaian tunggal untuk X
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
9
Bukti: Misalkan tunggal
, akan dibuktikan matriks X mempunyai penyelesaian yang memenuhi
, dan karena itu merupakan
penyelesaian dari kedua persamaan (2.2) dan (2.3). Untuk melihat bahwa penyelesaian ini tunggal misalkan bahwa Y juga memenuhi persamaan (2.2), yaitu
. Kemudian
Karena itu penyelesaian dari persamaan (2.2) adalah tunggal, dan argumen yang sama diterapkan pada persamaan (2.3).
Definisi 2.2 Invers Matriks Suatu matriks A berorde
dikatakan taksingular (nonsingular) atau
dapat dibalik (invertible) jika terdapat matriks B sehingga
.
Matriks B disebut sebagai invers perkalian (multiplicative inverse) dari A. Notasi yang umum untuk invers adalah
.
Definisi 2.3 Persamaan Linear Suatu persamaan linear dalam n variabel
adalah persamaan
yang dapat dinyatakan dalam bentuk (2.4)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
dengan dan
dan
adalah konstanta real,
10
adalah variabel
tidak semua sama dengan nol.
Definisi 2.4 Sistem Persamaan Linear Suatu sistem persamaan linear dalam
adalah himpunan
persamaan linear
variabel, yang dapat dinyatakan dalam bentuk
(2.5)
dengan
dan
adalah konstanta real dan
semua sama dengan nol, untuk , dapat terjadi
,
tidak
. Dalam sistem persamaan linear , atau
.
Definisi 2.5 Matriks Lengkap Matriks Lengkap dari sistem persamaan linear (2.5) adalah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
11
Definisi 2.6 Penyelesaian Sistem Persamaan Linear Apabila
,
dimana
adalah
konstanta-konstanta real yang memenuhi semua sistem persamaan linear dalam (2.5), maka konstanta
disebut penyelesaian dari sistem
persamaan linear.
Definisi 2.7 Sistem persamaan linear disebut konsisten jika sistem persamaan tersebut setidak-tidaknya mempunyai paling tepat sedikit satu penyelesaian atau takberhingga banyak penyelesaian. Sistem persamaan linear disebut tidak konsisten jika sistem persamaan tersebut tidak mempunyai penyelesaian.
Definisi 2.8 Sistem Persamaan Linear Homogen Suatu sistem persamaan linear disebut sistem persamaan linear homogen jika konstanta-konstanta di ruas kanan semuanya nol. Sistem persamaan linear homogen dapat dinyatakan dalam bentuk
(2.6)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
12
Sistem persamaan linear homogen selalu mempunyai penyelesaian konsisten. Jadi, jika dalam sistem persamaan linear homogen penyelesain tunggal
, memiliki
maka penyelesaian ini disebut
penyelesaian trivial. Jika ada penyelesaian lain maka penyelesaian itu disebut penyelesaian taktrivial.
Definisi 2.9 Operasi baris elementer Operasi baris elementer pada suatu matriks adalah salah satu operasi: 1. Menukar letak dari dua baris matriks tersebut, yakni menukar baris ke-i dan ke-j, dengan notasi
.
2. Mengalikan suatu baris dengan konstanta tak nol, yakni mengalikan baris ke-i dengan bilangan c, dimana
, dengan notasi
.
3. Mengganti suatu baris dengan hasil penjumlahan baris tersebut dan kelipatan baris lain, yakni mengganti baris ke-i ditambah dengan c kali baris ke-j, dengan notasi
.
Definisi 2.10 Bentuk eselon baris Suatu matriks dikatakan memiliki bentuk eselon baris jika 1. Entri bukan nol pertama dalam setiap baris adalah 1. 2. Jika baris k tidak seluruhnya mengandung nol, maka banyaknya entri nol di bagian depan pada baris dibagian depan pada baris k.
lebih besar dari banyaknya entri nol
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
13
3. Jika terdapat baris-baris yang entrinya semuannya nol, maka baris-baris ini berada di bawah baris-baris yang memiliki entri-entri bukan nol.
Definisi 2.11 Matriks Elementer Suatu matriks yang diperoleh dari matriks satuan I dengan melakukan satu operasi baris elementer disebut matriks elementer. Terdapat tiga jenis matriks elementer yang berkorespondensi dengan ketiga jenis operasi baris elementer. 1. Matriks elementer jenis 1 adalah matriks yang diperoleh dengan mempertukarkan dua baris dari I. 2. Matriks elementer jenis 2 adalah
matriks yang diperoleh dengan
mengalikan satu baris dari I dengan konstanta bukan nol. 3. Matriks elementer jenis 3 adalah matriks yang diperoleh dari I dengan menjumlahkan kelipatan dari satu baris pada baris yang lain.
Definisi 2.12 Ekivalen Baris Matriks B dikatakan ekivalen baris dengan A jika terdapat matriks elementer sehingga
B. Ruang Vektor Definisi 2.13 Ruang Vektor Misalkan V adalah suatu himpunan tak kosong yang terdiri dari objek-objek di mana didefinisikan operasi penjumlahan dan perkalian dengan skalar.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
14
Himpunan V dengan operasi penjumlahan dan perkalian dengan skalar dikatakan membentuk suatu ruang vektor jika aksioma-aksioma berikut dipenuhi: 1. 2. 3. Terdapat elemen
sehingga
4.
sehingga
5.
untuk setiap skalar
6.
untuk setiap skalar
7.
untuk setiap skalar
8. 9. Jika 10. Jika
dan
suatu skalar,
maka
Contoh 2.1
Misalkan
pada
dan
adalah vektor-vektor di
. Penjumlahan
didefinisikan sebagai berikut:
(2.7)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
dan operasi perkalian dengan skalar
di R didefinisikan sebagai berikut:
(2.8)
Tunjukkan bahwa
merupakan ruang vektor.
Bukti:
Misalkan
,
, dan
,
1. Akan ditunjukkan
2. Akan ditunjukkan
3. Akan ditunjukkan terdapat elemen
sehingga
15
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
4. Akan ditunjukkan
Invers dari
5. Akan ditunjukkan
6. Akan ditunjukkan
7. Akan ditunjukkan
sehingga
adalah
sehingga
16
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
17
8. Akan ditunjukkan
9. Akan ditunjukkan
Seperti pada persamaan (2.8) 10. Akan ditunjukkan
Seperti pada persamaan (2.7)
Definisi 2.14 Ruang bagian (subspace) Jika S adalah subhimpunan tak kosong dari suatu ruang vektor V, dan S memenuhi syarat-syarat berikut: a. b.
jika jika
untuk sembarang skalar . dan
Maka S disebut ruang bagian dari V.
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
18
Contoh 2.2
Tunjukan apakah bagian dari
merupakan ruang
atau tidak.
Bukti: 1. Akan dibuktikan
jika
untuk sembarang skalar .
dan karena
maka
karena
maka
2. Akan dibuktikan
jadi
jika
dan
.
.
dan karena
karena
dan
maka
dan
dan
maka
. Sehingga
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
19
ruang bagian dari
Definisi 2.15 Kombinasi linear Misalkan
adalah vektor-vektor dalam suatu ruang vektor V.
Jumlahan vektor-vektor yang berbentuk (2.9) dimana
adalah skalar-skalar disebut sebagai kombinasi linear
dari
Definisi 2.16 Merentang (span) Misalkan
adalah vektor-vektor dalam suatu ruang vektor V dan
jika masing-masing vektor pada V dapat dinyatakan sebagai kombinasi linear dari merentang V.
maka dapat dikatakan bahwa vektor-vektor
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
20
Definisi 2.17 Bebas linear (linearly independent) Vektor-vektor
dalam ruang vektor V disebut bebas linear jika (2.10)
mengakibatkan semua skalar-skalar
sama dengan 0.
Definisi 2.18 Bergantung linear (linearly dependent) Vektor-vektor
dalam ruang vektor V disebut bergantung linear
jika terdapat skalar-skalar
yang tidak semuanya nol sehingga (2.11)
Definisi 2.19 Basis Vektor-vektor
membentuk basis untuk ruang vektor V jika dan
hanya jika: a.
bebas linear.
b.
merentang V.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
21
Definisi 2.20 Dimensi dari ruang vektor V adalah
banyaknya vektor-vektor yang
membentuk basis untuk ruang vektor V. Selain itu, mendefinisikan ruang vektor nol sebagai berdimensi nol.
Definisi 2.21
Misalkan matriks
,
yaitu
. Vektor-vektor dalam
,
,
,
yang dibentuk dari baris-baris matriks A dinamakan
vektor-vektor baris dari A dan vektor-vektor dalam
,
,
, yaitu
,
yang dibentuk dari kolom-kolom matriks A
dinamakan vektor-vektor kolom dari A.
Definisi 2.22 Jika A adalah matriks
, maka ruang bagian dari
yang direntang
oleh vektor-vektor baris dari A disebut ruang baris dari A. Ruang bagian dari
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
22
yang direntang oleh vektor-vektor kolom dari A disebut ruang kolom dari A. Ruang kolom dari A dapat di notasikan
Contoh 2.3: Misalkan
Ruang baris dari A adalah himpunan ketiga tupel yang berbentuk
Ruang kolom dari A adalah himpunan semua vektor yang berbentuk
Jadi ruang baris dari A adalah ruang bagian berdimensi dua dari ruang kolom dari A adalah
.
Teorema 2.3 Dua matriks yang ekivalen baris memiliki ruang baris yang sama.
dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
23
Bukti: Jika B ekivalen baris dengan A, maka B dapat dibentuk dari A dengan sebarisan operasi baris yang berhingga banyaknya. Jadi vektor-vektor baris dari B harus merupakan kombinasi linear dari vektor-vektor baris dari A. Sebagai akibatnya, ruang baris dari B harus merupakan ruang bagian dari ruang baris A. Karena A ekivalen baris dengan B, maka dengan alasan yang sama, ruang baris dari A adalah ruang bagian dari ruang baris B.
Definisi 2.23 Ruang Nol (Null Spaces) Misal
adalah matriks
. Misalkan
penyelesaian dari sistem persamaan homogen
menyatakan himpunan semua . Jadi (2.12)
disebut sebagai ruang nol
Definisi 2.24 Rank dari matriks A adalah dimensi dari ruang baris dari A. Nulitas dari matriks A adalah dimensi ruang nol dari A.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
24
Untuk menentukan rank dari suatu matriks dapat dilakukan dengan mereduksikan matriks yang bersangkutan menjadi bentuk eselon baris.
Teorema 2.4 Jika suatu matriks
berada dalam bentuk eselon baris, maka vektor-vektor
baris dengan 1 utama (yaitu vektor-vektor baris taknol) membentuk suatu basis untuk ruang baris dari .
Bukti: Misalkan matriks
berada dalam bentuk eselon
baris, yakni
Akan dibuktikan vektor-vektor baris dengan 1 utama membentuk suatu basis untuk ruang baris dari . Ruang baris dari A dapat dibentuk sebagai berikut
Jadi ruang baris dari
adalah himpunan matriks-matriks
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
25
.
Akan ditunjukkan bahwa baris 1 sampai baris m dari matriks basis untuk ruang baris dari
membentuk
. Misalkan vektor-vektor baris dapat dinyakan
sebagai
.
Akan ditunjukkan
membentuk basis.
1. Akan ditunjukkan Vektor
bebas linear disebut bebas linear jika
mengakibatkan semua skalar persamaan
sama dengan nol. Perhatikan , yakni
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
26
Matriks lengkap dari sistem persamaan tersebut dapat ditulis
Dengan operasi baris elementer terhadap baris 2, yakni
maka
akan diperoleh
Operasi baris elementer dilakukan sampai pada baris ke-m, yakni dengan operasi baris elementer
dengan operasi baris elementer
maka akan diperoleh
maka akan diperoleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
maka
27
, . Karena
, maka
bebas linear. 2. Akan dibuktikan
merentang ruang baris dari A.
dikatakan merentang jika masing-masing vektor pada ruang baris di ruang bagian dari
dapat dinyatakan sebagai kombinasi linear dari
. Ambil sembarang vektor bagian dari
. Akan ditunjukkan untuk setiap
kombinasi linear , yakni
pada ruang baris di ruang dapat dinyatakan sebagai
. Perhatikan persamaan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
atau dapat ditulis
dengan operasi baris elementer
maka akan diperoleh
dengan operasi baris elementer
maka akan diperoleh
dengan operasi baris elementer
maka akan diperoleh
Karena maka
merentang ruang baris dari A.
28
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena
29
bebas linear dan merentang maka vektor-vektor tersebut
membentuk basis untuk ruang baris dari A.
Contoh 2.4 Misalkan
Dengan mereduksikan A menjadi bentuk eselon baris, maka diperoleh matriks
Akan dibuktikan bahwa baris 1 dan baris 2 dari matriks U dengan 1 utama membentuk suatu basis untuk ruang baris dari U. Ruang baris dari U yakni dapat dibentuk
Jadi ruang baris dari U adalah
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
30
Akan ditunjukkan bahwa baris 1 dan baris 2 dari matriks U membentuk basis untuk ruang baris dari U. Misalkan ditunjukkan
membentuk basis.
1. Akan dibuktikan Vektor
, akan
bebas linear
disebut bebas linear jika
semua skalar
mengakibatkan
sama dengan nol.
atau dapat ditulis
dengan operasi baris elementer
maka akan diperoleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
maka
,
,
. Karena
31
maka
bebas linear. 2. Akan dibuktikan
merentang ruang baris dari U
dikatakan merentang jika masing-masing vektor di
dapat
dinyatakan sebagai kombinasi linear. Perhatikan persamaan dibawa ini
atau dapat ditulis
dengan operasi baris elementer
maka maka
,
, dan
maka akan diperoleh
. Karena
dan
merentang ruang baris dari U. Karena
bebas linear dan merentang maka vektor-vektor
tersebut membentuk basis untuk ruang baris dari U. Jelas bahwa baris 1 dan baris 2 dari matriks U membentuk basis untuk ruang baris dari U adalah
, maka rank dari U adalah 2. Karena U dan A
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
32
ekivalen baris, maka matriks U dan A memiliki ruang baris yang sama sehingga rank dari A adalah 2.
Definisi 2.25 Variabel utama adalah variabel-variabel yang bersesuaian dengan 1 utama pada matriks yang diperluas. Sedangkan variabel yang bukan 1 utama disebut sebagai variabel bebas.
Teorema 2.5 Jika A adalah matriks
, maka dimensi ruang baris dari A sama dengan
dimensi ruang kolom dari A.
Bukti Jika A adalah matriks
dengan rank r, maka bentuk eselon baris
U dari A akan memiliki 1 utama sebanyak r. Kolom-kolom dari U yang berkorespondensi dengan 1 utama akan bebas linear. Akan tetapi, tidak membentuk basis untuk ruang kolom dari A, karena pada umumnya A dan U akan memiliki ruang-ruang kolom yang berbeda. Misalkan matriks yang diperoleh dari
melambangkan
dengan menghapus semua kolom-kolom yang
berkorespondesi dengan peubah-peubah bebas. Hapuskan kolom-kolom yang
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
sama dari A dan nyatakan matriks yang baru dengan dan
33
. Matriks-matriks
adalah ekivalen baris. Jadi, jika x adalah penyelesaian dari
maka x juga harus merupakan penyelesaian dari kolom dari
bebas linear, x harus sama dengan
sebelumnya karena linear. Karena
,
. Karena kolom. Berdasarkan uraian
x sama dengan 0 maka kolom-kolom dari
bebas
memiliki r kolom, maka dimensi ruang kolom dari A
satidaknya adalah r. Berdasarkan Definisi matriks transpos, baris-baris dari matriks A merupakan kolom-kolom dari matrik
sehingga dapat ditulis
Seperti yang telah dibuktikan bahwa untuk sembarang matriks dimensi ruang kolomnya lebih besar atau sama dengan dimensi ruang barisnya, sehingga
Berdasarkan Definisi matrik transpos, baris-baris dari matrik kolom-kolom dari matrik
merupakan
sehingga dapat ditulis
Jadi untuk sembarang matriks A, dimensi ruang barisnya harus sama dengan dimensi ruang kolomnya.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
34
Teorema 2.6 Jika A adalah suatu matriks dengan n kolom, maka
Bukti Karena A memiliki n kolom, maka sistem linear homogen
memiliki n
faktor yang tidak diketahui (variabel). Variabel ini terbagi dalam dua kategori, variabel utama dan variabel bebas. Jadi
Tetapi banyaknya variabel utama adalah sama dengan banyaknya 1 utama di dalam bentuk eselon baris tereduksi dari A, dan banyaknya variabel satu utama merupakan rank dari A. Jadi
Banyaknya variabel bebas adalah sama dengan nulitas dari A. Hal ini terjadi karena nulitas dari A adalah dimensi ruang solusi dari
, yang sama
dengan banyaknya parameter pada solusi umum yang sama dengan banyaknya variabel bebas. Jadi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
35
Definisi 2.26 Ruang hasil kali dalam Hasil kali dalam pada ruang vektor V adalah sebuah operasi pada V yang menunjuk setiap pasang vektor-vektor x dan y di dalam V dengan sebuah bilangan real a.
yang memenuhi syarat berikut: ,
b.
dan ,
c.
jika dan hanya jika
.
. ,
dan
.
Sebuah ruang vektor V dengan hasil kali dalamnya disebut ruang hasil kali dalam.
Contoh 2.5 Ruang vektor
. Tunjukkan bahwa hasil kali skalar yang didefinisikan:
(2.13)
adalah hasil kali dalam untuk
. Persamaan (2.13) dapat juga ditulis (2.14)
dengan
menyatakan transpose matriks x.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
36
Penyelesaian:
Ambil sembarang vektor
vektor
,
, dan
, dalam ruang
dan sembarang skalar
a. Akan dibuktikan
,
dan
jika dan hanya jika
. Akan dibuktikan Diketahui
(2.15) maka dari persamaan (2.15) dapat diperoleh
Jadi
Akan dibuktikan Diketahui
dan
maka diperoleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
37
Jadi b. Akan dibuktikan
,
.
Jadi terbukti c. Akan
dibuktikan .
,
dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
38
=
Jadi terbukti Dari a, b, dan c terbukti bahwa hasil kali dalam di ruang vektor
adalah
hasil kali dalam skalar
Definisi 2.27 Panjang vektor atau norma Jika x adalah sebuah vektor di dalam sebuah ruang hasil kali dalam panjang atau norma dari x didefinisikan
(2.16)
Teorema 2.7 Jika
adalah vektor pada
, maka:
a. b.
jika dan hanya jika
,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
39
Bukti: a. Misalkan
adalah vektor pada
ditulis
, akan dibuktikan .
atau dapat
ini jelas karena hasil dari akar
tidak akan bernilai negatif dan nilai dari kuadrat tidak akan bernilai negatif.
b. Akan dibuktikan
jika dan hanya jika
Diketahui
dan akan dibuktikan
.
(2.17) karena hasil dari
untuk setiap
negatif maka
untuk setiap
tidak akan bernilai . Sehingga persamaan
(2.17) bernilai benar jika dan hanya jika setiap
atau
, jadi
untuk
.
. Diketahui
, dan akan dibuktikan
Karena diketahui
, maka
. . Akibatnya
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
40
Teorema 2.8 .
Bukti: Misalkan x vektor sedemikian sehingga yaitu x memenuhi relasi . Karena
. Maka
. Oleh karena itu , maka jelas
, dan . Sebaliknya, jika
. Dengan demikian
maka akibat dari Teorema 2.6,
dimana n adalah banyaknya kolom A. Oleh karena itu teorema tersebut terbukti.
Teorema 2.9 Jika A adalah suatu matriks sebarang, maka
Bukti: Misalkan A sembarang matrik. Menurut Definisi rank maka
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
41
Berdasarkan Definisi matrik transpos, baris-baris dari matrik A merupakan kolom-kolom dari matrik
sehingga dapat ditulis
Berdasarkan Teorema 2.5, maka
Definisi 2.28 Ortogonal Dua vektor x dan y dalam
dikatakan ortogonal, jika (2.18)
dan dilambangkan dengan
Definisi 2.29 Subruang yang ortogonal Dua ruang bagian X dan Y dalam
dikatakan ortogonal, jika (2.19)
Jika X dan Y saling ortogonal , dapat dilambangkan dengan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
42
Definisi 2.30 Komplemen Ortogonal Misalkan Y adalah ruang bagian dari dalam
. Himpunan semua vektor-vektor di
yang ortogonal pada setiap vektor di Y akan dinotasikan dengan
.
Jadi
Himpunan
disebut komplemen ortogonal dari Y.
Teorema 2.10 1. Jika X dan Y adalah ruang bagian ortogonal dari
, maka
2. Jika Y adalah ruang bagian dari
juga merupakan ruang
bagian dari
, maka
.
.
Bukti: 1.
Misalkan
dan
, akan ditunjukkan
berdasarkan definisi ortogonal maka 2.7 b
2. Misalkan
. Karena , akibat dari teorema
.
dan
adalah bilangan skalar, maka untuk setiap
,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Oleh karena itu,
. Misalkan
43
adalah elemen-elemen dari
, maka
Untuk setiap dari
. Maka diperoleh
adalah ruang bagian
.
Definisi 2.31 Rank Penuh Jika A adalah matriks
dengan rank
, maka dapat
dikatakan bahwa matriks tersebut memiliki rank penuh.
Teorema 2.11 Misalkan
matriks berukuran
penuh m. Misalkan ruang kolom dari
. Misalkan matriks
menyatakan ruang nol maka
dan
Bukti: dan
Akan dibuktikan Berarti cukup dibuktikan
, artinya
menyatakan
merupakan subruang yang saling
orthogonal.
Misalkan
dan
mempunyai rank
,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
44
Perhatikan bahwa dan
Maka (2.20) Karena
maka persamaan (2.20) dapat di ubah menjadi
atau Dengan demikian Jadi
Gambar 2.1. –
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Dari Teorema 2.11 telah diperlihatkan bahwa adalah subruang yang saling orthogonal. Misalkan dan –
.
Maka
dapat juga ditulis
45
dan dan
–
(2.21)
Karena
, maka persamaan (2.21) dapat di ubah menjadi –
(2.22)
Kalikan kedua ruas dengan , maka didapatkan – Diketahui bahwa
, maka didapatkan
– –
atau
Dengan demikian
–
(2.23)
Subsitusikan persamaan (2.23) ke persamaan (2.22), maka didapatkan –
–
– –
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
–
46
(2.24)
dengan
(2.25)
Definisi 2.32 Matriks proyeksi ortogonal Matriks P berukuran
, dengan
disebut matriks
proyeksi ortogonal atau matriks proyeksi ruang nol dari .
Teorema 2.12 Jika A adalah sebuah matriks
, maka
dan
Bukti: Sebelumnya telah diketahui bahwa bahwa
. Di lain pihak, misalkan
dari
, maka
akibatnya
dimisalkan matriks
adalah sembarang vektor
ortogonal pada setiap vektor-vektor kolom dari
. Jadi x merupakan elemen dari
dan
dan ini mengimplikasikan
maka . Jadi
dan
. Karena . Secara khusus, dapat
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
47
Teorema 2.13 Jika S adalah ruang bagian dari
, maka
.
Bukti: Jika
, maka
ortogonal pada setiap
, sehingga sembarang elemen dari dan
. Karena
dan mengakibatkan,
di dalam
. Oleh karena itu,
. Di lain pihak, misalkan bahwa z adalah . Misalkan z sebagai penjumlaha , maka
ortogonal pada
. Oleh karena itu,
dan
, dimana
dan . Sehingga
.
Teorema 2.14 Sistem persamaan linear homogen
memiliki penyelesaian taktrivial jika
.
Bukti: Sistem homogen selalu konsisten. Bentuk eselon baris dari matriks yang bersangkutan memiliki paling banyak m baris bukan nol. Jadi terdapat paling banyak m peubah utama. Karena semuanya secara keseluruhan terdapat n
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
peubah dan
48
, maka harus terdapat beberapa peubah bebas. Peubah-
peubah bebas ini dapat diberi sembarang nilai. Untuk setiap pemberian nilai ke peubah-peubah bebas ini terdapat satu penyelesaian bagi sistem yang bersangkutan.
Teorema 2.15 Misalkan A matriks
. Hal-hal berikut adalah ekivalen:
a. A taksingular b.
hanya mempunyai penyelesaian trivial
Bukti:
Misalkan A taksingular. Akan dibuktikan
hanya mempunyai
penyelesaian trivial . Misalkan A taksingular dan
Karena
merupakan penyelesaian dari
merupakan penyelesaian dari
, maka
, maka
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Jadi
49
hanya mempunyai penyelesaian trivial.
Misalkan
hanya mempunyai penyelesaian trivial
. Akan
dibuktikan A taksingular. Misalkan
hanya mempunyai penyelesaian trivial
. Dengan
menggunakan operasi-operasi baris elementer, sistem tersebut dapat ditransformasikan menjadi bentuk
, dimana U berbentuk eselon
baris. Jika salah satu elemen diagonal dari U adalah 0, maka baris terakhir dari U seluruhnya terdiri dari 0. Tetapi kemudian
akan ekivalen
dengan suatu sistem dengan lebih banyak peubah daripada banyaknya persamaan dan dengan demikian berdasarkan Teorema 2.14 sistem akan memiliki penyelesaian taktrivial. Jadi U haruslah merupakan matriks segitiga dengan elemen-elemen diagonal semuanya sama dengan 1. Sebagai akibatnya maka I adalah bentuk eselon baris tereduksi dari A sehingga A ekivalen baris dengan I. Karena A ekivalen baris dengan I, maka terdapat matriks-matriks elementer
tetapi karena
sehingga
dapat dibalik,
juga dapat dibalik. Jadi A taksingular dan
maka hasil kali
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
50
Teorema 2.16 Matriks
adalah matriks bujur sangkar yang berorde
jika dan hanya jika
nonsingular
.
Bukti: Akan dibuktikan Misalkan
adalah nonsingular. Untuk membuktikan ini, misalkan z
sebagai penyelesaian untuk yakni
(2.26)
Berdasarkan Teorema 2.15, trivial maka
hanya mempunyai penyelesaian
. Sebagai akibatnya
hanya mempunyai
penyelesaian trivial dan vektor-vektor kolom dari linear, maka Akan dibuktikan
mempunyai rank
adalah bebas
.
adalah nonsingular
Untuk membuktikan ini, misalkan z sebagai penyelesaian untuk persamaan (2.26). Kemudian . Karena mempunyai
Jelas bahwa, , maka akibatnya
, maka vektor-vektor kolom dari
bebas linear dan sebagai akibatnya penyelesaian trivial. Jadi
. Jika adalah
hanya mempunyai
dan persamaan (2.26) hanya mempunyai
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
51
penyelesaian trivial. Oleh karena itu berdasarkan Teorema 2.15 adalah nonsingular.
Definisi 2.33 Persekitaran Persekitaran dari titik
adalah himpunan dari titik-titik , dengan
(2.27)
Definisi 2.34 Titik Interior Suatu titik dari
dikatakan titik interior dari himpunan S jika ada persekitaran
sedemikian sehingga semua titik dalam persekitaran dari
juga
berada dalam S, yakni (2.28)
Definisi 2.35 Transformasi Misalkan V dan W dua ruang vektor. Transformasi atau pemetaan atau fungsi T dari V ke dalam W adalah aturan yang memasangkan setiap elemen x di V dengan satu dan hanya satu elemen di W . Untuk selanjutnya, transformasi ini ditulis
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
52
Ruang vekror V disebut daerah asal T. Nilai transformasi T untuk elemen ditulis
yang merupakan elemen di W. Elemen
disebut peta
dari x. Maka transformasi
T dari V ke W jika dan hanya jika
Definisi 2.36 Misalkan
transformasi pada S, maka dan
, untuk setiap
adalah invers dari yaitu komposisi dari
jika dan
adalah transformasi identitas pada S. Notasi yang umum untuk invers adalah
.
Teorema 2.17 Misalkan
, maka
.
Bukti: Misalkan
adalah transformasi dari
. Akan dibuktikan
. i.
Misalkan , maka transformasi, sehingga
ini berarti bahwa dan dan
. Karena
adalah .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ii.
Misalkan
, karena
berarti ada
. Maka
berarti
53
sehingga maka
. Misalkan Akan
.
dibuktikan
adalah
dan jika Misalkan
karena
sehingga
transformasi
dari
dan
atau maka
, berarti ada
.
sedemikian
atau
maka
maka
. Misalkan
dan
, maka
dan
, tetapi
berarti
dan
adalah sebuah transformasi.
C. Masalah Program Linear Program linear (linear programming), adalah salah satu teknik analisis dari kelompok teknik riset operasi yang diterapkan dalam berbagai bidang yang memakai model matematika atau model simbolik sebagai wadahnya. Dengan demikian setiap persoalan yang dihadapi dalam suatu sistem permasalahan, haruslah dapat dirumuskan dalam simbol-simbol matematika tertentu. Misalnya di bidang ekonomi, masalah memaksimumkan laba dan meminimumkan
ongkos
produksi.
Manusia
cenderung
untuk
hidup
berprinsipkan ekonomi dengan usaha sedikit dapat memperoleh hasil sebanyak mungkin. Suatu perusahaan mempunyai kendala terbatasnya sumber input produksi dan berupaya mengoptimalkan output produksi untuk
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
54
memenuhi permintaan pasar dan mengoptimalkan penggunaan sumber produksi yang dimiliki. Permasalahan tersebut ada di dalam dunia nyata, sedangkan simbol matematika adalah dunia abstraksi yang dibuat sedemikian rupa sehingga mendekati kenyataan. Tujuan program linear adalah membantu dalam mengambil keputusan yang terbaik dari sekian banyak alternatif yang tersedia. Kelahiran teknik program linear ini berasal dari seorang ahli matematika bangsa Amerika Serikat yang bernama Dr. George Dantzig, yaitu dengan dikembangkannya metode simpleks pada tahun 1947. Pada tahun itu, Dantzig merupakan salah seorang teknokrat yang tergabung dalam kelompok Riset Operasi dari Angkatan Udara Amerika Serikat. Sebelum lahirnya karya Dantzig yang sistematis, telah terdapat pula berbagai ahli matematika lainnya yang melahirkan teknik-teknik penyelesaian masalah dengan memakai pendekatan aljabar linear (aljabar matriks) pada tahun 1930-an. Penerapan program linear untuk pertama kalinya di bidang perencanaan militer, khususnya dalam Perang Dunia II oleh angkatan bersenjata Amerika Serikat dan Inggris. Sejak itulah bersamaan dengan berkembangnya waktu, pembagunan dan teknologi, teknik-teknik program linear dengan cepat menjalar dan diterapkan dalam berbagai bidang dan disiplin ilmu dalam rangka memecahkan berbagai permasalahan yang dihadapi.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
55
Dalam merumuskan masalah program linear, diperlukan adanya fungsi sasaran dan kendala-kendala.
Definisi 2.37 Fungsi Sasaran Fungsi sasaran dalam masalah program linear dapat dinyatakan sebagai (2.29) dengan n merupakan bilangan bulat yang menyatakan banyaknya variabel, merupakan variabel ke-j, dan variabel ke-j, dengan
merupakan koefisien ongkos dari
.
Kendala-kendala dibagi dua, yakni kendala utama dan kendala tak negatif. Definisi 2.38 Kendala utama Kendala utama masalah program linear berbentuk (2.30) dengan m merupakan banyaknya persamaan, variabel ke-j pada persamaan ke-i dan kanan untuk persamaan ke-i.
merupakan koefisien menyatakan konstanta di ruas
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
56
Definisi 2.39 Kendala Tak Negatif Kendala tak negatif berbentuk (2.31) Bentuk standart masalah program linear dapat dituliskan sebagai berikut: Minimumkan
(2.32)
dengan kendala
(2.33)
dengan
dan
adalah konstanta real,
tidak semua sama dengan nol, untuk
, dan .
Fungsi sasaran (2.32) dan sistem pertidaksamaan linear (2.33) di atas dapat dituliskan dengan notasi matriks sebagai berikut: Minimumkan
(2.34)
dengan kendala
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
57
(2.35)
Atau dapat ditulis Minimumkan
(2.36)
dengan kendala
(2.37)
Dalam masalah program linear timbul hubungan dual antara dua soal program linear tertentu dan masing-masing penyelesaian optimumnya akan berkaitan. Bentuk umum masalah primal-dual adalah sebagai berikut: Masalah primal (P):
Meminimumkan
(2.38)
Dengan kendala
, .
Masalah Dual (D):
(2.39) (2.40)
Maksimumkan
(2.41)
Dengan kendala
(2.42) (2.43)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
58
dengan x adalah penyelesaian dari soal primal dan y adalah penyelesaian dari soal dual. Perhatikan bahwa vektor suku tetap dalam (2.39) menjadi vektor ongkos dalam (2.41) dan sebaliknya vektor ongkos dalam (2.38) menjadi vektor suku tetap dalam (2.42). Sedangkan koefisien matriks kendala (2.39) adalah transpose matriks koefisien dalam (2.42).
Definisi 2.40 Titik Layak dan Daerah Layak Suatu titik
yang memenuhi semua kendala pada
persamaan (2.30) dan (2.31) disebut titik layak (feasible point) atau penyelesaian layak (feasible solution). Himpunan dari titik layak-titik layak disebut daerah layak (feasible region) atau himpunan layak (feasible set) dan dinotasikan oleh S. Pada umumnya sistem pertidaksamaan linear (2.30) mempunyai penyelesaian takhingga banyak. Di antara penyelesaian-penyelesaian tersebut dicari juga yang memenuhi (2.31), dan pada umumnya masih mempunyai penyelesaian takhingga banyak. Kemudian di antara penyelesaian layak yang takhingga banyak ini dicari yang meminimumkan fungsi sasaran, maka akan diperoleh penyelesaian optimum.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
59
Definisi 2.41 Penyelesaian optimum Penyelesaian layak yang juga mengoptimumkan f disebut penyelesaian optimum.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB III METODE KARMARKAR
Masalah dalam program linear adalah mengoptimumkan suatu fungsi linear yang terbatas oleh kendala-kendala berupa persamaan atau pertidaksamaan linear. Untuk menyelesaikan masalah dalam program linear, selain menggunakan metode grafik atau metode simpleks yang sudah umum digunakan dapat juga diselesaikan dengan menggunakan metode titik-interior. Titik-interior merupakan titik-titik yang berada di dalam daerah layak. Ada dua langkah yang diperlukan dari metode titik-interior, yaitu mencari arah layak yang memperbaiki nilai fungsi sasaran pada titik tertentu dari setiap iterasi, dan menentukan besar langkah yang menghasilkan titik baru yang berada pada daerah layak sesuai arah layak yang memperbaiki nilai fungsi sasaran. Algoritma titik-interior dapat dibagi dalam empat kelas utama, yaitu affine scaling methods, metode proyektif atau lebih dikenal dengan metode Karmarkar, path-following methods, dan potential-reduction methods. Dalam bagian ini akan dibahas metode Karmarkar. Disebut metode proyektif karena tranformasi yang digunakan
adalah
tranformasi
proyektif.
Pada
tahun
1984,
seorang
matematikawan dari laboratorium AT & T Bell Laboratories bernama Narendra Karmarkar berhasil mengemukakan suatu algoritma baru untuk menyelesaikan masalah program linear yang besar dalam waktu yang cukup singkat yang tidak bisa dilakukan oleh metode simpleks. Metode Karmarkar untuk menyelesaikan masalah program linear pada dasarnya berbeda dari metode simpleks yaitu bahwa
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
61
metode simpleks dimulai dengan masalah program linear dalam bentuk standar, sedangkan metode Karmarkar dimulai dengan masalah program linear dalam bentuk kanonik khusus, yang disebut bentuk kanonik Karmarkar. Untuk lebih memahami konsep dalam metode Karmarkar perhatikan permasalahan program linear berikut. Contoh 3.1 Maksimumkan dengan kendala Agar masalah program linear di atas menjadi bentuk standar, maka ditambahkan variabel pengetat pada masalah program linear di atas, sehingga menjadi Maksimumkan dengan kendala
dengan
adalah variabel pengetat.
Gambar 3.1 menggambarkan masalah program linear di atas. Ruang penyelesaian ditunjukan dengan garis AB. Arah kenaikan f berada di arah positif
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
62
Gambar 3.1. Ilustrasi algoritma Karmarkar Iterasi dimulai dari titik-interior C dalam ruang penyelesaian (garis AB). Gradien fungsi tujuan (
) di C adalah arah yang membuat fungsi tujuan
meningkat dengan cepat. Jika satu titik sembarang ditempatkan di sepanjang gradien itu dan lalu memproyeksikannya secara tegak lurus terhadap ruang penyelesaian (garis AB), maka diperoleh titik baru D. Dari sudut pandang nilai f, titik D yang baru ini lebih baik dari titik awal C. Perbaikan seperti ini diperoleh dengan bergerak dalam arah CD, yang merupakan gradien garis hasil proyeksi, atau disebut sebagai gradien terproyeksi. Jika prosedur yang sama ini diulang di D, maka akan ditemukan satu titik baru di E yang lebih dekat dengan titik optimum. Dapat diperkirakan jika bergerak dengan sangat hati-hati dalam arah gradien terproyeksikan, maka akan dicapai titik optimum B. Langkah-langkah yang dihasilkan di sepanjang gradien terproyeksi tidak akan meleset dari titik optimum di B, dan dalam kasus n dimensi pada umumnya, arah yang diciptakan oleh gradien terproyeksi tidak akan menyebabkan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
63
terjebaknya algoritma tersebut di titik yang bukan optimum. Pada dasarnya inilah yang dicapai oleh algoritma Karmarkar.
A. Bentuk Kanonik Karmarkar Untuk menyelesaikan masalah program linear dengan menggunakan metode Karmarkar digunakan bentuk umum masalah program linear berikut: Meminimumkan
(3.1)
Dengan kendala
(3.2) (3.3) , i = 1, 2, … , n
di mana
A adalah matriks m × n,
(3.4) dan 0
adalah vektor kolom nol yang berukuran m.
Untuk memperkenalkan bentuk kanonik Karmarkar dimulai dengan memisalkan
adalah vektor dalam
komponen adalah 1. Misalkan .
dengan masing-masing
merupakan ruang nol (null spaces) dari A, maka
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
64
Definisi 3.1 Simpleks dalam adalah vektor dalam simpleks
adalah
, dan
dengan masing-masing komponen adalah 1. Pusat dari
adalah
maka
.
Berdasarkan Definisi 2.24 dan Definisi 3.1 bentuk kanonik Karmarkar dapat ditulis kembali menjadi Meminimumkan
(3.5)
dengan kendala
(3.6)
Himpunan kendala (himpunan layak)
dapat didefinikan sebagai
(3.7)
B. Asumsi-Asumsi dalam Masalah Karmarkar Algoritma Karmarkar dapat digunakan untuk menyelesaikan masalahmasalah program linear dalam bentuk kanonik Karmarkar, dengan asumsi berikut:
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
a. Pusat
dari simpleks
adalah suatu titik layak sehingga
65
.
Asumsi ini tidak bersifat membatasi, artinya sembarang masalah program linear yang memiliki suatu penyelesaian optimum dapat diubah kedalam bentuk Karmarkar sehingga memenuhi asumsi ini. b. Nilai minimum dari fungsi sasaran terhadap himpunan layak adalah nol. Asumsi ini untuk menentukan nilai
yang memenuhi nilai
minimum dari fungsi sasaran, untuk menyelesaikan masalah-masalah program linear dalam bentuk kanonik Karmarkar. c. Matriks
yang berukuran
, mempunyai rank
.
Asumsi ini merupakan asumsi teknis yang diperlukan dalam implementasi algoritma
C. Transformasi Proyeksi Pada bagian sebelumnya telah dijelaskan bahwa sembarang masalah program linear perlu diubah ke dalam suatu masalah yang ekuivalen dalam bentuk kanonik Karmarkar. Ekuivalen diartikan bahwa penyelesaian dari masalah dalam bentuk yang baru dapat digunakan untuk menentukan penyelesaian dari masalah dalam bentuk standar atau sebaliknya. Telah diketahui bahwa sembarang masalah program linear dapat ditransformasikan ke masalah yang ekuivalen dalam bentuk standar. Oleh karena itu, cukup ditunjukkan bahwa sembarang masalah program linear dalam bentuk standar dapat ditransformasikan ke suatu masalah ekuivalen dalam bentuk kanonik Karmarkar. Dalam kenyataanya, transformasi yang
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
66
diberikan berikut akan selalu menjamin bahwa asumsi a dari asumsi-asumsi dalam masalah Karmarkar dipenuhi.
Definisi 3.2 Misalkan
dimana
,dengan
. Misalkan
merupakan transformasi proyeksi yang memetakan positive orthant dari ke simpleks
, yakni
, yang didefinisikan sebagai
dengan
(3.8)
Teorema 3.1 Untuk
, maka T merupakan transformasi proyeksi yang memiliki sifat-sifat
berikut: 1. T merupakan pemetaan satu-satu yaitu untuk 2. T memetakan setiap
,
. pada
, yaitu untuk , ada
sedemikian sehingga
3. Transformasi invers dari T ada pada sebagai
dengan
.
dan diberikan .
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
4. T
memetakan
a
ke
pusat
simpleks
,
67
yakni
. 5. Misalkan
x
memenuhi . Maka
,
dan
.
Misalkan
.
Bukti: 1. T merupakan pemetaan satu-satu,yakni
Jika mengigat persamaan (3.8) dapat didefinisikan
(3.9)
Misalkan dengan yakni
dengan Untuk
maka dapat disimpulkan (3.10)
Untuk
maka (3.11)
Dari persamaan (3.10) dan persamaan (3.11) dapat disimpulkan bahwa
atau
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
68
sehingga dapat ditulis
atau Jadi terbukti bahwa T adalah pemetaan satu-satu
2. Akan dibuktikan Ambil sembarang
, maka dan
Misalkan kolom ke i dari
adalah
dan akan ditunjukkan
dikalikan kolom ke i dari ,
maka diperoleh
Akan dibuktikan
dimana
,yakni
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
69
(3.12)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena mengambil sembarang
,berarti
70
dengan
dengan demikian
Jadi, dari persamaan (3.12) diperoleh
Karena
dipilih sembarang, maka .
Jadi terbukti
3. Berdasarkan sifat 1 dan sifat 2, karena satu dan pada maka
memenuhi sifat satu-
memiliki fungsi invers yang dapat ditulis
dan diberikan sebagai
dengan
. Akan dibuktikan bahwa
cukup ditunjukkan bahwa
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena diketahui
maka
Bila diambil
maka diperoleh
Jadi terbukti
memiliki fungsi invers dengan
71
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
4. Jika mengigat persamaan (3.8) dan diketahui diberikan
Karena
72
, dan
, maka diperoleh
maka diperoleh
, yakni T memetakan a ke pusat dari simpleks.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
5. Ambil sembarang
, maka
, dan
sehingga
Karena
73
maka diperoleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
74
(3.13)
Karena x memenuhi
maka persamaan (3.13) dapat di ubah
menjadi
Karena
maka diperoleh
Teorema 3.2 Misalkan T merupakan transformasi proyektif seperti pada Teorema 3.1 dan diberikan matriks sehingga
. Maka ada suatu matriks jika dan hanya jika
.
sedemikian
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
75
Bukti: T merupakan transformasi proyektif, dan Akan dibuktikan
Ambil sembarang
, maka
, dan akan
dibuktikan Misalkan kolom ke kolom ke
dari
dari
adalah
dikalikan kolom ke
dari
, dan
adalah – , maka diperoleh –
Akan dibuktikan maka diperoleh
dan karena
,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
76
(3.14)
Karena
maka persamaan (3.14) dapat di ubah menjadi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Ambil sembarang
, maka
77
, dan akan
dibuktikan Misalkan kolom ke kolom ke
dari
dari
adalah
dikalikan kolom ke
dari
adalah – , maka diperoleh –
karena
, dan
maka diperoleh
, dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
78
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
79
Teorema 3.3 Misalkan T merupakan transformasi proyektif seperti pada definisi 3.2 dan diberikan vektor
. Maka ada suatu vektor
jika dan hanya jika
sedemikian sehingga
.
Bukti: T merupakan transformasi proyektif, dan Akan dibuktikan Ambil sembarang
, maka
, dan akan dibuktikan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Misalkan kolom ke
dari
, dan kolom ke
karena
adalah dari
dikalikan kolom ke
dari
80
untuk
adalah , maka diperoleh
, maka
(3.15)
Karena
, yakni
maka persamaan (3.15) dapat di ubah menjadi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Ambil sembarang
Misalkan kolom ke kolom ke
Karena
dari
, maka
dari
81
, dan akan dibuktikan
adalah
dikalikan kolom ke
adalah , maka diperoleh
, dan
maka
dari , dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
82
D. Mengubah Masalah Program Linear Bentuk Standar ke Bentuk Kanonik Karmarkar Pertimbangkan masalah program linear berikut dalam bentuk standar: Minimumkan Dengan kendala
,
(3.16)
Perhatikan bahwa sembarang masalah program linear dapat diubah ke bentuk seperti di atas. Masalah dual dari bentuk standar (3.16) di atas adalah Maksimumkan Dengan kendala
,
(3.17)
Berikut ini adalah langkah-langkah untuk menjelaskan bagaimana mengubah masalah program linear umum ke dalam bentuk kanonik Karmarkar.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
83
Langkah 1: Kombinasikan masalah primal dan dual Bila masalah primal dalam persamaan (3.16) dan malasah dual dalam persamaan (3.17) dikombinasikan akan diperoleh sistem berikut ini:
(3.18)
Lemma 3.1 Misalkkan x dan
masing-masing adalah penyelesaian layak untuk masalah
program linear primal dan dual, maka
Bukti
.
:
Karena x dan
adalah penyelesaian layak, maka
. Bila kedua sisi dari pertidaksamaan maka dihasilkan atau
. Karena
,
, dan
dikalikan dengan , maka
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
84
Teorema 3.4 Misalkan
dan
masing-masing adalah penyelesaian layak untuk primal
dan dual. Jika
, maka
dan
adalah penyelesaian optimum
untuk masing-masing masalah.
Bukti
:
Misalkan x adalah sembarang penyelesaian layak untuk masalah primal. Karena
adalah suatu peyelesaian layak untuk dual, maka dengan lemma
dualitas (Lemma 3.1) diperoleh . Karena itu
. Jadi jika
, maka
adalah penyelesaian optimum untuk
masalah primal. Di lain pihak, misalkan masalah dual. Karena
adalah sembarang penyelesaian layak untuk
adalah suatu penyelesaian layak untuk primal, maka
dengan lemma dualitas (Lemma 3.1) diperoleh jika
, maka
. Oleh karena itu, . Karena itu
adalah
penyelesaian optimum untuk masalah dual.
Langkah 2: Menambahkan variabel pengetat Berdasarkan Teorema 3.4 masalah program linear asli dapat diselesaikan jika dan hanya jika dapat ditemukan suatu pasangan
sehingga
memenuhi relasi dari himpunan pada persamaan (3.18). Selanjutnya dapat diberikan variabel pengetat u dan surplus v, untuk mendapatkan himpunan relasi yang ekuivalen berikut:
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
85
(3.19)
Langkah 3: Bentuk variabel semu untuk mendapatkan titik interior awal. Misalkan yang memenuhi
, ,
memilih
, ,
, dan , dan
adalah titik-titik . Sebagai contoh, dapat
dan demikian juga dengan
, dan
.
Pertimbangkan masalah program linear berikut yang disebut sebagai masalah Karmarkar semu Minimumkan Dengan kendala (3.20)
Perhatikan bahwa titik berikut adalah suatu titik interior tegas untuk masalah (3.20) di atas.
(3.21)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
86
Selanjutnya nilai minimum dari fungsi sasaran untuk masalah Karmarkar semu adalah nol jika dan hanya jika himpunan relasi sebelumnya pada persamaan (3.19) memiliki penyelesaian yakni ada
yang
memenuhi. Oleh karena itu, masalah program linear Karmarkar semu ekuivalen ke masalah program linear asli pada persamaan (3.16). Perbedaan utama antara masalah program linear asli di atas dan masalah Karmarkar semu adalah bahwa terdapat titik layak interior tegas yang eksplisit untuk masalah Karmarkar semu, sehingga harus dipenuhi asumsi yang telah ditentukan pada bab awal (asumsi-asumsi dalam masalah Karmarkar).
Langkah 4: Mengubah notasi Untuk mempermuda deskripsi dengan menulis ulang masalah (3.20) di atas dapat diwakili dalam notasi matriks berikut Minimumkan Dengan kendala
dimana
(3.22)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
87
(3.23)
Langkah 5: Menentukan transformasi proyektif dari ortan positif ke simpleks Pertama akan ditunjukkan sebuah cara sederhana untuk mengubah masalah di atas ke dalam bentuk kanonik Karmarkar, dengan mengabaikan syarat untuk memenuhi asumsi a dari asumsi-asumsi dalam masalah Karmarkar. Untuk ini, definisikan sebuah variabel baru .
Juga
definisikan
dan
dengan .
Dengan
menggunakan notasi ini masalah program linear pada persamaan (3.22) dapat ditulis ulang menjadi
Minimumkan Dengan kendala
,
(3.24)
Diperlukan satu langkah lagi untuk mengubah masalah tersebut ke dalam bentuk yang memuat kendala yang jumlah variabel keputusannya adalah 1. Untuk ini, misalkan
, dimana
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
88
Transformasi dari x ke y ini disebut transformasi proyeksi. Hal ini dapat ditunjukkan bahwa
Oleh karena itu, masalah program linear yang diberikan dalam bentuk standar telah ditransformasikan kemasalah di bawah ini, yakni dalam bentuk kanonik Karmarkar:
Minimumkan
,
Dengan kendala
,
Teknik transformasi di atas dapat diubah sedikit untuk menjamin bahwa asumsi a dipenuhi. Pertama dengan menganggap bahwa diberikan suatu titik yang merupakan titik layak interior tegas, yaitu
, dan
. Akan ditunjukkan bagaimana asumsi tersebut dapat dipenuhi. Misalkan merupakan positive orthant dari
, yakni
menjadi simpleks di pemetaan
dengan
. Misalkan . Definisikan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
89
dimana
Pemetakaan T disebut transformasi proyeksi dari positive orthant kedalam simpleks . Transformasi T memiliki beberapa sifat menarik. Secara khusus, dapat ditemukan vektor sehingga untuk setiap
dan matriks
,
Perhatikan bahwa untuk setiap
, mempunyai
, selain itu
. Selanjutnya, perhatikan bahwa untuk setiap
Sebagai aplikasi dari teorema yang sudah dibahas di atas, pertimbangkan masalah program linear berikut :
Minimumkan Dengan kendala
,
(3.25)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
90
y Perhatikan bahwa masalah program linear pada persamaan (3.25) adalah dalam bentuk kanonik Karmarkar. Selanjutnya dalam definisi
dan
, masalah
program linear di atas ekuivalen dengan masalah asli dalam bentuk standar. Dengan demikian, masalah program linear dalam bentuk standar telah diubah ke masalah ekuivalen dalam bentuk kanonik Karmarkar. Selain itu, karena a adalah titik layak interior tegas, dan
adalah pusat dari simpleks , maka titik
adalah titik layak dari masalah yang ditransformasikan, oleh karena itu asumsi a dari asumsi-asumsi dalam masalah program linear dipenuhi untuk masalah program linear di atas.
Berdasarkan uraian di atas maka mengubah masalah program linear bentuk standar ke bentuk kanonik Karmarkar dapat dirangkum mengikuti langkahlangkah berikut: Pertimbangkan masalah program linear berikut dalam bentuk standar: Minimumkan Dengan kendala
,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
91
Masalah dual dari bentuk standar adalah Maksimumkan Dengan kendala
,
Berikut ini adalah langkah-langkah untuk menjelaskan bagaimana mengubah masalah program linear umum ke dalam bentuk kanonik Karmarkar. 1. Kombinasikan masalah primal dan dual.
2. Menambahkan variabel pengetat
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
3. Bentuk variabel semu
92
untuk mendapatkan titik interior awal.
Minimumkan Dengan kendala
4. Mengubah notasi. Minimumkan Dengan kendala
dimana
5. Menentukan transformasi proyektif dari ortan positif ke simpleks. a.
Tentukan titik
b.
Dengan menggunakan masalah program linear pada langkah 4 dapat di tulis ulang menjadi
yang memenuhi
, dan
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Minimumkan
,
dengan kendala
,
93
dengan
Berikut ini adalah contoh untuk menunjukkan bagaimana mengubah masalah program linear umum ke dalam bentuk kanonik Karmarkar. Contoh 3.2: Pertimbangkan masalah program linear berikut dalam bentuk standar: Minimumkan dengan kendala
Ubahlah masalah program linear diatas ke dalam bentuk kanonik Karmarkar.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Penyelesaian
Minimumkan
dengan kendala
Bentuk dual dari masalah Program Linear diatas adalah:
Maksimumkan
dengan kendala
Langkah 1: Kombinasikan masalah primal dan dual
94
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Langkah 2: Menambah variabel pengetat
dan
95
, sehingga
diperoleh sistem
Langkah 3: Bentuk variabel semu z untuk mendapatkan titik interior awal yang memenuhi Minimumkan
dengan kendala
z
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
atau dapat ditulis Minimumkan
z
dengan kendala
Langkah 4: Mengubah notasi Minimumkan dengan kendala
96
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
97
dimana
Langkah 5: Menentukan
transformasi proyektif dari ortan positif ke
simpleks Langkah pertama dengan mencari suatu titik dan
, dimana
yang memenuhi
seperti pada langkah 4. Dengan melakukan
operasi baris elementer pada matriks
sampai memperoleh bentuk eselon
baris, dan dengan mengambil nilai random
maka diperoleh akan .
Selanjutnya seperti yang telah dibuktikan pada Teorema 3.2 dan Teorema 3.3 dapat ditemukan vektor
dan matriks
dimana
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
98
Sehingga diperoleh bentuk kanonik Karmarkar
Minimumkan
,
dengan kendala
,
dengan
E. Algoritma Karmarkar Pada bagian ini akan dibahas algoritma Karmarkar, dengan mengingat bahwa masalah program linear yang akan diselesaikan adalah masalah Karmarkar yang terbatas, yaitu masalah dari bentuk kanonik Karmarkar yang memenuhi asumsi-asumsi dalam masalah Karmarkar. Perhatikan kembali masalah Karmarkar berikut
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
99
Minimumkan dengan kendala dengan
, dan
.
Algoritma Karmarkar adalah algoritma iteratif, yakni diberikan titik awal dan diberikan parameter penghentian , maka akan menghasilkan urutan , yang memenuhi Untuk menentukan
.
, digunakan persamaan (3.26)
dengan
adalah besar langkah sedemikian sehingga nilai
pada daerah layak dan sasaran. Besar langkah
tetap berada
adalah arah layak yang memperbaiki nilai fungsi yang dipilih memenuhi
aslinya Karmarkar merekomendasikan nilai yang memperbaiki nilai fungsi sasaran
. Dalam tulisan . Sedangkan arah layak
dipilih sebagai berikut. Pertama
perhatikan bahwa gradien fungsi objektif adalah c. Oleh karena itu, arah tingkat penurunan maksimum fungsi tujuan adalah –c. Akan tetapi, secara umum arah tersebut tidak dapat digunakan, karena
haruslah terletak di
himpunan kendala
(3.27)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
dimana
100
didefinisikan dengan
Teorema 3.5 Misalkan
, dan
dan
adalah titik interior tegas dari
. Misalkan A memenuhi
, dan D adalah matriks
diagonal yang entri-entri diagonalnya merupakan komponen dari matriks B didefinisikan sebagai
maka
, dan oleh karena itu
Bukti:
Misalkan
dan A memenuhi
Akan dibuktikan
i.
memenuhi
adalah nonsingular.
. Jika
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
ii.
101
adalah nonsingular.
Jika
adalah matriks
yang memenuhi
bentuk eselon baris
dari
, maka
akan memiliki
utama. Untuk membuktikan matriks , cukup membuktikan
banyaknya 1 memenuhi
adalah matriks
. Dimana
adalah matriks diagonal yang entri-entri diagonalnya merupakan komponen dari
, dan
adalah titik interior tegas dari
dengan tegas dari
. Karena , maka
memenuhi
Misal
memenuhi
adalah titik interior
. Sehingga elemen-elemen pada D tidak
akan bernilai nol. Dengan demikian matriks
,
adalah matriks
dan
.
, akan dibuktikan
adalah nonsingular. Berdasarkan Teorema 2.15 diatas untuk menunjukan nonsingular dengan menunjukkan
. Seperti yang
diperlihatkan dalam Teorema 2.7 dan Teorema 2.9 , maka
adalah
adalah nonsingular.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Perhatikan karena
, yakni
yang juga terletak pada
102
, maka untuk yakni memenuhi,
maka diperoleh
atau
Dengan demikian dari
, maka vektor
. Oleh karena itu, dipilih
dari -c pada ruang nol dari
haruslah elemen ruang nol
yang merupakan arah proyeksi ortogonal
. Proyeksi ini dilakukan oleh matriks
yang
didefinisikan dengan
Perhatikan bahwa
adalah nonsingular dari asumsi c.
Dalam suatu jurnal A New Polynomial-Time Algorithm For Linear Programming (Karmarkar, 1984) menguraikan bahwa jari bola terbesar dalam simpleks
. Oleh karena itu, vektor
adalah jari,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
dengan dari
menunjuk pada arah proyeksi
dari
103
pada ruang nol
.
Untuk iterasi selanjutnya, fungsi
, yakni
. Ide dasar pembaharuan tersebut mirip
dengan pembaruan dari perlu diketahui bahwa
diperbaharui dengan menggunakan
ke
yang telah dijelaskan di atas. Namun,
, secara umum bukan di pusat simpleks. Oleh
karena itu, titik tersebut haruslah ditransformasi ke pusat. Untuk melakukan hal ini, memisalkan
adalah matriks diagonal yang entri-entri diagonalnya
adalah komponen dari vektor
Karena
sehingga
adalah titik interior tegas dari , dan
adalah titik interior tegas dari
interior tegas dari karena itu,
, yaitu
untuk setiap k, yakni
adalah nonsingular, dan
, selanjutnya
adalah titik . Oleh
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Pertimbangkan pemetaan . Perhatikan bahwa
dengan
didefinisikan sebagai
104
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Akan digunakan ini dilakukan sehingga
untuk mengubah variabel x ke
. Langkah
dipetakan ke pusat dari simpleks, seperti yang
diperlihatkan di atas. Perhatikan bahwa diinverskan, dimana
105
adalah pemetaan yang dapat
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Misalkan
106
, maka dengan menerapkan prosedur yang
sudah dijelaskan sebelumnya untuk mendapatkan khusus,
dari
diperbaharui untuk memperoleh
pembaruan
menggunakan rumus
. Untuk menghitung
linear awal perlu dinyatakan dalam variabel
. Secara
, masalah program
yang baru:
Minimumkan Dengan kendala
,
(3.28)
Teorema 3.6 Misalkan diagonal
adalah titik interior tegas dari
, dan
adalah matriks
yang entri-entri diagonalnya merupakan komponen dari
Didefinisikan pemetaan
dengan
.
. Misalkan
menunjukkan perubahan dari variabel. Maka masalah program linear tertransformasi berikut dalam variabel Minimumkan Dengan kendala
,
adalah ekuivalen terhadap masalah program linear
(3.29)
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
107
Meminimumkan Dengan kendala
yakni
(3.30)
adalah penyelesaian optimal dari masalah (3.30) jika dan hanya jika adalah penyelesaian optimal untuk masalah (3.29).
Bukti: Misalkan
adalah titik interior tegas dari dan
adalah matriks diagonal
diagonalnya merupakan komponen dari Akan dibuktikan
, yakni yang entri-entri
.
adalah penyelesaian optimal dari masalah (3.30)
adalah penyelesaian optimal untuk masalah (3.29).
Misalkan
yakni
adalah penyelesaian optimal dari masalah (3.30),
meminimumkan
Akan dibuktikan
dan memenuhi
.
adalah penyelesaian optimal untuk
masalah (3.29), yakni memenuhi
dan
dan
meminimumkan .
dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
i.
memenuhi
akan ditunjukkan
108
memenuhi
. Karena
Karena
ii.
memenuhi
maka
maka
akan ditunjukkan
Diketahui
memenuhi
maka
adalah matriks diagonal yang entri-entri diagonalnya merupakan komponen dari
, maka
sehingga
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena
iii.
, maka
meminimumkan meminimumkan
109
akan
dibuktikan
.
Berdasarkan asumsi b dari asumsi-asumsi dalam masalah Karmarkar, jika
meminimumkan
Maka nilai minimum dari
, maka nilai minimum dari
.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena
110
maka diperoleh
adalah penyelesaian optimum untuk masalah (3.30) . adalah penyelesaian optimum untuk masalah (3.29)
Misalkan
adalah penyelesaian optimal dari masalah (3.29),
yakni
meminimumkan
dan
. Akan dibuktikan
masalah (3.30), yakni dan
dan memenuhi adalah penyelesaian optimal untuk
meminimumkan
dan memenuhi
.
i.
memenuhi memenuhi
. Karena
akan
ditunjukkan maka
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena
ii.
111
, maka
memenuhi
akan ditunjukkan
memenuhi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena
iii.
, maka
meminimumkan meminimumkan Karena
akan
.
meminimumkan
maka
dibuktikan
112
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Karena
113
, maka
. adalah penyelesaian optimum untuk masalah (3.29) adalah penyelesaian optimum untuk masalah (3.30). adalah
penyelesaian
meminimumkan
optimal
dan memenuhi
dari
masalah
(3.30),
dan
.
adalah penyelesaian optimal untuk masalah (3.29), yakni meminimumkan
dan memenuhi
dan
.
yakni
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
114
Dapat ditunjukkan bahwa masalah program linear di atas dalam variabel yang baru ekuivalen dengan masalah program linear dalam bentuk standar dalam arti bahwa
adalah penyelesaian optimal untuk masalah dalam bentuk
standar jika dan hanya jika
adalah penyelesaian optimal dari masalah
yang sudah ditransformasikan. Untuk melihat ini, perhatikan bahwa , dan fungsi tujuan serta kendala dapat ditulis kembali sebagai berikut. Perhatikan bahwa
Pilih
, dimana pada ruang nol dari
adalah proyeksi normal dari , dan
definisikan matriks proyeksi ortogonal
Perhatikan bahwa
dengan
adalah nonsingular. Oleh karena itu, vektor
diberikan
Maka vektor arah
. Untuk menentukan
dapat diperoleh
,
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Vektor
115
, dijamin terletak pada daerah layak yang sudah
ditransformasikan
. Langkah terakhir adalah menerapkan
transformasi invers
untuk memperoleh
Perhatikan memetakan
terletak di himpunan
, yakni
. Dapat dilihat bahwa
dan
kedalam .
Dari uraian di atas maka algoritma Karmarkar dirangkum mengikuti langkah-langkah berikut: 1. Langkah awal: Tetapkan 2. Memperbaruhi:
Tetapkan
,
. ,
dimana
adalah
pembaruan pemetaan yang ditentukan melalui langkah-langkah berikut ini: 1. Hitunglah matriks:
2. Hitunglah proyeksi ortogonal pada ruang nol dari
:
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
116
3. Hitunglah proyeksi ortogonal ternormalisasi dari c pada ruang nol dari
:
4. Hitunglah vektor arah:
5. Hitunglah
dimana
menggunakan:
adalah ukuran langkah,
6. Hitunglah
.
dengan menerapkan transformasi invers
3. Periksa kriteria penghentian: Jika kondisi iterasi berhenti. Jika tidak, tetapkan
:
dipenuhi, maka , kembali ke langkah 2.
Berikut ini adalah contoh untuk menunjukkan bagaimana menyelesaikan masalah program linear dalam bentuk kanonik dengan menggunakan Algoritma Karmarkar. Contoh 3.3 Pertimbangkan masalah program linear berikut ini, yang sudah berada dalam bentuk kanonik Karmarkar. Minimumkan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
117
dengan kendala
Iterasi 0 Tetapkan
Iterasi 1 Akan ditentukan
dengan
langkah berikut. i.
Menghitung matriks
ii.
Menghitung proyeksi ortogonal pada ruang nol dari
diperoleh dengan langkah-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
118
iii.
Menghitung proyeksi ortogonal ternormalisasi dari c pada ruang nol dari
iv.
Menghitung vektor arah
v.
Menghitung
dengan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
vi.
Menghitung
dengan menerapkan transformasi invers
,
Karena
maka
119
:
iterasi
dilanjutkan. Tetapkan k=1.
Iterasi 2 Akan ditentukan langkah berikut.
dengan
diperoleh dengan langkah-
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
120
i.
Menghitung matriks
ii.
Menghitung proyeksi ortogonal pada ruang nol dari
iii.
Menghitung proyeksi ortogonal ternormalisasi dari c pada ruang nol dari
iv.
Menghitung vektor arah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
v.
Menghitung
dengan
vi.
Menghitung
dengan menerapkan transformasi invers
Karena
dilanjutkan. Tetapkan k=2.
Iterasi 3
,
maka
121
:
iterasi
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Akan ditentukan
dengan
122
diperoleh dengan langkah-
langkah berikut. i.
Menghitung matriks
ii.
Menghitung proyeksi ortogonal pada ruang nol dari
iii.
Menghitung proyeksi ortogonal ternormalisasi dari c pada ruang nol dari
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
iv.
Menghitung vektor arah
v.
Menghitung
dengan
vi.
Menghitung
dengan menerapkan transformasi invers
:
123
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
124
, maka iterasi dilanjutkan.
Karena
Untuk memenuhi
titik optimumnya, yakni
akan dibutuhkan 24 iterasi dan diperoleh
.
F. Aplikasi Metode Karmarkar untuk Menyelesaikan Masalah Program Linear dengan Program MATLAB Contoh 3.4 Pertimbangkan masalah program linear berikut ini, yang sudah berada dalam bentuk kanonik Karmarkar. Minimumkan dengan kendala
dengan
,dan
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Contoh 3.5: Pertimbangkan masalah program linear berikut dalam bentuk standar: Minimumkan dengan kendala
dengan
,
, dan
125
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
Output Bentuk kanonik Karmarkar untuk masalah program linear di atas adalah Minimumkan Dengan kendala Dengan
dan
seperti yang diperlihatkan di bawah
126
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
127
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
BAB IV PENUTUP
A. Kesimpulan Berdasarkan pembahasan yang telah di uraikan sebelumnya dapat di ambil kesimpulan bahwa masalah program linear dapat diselesaikan dengan mengunakan metode titik-interior yang salah satunya adalah metode Karmarkar. Suatu masalah program linear dalam bentuk standar untuk dapat diselesaikan dengan algoritma Karmarkar harus di ubah dahulu ke dalam bentuk kanonik Karmarkar. Masalah program linear dalam bentuk standar meminimumkan dapat diubah ke dalam bentuk kanonik Karmarkar dengan menggunakan transformasi proyektif, yaitu dengan mengubah program linear standar ke bentuk kanonik Karmarkar. Ide dasar metode Karmarkar, yaitu dimulai dengan memilih titikinterior awal di dalam ruang penyelesaian. Gradien fungsi tujuan di titikinterior awal adalah arah yang membuat fungsi tujuan meningkat dengan cepat. Jika satu titik sembarang ditempatkan di sepanjang gradien itu dan lalu memproyeksikannya secara tegak lurus terhadap ruang penyelesaian, maka hasil transformasi titik-interior yang dipilih diposisikan lebih dekat dengan titik optimum. Hasil transformasi titik-interior yang dipilih dijalankan ke suatu titik-interior lain dengan arah layak dan besar langkah
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
129
yang sesuai. Proses iterasi ini diulang hingga nilai fungsi sasaran sama dengan nol. B. Saran Menyelesaikan masalah program linear dengan menggunakan metode Karmarkar dalam skripsi ini hanya bisa digunakan untuk meminimumkan nilai fungsi sasaran dengan menggunakan kendala lebih besar sama dengan saja. Bagi pembaca yang tertarik untuk menyelesaikan masalah program linear dengan metode titik-interior salah satu pilihannya dapat melanjutkan skripsi ini dengan menggunakan kendala campuran. Selain melanjutan skripsi ini, untuk menyelesaikan masalah program linear dengan metode titik-interior dapat juga digunakan misalnya affine scaling methods, path-following methods, dan potential-reduction methods.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
130
DAFTAR PUSTAKA Anton, H. (1981). Aljabar Linear Elementer. Jakarta: Erlangga. Chong, E. K.P. dan Zak, S. H. (1996). An Introduction To Optimazation. Newyork: John Wiley & Sons Inc. Karmarkar, N. (1984). A New Polynomial-Time Algorithm For Linear Programming. Combinatorica. 4(4): 373-395. Kurtz, D. (1992). Foundations of Abstract Mathematics. New York: McGrawHill. Leon, S. J. (1998). Aljabar Linear dan Aplikasinya. Jakarta: Erlangga. Mirsky, L. (1955). An Introduction To Linear Algebra. London: Oxford University Press Nasendi, B. D. dan Anwar, A. (1985). Program Linear dan Variasinya. Jakarta: Gramedia. Nash, S. G. and Sofer, A. (1996). Linear and Nonlinear Programming. New York: McGraw-Hill. Retnojiwati, A. (2007). Metode Primal Affine-skaling untuk Masalah Program Linear (Skripsi). Yogyakarta: Fakultas MIPA USD. Taha, H. A. (1996). Riset Operasi. Suatu Pengantar. Jakarta: Bina Rupa Aksara. Winston, W. N. and Venkataramanan, M. (2003). Introduction to Mathematical Programming. London: Thomson Learning.
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
131
LAMPIRAN 1 Listing Program %Program menyelesaikan masalah program linear dengan metode Karmarkar %Fungsi YB0 menampilkan Program menyelesaikan masalah PL dalam bentuk baku masalah minimum %Fungsi YB1 menampilkan Program menyelesaikan masalah PL dalam bentukkanonik Karmarkar clc;clear all;close all; YB0='masukkan 0 untuk PL dalam bentuk baku masalah minimum'; YB1='masukkan 1 untuk PL dalam bentuk kanonik Karmarkar'; disp(YB0) disp(YB1) YB=input('masukkan pilihan '); tic if YB==1 Kanonik_Karmarkar elseif YB==0 Minimum_standar else YB='input yang anda masukkan salah'; disp(YB) end toc
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
132
LAMPIRAN 2 Listing Program Masalah Program linear dalam bentuk Kanonik Karmarkar %Program menyelesaikan masalah program linear dengan metode Karmarkar %Masalah program linear dalam bentuk Kanonik Karmarkar clear all;close all; 'Menyelesaikan masalah program linear dalam bentuk kanonik Karmarkar dengan algoritma Karmarkar' n=input('masukkan banyak variabel '); c=input('masukkan koefisien ongkos c= ')'; A=input('masukkan koefisien teknis A= '); x=((ones(1,n))*(1/n))'; e=(ones(1,n)); I=diag(e); r=1/(sqrt(n*(n-1))); alpa=(1/4); a=x; Q=0.00000001; salah=1; A_baru=[A;e]; p=A_baru(:,1); w=length(p); R=rank(A_baru); iterasi=0; if w==R while salah>=Q iterasi=iterasi+1; D=diag(x); AD=A*D; B=[AD;e]; P=I-B'*(inv(B*B'))*B; pdc=(P*(D*c)); ck=pdc/(norm(pdc)); dk=-r*ck; x_bar=(a)+(alpa*dk); x_baru=(D*(x_bar))/(e*D*(x_bar)); x=x_baru; salah=(c'*x_baru)/(c'*a); end iterasi=iterasi; 'Jadi diperoleh titik optimumnya, yakni' x else 'Asumsi c tidak dipenuhi dan matriks A tidak mempunyai invers' 'Tidak dapat diselesaikan dengan algoritma Karmarkar' end
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
133
LAMPIRAN 3 Listing Program Masalah Program linear dalam bentuk standar meminimumkan
%Program menyelesaikan masalah program linear dengan Karmarkar %Masalah program linear dalam bentuk baku meminimumkan clc;clear all;close all; warning('off');
metode
'Menyelesaikan masalah program linear dalam bentuk standar dengan mengunakan algoritma Karmarkar' N=input('masukkan banyak variabel '); M=input('masukkan banyak kendala '); c_awal=input('masukkan koefisien ongkos c= ')'; A_awal=input('masukkan koefisien teknis A= '); b_awal=input('masukkan suku tetap di ruas kanan b= ')'; n=(((N+M)*2)+1); baris=(N+M+1); c_tilda=[(zeros(((N+M)*2),1));1]; a1=[(c_awal)' (-(b_awal))' (zeros(1,N)) (zeros(1,M)) (((c_awal)'*(ones(N,1)))+((b_awal)'*(ones(M,1))))]; a2=[A_awal (zeros(M,M)) (zeros(M,N)) (-(diag(ones(1,M)))) ((b_awal)-((A_awal)*(ones(N,1)))+(ones(M,1)))]; a3=[(zeros(N,N)) (A_awal)' (diag(ones(1,N))) (zeros(N,M)) ((c_awal)-((A_awal)'*(ones(M,1))))]; A_tilda=[a1;a2;a3]; b_tilda=[0 (b_awal)' (c_awal)']'; A_baru=[A_tilda b_tilda]; r_ref=rref(A_baru); R=rank(r_ref); a_rand=rand(n-R,1); matrix=r_ref(:,n+1); matrix2=r_ref(:,n+1); col=1; col2=1; vektor=[]; for index1=1:n jml0=0; jml1=0; for index2=1:baris if r_ref(index2,index1)==0
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
jml0=jml0+1; end if r_ref(index2,index1)==1 jml1=jml1+1; end end if (jml0+jml1)==baris && jml1==1 isexist=0; for i=1:col if matrix(:,i)==r_ref(:,index1) isexist=1; end end if isexist == 0 matrix=[matrix r_ref(:,index1)]; vektor=[vektor index1]; col=col+1; else matrix2=[matrix2 r_ref(:,index1)]; col2=col2+1; end else matrix2=[matrix2 r_ref(:,index1)]; col2=col2+1; end end matrix2=matrix2(:,2:col2); matrix=[matrix(:,2:col) matrix(:,1)]; Abaru=[matrix(:,1:col-1) matrix(:,col)-(matrix2*a_rand)]; A=Abaru(:,R+1); z=A'; iterasi=0; tol=zeros(R,1); f=false; for index=1:length(z) if z(:,index)<=0; f=true; end end while f iterasi=iterasi+1; a_rand=rand(n-R,1); Abaru2=[matrix(:,1:col-1) matrix(:,col)-(matrix2*a_rand)]; A=Abaru2(:,R+1); g=0; z=A'; for index=1:length(z) if z(:,index)>0 g=g+1; end end
134
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
if g==length(z) f=false; end end a_rand; A1=A'; aa_rand=(a_rand)'; a_baru=[]; vektor; index_rand=1; for i=1:n exist=0; in=0; for a=1:R if i==vektor(:,a) vektor(:,a); in=a; exist=1; end end if exist==1 exist; a_baru=[a_baru A1(:,in)]; else a_baru=[a_baru aa_rand(:,index_rand)]; index_rand=index_rand+1; end end a_baru; c2=(c_tilda)'; for index=1:length(a_baru) A2(:,index)=A_tilda(:,index)*a_baru(:,index); c3(:,index)=c2(:,index)*a_baru(:,index); end A2; c3; 'dimana' c_aksen=[c3 0] A_aksen=[A2 -(b_tilda)] N_baru=n+1; x=((ones(1,N_baru))*(1/N_baru))'; e=(ones(1,N_baru)); I=diag(e); r=1/(sqrt(N_baru*(N_baru-1))); alpa=(1/4); a=x; Q=(10^(-4)); salah=1; i=0; c=(c_aksen)';
135
PLAGIAT PLAGIATMERUPAKAN MERUPAKANTINDAKAN TINDAKANTIDAK TIDAKTERPUJI TERPUJI
136
AA=[A_aksen;e]; p=AA(:,1); w=length(p); R=rank(AA); if w==R while salah>=Q i=i+1; D=diag(x); AD=A_aksen*D; B=[AD;e]; P=I-(B'*(inv(B*B'))*B); pdc=(P*(D*c)); ck=pdc/(norm(pdc)); dk=-r*ck; x_bar=(a)+(alpa*dk); x_baru=(D*(x_bar))/(e*D*(x_bar)); salah=(c'*x_baru); x=x_baru; end i=i 'Jadi penyelesaian untuk masalah program linear dalam bentuk kanonik Karmarkar, yakni' x x_barr=x'; z_solusi=c'*x for indeks=1:N y(:,indeks)=((a_baru(:,indeks))*(x_barr(:,indeks)))/x_barr(:,N_bar u); end 'Jadi penyelesaian untuk masalah program linear dalam bentuk standar adalah' y_solusi=y 'Dengan nilai fungsi sasaran adalah' solusi=(y_solusi)*c_awal else 'Asumsi c tidak dipenuhi dan matriks A tidak mempunyai invers' 'Tidak dapat diselesaikan dengan algoritma Karmarkar' end