KONSTRUKSI SIKLUS DALAM METODE SIMPLEKS

KONSTRUKSI SIKLUS DALAM METODE SIMPLEKS

TESIS

Oleh

MISNAWATI 077021065/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009

Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

KONSTRUKSI SIKLUS DALAM METODE SIMPLEKS

TESIS

Diajukan Sebagai Salah Satu Syarat Untuk Memperoleh Gelar Magister Sains dalam Program Studi Magister Matematika pada Sekolah Pascasarjana Universitas Sumatera Utara

Oleh

MISNAWATI 077021065/MT

SEKOLAH PASCASARJANA UNIVERSITAS SUMATERA UTARA MEDAN 2009


Judul Tesis

: KONSTRUKSI SIKLUS DALAM METODE SIMPLEKS Nama Mahasiswa : Misnawati Nomor Pokok : 077021065 Program Studi : Matematika

Menyetujui, Komisi Pembimbing

(Dr. Saib Suwilo, M.Sc) Ketua

(Prof. Dr. Herman Mawengkang) Anggota

Ketua Program Studi,

Direktur,

(Prof. Dr. Herman Mawengkang)

(Prof. Dr. Ir. T.Chairun Nisa. B,M.Sc)

Tanggal lulus: Mei 2009


Telah diuji pada Tanggal Mei 2009

PANITIA PENGUJI TESIS Ketua

: Dr. Saib Suwilo, M.Sc

Anggota

: 1. Prof. Dr. Herman Mawengkang 2. Prof. Dr. Opim Salim Sitompul. MIKom 3. Drs. Suwarno Arriswoyo, M.Si


ABSTRAK Pembentukan siklus dalam metode simpleks dapat mengakibatkan pemrograman linier bisa gagal berakhir (tidak mencapai solusi optimal), karena itu pembentukan siklus harus dihindari. Sebagian besar contoh pembentukan siklus dalam metode simpleks diberikan tanpa penjelasan tentang bagaimana siklus tersebut dibentuk. Dengan menggunakan pendekatan versi geometri, akan diberikan penjelasan geometrik sederhana untuk konstruksi siklus dalam metode simpleks, termasuk contoh awal Hoffman. Kata kunci : Pemrograman Linear, Metode Simpleks, Siklus.

i Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

ABSTRACT The forming of cycle in a simplex method may result a linear programming keep into fail (achieving not any optimal solution), that a forming of cycle should be avoided. It is mostly forming of the cycle in a simplex method given without any description about how the cycle to produce out. By using a geometric version approach, it may give a simply geometric version for a cycle construction in simplex method including an early example of Hoffman. Keywords : Linear Programming, Simplex Method, Cycle.

ii Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

KATA PENGANTAR Puji dan syukur penulis ucapkan kepada sang maha pencipta yang telah memberikan begitu banyak nikmat sehingga tesis ini dapat diselesaikan dengan baik. Dalam menyelesaikan pendidikan di program Pascasarjana Universitas Sumatera Utara ini, penulis mengucapkan terima kasih dan penghargaan yang sebesarbesarnya kepada : Prof.dr.Chairuddin P.Lubis, DTM&H, Sp.A(K) selaku Rektor Universitas Sumatera Utara. Prof. Dr. Ir. T.Chairun Nisa B, M.Sc selaku Direktur Sekolah Pascasarjana Universitas Sumatera Utara yang telah memberikan kesempatan kepada penulis untuk mengikuti Program Studi Magister Matematika di Sekolah Pascasarjana Universitas Sumatera Utara. Drs. Sahlan Daulay, MPd selaku Kepala Sekolah SMA Negeri 3 Medan yang telah memberikan dukungan kepada penulis untuk mengikuti Sekolah Pascasarjana Universitas Sumatera Utara ini. Prof. Dr. Herman Mawengkang, selaku Ketua Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara dan Dosen Pembimbing II yang banyak memberikan bimbingan dan motivasi kepada penulis sehingga pendidikan ini dapat diselesaikan dengan baik. Dr. Saib Suwilo, MSc, selaku Sekretaris Program Studi Magister Matematika dan Dosen Pembimbing I yang telah memberikan bimbingan dan petunjuk sehingga tesis ini dapat diselesaikan dengan baik.

iii Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

Seluruh Staf Pengajar pada Program Studi Magister Matematika Sekolah Pascasarjana Universitas Sumatera Utara, yang telah memberikan ilmu pengetahuan kepada penulis selama perkuliahan hingga selesai. Secara Khusus penulis menyampaikan terimakasih yang tak terhingga kepada Ayahanda tercinta yaitu Alm. Rengkut Gurusinga dan Ibunda tercinta Djendam Br. Ginting yang doa-doanya selalu menyertai penulis. Kepada suami tercinta Membela Sembiring dan Ananda tercinta Josia, dan Vina yang selalu menjadi motivator penulis Kepada semua pihak yang telah turut membantu baik langsung maupun tidak langsung yang penulis dapatkan selama ini. Semoga tesis ini bermamfaat bagi pembaca dan pihak-pihak yang membutuhkannya.

Medan,

Juni 2009

Penulis,

Misnawati

iv Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

RIWAYAT HIDUP Misnawati dilahirkan di Medan pada tanggal 4 April 1964 dan merupakan anak pertama dari lima bersaudara dari Ayah Alm. Rengkut Gurusinga dan Ibu Djendam br. Ginting. Menamatkan di SD Swasta Gloria Sei Padang pada tahun 1976, Sekolah Menengah Pertama pada SMP Puteri Cahaya Medan Kecamatan Medan Baru pada tahun 1979, Sekolah Menengah Atas pada SMA Negeri 4 Medan pada tahun 1982, memasuki Perguruan Tinggi pada IKIP Negeri Medan Jurusan Matematika D3. Pada tahun 1986 diangkat sebagai calon Pegawai Negeri Sipil di SMA Negeri Tanobato Tapanuli Selatan. Pada tahun 1990 mutasi ke SMA Negeri 3 Medan hingga sekarang. Pada tahun 2004 memasuki Perguruan Tinggi Sekolah Tinggi Keguruan dan Ilmu Pendidikan RIAMA Medan dan memperoleh gelar Sarjana Pendidikan (SPd) pada tahun 2006. Pada tahun 2007 mengikuti Program Studi Magister Matematika di Sekolah Pasca Sarjana Universitas Sumatera Utara.

vi Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

DAFTAR ISI Halaman ABSTRAK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

i

ABSTRACT . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ii

KATA PENGANTAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

iii

RIWAYAT HIDUP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vi

DAFTAR ISI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

vii

DAFTAR TABEL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix

DAFTAR GAMBAR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

x

BAB 1 PENDAHULUAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.1 Latar Belakang . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

1

1.2 Rumusan Masalah . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.3 Tujuan Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.4 Kontribusi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

5

1.5 Metodologi Penelitian . . . . . . . . . . . . . . . . . . . . . . . . . . . .

6

BAB 2 TINJAUAN PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

7

BAB 3 LANDASAN TEORI . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.1 Pemrograman Linier . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

9

3.2 Metode Simpleks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

10

3.2.1 Persoalan Minimum Standar . . . . . . . . . . . . . . . . . . .

15

3.2.2 Asumsi Nondegenerasi . . . . . . . . . . . . . . . . . . . . . . .

19

vii Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

3.3 Beberapa Sifat Metode Simpleks . . . . . . . . . . . . . . . . . . . .

20

BAB 4 KONSTRUKSI SIKLUS DALAM METODE SIMPLEKS . . . . . .

24

4.1 Visualisasi Siklus dalam Metode Simpleks . . . . . . . . . . . . . .

24

4.2 Konstruksi Siklus dalam Metode Simpleks . . . . . . . . . . . . . .

31

BAB 5 KESIMPULAN DAN SARAN . . . . . . . . . . . . . . . . . . . . . . . . .

37

5.1 Kesimpulan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

37

5.2 Saran . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

39

DAFTAR PUSTAKA . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

40

LAMPIRAN . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

41

A. PEMBENTUKAN SIKLUS DALAM METODE SIMPLEKS, CONTOH DARI CHVATAL . . . . . . . . . . . . . . . . . . . . . . . . . .

41

B. BEBERAPA CONTOH SIKLUS YANG DITEMUKAN DALAM LITERATUR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

44

viii Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

DAFTAR TABEL

Nomor

Judul

4.1

Primal dan dual . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

ix Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

Halaman 29

DAFTAR GAMBAR

Nomor

Judul

Halaman

1.1

Siklus Hoffman . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

4

3.1

Path Hamilton pada 3-kubus . . . . . . . . . . . . . . . . . . . . . . . . .

21

4.1

Contoh Siklus Chvátal (1983) . . . . . . . . . . . . . . . . . . . . . . . .

28

4.2

Putaran Kekiri dan Kekanan . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.3

Kontruksi Siklus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

32

4.4

Contoh Siklus dalam ProgramLinier yang Layak . . . . . . . . . . .

35

4.5

Contoh Siklus dalam ProgramLinier yang Tidak Layak . . . . . .

35

5.1

Geometri Pembentukan Siklus . . . . . . . . . . . . . . . . . . . . . . . .

37

5.2

Siklus Pemrograman Linier yang Layak . . . . . . . . . . . . . . . . .

38

5.3

Siklus Pemrograman Linier yang Tidak Layak . . . . . . . . . . . . .

38

x Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

BAB 1 PENDAHULUAN

1.1 Latar Belakang Pemrograman linier berkenaan dengan masalah maksimisasi atau minimisasi fungsi linier yang variabel-variabelnya harus memenuhi sistem batasan linier, batasan yang merupakan persamaan atau ketaksamaan linier. Topik ini mungkin lebih tepat disebut optimisasi linier. Masalah optimasi linier muncul secara alamiah dan sangat elementer dalam banyak aplikasi terutama dalam masalah perencanaan ekonomi. Selanjutnya, suatu prosedur penyelesaian yang sangat efisien untuk masalah-masalah pemrograman linier bahkan masalah yang besar sekalipun dinamakan metode simpleks. Metode simpleks adalah suatu algoritma, yang hanyalah suatu proses di mana suatu prosedur sistematis diulang-ulang sampai yang diinginkan tercapai (solusi optimal). Setiap kali mengulang prosedur sistematis yang bersangkutan dinamakan suatu iterasi. Metode simpleks merupakan prosedur aljabar, di mana setiap iterasi adalah mengenai penyelesaian suatu sistem persamaan untuk memperoleh suatu penyelesaian percobaan yang baru untuk uji optimalitas. Akan tetapi, metode ini juga mempunyai interprestasi geometris yang sangat berguna. Sudah diketahui dengan jelas bahwa pembentukan siklus terjadi pada metode simpleks bila metode tersebut menghasilkan barisan penyelesaian basis x, x1, . . . , xt di mana x = x1 = · · · = xt serta x dan xt berbagi basis yang sama. Misalkan

1 Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

2 contoh pembentukan siklus dalam metode simpleks dari Chvátal. Maksimumkan. 10x1 − 57x2 − 9x3 − 24x4 dengan batasan 0, 5x1 − 5, 5x2 − 2, 5x3 + 9x4 ≤ 0 0, 5x1 − 1, 5x2 − 0, 5x3 + x4 ≤ 0 x1 ≤ 1 Dalam contoh ini siklus terjadi setelah melalui 6 tabel dan kembali ke tabel awal. Jika dilanjutkan menggunakan kaidah-kaidah yang sama untuk memilih variabel keluar dan variabel masuk, maka akan dijalani siklus melalui tabel-tabel ini secara tak berhingga. Ini disebut pembentukan siklus dan inilah satu-satunya cara metode simpleks bisa gagal berakhir. Untungnya, pembentukan siklus selalu bisa dihindari. Sebagian besar contoh pembentukan siklus dalam metode simpleks diberikan tanpa penjelasan tentang bagaimana siklus tersebut dibentuk. Setiap buku teks tentang pemrograman linier mengkhususkan suatu bab tentang pembentukan siklus dalam metode simpleks; akan tetapi, tidak ada buku teks yang memberikan intuisi geometrik di balik pembentukan siklus tersebut. Daftar ini mencakup buku teks klasik Chvátal (1983) dan Dantzig (1963) serta Sierksma (1996). Contoh biasanya dipresentasikan sebagai rangkaian tabel atau kamus, jika mengikuti terminologi dan notasi yang digunakan Chvátal. Presentasi sedemikian jelas meyakinkan bahwa metode simpleks bisa bersiklus, tetapi tidak memberikan pengetahuan apapun di balik konstruksinya. Dapat diperhatikan contoh pembentukan-siklus pertama, yang dibuat Hoffman (1953) dan Dantzig (1963), dengan kamus awal :


3

x0 =1 x1 = − cos ϕx3 + ω cos ϕx4 − cos 2ϕx5 + 2ω cos2 ϕx6 − cos 2ϕx7 − 2ω cos ϕx8 − cos ϕx9 − ω cos ϕx10 x2 = − [(tan ϕ sin ϕ)/ω]x3 − cos ϕx4 − [tan ϕ sin 2ϕ)/ω]x5 − cos 2ϕx6 + 2(sin2 ϕ/ω)x7 − cos 2ϕx8 + [− tan ϕ sin ϕ)/ω]x9 − cos ϕx10 z =[(1 − cos ϕ)/ cos ϕ]x3 − ωx4 − 2ωx6 − 4sin2 ϕx7 + 2ω cos 2ϕx8 − 4sin2 ϕx9 − ω(1 − 2 cos ϕ)x10 Jika ditetapkan ϕ = 2π/5, ω > (1 − cos 2ϕ)/(1 − 2 cos ϕ) ≈ 4, 74, metode simpleks menggunakan siklus kaidah Dantzig melalui rangkaian 10 tabel. Variabel-variabel ruas kiri bersiklus berulang-ulang melalui barisan {x0 , x1, x2}, {x0, x2 , x3}, . . . , {x0, x9 , x10}, {x0, x10, x1}

Lee (1997) berhasil menguraikan penurunan aljabar dari contoh Hoffman, dengan menggunakan geometri kolom - dikenal sebagai penafsiran simpleks (Dantzig (1963), hal. 160 - dan menghasilkan gambar tiga-dimensi). Pada Gambar 1.1, diperlihatkan contoh Hoffman dalam dua-dimensi dengan menggunakan geometri metode simpleks dual, yang dijelaskan dan digunakan pertama kali untuk membangun siklus-siklus oleh Beale (1955), tetapi tidak digunakan untuk menganalisa contoh Hoffman.


4

Gambar 1.1 Siklus Hoffman

Zörnig (2006), mengungkapkan bahwa contoh pembentukan siklus dibangun untuk berbagai varian strategi pemilihan pivot : kaidah penurunan biaya paling negatif dan tepi paling terjal untuk variabel masuk, dan kaidah rasio terkecil untuk variabel keluar (dimana ikatan diputus masing-masing menurut indeks terkecil atau kriteria koefisien terbesar). Hasil-hasil memang menarik secara teoritis karena hanya sejumlah terbatas dari contoh pembentukan siklus yang hingga saat ini dipresentasikan dalam literatur. Contoh pembentukan siklus yang dibangun juga bisa berfungsi sebagai persoalan ujian untuk mengevaluasi kinerja praktis dari prosedur anti-pembentukan siklus atau varian baru dari jenis metode simpleks. Untuk itu dalam penulisan tesis ini, penulis tertarik mengulas kontruksi siklus dalam metode simpleks dengan memberikan versi yang disederhanakan dari penafsiran geometrik dan membandingkan contoh pembentukan siklus yang diperoleh dari berbagai literatur pemrograman linier, serta berbagai ekuivalen secara kombinatorial.


5 1.2 Rumusan Masalah Sebagian besar contoh pembentukan siklus dalam metode simpleks diberikan tanpa penjelasan tentang bagaimana siklus tersebut dibentuk. Satu pengecualian adalah contoh Beale (1995) yang dibangun di sekitar geometri bidang dalam metode simpleks dual. Dengan menggunakan berbagai pendekatan geometri sederhana atas sejumlah contoh pembentukan siklus dalam metode simpleks, termasuk contoh awal Hoffman dapat membantu dalam memahami metode simpleks melalui penafsiran visual. Sehingga bagaimanakah mengkonstruksikan siklus dalam metode simpleks yang efisien untuk masalah-masalah pemrograman linier sehingga solusi optimal yang diinginkan dapat tercapai.

1.3 Tujuan Penelitian Penelitian ini diharapkan dapat memberikan sumbangan dalam bidang matematika secara umum dan khususnya dalam bidang matematika terapan sehingga dapat membantu mahasiswa memahami siklus dalam metode simpleks.

1.4 Kontribusi Penelitian Penelitian ini diharapkan dapat memberikan sumbangan dalam bidang matematika secara umum dan khususnya dalam bidang matematika terapan sehingga dapat membantu mahasiswa memahami siklus dalam metode simpleks.


6 1.5 Metodologi Penelitian Metode penelitian yang digunakan pada tesis ini bersifat literatur yaitu disusun berdasarkan rujukan pustaka dengan langkah-langkah sebagai berikut :

1. Mengumpulkan dan mempelajari bahan-bahan berupa buku, jurnal ilmiah dan makalah yang menimbulkan gagasan dan mendasari penelitian yang dilakukan. Selanjutnya gagasan tersebut dituangkan dalam bagian pendahuluan, yang berisi latar belakang, perumusan masalah, tujuan dan kontribusi penelitian. 2. Pada bagian ke dua, diuraikan teori-teori pendukung yang dipakai untuk menyelesaikan permasalahan konstruksi siklus dalam metode simpleks, yang meliputi pemrograman linier dan teknik penyelesaian pemrograman linier dengan metode simpleks (algoritma metode simpleks) serta penjelasan geometrik sederhana atas sejumlah contoh konstruksi siklus dalam metode simpleks. 3. Bagian selanjutnya, akan diuraikan inti dari persoalan yaitu visualisasi dan konstruksi siklus dalam metode simpleks yang efisien untuk masalah-masalah pemrograman linier dengan membandingkan contoh pembentukan siklus yang diperoleh dari berbagai literatur pemrograman linier. 4. Bagian akhir dari penulisan tesis ini adalah menetapkan kesimpulan dan saran-saran yang diperoleh dari studi yang dilakukan.


BAB 2 TINJAUAN PUSTAKA

Gass (1964) menyebutkan bahwa pemrograman linier merupakan teknik yang ampuh untuk mengatasi masalah alokasi sumber daya terbatas di antara kegiatan-kegiatan bersaingan dan juga masalah-masalah lain yang mempunyai rumusan matematis yang serupa (fungsi linier). Selanjutnya suatu prosedur penyelesaian yang sangat efisien yang dinamakan metode simpleks, tersedia untuk menyelesaikan masalah-masalah pemrograman linier bahkan masalah yang besar sekalipun. Metode simpleks merupakan algoritma yang efisien dan terhandal untuk menyelesaikan persoalan-persoalan pemrograman linier. Meskipun mempunyai interprestasi geometris yang berguna, metode simpleks merupakan prosedur aljabar. Pada setiap iterasi, prosedur ini bergerak dari penyelesaian layak dasar yang sekarang ke suatu penyelesaian layak dasar yang berdekatan yang lebih baik dengan memilih baik suatu variabel dasar masuk maupun suatu variabel dasar keluar, dan kemudian memakai eliminasi Gauss untuk menyelesaikan suatu sistem persamaan linier. Bilamana penyelesaian yang sekarang tidak memiliki penyelesaian layak dasar berdekatan yang lebih baik, maka penyelesaian yang sekarang adalah optimal dan algoritma berhenti. Sejak diciptakan Dantzig pada tahun 1947, banyak sekali literatur tentang variasi dan perluasan metode simpleks dalam banyak arah, beberapa diajukan oleh Dantzig sendiri. Hal yang dipertanyakan seputar jumlah tahap pivot yang dibutuhkan untuk menyelesaikan pemograman linier pada kasus yang terburuk. Berdasarkan banyak pengalaman empiris, tampak bahwa program m × n biasanya 7 Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

8 diselesaikan dengan kira-kira 3m/s pivot. Akan tetapi, pada tahun 1972, Klee dan Minty (1972) memberikan contoh masalah standar m × 2m yang menggunakan kaidah pilihan Dantzig yang membutuhkan 2m − 1 pivot. (Gale, David, March 2007). Zörnig (2006) mengungkapkan bahwa contoh pembentukan siklus dibangun untuk berbagai varian strategi pemilihan pivot : kaidah penurunan biaya paling negatif dan tepi paling terjal untuk variabel masuk, dan kaidah rasio terkecil untuk variabel keluar (dimana ikatan diputus masing-masing menurut indeks terkecil atau kriteria koefisien terbesar). Hasil-hasil memang menarik secara teoritis karena hanya sejumlah terbatas dari contoh pembentukan siklus yang hingga saat ini dipresentasikan dalam literatur. Contoh pembentukan siklus yang dibangun juga bisa berfungsi sebagai persoalan ujian untuk mengevaluasi kinerja praktis dari prosedur anti-pembentukan siklus atau varian baru dari jenis metode simpleks.


BAB 3 LANDASAN TEORI

3.1 Pemrograman Linier Pemrograman linier berkenaan dengan masalah maksimisasi atau minimisasi fungsi linier yang variabel-variabelnya harus memenuhi sistem batasan-batasan linier, batasan yang merupakan persamaan atau ketaksamaan linier. Masalah semacam ini muncul dengan cara alamiah dan sangat elementer dalam banyak konteks terutama dalam masalah perencanaan ekonomi. Pada umumnya, aktivitas adalah sebuah kolom vektor yang entri positipnya merupakan output, entri negatipnya merupakan input. Diasumsikan bahwa aktivitas aj bisa dilaksanakan pada tingkat non-negatip xj . Batasan-batasan diberikan oleh vektor aktivitas lain b, ruas kanan, yang menetapkan jumlah barang-barang yang berbeda yang akan diproduksi atau dikonsumsi, misalkan untuk masalah diet ini adalah daftar jumlah gizi yang ditetapkan dan untuk masalah transportasi adalah penawaran dan permintaan tertentu di tempat asal dan tujuan. Terakhir, yang terkait dengan setiap aktivitas aj adalah biaya cj . Diberikan m barang dan n aktivitas aj , masalah pemrograman linier adalah untuk menentukan tingkat aktivitas xj yang memenuhi batasan-batasan dan meminimalkan n P cj cxj . Sebagai alternatip, c bisa dianggap sebagai laba yang ditotal biaya j=1

hasilkan oleh aktivitas a, di mana dalam kasus ini masalahnya adalah untuk n P cj cxj . Metode simpleks adalah algoritma yang mencari penyememaksimalkan j=1

lesaian pemrograman linier atau menunjukkan bahwa tidak ada penyelesaian.


10 3.2 Metode Simpleks Algoritma simpleks dapat dianggap sebagai generalisasi yang berarti dari eliminasi Gauss-Jordan standar atas aljabar linier biasa. Tahap perhitungan dasar dalam algoritma simpleks sama dengan tahap perhitungan dasar dalam sebagian besar aljabar linier dasar, yang disebut dengan operasi pivot. Ini merupakan operasi atas matriks-matriks yang digunakan untuk menyelesaikan sistem persamaan linier, untuk menempatkan matriks dalam bentuk baku (eselon), untuk mengevaluasi determinan, dan lain-lain. Diberikan sebuah matriks A, lalu pilih entri pivot tak nol aij dan tambahkan kelipatan baris i ke baris lainnya untuk memperoleh nol pada kolom ke-j. Kemudian baris i dinormalisasikan dengan membaginya dengan aij . Untuk menyelesaikan persamaan-persamaan linier elemen pivot bisa salah satu dari entri yang tidak nol. Sebaliknya, metode simpleks membatasi pilihan entri pivot dan ditetapkan secara total dengan memberikan sepasang kaidah sederhana, kaidah masuk yang menentukan kolom pivot j dan kaidah keluar yang menentukan baris pivot i (secara teori, ketiga kaidah baris elementer mungkin diperlukan untuk menghindari kasus degenerate). Dengan mengikuti kaidah ini yang dimulai dari data awal algoritma sampai pada penyelesaian program linier dengan sejumlah berhingga pivot.

Definisi 1 Tabel X dari himpunan vektor-vektor A = {a1 , a2 , . . . , an } dengan basis B = {b1 , b2, . . . , bm } adalah mariks m × n,


11

b1 b2 .. . bj .. . bm

       

a1 a2 x011 x012 x021 x022 .. .. . . x0i1 x0i2 .. .. . . x0m1 x0m1

··· ··· ··· .. . ··· .. . ···

aj x01j x02j .. . x0ij .. . x0mj

· · · an · · · x01n · · · x02n .. .. . . · · · x0in .. .. . . · · · x0mn

       

di mana xij adalah koefisien bi dalam rumus untuk aj sebagai kombinasi linier dari bi . Dalam bentuk matriks, X adalah matriks (unik) yang memenuhi : BX=A

(3.1)

Ini akan sering digunakan untuk mencakup vektor satuan ei dalam tabel di mana dalam kasus ini, tampak seperti yang diperlihatkan di bawah ini. b1 b2 .. . bi .. . bm

.. . .. .

e2  e1 y11 y12  y21 y22  . ..  .. .   yi1 yi2  . ..  .. . ym1 ym1 a2  a1 x11 x12  x21 x22  . ..  .. .   xi1 xi2  . ..  .. . xm1 xm1

··· ··· ··· .. . ··· .. . ···

ej y1j y2j .. . yij .. . ymj

· · · aj · · · x1j · · · x2j .. .. . . · · · xij .. .. . . · · · xmj

· · · en · · · y1n · · · y2n .. .. . . · · · yin .. .. . . · · · ymn ··· ··· ··· .. . ··· .. . ···

an x1n x2n .. . xin .. . xmn

               

Catat bahwa dari (3.1), Y = {yij } adalah penyelesaian dari B Y = I sehingga Y = B−1 . Dengan mengalikan (3.1) pada ruas kiri dengan Y menghasilkan persamaan : Y A=X


(3.2)

12 Mudah dibuktikan bahwa jika ditetapkan pivot pada entri xij , maka diperoleh matriks baru X0 , yaitu tabel untuk basis baru di mana aj menggantikan bj . b1 b2 .. . bj .. . bm

       

a1 x011 x021 .. . x0i1 .. . x0m1

a2 x012 x022 .. . x0i2 .. . x0m1

· · · aj · · · x01j · · · x02j .. .. . . · · · x0ij .. .. . . · · · x0mj

··· ··· ··· .. . ··· .. . ···

an x01n x02n .. . x0in .. . x0mn

       

Metode simpleks menyelesaikan program linier dengan serangkaian pivot dalam tabel-tabel yang berurutan (iterasi) atau, ekuivalen dengan menentukan serangkaian basis, di mana masing-masing basis berbeda dari basis sebelumnya dengan vektor tunggal.

Teorema 1 Sistem persamaan linier berikut mempunyai tepat satu penyelesaian: Ax = b

(3.3)

y T A = 0T , y T b = 1

(3.4)

atau

Jika (3.3) tidak mempunyai penyelesaian ini berarti bahwa b tidak berada di dalam ruang linier yang dihasilkan oleh aj . Dalam kasus tersebut ada vektor y yang ortogonal terhadap aj tetapi tidak terhadap b. Terlihat bahwa (3.3) dan (3.4) tidak berlaku karena dengan mengalikan (3.3) dengan yT dan (3.4) dengan x akan mengimplikasikan 0 = 1. Bagian nontrivial adalah menunjukkan bahwa (3.3) atau (3.4) harus berlaku. Ini dapat dilakukan dengan memberikan algoritma yang dengan paling banyak m pivot, untuk mencari penyelesaian dari (3.3) atau (3.4).


13 Tabel awal terdiri dari matriks A bersama-sama dengan ruas kanan b yang semuanya didahului oleh matriks identitas I. Ini digambarkan secara skematis dalam bentuk berikut : {ei } {aj } {b} A b ] {bi } [ I (Simbol seperti {ei}, {aj } dalam tanda kurung kurawal adalah basis baris dan basis kolom dari tabel). Dengan berusaha mengganti ei secara terurut dengan aj . Tabel pada setiap iterasi mempunyai berbentuk : {ei } {aj } {b} X u ] {bi } [ Y Sekarang ada dua kemungkinan : Semua vektor satuan ei dapat diganti dengan sesuatu dari aj . Kemudian penyelesaian dari (3.3) dapat dibaca dari vektor u dalam kolom b dari tabel di atas, yaitu, setiap komponen u, katakanlah ui , adalah nilai variabel xji yang kolomnya yang bersesuaian aji = bi . Setiap xj yang kolomnya bersesuaian, tidak berada dalam basis saat ini mempunyai nilai nol. Kasus II : Berusaha mengganti ek , dimana tidak tersedia pivot karena xkj = 0 untuk semua j.

Kasus I :

i. Jika ditambahkan uk = 0, maka tinggalkan ek dalam basis dan teruskan mengganti ek+1 . ii. Jika uk 6= 0, maka baris ke-k yk dari Y memberikan penyelesaian dari (3.4). Untuk mengetahuinya, catat bahwa dari (3.2) [Y ][A b] = [X u]. Karena baris ke-k dari X sama dengan nol, diperoleh yk A = 0, sementara yk b = uk 6= 0, karenanya yk /uk menyelesaikan (3.4). Aljabar menjadi lebih sulit secara berarti, jika penyelesaian dari (3.3) nonnegatip. Dalam kasus ini akan diperoleh teorema eksistensi berikut (dikenal sebagai Lemma Farkas).


14 Teorema 2 Sistem persamaan linier berikut mempunyai tepat satu penyelesaian A x = b, x ≥ 0

(3.5)

y T A ≤ 0T , y T b > 0

(3.6)

atau

Tidak dimungkinkan kedua sistem mempunyai penyelesaian karena dengan mengalikan (3.5) dengan yT dihasilkan yT Ax = yT b > 0 sementara dengan mengalikan (3.6) dengan x dihasilkan yT Ax ≤ 0. Persamaan (3.5) menyatakan bahwa b terletak di dalam kerucut cembung yang dihasilkan oleh kolom-kolom aj dari A. Jika b tidak berada di dalam kerucut ini, maka terdapat ”hyperplane pemisah” yang normalnya membentuk sudut nonakut dengan aj dan membentuk sudut akut dengan vektor b. Metode simpleks mencari penyelesaian (3.5) atau (3.6) dengan sejumlah hingga pivot. Akan tetapi, tidak ada batas atas yang berguna untuk jumlah pivot yang mungkin dibutuhkan. Dapat diasumsikan memulainya dengan vektor b nonnegatip (jika tidak, ubah tanda sebahagian persamaan).

Definisi 2 Suatu basis B disebut layak (sangat layak) jika b adalah kombinasi linier nonnegatip (positip) dari vektor-vektor B. Ini ekuivalen dengan syarat bahwa b kolom u dari tabel nonnegatip (positip).

Dengan meniru algoritma dari bagian sebelumnya, dimulai dari basis layak {ei } dari vektor-vektor satuan dan berusaha membawa masuk {aj } melalui serangkaian pivot yang menjaga kelayakan, tetapi untuk ini kaidah pivot dari bagian sebelumnya harus dibatasi.


15 Andaikan aj akan dibawa ke dalam basis layak baru. Maka agar supaya basis baru layak, vektor 0 basis yang digantikannya harus memenuhi syarat yang diperoleh dengan cara mudah berikut. Kaidah Pivot Keluar Elemen pivot xij harus memenuhi (i) xij > 0, (ii) ui /xij ≤ uk /xkj untuk semua k dengan xkj > 0. Karena batasan di atas tidak lagi dimungkinkan hanya mengganti vektor basis ei satu per satu seperti pada bagian sebelumnya. Kaidah lebih lanjut untuk memilih kolom pivot haruslah diberikan.

3.2.1 Persoalan Minimum Standar Diberikan m-vektor b, n-vektor cT dan matriks A berukuran m×n, tentukan n-vektor x sehingga : Minimumkan cT x (3.7)

Kendala Ax = b x≥0

Yang bersesuaian dengan masalah ini (dan dengan menggunakan data yang persis sama) adalah masalah dual, tentukan m-vektor yT sehingga : Maksimumkan cT x (3.8) T

Kendala y A ≤ c

T

Fungsi linier cT x dan yT b disebut fungsi tujuan masing-masing dari (3.7)


16 dan (3.8). Vektor-vektor x, y yang menyelesaikan masalah ini disebut penyelesaian optimal; bilangan cT x dan yb adalah nilai-nilai optimal. Misalkan X dan Y adalah himpunan (mungkin kosong) dari semua vektor yang memenuhi masing-masing batasan (3.7) dan (3.8). Vektor sedemikian disebut layak. Pengamatan Utama. Jika x ∈ X, yT ∈ Y, maka yT b ≤ cT x. Bukti. Kalikan Ax = b dengan yT dan yT A ≤ cT dengan x. Konsekuensi penting dari pengamatan ini adalah : Akibat.

Jika x ∈ X dan y ∈ Y memenuhi yT b ≤ cT x, maka x dan y

adalah penyelesaian optimal, dan bilangan yT b = cT x adalah nilai optimal untuk masalahnya masing-masing. Kebalikan dari fakta ini membentuk yang disebut teorema dualitas dasar. Teorema Dualitas Dasar : Masalah dual di atas mempunyai penyelesaian optimal x, yT jika dan hanya jika X dan Y tidak kosong di mana dalam kasus ini nilai optimal cT x dan yT b sama. Untuk mengetahui bagaimana Teorema 2 merupakan kasus khusus dari teorema dualitas, maka misalkan diambil [I A b] sebagai tabel awal tertentu dari masalah minimum standar dan vektor cT = (1, . . . , 1, 0, . . . , 0) yang m entri pertamanya sama dengan 1, sisanya sama dengan 0, sebagai fungsi tujuan. Himpunan X tidak kosong karena memuat vektor nonnegatip (b1 , . . . , bm , 0, . . . , 0), dan himpunan Y tidak kosong karena memuat vektor nol. Jika nilai optimal sama dengan nol, maka subvektor penyelesaian optimal x menyelesaikan (3.5). Jika nilai optimal positip, maka vektor optimal dual y menyelesaikan (3.6).


17 Sekarang akan diperlihatkan bagaimana metode simpleks menyelesaikan masalah (3.7), (3.8) dan memberikan bukti konstruktif dari teorema dualitas. Sebagai langkah pertama, masukkan fungsi tujuan cT x sebagai baris 0 dari tabel. Yaitu, dengan mendefinisikan vektor kolom diperluas a ˆ j sama dengan (−cj , aj ), dan memperkenalkan vektor satuan ke-0, yaitu e0 . Maka tabel awal diperluas adalah : ˆ e0 {ei } {âj } b T e0 1 0 −c 0 {ei } 0 I A b Asumsikan bahwa, ditemukan basis layak awal, dengan mengaplikasikan metode simpleks pada masalah penyelesaian nonnegatip (3.5), (3.6) seperti yang telah dijelaskan. Kemudian berkenaan dengan basis diperluas umum {e0, ˆb1 , . . . , ˆbm }, tabel mempunyai bentuk di bawah ini, ˆ e0 {ei } {âj } b T T e0 1 y z w î } 0 Y X u {b P Catat bahwa menurut definisi tabel, we0 + i uiˆbi = ˆb sehingga untuk entri P P ke-0 dapat diperoleh w − i ui ci = 0, sehingga w = i ui ci , yaitu nilai dari fungsi tujuan untuk basis layak dasar {bi }. Juga dari tabel zj =

P

i

xij ci − cj . Bilangan ini membandingkan biaya yang

terkait dengan vektor aktivitas aj dengan biaya kombinasi linier dari vektor-vektor bi yang bersesuaian. Jika zj positip itu berarti bahwa kita dapat mengurangi total biaya dengan memasukkan vektor aj ke dalam basis berikutnya. Ini menghasilkan kedua pengamatan penting berikut: I. Jika baris zT nonpositip, maka u bisa diperluas ke penyelesaian x dari (3.7) dan y T menyelesaikan (3.8). Yaitu, dengan menggunakan (3.2) sehingga


18 diperoleh :

1 yT 0 Y

−cT 0 A b

=

zT w X u

sehingga −cj +yT aj = zj ≤ 0. Karenanya yT A ≤ cT sehingga yT memenuhi batasan-batasan dual. Dengan cara yang sama diperoleh yT b = w = cT x, sehingga dari akibat di atas, Teorema Dualitas terbukti. II. Jika untuk suatu j diperoleh zj > 0 dan xij ≤ 0 untuk semua i, maka masalah (3.7) tidak mempunyai minimum, sebab dari tabel kita peroleh P aj − i xij bi = 0; dan karena xij ≤ 0, diperoleh, λ ( âj −

X

î) + xij b

i

X

î = b xi b

i

yang memberikan penyelesaian (nonnegatip) layak baru untuk suatu λ > 0. P Perubahan yang bersesuaian dalam fungsi tujuan adalah λ(cj − i xij ci ) = −λzj ; jadi karena zj > 0 fungsi tidak mempunyai minimum. Kaidah Pivot Masuk Bawa masuk ke dalam basis setiap kolom âj di mana zj positip. Catat bahwa seperti yang telah dijelaskan kaidah pivot kedua, pada umumnya, mungkin mengharuskan pengambilan pilihan dari antara banyak positip zj yang mungkin. Pilihan yang lumrah misalnya adalah memilih kolom dengan nilai terbesar zj , pilihan yang pada awalnya diajukan Dantzig. Kedua kaidah pivot menguraikan algoritma simpleks selengkapnya. Jika untuk suatu j, zj positip dan ada xij positip, karenanya membawa aj ke dalam basis (dengan pivot). Masih harus ditunjukkan bahwa pada akhirnya I atau II akan terjadi.


19 3.2.2 Asumsi Nondegenerasi Setiap basis layak adalah sangat layak. Catat jika tidak demikian halnya, maka b akan merupakan kombinasi linier positip dari kurang dari m vektor aj , suatu situasi degeneratif. Walaupun kasus degeneratif tampaknya akan jarang (atas dasar matematik), namun tidak demikian halnya di dalam praktek. Andaikan xij adalah pivot (positip). Maka setelah pempivotan w0 = w − zj ui /xij < w, karena ui > 0 dari nondegenerasi, sehingga nilai fungsi tujuan berkurang dengan setiap pivot. Ini berarti bahwa tidak ada basis yang muncul kembali (karena basis menentukan nilai tujuan), dan karena hanya ada sejumlah hingga banyaknya basis, algoritma harus berakhir pada keadaan I atau keadaan II. Jika asumsi nondegenerasi tidak dipenuhi maka diperlukan alasan lebih lanjut. Tentu saja, contoh-contoh yang dibangun Hoffman (1953), dengan menggunakan kaidah pilihan pivot Dantzig yang bisa menghasilkan ”pembentukan siklus”, yang berarti barisan basis-basis layak muncul kembali secara tak berhingga. Akan tetapi, ternyata bahwa kaidah sederhana berikut dari Bland (1977), menjamin bahwa tidak ada basis yang akan muncul kembali.

Kaidah Seleksi Pivot Bland Di antara vektor-vektor masuk yang memenuhi syarat pilih satu vektor dengan indeks terendah dan biarkan itu menggantikan vektor basis yang memenuhi syarat dengan indeks terendah.


20 Walaupun syarat mudah dinyatakan, namun bukti bahwa syarat itu menghindari pembentukan siklus sangat mungkin. Tambahan lagi, ini tidak seefisien kaidah pilihan pivot biasa (Dantzig). Terakhir, ada penafsiran ekonomis alamiah dari masalah dual. Pada model barang dan aktivitas, vektor yT = (y1, . . . , ym ) dapat dianggap sebagai vektor harga di mana yi adalah harga satu unit barang ke-i. Maka yT aj adalah pendapatan yang dihasilkan dengan mengoperasikan aktivitas aj pada tingkat unit. Syarat kelayakan dual, yT aj − cj ≤ 0 menyatakan bahwa laba (pendapatan dikurang biaya) tidak bisa positip. Ini merupakan persyaratan yang lumrah secara ekonomis, sebab jika aktivitas menghasilkan laba positip, produsen akan ingin mengoperasikannya pada tingkat tinggi secara sebarang dan ini jelas tidak akan layak. Maka dualitas menyatakan bahwa harga adalah sedemikian rupa sehingga vektor harga yT memaksimalkan nilai yT b dari aktivitas ruas kanan b dengan memenuhi syarat tidak ada laba positip.

3.3 Beberapa Sifat Metode Simpleks Sejak diciptakan Dantzig pada tahun 1947, banyak sekali literatur tentang variasi dan perluasan metode simpleks, beberapa diajukan oleh Dantzig sendiri. Berdasarkan banyak pengalaman empiris, tampak bahwa program m × n biasanya diselesaikan dengan kira-kira 3m/s pivot. Akan tetapi, pada tahun 1972, Klee dan Minty [6] memberikan contoh masalah standar m × 2m yang menggunakan kaidah pilihan Dantzig yang membutuhkan 2m − 1 pivot. Untuk memahami contoh, pertama perhatikan matriks A yang terdiri dari m vektor satuan ei dan m vektor aj = ei di mana ruas kanan adalah e, vektor yang semua entrinya sama dengan satu. Dengan pemeriksaan, (lihat misalnya tabel di bawah ini) himpunan penye-


21 lesaian layak X terdekomposisi menjadi pergandaan langsung m selang satuan, dengan demikian, ini merupakan m-kubus satuan. "

{ei } 1 0 0 1 0 1 0 0 0 0 1 0

{aj } # " 0 0 1 0 0 1

b # 1 1 1

Tidak sulit dilihat bahwa setiap basis layak, dengan demikian setiap verteks dari kubus, harus memuat ai atau ei , tetapi bukan keduanya, untuk semua i. Sifat ini akan tetap terjaga jika ai sedikit terganggu. Dengan pilihan cerdik atas gangguan ini dan fungsi tujuan yang cocok, menunjukkan bahwa kaidah pivot Dantzig menyebabkan algoritma menyinggahi semua ke 2m verteks yang mengikuti path- Hamiltonian terkenal atas m-kubus.

Gambar 3.1 Path Hamilton pada 3-kubus

Ini berarti, misalnya, bahwa vektor a1 masuk basis pada pivot pertama, tetap di dalam basis untuk satu pivot, kemudian keluar dan tetap di luar untuk satu pivot, lalu masuk kembali dan tetap bertahan, kemudian keluar dan tetap di luar, dan seterusnya sepanjang perhitungan. Sehingga pada kasus terburuk metode simpleks mungkin membutuhkan perpangkatan dari pivot, walaupun, seperti yang disebutkan sebelumnya, tidak ada masalah yang muncul secara ala-


22 miah pernah menunjukkan perilaku sedemikian. Juga ada hasil-hasil atas perkiraan jumlah pivot dari program linier ”acak”. Karena contoh Klee-Minty menunjukkan bahwa dimungkinkan bagi algoritma simpleks berperilaku buruk, lumrah kiranya bertanya apakah mungkin ada algoritma pempivotan lain yang dijamin menemukan penyelesaian optimal dengan jumlah pivot yang terbatas, katakanlah, hingga polinomial dalam n. Mulamula perhatikan batas bawah untuk jumlah pivot. Jika basis layak awal adalah A = {a1 , . . . , am } dan basis optimal adalah himpunan yang saling lepas B = {b1 , . . . , bm } maka jelas akan dibutuhkan setidaknya m pivot untuk beranjak dari A ke B. Fakta yang sangat aneh adalah bahwa jika himpunan X dari penyelesaian-penyelesaian layak dibatasi, maka dalam semua contoh yang diketahui dimungkinkan beranjak dari setiap basis layak ke setiap basis lainnya dengan paling banyak m pivot. Ingat kembali bahwa himpunan X adalah polytop cembung m-dimensi yang verteks-verteksnya merupakan basis-basis layak. Pengamatan di atas ekuivalen dengan pernyataan bahwa setiap dua verteks dari polytop ini dihubungkan oleh path-edge dengan paling banyak m edge. Perkiraan yang pada awalnya diajukan Warren Hirsch dibuktikan Klee dan Walkup melalui dimensi 5 tetapi tetap tak terselesaikan dalam dimensi yang lebih tinggi. Bagi Dantzig ”perkiraan Hirsch” ini sangat menarik karena bukti konstruktif dari perkiraan akan berarti bahwa mungkin ada algoritma yang menyelesaikan program linier dengan paling banyak m pivot. Akan tetapi, sekalipun ada algoritma sedemikian, mungkin saja bahwa jumlah perhitungan yang terlibat dalam memilih rangkaian pivot-pivot akan menjadikannya jauh kurang efisien dari segi perhitungan dibandingkan dengan metode simpleks. Tentu saja algoritma terke-


23 nal ini dan banyak penajamannya hingga saat ini tetap merupakan metode pilihan untuk menyelesaikan sebagian besar masalah pemrograman linier.


BAB 4 KONSTRUKSI SIKLUS DALAM METODE SIMPLEKS

4.1 Visualisasi Siklus dalam Metode Simpleks Diberikan program linier, n P cj xj , Maksimumkan : z = j=1

dengan kendala : n X

aij xj ≤ bj , i = 1, . . . , m

j=1

xj ≥ 0, j = 1, . . . , n dengan menambahkan variabel slack nonnegatip xn+1 , . . . , xn+m , maka diperoleh suatu sistem persamaan-persamaan linier, n X

aij xj + xn+i = bi , i = 1, . . . , m

(4.1)

j=1

Selanjutnya dengan menyelesaikan ke m persamaan ini untuk m + n variabel, diperoleh suatu bentuk kanonik. Sebagai contoh misalnya, program linier: Maksimumkan : z = 10x1 − 57x2 − 9x3 − 24x4 Dengan kendala : 0.5x1 − 5.5x2 − 2.5x3 + 9x4 ≤ 0 (4.2) 0.5x1 − 1.5x2 − 0.5x3 + x4 ≤ 0 x1 , x2, x3, x4 ≥ 0 Dirubah kebentuk standar baku, sehingga menjadi bentuk iterasi: x5 = 0 − 0.5x1 + 5.5x2 + 2.5x3 − 9x4 x6 = 0 − 0.5x1 + 1.5x2 + 0.5x3 − x4

(4.3)

z = 0x5 + 0x6 + 10x1 − 57x2 − 9x3 − 24x4 24 Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

25 dan setiap variabel bersesuaian dengan ketaksamaan dari (4.2), x1 , . . . , x4 untuk batasan nonnegatif dari x5 dan x6 untuk ketaksamaan yang ditambahkan (diperluas). Jika penyelesaian dasar yang diperoleh dengan menetapkan variabel cobasic (ruas kanan) sama dengan nol dan mengevaluasi variabel basis (ruas kiri) nonnegatif, kemudian dari iterasi ini dapat diperoleh penyelesaian layak dasar untuk program linier, nilai z menjadi nilai tujuan. Metode simpleks berusaha meningkatkan nilai tujuan dengan menukarkan variabel cobasic xs dengan koefisien positip dalam baris-z dengan variabel basis xr , sambil tetap mempertahankan penyelesaian layak dasar. Ini dicapai melalui uji rasio yang memilih xr , sedemikian sehingga dari (4.1) koefisien xs dalam persamaan xr negatif, dan dari (4.2) dengan menyelesaikan persamaan ini untuk xs dan mensubstitusikan xs dalam persamaan lainnya dihasilkanlah penyelesaian dasar layak lainnya. Operasi dasar ini disebut pivot dalam simpleks. Kaidah pivot menentukan variabel mana yang akan dipilih; misalnya, dengan mengikuti kaidah pivot Dantzig, akan dapat dipilih variabel dalam baris-z dengan koefisien positip terbesar. Dalam contoh (4.2), pivot pada variabel x1 dan x5, yang disebut pertama dipilih karena mempunyai koefisien positip terbesar dalam baris-z dan yang disebut terakhir dipilih secara sebarang dari x5 dan x6 karena ikatan uji rasio disebabkan degenerasi yang menghasilkan bentuk iteratif, x1 = 11x2 + 5x3 − 18x4 − 2x5 x6 = −4x2 − 2x3 + 8x4 + x5

(4.4)

z = 53x2 + 41x3 − 204x4 − 20x5 Degenerasi bisa menyebabkan metode simpleks gagal atau berpivot dari satu iterasi ke iterasi lainnya tanpa meningkatkan nilai tujuan. Metode simpleks bersiklus bisa gagal secara tak berhingga, yang menuju kembali iterasi-iterasi yang sudah


26 dihitung sebelumnya. (Terdapat kaidah pivot berhingga untuk mengendalikan pembentukan siklus). Dengan melanjutkan iterasi ini, metode simpleks dengan kaidah Dantzig mengunjungi iterasi-iterasi berikut : x1 = −0.5x3 + 4x4 + 0.75x5 − 2.75x6 x2 = −0.5x3 + 2x4 + 0.25x5 0.25x6

(4.5)

z = 14.5x3 − 98x4 − 6.75x5 − 13.25x6 x2 = x1 − 2x4 − 0.5x5 + 2.5x6 x3 = −2x1 + 8x4 + 1.5x5 − 5.5x6

(4.6)

z = −29x1 + 18x4 + 15x5 − 93x6 x3 = 2x1 − 4x2 − 0.5x5 + 4.5x6 x4 = 0.5x1 − 0.5x2 − 0.25x5 + 1.25x6

(4.7)

z = −20x1 − 9x2 + 10.5x5 − 70.5x6 x4 = −0.5x1 + 1.5x2 + 0.5x3 − x6 x5 = 4x1 − 8x2 − 2x3 + 9x6

(4.8)

z = 22x1 − 93x2 − 21x3 + 24x6 dan kembali ke iterasi awal (4.3), yang bersiklus melalui barisan basis {5,6}, {1,6}, {1,2}, {2,3}, {3,4}, {4,5}, {5,6}, dan seterusnya kembali berulang. Keenam basis dari ketaksamaan program linier (4.2), mendefinisikan polihedron empatdimensi, dan metode simpleks bersiklus antara basis-basis dengan verteks tunggal yang berlokasi di koordinat (0, 0, 0, 0). Geometri ini tidak bisa membantu memvisualisasikan siklus. Beale (1955) membangun suatu siklus untuk metode simpleks dengan mengkaji geometri dari masalah dual.


27 Dual dari pemrograman linier (4.2) adalah Minimumkan : ; ;w = 0y1 + 0y2 Dengan kendala : (1) 0.5y1 + 0.5y2 ≥ 10 (2) − 5.5y1 − 1.5y2 ≥ −57 (3) − 2.5y1 − 0.5y2 ≥ −9

(4.9)

(4) 9y1 + y2 ≥ −24 (5) y1 ≥ 0 (6) y2 ≥ 0 yang mempunyai enam ketidaksamaan dalam dua dimensi. Ternyata, iterasi dual hanyalah merupakan versi disamarkan dari iterasi-iterasi primal untuk masalah primal (transpose sistem) dengan tanda-tanda dibalikkan. Dalam metode simpleks dual, baris-w diasumsikan mempunyai koefisien yang semuanya nonnegatip. Variabel basis keluar dipilih dari variabel-variabel basis dengan konstanta negatip di ruas kanan kamus. Uji rasio digunakan untuk memilih variabel masuk sehingga baris-w tetap nonnegatif. Mudah dibuktikan bahwa metode simpleks dual yang diaplikasikan pada masalah dual, dengan kaidah pivot yang dipilih dengan tepat, akan mengikuti barisan pivot-pivot yang sama dengan yang diikuti metode simpleks primal pada masalah primal. Barisan basis-basis untuk masalah primal menjadi barisan cobasis-cobasis untuk masalah dual, dan demikian sebaliknya. Pembentukan grafik dari persoalan dual program linier (4.9), geometri di balik siklus metode simpleks mulai terbuka kerudungnya. Sehingga diperoleh susunan garis-garis, yang masing-masing membatasi ketaksamaan (4.9). Gambar 4.1 mengilustrasikan susunan ini.


28

Gambar 4.1 Contoh Siklus Chvátal (1983) Penafsiran geometri dua-dimensi dari metode simpleks dual tidak sulit, bila fungsi tujuan nol. Untuk sementara waktu, diabaikan kaidah pivot spesifik dan tinjau kembali pivot simpleks pada umumnya. Setiap garis dalam susunan bersesuaian dengan variabel dalam iteratif dual. Slack variabel yi untuk i = 3, . . . , n bersesuaian dengan garis i−2, sementara y1 dan y2 bersesuaian dengan garis n−1 dan n. Setiap perpotongan garis bersesuaian dengan penyelesaian dual basis yang diperoleh dengan menetapkan kedua variabel yang bersesuaian sama dengan nol. Ini adalah dua variabel cobasis dual untuk kamus dual yang bersesuaian. Sebagai contoh misalnya, iteratif dual dalam Tabel 4.1 dengan cobasis 1,2 bersesuaian dengan perpotongan garis berlabel 5 dan 6. (Catat bahwa variabel primal xi bersesuaian dengan garis yang membatasi ketaksamaan i dari program linier dual). Variabel basis yang dipilih dalam pivot bersesuaian dengan ketaksamaan yang dilanggar : dalam kasus ini, titik perpotongan terletak pada sisi yang salah dari garis 1, karenanya y3 adalah variabel basis keluar. Variabel masuk dipilih dari variabel-variabel dengan koefisien positip dalam persamaan untuk variabel keluar,


29 sehingga bahwa penyelesaian dasar baru akan memenuhi ketaksamaan yang bersesuaian dengan variabel masuk. Dalam kasus ini, dapat kita pilih y1 atau y2 sebagai variabel masuk. Akan tetapi, perhatikan situasi pada cobasis {1, 6} dari {1, 6} dapat berpivot ke cobasis 1,2. Karena ini berada pada sisi yang tepat dari garis 4, akibatnya tidak bisa berpivot ke cobasis 3,6 karena ini berada pada sisi yang salah dari garis 5. Variabel basis negatip mengindikasikan tingkat ketidaklayakan, misalnya, y3 = −10 + 0, 5y1 + 0, 5y2 mengindikasikan bahwa di perpotongan garis 5 dan garis 6, garis 1 tidak layak hingga -10/0,5 satuan sepanjang garis 5 dan hingga 10/0,5 satuan sepanjang garis 6 atas ruang vektor basis {y1, y2}. Metode simpleks dual, bila fungsi tujuan sama dengan nol, berakhir bila dicapai suatu titik di mana tidak ada ketaksamaan dilanggar (optimalitas) atau bila tidak bisa berpivot ke ketaksamaan yang dilanggar tanpa melanggar satu dari dua garis yang berpotongan (taklayak dual). Karena itu pivot masalah primal melalui siklus yang sama, dengan basis/cobasis saling dipertukarkan. Tabel 4.1 Primal dan dual Primal

Dual

x5 = 0 − 0.5x1 + 5.5x2 + 2.5x3 − 9x4 x6 = 0 − 0.5x1 + 1.5x2 + 0.5x3 − x4 z = 0x5 + 0x6 + 10x1 − 57x2 − 9x3 − 24x4

y3 = −10 − 0.5y1 − 0.5y2 y4 = 57 + 5.5y1 + 1.5y2 y5 = −9 + 2.5y1 + 0.5y2 y6 = 24 − 9y1 − y2 w = 0 + 0y1 + 0y2


30 Contoh berikut yang ditemukan dalam buku Chvátal (1983). Iterasi pertama siklus dipresentasikan sebagai: x5 = −0.5x1 + 5.5x2 + 2.5x3 − 9x4 x6 = −0.5x1 + 1.5x2 + 0.5x3 − x4 (4.10) x7 = 1 − x1 z = 10x1 − 57x2 − 9x3 − 24x4 dan terdiri dari tujuh variabel dan tiga persamaan. Akan tetapi, variabel x7 tidak pernah meninggalkan basis karena siklus hanya berpivot pada variabel x1 hingga x6 . Persamaan x7 = 1 − x1 hanya berfungsi membatasi program linier tetapi bisa dikeluarkan dari iterasi awal (4.10) tanpa mempengaruhi siklus. Karenanya banyak contoh lain ditemukan dalam literatur, termasuk contoh Hoffman, bisa direduksi dengan cara ini dan kemudian digambarkan grafiknya dalam dua dimensi. Ternyata, kemudian banyak yang ekuivalen secara kombinasi. Bagaimanapun juga geometri yang dijelaskan dalam bagian ini tidak terbatas pada siklus dengan m = 2, karena bila m = d garis terorientasi menjadi bidang-hiper terorientasi d-dimensi dan pivot simpleks dual mempunyai deskripsi yang analog dengan padanannya m = 2 (bergerak ke arah ketaksamaan yang dilanggar). Geometri bisa digunakan untuk menjelaskan contoh bersiklus dengan m ≥ 3 seperti Fukuda dan Luthi (1999), Marshall dan Suurballe (1969) dan Nering dan Tucker (1993). Akan tetapi, visualisasi suatu siklus pada susunan bidang-hiper dalam dimensi ≥ 3 bukanlah tugas mudah.


31 4.2 Konstruksi Siklus dalam Metode Simpleks Lee (1997), Hall dan McKinnon (2004) dan Zrnig (2006) mempresentasikan konstruksi aljabar dari siklus metode simpleks. Lee (1997) mengeneralisir contoh yang dibuat Hoffman, Hall dan McKinnon (2004) selanjutnya mengembangkan syarat perlu dan syarat cukup untuk membentuk contoh dari kelas siklus khusus dari metode simpleks dengan kaidah Dantzig yang hanya membutuhkan enam iterasi untuk menghindari siklus (yang merupakan bagian terkecil; lihat Beale (1955) serta Yudin dan Golshtein (1965) tentang bukti-bukti ini), sementara Zrnig (2006) mempresentasikan prosedur sistematik untuk membentuk contoh dengan menyelesaikan sistem ketaksamaan determinan nonlinier. Telah sama-sama diketahui bahwa setiap susunan dua-dimensi dari k ketaksamaan bisa disandikan sebagai kamus primal dengan k persamaan dan k + 2 variabel. Untuk sementara waktu, dengan mengabaikan kaidah pivot spesifik dan memperhatikan pivot simpleks pada umumnya. Hanya dua kaidah dasar yang perlu diikuti untuk membangun siklus dalam metode simplek, yaitu:

1. Setiap pivot harus merupakan pivot simpleks : pivot yang melangkah dari perpotongan garis r dan s ke perpotongan garis r dan t adalah pivot simpleks jika dan hanya jika ketidakaksamaan yang dibatasi oleh t dilanggar di {r, s} dan ketidaksamaan yang dibatasi s dipenuhi di {r, t}. 2. Siklus harus digambarkan oleh loop tertutup dalam diagram. Path terdiri dari rangkaian memutar kiri dan memutar kanan berselang-seling dalam susunan garis karena titik berikutnya harus selalu memenuhi kedua garis yang berpotongan saat ini (lihat Gambar 4.2).


32

Gambar 4.2 Putaran Kekiri dan Kekanan Dengan menggunakan sifat ini untuk membangun siklus, maka dapat diikuti konstruksi dalam Gambar 4.3. Pertama, dengan menggunakan penggal-penggal garis, ditarik path yang terdiri dari rangkaian memutar kiri dan memutar kanan berselang-seling yang membentuk loop tertutup. Dapat dilihat bahwa jumlah titik harus genap untuk membentuk loop tertutup, dan loop tentu saja bisa memotong diri sendiri (seperti dalam Gambar 4.3). Selanjutnya, dipilih sumbu koordinat (y1 , y2), dan garis-garis yang membatasi y1 = 0, y2 = 0 sehingga loop terletak di kuadran positip.

Gambar 4.3 Kontruksi Siklus


33 Kemudian, dengan mencocokkan garis melalui masing-masing penggal garis di dalam loop. Untuk setiap garis, alokasikan arah kelayakan yang bertepatan dengan path (lihat Gambar 4.5 dan 4.6 sebagai contohnya). Hitung ketaksamaan ini untuk (y1, y2), dan tambahkan fungsi tujuan nol untuk memperoleh program linier dual. Program linier dual mencakup ketaksamaan y1 ≥ 0 dan y2 ≥ 0, yang bisa dicoret karena tidak terlibat dalam siklus. Selanjutnya, dengan dualitas, diubah menjadi program linier primal, dengan menambahkan variabel slack, dan hitung iterasi awal: x2 = 0 + x1 − 10x3 + 10x4 − 101x7 + 10x8 x5 = 0 + x3 − x4 + x6 + 10x7 − 0x8

(4.11)

z = −5x1 − 15x3 + 10x4 − 75x6 − 165x7 + 85x8 Sekarang pivot simpleks dalam diagram, disesuaikan dengan pivot simpleks dalam program linier primal, yang bersiklus berulang-ulang melalui barisan {x2 , x5}, {x2 , x8}, {x4, x8}, {x4, x6 }, {x1 , x6}, {x1, x7}, {x3, x7 }, {x3 , x5}. Dengan memperluas konstruksi visual ke dimensi yang lebih tinggi, sama nontrivialnya dengan memvisualisasikan susunan bidang-hiper dalam dimensi yang lebih tinggi. Akan tetapi, dengan menggunakan konstruksi dua-dimensi seperti yang dijelaskan di atas, Kaluzny (2006) menghasilkan program linier dengan m+n ketaksamaan dalam n dimensi atas mana metode simpleks bisa bersiklus dan mengunjungi Θ(nm ) basis yang berbeda. Agar siklus mengikuti kaidah pivot spesifik, dibutuhkan tahap tambahan. Catat bahwa untuk setiap ketaksamaan ai1 y1 + ai2y2 ≤ bi untuk i = 1, . . . , 8, dapat ditentukan skala ruas kiri dan kanan dengan konstanta positip Ci sesuai yang dikehendaki, karena ai1y1 + ai2 y2 ≤ bi ⇔ Ci (ai1y1 + ai2 y2) ≤ Cbi. Konstanta


34 ini pada gilirannya menentukan skala variabel primal, yang menghasilkan iterasi: C1 x1 − C2 C3 x5 = 0 + x3 − C5

x2 = 0 +

10C3 10C4 10C7 101C8 x3 + x4 − x7 + x8 C2 C2 C2 C2 C4 C6 10C7 10C8 x4 + x6 + x7 − x8 C5 C5 C5 C5

(4.12)

z = −5C1 x1 − 15C3 x3 + 10C4 x4 − 75C6 x6 − 165C7 x7 + 85C8 x8 Dengan berpivot sepanjang siklus yang diinginkan, iterasi yang bersesuaian sepanjang path membatasi nilai Ci yang dapat dipilih sehingga kaidah pivot dipenuhi. Sebagai contoh misalnya, agar pivot pertama memenuhi kaidah Dantzig, diperlukan 85C8 > 10C4 dalam kamus primal. Untuk setiap pemilihan iterasi dan kaidah pivot berikutnya, maka diakumulasikan semua batasan relatip atas Ci dengan cara ini. Hanya jika ditentukan pengurutan layak dari Ci kemudian dengan mengikuti kaidah pivot akan dihasilkan siklus begitu ditetapkan nilai Ci untuk memenuhi batasan. Jika urutan tidak layak, maka tidak soal berapa nilai yang dipilih untuk Ci , metode simpleks yang mengikuti kaidah pivot akan menyimpang jauh dari siklus diinginkan yang diambil. Sehingga dapat dengan mudah memeriksa bahwa koefisien untuk variabel xj dalam iterasi baris-z berskala tiada lain adalah Cj kali koefisien variabel xj dalam baris-z kamus tak berskala untuk basis yang sama). Dalam contoh kita, kita butuhkan 85C8 > 10C4 , 85C6 > 10C1 , 80C7 > 10C3 , 135C5 > 15C2 , jelas merupakan pengurutan layak. Dengan demikian, dengan menetapkan Ci = 1 untuk i = 1, . . . , 8 akan menghasilkan siklus metode simpleks yang mengikuti kaidah pivot Dantzig. Pada dasarnya, diberikan siklus yang dibangun secara geometrik, Ci adalah satu-satunya parameter yang bisa dimainkan untuk memungkinkan mencapai siklus dengan mengikuti kaidah pivot tertentu.


35

Gambar 4.4 Contoh Siklus dalam ProgramLinier yang Layak

Gambar 4.5 Contoh Siklus dalam ProgramLinier yang Tidak Layak

Proses ini mempunyai analog geometrik yang bisa menuntun dalam usaha membangun diagram dimana kaidah Dantzig (misalnya) mengikuti loop. Syarat cukup adalah sebagai berikut: Diberikan suatu diagram, untuk setiap titik sepanjang loop, dengan mendaftarkan persyaratan kaidah pivot (misalnya, koefisien positip terbesar) yang dibu-


36 tuhkan agar siklus diikuti. Sebagai contoh misalnya, di titik A dalam Gambar 4.3, diinginkan berpivot untuk garis 4 yang dilanggar dan bukan garis 2 atau 6 yang juga dilanggar di A. Ini diterjemahkan menjadi batasan C4 > C2 dan C4 > C6 . Batasan serupa diperoleh dari semua titik B, C, D, E dan F sepanjang siklus. Jika himpunan batasan dipenuhi (pengurutan layak ada), seperti dalam kasus di sini, maka setelah pengubahan ke dalam bentuk iterasi, dapat dilanjutkan untuk menemukan nilai yang cocok untuk Ci sedemikian sehingga kaidah Dantzig akan bersiklus pada program linier yang dihasilkan. Dalam hal ini hanya perlu mengakumulasi batasan-batasan atas Ci berbobot dari barisan kamus-kamus dan menetapkan nilai yang tepat untuk setiap Ci . Tentu saja, yang menjadi tantangan adalah menggambar diagram dengan mencamkan semua ini karena tidak ada jaminan keberhasilan.

Akan tetapi,

dengan menggunakan pendekatan geometrik ini, Kalyzny (2006) menunjukkan bahwa famili siklus-siklus dengan panjang n ≥ 10 yang dikembangkan Lee (1997) bisa dibuat dengan memenuhi kaidah Dantzig. Namun demikian, mungkin perlu kiranya menempuh jalur konstruksi aljabar untuk membangun bagian-bagian spesifik siklus yang mengikuti kaidah pivot tertentu.


BAB 5 KESIMPULAN DAN SARAN

5.1 Kesimpulan 1. Dua kaidah dasar yang perlu diperhatikan dalam mengamati terbentuknya siklus dalam metode simpleks, yaitu : a. Setiap pivot harus merupakan pivot simpleks : pivot yang melangkah dari perpotongan garis r dan s ke perpotongan garis r dan t adalah pivot simpleks jika dan hanya jika ketidakaksamaan yang dibatasi oleh t dilanggar di {r, s} dan ketidaksamaan yang dibatasi s dipenuhi di {r, t}. b. Siklus digambarkan oleh loop tertutup dalam diagram. Path terdiri dari rangkaian memutar kiri dan memutar kanan berselang-seling dalam susunan garis karena titik berikutnya harus selalu memenuhi kedua garis yang berpotongan saat ini.

Gambar 5.1 Geometri Pembentukan Siklus

2. Pembentukan siklus dalam metode simpleks dapat mengakibatkan pemrograman linier bisa gagal berakhir (tidak mencapai solusi optimal), karena itu pembentukan siklus harus dihindari. 37 Misnawati : Konstruksi Siklus Dalam Metode Simpleks, 2009

38 3. Berikut diberikan versi geometri untuk konstruksi siklus dalam metode simpleks: a. Contoh siklus dalam pemrograman linier yang Layak (mempunyai solusi optimal)

Gambar 5.2 Siklus Pemrograman Linier yang Layak

b. Contoh siklus dalam pemrograman linier yang tidak Layak (tidak memiliki solusi optimal)

Gambar 5.3 Siklus Pemrograman Linier yang Tidak Layak


39 5.2 Saran Untuk studi lanjutan berikutnya, mungkin perlu kiranya menempuh jalur konstruksi aljabar untuk membangun bagian-bagian spesifik siklus yang mengikuti kaidah pivot tertentu.


DAFTAR PUSTAKA

Balinski, M., A. Tucker. Duality Theory of Linear Programs - a Constructive Approach with Applications, SIAM Review 11 (3) : 347-77, 1969. Beale, E. Cycling in the Dual Simplex Method, Naval Research Logistics Quarterly 2 (4) : 269-75, 1955. Chvátal, V. Linear Programming, Freeman, New York, 1983. Dantzig, G. Linear Programming and Extensions, Princeton University Press, NJ, 1963. Gale, D., H. W. Kuhn, and A. W. Tucker, Linear Programming and the Theory of Games, in T. C. Koopmans (ed.), Activity Analysis of Production and Allocation, John Wiley & Sons, New York, 1951. Gass, S. Linear Programming : Methods and Applications, 5th edition, McGrawHill Book Company, New York, 1985. Gass, S., S. Vinjamuri. Erratum to ”Cycling in Linear Programming Problems” (Computer, Operation Research. 2004 31(2) : 303-311), Computer, Operation Research. 33(8) 2445, 2006. Hall, J., K McKinnon, The Simplest Examples where the Simplex method Cycles and Conditions where EXPAND fails to Prevent Cycling. Math. Programming 100(1) 133-150, 2004. Hoffman, A. Cycling in the Simplex Algorithm, National Bureau of Standards, Washington, 1953. Lee, J. Hofmanns Circle Untangled, SIAM Review 39 : 98-105, 1997. Marshall, K., J. Suurballe, A Note on Cycling in the Simplex Method, Naval Research Logistics Quartely 16 (1) 121-37, 1969. Nering, E., A. Tucker, Linear Programs and Related Problems, Academic Press, Boston, 1993. Sierksma, G. Linear and Integer Programming, 2n d ed. Marcel Dekker Inc., New York, 1996. Solow, D. Linear Programming : An Introduction to Finite Improvement Algoritms, North-Holland Press, Amsterdam, 1984. Zörnig, P., Systematic Construction of Examples for Cycling in the Simplex Method, Computer Operation Res. 2247-2262, 2006.


41

LAMPIRAN A PEMBENTUKAN SIKLUS DALAM METODE SIMPLEKS, CONTOH DARI CHVATAL


44

LAMPIRAN B BEBERAPA CONTOH SIKLUS YANG DITEMUKAN DALAM LITERATUR


KONSTRUKSI SIKLUS DALAM METODE SIMPLEKS

Recommend Documents