METODE PRIMAL AFFINE-SKALING UNTUK MASALAH PROGRAM LINEAR

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

METODE PRIMAL AFFINE-SKALING UNTUK MASALAH PROGRAM LINEAR Skripsi

Diajukan untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains Program Studi Matematika

Oleh: Ajeng Retnojiwati NIM : 013114013

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SANATA DHARMA YOGYAKARTA 2007

i


ii


iii


HALAMAN PERSEMBAHAN

“Dan apa saja yang kamu minta dalam doa dengan penuh kepercayaan, kamu akan menerimanya.” (Matius 21:22)

Terimakasih Tuhan Yesus

Engkau bantu aku melewati satu pergumulan lagi dalam hidup

Kupersembahkan karya ini untuk: Tuhan Yesus dan Bunda Maria Bapak, Ibu, Mas Purwiyadi, Mas Sugeng, simbah dan keluargaku

iv


v


ABSTRAK

Untuk menyelesaikan masalah program linear, selain dengan metode grafik atau metode simpleks dapat juga diselesaikan dengan metode titik-dalam. Salah satu kelas dalam metode titik-dalam adalah metode primal affine-skaling. Untuk menentukan penyelesaian masalah program linear dengan metode primal affineskaling dimulai dengan memilih titik-dalam awal, yaitu x k dari suatu daerah layak di ruang penyelesaian awal. Kemudian x k ditransformasi oleh transformasi affineskaling, yaitu Tk sedemikian sehingga hasil transformasi x k diposisikan dekat dengan pusat di ruang penyelesaian hasil transformasi ini. Hasil transformasi x k sebut saja y k . Langkah selanjutnya, dari y k dijalankan ke titik-dalam lain, yaitu y k +1 yang menggerakkan nilai f sampai f optimum dicapai sesuai dengan alur iterasi

y k +1 = y k + α k d ky , dengan d ky adalah arah layak turun tercuram (steepest

descent) yang menyebabkan nilai fungsi berkurang dengan cepat. Dan α k adalah besarnya langkah yang menyatakan seberapa jauh arah tersebut akan menuju ke titik optimum yang tetap berada pada daerah layak. Penyelesaian yang didapat di ruang penyelesaian tersebut ditransformasikan kembali dengan transformasi invers, yaitu Tk−1 . Proses iterasi ini diulang hingga penyelesaian optimum dicapai.

vi


ABSTRACT

Linear programming problems not only can be solved with graphic method or simplex method, but also it can be solved with interior-point method. One of the classes of the interior-point method is primal affine-scaling method. To find the solution of linear programming using primal affine-scaling method, we should start by selecting the interior-point solution , namely x k from inside feasible region in original solution space. Then, x k is transformed with an affine-scaling transformation, which is called Tk , so that the selected interior-point solution is placed near the transformed feasible region. The image of x k called y k . Then, from y k we move to another interior-point y k +1 , which improves the value of objective function f , in accordance to the iteration y k +1 = y k + α k d ky . Here, d ky is the direction of steepest descent that causes the fastest rate of decrease in the objective function. While α k is the step-length which gives how far the direction can move to the optimum point but it still remains in the feasible region. The solution, which is found in the solution space, is transformed back with inverse transformation, −1 called Tk . This process will be repeated until we obtain an optimum solution with the desired accuracy.

vii


KATA PENGANTAR

Puji syukur penulis panjatkan kepada Tuhan Yesus 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, Jurusan Matematika, Fakultas Matematika dan Ilmu Alam, 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. Ibu Lusia Krismiyati, S.Si, M.Si sebagai dosen pembimbing yang penuh perhatian dan kesabaran telah membimbing serta memberi saran dan kritik kepada penulis selama proses penulisan skripsi ini. 2. Bapak Y.G. Hartono, S.Si, M.Sc sebagai dosen pembimbing dan selaku Ketua Program Studi Matematika, dosen pembimbing akademik dan dosen penguji yang telah memberikan dukungan, saran dan kritik dalam skripsi ini. 3. Bapak Ir. Ig. Aris Dwiatmoko, M.Sc selaku Dekan fakultas MIPA yang telah memberi dukungan dalm penulisan skripsi ini. 4. Ibu Any Herawati, S.Si, M.Si selaku dosen penguji yang telah memberikan saran dan kritik dalam skripsi ini. 5. Bapak dan Ibu dosen di Fakultas MIPA yang telah membimbing dan mendidik penulis selama menuntut ilmu di Universitas Sanata Dharma.

viii


6. Bapak dan Ibu karyawan Universitas Sanata Dharma, khususnya sekretariat fakultas MIPA dan perpustakaan Universitas Sanata Dharma atas segala bantuan dan fasilitas yang telah diberikan. 7. Sahabat-sahabatku seperjuangan angkatan 2001: Very, Upik, Yuli, Dani, Tabita, Fanya, Andre, Indah, Ariel, Agnes, Erika, Wiwit, Deta, Maria, Rita, Alam, Vrysca, Daniel, Tedy, Ray, April, Ardi, serta kakak-kakak angkatan 1998, 1999, 2000 dan adik-adik angkatan 2002, 2003, 2004 yang telah membantu dan mendukung penulis. 8. Dhe-dhe dan keluarga yang telah memberi dukungan, semangat dan doanya. 9. Tien, Mei, Bayu, Helbin, Sinta, Heni, Henri, Mbak uci dan keluarga, mbak Novi, Murni, Rini ikom, teman-teman Gloria Graha dan temen-temen radio masdha, yang telah memberi dukungan, semangat dan doanya. 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, 7 Februari 2007

Penulis

ix


DAFTAR ISI

Halaman HALAMAN JUDUL …………………………………………….…………..….

i

HALAMAN PERSETUJUAN PEMBIMBING …………….…………………..

ii

HALAMAN PENGESAHAN …………………………………………………..

iii

HALAMAN PERSEMBAHAN ……………………………………….…..……

iv

PERNYATAAN KEASLIAN KARYA ……………………….…………….….

v

ABSTRAK ……………………………………………….………………….…..

vi

ABSTRACT ………………………………………………….………………....

vii

KATA PENGANTAR …………………………………….……………….……

viii

DAFTAR ISI ……………………………………………………….……….…..

x

DAFTAR GAMBAR ………………………………………………………..…

xiii

TABEL …………………………………………………………………………

xiii

BAB I

PENDAHULUAN ……………………………………………..…...

1

A. Latar Belakang Masalah …………………………………….….

1

B. Rumusan Masalah …………………………………….…...……

3

C. Pembatasan Masalah …………………………….…………...….

4

D. Tujuan Penulisan …………………………………………….…..

4

E. Manfaat Penulisan …….................................................................

4

F. Metode Penulisan ……………………………..…………..……..

5

G. Sistematika Penulisan ……………………….…………………..

5

x


BAB II

ORTOGONALITAS DAN OPTIMISASI UNTUK PERSOALAN LINEAR …………………………………………………………….

6

A. Sistem Persamaan Linear Dan Matriks ……………...………….

6

B. Ruang Vektor ………………………………………..……….…

10

1. Ruang Vektor ……………..…..…………………..………...

10

2. Hasil Kali Dalam Dan Ortogonalitas ….................................

22

3. Transformasi Linear ……………………………….………… 31

BAB III

C. Masalah Program Linear …………………………………...…. .

32

1. Bentuk Standar Masalah Program Linear …………………..

32

2. Dualitas ……………………………………………………. .

37

D. Optimisasi Fungsi Untuk Persoalan Linear ………………..……

40

1. Optimisasi …………………………………………………..

40

2. Kelayakan ……………………………………………...…....

41

E. Metode Arah Layak ………………………………………...…...

42

F. Metode Arah Turun Tercuram (Steepest Descent) ………….....

44

METODE PRIMAL AFFINE-SKALING ……………………..….

45

A. Metode Primal Affine-Skaling …………………………..…….

46

1. Transformasi Affine-Skaling ……………………………....

49

2. Menentukan Arah Layak ………………………………..…

61

a. Bentuk Masalah Program Linear di Ruang Penyelesaian Hasil Transformasi ……………………………………………….

61

b. Menentukan Arah Layak ……………………………..……

66

xi


c. Perumusan Arah Langkah Dengan Arah Turun Tercuram .....

70

3. Menentukan Besar Langkah α k ……………..………...……

74

B. Algoritma Primal Affine-Skaling ………………………...…..…

83

C. Aplikasi Metode Primal Affine-Skaling Untuk Menyelesaikan

BAB IV

Masalah Program Linear Dengan Program Matlab ……….....…

87

PENUTUP ...................................................................................…..

99

A. Kesimpulan ……………....................................................……..

99

B. Saran ………………………………………………………...…

100

DAFTAR PUSTAKA ………………………………………………………….

101

LAMPIRAN …………………………………………………………………..

102

xii


DAFTAR GAMBAR

Halaman Gambar 1.1 Metode titik-dalam vs metode simpleks …………………………..

2

Gambar 2.1 c = x + y ……………………………………………………….….

28

Gambar 3.1 Ide transformasi affine-skaling ………………….…………...……

50

Gambar 3.2 Titik-dalam x k ditransformasikan oleh Tk ke posisi e ……….....

54

Gambar 3.3 Sifat-sifat dari transformasi affine-skaling ……………………….

59

Gambar 3.4 Daerah layak soal A ………………………………………………

65

Gambar 3.5 Daerah layak soal B …………………………………………...….

66

Gambar 3.6 Proyeksi − c k ke ruang nol A k …………………………………..

71

Gambar 3.7 Daerah layak sebelum dikenai transformasi affine skaling ……...

94

Gambar 3.8 Daerah layak yang sudah ditransformasi oleh transformasi affine skaling …………………………………..

95

TABEL Halaman Tabel 1 Hasil iterasi contoh 3.4 Tabel 2 Hasil iter5asi contoh 3.5

…………………………………..………….

103

……………………………………………. 104

xiii

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI 1

BAB I PENDAHULUAN

A. LATAR BELAKANG MASALAH Masalah program linear adalah suatu masalah penyelesaian sistem persamaan linear. Masalah program linear dapat diselesaikan dengan cara metode grafik atau metode simpleks. Pada metode grafik penyelesaiannya khusus dikerjakan hanya untuk dua variabel saja, sehingga apabila memuat lebih dari dua variabel akan sulit menyelesaikannya. Meskipun dalam prakteknya masalah program linear jarang yang hanya memuat dua variabel tetapi metode grafik mempermudahkan orang dalam memahami pengertian-pengertian yang timbul dalam masalah program linear. Untuk menyelesaikan masalah program linear yang memuat dua atau lebih variabel dapat digunakan metode simpleks. Ada metode lain yaitu metode titik-dalam yang dapat digunakan untuk menyelesaikan masalah program linear yang memuat dua atau lebih variabel. Perbedaan proses penyelesaian antara metode simpleks dan metode titikdalam, yaitu pada metode simpleks penyelesaian dilakukan dengan meninjau setiap titik-titik sudut pada batas dari daerah layak hingga dicapai titik optimum. Sedangkan pada metode titik-dalam dengan meninjau titik-titik yang berada dalam daerah layak hingga dicapai titik optimum. Sehingga apabila program linear memuat masalah yang kompleks maka proses penyelesaian yang dilakukan dengan metode titik-dalam dapat lebih cepat dan efisien dibandingkan dengan metode simpleks. Karena pada metode simpleks apabila program linear memuat masalah


yang kompleks maka program linear tersebut juga akan memiliki banyak titik batas. Sehingga dibutuhkan proses lebih panjang dibandingkan dengan metode titikdalam untuk mencapai titik optimum. Sebagai ilustrasi perhatikan gambar 1.1 berikut: Langkah-langkah Metode Simpleks

x k +1

xk

Langkah-langkah metode titik-dalam

Gambar 1.1 Metode Titik-dalam vs Metode Simpleks

Ada dua langkah yang diperlukan dari metode titik-dalam, yaitu a. Mencari arah layak yang memperbaiki nilai fungsi sasaran pada titik yang ditentukan dari tiap iterasi. b. Menentukan besar langkah yang berada pada daerah layak sesuai arah layak yang memperbaiki nilai fungsi sasaran. Metode titik-dalam dibagi menjadi empat kelas utama, yaitu metode affine-skaling (affine-scaling method), metode proyektif (projective method) atau lebih dikenal dengan metode Karmarkar , metode path-following (path-following method), dan metode potensial-reduksi (potential-reduction method). Dalam tulisan ini hanya akan dibahas metode affine-skaling. Metode affine-skaling adalah salah satu metode titik-dalam yang paling sederhana diantara


semua metode titik-dalam. Disebut metode affine-skaling karena transformasi yang digunakan adalah transformasi affine-skaling. Metode affine-skaling yang akan digunakan dibatasi hanya untuk masalah primal program linear yang meminimumkan fungsi sasaran.

Sehingga metode ini disebut juga sebagai me-

tode primal affine-skaling. Ide dasar metode primal affine-skaling yaitu dimulai dengan memilih suatu titik-dalam awal didalam daerah layak. Kemudian titik dalam yang dipilih ditransformasi oleh transformasi affine-skaling sedemikian sehingga hasil transformasi titik-dalam yang dipilih diposisikan dekat dengan pusat di ruang penyelesaian hasil transformasi.

Hasil transformasi

titik-dalam yang dipilih

dijalankan ke suatu titik-dalam lain dengan arah layak dan besar langkah yang sesuai. Penyelesaian yang didapat di ruang penyelesaian tersebut ditransformasi kembali dengan transformasi invers yang sesuai. Proses iterasi ini diulang hingga penyelesaian optimum dicapai. Selain dibahas metode primal affine-skaling

juga akan dibahas

aplikasinya dengan menggunakan program matlab untuk menyelesaikan masalah program linear.

B. RUMUSAN MASALAH Berdasarkan latar belakang masalah di atas, maka dibuat rumusan sebagai berikut: 1. Bagaimana menyelesaikan masalah program linear dengan menggunakan metode primal affine-skaling?


2. Bagaimana aplikasi dari metode primal affine-skaling dengan menggunakan program matlab?

C. PEMBATASAN MASALAH 1. Penulis hanya akan membahas masalah dalam bentuk meminimumkan, sehingga masalah memaksimumkan harus diubah dalam bentuk meminimumkan, yaitu negatif dari maksimum fungsinya. 2. Metode yang digunakan adalah metode primal affine-skaling. 3. Transformasi yang digunakan adalah transformasi affine-skaling. 4. Daerah layak dari soal program linear adalah terbatas dan tidak kosong. 5. Hanya memuat variabel kurang dari atau sama dengan 10 ( n ≤ 10 ).

D. TUJUAN PENULISAN Sesuai dengan latar belakang di atas, penulisan skripsi ini bertujuan untuk menunjukkan langkah-langkah metode primal affine-skaling untuk menyelesaikan masalah program linear yang memuat n ≤ 10 dan dapat dipertanggungjawabkan langkah demi langkah.

E. MANFAAT PENULISAN Manfaat dari penulisan skripsi ini adalah memberikan tambahan referensi dalam menyelesaikan masalah program linear dengan metode primal affine skaling.


F. METODE PENULISAN Metode yang digunakan dalam skripsi ini adalah penelitian kepustakaan, yaitu dengan mempelajari buku-buku yang berkaitan dengan topik skripsi ini, sehingga dalam tulisan ini tidak ditemukan hal-hal yang baru.

G. SISTEMATIKA PENULISAN Penulisan skripsi ini menggunakan sistematika sebagai berikut: Bab I

PENDAHULUAN Bab ini berisi latar belakang masalah, perumusan masalah, pembatasan masalah, tujuan penulisan, manfaat penulisan, dan metode penulisan.

Bab II

ORTOGONALITAS DAN OPTIMISASI UNTUK PERSOALAN LINEAR Bab ini berisi tentang dasar teori yang berkaitan dan digunakan dalam metode primal affine-skaling, yaitu mengenai sistem persamaan linear dan matriks, ruang vektor, masalah program linear, optimisasi fungsi untuk persoalan linear, metode arah layak dan metode arah turun tercuram.

Bab III METODE PRIMAL AFFINE-SKALING Bab ini membahas tentang langkah-langkah metode primal affine-skaling dan aplikasinya menggunakan program matlab. Bab IV PENUTUP Bab ini berisi beberapa kesimpulan dan saran berdasarkan hasil pembahasan dan keseluruhan proses penyusunan skripsi.


BAB II ORTOGONALITAS DAN OPTIMISASI UNTUK PERSOALAN LINEAR

Pada bab ini akan dibahas hal-hal yang melandasi bab berikutnya. Definisi, teorema serta konsep-konsep mengacu pada daftar pustaka.

A. Sistem Persamaan Linear Dan Matriks Definisi 2.1 Persamaan Linear Persamaan linear dalam n variabel x1 , x 2 ,L , x n adalah persamaan yang dapat dinyatakan dalam bentuk a1 x1 + a 2 x 2 + L + a n x n = b

(2.1)

dengan a1 , a 2 ,K , a n dan b adalah konstanta real dan a1 , a 2 , K, a n tidak semua sama dengan nol.

Definisi 2.2 Sistem Persamaan Linear Suatu sistem persamaan linear m × n adalah himpunan m persamaan linear dengan n variabel, yang dapat dinyatakan dalam bentuk ⎧a11 x1 + a12 x 2 + L + a1n x n = b1 ⎪a x + a x + L + a x = b ⎪ 21 1 2n n 2 22 2 ⎨ O M ⎪ M ⎪⎩a m1 x1 + a m 2 x 2 + L + a mn x n = bm

(2.2)

dengan ai1 , ai 2 , K , ain dan bi adalah konstanta real dan ai1 , ai 2 , K , ain tidak semua sama dengan nol, untuk i = 1,2,K, m .


7

Dalam

sistem

persamaan

linear

m×n ,

dapat

terjadi

m = n, m > n atau m < n . Apabila x1 = t1 , x 2 = t 2 , L, x n = t n dimana t1 , t 2 ,K , t n adalah konstanta-konstanta real yang memenuhi semua persamaan linear dalam sistem (2.2), maka pasangan terurut (t1 , t 2 ,K , t n ) disebut penyelesaian atau jawab dari sistem persamaan linear (2.2).

Definisi 2.3 Konsisten dan Tidak Konsisten

1. Sistem persamaan linear disebut konsisten jika sistem persamaan tersebut mempunyai penyelesaian. 2. Sistem persamaan linear disebut tidak konsisten jika sistem persamaan tersebut tidak mempunyai penyelesaian. Sistem yang konsisten dapat mempunyai tepat satu penyelesaian atau mempunyai banyak penyelesaian.

Sistem persamaan linear (2.2) di atas dapat dituliskan dengan notasi matriks sebagai berikut: ⎡ a11 ⎢a ⎢ 21 ⎢ M ⎢ ⎣a m1

a12 a 22 M am2

L a1n ⎤ ⎡ x1 ⎤ ⎡ b1 ⎤ L a 2 n ⎥⎥ ⎢⎢ x 2 ⎥⎥ ⎢⎢ b2 ⎥⎥ = O M ⎥⎢ M ⎥ ⎢ M ⎥ ⎥⎢ ⎥ ⎢ ⎥ L a mn ⎦ ⎣ x n ⎦ ⎣bm ⎦

(2.3)

Atau lebih singkat ditulis Ax = b , dimana A = (aij ) yaitu matriks koefisien, x = (x j ) dan b = (b i ) , untuk i = 1,K, m dan j = 1,L, n


8

Definisi 2.4 Sistem Persamaan Linear Homogen Suatu sistem persamaan linear disebut sistem persamaan linear homogen jika konstanta bi = 0 , untuk setiap i = 1,2,..., m . Sistem persamaan linear homogen mempunyai bentuk umum: ⎧a11 x1 + a12 x 2 + L + a1n x n = 0 ⎪a x + a x + L + a x = 0 ⎪ 21 1 2n n 22 2 ⎨ O M ⎪ M ⎪⎩a m1 x1 + a m 2 x 2 + L + a mn x n = 0

Sistem

persamaan

linear

homogen

(2.4)

selalu

konsisten

karena

x1 = 0, x 2 = 0, ..., x n = 0 selalu merupakan penyelesaian. Penyelesaian ini disebut penyelesaian trivial. Jika ada penyelesaian lain maka penyelesaian itu disebut penyelesian nontrivial.

Definisi 2.5 Matriks Lengkap Matriks lengkap dari sistem persamaan linear (2.2) adalah ⎡a11 a12 L a1n ⎢a a L a 2n ⎢ 21 22 ⎢ M O M ⎢ ⎣a m1 a m 2 L a mn

b1 ⎤ b2 ⎥⎥ M ⎥ ⎥ bm ⎦

Definisi 2.6 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 Ri ↔ R j .


9

2. Mengalikan suatu baris dengan konstanta tak nol, yakni mengalikan baris ke- i dengan bilangan c, c ≠ 0 , dengan notasi cRi . 3. Mengganti suatu baris dengan hasil penjumlahan baris tersebut dan kelipatan baris lain, yakni mengganti baris ke- i ditambah c kali baris ke- j , dengan notasi Ri + cR j .

Definisi 2.7 Matriks Ekivalen Baris Matriks B dikatakan ekivalen baris dengan matriks A jika terdapat matriks elementer E1 , E 2 ,..., E k sehingga B = E k E k −1 ...E1 A atau A = E1−1E 2−1 ...E −k 1B .

Dengan operasi baris elementer, matriks lengkap dari suatu sistem persamaan linear harus diubah menjadi suatu matriks dari sistem persamaan linear yang mudah dicari jawabnya, yakni dengan matriks eselon.

Definisi 2.8 Matriks Eselon Matriks E disebut matriks eselon jika memenuhi dua sifat berikut: 1. Setiap baris yang hanya terdiri dari bilangan nol terletak sesudah baris yang memuat elemen tak nol. 2. Pada setiap baris dari matriks E yang mempunyai elemen tak nol, elemen tak nol yang pertama harus terletak di kolom sebelah kanan elemen tak nol dari baris sebelumnya. Matriks eselon ini disebut juga matriks eselon baris. Elemen tak nol pertama dari suatu baris disebut elemen utama atau elemen pivot. Sifat kedua dari matriks eselon mengatakan bahwa elemen di bawah elemen pivot haruslah nol.


10

B. Ruang Vektor 1. Ruang Vektor Definisi 2.9 Ruang Vektor Ruang Vektor atas lapangan F adalah himpunan tidak kosong V yang dilengkapi dengan operasi penjumlahan dan operasi perkalian dengan skalar sedemikian sehingga ∀ x, y , z ∈ V dan ∀ α , β ∈ F memenuhi syarat - syarat berikut: a. x + y ∈ V b. x + y = y + x

(sifat komutatif)

c. x + (y + z ) = (x + y ) + z

(sifat asosiatif)

d. Terdapat elemen 0 ∈ V , ∀ x ∈ V , x + 0 = x

(unsur identitas)

e. ∀ x ∈ V ∃ (−x) ∈ V sehingga x + (−x) = 0

(elemen invers)

f. αx ∈ V g. α (x + y ) = α x + α y

(sifat distributif)

h. (α + β )x = α x + β x i. 1x = x j. (α β ) x = α ( β x) Elemen – elemen di V disebut vektor dan biasanya dinyatakan dengan huruf – huruf a, b,K, x, y, K . Elemen – elemen di F disebut skalar .


11

Contoh 2.1 ⎡ x1 ⎤ ⎡ y1 ⎤ ⎢x ⎥ ⎢y ⎥ 2⎥ ⎢ Misalkan x = dan y = ⎢ 2 ⎥ adalah vektor – vektor di R n . Penjumlahan ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎣ xn ⎦ ⎣ yn ⎦

pada R n didefinisikan sebagai berikut: ⎡ x1 ⎤ ⎡ y1 ⎤ ⎡ x1 + y1 ⎤ ⎢x ⎥ ⎢ y ⎥ ⎢x + y ⎥ 2⎥ x+ y = ⎢ 2⎥ + ⎢ 2⎥ = ⎢ 2 , ∀ x, y ∈ R n ⎢M⎥ ⎢M⎥ ⎢ M ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ xn ⎦ ⎣ y n ⎦ ⎣ xn + y n ⎦

(2.5)

dan operasi perkalian dengan skalar α di R didefinisikan sebagai berikut: ⎡ x1 ⎤ ⎡α x1 ⎤ ⎢ x ⎥ ⎢α x ⎥ α x = α ⎢ 2 ⎥ = ⎢ 2 ⎥ , ∀ x ∈ R n , ∀α ∈ R ⎢M⎥ ⎢ M ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ x n ⎦ ⎣α x n ⎦

(2.6)

Tunjukkan bahwa R n merupakan ruang vektor. Bukti: ⎡ x1 ⎤ ⎡ y1 ⎤ ⎡ z1 ⎤ ⎢x ⎥ ⎢y ⎥ ⎢z ⎥ 2⎥ 2⎥ ⎢ ⎢ Misalkan x = , y= , dan z = ⎢ 2 ⎥ , ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ xn ⎦ ⎣ yn ⎦ ⎣zn ⎦

∀ x, y , z ∈ R n , ∀α , β ∈ R

a. Akan ditunjukkan x + y ∈ R n . Sudah jelas (dari persamaan (2.5)) b. Akan ditunjukkan x + y = y + x ⎡ x1 ⎤ ⎡ y1 ⎤ ⎡ x1 + y1 ⎤ ⎡ y1 + x1 ⎤ ⎡ y1 ⎤ ⎡ x1 ⎤ ⎢x ⎥ ⎢ y ⎥ ⎢x + y ⎥ ⎢ y + x ⎥ ⎢ y ⎥ ⎢x ⎥ 2⎥ 2⎥ x+ y = ⎢ 2⎥ + ⎢ 2⎥ = ⎢ 2 = ⎢ 2⎥ + ⎢ 2⎥ = y + x =⎢ 2 ⎢M⎥ ⎢M⎥ ⎢ M ⎥ ⎢ M ⎥ ⎢M⎥ ⎢M⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎣ xn ⎦ ⎣ y n ⎦ ⎣ xn + y n ⎦ ⎣ y n + xn ⎦ ⎣ y n ⎦ ⎣ xn ⎦


12

c. Akan ditunjukkan x + (y + z ) = (x + y ) + z ⎡ x1 ⎤ ⎡ y1 + z1 ⎤ ⎡ x1 + ( y1 + z1 ) ⎤ ⎡ ( x1 + y1 ) + z1 ⎤ ⎢ x ⎥ ⎢ y + z ⎥ ⎢ x + ( y + z ) ⎥ ⎢( x + y ) + z ⎥ 2⎥ 2 2 ⎥ 2 2⎥ x + (y + z ) = ⎢ 2 ⎥ + ⎢ 2 =⎢ 2 =⎢ 2 ⎥ ⎥ ⎢M⎥ ⎢ M ⎥ ⎢ ⎢ M M ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎣ x n ⎦ ⎣ y n + z n ⎦ ⎣ x n + ( y n + z n ) ⎦ ⎣( x n + y n ) + z n ⎦ ⎡ x1 + y1 ⎤ ⎡ z1 ⎤ ⎢x + y ⎥ ⎢z ⎥ 2⎥ =⎢ 2 + ⎢ 2 ⎥ = (x + y ) + z ⎢ M ⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎣ xn + yn ⎦ ⎣ z n ⎦

d. Akan ditunjukkan ada elemen identitas terhadap operasi penjumlahan. ⎡0 ⎤ ⎢0 ⎥ Elemen identitasnya 0 = ⎢ ⎥ sehingga ⎢M ⎥ ⎢ ⎥ ⎣0 ⎦ ⎡ x1 ⎤ ⎡0⎤ ⎡ x1 + 0 ⎤ ⎡ x1 ⎤ ⎢ x ⎥ ⎢0 ⎥ ⎢ x + 0 ⎥ ⎢ x ⎥ ⎥ = ⎢ 2⎥ = x x+0 = ⎢ 2⎥ + ⎢ ⎥ = ⎢ 2 ⎢ M ⎥ ⎢M⎥ ⎢ M ⎥ ⎢ M ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎣ x n ⎦ ⎣0 ⎦ ⎣ x n + 0 ⎦ ⎣ x n ⎦

e. Akan ditunjukkan mempunyai invers. ⎡ x1 ⎤ ⎡ − x1 ⎤ ⎢x ⎥ ⎢− x ⎥ Invers dari x = ⎢ 2 ⎥ adalah − x = ⎢ 2 ⎥ sehingga ⎢M⎥ ⎢ M ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ xn ⎦ ⎣− x n ⎦ ⎡ x1 ⎤ ⎡ − x1 ⎤ ⎡ x1 + (− x1 ) ⎤ ⎡0⎤ ⎢ x ⎥ ⎢ − x ⎥ ⎢ x + ( − x ) ⎥ ⎢0 ⎥ 2 ⎥ x + ( − x) = ⎢ 2 ⎥ + ⎢ 2 ⎥ = ⎢ 2 =⎢ ⎥=0 ⎢M⎥ ⎢ M ⎥ ⎢ ⎥ ⎢M⎥ M ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ x n ⎦ ⎣ − x n ⎦ ⎣ x n + ( − x n ) ⎦ ⎣0 ⎦

f. Akan ditunjukkan α x ∈ R n . Sudah jelas (dari persamaan (2.6))


13

g. Akan ditunjukkan α (x + y ) = α x + α y ⎡ x1 + y1 ⎤ ⎡ α x1 + α y1 ⎤ ⎡α x1 ⎤ ⎡α y1 ⎤ ⎢ x + y ⎥ ⎢α x + α y ⎥ ⎢α x ⎥ ⎢α y ⎥ 2⎥ 2⎥ = ⎢ 2⎥ + ⎢ 2⎥ =α x +α y =⎢ 2 α (x + y ) = α ⎢ 2 ⎢ M ⎥ ⎢ ⎥ ⎢ M ⎥ ⎢ M ⎥ M ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎣ x n + y n ⎦ ⎣α x n + α y n ⎦ ⎣α x n ⎦ ⎣α y n ⎦

h. Akan ditunjukkan (α + β ) x = α x + β x ⎡ x1 ⎤ ⎡ (α + β ) x1 ⎤ ⎡ α x1 ⎢ x ⎥ ⎢(α + β ) x ⎥ ⎢α x 2⎥ =⎢ 2 (α + β ) x = (α + β ) ⎢ 2 ⎥ = ⎢ ⎢M⎥ ⎢ ⎥ ⎢ M ⎢ ⎥ ⎢ ⎥ ⎢ ⎣ x n ⎦ ⎣(α + β ) x n ⎦ ⎣α x n

+ β x1 ⎤ ⎡α x1 ⎤ ⎡ β x1 ⎤ + β x 2 ⎥⎥ ⎢⎢α x 2 ⎥⎥ ⎢⎢ β x 2 ⎥⎥ = + ⎥ ⎢ M ⎥ ⎢ M ⎥ M ⎥ ⎢ ⎥ ⎢ ⎥ + β x n ⎦ ⎣α x n ⎦ ⎣ β x n ⎦

=αx+β x

i. Akan ditunjukkan ada elemen identitas terhadap operasi perkalian ⎡ x1 ⎤ ⎡1 x1 ⎤ ⎡ x1 ⎤ ⎢ x ⎥ ⎢1 x ⎥ ⎢ x ⎥ 1x = 1 ⎢ 2 ⎥ = ⎢ 2 ⎥ = ⎢ 2 ⎥ = x ⎢M⎥ ⎢ M ⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ x n ⎦ ⎣1 x n ⎦ ⎣ x n ⎦

j. Akan ditunjukkan (α β ) x = α ( β x) ⎡ x1 ⎤ ⎡ (α β ) x1 ⎤ ⎡ α ( β x1 ) ⎤ ⎡ β x1 ⎤ ⎢ x ⎥ ⎢(α β ) x ⎥ ⎢ α ( β x ) ⎥ ⎢β x ⎥ 2⎥ 2⎥ 2 ⎥ ⎢ ⎢ ⎢ x = = = = (α β ) α ⎢ 2 ⎥ = α ( β x) . ~ αβ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ M ⎥ M M ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ x n ⎦ ⎣(α β ) x n ⎦ ⎣α ( β x n _)⎦ ⎣β xn ⎦

Definisi 2.10 Subruang (Subspaces)

Jika W adalah subhimpunan tak kosong dari suatu ruang vektor V dan W memenuhi syarat-syat berikut:


14

a. untuk x ∈ W dan sebarang skalar α ∈ F maka α x ∈ W b. untuk x ∈ W dan y ∈ W maka vektor x + y ∈ W maka W disebut subruang vektor dari V .

Definisi 2.11 Ruang Nol (Null Spaces)

Misalkan A adalah matriks berukuran m × n . Misalkan N ( A) menyatakan himpunan semua penyelesaian dari sistem persamaan homogen A x = 0 . Jadi N ( A) = { x ∈ R n

Ax = 0 }

(2.7)

N ( A) disebut sebagai ruang nol.

Contoh 2.2

Tunjukkan bahwa N ( A) = { x ∈ R n

Ax = 0 } merupakan ruang vektor.

Bukti: ⎡ x1 ⎤ ⎡ y1 ⎤ ⎡ z1 ⎤ ⎢x ⎥ ⎢y ⎥ ⎢z ⎥ 2⎥ 2⎥ ⎢ ⎢ Misalkan x = , y= , dan z = ⎢ 2 ⎥ , ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ xn ⎦ ⎣ yn ⎦ ⎣zn ⎦

a. Akan ditunjukkan Ax + Ay ∈ N ( A) ⎡0 ⎤ ⎡ 0 ⎤ ⎡0 ⎤ ⎢0 ⎥ ⎢ 0 ⎥ ⎢0 ⎥ Ax + Ay = 0 + 0 = ⎢ ⎥ + ⎢ ⎥ = ⎢ ⎥ = 0 ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 ⎦ ⎣ 0 ⎦ ⎣0 ⎦ Jadi Ax + Ay ∈ N ( A) b. Akan ditunjukkan Ax + Ay = Ay + Ax

∀ x, y, z ∈ R n , ∀α , β ∈ R


15

⎡0 ⎤ ⎡0 ⎤ ⎡ 0 ⎤ ⎡0 ⎤ ⎢0 ⎥ ⎢0 ⎥ ⎢ 0 ⎥ ⎢0 ⎥ Ax + Ay = 0 + 0 = ⎢ ⎥ + ⎢ ⎥ = ⎢ ⎥ + ⎢ ⎥ = 0 + 0 = Ay + Ax ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 ⎦ ⎣0 ⎦ ⎣ 0 ⎦ ⎣0 ⎦ c. Akan ditunjukkan Ax + ( Ay + Az ) = ( Ax + Ay ) + Az ⎡ 0 ⎤ ⎛ ⎡ 0 ⎤ ⎡0 ⎤ ⎞ ⎛ ⎡0 ⎤ ⎡ 0 ⎤ ⎞ ⎡0 ⎤ ⎢ 0 ⎥ ⎜ ⎢ 0 ⎥ ⎢0 ⎥ ⎟ ⎜ ⎢0 ⎥ ⎢ 0 ⎥ ⎟ ⎢0 ⎥ ⎜ ⎟ ⎜ ⎟ Ax + ( Ay + Az ) = 0 + (0 + 0) = ⎢ ⎥ + ⎜ ⎢ ⎥ + ⎢ ⎥ ⎟ = ⎜ ⎢ ⎥ + ⎢ ⎥ ⎟ + ⎢ ⎥ ⎢M⎥ ⎢M⎥ ⎢M ⎥ ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎜⎜ ⎢ ⎥ ⎢ ⎥ ⎟⎟ ⎜⎜ ⎢ ⎥ ⎢ ⎥ ⎟⎟ ⎢ ⎥ ⎣ 0 ⎦ ⎝ ⎣ 0 ⎦ ⎣0 ⎦ ⎠ ⎝ ⎣0 ⎦ ⎣ 0 ⎦ ⎠ ⎣0 ⎦

= (0 + 0) + 0 = ( Ax + Ay ) + Az d. Akan ditunjukkan ada elemen identitas terhadap operasi penjumlahan ⎡0 ⎤ ⎢0 ⎥ Elemen identitasnya 0 = ⎢ ⎥ sehingga ⎢M ⎥ ⎢ ⎥ ⎣0 ⎦ ⎡ 0 ⎤ ⎡0 ⎤ ⎡0 ⎤ ⎢ 0 ⎥ ⎢0 ⎥ ⎢0 ⎥ Ax + 0 = 0 + 0 = ⎢ ⎥ + ⎢ ⎥ = ⎢ ⎥ = 0 = Ax ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 0 ⎦ ⎣0 ⎦ ⎣0 ⎦ e. Akan ditunjukkan ada elemen invers ⎡ − 0⎤ ⎡0 ⎤ ⎢ − 0⎥ ⎢0 ⎥ ⎥ ⎢ adalah − ( Ax) = −0 = ⎢ ⎥ sehingga Invers dari Ax = 0 = ⎢ M ⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎣ − 0⎦ ⎣0 ⎦ ⎡0 ⎤ ⎡ − 0 ⎤ ⎡0 ⎤ ⎢0 ⎥ ⎢ − 0 ⎥ ⎢0 ⎥ Ax + (−( Ax)) = ⎢ ⎥ + ⎢ ⎥ = ⎢ ⎥ = 0 ⎢M ⎥ ⎢ M ⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 ⎦ ⎣ − 0 ⎦ ⎣0 ⎦


16

f. Akan ditunjukkan αAx ∈ N ( A) ⎡0 ⎤ ⎡0 ⎤ ⎢0 ⎥ ⎢0 ⎥ α Ax = α 0 = α ⎢ ⎥ = ⎢ ⎥ = 0 ∈ N ( A) ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 ⎦ ⎣0 ⎦ g. Akan ditunjukkan α ( Ax + Ay ) = αAx + αAy ⎛ ⎡0⎤ ⎡0⎤ ⎞ ⎡α 0⎤ ⎡α 0⎤ ⎜⎢ ⎥ ⎢ ⎥⎟ ⎢ ⎥ ⎢ ⎥ 0 ⎟ α0 α0 ⎜ 0 α ( Ax + Ay ) = α (0 + 0) = α ⎜ ⎢ ⎥ + ⎢ ⎥ ⎟ = ⎢ ⎥ + ⎢ ⎥ = αAx + αAy ⎢M⎥ ⎢M⎥ ⎢ M ⎥ ⎢ M ⎥ ⎜⎢ ⎥ ⎢ ⎥⎟ ⎢ ⎥ ⎢ ⎥ ⎜ 0 ⎟ ⎝ ⎣ ⎦ ⎣0⎦ ⎠ ⎣α 0⎦ ⎣α 0⎦

h. Akan ditunjukkan (α + β ) Ax = = αAx + βAx ⎡ 0 ⎤ ⎡(α ⎢ 0⎥ ⎢(α α β Ax α β Ax α β ( + ) =( + ) = ( + )⎢ ⎥ = ⎢ ⎢M⎥ ⎢ ⎢ ⎥ ⎢ ⎣ 0 ⎦ ⎣(α

+ β ) 0⎤ ⎡α 0⎤ ⎡ β 0⎤ + β ) 0⎥⎥ ⎢⎢α 0⎥⎥ ⎢⎢ β 0⎥⎥ + = ⎥ ⎢ M ⎥ ⎢ M ⎥ M ⎥ ⎢ ⎥ ⎢ ⎥ + β ) 0⎦ ⎣α 0⎦ ⎣ β 0⎦

= αAx + βAx i. Akan ditunjukkan ada elemen identitas terhadap operasi perkalian ⎡0 ⎤ ⎡0 ⎤ ⎢0 ⎥ ⎢0 ⎥ 1Ax = 1 0 = 1⎢ ⎥ = ⎢ ⎥ = 0 = Ax ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎣0 ⎦ ⎣0 ⎦ j. Akan ditunjukkan (αβ ) Ax = α ( βAx) ⎡ β 0⎤ ⎡ 0 ⎤ ⎡(αβ ) 0⎤ ⎢ ⎥ ⎢ 0⎥ ⎢(αβ ) 0⎥ ⎥ = α ⎢ β 0⎥ = α ( βAx) . ~ (αβ ) Ax = (αβ ) Ax = (αβ ) ⎢ ⎥ = ⎢ ⎢ M ⎥ ⎢M⎥ ⎢ M ⎥ ⎢ ⎥ ⎥ ⎢ ⎥ ⎢ ⎣ β 0⎦ ⎣ 0 ⎦ ⎣(αβ ) 0⎦


17

Teorema 2.1 N ( A) = { x ∈ R n

Ax = 0 } merupakan subruang dari R n .

Bukti:

Akan dibuktikan bahwa N ( A) adalah subruang dari R n , yakni a. Misalkan x ∈ N (A) dan α suatu skalar, maka A(α x) = α ( Ax) = α 0 = 0 . Jadi α x ∈ N (A) . b. Misalkan x dan y adalah elemen – elemen dari N ( A) , maka

A(x + y ) = Ax + Ay = 0 + 0 = 0 Jadi x + y ∈ N ( A) . Dari (a) dan (b) terbukti bahwa N ( A) adalah subruang dari R n . ▄

Definisi 2.12 Kombinasi Linear

Misalkan x1 , x 2 ,K, x n adalah vektor – vektor dalam suatu ruang vektor V atas lapangan F . Jumlahan vektor-vektor yang berbentuk

α 1 x1 + α 2 x 2 + L + α n x n

(2.8)

disebut suatu kombinasi linear dari x1 , x 2 , K, x n , dengan skalar α 1 ,K , α n ∈ F .

Definisi 2.13 Merentang (span)

Jika x1 , x 2 , K, x n adalah vektor-vektor pada ruang vektor V dan jika masingmasing vektor pada V

dapat dinyatakan sebagai kombinasi linear dari

x1 , x 2 , K, x n maka dapat dikatakan bahwa vektor-vektor x1 , x 2 , K, x n merentang


18

V dan dilambangkan S (x1 , x 2 , K, x n ) .

Teorema 2.2

Jika

x1 , x 2 , K , x n

adalah vektor-vektor dalam ruang vektor

V

maka

S (x1 , x 2 ,K, x n ) adalah subruang dari V . Bukti:

Misalkan β suatu skalar dan misalkan b = α 1 x1 + α 2 x 2 + L + α n x n adalah sebarang elemen dari S (x1 , x 2 , K, x n ) . Maka β b = ( βα 1 )x1 + ( βα 2 )x 2 + L + ( βα n )x n Jadi β b ∈ S (x1 , x 2 ,K, x n ) Selanjutnya akan ditunjukkan bahwa sebarang jumlah elemen-elemen dari S (x1 , x 2 ,K, x n ) juga berada dalam S (x1 , x 2 ,K, x n ) Misalkan b = α 1 x1 + α 2 x 2 + L + α n x n dan c = β 1 x1 + β 2 x 2 + L + β n x n Maka b + c = (α 1 + β 1 )x1 + (α 2 + β 2 )x 2 + L + (α n + β n )x n Jadi b + c ∈ S (x1 , x 2 ,K , x n ) Jadi S (x1 , x 2 ,K , x n ) adalah subruang dari V . ▄

Definisi 2.14 Himpunan Perentang

Himpunan {x1 , x 2 , K, x n } disebut himpunan perentang untuk ruang vektor V jika hanya jika V = S (x1 , x 2 , K , x n ) .


19

Contoh 2.3

Misalkan e i adalah vektor dalam R n yang komponen ke- i adalah 1 dan komponen yang lainnya semua sama dengan nol, untuk i = 1,2,K , n . Jadi ⎡0⎤ ⎡0 ⎤ ⎡1⎤ ⎢0⎥ ⎢1 ⎥ ⎢0 ⎥ e1 = ⎢ ⎥ , e 2 = ⎢ ⎥ , L , e n = ⎢ ⎥ . ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣1 ⎦ ⎣0 ⎦ ⎣0 ⎦ Setiap vektor v ∈ R n dapat dinyatakan sebagai kombinasi linear dari vektor-vek⎡ v1 ⎤ ⎢v ⎥ tor e1 , e 2 ,L, e n tersebut, yaitu jika v = ⎢ 2 ⎥ adalah sebarang vektor dalam R n , ⎢M⎥ ⎢ ⎥ ⎣v n ⎦

maka v = v1e1 + v 2 e 2 + L + v n e n . Oleh karena itu {e1 , e 2 ,L, e n } adalah himpunan perentang untuk R n . ~

Definisi 2.15 Bebas linear (linearly independent)

Vektor – vektor x1 , x 2 , K, x n dalam ruang vektor V disebut bebas linear jika

α 1 x1 + α 2 x 2 + L + α n x n = 0

(2.9)

mengakibatkan semua skalar – skalar α 1 , K , α n harus sama dengan nol.

Definisi 2.16 Bergantung Linear (linearly dependent)

Vektor – vektor x1 , x 2 , K, x n dalam ruang vektor V disebut bergantung linear jika terdapat skalar – skalar α 1 , K , α n yang tidak semuanya nol sehingga

α 1 x1 + α 2 x 2 + L + α n x n = 0

(2.10)


20

Definisi 2.17 Basis

Misalkan V suatu ruang vektor atas lapangan F . Himpunan vektor - vektor

{ x1 , x 2 ,.K, x n } membentuk basis untuk ruang vektor V a.

{ x1 , x 2 ,.K, x n } bebas linear

b.

{ x1 , x 2 ,.K, x n } merentang

jika dan hanya jika

V

Contoh 2.4

Tunjukkan bahwa

{ e1 , e 2 ,K, e n } adalah basis.

Bukti:

Dalam contoh 2.3 telah ditunjukkan bahwa e1 , e 2 , K, e n merentang R n . Bila ⎡ v1 ⎤ ⎡0⎤ ⎢ v ⎥ ⎢0 ⎥ v1e1 + v 2 e 2 + L + v n e n = 0 maka ⎢ 2 ⎥ = ⎢ ⎥ , sehingga v1 = v 2 = L = v n = 0 . ⎢ M ⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎣v n ⎦ ⎣0 ⎦

Jadi e1 , e 2 ,K, e n bebas linear. Maka {e1 , e 2 ,K, e n } merupakan basis untuk R n . ~ Basis tersebut disebut basis baku untuk R n

Definisi 2.18 Vektor-Vektor Baris dan Vektor-Vektor Kolom ⎡ a11 ⎢a Misalkan matriks A = ⎢ 21 ⎢ M ⎢ ⎣a m1

r1 = [a11

a12 a 22

M am2

a12 L a1n ] , r2 = [a 21

L a1n ⎤ L a 2 n ⎥⎥ . Vektor-vektor dalam R 1×n yaitu O M ⎥ ⎥ L a mn ⎦

a 22 L a 2 n ] , L , rm = [a m1

a m 2 L a mn ]


21

yang dibentuk dari baris-baris matriks A dinamakan vektor-vektor baris dari A dan vektor-vektor dalam R m , yaitu ⎡ a11 ⎤ ⎡ a12 ⎤ ⎡ a1n ⎤ ⎢a ⎥ ⎢a ⎥ ⎢a ⎥ 21 ⎥ 22 ⎥ ⎢ ⎢ , k2 = , L, k n = ⎢ 2n ⎥ k1 = ⎢ M ⎥ ⎢ M ⎥ ⎢ M ⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣a m1 ⎦ ⎣a m 2 ⎦ ⎣a mn ⎦

yang dibentuk dari kolom-kolom matriks A , dinamakan vektor-vektor kolom dari A .

Definisi 2.19 Ruang Baris dan Ruang kolom

a. Subruang yang direntang oleh m vektor baris matriks A merupakan subruang dari R 1×n dan disebut ruang baris A . b. Subruang yang direntang oleh n vektor kolom matriks A merupakan subruang dari R m dan disebut ruang kolom

A . Ruang kolom A dapat

dinotasikan

{

R ( A) = b ∈ R m b = Ax untuk x ∈ R n

}

Definisi 2.20 Rank Dari Matriks Rank dari matriks A berukuran m × n ditunjukkan dengan r ( A) . Rank matriks

A penuh jika r ( A) = min {m, n} .


22

2. Hasil Kali Dalam Dan Ortogonalitas Definisi 2.21 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 sebuah bilangan real

x, y yang memenuhi syarat berikut:

a.

x, x ≥ 0, ∀ x ≠ 0 dan x, x = 0 jika hanya jika x = 0 .

b.

x, y = y , x

∀ x, y ∈ V

c. α x + β y , z = α x, z + β y , z , ∀ x, y , z ∈ V dan ∀ α , β ∈ R Sebuah ruang vektor V dengan hasil kali dalamnya disebut ruang hasil kali

dalam .

Contoh 2.5 Ruang vektor R n . Tunjukkan bahwa hasil kali skalar yang didefinisikan:

x, y = x T y = [x1

x2

⎡ y1 ⎤ ⎢y ⎥ L x n ] ⎢ 2 ⎥ = x1 y1 + x 2 y 2 + K + x n y n . (2.11) ⎢M⎥ ⎢ ⎥ ⎣ yn ⎦

adalah hasil kali dalam untuk R n (yang disebut hasil kali dalam baku). Persamaan (2.11) dapat juga ditulis n

x, y = x T y = ∑ xi y i i =1

dengan x T menyatakan transpose matriks x .

(2.12)


23

Bukti: ⎡ x1 ⎤ ⎡ y1 ⎤ ⎡ z1 ⎤ ⎢x ⎥ ⎢y ⎥ ⎢z ⎥ 2⎥ 2⎥ ⎢ ⎢ , y= , dan z = ⎢ 2 ⎥ dalam ruang Ambil sebarang vektor x = ⎢M⎥ ⎢M⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ xn ⎦ ⎣ yn ⎦ ⎣zn ⎦

vektor R n dan sebarang skalar α , β ∈ R a. Dibuktikan x, x = x T x ≥ 0 Diketahui

x, x = x T x

x, x = x T x = [x1

x2

⎡ x1 ⎤ ⎢x ⎥ 2 2 2 L x n ] ⎢ 2 ⎥ = x1 + x 2 + K + x n ≥ 0 ⎢M⎥ ⎢ ⎥ ⎣ xn ⎦

Jadi x, x ≥ 0 (⇒) Diketahui x, x = 0 Untuk x12 + x22 + ... + xn2 = 0 diperoleh x1 = x2 = ....... = xn = 0 ⎡ x1 ⎤ ⎡0⎤ ⎢ x ⎥ ⎢0 ⎥ jadi x = ⎢ 2 ⎥ = ⎢ ⎥ = 0 ⎢ M ⎥ ⎢M⎥ ⎢ ⎥ ⎢ ⎥ ⎣ x n ⎦ ⎣0 ⎦

(⇐) Diketahui x = 0 Dibuktikan x, x = x T x = 0 ⎡0 ⎤ ⎢0 ⎥ x, x = x T x = 0 T 0 = [0 0 L 0] ⎢ ⎥ ⎢M⎥ ⎢ ⎥ ⎣0 ⎦


24

Jadi x T x = 0.0 + 0.0 +K + 0.0 = 0 b. Dibuktikan

x, y = y , x

yaitu dibuktikan

∀ x, y ∈ R n

x, y = x T y = y T x = y , x

x, y = x T y

= [x1

x2

⎡ y1 ⎤ ⎢y ⎥ L x n ] ⎢ 2 ⎥ = x1 y1 + x 2 y 2 + K + x n y n ⎢M⎥ ⎢ ⎥ ⎣ yn ⎦

= y1 x1 + y 2 x 2 + K + y n x n

= [ y1

y2

⎡ x1 ⎤ ⎢x ⎥ L y n ]⎢ 2 ⎥ ⎢M⎥ ⎢ ⎥ ⎣ xn ⎦

= y T x = y, x

Jadi x T y = y T x Jadi terbukti x, y = y , x

(2.13) ∀ x, y ∈ R n

c. Dibuktikan α x + β y , z = α x, z + β y , z , ∀ x, y , z ∈ R n , ∀ α , β ∈ R

α x + β y , z = [α x1 + β y1 α x 2 + β y 2

⎡ z1 ⎤ ⎢z ⎥ L α xn + β yn ]⎢ 2 ⎥ ⎢M⎥ ⎢ ⎥ ⎣zn ⎦

= α x1 z1 + α x 2 z 2 + K + α x n z n + β y1 z1 + β y 2 z 2 + K + β y n z n = α ( x1 z1 + x 2 z 2 + K + x n z n ) + β ( y1 z1 + y 2 z 2 + K + y n z n )


25

= α [x1

x2

⎡ z1 ⎤ ⎢z ⎥ L x n ] ⎢ 2 ⎥ + β [ y1 ⎢M⎥ ⎢ ⎥ ⎣zn ⎦

y2

⎡ z1 ⎤ ⎢z ⎥ L yn ]⎢ 2 ⎥ ⎢M⎥ ⎢ ⎥ ⎣zn ⎦

= α xT z + β y T z

(2.14)

= α x, z + β y , z

Jadi terbukti α x + β y , z = α x, z + β y , z , ∀ x, y , z ∈ R n Dari (a), (b), (c) terbukti bahwa hasil kali dalam di ruang vektor R n adalah hasil kali skalar x, y = x T y . ~

Definisi 2.22 Panjang atau norma Jika x adalah sebuah vektor di dalam sebuah ruang hasil kali dalam R n , panjang atau norma dari x didefinisikan x = (x T x) = x12 + x 22 + K + x n2

(2.15)

Definisi 2.23 Ortogonal Dua vektor dalam R n , yaitu x dan y , dikatakan orthogonal, dilambangkan x ⊥ y , jika xT y = 0

(2.16)

Definisi 2.24 Subruang Yang Ortogonal Dua subruang vektor dalam R n , yaitu X dan Y , dikatakan orthogonal jika


26

x T y = 0, ∀ x ∈ X dan y ∈ Y

(2.17)

Jika X dan Y saling orthogonal, dapat ditulis sebagai X ⊥ Y .

Teorema 2.3 Ax = b adalah konsisten jika hanya jika b ∈ R(A)

Bukti: (⇒) Akan dibuktikan b ∈ R(A) , artinya b berada di ruang kolom dari R (A) Misalkan A adalah matriks m × n dan x ∈ R n Karena Ax = b adalah konsisten maka Ax = b mempunyai penyelesaian Misalkan x adalah penyelesaian ⎡ a11 ⎢a Maka Ax = ⎢ 21 ⎢ M ⎢ ⎣a m1

a12 a 22 M am2

L a1n ⎤ ⎡ x1 ⎤ L a 2 n ⎥⎥ ⎢⎢ x 2 ⎥⎥ O M ⎥⎢ M ⎥ ⎥⎢ ⎥ L a mn ⎦ ⎣ x n ⎦

⎡ a11 x1 + a12 x 2 + L + a1n x n ⎤ ⎢ a x + a x +L+ a x ⎥ 22 2 2n n ⎥ = ⎢ 21 1 ⎢ ⎥ M ⎢ ⎥ ⎣a m1 x1 + a m 2 x 2 + L + a mn x n ⎦ ⎡ b1 ⎤ ⎢b ⎥ ⎢ 2⎥=b ⎢M⎥ ⎢ ⎥ ⎣bm ⎦

Atau dapat ditulis bi = ai1 x1 + ai 2 x 2 + L + ain x n


27

Perhatikan bahwa b merupakan vektor yang direntang oleh vektor-vektor kolom matriks A . Ini berarti b berada di ruang kolom A . Jadi b ∈ R(A)

(⇐) Akan dibuktikan Ax = b adalah konsisten Karena b ∈ R(A) maka b dapat direntangkan oleh oleh vektor-vektor kolom matriks A , yang dapat ditulis bi = ai1 x1 + ai 2 x 2 + L + ain x n ⎡ x1 ⎤ ⎢x ⎥ Berarti x = ⎢ 2 ⎥ memenuhi sistem Ax = b ⎢M⎥ ⎢ ⎥ ⎣ xn ⎦

Jadi x adalah penyelesaian Jadi Ax = b adalah konsisten. ▄

Teorema 2.4 Misalkan A matriks berukuran m × n . Andaikan matriks A mempunyai rank penuh m . Misalkan N (A) menyatakan ruang nol A dan R( A T ) menyatakan ruang kolom dari A T maka N (A) dan R( A T ) merupakan subruang yang saling orthogonal. Bukti: Misalkan x ∈ N (A) dan y ∈ R( A T ) Akan dibuktikan N (A) ⊥ R ( A T )


28

Berarti cukup dibuktikan x ⊥ y , artinya x T y = 0 , ∀ x ∈ N ( A) , y ∈ R ( A T ) N ( A) = { x ∈ R n

Ax = 0 } dan

{

R ( A T ) = y ∈ R n y = A T z untunk z ∈ R m

}

Maka x T y = x T ( A T z ) = ( Ax) T z Karena Ax = 0 Maka x T y = 0 T z Maka x T y = 0 Jadi x ⊥ y Jadi N (A) ⊥ R ( A T ) . ▄ R ( A T ) disebut juga sebagai ruang jawab dari y = A T z .

Dari teorema 2.4 telah diperlihatkan bahwa N ( A) ∈ R n dan R( A T ) ∈ R n adalah subruang yang saling orthogonal. Misalkan x ∈ N (A) dan y ∈ R( A T ) dan c = x + y , c ∈ Rn .

y

c

Ax = 0

x Gambar 2.1. c = x + y


29

x dapat juga ditulis x =c−y

(2.18)

Karena y = A T z , maka didapatkan x = c − AT z

(2.19)

Kalikan kedua ruas dengan A , maka didapatkan

Ax = Ac − AA T z Diketahui bahwa Ax = 0 , maka didapatkan 0 = Ac − AA T z

Ac = AA T z z = ( AA T ) −1 Ac

(2.20)

Subsitusikan persamaan (2.20) ke persamaan (2.19), maka didapatkan x = c − A T ( AA T ) −1 Ac = [ I − A T ( AA T ) −1 A ] c = Pc

(2.21)

dengan P = [ I − A T ( AA T ) −1 A ]

(2.22)

Definisi 2.25 Matriks Proyeksi Orthogonal Matriks P berukuran n × n , dengan

P = [ I − A T ( AA T ) −1 A ] disebut matriks

proyeksi ruang nol A atau matriks proyeksi orthogonal.

Perhatikan bahwa y ∈ R ( A T ) , maka berdasarkan persamaan (2.20) y = A T z = A T ( AA T ) −1 Ac = Rc

(2.23)


30

dengan R = A T ( AA T ) −1 A

(2.24)

Sifat 2.1 Misalkan P adalah matriks proyeksi orthogonal berukuran n × n , dengan P = [ I − A T ( AA T ) −1 A ] maka a. P 2 = P b. P T = P Bukti: a. Diketahui P = [ I − A T ( AA T ) −1 A ] Maka P 2 = [ I − A T ( AA T ) −1 A ] [ I − A T ( AA T ) −1 A ] = I 2 − 2 I ( A T ( AA T ) −1 A ) + A T ( AA T ) −1 A A T ( AA T ) −1 A = I − 2 ( A T ( AA T ) −1 A ) + A T ( AA T ) −1 A = I − A T ( AA T ) −1 A = P b. P T = [ I − A T ( AA T ) −1 A ] T = I − A T (( AA T ) −1 ) T A = I − A T (( AA T ) T ) −1 A = I − A T ( AA T ) −1 ) A = P . ▄


31

3. Transformasi Linear Definisi 2.26 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 T :V → W

Ruang vektor V disebut daerah asal T . Nilai transformasi T untuk elemen x ∈ V ditulis T (x) yang merupakan elemen di W . Elemen T (x) disebut peta

dari x .

Definisi 2.27 Transformasi Linear Misalkan V dan W dua ruang vektor. Transformasi T : V → W disebut transformasi linear jika a. Untuk sebarang vektor x1 dan x 2 di V berlaku T ( x1 + x 2 ) = T (x1 ) + T ( x 2 )

(2.25)

b. Untuk sebarang bilangan real s dan vektor x di V berlaku

T ( sx) = sT (x)

(2.26)


32

C. Masalah Program Linear 1. Bentuk Standar Masalah Program Linear Perumusan masalah program linear dibagi menjadi dua, yakni fungsi sasaran dan kendala-kendala.

Definisi 2.28 Fungsi sasaran Fungsi sasaran dalam masalah program linear dapat dinyatakan sebagai p

f = ∑cjxj

(2.27)

j =1

dengan p merupakan bilangan bulat yang menyatakan banyaknya variabel, x j merupakan variabel ke- j , dan c j ∈ R merupakan koefisien ongkos dari variabel ke- j , dengan j = 1,K, p

Kendala-kendala dibagi dua, yakni kendala utama dan kendala tak negatif. Definisi 2.29 Kendala utama Kendala utama masalah program linear berbentuk p

∑ a x (≤, =, ≥)b j =1

ij

j

i

, i = 1,2,..., m ; j = 1,K , p

(2.28)

dengan m merupakan banyaknya persamaan, aij ∈ R merupakan koefisien variabel ke- j pada persamaan ke- i dan bi menyatakan konstanta di ruas kanan untuk persamaan ke- i .


33

Definisi 2.30 Kendala Tak Negatif Kendala tak negatif berbentuk x j ≥ 0; j = 1,2,..., p.

(2.29)

Untuk mencari penyelesaian dari sistem (2.28), kendala utama yang berbentuk pertidaksamaan diubah menjadi persamaan, dengan cara sebagai berikut: p

a. Kendala yang berbentuk

∑a x ij

j =1

j

≤ bi , pada ruas kiri disisipkan variabel

pengetat (slack variable) si sedemikian sehingga dipenuhi: p

∑a x ij

j =1

j

+ si = bi dengan si ≥ 0, i = 1,2,..., m ; j = 1,2,..., p

Dalam hal ini, p

jika

∑a x j =1

ij

j

= bi ; i = 1,2,..., m ; j = 1,2,..., p maka si = 0

p

dan jika

∑a x j =1

ij

j

< bi ; i = 1,2,..., m ; j = 1,2,..., p maka si > 0 p

b. Kendala yang berbentuk

∑a x j =1

ij

j

≥ bi , pada ruas kanan disisipkan variabel

surplus (surplus variable) t i sedemikian sehingga dipenuhi: p

∑a x j =1

ij

j

= ti + bi ; i = 1,2,..., m ; j = 1,2,..., p

yang ekivalen dengan p

∑a x j =1

ij

j

− ti = bi dengan t i ≥ 0, i = 1,2,..., m ; j = 1,2,..., p


34

Dalam hal ini, p

jika

∑a x j =1

ij

j

= bi ; i = 1,2,..., m ; j = 1,2,..., p maka t i = 0

j

> bi ; i = 1,2,..., m ; j = 1,2,..., p maka t i > 0

p

jika

∑a x j =1

ij

Dengan demikian kendala utama akan berubah menjadi sistem persamaan linear: n

∑a x ij

j =1

j

= bi ; i = 1,2,..., m ; j = 1,2,..., n

(2.30)

yakni dengan memberi lambang variabel pengetat atau variabel surplus x j dimulai dari j = p + 1 sampai j = n, dengan n adalah banyaknya variabel x j . Dan supaya penyelesaian sistem (2.30) menjadi layak masih harus dipenuhi kendala tak negatif x j ≥ 0; j = 1,2,..., n.

(2.31)

Untuk menyesuaikan dengan bentuk kendala yang baru, fungsi sasaran yang semula berbentuk p

f = ∑ c j x j = c1 x1 + c2 x2 + ... + c p x p

(2.32)

j =1

dilengkapi menjadi n

f = ∑ c j x j = c1 x1 + c2 x2 + ... + c p x p + c p +1 x p +1 + ... + cn xn j =1

dengan c p +1 = c p + 2 = .... = c n = 0

(2.33)


35

Dengan demikian, suatu masalah program linear dapat dinyatakan dalam bentuk sebagai berikut: Maksimumkan (atau minimumkan) n

f = ∑cjxj

(2.34)

j =1

dengan kendala n

∑a x j =1

ij

j

= bi ; i = 1,2,..., m ; j = 1,2,..., n.

x j ≥ 0; j = 1,2,..., n.

(2.35) (2.36)

Bentuk di atas (dengan semua kendala utama berbentuk persamaan) disebut bentuk standar dari masalah program linear.

Bentuk di atas bila ditulis dalam notasi matriks adalah sebagai berikut Maksimumkan (atau Minimumkan) f = cT x dengan kendala

Ax{≤, ≥, =}b

(2.38)

x≥0

(2.39)

dengan x = (x j ) A = (aij ) adalah koefisien matriks kendala b = (bi ) adalah vektor suku tetap c = (c j ) adalah vektor ongkos Dimana i = 1,2,..., m ; j = 1,2,..., n.

(2.37)


36

Definisi 2.31 Penyelesaian Layak Nilai-nilai variabel yang memenuhi kendala utama (2.38) dan kendala tak negatif (2.39) disebut penyelesaian layak .

Pada umumnya sistem persamaan linear (2.38) mempunyai penyelesaian takhingga banyak. Di antara penyelesaian-penyelesaian tersebut dicari juga yang memenuhi (2.39), dan pada umumnya masih mempunyai penyelesaian takhingga banyak. Kemudian di antara penyelesaian layak yang takhingga banyak ini dicari yang mengoptimumkan fungsi sasaran, maka akan diperoleh penyelesaian optimum.

Definisi 2.32 Penyelesaian Basis Suatu vektor x merupakan penyelesaian basis, jika: a. x memenuhi persamaan kendala dalam program linear b. kolom-kolom matriks kendala yang bersesuaian dengan vektor tak nol x adalah bebas linear.

Definisi 2.33 Penyelesaian Layak Basis Suatu vektor x disebut penyelesaian layak basis jika vektor x merupakan penyelesaian basis yang memenuhi kendala tak negatif x ≥ 0 .

Definisi 2.34 Penyelesaian Layak Basis Optimum Suatu vektor x disebut penyelesaian layak basis optimum jika x adalah


37

penyelesaian layak basis yang memberikan nilai optimum untuk fungsi sasaran.

2. Dualitas Dalam masalah program linear timbul hubungan dual antara dua soal program linear tertentu dan masing-masing penyelesaian optimumnya akan berkaitan. Perhatikan contoh berikut.

Contoh 2.6 Misalkan terdapat masalah program linear , namakan saja soal P, yakni Maksimumkan

f = cT x

(2.40)

dengan kendala

Ax ≤ b

(2.41)

x≥0

(2.42)

Masalah program linear ini berpola maksimum standar. Soal P disebut soal primal karena lebih dulu ditentukan. Dari soal primal dapat ditentukan soal dual, yakni Minimumkan

g = bT w

(2.43)

dengan kendala

AT w ≥ c

(2.44)

w≥0

(2.45)

dengan x adalah penyelesaian dari soal primal dan w penyelesaian dari soal dual. Perhatikan bahwa vektor suku tetap dalam (2.41) menjadi vektor ongkos dalam (2.43) dan sebaliknya vektor ongkos dalam (2.40) menjadi vektor suku


38

tetap dalam (2.44). Sedangkan koefisien matriks kendala (2.41) adalah transpose matriks koefisien kendala (2.44).

Teorema 2.5 Jika x suatu penyelesaian layak dari soal primal dan w penyelesaian layak dari soal dual maka c T x ≤ b T w (berarti nilai f yang bersesuaian dengan soal primal lebih kecil atau sama dengan nilai g yang bersesuaian dengan soal dual) Bukti: ⎡ x1 ⎤ ⎢x ⎥ Misalkan x = ⎢ 2 ⎥ adalah penyelesaian layak dari soal primal ⎢M⎥ ⎢ ⎥ ⎣ xn ⎦ ⎡ w1 ⎤ ⎢w ⎥ dan w = ⎢ 2 ⎥ adalah penyelesaian layak dari soal dual ⎢ M ⎥ ⎢ ⎥ ⎣ wm ⎦

Maka

n

∑a j =1

ij

x j ≤ bi , untuk i = 1,K , m

Bila kedua ruas dikalikan dengan wi , maka didapatkan n

wi ∑ aij x j ≤ wi bi , untuk i = 1,K , m j =1

(karena wi ≥ 0 )

Bila dijumlahkan menurut i , maka didapatkan n

n

j =1

j =1

w1 ∑ aij x j + L + wm ∑ aij x j ≤ w1b1 + L + w m bm

Dari persamaan (2.12), maka


39

m

n

m

i =1

j =1

i =1

∑ wi ∑ aij x j ≤ ∑ wi bi w T Ax ≤ w T b Dari persamaan (2.13), maka didapatkan w T Ax ≤ b T w

(2.46)

Karena w penyelesaian layak dari soal dual. Maka

m

∑a i =1

ij

wi ≥ c j ,

untuk j = 1,K, n . Bila kedua ruas dikalikan dengan x j , maka didapatkan m

∑a i =1

ij

wi x j ≥ c j x j , untuk j = 1,K, n

m

∑w a i =1

i

ij

x j ≥ c j x j , untuk j = 1,K, n

Bila dijumlahkan menurut j , maka didapatkan m

m

i =1

i =1

∑ wi ai1 x1 + L + ∑ wi ain xn ≥ c1 x1 + L + cn xn m

∑ w (a i =1

i

x + L + ain x n ) ≥ c1 x1 + L + c n x n

i1 1

m

n

n

i =1

j =1

j =1

∑ wi ∑ aij x j ≥ ∑ c j x j w T Ax ≥ c T x

(2.47)

Dari persamaan (2.46) dan persamaan (2.47), maka c T x ≤ w T Ax ≤ b T w Jadi c T x ≤ b T w . ▄


40

Teorema 2.6 Jika x 0 adalah penyelesaian layak dari soal primal dan w 0 penyelesaian layak dari soal dual dengan c T x 0 = b T w 0 , maka x 0 adalah penyelesaian optimum untuk soal primal dan w 0 penyelesaian optimum untuk

soal dual.

Ini berarti

f maksimum = g minimum .

Bukti: Diketahui c T x 0 = b T w 0 . Dari teorema 2.5, maka c T x ≤ b T w 0 = c T x 0 untuk sebarang penyelesaian layak x . Jadi c T x ≤ c T x 0 berarti x 0 adalah penyelesaian optimum bagi soal primal. Analog dengan bukti di atas, untuk sebarang penyelesaian w bagi soal dual berlaku b T w ≥ c T x 0 = b T w 0 . Jadi b T w ≥ b T w 0 berarti w 0 adalah penyelesaian optimum untuk soal dual. Sehingga f maksimum = c T x 0 = b T w 0 = g minimum . ▄

D. Optimisasi Fungsi Untuk Persoalan Linear 1. Optimisasi Optimisasi merupakan suatu proses penentuan penyelesaian yang terbaik dari suatu masalah. Dalam masalah optimisasi fungsi sasaran adalah mengoptimumkan (memaksimumkan/meminimumkan) nilai suatu fungsi. Perhatikan masalah berikut Minimum kan f (x) , x∈S

dengan x ∈ R n


41

Karena masalah memaksimumkan dapat juga dinyatakan sebagai masalah yang meminimumkan seperti berikut Maksimum f (x) = Minimum (− f (x)) x∈S

x∈S

dan kemudian nilai optimum sasarannya dikalikan dengan -1. Alasan inilah sehingga cukup untuk dibahas masalah minimum saja.

Definisi 2.35 Pembuat Minimum Global Suatu titik x* ∈ S disebut pembuat minimum global f (x) atas S jika untuk setiap x ∈ S berlaku f (x* ) ≤ f (x) .

Definisi 2.36 Pembuat Minimum Lokal Suatu titik x* disebut pembuat minimum lokal f (x) atas S jika untuk setiap

x ∈ S terdapat δ > 0 dan x − x* < δ sedemikian hingga berlaku f (x* ) ≤ f (x) .

2. Kelayakan Definisi 2.37 Titik Layak dan Daerah Layak a. Suatu titik yang memenuhi semua kendala disebut titik layak (feasible point) b. Himpunan dari titik layak-titik layak disebut daerah layak (feasible region) atau himpunan layak (feasible set) dan dinotasikan dengan S .


42

Definisi 2.38 Persekitaran (Neighbourhoods) Persekitaran dari titik x ∈ R n adalah himpunan dari titik – titik

{

}

N ε (x) = y ∈ R n : y − x < ε , dengan ε > 0

(2.48)

Definisi 2.39 Titik Dalam (Interior Point) Suatu titik x * dikatakan titik dalam dari himpunan S jika ada persekitaran dari

x * sedemikian sehingga semua titik dalam persekitaran dari x * juga berada dalam S , yakni

N ε (x * ) ⊂ S

(2.49)

Definisi 2.40 Titik batas Suatu titik x dikatakan titik batas dari himpunan S jika setiap persekitaran dari

x terdiri dari titik yang berada di dalam dan di luar S , dinotasikan N ε ( x) ∩ S ≠ φ ∧ N ε ( x) ∩ S c ≠ φ

(2.50)

E. Metode arah layak Metode arah layak merupakan suatu metode untuk menyelesaikan masalah program linear dengan bergerak dari suatu penyelesaian layak ke penyelesaian layak yang lain pada suatu arah d k sehingga diperoleh nilai sasaran yang lebih baik dengan syarat-syarat yang menyertainya. Pada masalah meminimumkan, ide dasar dari metode arah layak adalah memilih titik awal yang memenuhi semua


43

kendala, kemudian ke titik yang lebih baik sesuai dengan alur iterasi:

x k +1 = x k + α k d k x k adalah penyelesaian layak pada iterasi ke- k ,

d k arah pencarian

α k adalah besar langkah ( α > 0 ) Nilai α dipilih sedemikian sehingga nilai x k +1 tetap berada pada daerah layak. Sedangkan arah langkah d k dipilih sedemikian sehingga pada setiap perpindahan dalam iterasinya tidak melanggar kendala yang diberikan sehingga dapat memperbaiki nilai dari fungsi sasaran. Jadi, titik x k +1 yang diperoleh dipakai sebagai titik baru untuk iterasi berikutnya dan iterasi diulang sampai diperoleh suatu titik (sebut x * ) sedemikian sehingga tidak dapat ditentukan lagi arah layak yang memperbaiki nilai sasaran atau dengan kata lain titik itu sudah memenuhi syarat arah langkah d k yang memperbaiki nilai sasaran.

Definisi 2.41 Arah layak (Feasible direction) Diberikan masalah meminimumkan f (x) dengan kendala x ∈ S dan S adalah himpunan layak. Suatu vektor d ∈ R n , d ≠ 0 adalah arah layak pada x ∈ S jika: ∃α 0 > 0 ∋ x + α d ∈ S , ∀ α ∈ [0, α 0 ]

(2.51)

Selanjutnya, vektor d , d ≠ 0 disebut arah layak yang memperbaiki nilai sasaran (improving feasible direction) pada x ∈ S jika: ∃α 0 > 0 ∋ x + α d ∈ S dan f (x + α d) < f (x) , ∀ α ∈ [0, α 0 ]

(2.52)


44

Dari definisi 2.41, secara umum iterasi dari metode arah layak memerlukan dua langkah, yaitu: 1. Mencari arah layak yang memperbaiki nilai sasaran pada titik yang ditentukan dari tiap iterasinya. 2. Menentukan besar langkah yang berada pada daerah layak sesuai arah layak yang memperbaiki nilai sasaran.

F. Metode Arah Turun Tercuram (Steepest Descent Direction) Metode arah turun tercuram adalah metode arah layak yang dalam menentukan besar langkah α dipilih untuk memperoleh harga maksimum dari penurunan fungsi sasaran pada setiap langkahnya. Metode arah turun tercuram digunakan untuk mencari minimum suatu fungsi, yakni dengan menggunakan nilai negatif dari gradien fungsi di suatu titik. Digunakan nilai negatif dari gradien karena gradien memberikan nilai kenaikan yang semakin besar. Dengan nilai negatif dari gradien maka akan diperoleh nilai penurunan yang semakin besar.


45

BAB III METODE PRIMAL AFFINE SKALING

Metode affine-skaling adalah salah satu kelas dalam metode titik-dalam yang paling sederhana. Dalam tulisan ini akan dibatasi hanya untuk masalah primal program linear yang meminimumkan fungsi sasaran, sehingga metode yang digunakan disebut sebagai metode primal affine-skaling. Penyelesaian masalah program linear menggunakan metode primal affine-skaling dimulai dengan memilih titik-dalam (interior point), namakan x k , dari suatu daerah layak di ruang penyelesaian awal. Kemudian x k ditransformasi oleh transformasi affine-skaling, namakan Tk ,

sedemikian sehingga hasil

transformasi x k diposisikan dekat dengan pusat di ruang penyelesaian hasil transformasi.

Hasil transformasi affine-skaling tersebut namakan

yk .

Selanjutnya dari

y k dijalankan ke titik-dalam lain, yaitu y k +1

menggerakkan nilai

f sampai f optimum. Digunakan arah turun tercuram

yang

(steepest descent), yakni dengan menggunakan nilai negatif dari gradien fungsi yang akan dioptimumkan di suatu titik, yang bertujuan untuk memilih pencapaian jumlah maksimum berkurangnya nilai fungsi sasaran. Penyelesaian yang didapat di ruang penyelesaian tersebut ditransformasikan kembali dengan transformasi invers yang sesuai, yaitu Tk

−1

ke ruang penyelesaian awal. Proses iterasi ini

diulang hingga penyelesaian optimum dicapai.


46

Dalam bab ini akan dibahas yaitu bagaimana metode ini dimulai, bagaimana cara penentuan arah layak perpindahan terbaik dalam memperbaiki f , dan bagaimana proses iterasinya berhenti.

A. Metode Primal Affine-Skaling Untuk menyelesaikan masalah program linear dengan menggunakan metode primal affine-skaling digunakan bentuk primal standar masalah program linear berikut: Minimumkan:

f = cT x

dengan kendala: Ax = b x≥0

(3.1) (3.2) (3.3)

dengan A adalah matriks m × n yang mempunyai rank penuh m , dengan m ≤ n , b adalah vektor yang panjangnya m , c dan x adalah vektor yang panjangnya n .

Definisi 3.1 Daerah Layak Daerah layak dari soal primal adalah himpunan

{

P = x ∈ R n Ax = b, x ≥ 0}

(3.4)

Definisi 3.2 Daerah Layak Dalam Daerah layak dalam dari P adalah himpunan

{

P 0 = x ∈ R n Ax = b, x > 0}

(3.5)


47

Definisi 3.3 Penyelesaian Dalam (Interior Solution) Titik x disebut penyelesaian dalam dari masalah program linear jika x ∈ P 0 dan P0 ≠ φ .

Definisi 3.4 Ortant tak negatif R n+ R n+ disebut ortant taknegatif dari R n jika ∀ x i ∈ R n , x i > 0 dengan i = 1, K , n .

Definisi 3.5 Pusat Vektor e ∈ R n adalah vektor yang setiap elemennya sama dengan 1, yakni ⎡1⎤ ⎢1⎥ e = ⎢ ⎥ . Vektor e disebut sebagai pusat R n+ . ⎢M ⎥ ⎢⎥ ⎣1⎦

Berikut merupakan contoh untuk menentukan dan memperkenalkan titik-dalam dari soal program linear

Contoh 3.1 Minimumkan:

f = −2 x1 + x 2

dengan kendala:

x1 − x 2 ≤ 15 x 2 ≤ 15 x1 , x 2 ≥ 0

Agar menjadi bentuk standar, variabel pengetat ditambahkan pada masalah program linear tersebut, yakni:


48

Minimumkan:

f = −2 x1 + x 2 + 0 x3 + 0 x 4

dengan kendala:

x1 − x 2 + x3 = 15 x 2 + x 4 = 15

x1 , x 2 , x3 , x 4 ≥ 0 Untuk menyelesaikan masalah program linear dengan metode primal affineskaling, diperlukan titik-dalam awal yang memenuhi persamaan (3.5). Untuk menentukan titik-dalam awal dapat digunakan subsitusi mundur atau algoritma Gauss-Jordan. Dalam contoh 3.1 digunakan subsitusi mundur. Matriks lengkap dari persamaan kendala di atas adalah ⎡1 − 1 1 0 15⎤ A=⎢ ⎥ ⎣0 1 0 1 15⎦ Kemudian matriks lengkap dari sistem persamaan kendala diatas diubah menjadi matriks eselon ⎡1 − 1 1 0 15⎤ R1 + R2 ⎡1 0 1 1 30⎤ ⎢0 1 0 1 15⎥ ⎯⎯⎯→⎢0 1 0 1 15 ⎥ ⎣ ⎦ ⎣ ⎦ Setelah didapatkan matriks eselon. Tentukan variabel bebas dan variabel tak bebas.

x3 , x 4 adalah variabel bebas dan x1 , x 2 adalah variabel tak bebas. Ke-

mudian

nyatakan

variabel

bebas

x3 = s dan x 4 = t Dari persamaan terakhir didapat x 2 = 15 − x 4 = 15 − t

Dari persamaan pertama didapatkan x1 = 30 − x3 − x 4 = 30 − s − t

tersebut

dalan

parameter.

Misal


49

Jadi penyelesaian dari persamaan linear tersebut adalah ⎡ x1 ⎤ ⎡30 − s − t ⎤ ⎢ x ⎥ ⎢ 15 − t ⎥ ⎥ x = ⎢ 2⎥ = ⎢ ⎢ x3 ⎥ ⎢ ⎥ s ⎢ ⎥ ⎢ ⎥ t ⎦ ⎣ x4 ⎦ ⎣

Karena bentuk umum penyelesaian dari sistem persamaan linear ini diketahui, beberapa penyelesaian dari sistem persamaan linear ini dapat dicari dengan menentukan nilai s dan t , dengan catatan harus memenuhi persamaan (3.5). Misal s = 7 dan t = 13 , maka didapat

⎡ x1 ⎤ ⎡10⎤ ⎢x ⎥ ⎢ 2 ⎥ 1 x = ⎢ 2⎥ = ⎢ ⎥ ⎢ x3 ⎥ ⎢ 7 ⎥ ⎢ ⎥ ⎢ ⎥ ⎣ x 4 ⎦ ⎣13⎦

adalah penyelesaian dalam untuk soal di atas. ~

1. Transformasi Affine-Skaling Langkah pertama dari metode primal affine-skaling adalah transformasi affine-skaling, yaitu mengubah penyelesaian dalam yang dipilih dengan transformasi affine-skaling sedemikian sehingga penyelesaian dalam yang dipilih diposisikan dekat dengan pusat dari daerah layak. Ide dasar dari transformasi ini, yaitu a. Jika penyelesaian dalam yang dipilih letaknya dekat dengan pusat dari daerah layak seperti titik x1 pada gambar 3.1. Maka dapat dibuat perpindahan ke titik

x * yang maksimum dengan tetap memenuhi kelayakan. Sehingga dihasilkan


50

juga perbaikan nilai fungsi sasaran yang maksimum. Sedangkan jika penyelesaian dalam yang dipilih letaknya dekat batas daerah layak seperti titik x 2 pada gambar 3.1. Maka hanya sedikit perpindahan dapat dibuat dengan tetap memenuhi kelayakan. Sehingga dihasilkan juga perbaikan nilai fungsi sasaran yang kecil. Perpindahan tersebut dilakukan dengan menggunakan arah turun tercuram dari fungsi sasarannya. Dengan demikian arah turun tercuram lebih efektif jika penyelesaian dalam yang dipilih berada dekat dengan pusat dari daerah layak.

x1 x2 x* Gambar 3.1 Ide transformasi affine-skaling

Keterangan:

x * adalah titik optimum yang ingin dicapai, x1 adalah titik-dalam yang dipilih dan letaknya dekat dengan pusat dari daerah layak, x 2 adalah titik-dalam yang dipilih dan letaknya dekat dengan batas dari daerah layak

b. Tanpa harus mengubah soal, suatu transformasi yang sesuai dapat digunakan sedemikian sehingga penyelesaian dalam yang dipilih diposisikan dekat dengan pusat daerah layak.


51

Definisi 3.6 Matriks skaling (Scaling Matrix) Misalkan x k ∈ R n adalah titik-dalam dari ortan tak negatif R n+ yaitu xik > 0 untuk i = 1,L , n . Matriks diagonal n × n dengan elemen diagonalnya adalah titikdalam x k disebut matriks skaling X k , dituliskan sebagai berikut ⎡ x1k ⎢ 0 k X k = diag ( xi ) = ⎢ ⎢M ⎢ ⎣⎢ 0

0 k 2

x M

0

0⎤ ⎥ L 0⎥ O M⎥ ⎥ L x nk ⎦⎥

L

(3.6)

matriks X k adalah matriks nonsingular dengan matriks inversnya, yaitu

Xk

−1

⎡ ⎢ ⎢ ⎛ ⎞ = diag ⎜ 1 k ⎟ = ⎢ ⎝ xi ⎠ ⎢ ⎢ ⎢ ⎣

Karena X k dan X k

−1

−1

x1k 0 M 0

0 1

x 2k M 0

L L O L

0 ⎤ ⎥ 0 ⎥ ⎥ M ⎥ ⎥ 1 k⎥ xn ⎦

(3.7)

adalah matriks diagonal n × n sehingga

(X k )T = X k dan

1

(X k )T = X k

(3.8) −1

(3.9)

Definisi 3.7 Transformasi affine-skaling (Affine-Scaling Tranformation) Misalkan x ≥ 0 , x ∈ R n , transformasi affine-skaling Tk (x) (atau dapat ditulis Tk ) dari R n+ ke R n+ didefinisikan −1

y = Tk (x) = X k x

(3.10)


52

Sifat 3.1 −1

Misalkan Tk (x) ∈ R n+ . Transformasi affine-skaling Tk (x) dengan Tk (x) = X k x adalah transformasi linear. Bukti: a. Untuk sebarang vektor x1 dan x 2 di R n −1

T (x1 + x 2 ) = X k (x1 + x 2 ) −1

−1

= X k x1 + X k x 2 = T (x1 ) + T (x 2 ) −1

b. T ( sx) = X k ( sx) −1

= s ( X k x)

= sT (x) −1

Jadi Tk (x) = X k x adalah transformasi linear. ▄

Transformasi Tk memiliki beberapa sifat yaitu: Sifat 3.2 Jika x k adalah suatu titik-dalam di R n+ maka Tk adalah pemetaan yang terdefinisi dengan baik (well defined) dari R n+ ke R n+ . Bukti: Terdefinisi dengan baik yaitu ∀ x k , y k ∈ R +n , x k = y k ⇒ Tk (x k ) = Tk (y k ) Akan dibuktikan dengan kontrapositifnya, yaitu Tk (x k ) ≠ Tk (y k ) ⇒ x k ≠ y k


53

Misalkan x k , y k ∈ R n+ Bila x k dan y k dikenai transformasi affine-skaling Tk , maka didapat −1

Tk (x k ) = X k x k

dan

−1

Tk (y k ) = X k y k

Karena Tk (x k ) ≠ Tk (y k ) −1

−1

Maka X k x k ≠ X k y k −1

−1

Xk Xk xk ≠ Xk Xk y k Jadi x k ≠ y k Jadi Tk adalah pemetaan yang terdefinisi dengan baik dari R n+ ke R n+ . ▄

Sifat 3.3 Tk memetakan x k ke posisi pusat dari R n+ , yaitu Tk (x k ) = e . Bukti: ⎡ x1k ⎤ ⎢ k⎥ x k Misalkan x = ⎢ 2 ⎥ ∈ R n+ ⎢M⎥ ⎢ k⎥ ⎢⎣ x n ⎥⎦

Bila x k dikenai transformasi affine-skaling Tk , maka didapat −1

Tk (x k ) = X k x k ⎡ ⎢ ⎢ k Tk (x ) = ⎢ ⎢ ⎢ ⎢ ⎣

1

x1k 0

0 1

M

x 2k M

0

0

L L O L

0 ⎤ k ⎥ ⎡ x1 ⎤ 0 ⎥ ⎢ x 2k ⎥⎥ ⎥⎢ M ⎥⎢ M ⎥ ⎥⎢ ⎥ 1 k ⎥ ⎣⎢ x nk ⎦⎥ xn ⎦


54

⎡ x1k ⎤ ⎢ x1k ⎥ ⎡1⎤ ⎢ k ⎥ ⎢⎥ ⎢ x2 ⎥ 1 = ⎢ x 2k ⎥ = ⎢ ⎥ = e ⎢M ⎥ ⎢ M ⎥ ⎢⎥ k ⎢ x n ⎥ ⎣1⎦ ⎢ xk ⎥ n⎦ ⎣

Jadi Tk (x k ) = e . ▄

(3.11)

Secara geometri pemetaan transformasi affine skaling Tk (x k ) dapat diperlihatkan pada ilustrasi dalam R 2 berikut ini

y2

x2

•e

xk

x1

y1

k

Gambar 3.2. Titik-dalam yang dipilih x ditransformasikan oleh Tk ke posisi e .

Sifat 3.4 Jika x adalah titik batas dari S maka Tk (x) adalah titik batas dari T (S ) . Bukti: Dari definisi 2.40, suatu titik x dikatakan titik batas dari S jika setiap persekitaran dari x terdiri dari titik yang berada di dalam dan di luar S , yakni

N ε ( x) ∩ S ≠ φ ∧ N ε ( x) ∩ S c ≠ φ


55

Akan dibuktikan Tk (x) titik batas dari T (S ) Cukup dibuktikan a. N ε (Tk (x)) ∩ T ( S ) ≠ φ b. N ε (Tk (x)) ∩ T ( S c ) ≠ φ Akan dibuktikan a. N ε (Tk (x)) ∩ T ( S ) ≠ φ Bila x dikenai transformasi affine-skaling, maka didapatkan

y = Tk (x) = X k ⎡ ⎢ ⎢ =⎢ ⎢ ⎢ ⎢ ⎣

1

k 1

x 0

0

L

1

M

x 2k M

0

0

L O L

−1

x ⎡ x1 ⎤ 0 ⎤ k ⎥ ⎢ ⎥ ⎡ x1 ⎤ ⎢ x1 ⎥ 0 ⎥ ⎢⎢ x 2 ⎥⎥ ⎢ x 2 ⎥ ⎥ = ⎢ x 2k ⎥ ⎢ ⎥ ⎥ M M ⎢ ⎥ ⎥⎢ ⎥ ⎢ M ⎥ 1 k ⎥ ⎢⎣ x n ⎥⎦ xn xn ⎦ ⎢ k⎥ ⎣ xn ⎦

atau dapat juga ditulis y i =

xi

xik

, dengan i = 1,K , n

Akan dibuktikan dengan kontradiksinya Andaikan N ε (Tk (x)) ∩ T ( S ) = φ Berarti ∀ y i ∈ N ε (Tk (x)) , y i < 0 Pilih y i ∈ N ε (Tk (x)) , dengan x ∈ S Maka y i =

xi

xik

>0

(karena xi > 0 dan xik > 0 )

Timbul kontradiksi maka pengandaian salah


56

Jadi N ε (Tk (x)) ∩ T ( S ) ≠ φ b. N ε (Tk (x)) ∩ T ( s c ) ≠ φ Andaikan N ε (Tk (x)) ∩ T ( s c ) = φ Berarti ∀ y i ∈ N ε (Tk (x)) , y i > 0 Karena N ε (x) ∩ T ( S c ) ≠ φ Maka ada xi < 0 sehingga y i =

xi

xik

<0

(karena xi < 0 dan xik > 0 )

Timbul kontradiksi maka pengandaian salah Jadi N ε (Tk (x)) ∩ T ( S c ) ≠ φ Karena N ε (Tk (x)) ∩ T ( S ) ≠ φ ∧ N ε (Tk (x)) ∩ T ( S c ) ≠ φ Jadi Tk (x) adalah titik batas dari R n+ . ▄

Sifat 3.5 Jika x * adalah titik-dalam dari S maka Tk (x * ) adalah titik-dalam dari T (S ) .

Bukti: Suatu titik x * dikatakan titik-dalam dari S berarti N ε (x * ) ⊂ S Akan dibuktikan Tk (x * ) titik-dalam Cukup dibuktikan N ε (Tk (x * )) ⊂ T ( S ) Andaikan N ε (Tk (x * )) ⊇ T ( S ) Berarti ∃ y i ∈ N ε (Tk (x)) , y i ∈ T ( S c )


57

Karena x * ⊂ S berarti xi* > 0 Dan xik > 0 Maka y i =

xi*

xik

> 0 berarti y i ∈ T (S )

Timbul kontradiksi maka pengandaian salah Jadi N ε (Tk (x * )) ⊂ T ( S ) Jadi Tk (x * ) titik-dalam. ▄

Sifat 3.6 Tk merupakan pemetaan satu-satu (one to one) dan juga pemetaan pada (onto) dengan transformasi invers Tk Tk

−1

−1

, sehingga

(y ) = X k y

(3.12)

Bukti: a. Tk merupakan pemetaan satu-satu (one to one), yaitu (∀ x, y ∈ R n+ ) x ≠ y ⇒ Tk (x) ≠ Tk (y ) Akan dibuktikan dengan kontrapositifnya, yaitu (∀ x, y ∈ R +n ) Tk (x) = Tk (y ) ⇒ x = y Misalkan x, y ∈ R n+ Bila x dan y dikenai transformasi affine skaling, maka didapatkan −1

−1

Tk (x) = X k x dan Tk (y ) = X k y

Karena Tk (x) = Tk (y )


58

−1

−1

Maka X k x = X k y Maka x = y Jadi Tk pemetaan satu-satu b. Tk merupakan pemetaan pada (onto), yaitu (∀y ∈ R n+ ) (∃x ∈ R n+ ) Tk (x) = y Misalkan y ∈ R n+ Klaim x = X k y

(3.13)

Bila x dikenai transformasi affine skaling, maka didapatkan −1

Tk (x) = X k x −1

= Xk Xk y

Tk (x) = y Jadi Tk pemetaan pada Jadi Tk merupakan pemetaan satu-satu dan juga pemetaan pada. ▄

Agar lebih memahami sifat-sifat dari transformasi affine-skaling Tk , perhatikan contoh 3.2 berikut.

Contoh 3.2 ⎡ 3 1 3⎤ Misalkan a, b, c, d, x, y, z di R 3 . Misalkan a = ⎢ , , ⎥ adalah titik-dalam ⎣10 10 5 ⎦


59

⎡1 2⎤ ⎡ 1 6⎤ ⎡3 1 ⎤ b = ⎢ , 0, ⎥ , c = ⎢0, , ⎥ , d = ⎢ , , 0⎥ , x = [1, 0, 0], y = [0,1, 0] , z = [0, 0,1] 3⎦ ⎣ 7 7⎦ ⎣4 4 ⎦ ⎣3

adalah titik batas. Titik-titik a, b, c, d, x, y, z ditransformasi oleh transformasi affine- skaling Tk . Tentukan hasil dari transformasi affine-skaling Tk tersebut. Perhatikan gambar 3.3 berikut

z

Tk (z )

Tk

c

b

Tk (c) T k (b )

a

Tk (a)

y d

x

Tk (x)

Tk (d )

Tk (y )

Gambar 3.3. Titik-dalam a ditransformasikan oleh Tk tetap menghasilkan titik-dalam juga, yaitu Tk (a) , titiktitik pada batas yaitu, b, c, d, x, y , z ditransformasikan Tk tetap menghasilkan titik pada batas juga, yaitu Tk (b), Tk (c), Tk (d) , Tk (x), Tk (y ), Tk (z ) .

Jawab: Misalkan a adalah titik-dalam, maka dapat dibuat matriks skaling X k , yaitu ⎡3 ⎢ 10 Xk = ⎢ 0 ⎢ ⎢⎣ 0

0⎤ ⎡10 0 0⎤ 3 ⎥ ⎥ ⎢ −1 0 ⎥ dan X k = ⎢ 0 10 0 ⎥ ⎢ 0 3 ⎥⎥ 0 5 ⎥ 3⎦ ⎣ 5⎦

0 1 10 0

Dari persamaan (3.10), yaitu −1

Tk (x) = X k x


60

⎡ 3 1 3⎤ Maka bila a = ⎢ , , ⎥ dikenai transformasi affine-skaling, akan diperoleh ⎣10 10 5 ⎦

⎡10 0 0 ⎤ ⎡ 310⎤ ⎡1⎤ 3 ⎥ ⎥⎢ ⎢ Tk (a) = ⎢ 0 10 0 ⎥ ⎢ 1 ⎥ = ⎢⎢1⎥⎥ = e . Sesuai dengan sifat 3.3 ⎢ 10⎥ ⎢ 0 0 5 ⎥ ⎢ 3 ⎥ ⎢⎣1⎥⎦ 3⎦ ⎣ 5 ⎦ ⎣ ⎡1 2⎤ ⎡ 1 6⎤ ⎡3 1 ⎤ Misalkan b = ⎢ , 0, ⎥ , c = ⎢0, , ⎥ , d = ⎢ , , 0⎥ , x = [1, 0, 0], y = [0,1, 0] , 3⎦ ⎣ 7 7⎦ ⎣4 4 ⎦ ⎣3 z = [0, 0,1] adalah titik pada batas

Maka bila b, c, d, x, y , z dikenai transformasi affine-skaling Tk , akan diperoleh ⎡10 0 ⎢ 3 Tk (b) = ⎢ 0 10 ⎢ 0 0 ⎣

0 ⎤ ⎡ 1 ⎤ ⎡10 ⎤ ⎥ ⎢ 3⎥ ⎢ 9⎥ 0 ⎥⎢ 0 ⎥ = ⎢ 0 ⎥ 5 ⎥ ⎢ 2 ⎥ ⎢10 ⎥ 3⎦ ⎣ 3⎦ ⎣ 9⎦

⎡10 0 0 ⎤⎡ 0 ⎤ ⎡ 0 ⎤ ⎥ ⎥⎢ ⎥ ⎢ ⎢ 3 Tk (c) = ⎢ 0 10 0 ⎥ ⎢ 1 ⎥ = ⎢10 ⎥ ⎢ 7⎥ ⎢ 7⎥ ⎢ 0 0 5 ⎥ ⎢ 6 ⎥ ⎢10 ⎥ 3⎦ ⎣ 7⎦ ⎣ 7⎦ ⎣ ⎡10 0 0 ⎤ ⎡ 3 4⎤ ⎡5 2⎤ 3 ⎥⎢ ⎥ ⎢ ⎥ ⎢ Tk (d) = ⎢ 0 10 0 ⎥ ⎢ 1 ⎥ = ⎢ 5 ⎥ ⎢ 4⎥ ⎢ 2⎥ ⎢ 0 0 5 ⎥⎢ 0 ⎥ ⎢ 0 ⎥ 3⎦ ⎣ ⎦ ⎣ ⎦ ⎣ ⎡10 0 0 ⎤ ⎡1⎤ ⎡10 ⎤ 3 ⎢ 3⎥ ⎥ ⎢ Tk (x) = ⎢ 0 10 0 ⎥ ⎢⎢0⎥⎥ = ⎢ 0 ⎥ ⎢ 0 0 5 ⎥ ⎢⎣0⎥⎦ ⎢ 0 ⎥ 3⎦ ⎦ ⎣ ⎣ ⎡10 0 0 ⎤ ⎡0 ⎤ ⎡ 0 ⎤ ⎥ ⎢ 3 Tk (y ) = ⎢ 0 10 0 ⎥ ⎢⎢1⎥⎥ = ⎢⎢10⎥⎥ ⎢ 0 0 5 ⎥ ⎢⎣0⎥⎦ ⎢⎣ 0 ⎥⎦ 3⎦ ⎣


61

⎡10 0 0 ⎤ ⎡0 ⎤ ⎡ 0 ⎤ ⎢ ⎥ ⎥ ⎢ 3 Tk (z ) = ⎢ 0 10 0 ⎥ ⎢⎢0⎥⎥ = ⎢ 0 ⎥ ⎢ 0 0 5 ⎥ ⎢⎣1⎥⎦ ⎢ 5 ⎥ 3⎦ ⎣ 3⎦ ⎣

Maka didapatkan Tk (b) , Tk (c) , Tk (d) , Tk (x) , Tk (y ) , Tk (z ) yang merupakan titik pada batas di R 3 . Sesuai dengan sifat 3.4. ~

2. Menentukan Arah Layak Setelah titik-dalam yang dipilih x k ditransformasi oleh tranformasi affine- skaling Tk , langkah selanjutnya adalah menentukan ke arah mana suatu titik itu akan menuju ke titik yang lebih baik (titik optimum) pada nilai fungsi, dengan catatan arahnya adalah arah layak yaitu arah yang tetap pada daerah layak.

a. Bentuk Masalah Program Linear di Ruang Penyelesaian Hasil Transformasi Andaikan x k adalah penyelesaian dalam yang diketahui dari soal program linear berikut Minimumkan:

f = cT x


(3.14) (3.15) (3.16)

dengan A adalah matriks m × n yang mempunyai rank penuh m , dengan m ≤ n , b adalah vektor yang panjangnya m , dan c, x adalah vektor yang panjangnya n .

Namakan soal A.


62

Penyelesaian dalam x k ditransformasi oleh transformasi affine-skaling Tk diposisikan ke e . Dari persamaan (3.13) yakni x = X k y , maka •

Fungsi sasaran f = cT x dari persamaan (3.14) dapat dituliskan f = cT (X k y) Dari persamaan (3.8), maka didapatkan f = (c T X k )y T

= ( X k c) T y

•

•

= (c k ) T y

(3.17)

dengan c k = X k c

(3.18)

Himpunan kendala Ax = b dari persamaan (3.15) dapat dituliskan

AX k y = b

(3.19)

atau A k y = b

(3.20)

dengan A k = AX k

(3.21)

Dengan kendala tak negatif di ruang penyelesaian hasil transformasi, yaitu

y≥0

( karena x ≥ 0 )

(3.22)

Dengan demikian didapatkan soal program linear yang bersesuaian (berkorespondensi) di ruang penyelesaian hasil transformasi, yaitu Minimumkan:

f = (c k ) T y

(3.23)

dengan kendala:

Ak y = b

(3.24)

y≥0

(3.25)

dengan c k = X k c dan A k = AX k .


63

A k adalah matriks m × n yang mempunyai rank penuh m , dengan m ≤ n , b adalah vektor yang panjangnya m , c k dan y adalah vektor yang panjangnya n . Namakan soal B.

Contoh 3.3 Minimumkan:

f = −5 x1 − x 2

dengan kendala:

2 x1 + 3 x 2 ≤ 12

(1.a)

2 x1 + x 2 ≤ 8

(2.a)

x1 , x 2 ≥ 0

Namakan soal A Ubahlah soal A di atas ke bentuk soal B.

Penyelesaian: Bentuk standar soal A program linear tersebut, yakni: Minimumkan:

f = −5 x1 − x 2 + 0 x3 + 0 x 4

dengan kendala:

2 x1 + 3 x 2 + x3 = 12

(1.a’)

2 x1 + x 2 + x 4 = 8

(2.a’)

x1 , x 2 , x3 , x 4 ≥ 0 ⎡− 5⎤ ⎢ − 1⎥ ⎡2 3 1 0⎤ ⎡12⎤ dengan c = ⎢ ⎥ , A = ⎢ , b=⎢ ⎥ ⎥ ⎢0⎥ ⎣2 1 0 1⎦ ⎣8⎦ ⎢ ⎥ ⎣0⎦


64

⎡1 ⎤ ⎢ 2⎥ 2 Misal dipilih titik-dalam awalnya x1 = ⎢ ⎥ ⎢5⎥ ⎢ ⎥ ⎢⎣ 5 ⎥⎦ Kemudian dibuat matriks skaling X k , yaitu ⎡1 ⎢ 2 0 Xk = ⎢ ⎢0 ⎢ ⎣⎢ 0

0 0 0⎤ ⎥ 2 0 0⎥ 0 5 0⎥ ⎥ 0 0 5⎦⎥

Dari persamaan (3.18) yakni c k = X k c , diperoleh ⎡1 ⎢ 2 0 ck = ⎢ ⎢0 ⎢ ⎢⎣ 0

0 0 0 ⎤ ⎡ − 5⎤ ⎡ − 5 ⎤ ⎥ ⎢ ⎥ ⎢ 2⎥ 2 0 0 ⎥ ⎢ − 1⎥ ⎢ − 2 ⎥ = 0 5 0⎥ ⎢ 0 ⎥ ⎢ 0 ⎥ ⎥ ⎥⎢ ⎥ ⎢ 0 0 5⎥⎦ ⎣ 0 ⎦ ⎣⎢ 0 ⎦⎥

Dari persamaan (3.21) yakni A k = AX k , diperoleh ⎡1 ⎢ 2 ⎡2 3 1 0⎤ ⎢ 0 Ak = ⎢ ⎥ ⎣2 1 0 1 ⎦ ⎢ 0 ⎢ ⎣⎢ 0

0 0 0⎤ ⎥ 2 0 0⎥ ⎡1 6 5 0⎤ =⎢ ⎥ 0 5 0⎥ ⎣1 2 0 5⎦ ⎥ 0 0 5⎦⎥

Sehingga didapatkan suatu soal B yang bersesuaian dengan soal A, yaitu

Minimumkan:

⎡ y1 ⎤ ⎢y ⎥ −5 −2 0 0 ⎢ 2⎥ 2 ⎢ y3 ⎥ ⎢ ⎥ ⎣ y3 ⎦

[

]


65

⎡ y1 ⎤ ⎢ ⎥ ⎡1 6 5 0⎤ ⎢ y 2 ⎥ ⎡12⎤ dengan kendala: ⎢ =⎢ ⎥ ⎥ ⎣1 2 0 5⎦ ⎢ y 3 ⎥ ⎣ 8 ⎦ ⎢ ⎥ ⎣ y3 ⎦

y i ≥ 0 , i = 1,..,4

Agar dapat dinyatakan secara grafik abaikan saja variabel pengetatnya. Maka soal B dapat ditulis lagi sebagai berikut: Minimumkan:

−

5 y1 − 2 y 2 2

dengan kendala: y1 + 6 y 2 ≤ 12 y1 + 2 y 2 ≤ 8

(1.b) (2.b)

y i ≥ 0 , i = 1,2 Dari Gambar 3.4 diperlihatkan bahwa daerah layak dari soal A yaitu segi empat yang diarsir.

Gambar 3.4 Daerah layak soal A


66

Dari Gambar 3.5 diperlihatkan daerah layak A pada gambar 3.4 yang sudah ditransformasi oleh transformasi affine skaling sehingga menghasil segi empat yang diarsir yang merupakan daerah layak dari soal B.

Gambar 3.5 Daerah layak soal B

b. Menentukan Arah Layak

Dalam menentukan arah layak harus ditentukan apakah arah layak tersebut merupakan arah yang menuju ke titik yang lebih baik, yaitu ke titik yang memberikan nilai optimum fungsi sasaran. Oleh karena itu akan ditentukan arah layak yang memperbaiki nilai fungsi sasaran tersebut. Perhatikan soal B berikut: Minimumkan:

f = (c k ) T y

dengan kendala: A k y = b y≥0

(3.26) (3.27) (3.28)

dengan c k = X k c dan A k = AX k . dengan A k adalah matriks berukuran m × n yang mempunyai rank m , dengan


67

m ≤ n , b adalah vektor yang panjangnya m , c k dan y adalah vektor yang panjangnya n . Dengan memperhatikan soal B , akan ditentukan apakah d ky merupakan arah layak dan apakah d ky tersebut merupakan arah yang memperbaiki nilai fungsi sasaran. Misal y k adalah penyelesaian layak, kemudian y k akan dijalankan ke suatu titik layak lain yaitu y k +1 (yaitu titik dengan perubahan nilai sasarannya) di ruang penyelesaian hasil transformasi sesuai dengan alur iterasi berikut: y k +1 = y k + α k d ky

(3.29)

dengan: y k adalah penyelesaian layak pada iterasi ke- k , d ky adalah arah perpindahan di ruang penyelesaian hasil transformasi

α k adalah besar langkah (α k > 0) Nilai α k dipilih sedemikian sehingga nilai y k +1 tetap berada pada daerah layak. Sedangkan arah langkah d ky dipilih sedemikian sehingga pada setiap perpindahan dalam iterasinya tidak melanggar kendala yang diberikan sehingga dapat memperbaiki nilai dari fungsi sasaran. Menurut definisi 2.41, yakni d , dengan d ≠ 0 merupakan arah layak pada

y∈S

∀ α ∈ [0, α 0 ] .

jika terdapat

α0 > 0

sedemikian sehingga

y +α d∈S ,


68

Maka vektor tak nol d ky merupakan arah layak jika memenuhi kendala persamaan: A k y k +1 = b

dengan

(3.30)

y k +1 = y k + α k d ky ≥ 0

Dimana (y k + α k d ky ) merupakan kendala tak negatif untuk setiap α k ∈ [0, α 0 ] dan y k ∈ S . Dari persamaan (3.29), maka A k (y k + α k d ky ) = b

Karena A k y = b , maka A k y k + A k α k d ky = b b + A k α k d ky = b A k α k d ky = 0

Maka untuk nilai α k yang cukup kecil dan positif, nilai α k dapat diabaikan Maka didapatkan A k d ky = 0

(3.31)

Jadi d ky pasti berada di ruang nol dari matriks A k = AX k . Sehingga d ky merupakan penyelesaian di ruang nol matriks A k . Pada kendala tak negatif yakni y k + α k d ky ≥ 0 dengan α k > 0 , diketahui nilai y ik , yaitu y ik > 0 atau y ik = 0 ; sedangkan nilai (d yk ) i yang mungkin adalah


69

1. (d yk ) i > 0 atau (d yk ) i ≥ −

y ik

αk

jika y ik > 0

2. (d yk ) i ≥ 0 jika y ik = 0 Jadi, dari uraian di atas d ky merupakan arah layak jika hanya jika: 1. A k d ky = 0 2. (d yk ) i ≥ −

y ik

αk

jika y ik > 0

3. (d yk ) i ≥ 0 jika y ik = 0 untuk setiap i = 1,2,L, n

Selanjutnya akan ditunjukkan apakah d ky merupakan arah layak yang memperbaiki nilai sasaran, menurut definisi (2.41). Perhatikan bentuk y + αd

Bentuk ini merupakan titik baru iterasi, artinya fungsi f (y ) didekati atau dihampiri melalui tiap iterasi sampai pada titik y dengan arah d yang menghasilkan titik baru

y + αd

(3.32)

Dari definisi (2.41), untuk masalah meminimumkan f (y ) , arah d merupakan arah yang memperbaiki nilai sasaran jika:

f (y + α d) < f (y ) atau

f ( y + α d) − f ( y ) < 0

(3.33)

Atau, sesuai dengan alur iterasi dapat ditulis f (y k +1 ) − f (y k ) < 0

(3.34)


70

Dapat juga ditulis (c k ) T y k +1 − (c k ) T y k < 0

(3.35)

Dari persamaan (3.29), maka (c k ) T (y k + α k d ky ) − (c k ) T y k < 0 (c k ) T y k + (c k ) T α k d ky − (c k ) T y k < 0 (c k ) T α k d ky + (c k ) T y k − (c k ) T y k < 0

didapatkan (c k ) T α k d ky < 0

(3.36)

Maka untuk nilai α k yang cukup kecil dan positif, nilai α k dapat diabaikan. Maka didapatkan (c k ) T d ky < 0

(3.37)

Jadi, d ky merupakan arah layak yang memperbaiki, yaitu yang menunjukan bahwa f (y k +1 ) − f (y k ) < 0 , jika (c k ) T d ky < 0

(3.38)

c. Perumusan Arah Langkah Dengan Arah Turun Tercuram

Akan ditentukan perumusan vektor arah perpindahan dengan arah turun tercuram. Misalkan matriks A k berukuran m × n yang mempunyai rank m . Misalkan N ( A k ) menyatakan ruang nol dari matriks A k dituliskan sebagai berikut


71

N ( A k ) = { d ky ∈ R n

A k d ky = 0}

T

(3.39) T

Dan R( A k ) menyatakan ruang jawab dari A k , dituliskan sebagai berikut

{

R ( A k ) = y ∈ R n y = A k z, untuk z ∈ R m T

T

}

Dari teorema 2.4 telah diperlihatkan ruang nol

(3.40)

dan ruang jawab

merupakan subruang dari R n yang saling orthogonal. Jadi N ( A k ) ⊥ R( A k ) . T

Misalkan d ky ∈ N ( A k ) dan y ∈ R( A k ) dan c k = d ky + y , c k ∈ R n . T

Perhatikan gambar 3.6

− ck yk d ky

y k +1

Gambar 3.6 Gradien negatif dari fungsi

f (y ) , yaitu − c k

diproyeksikan ke ruang nol A k agar tercipta arah layak d y . k

d ky dapat juga dituliskan sebagai d ky = c k − y

Karena y = A k z , maka didapatkan T

d ky = c k − A k z T

(3.41)


72

Bila kedua ruas dikalikan dengan A k , maka didapatkan A k d ky = A k c k − A k A k z T

Karena A k d ky = 0 , maka didapatkan 0 = Akck − Ak Ak z T

Akck = Ak Ak z T

z = ( A k A k ) −1 A k c k T

(3.42)

Subsitusikan persamaan (3.42) ke persamaan (3.41), maka didapatkan d ky = c k − A k ( A k A k ) −1 A k c k T

T

= [ I − A k ( A k A k ) −1 A k ] c k T

T

= Pk c k

(3.43)

dengan Pk = [ I − A k ( A k A k ) −1 A k ] T

T

(3.44)

Pk = I − A Tk ( A k A Tk ) −1 A k disebut matriks proyeksi orthogonal pada ruang nol Ak

Perhatikan bahwa y ∈ R( A k ) , maka berdasarkan persamaan (3.42) T

y = A k z = A k ( A k A k ) −1 A k c k = R k c k T

T

T

dengan R k = A k ( A k A k ) −1 A k T

T

Perhatikan persamaan (3.44), karena A k = AX k maka Pk = I − ( AX k ) T (( AX k )( AX k ) T ) −1 ( AX k )

(3.45) (3.46)


73

= I − ( X k A T )((AX k )( X k A T )) −1 AX k 2

= I − ( X k A T )( AX k A T ) −1 AX k

(3.47)

Perhatikan persamaan (3.43), yakni didapatkan arah perpindahan d ky = Pk c k . Karena tujuan kita adalah meminimumkan nilai dari fungsi sasaran,

maka digunakan gradien negatif dari fungsi f (y k ) , yaitu − c k untuk diproyeksikan pada ruang nol matriks A k . Digunakan nilai negatif dari gradien karena gradien memberikan nilai kenaikan yang semakin besar. Dengan nilai negatif dari gradien maka akan diperoleh nilai penurunan yang semakin besar. Sehingga tercipta arah d ky terbaik dengan perubahan nilai fungsi sasaran yang maksimum serta menurunkan nilai fungsi sasaran dari soal B. Seperti digambarkan pada gambar 3.6.

Arah perpindahan d ky dengan arah turun tercuram dapat dituliskan d ky = Pk (−c k )

(3.48)

Dari persamaan (3.47) dan persamaan (3.18), maka persamaan (3.48) dapat dituliskan 2

d ky = −[I − X k A T ( AX k A T ) −1 AX k ]X k c

(3.49)


74

3. Menentukan Besar langkah α k

Setelah dapat ditentukan arah langkah d ky yang memperbaiki nilai sasaran maka selanjutnya akan ditentukan sejauh mana arah ini bergerak menuju tiitk optimum. Diberikan vektor awal y k dan d ky adalah suatu arah layak yang memperbaiki nilai fungsi sasaran. Untuk menentukan vektor berikutnya yaitu y k +1 = y k + α k d ky

besar langkah α k dapat diperoleh dengan mencari penyelesaian dari masalah Minimumkan:

f (y k + α k d ky )

dengan kendala:

A k (y k + α k d ky ) = b y k + α k d ky ≥ 0

αk ≥ 0 Perhatikan bahwa: A k y k = b dan Akdk = 0

Maka A k (y k + α k d ky ) = b dipenuhi untuk setiap α k ≥ 0

Dalam kendala tak negatif diperoleh bahwa y k + α k d ky ≥ 0

(3.50)

Dengan demikian untuk (d yk ) i ≥ 0 maka batas maksimum α k agar persamaan (3.50) tetap terpenuhi adalah α k maks = ∞ .


75

Dan untuk (d yk ) i < 0 maka batas maksimum α k agar persamaan (3.50) tetap terpenuhi didapat dari bentuk y ik + α k (d yk ) i ≥ 0 ⇔ α k ≥

− y ik (d yk ) i

sehingga batas maksimumnya merupakan minimum dari

y ik , untuk − (d yk ) i

i = 1,2,K , n . Dari sifat 3.3, maka y ik 1 . = k − (d y ) i − (d yk ) i

Sehingga untuk menentukan suatu besar langkah yang maksimum dan agar persamaan (3.50) tetap terpenuhi maka dipilih 0 < α < 1 , yaitu dipilih α = 0.99 sehingga

α 1 = k − (d y ) i − (d yk ) i

αk = α Jadi

⎧⎪ 0.99 ⎫⎪ k ( ) < 0 d ⎬ y i k ⎪⎩ − (d y ) i ⎪⎭

α k = min ⎨ i

(3.51)

Dengan demikian masalah di atas dapat diubah menjadi masalah pencarian besar langkah Minimumkan:

f (y k + α k d ky )

dengan kendala:

0 ≤ α ≤ α maks


76

⎧ ⎧⎪ 0.99 ⎫⎪ ; d yk < 0⎬ ⎪min ⎨ k k ⎪ ⎪⎩ − (d y ) i ⎪⎭ jika d < 0 dengan α k = ⎨ jika d k ≥ 0 ⎪∞ ⎪ ⎩

Langkah selanjutnya adalah memetakan penyelesaian baru y k +1 kembali ke ruang penyelesaian awal, agar didapat suatu perpindahan penyelesaian x k +1 untuk soal A. Hal ini dapat dilakukan dengan menggunakan transformasi invers Tk−1 , yakni x k +1 = Tk−1 (y k +1 ) .

Dari persamaan (3.12), maka didapatkan x k +1 = Tk−1 (y k +1 ) = X k y k +1

Dari persamaan (3.29), maka didapatkan x k +1 = X k (y k + α k d ky ) = X k y k + α k X k d ky

Dari persamaan (3.13), maka didapatkan x k +1 = x k + α k X k d ky

(3.52)

x k +1 = x k + α k d kx

(3.53)

dengan d kx = X k d ky

(3.54)

Ini berarti arah perpindahan di ruang penyelesaian awal yaitu d kx , dengan d kx = X k d ky dan besar langkahnya adalah α k .


77

Perhatikan kembali persamaan (3.52), yaitu x k +1 = x k + α k X k d ky

Dari persamaan (3.49), maka 2

x k +1 = x k − α k X k [(I − X k A T ( AX k A T ) −1 AX k ) X k c] 2

2

2

= x k − α k X k [c − A T ( AX k A T ) −1 AX k c] 2

= x k − α k X k [c − A T w k ] 2

(3.55)

2

dengan w k = ( AX k A T ) −1 AX k c

(3.56)

Perhatikan persamaan (3.55), arah perpindahan di ruang penyelesaian awal dapat juga ditulis 2

d kx = − X k [c − A T w k ]

(3.57)

Perhatikan kembali persamaan (3.49), yaitu 2

d ky = −[I − X k A T ( AX k A T ) −1 AX k ]X k c 2

2

= − X k c + X k A T ( AX k A T ) −1 AX k c

Dari persamaan (3.56), maka didapatkan d ky = − X k c + X k A T w k

= −X k [ c − A T w k ]

(3.58)

atau

d ky = − X k r k

(3.59)

dengan

r k = c − AT w k

(3.60)


78

Ada dua pengamatan penting yang perlu diperhatikan disini: Pengamatan 1

Misalkan d ky = −Pk c k dan d kx = X k d ky . Misalkan Pk adalah pemetaan proyeksi, maka dapat dilihat bahwa c T x k +1 = c T (x k + α k d kx ) = c T (x k + α k X k d ky )

Dari persamaan (3.8), maka didapatkan c T x k +1 = c T x k + α k c T X k d ky T

= c T x k + α k ( X k c) T d ky

Dari persamaan (3.18) , maka didapatkan c T x k +1 = c T x k + α k (c k ) T d ky

Dari persamaan (3.48), maka didapatkan c T x k +1 = c T x k − α k (c k ) T Pk c k

Dari sifat 2.1 , yakni , PP = P dan P T = P maka didapatkan

c T x k +1 = c T x k − α k (c k ) T Pk Pk c k = c T x k − α k (c k ) T PkT Pk c k = c T x k − α k (Pk c k ) T Pk c k = c T x k − α k (−Pk c k ) T (−Pk c k )

Dari persamaan (2.15), maka

c T x k +1 = c T x k − α k d ky

2

(3.61)


79

Sehingga jika arah perpindahan d ky ≠ 0 ini berarti ada perpindahan yang terjadi dari x k ke x k +1 .

Sedangkan jika d ky = 0 ini berarti c T x k +1 = c T x k , maka

x k = x k +1 berarti sudah tidak terjadi perpindahan, maka proses iterasi berhenti.

Beberapa teorema yang penting untuk kondisi arah layak d ky diberikan oleh teorema berikut: Teorema 3.1

Misalkan x k ∈ P 0 . Misalkan d ky pada ruang nol dari A k dengan d ky > 0 maka nilai fungsi sasaran f masalah program linear dari soal A adalah tak terbatas (unbounded), maka soal A tidak mempunyai penyelesaian optimum. Bukti:

Diketahui x k ∈ P 0 maka x k ∈ R n dengan Ax k = b , x k > 0 Karena d ky pada ruang nol dari A k dengan d ky > 0 Maka y k +1 = y k + α k d ky adalah layak untuk soal B, untuk setiap α k > 0 Dari persamaan (3.61), yakni c T x k +1 = c T x k − α k d ky

2

Sehingga untuk (d yk ) i > 0 maka batas maksimum α k yang memenuhi y k +1 = y k + α k d ky adalah α k maks = ∞

Maka c T x k +1 akan mencapai − ∞ atau tak terbatas Maka soal A tidak mempunyai penyelesaian optimum. ▄


80

Teorema 3.2

Misalkan x k ∈ P 0 .

Misalkan d ky pada ruang nol A k dengan d ky = 0 maka

penyelesaian layak dari soal A adalah penyelesaian optimum. Bukti:

Diketahui x k ∈ P 0 maka x k ∈ R n dengan Ax k = b , x k > 0 Diketahui d ky = − Pk c k , dengan Pk matriks proyeksi pada ruang nol A k Karena d ky = 0 Maka d ky = −Pk c k = −(I − A Tk ( A k A Tk ) −1 A k )c k = 0 A Tk ( A k A Tk ) −1 A k c k − c k = 0 A Tk ( A k A Tk ) −1 A k c k = c k A Tk u k = c k

dengan u k = ( A k A Tk ) −1 A k c k Perhatikan bahwa sebenarnya u k = w k , dengan A k = AX k . Dari persamaan (3.18) dan persamaan (3.21), maka didapatkan ( AX k ) T u k = X k c Dari persamaan (3.8), maka didapatkan ( AX k ) T u k = X k c T

Dari persamaan (2.13), maka didapatkan (u k ) T AX k = c T X k (u k ) T AX k X −k 1 = c T X k X −k 1


81

(u k ) T A = c T Misalkan x adalah penyelesaian layak dari Ax = b , maka (u k ) T Ax = c T x (u k ) T b = c T x b T (u k ) = c T x

Dengan menggunakan teorema 2.6, diperoleh x penyelesaian optimum soal primal. ▄

Pengamatan 2

Jika x k adalah vertek, maka persamaan (3.56), yakni 2

2

w k = ( AX k A T ) −1 AX k c

Dapat disederhanakan menjadi w k = (B T ) −1 c B 2

(3.62) 2

dengan B T = ( AX k A T ) dan c B = AX k c Perhatikan persamaan (3.62), bila kedua ruas dikalikan dengan B T maka didapatkan B T w k = B T (B T ) −1 c B BT w k = c B

Vektor w k disebut sebagai penduga dual (dual estimates) yang bersesuaian dengan penyelesaian primal x k .


82

Perhatikan persamaan (3.60), yakni r k = c − AT w k

Persamaan (3.60) di atas dapat disederhanakan menjadi

r k = c − A T (B T ) −1 c B r k disebut vektor ongkos tereduksi (reduced cost vector) yang bersesuaian

dengan x k . Misalkan x k penyelesaian primal . Bila x k dikenai transformasi affine-skaling, maka −1

Tk (x k ) = X k x k

Dari sifat 3.3, yakni Tk (x k ) = e −1

Maka e = X k x k Bila kedua ruas ditransposkan, maka didapatkan −1

eT = (X k x k )T

Dari persamaan (3.9), maka didapatkan e T = (x k ) T X k

−1

−1

e T X k = (x k ) T X k X k

e T X k = (x k ) T

Dari persamaan (3.8), maka didapatkan e T X k = (x k ) T T

( X k e) T = ( x k ) T Bila dikalikan dengan r k , maka ( X k e) T r k = ( x k ) T r k


83

Jika r k ≥ 0 , maka penduga dual w k akan menjadi penyelesaian layak dual. Dan ( X k e) T r k = (x k ) T r k disebut duality gap dari pasangan penyelesaian layak (x k , w k ) , yakni cT x k − b T w k = eT X k r k

(3.63)

Perhatikan persamaan (3.63) tersebut, jika e T X k r k = 0 dan r k ≥ 0 , maka

c T x k = b T w k , artinya bahwa penyelesaian layak soal primal , yaitu x k sama dengan penyelesaian layak soal dual, yaitu w k . Dari teorema 2.6, maka x k adalah penyelesaian optimum soal primal dan w k adalah penyelesaian optimum soal dual.

B. Algoritma Primal Affine-Skaling

Dari uraian pada bagian-bagian sebelumnya, maka algoritma primal affine- skaling untuk masalah:

Minimumkan:

f = cT x


dengan A adalah matriks m × n yang mempunyai rank penuh m dan m ≤ n , b adalah vektor yang panjangnya m , c, x adalah vektor yang panjangnya n . Dapat disusun sebagai berikut: Langkah 1 : (Inisialisasi)

Pilih titik-dalam awal x k yang memenuhi:


84

Ax k = b

Ambil k = 1 dan lanjutkan ke langkah 2. Langkah 2 : (Menentukan vektor penduga dual)

Menentukan vektor penduga dual dengan aturan 2

2

w k = ( AX k A T ) −1 AX k c

dengan X k adalah matriks diagonal yang elemen diagonalnya adalah komponenkomponen dari x k . Langkah 3 : (Menentukan vektor ongkos tereduksi)

Menentukan vektor ongkos tereduksi dengan aturan r k = c − AT w k Langkah 4 : (Uji keoptimalan)

Jika r k ≥ 0 dan e T X k r k ≤ ε ( ε adalah bilangan positif kecil yang diberikan) maka proses berhenti. Dengan demikian x k sudah optimum. Selainnya lanjutkan ke langkah selanjutnya. Langkah 5 : (Menentukan arah perpindahan d ky )

Menentukan arah perpindahan d ky dengan aturan d ky = − X k r k

Langkah 6 : (Cek untuk nilai f tak terbatas atau f sudah optimum)

Jika d ky > 0

maka proses berhenti.

Berarti f tak terbatas maka soal tak

mempunyai penyelesaian. Jika d ky = 0 maka proses berhenti. Berarti f sudah


85

optimum maka x k adalah penyelesaian optimum soal primal. Selainnya lanjutkan ke langkah selanjutnya Langkah 7 : (Menentukan besar langkah)

Menentukan besar langkah dengan aturan

⎧⎪ α ⎫⎪ k < ( d ) 0 ⎬ , dimana 0 < α < 1 y i k ⎪⎭ ⎩⎪ − (d y ) i

α k = min ⎨ i

dengan α = 0.99 Langkah 8 (Menentukan titik baru)

Menentukan titik baru dengan aturan x k +1 = x k + α k X k d ky


86

Flowchart metode primal affine-skaling adalah sebagai berikut: Mulai

Masukkan

x k , c, A, e, ε 2

2

w k = ( AX k A T ) −1 AX k c

r k = c − AT w k

r k ≥ 0 dan eT X k r k ≤ ε

ya

xk penyelesaian optimum

tidak d ky = − X k r k Nilai f tak terbatas

berhenti ya

d>0

tidak

berhenti

xk penyelesaian optimum

d ky = 0

ya tidak

⎧⎪ α k ⎪⎩ - (d y ) i

α k = min ⎨ i

x k +1 = x k + α k X k d ky

berhenti


87

C. Aplikasi Metode Primal Affine-Skaling Untuk Menyelesaikan Masalah Program Linear Dengan Program Matlab.

Contoh 3.4

Selesaikan masalah program linear berikut menggunakan metode primal affineskaling.

Minimumkan:

f = −2 x1 + x 2

dengan kendala: x1 − x 2 ≤ 15 x 2 ≤ 15 x1 , x 2 ≥ 0

Agar menjadi bentuk standar variabel pengetat ditambahkan pada masalah program linear tersebut, yakni: Minimumkan:

f = −2 x1 + x 2 + 0 x3 + 0 x 4

dengan kendala: x1 − x 2 + x3 = 15 x 2 + x 4 = 15

x1 , x 2 , x3 , x 4 ≥ 0

Matriks kendala A , vektor ongkos c , dan misal dipilih titik-dalam x1 dari sistem tersebut, ditulis secara berurutan, yaitu

⎡1 − 1 1 0 ⎤ A=⎢ ⎥, ⎣0 1 0 1 ⎦

⎡ − 2⎤ ⎡10⎤ ⎢1 ⎥ ⎢2⎥ 1 ⎢ ⎥ c= , x =⎢ ⎥ ⎢0⎥ ⎢7⎥ ⎢ ⎥ ⎢ ⎥ ⎣0⎦ ⎣13⎦


88

⎡10 ⎢0 Maka matriks skaling X1 = ⎢ ⎢0 ⎢ ⎣0

0 2 0 0

Listing Program

function pas1 clc; clear; x=input('masukkan titik-dalam x= '); c=input('c = '); A=input('A = '); e=input('e= '); epsilon=input('epsilon = '); X=diag(x); w=inv(A*X*X*A')*A*X*X*c; r=c-A'*w; p=e'*X*r; d=-X*r; norm_d=sqrt(d'*d); d_min=min(d); alpa_maks=min(0.99/-d_min); x_baru=x+alpa_maks*X*d; fprintf('\n w = '); fprintf('\n %3.4f ',w); fprintf('\n\n r = '); fprintf('\n %3.4f ',r); fprintf('\n\n p = '); fprintf('\n %3.4f ',p); fprintf('\n\n d = '); fprintf('\n %3.4f ',d); fprintf('\n\n d min = '); fprintf('\n %3.4f ',d_min);

0 0⎤ ⎡1⎤ ⎥ ⎢1⎥ 0 0⎥ dan e = ⎢ ⎥ , ε = 0.00001 ⎢1⎥ 7 0⎥ ⎥ ⎢⎥ 0 13⎦ ⎣1⎦


89

fprintf('\n\n norm_d = %3.4f ',norm_d); fprintf('\n\n alpa maks = %3.4f ',alpa_maks); fprintf('\n\n x baru = '); fprintf('\n %3.4f ',x_baru); fprintf('\n -------------------------------------------'); while (r<0 | p>epsilon); x=x_baru X=diag(x); w=inv(A*X*X*A')*A*X*X*c; r=c-A'*w; p=e'*X*r; d=-X*r; norm_d=sqrt(d'*d); d_min=min(d); alpa_maks=min(0.99/-d_min); x_baru=x+alpa_maks*X*d;

fprintf('\n w = '); fprintf('\n %3.4f ',w); fprintf('\n\n r = '); fprintf('\n %3.4f ',r); fprintf('\n\n p = '); fprintf('\n %3.4f ',p); fprintf('\n\n d = '); fprintf('\n %3.4f ',d); fprintf('\n\n d min = '); fprintf('\n %3.4f ',d_min); fprintf('\n\n norm_d = %3.4f ',norm_d); fprintf('\n\n alpa maks = %3.4f ',alpa_maks); fprintf('\n\n x baru = '); fprintf('\n %3.4f ',x_baru);


90

fprintf('\n -------------------------------------------'); end; end;

Output

masukkan titik-dalam x= [10;2;7;13] c = [-2;1;0;0] A = [1 -1 1 0;0 1 0 1] e= [1;1;1;1] epsilon = 0.00001 w= -1.3335 -0.0077 r= -0.6665 -0.3258 1.3335 0.0077 p= 2.1187 d= 6.6647 0.6516 -9.3347 -0.1003 d min = -9.3347 norm_d = 11.4887 alpa maks = 0.1061 x baru = 17.0682 2.1382 0.0700 12.8618


91

------------------------------------------x= 17.0682 2.1382 0.0700 12.8618 w= -1.9849 -0.0265 r= -0.0151 -0.9584 1.9849 0.0265 p= -1.8270 d= 0.2573 2.0493 -0.1389 -0.3407 d min = -0.3407 norm_d = 2.0980 alpa maks = 2.9058 x baru = 29.8296 14.8714 0.0417 0.1286 -------------------------------------------


92

⎡29.8296⎤ ⎢14.8714 ⎥ ⎥ Jadi didapat titik optimumnya, yakni x = ⎢ ⎢ 0.0417 ⎥ ⎢ ⎥ ⎣ 0.1286 ⎦ Nilai f = −44.7877

Contoh 3.5

Minimumkan:

f = 100 − 20 x1 − 10 x 2

dengan kendala:

2 x1 − x 2 ≤ 4 3 x1 + x 2 ≤ 11

x1 + 2 x 2 ≤ 8 x1 − 3 x 2 ≤ −3 x1 , x 2 ≥ 0

Penyelesaian:

Bentuk standar program linear tersebut, yakni: Minimumkan:

f = 100 − 20 x1 − 10 x 2 + 0 x3 + 0 x 4 + 0 x5 + 0 x 6

dengan kendala:

2 x1 − x 2 + x 3 = 4 3 x1 + x 2 + x 4 = 11

x1 + 2 x 2 + x5 = 8 x1 − 3x 2 + x 6 = −3 x1 , x 2 , x 3 , x 4 , x 5 , x 6 ≥ 0


93

⎡− 20⎤ ⎢ − 10 ⎥ ⎡2 − 1 ⎥ ⎢ ⎢3 1 ⎢ 0 ⎥ Dengan c = ⎢ ⎥, A = ⎢ ⎢1 2 0 ⎥ ⎢ ⎢ ⎢ 0 ⎥ ⎣1 − 3 ⎥ ⎢ ⎣⎢ 0 ⎦⎥

1 0 0 0

0 1 0 0

0 0 1 0

0⎤ 0⎥⎥ 0⎥ ⎥ 1⎦

⎡13 ⎤ ⎢ 5⎥ ⎢115 ⎥ ⎢ ⎥ Misal dipilih titik-dalam awalnya x1 = ⎢ 1 ⎥ ⎢ 1 ⎥ ⎢ ⎥ ⎢ 1 ⎥ ⎢⎣ 1 ⎥⎦

⎡13 0 0 0 0 0⎤ ⎢ 5 ⎥ ⎢ 0 115 0 0 0 0⎥ ⎢ ⎥ 0 1 0 0 0⎥ Matriks skaling X k = ⎢ 0 ⎢ 0 0 0 1 0 0⎥ ⎢ ⎥ 0 0 0 1 0⎥ ⎢ 0 ⎢⎣ 0 0 0 0 0 1⎥⎦


94

Dari Gambar 3.7 diperlihatkan bahwa daerah layak sebelum ditransformasi oleh transformasi affine-skaling yaitu segi empat yang diarsir.

Gambar 3.7 Daerah layak sebelum dikenai transformasi affine-skaling


95

Dari Gambar 3.8 diperlihatkan daerah layak pada gambar 3.7 yang sudah ditransformasi oleh transformasi affine-skaling.

Gambar 3.8 Daerah layak yang sudah ditransformasi oleh transformasi affine-skaling

Output

masukkan titik-dalam x= [13/5;11/5;1;1;1;1] c = [-20;-10;0;0;0;0] A = [2 -1 1 0 0 0;3 1 0 1 0 0;1 2 0 0 1 0;1 -3 0 0 0 1] e= [1;1;1;1;1;1] epsilon = 0.0001 w= -1.9830 -4.6185 -2.6355 0.6525


96

r= -0.1953 -0.1359 1.9830 4.6185 2.6355 -0.6525 p= 7.7779 d= 0.5078 0.2989 -1.9830 -4.6185 -2.6355 0.6525 d min = -4.6185 norm_d = 5.7430 alpa maks = 0.2144 x baru = 2.8830 2.3410 0.5749 0.0100


97

0.4351 1.1399 ------------------------------------------x= 2.8830 2.3410 0.5749 0.0100 0.4351 1.1399

w= 0.5269 -6.8009 -0.9237 0.2686 r= 0.0042 -0.0191 -0.5269 6.8009 0.9237 -0.2686 p= -0.1719 d=


98

-0.0120 0.0448 0.3029 -0.0680 -0.4019 0.3062 d min = -0.4019 norm_d = 0.5948 alpa maks = 2.4636 x baru = 2.7975 2.5991 1.0040 0.0083 0.0044 1.9996 -------------------------------------------

⎡2.7975⎤ ⎢ 2.5991⎥ ⎥ ⎢ ⎢1.0040 ⎥ Jadi didapatkan titik optimumnya, yakni x = ⎢ ⎥ ⎢0.0083⎥ ⎢0.0044⎥ ⎥ ⎢ ⎢⎣1.9996 ⎥⎦ Nilai optimum f = 18.059


99

BAB IV PENUTUP

A. Kesimpulan

Berdasarkan pembahasan yang telah diuraikan sebelumnya dapat diambil kesimpulan sebagai berikut: 1. Masalah program linear dapat diselesaikan dengan metode titik-dalam yang salah satunya adalah metode primal affine-skaling. 2. Langkah-langkah untuk menyelesaikan masalah program linear dengan metode primal affine-skaling dimulai dengan memilih titik-dalam awal, yaitu x k dari suatu daerah layak di ruang penyelesaian awal. Kemudian x k ditransformasi oleh transformasi affine-skaling, yaitu Tk sedemikian sehingga hasil transformasi x k diposisikan dekat dengan pusat di ruang penyelesaian hasil transformasi ini. Hasil transformasi x k sebut saja y k . Langklah selanjutnya, dari

y k dijalankan ke titik-dalam lain, yaitu y k +1 yang menggerakkan nilai

f sampai f optimum dicapai sesuai dengan alur iterasi y k +1 = y k + α k d ky , dengan d ky adalah arah layak turun tercuram (steepest descent) yang menyebabkan nilai fungsi berkurang dengan cepat. Dan α k adalah besarnya langkah yang menyatakan seberapa jauh arah tersebut akan menuju ke titik optimum yang tetap berada pada daerah layak. Penyelesaian yang didapat di ruang penyelesaian tersebut ditransformasikan kembali dengan transformasi


100

invers, yaitu Tk−1 . Proses iterasi ini diulang hingga penyelesaian optimum dicapai.

B. Saran

Bagi pembaca yang tertarik untuk menyelesaikan masalah program linear dengan metode titik-dalam dapat juga digunakan misalnya metode proyektif (projective method) atau lebih dikenal dengan metode Karmarkar , metode path-following

(path-following method), dan metode potensial-reduksi (potential-reduction method).


101

DAFTAR PUSTAKA

Bhatti, M. A. (1998). Practical Optimization Methods with Mathematica Applications. New york: Springer –Verlag.

Chong, E.K.P. and S.H. Zak (1996). An Introduction to Optimization. New York: Wiley. Fang, S-C and S. Puthenpura. (1993). Linear Optimization and Extensions. Englewood cliffs.NJ: Prentice-Hall. Ignizio, J.P and T.M. Cavalier. (1994). Linear Programming. New Jersey: Prentice-Hall, Inc. Leon, S.J. (1998). Aljabar Linear dan Aplikasinya. Jakarta: Erlangga Nash, G. S. and Ariela Sofer. (1996). Linear and Nonlinear Program-ming. New York : Hill International Editions. Susanta, B. (1994). Program Linear. Jakarta: LPTK Depdikbud. Wono. S. B. (1995). Aljabar Linear. Jakarta: PT Gramedia Pustaka Utama


102

Lampiran


103

Tabel 1. Hasil iterasi contoh 3.4

k

xk

cx k wk

rk

dk

dk

αk T

e Xkr

k

x k +1

Status

1 10 ⎡ ⎤ ⎢2⎥ ⎢ ⎥ ⎢7⎥ ⎢ ⎥ ⎣13⎦ -18 ⎡ − 1.3335 ⎤ ⎢− 0.0077⎥ ⎣ ⎦

2 17 . 0682 ⎡ ⎤ ⎢ 2.1382 ⎥ ⎢ ⎥ ⎢ 0.0700 ⎥ ⎢ ⎥ ⎣12.8618⎦ -31.9982 ⎡ − 1.9849 ⎤ ⎢− 0.0265⎥ ⎣ ⎦

3 29 . 8296 ⎡ ⎤ ⎢14.8714 ⎥ ⎢ ⎥ ⎢ 0.0417 ⎥ ⎢ ⎥ ⎣ 0.1286 ⎦ -44.7878 ⎡− 2.0000⎤ ⎢ − 0.9999⎥ ⎣ ⎦

⎡− 0.6665⎤ ⎢− 0.3258⎥ ⎢ ⎥ ⎢ 1.3335 ⎥ ⎢ ⎥ ⎣ 0.0077 ⎦ ⎡ 6.6647 ⎤ ⎢ 0.6516 ⎥ ⎢ ⎥ ⎢− 9.3347⎥ ⎢ ⎥ ⎣ − 0.1003⎦

⎡ − 0.0151⎤ ⎢− 0.9584⎥ ⎢ ⎥ ⎢ 1.9849 ⎥ ⎢ ⎥ ⎣ 0.0265 ⎦ ⎡ 0.2573 ⎤ ⎢ 2.0493 ⎥ ⎢ ⎥ ⎢ − 0.1389⎥ ⎢ ⎥ ⎣− 0.3407⎦

⎡0.0000⎤ ⎢ 0.0001⎥ ⎢ ⎥ ⎢2.0000⎥ ⎢ ⎥ ⎣0.9999⎦

11.4887

2.0980

0.1061

2.9058

2.1187

-1.8270

⎡17.0682⎤ ⎢ 2.1382 ⎥ ⎢ ⎥ ⎢ 0.0700 ⎥ ⎢ ⎥ ⎣12.8618⎦ Belum optimum

⎡29.8296⎤ ⎢14.8714 ⎥ ⎢ ⎥ ⎢ 0.0417 ⎥ ⎢ ⎥ ⎣ 0.1286 ⎦ Belum optimum

Sudah optimum


104

Tabel 2. Hasil iterasi contoh 3.5 1 2 ⎡13 ⎤ ⎡2.8830⎤ ⎢ 5⎥ ⎢2.3410⎥ ⎢115 ⎥ ⎥ ⎢ ⎢ ⎥ ⎥ ⎢ 0 . 5749 ⎢ 1 ⎥ ⎥ ⎢ ⎢ 1 ⎥ ⎢0.0100⎥ ⎢ ⎥ ⎢ 0.4351⎥ ⎢ 1 ⎥ ⎥ ⎢ ⎢⎣ 1 ⎥⎦ ⎣⎢1.1399 ⎦⎥ 26 18.93 ⎡ − 1.9830 ⎤ ⎡ 0.5269 ⎤ ⎢− 4.6185⎥ ⎢ − 6.8009⎥ ⎢ ⎥ ⎢ ⎥ ⎢− 2.6355⎥ ⎢− 0.9237⎥ ⎢ ⎥ ⎢ ⎥ ⎣ 0.6525 ⎦ ⎣ 0.2686 ⎦ ⎡ − 0.1953⎤ ⎡ 0.0042 ⎤ ⎢− 0.1359⎥ ⎢ − 0.0191⎥ ⎥ ⎥ ⎢ ⎢ ⎢ 1.9830 ⎥ ⎢− 0.5269⎥ ⎥ ⎥ ⎢ ⎢ ⎢ 4.6185 ⎥ ⎢ 6.8009 ⎥ ⎢ 2.6355 ⎥ ⎢ 0.9237 ⎥ ⎥ ⎥ ⎢ ⎢ ⎣⎢ − 0.6525⎦⎥ ⎣⎢− 0.2686⎦⎥

k

xk

cx k

wk

rk

dk

⎡ 0.5078 ⎤ ⎢ 0.2989 ⎥ ⎥ ⎢ ⎢ − 1.9830 ⎥ ⎥ ⎢ ⎢− 4.6185⎥ ⎢− 2.6355⎥ ⎥ ⎢ ⎣⎢ 0.6525 ⎦⎥

⎡− 0.0120⎤ ⎢ 0.0448 ⎥ ⎥ ⎢ ⎢ 0.3029 ⎥ ⎥ ⎢ ⎢− 0.0680⎥ ⎢− 0.4019⎥ ⎥ ⎢ ⎣⎢ 0.3062 ⎦⎥

dk

5.7430

0.5948

0.2144

2.4636

7.7779

-0.1719

⎡2.8830⎤ ⎢2.3410⎥ ⎥ ⎢ ⎢0.5749⎥ ⎥ ⎢ ⎢0.0100⎥ ⎢ 0.4351⎥ ⎥ ⎢ ⎢⎣1.1399 ⎥⎦ Belum optimum

⎡2.7975⎤ ⎢ 2.5991⎥ ⎥ ⎢ ⎢1.0040 ⎥ ⎥ ⎢ ⎢0.0083⎥ ⎢0.0044⎥ ⎥ ⎢ ⎢⎣1.9996 ⎥⎦ Belum optimum

αk T

e Xkr

k

x k +1

Status

3

⎡2.7975⎤ ⎢ 2.5991⎥ ⎥ ⎢ ⎢1.0040 ⎥ ⎥ ⎢ ⎢0.0083⎥ ⎢0.0044⎥ ⎥ ⎢ ⎣⎢1.9996 ⎦⎥ 18.059 ⎡ − 0.0004⎤ ⎢ − 5.9995⎥ ⎢ ⎥ ⎢− 2.0006⎥ ⎢ ⎥ ⎣ − 0.0001⎦ ⎡0.0000⎤ ⎢0.0000⎥ ⎥ ⎢ ⎢0.0004⎥ ⎥ ⎢ ⎢5.9995⎥ ⎢2.0006⎥ ⎥ ⎢ ⎣⎢ 0.0001⎦⎥

Sudah optimum


105

METODE PRIMAL AFFINE-SKALING UNTUK MASALAH PROGRAM LINEAR

Recommend Documents