PROGRAM LINEAR BILANGAN BULAT DUAL SKRIPSI

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

PROGRAM LINEAR BILANGAN BULAT DUAL

SKRIPSI

Diajukan Untuk Memenuhi Salah Satu Syarat Memperoleh Gelar Sarjana Sains (S.Si) Program Studi Matematika

Oleh: Bernadeta Widiasih NIM : 013114017

PROGRAM STUDI MATEMATIKA JURUSAN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM

UNIVERSITAS SANATA DHARMA YOGYAKARTA 2007


ii


iii


HALAMAN PERSEMBAHAN

Terima kasih Telah mengajariku membedakan yang benar dan yang salah Mendorongku untuk mempertahankan mimpimimpiku Menunjukkan padaku untuk tidak terpengaruh oleh rintangan Dan untuk mengubah kebingunganku menjadi senyuman Telah mengatakan bahwa kalian menyayangiku Menunjukkan betapa istimewanya cinta itu Menghapuskan air mataku kala aku sedih Dan untuk menenangkanku saat aku ingin marah Telah membantu sesama dengan perbuatan baik kalian Mengajariku bahwa aku pun mesti menolong sesama Memelukku ketikaaku merasa sunyi Dan membisikkan padaku

AKU SAYANG PADAMU Terima kasih keluargaku atas segala yang kalian lakukan Entah bagaimana jadinya diriku tanpa kalian

Kupersembahkan karya ini untuk: Tuhan Yesus Kristus dan Bunda Maria Almarhum Bapak,

Ibu, Mba eta, Lia dan

Semua Keluarga Besarku. iv


v


ABSTRAK

Program linear bilangan bulat merupakan bagian dari program linear di mana menginginkan penyelesaian dalam bentuk bilangan bulat. Dalam program linear bilangan bulat terdapat dua model, yakni program linear bilangan bulat fraksional dual dan program linear bilangan bulat dual. Program linear bilangan bulat fraksional dual memungkinkan adanya nilai variabel berupa bilangan pecahan dalam perhitungannya, sedangkan dalam program linear bilangan bulat dual semua nilai variabel dalam perhitungan haruslah berupa bilangan bulat. Masalah program linear bilangan bulat dapat diselesaikan dengan menggunakan beberapa metode, seperti metode bidang pemotong, metode cabang dan batas, dan metode enumerasi. Pada penulisan ini masalah program linear bilangan bulat akan diselesaikan dengan metode bidang pemotong. Penyelesaian masalah program linear bilangan bulat dengan metode bidang pemotong dimulai dengan mengubah bentuk baku menjadi bentuk kanonik, dan menyusun tabel awal. Setelah itu dilanjutkan dengan mencari baris sumber dan kolom pivot serta menentukan bentuk kendala bidang pemotong. Bentuk kendala bidang pemotong tersebut kemudian ditambahkan ke dalam tabel, yang selanjutnya diselesaikan dengan metode simpleks. Proses iterasi ini diulang hingga penyelesaian optimum dicapai.

vi


ABSTRACT

Integer programming is a part of linear programming where its solutions are integer. There are two models of integer programming, dual fractional integer programming and dual all-integer integer programming. The value of variables in calculations of dual fractional integer programming can be in the form of fractional, while in dual all-integer integer programming all of variable values in calculations must be in the form of integer. Some methods, such as cutting plane method, branch and bound method and enumeration method can solve the integer programming problem. In this paper, we use cutting plane method to solve integer programming problem. The first step in solving integer programming problem by cutting plane method is changing standard form to canonic form, and arranging the beginning table. After that, we choose the source row and pivot column, and then determine the form of the Gomory Cut. We will add the Gomory Cut into the table and solve it by dual simplex method. We repeat this iteration process until optimum integer solution.

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 Ir. Ig. Aris Dwiatmoko, M.Sc selaku Dekan fakultas MIPA yang telah memberi dukungan dalm penulisan skripsi ini. 3. Bapak Y.G. Hartono, S.Si, M.Sc selaku Ketua Program Studi Matematika, dan dosen penguji yang memberikan dukungan, saran dan kritik dalam 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. 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. Almarhum Bapak (pak aku belum bisa buat bapak bahagia dengan kelulusan ini tapi aku tau bapak selalu menyertai hidupku, makasih pak aku sayang bapak), viii


Ibu, Mba eta, Lia dan semua keluargaku tercinta atas kasih sayang, doa, semangat, dukungan dan kesabarannya menanti kelulusan ini. 8. Sahabat-sahabatku seperjuangan angkatan 2001: Maria(jangan lupain masa2 qta nunggu 21 ya!!!), Indah, Erika, Ajeng(tunggu aku dijakarta ya), Very, Upik, Yuli, Dani, Tabita, Fanya(makasih laptopnya), Andre, Ariel, Agnes, Wiwit, Rita+Alam (makasih semangat n bantuannya), 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. 9. Untuk seseorang yang selama ini mengisi hatiku yang telah memberi dukungan, semangat, nasehat, doa, cinta dan rasa sayangnya. 10. Untuk saudara-saudaraku yang menemaniku dijogja: Wahyu(makasih dah mau anter aku n pinjemin komputernya), Nita, Wiwit, mas Lus dan keluargaku yang telah memberi dukungan, semangat, saran dan doanya. 11. Anak-anak kost gang endro no 8 : Mba lina(makasih atas perhatiannya hingga ku bisa mengerti arti hidup), Mba rini, Mba armi, Ayu, Tia, Mery, F3, Cu2, Weni, Rini, Ika, Lia, Ratna, Riska, Winda,Beni dan teman-teman kost dari awal sampai akhir aku kuliah yang telah memberi dukungan, semangat, doa dan candanya. 12. 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.

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 ……………………………………………………….……. xii DAFTAR TABEL ………………………………………………………….……. xiii BAB I

PENDAHULUAN ……………………………………………..……. 1 A. Latar Belakang Masalah …………………………………….…… 1 B. Rumusan Masalah ………………………………………...…….. 2 C. Pembatasan Masalah ………………………………………...….. 2 D. Tujuan Penulisan …………………………………………………. 3 E. Manfaat Penulisan ……………………………………………….. 3 F. Metode Penulisan ……………………………..…………..……... 3 G. Sistematika Penulisan ……………………….…………………… 4

x


BAB II

PROGRAM LINEAR DENGAN DUAL……………………..……...

5

A. Program Linear ……………………………………………….…… 5 B. Metode Grafik ……………………………………………….…… 9 C. Metode simpleks…………………………………...……………... 10 D. Metode Simpleks Dual ……………………………………..…….. 16 E. Program Linear Bilangan Bulat ..…………………………...…… 21 BAB III

PROGRAM LINEAR BILANGAN BULAT FRAKSIONAL DUAL 25 A. Masalah Program Linear Bilangan Bulat........…………………...

25

B. Penyelesaian Masalah Program Linear Bilangan Bulat Fraksional Dual ……………………………………………………….….…… 29 BAB IV

PROGRAM LINEAR BILANGAN BULAT DUAL .........................

60

A. Masalah Program Linear Bilangan Bulat Dual Dengan Metode Bidang Pemotong...................................................................……

60

B. Penyelesaian Masalah Program Linear Bilangan Bulat Dual......... 68 BAB IV

PENUTUP .....................................................................................….. 81 A. Kesimpulan ……………......................................................…….. 81 B. Saran ………………………………………………………...…… 82

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

xi


DAFTAR GAMBAR

Halaman Gambar 2.1.Ilustrasi Penyelesaian Masalah Program Linear

dengan metode

grafik……………………………………………………………… 10 Gambar 3.1.Ilustrasi Penyelesaian Masalah Program Linear Bilangan Bulat dengan metode bidang pemotong …………..……....……………...............

26

Gambar 3.2.Penyelesaian Masalah Program Linear Bilangan Bulat Fraksional Dual……………………………………………………………….. 51 Gambar 4.1. Penyelesaian Masalah Program Linear Bilangan Bulat Dual……... 80

xii


DAFTAR TABEL

Halaman Tabel 2.1 Tabel Awal Simpleks…………………………………………………………… 14 Tabel 2.2 Tabel Awal Simpleks Dual………………………………………………...…… 19 Tabel 3.1 Tabel Awal Program Linear Bilangan Bulat Fraktional Dual.......…………..... 30 Tabel 3.2. Tabel Dengan Bentuk Kendala Bidang Pemotong........ ………………………. 32 Tabel 3.3. Tabel Awal Pada Contoh Masalah Program Linear Bilangan Bulat…………

40

Tabel 3.4. Tabel Setelah Operasi Baris Elementer Pada Iterasi 1.…………………...….

41

Tabel 3.5. Tabel Setelah Operasi Baris Elementer Pada Iterasi 2………………………..

42

Tabel 3.6. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 1………………...….

45

Tabel 3.7. Tabel Setelah Dilakukan Operasi Baris Elementer Pada Iterasi 1.........……..

46

Tabel 3.8. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 2................................

48

Tabel 3.9. Tabel Setelah Dilakukan Operasi Baris Elementer Pada Iterasi 2....................

49

Tabel 3.10. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 3.............................

54

Tabel 3.11. Tabel Setelah Dilakukan Operasi Baris Elementer Pada Iterasi 3................

55

Tabel 3.12. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 4............................

57

Tabel 3.13. Hasil setelah dilakukan operasi baris elementer pada iterasi 4.....................

58

Tabel 4.1. Tabel Awal Program Linear Bilangan Bulat..................................................

65

Tabel 4.2. Tabel Awal Pada Contoh Masalah Program Linear Bilangan Bulat.............

73

Tabel 4.3. Tabel Bentuk Kendala Bidang Pemotong Pada Iterasi 1...............................

75

Tabel 4.4. Tabel Setelah Dilakukan Operasi Baris Elementer Pada Iterasi 1..................

75

Tabel 4.5. Tabel Dengan Bentuk Kendala Bidang Pemotong Pada Iterasi 2..................

78

Tabel 4.6. Tabel Setelah Dilakukan Operasi Baris Elementer Pada Iterasi 2.................

78

xiii


1

BAB I P ENDAHULUAN

A. Latar Belakang Masalah Program linear adalah teknik optimasi yang bertujuan untuk menentukan pemecahan masalah dari suatu program matematika yang linear sehingga dapat ditemukan nilai sasaran yang optimal. Hasil akhir penyelesaian masalah program linear bisa dapat berupa bilangan pecahan atau bilangan bulat. Dalam penyelesaian masalah yang berupa bilangan bulat diperlukan suatu penyelesaian khusus untuk menjawabnya, yaitu program linear bilangan bulat. Program linear bilangan bulat merupakan salah satu bentuk dari program linear dengan satu variabel atau lebih. Dalam masalah program linear bilangan bulat ini variabel masukannya bernilai bilangan bulat. Banyak sekali ditemukan permasalahan program linear bilangan bulat dalam kehidupan sehari-hari dan industri. Permasalahan tersebut tidak dapat diselesaikan hanya dengan program linear biasa, misalnya masalah produksi, masalah transportasi, masalah penjadwalan para pekerja dan mesin-mesin kantor, desain jaringan telekomunikasi dan masalah salesmen yang berpergian (traveling salesman). Dalam program linear bilangan bulat terdapat dua model, yakni program linear bilangan bulat fraksional dual dan program linear bilangan bulat dual. Program linear bilangan bulat fraksional dual memungkinkan adanya nilai variabel berupa bilangan pecahan dalam perhitungannya, sedangkan dalam


2

program linear bilangan bulat dual semua nilai variabel dalam perhitungan haruslah berupa bilangan bulat. Masalah program linear bilangan bulat

dapat diselesaikan dengan

menggunakan beberapa metode, seperti metode bidang pemotong, metode cabang dan batas, dan metode enumerasi. Pada penulisan ini masalah program linear bilangan bulat

akan diselesaikan dengan metode bidang pemotong. Metode

bidang pemotong untuk pertama kalinya diaplikasikan pada masalah program linear bilangan bulat fraktional dual kemudian diperbaiki menjadi masalah program linear bilangan bulat dual. Penyelesaian kedua masalah program linear bilangan bulat tersebut menggunakan metode simpleks dual.

B. Rumusan Masalah Pokok permasalahan yang akan dibahas dalam skripsi ini dapat dituliskan dengan beberapa pertanyaan sebagai berikut : 1. Bagaimana menyelesaikan masalah program linear bilangan bulat fraksional dual dengan metode bidang pemotong ? 2. Bagaimana menyelesaikan masalah program linear bilangan bulat dual dengan metode bidang pemotong ?

C. Pembatasan Masalah Dalam skripsi ini hanya akan dibahas tentang program linear bilangan bulat, yakni program linear bilangan bulat fraksional dual dan program linear bilangan bulat dual yang diselesaikan dengan metode bidang pemotong yang


3

menggunakan metode simpleks dual dan landasan teori yang berkaitan dengan aljabar linear seperti sistem persamaan linear, matriks dan ruang vektor yang telah dipelajari pada saat kuliah tidak akan dibahas dalam skripsi ini.

D. Tujuan Penulisan Sesuai dengan latar belakang di atas, penulisan skripsi ini bertujuan untuk dapat menyelesaikan masalah program linear bilangan bulat khususnya tentang masalah program linear bilangan bulat fraksional dual dan masalah program linear bilangan

bulat

dual

dengan

metode

bidang

pemotong

dan

dapat

dipertanggungjawabkan langkah demi langkah.

E. Manfaat Penulisan 1. Dapat menyelesaikan masalah program linear bilangan bulat fraksional dual 2. Dapat menyelesaikan masalah program linear bilangan bulat dual

F. Metode Penulisan Metode penulisan yang digunakan dalam penulisan skripsi ini adalah metode studi pustaka, yaitu dengan membaca dan mempelajari materi dari buku buku acuan yang berkaitan dengan topik skripsi ini, sehingga tulisan ini tidak ada penemuan hal-hal yang baru.


4

G. Sistematika Penulisan Sistem penulisan skripsi ini terdiri dari 5 bab dengan urutan sebagai berikut: Bab I

PENDAHULUAN Bab ini menjelaskan uraian mengenai hal-hal yang menjadi dasar dalam pembahasan skripsi ini. Uraian tersebut berisi latar belakang masalah, perumusan masalah, pembatasan masalah, tujuan penulisan, manfaat penulisan, metode penulisan dan sistematika penulisan.

BAB II PROGRAM LINEAR DENGAN DUAL Bab ini memberikan penjelasan secara singkat beberapa dasar pengetahuan, yaitu tentang program linear, metode grafik, metode simpleks, metode simpleks dual dan program linear bilangan bulat. BAB III PROGRAM LINEAR BILANGAN BULAT FRAKSIONAL DUAL Bab ini membahas tentang langkah-langkah penyelesaian masalah program linear bilangan bulat fraksional dual menggunakan metode bidang pemotong. BAB IV PROGRAM LINEAR BILANGAN BULAT DUAL Bab ini membahas tentang langkah-langkah penyelesaian masalah program linear bilangan bulat dual menggunakan metode bidang pemotong. BAB V Penutup Bab ini berisi beberapa kesimpulan dan saran berdasarkan hasil pembahasan dan keseluruhan proses penyusunan skripsi.


5

BAB II PROGRAM LINEAR DENGAN DUAL

A. Program Linear Penerapan program linear untuk pertama kalinya adalah di bidang perencanaan militer, yakni pada perang dunia II oleh angkatan bersenjata Amerika Serikat dan Inggris. Kemudian pada tahun1930-an ahli matematika seperti Von Neuman dan Leontief melahirkan teknik-teknik penyelesaian masalah program linear dengan menggunakan pendekatan aljabar linear (aljabar matriks). Karya Leontif yang terkenal adalah model input-output. Setelah itu ahli matematika Dr George B. Dantzig, seorang anggota dari pasukan Angkatan Udara tersebut, memformulasikan masalah program linear secara umum dan menemukan penyelesaian dengan metode simpleks pada tahun 1947. Program linear adalah suatu metode optimasi yang digunakan untuk menyelesaikan masalah dengan fungsi sasaran dan kendala-kendala berbentuk linear. Secara umum masalah program linear dapat dinyatakan sebagai berikut : 1. Bentuk Baku Masalah Program Linear : Minimumkan ( atau maksimumkan) : z = c1 x1 + c2 x2 + K + cn xn

(2.1)


6

dengan kendala-kendala : a 11 x 1 + a 12 x 2 + K + a 1 n x n { ≤ , = , ≥ }b1

⎫ a 21 x 1 + a 22 x 2 + K + a 2 n x n { ≤ , = , ≥ }b 2 ⎪⎪ ⎬ M O O M ⎪ a m 1 x 1 + a m 2 x 2 + K + a mn x n { ≤ , = , ≥ }b m ⎪⎭

(2.2)

x j ≥ 0, j = 1,2, K, n

(2.3)

Rumus di atas dapat diringkas sebagai berikut : Minimumkan ( atau maksimumkan) : n

z = ∑cjxj

(2.4)

j =1

dengan kendala n

∑a j =1

ij

x j (≤, =, ≥) bi

xj ≥ 0

, i = 1,2, K , m

, j = 1,2,K , n

(2.5) (2.6)

2. Bentuk Matriks Masalah Program linear : Minimumkan (atau maksimumkan) : z = cx

(2.7)

dengan kendala-kendala : Ax{≤, =, ≥}b x≥0

dengan :

⎡a11 ⎢a A = ⎢ 21 ⎢M ⎢ ⎣a m1

a12 K a1n ⎤ ⎡ x1 ⎤ ⎡b1 ⎤ ⎥ ⎢ ⎢b ⎥ ⎥ a 22 K a 2 n ⎥ x2 ⎥ ⎢ ,x = , b = ⎢ 2 ⎥ , c = (c1 , c 2 , K , c n ) ⎢M ⎥ ⎢M ⎥ O M ⎥ ⎥ ⎢ ⎥ ⎢ ⎥ a m 2 K a mn ⎦ ⎣ xn ⎦ ⎣bn ⎦

(2.8)


7

Definisi 2.1 Fungsi sasaran atau fungsi tujuan Fungsi sasaran masalah program linear berbentuk p

z = ∑cjxj j =1

dengan p merupakan banyaknya variabel, x j merupakan variabel ke- j , dan c j merupakan koefisien ongkos dari variabel ke- j .

Definisi 2.2 Kendala utama dan kendala tak negatif Persamaan atau pertidaksamaan dalam masalah program linear n

∑a j =1

i, j

x j (≤, =, ≥ )bi , i = 1,2,..., m

disebut kendala utama, dengan m merupakan banyaknya kendala, dan ai , j (koefisien teknis) merupakan koefisien kendala ke- i dari variabel ke- j dan bi menyatakan konstanta di ruas kanan untuk kendala ke- i . Sedangkan x j ≥ 0; j = 1,2,..., p disebut kendala tak negatif

Untuk mengembangkan suatu metode penyelesaian, secara umum harus sesuai dengan karakter dari masalah program linear. Karakter tersebut dinyatakan dalam bentuk baku sebagai berikut : 1. Fungsi sasarannya berpola minimum atau maksimum. 2. Semua kendalanya berbentuk persamaan. Bentuk ini disebut bentuk kanonik dari masalah program linear. 3. Semua variabel keputusan xi adalah tak negatif.


8

Definisi 2.3 Penyelesaian layak Penyelesaian layak adalah penyelesaian yang memenuhi semua kendala yakni kendala utama dan kendala tak negatif.

Definisi 2.4 Penyelesaian optimum Penyelesaian optimum adalah penyelesaian layak yang takhingga banyak yang mengoptimumkan fungsi sasaran.

Definisi 2.5 Penyelesaian basis Suatu vektor x merupakan penyelesaian basis, jika: (i) x memenuhi persamaan kendala utama dalam program linear. (ii) kolom-kolom matriks kendala yang bersesuaian dengan vektor tak nol x adalah bebas linear.

Definisi 2.6 Penyelesaian layak basis Suatu vektor x disebut penyelesaian layak basis jika x adalah penyelesaian basis dan memenuhi kendala tak negatif x ≥ 0 .

Definisi 2.7 Penyelesaian layak basis optimum Suatu vektor x disebut penyelesaian layak basis optimum jika x adalah penyelesaian layak basis yang juga mengoptimumkan fungsi sasaran.


9

Masalah program linear biasanya diselesaikan dengan dua metode penyelesaian, yaitu metode grafik dan metode simpleks. Masalah program linear dapat diselesaikan dengan menggunakan metode grafik bila masalah tersebut hanya memiliki dua variabel keputusan. Tetapi untuk masalah yang memiliki variabel keputusan lebih dari dua tidak mungkin menggunakan metode grafik. Lalu pada tahun 1947 George Dantzig dan pakar-pakar lainnya mengembangkan metode simpleks yang dapat menyelesaikan masalah program linear yang memuat tiga variabel keputusan atau lebih.

B. Metode Grafik Masalah program linear dengan dua variabel dapat diselesaikan menggunakan metode grafik. Meskipun masalah program linear jarang yang hanya memuat dua variabel tetapi metode grafik memudahkan dalam penyelesaian masalah tersebut. Masalah program linear dapat diilustrasikan dengan melihat Gambar 2.1, yakni Pasangan

(x1 , x 2 )

yang memenuhi semua kendala disebut

penyelesaian layak (feasible solution). Titik-titik dalam daerah layak disebut titik layak. Himpunan titik layak yang terlihat dalam Gambar 2.1, yakni daerah OABCD adalah daerah layak yang diperoleh dari perpotongan kendala-kendala utama. Grafik fungsi sasaran ini berupa garis lurus z dan disebut garis selidik karena menggambarkan pasangan-pasangan ( x1 , x 2 ) yang memberikan nilai z yang sama. Pada masalah program linear yang memaksimumkan fungsi sasaran z maka akan ditemukan penyelesaian optimum titik B, yakni titik yang memaksimumkan fungsi sasaran.


10

x

2

D C

B

0

z

x1

A

Gambar 2.1. Ilustrasi Penyelesaian Masalah Program Linear dengan metode grafik

C. Metode simpleks Untuk menyelesaikan masalah program linear dengan metode simpleks, kendala yang masih berbentuk pertidaksamaan ini harus diubah dahulu ke bentuk persamaan dengan penambahan variabel slack atau variabel pengetat yang mempunyai koefisien ongkos nol. Jika kendala berpola kurang dari (≤) , yakni

kendala berbentuk pertidaksamaan :

a k1 x1 + a k 2 x 2 + K + a kn x n ≤ bk maka kendala tersebut dapat diubah ke bentuk persamaan dengan menambah variabel pengetat x n +1 dengan x n +1 > 0 . Dengan demikian , persamaan untuk kendala tersebut adalah

a k1 x1 + a k 2 x 2 + K + a kn x n + x n +1 = bk

, x n +1 > 0 .


11

Dengan cara yang sama, kendala berpola lebih besar dari (≥) , yakni kendala berbentuk pertidaksamaan :

a k1 x1 + a k 2 x 2 + K + a kn x n ≥ bk dapat diubah ke bentuk persamaan dengan mengurangi pertidaksamaan tersebut dengan variabel pengetat x n +1 dengan x n +1 > 0

a k1 x1 + a k 2 x 2 + K + a kn x n − x n +1 = bk

, x n +1 > 0

Untuk menyesuaikan dengan bentuk kendala baru, fungsi sasaran yang semula berbentuk z = c1 x1 + c2 x2 + K + cn xn diubah menjadi z = c1 x1 + c 2 x 2 + K + c n x n + c j ( x n +1 + K + x p ) , j = n + 1, n + 2, K , p c n +1 = c n + 2 = K = c p = 0

dengan

dan xi , i = n + 1, n + 2, K, p

adalah variabel

pengetat. Dengan demikian masalah yang telah diubah kedalam bentuk kanonik akan menjadi seperti ini :

Minimumkan ( atau maksimumkan ) : n

z = ∑cjxj

(2.9)

j =1

dengan kendala n

∑a j =1

ij

x j = bi

xj ≥ 0

, i = 1,2, K , m

, j = 1,2, K , n

(2.10) (2.11)


12

Definisi 2.8 Bentuk kanonik

Bentuk pertidaksamaan yang sudah diubah dalam bentuk persamaan disebut bentuk kanonik dari masalah program linear.

Berikut ini akan diberikan contoh masalah program linear yang diubah ke bentuk kanonik

Contoh 2.1

Ubah soal dibawah ini ke bentuk kanonik. Maksimumkan : z = 10 x1 − 20 x2 + 5 x3 dengan kendala x1 − x 2 + x3 ≤ 8 2 x1 − x 2 + x3 ≤ 10

Penyelesaian : Pada masing-masing kendala yang masih berbentuk pertidaksamaan ditambahkan satu variabel pengetat, misalkan x 4 dan x5 sehingga masala program linear di atas menjadi : Maksimumkan

: z = 10 x1 − 20 x 2 + 5 x3 + 0 x 4 + 0 x5

Dengan kendala

: x1 − x 2 + x3 + x 4 2 x1 − x 2 + x3

=8

+ x5 = 10

Soal ini sudah berbentuk kanonik dan berpola maksimum, dengan x1 , x 2 , x3 variabel asli dan x 4 , x5 adalah variabel pengetat.


13

Jika masalah program linear yang telah diubah ke dalam bentuk persamaan berpola maksimum maka masalah sudah dapat diselesaikan dengan metode simpleks. Bila masalah program linear berpola maksimum atau berpola minimum dan mempunyai penyelesaian basis yang tidak layak, karena memuat nilai negatif untuk variabel pengetat, maka masalah program linear tersebut belum bisa diselesaikan dengan metode simpleks. Masalah program linear yang masih memuat nilai negatif pada variabel pengetatnya memerlukan variabel semu, yaitu variabel yang ditambahkan kedalam persamaan kendala-kendala. Jika a adalah variabel semu yang disisipkan pada persamaan yang memuat variabel pengetat bernilai negatif maka masalah program linear tersebut sudah memuat suatu penyelesaian layak basis. Variabel semu ini bersifat sebagai katalisator (penghubung) dan mempunyai nilai nol supaya masalah semula mempunyai penyelesaian optimum. Bila ada variabel semu yang dipakai maka fungsi sasaran yang baru untuk pola maksimum berbentuk z = z − Ma , sedangkan fungsi sasaran yang baru untuk pola minimum berbentuk z = z + Ma dengan M bilangan positif yang cukup besar. Salah satu cara untuk menyelesaikan masalah program linear dengan menggunakan metode simpleks adalah melalui tabel simpleks. Langkah-langkah penyelesaian masalah program linear dengan menggunakan metode simpleks melalui tabel simpleks adalah sebagai berikut :


14

Langkah 1: Membentuk masalah program linear menjadi bentuk kanonik yaitu kendalanya harus berbentuk persamaan, dengan menambahkan variabel pengetat, variabel semu dan bi ≥ 0 sehingga memenuhi bentuk baku program linear.

Langkah 2 : Menyusun tabel awal seperti dalam tabel berikut ( Tabel 2.1 ) Tabel 2.1 Tabel Awal Simpleks

cj

c1

c2

K

cn

ci

xi \ x j

x1

x2

K

xn

bi

Ri

c1

x1

a11

a12

K

a1n

b1

R1

c2

x2

a 21

a 22

K

a2n

b2

R2

M

M

cm

xm

M a m1

O am2

K

M a mn

M bm

M Rm

zj

z1

z2

K

zn

z

zj −cj

z1 − c1

z 2 − c2

K

z n − cn

z

Keterangan :

xj

: variabel-variabel keputusan

aij

: koefisien teknis

bi

: suku tetap (tak negatif)

cj

: koefisien ongkos

xi

: variabel yang menjadi basis dalam tabel yang ditinjau


15

ci

: koefisien ongkos milik variabel basis xi

zj

:

z

:

m

∑c a i =1

i

ij

m

∑c b i =1

i i

zj −cj

: selisih z j

Ri

:

dengan c j

bi hanya untuk a a ik

i

≥ 0

Langkah 3 : Menguji keoptimuman, dengan memperhatikan nilai z j − c j . Untuk masalah dengan pola maksimum, tabel dikatakan optimum bila nilai z j − c j ≥ 0 untuk semua j. Sedangkan untuk masalah dengan pola minimum tabel dikatakan optimum bila nilai z j − c j ≤ 0 untuk semua j. Bila sudah optimum berarti sudah didapatkan penyelesaiannya. Jika belum optimum maka dilanjutkan ke Langkah 4.

Langkah 4 : Memperbaiki tabel. Dalam hal ini artinya memilih variabel baru yang masuk menjadi variabel basis. Untuk masalah yang berpola maksimum adalah dengan memilih kolom pivot, yaitu kolom dengan nilai z j − c j terkecil atau paling minimum. Untuk masalah yang berpola maksimum adalah dengan memilih nilai z j − c j

terbesar atau paling maksimum. Setelah ditemukan


16

kolom pivot maka selanjutnya dicari nilai rasio ( Ri ) untuk setiap baris, yaitu bi

dibagi unsur-unsur pada kolom pivot yang bernilai positif. Tidak

berbeda untuk pola maksimum dan pola minimum, dipilih nilai Ri ⎛b atau Ri = min ⎜⎜ i ⎝ aik

terkecil

⎞ ⎟⎟ . Baris dengan Ri terkecil kemudian menjadi baris ⎠

pivot. Setelah baris pivot dan kolom pivot terpilih, maka perpotongan antara baris pivot dan kolom pivot (a rs ) disebut sebagai elemen pivot dimana variabelnya akan menjadi variabel basis baru yang akan menggantikan variabel basis lama dan selanjutnya menuju ke Langkah 5.

Langkah 5 : Pada tabel selanjutnya elemen a rs diubah supaya bernilai satu dan semua elemen pada kolom yang bersesuaian diubah menjadi nol dengan melakukan operasi baris elementer. Variabel basis baru dan koefisien ongkos menyesuaikan dengan variabel basis baru tersebut. Selanjutnya kembali ke langkah 3.

D. Metode Simpleks Dual Masalah program linear memiliki dua macam metode simpleks, yaitu metode simpleks primal dan metode simpleks dual. Untuk setiap masalah program linear dapat diubah ke bentuk dual dimana kendala dan variabelnya adalah kebalikan dari primal, yakni koefisien variabel dalam masalah primal menjadi koefisien kendala dalam masalah dual. Jika dalam masalah primal mempunyai n


17

variabel dan m kendala maka masalah dualnya akan menjadi m variabel dan n kendala. Dapat dikatakan bahwa jumlah kendala dalam masalah primal sama dengan

jumlah

variabel

dalam

masalah

dual.

Bila

masalah

primal

memaksimumkan fungsi sasaran maka masalah dualnya pasti meminimumkan fungsi sasaran, dan begitu sebaliknya. Berikut akan diberikan contoh bentuk dual dari bentuk primal pada masalah program linear

Contoh 2.2 Masalah primal Minimumkan z = 6 x1 + 2 x 2 − x3 + 2 x 4 dengan kendala 4 x1 + 3 x 2 − 2 x3 + 2 x 4 ≥ 10 8 x1 + x 2 + 2 x3 + 4 x 4 ≥ 18 dan

x1 , x2 , x3 , x4 ≥ 0

Penyelesaian : Masalah dual Maksimumkan g = 10 y1 + 18 y 2 dengan kendala 4 y1 + 8 y 2 ≤ 6 3 y1 + y 2 ≤ 2 − 2 y1 + 2 y 2 ≤ −1 2 y1 + 4 y2 ≤ 2

dan

y1 , y 2 ≥ 0


18

Dalam metode simpleks dual penyelesaiannya dimulai dari penyelesaian basis yang tidak layak dan memenuhi ciri optimum sedangkan metode simpleks primal penyelesaiannya dimulai dari penyelesaian layak basis tetapi tidak harus optimum. Masalah program linear yang akan dicari dualnya harus berpola maksimum baku atau minimum baku yang memiliki bentuk baku sebagai berikut :

Pola maksimum baku : Maksimumkan z = cx memenuhi

Ax ≤ b ( semua berbentuk ≤ )

Pola minimum baku : Minimumkan z = cx memenuhi

Ax ≥ b ( semua berbentuk ≥ )

Untuk dapat menyusun suatu masalah primal kedalam bentuk dual maka harus dibuat kedalam bentuk kanonik sebagai berikut :

Pola maksimum (atau pola minimum): Maksimumkan (atau minimumkan) z = cx

(2.12)

Ax = b

(2.13)

yang memenuhi


19

Langkah-langkah metode simpleks dual adalah sebagai berikut : Langkah 1 :

Membentuk masalah program linear menjadi bentuk kanonik, yaitu kendalanya harus berbentuk persamaan, dengan menambahkan variabel pengetat, variabel semu dan bi ≥ 0 sehingga memenuhi bentuk baku program linear.

Langkah 2 :

Menyusun tabel awal dual simpleks yang disajikan sebagai berikut Tabel 2.2 Tabel Awal Simpleks Dual

ci

c1

c2

K

cn

cj

xi \ x j

x1

x2

K

xn

bi

c1

x1

a11

a12

K

a1n

b1

c2

x2

a 21

a 22

K

a2n

b2

M

M

cm

xm

M a m1

O am2

K

M a mn

M bm

zj

z1

z2

K

zn

z

zj −cj

z1 − c1

z 2 − c2

K

z n − cn

z

Ri

R1

R2

Keterangan : Ri =

zj −cj aij

, hanya untuk a ij < 0

K

Rn


20

Langkah 3 :

Memilih baris pivot, yakni dengan memilih baris i yang mempunyai nilai bi paling minimum dengan ( bi < 0 ) Jika ada nilai bi yang sama maka dipilih sembarang bi .

Langkah 4 :

Memilih kolom pivot, yakni mencari nilai rasio. Nilai rasio Ri diperoleh dengan membagi z j − c j dan nilai mutlak dari koefisien teknis yang ⎛ zj − cj berkoefisien negatif atau Ri = ⎜ ⎜ a ij ⎝

⎞ ⎟ dengan a ij < 0 . Untuk masalah ⎟ ⎠

yang berpola minimum dipilih nilai rasio yang terkecil atau ⎛ zj −cj = min ⎜ ⎜ a ij ⎝

rasio a ij

Ri

⎞ ⎟ , sedangkan masalah yang berpola maksimum dipilih nilai ⎟ ⎠

⎛ zj −cj yang terkecil atau Ri = min ⎜ ⎜ a ij ⎝

⎞ ⎟ . Jika koefisien teknis a ij ⎟ ⎠

bernilai positif atau nol maka masalah program linear tersebut tidak ada penyelesaian yang layak.

Langkah 5 :

Melakukan operasi baris elementer agar perpotongan antara baris pivot dan kolom pivot ( a rs ) yang disebut elemen pivot ini bernilai 1 dan yang lainnya bernilai 0.


21

Langkah 6 :

Menguji

keoptimuman. Jika semua bi ≥ 0 maka penyelesaian sudah

optimum, jadi iterasi harus dihentikan. Jika belum optimum maka harus dilanjutkan ke Langkah 2.

Perbedaan masalah program linear dengan menggunakan metode simpleks primal dan metode simpleks dual adalah sebagai berikut : 1. Jika masalah program linear dalam primal memiliki pola maksimum maka dalam dualnya masalah program linear tersebut akan memiliki pola minimum. 2. Jumlah variabel primal sama dengan jumlah kendala pada bentuk dualnya. 3. Dalam masalah primal, matriks koefisien teknis adalah (aij

)

tetapi dalam

masalah dualnya berbentuk tranpose dari matriks tersebut, yakni (aij

). t

4. bi dalam masalah program linear yang berbentuk primal disebut suku tetap tetapi dalam bentuk dualnya bi

menjadi koefisien ongkos.

5. c j dalam masalah program linear yang berbentuk primal disebut koefisien ongkos tetapi dalam bentuk dualnya c j menjadi suku tetap. 6. Dalam masalah dual, koefisien kendala ke-i berasal dari koefisien variabel ke-i masalah primal. 7. Dalam masalah dual, koefisien variabel ke-j berasal dari koefisien kendala ke-j masalah primal.


22

D. Program Linear Bilangan Bulat

Program linear bilangan bulat merupakan bagian dari program linear dengan tambahan kendala, dimana beberapa atau semua variabel keputusannya memiliki nilai-nilai bilangan bulat. Masalah-masalah program linear bilangan bulat menyangkut masalah-masalah yang harus diselesaikan dengan bentuk bilangan bulat. Program linear bilangan bulat ada dua model, yaitu program linear bilangan bulat murni atau biasa disebut program linear bilangan bulat (integer programming) dan program linear bilangan bulat campuran (mixed integer programming). Program linear bilangan bulat murni adalah suatu model program linear yang semua variabelnya adalah bilangan bulat, sedangkan program bilangan bulat campuran adalah suatu model program linear dengan beberapa variabelnya berupa bilangan bulat . Secara umum bentuk masalah program linear bilangan bulat murni dan campuran adalah sebagai berikut : 1. Bentuk baku masalah program linear bilangan bulat murni. Maksimumkan (atau minimumkan ) : Z = c1 x1 + c 2 x2 + K + c n x n

(2.14)

dengan kendala-kendala : a 11 x 1 + a 12 x 2 + K + a 1 n x n { ≤ , = , ≥ }b1

⎫ a 21 x 1 + a 22 x 2 + K + a 2 n x n { ≤ , = , ≥ }b 2 ⎪⎪ ⎬ M O O M ⎪ a m 1 x 1 + a m 2 x 2 + K + a mn x n { ≤ , = , ≥ }b m ⎪⎭

x j ≥ 0, j = 1,2, K , n dan x j bilangan bulat.

(2.15)

(2.16)


23

Rumus di atas dapat diringkas sebagai berikut : Maksimumkan (atau minimumkan) n

Z = ∑cj xj

(2.17)

j =1

dengan kendala : n

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

ij

j

(2.18)

i

x j ≥ 0,

x j bilangan bulat

i = 1,2,K , m ,

(2.19)

j = 1,2, K , n.

2. Bentuk baku masalah program linear bilangan bulat campuran. Maksimumkan (atau minimumkan) : n

p

j =1

k =1

Z = ∑ c j x j + ∑ d k yk

(2.20)

dengan kendala : n

p

j =1

k =1

∑ aij x j ∑ g ik y k ≤ atau ≥ bi xj ≥ 0 ,

y k ≥ 0 , x j bilangan bulat

i = 1,2,K , m , j = 1,2, K , n ,

(2.21)

k = 1,2, K , p.

Dalam tulisan ini hanya akan dibahas program linear bilangan bulat murni (integer programming). Masalah program linear bilangan bulat

dapat diselesaikan dengan

menggunakan beberapa metode, seperti metode bidang pemotong (cutting plane method), metode cabang dan batas (branch and bound method), dan metode enumerasi (enumerative methods). Secara umum, langkah pertama dalam menyelesaikan

masalah

program

linear

bilangan

bulat

adalah

dengan

mengabaikan kendala bilangan bulat. Jika sudah ditemukan penyelesaian yang


24

merupakan bilangan bulat maka penyelesaian program linear bilangan bulat sudah dicapai. Jika ternyata masih terdapat penyelesaian yang merupakan bilangan pecahan maka dilakukan suatu proses untuk menentukan penyelesaian bilangan bulat dari masalah tersebut. Dalam tulisan ini hanya akan dibahas menggunakan metode bidang pemotong untuk menyelesaikan masalah program linear bilangan bulat. Pada tahun 1958 Ralph Gomory mengembangkan metode bidang pemotong (cutting plane method) yang untuk pertama kalinya diaplikasikan pada masalah program linear bilangan bulat fraktional dual (dual fractional integer programming) adalah penyelesaian metode bidang pemotong yang menggunakan metode simpleks dual dan memungkinkan adanya bilangan pecahan dalam perhitungannya. Lalu pada tahun 1960 Ralph Gomory memperbaiki metode bidang pemotong tersebut, yakni menjadi masalah program linear bilangan bulat dual (dual all-integer integer programming) yang dalam perhitungannya harus berupa bilangan bulat. Metode bidang pemotong dalam kedua masalah program linear bilangan bulat ini menggunakan metode simpleks dual. Uraian untuk kedua masalah program linear bilangan bulat tersebut akan dijelaskan pada bab-bab berikutnya.


25

BAB III PROGRAM LINEAR BILANGAN BULAT FRAKSIONAL DUAL

A. Masalah Program Linear Bilangan Bulat Salah satu langkah yang dilakukan dalam penyelesaian masalah program linear bilangan bulat yang menggunakan metode bidang pemotong adalah dengan menambahkan kendala baru. Penambahan kendala baru dalam metode ini diperoleh dengan menyusun suatu persamaan yang memenuhi setiap penyelesaian layak dari masalah program linear bilangan bulat yang semula. Penambahan kendala tersebut memungkinkan diperolehnya penyelesaian yang optimum dari masalah program linear yang berupa bilangan bulat. Masalah program linear bilangan bulat yang diselesaikan dengan metode bidang pemotong dapat diilustrasikan dengan melihat Gambar 3.1. ABCDE adalah daerah layak yang diperoleh dari perpotongan kendala-kendala utama. Penyelesaian dari masalah program linear bilangan bulat dapat digambarkan sebagai titik-titik layak pada daerah layak tersebut dan titik D adalah penyelesaian optimum program linear yang pertama kali diperoleh. Sebuah kendala baru x ′ ≥ 0 ditambahkan sehingga titik D terbuang dari daerah layak dan jika dilakukan optimisasi kembali akan didapat penyelesaian optimum program linear yang baru, yakni titik F sehingga daerah layak yang baru adalah ABCGFE. Sebuah kendala baru kedua x ′′ ≥ 0 ditambahkan agar menghapus titik F dari daerah layak sehingga diperoleh daerah layak yang baru adalah ABCGHIE. Dalam


26

m menyelesaik kan kembali masalah prrogram lineaar bilangan bulat akan ditemukan p penyelesaian n optimum bilangan b bulaat, yakni titiik H.

G Gambar 3.1. Ilustrasi Penyyelesaian Masaalah Program Linear Bilanggan Bulat den ngan metode bidang b pemotoong

Perbedaan metodde simpleks dual yang suudah dibahass pada bab sebelumnya d dengan masaalah program m linear bilaangan bulat adalah a pada elemen pivo otnya yaitu b bernilai -1. Perhatikan kemb bali pada bbab sebelum mnya mengeenai masalahh program l linear bilang gan bulat. Secara umum m masalah prrogram lineaar bilangan bulat yang b berpola mak ksimum dappat dinyatakaan dalam beentuk kanonnik dan benttuk matriks s sebagai berik kut :


27

1. Bentuk kanonik masalah program linear bilangan bulat : Maksimumkan : z = c1 x1 + c 2 x 2 + K + c n x n

(3.1)

dengan kendala-kendala :

a 11 x1 + a 12 x 2 + K + a 1 n x n + x n +1 = b1 ⎫ a 21 x1 + a 22 x 2 + K + a 2 n x n + x n + 2 = b 2 ⎪⎪ ⎬ M O O M ⎪ a m 1 x1 + a m 2 x 2 + K + a mn x n + x n + m b m ⎪⎭

(3.2)

x j ≥ 0, j = 1,2, K , n

(3.3)

dan x j bilangan bulat.

2. Bentuk matriks masalah program linear bilangan bulat : Maksimumkan :

cx = z

(3.4)


Ax ≤ b

(3.5)

x ≥ 0 dan komponen-komponen x adalah bilangan bulat.

(3.6)

dengan A = (aij ) matriks kendala berukuran m x n.

Bentuk kanonik pada masalah program linear bilangan bulat disusun ke dalam bentuk seperti dibawah ini : Maksimumkan : z = (− c1 (− x1 ) ) + (− c 2 (− x 2 )) + K + (− c n (− x n ))

(3.7)


28


(− a11 (− x1 )) + (− a12 (− x 2 )) + K + (− a1n (− x n )) + x n +1 = b1 (− a 21 (− x1 )) + (− a 22 (− x 2 )) + K + (− a 2 n (− x n )) + x n+ 2 = b2 M O O M M M (− a m1 (− x1 )) + (− a m 2 (− x 2 )) + K + (− a mn (− x n )) + x n + m = bm

(3.8)

x j ≥ 0, j = 1,2, K , n dan x j bilangan bulat.

Bentuk kanonik di atas dapat diubah ke dalam bentuk seperti dibawah ini : Maksimumkan : x0 = a 00

+ a 01

(− x1 ) + a02

(− x 2 ) + K + a0n

(− x n )

(3.9)

⎫ ⎪ ⎪ ⎬ ⎪ −1(− xn )⎪⎭

(3.10)


x1 =

−1(− x1 )

x2 = M xn =

−1(− x2 ) O

xn+1 = an+1,0 + an+1,1 (− x1 ) + an+1,2 (− x2 ) + K+ an+1,n (− xn ) ⎫ ⎪ M O O O O M ⎬ xn+m = an+m,0 + an+m,1 (− x1 ) + an+m,2 (− x2 ) + K+ an+m,n (− xn )⎪⎭

(3.11)

dengan x j ≥ 0, j = 1,2, K , n + m dan x j bilangan bulat untuk j = 0,1, K , n + m . Persamaan (3.10) merupakan persamaan kendala untuk variabel keputusan (original variables), yakni variabel awal pada masalah program linear bilangan bulat. Persamaan (3.11) merupakan persamaan kendala untuk kendala utama (original constraints) yang ada pada masalah program linear bilangan


29

bulat. Pada bentuk di atas, n dan m masing-masing menunjukkan banyaknya variabel keputusan dan variabel slack yang muncul dari kendala utama. Dengan membandingkan persamaan (3.7), (3.8), (3.10) dan (3.11) dapat didefinisikan

x0 = z , a 00 = 0 , c j = − a 0 j ,

( j = 1, K , n ),

(i = 1,K, m ) , dan

aij = a n +i , j (i = 1, K , m ; j = 1 = 1, K , n ) .

bi = a n +i , 0

B. Penyelesaian Masalah Program Linear Bilangan Bulat Fraksional Dual Metode yang digunakan untuk mencari penyelesaian program linear bilangan bulat fraksional dual merupakan perluasan dari metode simpleks dual, yakni dengan menambah kendala baru pada masalah tersebut. Langkah-langkah masalah program linear bilangan bulat fraksional dual adalah sebagai berikut : 1. Mengubah bentuk baku menjadi bentuk kanonik seperti persamaan (3.2)

2. Menyusun tabel awal dari masalah program linear bilangan bulat. Pada persamaan (3.2) tabel awal tersebut disajikan sebagai berikut :


30

Tabel 3.1 Tabel Awal Program Linear Bilangan Bulat Fraktional Dual.

1

(− x1 ) K (− x j )

K

(− xn )

x0 =

a 00

a 01

K

a0 j

K

a0n

x1 =

0

−1

0

M xj =

M

K O L

M xn =

M

M 0 M 0

K O L

0 M 0 M

0 0

O K

M −1 M 0

x n +1 =

a n +1,0

a n +1,1 K

a n +1, j

M xn+ m =

M a n+ m,0

O M a n + m ,1 K

M a n+ m, j

O K

K O K

−1

a n +1,n M a n + m,n

Keterangan : x0 = z , a 00 = 0 , c j = − a 0 j , ( j = 1, K, n ), bi = a n +i , 0

( i = 1, K , m ), dan

aij = a n +i , j (i = 1, K , m ; j = 1 = 1, K , n ) , xi ≥ 0 ( i = 1, K , n + m) .

3. Masalah program linear bilangan bulat ini diselesaikan dahulu sebagai masalah program linear, yakni dengan menggunakan metode simpleks dual. Dengan langkah-langkah sebagai berikut :

Langkah 1: Memilih baris pivot, yakni dengan memilih baris v yang mempunyai nilai a v 0 paling minimum dengan a v 0 < 0 , v ≠ 0


31

Langkah 2 : Memilih kolom pivot, yakni kolom dengan nilai rasio yang

⎧⎪ a 0 j ⎫⎪ paling minimum dan nilai rasio = min ⎨ ⎬ ⎪⎩ a vj ⎪⎭ Langkah 3 : Mengganti variabel nonbasis pada kolom pivot dengan variabel xv , yakni variabel pada baris pivot.

Langkah 4 : Melakukan operasi kolom agar elemen-elemen baris xv pada

kolom pivot bernilai -1 dan yang lain bernilai 0. Langkah 5 : Bila nilai a v 0 masih ada yang bernilai negatif maka kembali ke

langkah 1. Jika sudah tidak ada lagi yang bernilai negatif maka langkah dihentikan dan penyelesaian masalah program linear bilangan bulat sudah optimum.

4. Menguji keoptimuman. Bila penyelesaian optimum yang diperoleh pada langkah sebelumnya adalah bilangan bulat maka masalah program linear bilangan bulat sudah selesai. Jika penyelesaian optimumnya belum berupa bilangan bulat maka langkah-langkah penyelesaian dilanjutkan lagi menggunakan metode bidang pemotong dengan menambahkan kendala bidang pemotong yang baru yang memuat variabel pengetat x n + m + k . Lalu kendala bidang pemotong yang baru ditambahkan pada tabel yang ditulis pada baris terakhir maka bentuk tabel akan menjadi :


32

Tabel 3.2. Tabel Dengan Bentuk Kendala Bidang Pemotong

1

(− x1 ) K (− x j )

K

(− xn )

x0 =

a 00

a 01

K

a0 j

K

a0n

x1 =

0

−1

0

M xj =

M

K O L

M xn =

M

M 0 M 0

K O L

0 M 0 M

0 0

O K

M −1 M 0

x n +1 =

a n +1,0

a n +1,1 K

a n +1, j

M xn+m =

M a n+ m,0

O M a n + m ,1 K

M a n+ m, j

xn+ m + k =

a n+m+ k ,0

O K K O K

−1

a n +1,n M a n + m,n

a n + m+ k ,1 K a n + m+ k , j K a n + m + k ,n

Dalam menentukan kendala bidang pemotong harus ditentukan dahulu baris sumber. Berikut ini akan dijelaskan bagaimana cara menentukan bentuk kendala bidang pemotong dan cara memilih baris sumber : a. Memilih baris sumber Cara memilih baris sumber adalah dengan memilih baris yang memuat variabel-variabel basis yang nilainya belum berupa bilangan bulat. Dalam hal ini variabel yang akan terpilih harus memberikan ketaksamaan yang kuat yaitu nilai dengan bilangan pecahan terbesar supaya dapat mempercepat pencapaian penyelesaian program linear bilangan bulat yang optimum.


33

Jika variabel basis xi pada persamaan ke-i bukan merupakan bilangan bulat maka variabel tersebut dapat dinyatakan sebagai : xi − ∑ aij (− x J ( j ) ) = ai 0 n

(3.12)

j =1

Keterangan : ai 0 bukan bernilai bilangan bulat aij dapat berbentuk bilangan bulat J adalah himpunan indeks variabel nonbasis J(j) adalah elemen j di dalam J x J ( j ) adalah variabel nonbasis j di dalam J

Persamaan (3.12) dapat ditulis sebagai berikut xi = ai 0 + ∑ aij (− x J ( j ) ) n

(3.13)

j =1

Setiap persamaan seperti di atas dinyatakan sebagai baris sumber (source row).

Misalkan : ai 0 = [ai 0 ] + f i

dan

[ ]

aij = aij + f ij

dengan :

(3.14)


34

[ai 0 ] adalah bilangan bulat terbesar yang kurang dari atau sama dengan

ai 0 ,

dan

[a ] adalah bilangan bulat terbesar yang kurang dari atau sama dengan ij

aij

maka 0 < f i < 1 dan 0 ≤ f ij < 1 Ada dua cara untuk memilih baris sumber yaitu : 1. Baris dengan nilai f i 0 yang paling maksimum. ⎧ ⎫ ⎪ f ⎪ ⎪ ⎪ 2. Baris dengan nilai ⎨ n i 0 ⎬ yang paling maksimum. ⎪ ∑ f ij ⎪ ⎪⎩ j =1 ⎪⎭

Jika nilai f i 0

⎧ ⎫ ⎪ f ⎪ ⎪ ⎪ atau ⎨ n i 0 ⎬ untuk setiap baris selalu sama maka dapat dipilih ⎪ ∑ f ij ⎪ ⎪⎩ j =1 ⎪⎭

sebarang baris untuk menjadi baris sumber. b.

Menentukan bentuk kendala bidang pemotong Dari uraian pemilihan baris sumber, dengan persamaan (3.13) akan menjadi :


35

[ ]

xi = [a i 0 ] + f i + ∑ ( a ij + f ij )(− x J ( j ) ) n

j =1

[ ]

= [a i 0 ] + f i + ∑ a ij (− x J ( j ) ) + ∑ f ij (− x J ( j ) ) n

n

j =1

j =1

atau

[ ]

f i + ∑ f ij (− x J ( j ) ) = xi − [ai 0 ] − ∑ aij (− x J ( j ) ) n

n

j =1

j =1

(3.15)

Supaya nilai xi dan (− x J ( j ) ) adalah bilangan bulat, maka ruas kanan dari persamaan (3.15) harus bernilai bilangan bulat yang mengakibatkan ruas kiri persamaan (3.15) haruslah bernilai bilangan bulat. Karena

(− x ( ) ) ≤ 0 untuk setiap nilai i dan J j

f ij ≥ 0 dan

j , maka

∑ f (− x ( ) ) ≤ 0 n

j =1

dengan demikian

J j

ij

f i + ∑ f ij (− x J ( j ) ) ≤ f i . n

j =1

Karena f i < 1 maka

f i + ∑ f ij (− x J ( j ) ) < 1 n

j =1

atau f i < 1 − ∑ f ij (− x J ( j ) ) n

j =1

(3.16)


36

Karena ruas kiri persamaan (3.15) harus bernilai bilangan bulat, maka berdasarkan persamaan (3.15), haruslah f i + ∑ f ij (− x J ( j ) ) ≤ 0 n

j =1

Jika bentuk di atas ditambahkan dengan variabel pengetat x n + m + k dengan x n + m + k ≥ 0 bilangan bulat, maka didapat : f i + ∑ f ij (− x J ( j ) ) + x n + m + k = 0 n

j =1

atau x n + m + k = −∑ f ij (− x J ( j ) ) − f i n

(3.17)

j =1

Persamaan (3.17) merupakan bagian pecahan (fractional cut) atau disebut juga pembatas sekunder. Jika pembatas sekunder ini sudah dimasukkan ke dalam

tabel yang berada pada baris terakhir dalam tabel dan dilakukan operasi kolom maka tabel terakhir didapat

(− x ( ) ) = 0 J j

sehingga x n + m + k = f i , yang berarti

tidak layak. Hal ini berarti pembatas sekunder yang baru tersebut tidak dipenuhi oleh penyelesaian yang diperoleh karena mengakibatkan nilai yang didapat belum berupa bilangan bulat sehingga untuk mengatasi ketidaklayakan ini dapat digunakan metode simpleks dual, yang pada dasarnya sama dengan memotong daerah layak ke arah penyelesaian optimum yang berupa bilangan bulat.


37

Dari penjelasan yang sudah dijabarkan di atas dan cara-cara memilih baris sumber serta menentukan pembatas sekunder, secara umum langkah pertama yang dilakukan dalam menyelesaikan masalah program linear bilangan bulat fraksional dual adalah mengubah masalah ke dalam bentuk kanonik dan menyusun tabel awal, menyelesaikan masalah program linear bilangan bulat dengan cara simpleks biasa dan dilanjutkan dengan langkah-langkah sebagai berikut : Langkah 1 :

Memilih baris sumber x v dengan dua cara di bawah ini : 1. Baris dengan nilai f v 0 yang paling maksimum. ⎧ ⎫ ⎪ f ⎪ ⎪ ⎪ 2. Baris dengan nilai ⎨ n v ⎬ yang paling maksimum. ⎪ ∑ f vj ⎪ ⎪⎩ j =1 ⎪⎭ Langkah 2 :

Menentukan bentuk kendala bidang pemotong yang baru, yakni pembatas sekunder seperti persamaan (3.17) x n + m + k = −∑ f vj (− x J ( j ) ) − f v n

j =1

Langkah 3 :

Tambahkan bentuk pembatas sekunder yang baru dalam tabel simpleks.


38

Langkah 4 :

Mencari baris pivot dengan melihat nilai koefisien a v 0 yang bernilai negatif dan dipilih yang paling minimum Langkah 5 :

Mencari kolom pivot dengan melihat niali R=

a0 j a vj

yang terkecil.

Langkah 6 :

Menggantikan variabel non basis pada kolom pivot dengan Variabel x v . Langkah 7 :

Melakukan operasi kolom agar elemen-elemen baris xv pada kolom pivot bernilai -1 dan yang lainnya bernilai 0. Langkah 8 :

Jika masih ada nilai xv

yang nilainya belum berupa bilangan bulat maka

dilanjutkan ke Langkah 1. Jika sudah tidak ada maka proses dihentikan dan diperoleh tabel optimum. Masalah program linear bilangan bulat fraksional dual tidak membedakan antara variabel keputusan dan variabel pengetat yakni bahwa semua variabel harus berupa bilangan bulat. Adanya koefisien yang tidak bulat dalam kendala tidak


39

memungkinkan untuk variabel pengetat berupa bilangan bulat. Dalam hal ini, masalah program linear bilangan bulat fraksional dual dapat menyatakan bahwa tidak terdapat penyelesaian layak, sekalipun masalah tersebut mempunyai penyelesaian layak yang bernilai bilangan bulat dalam bentuk bukan variabel pengetat. Berikut akan diberikan contoh penyelesaian masalah program linear bilangan bulat menggunakan metode bidang pemotong Contoh 3.1

Selesaikan masalah program linear bilangan bulat berikut: Maksimumkan:

z = −4 x1 − 5 x 2

Dengan kendala:

− x1 − 4 x 2 ≤ −5 − 3 x1 − 2 x 2 ≤ −7

x1 , x 2 ≥ 0

dan

Penyelesaian :

Masalah program linear di muka dapat dibuat ke bentuk kanonik sebagai berikut : Maksimumkan:

z = −4 x1 − 5 x 2

Dengan kendala:

− x1 − 4 x 2 + x3 − 3 x1 − 2 x 2

dan

x1 , x 2 , x3 , x 4 ≥ 0

= −5 + x 4 = −7


40

1. Menyusun tabel awal simpleks. Tabel 3.3. Tabel Awal Pada Contoh Masalah Program Linear Bilangan Bulat

1

(− x1 ) (− x 2 )

x0

0

4

5

x1

0 0 −5 −7

−1

0

0

−1

−1

−4

−3

−2

x2 x3 x4

2. Menyelesaikan dengan metode simpleks dual.

ITERASI 1 Langkah 1 : Memilih baris pivot Dari tabel awal diperoleh nilai a30 = −5 dan a 40 = −7 maka nilai min {a30 , a 40 } = min {− 5,−7} = −7 . Jadi baris empat sebagai baris pivot.

Langkah 2 : Memilih kolom pivot Dengan memilih nilai rasio terkecil yakni

⎧⎪ a a R4 = min ⎨ 01 , 02 ⎪⎩ a 41 a 42

⎫⎪ ⎬ ⎪⎭

⎧⎪ 4 5 ⎫⎪ 4 = min ⎨ , ⎬ = . Jadi kolom pertama akan terpilih sebagai kolom ⎪⎩ − 3 − 2 ⎪⎭ 3 pivot.

Langkah 3 : Menggantikan variabel x1 dengan variabel x 4 Langkah 4 : Melakukan operasi kolom, sehingga diperoleh tabel baru berikut


41

Tabel 3.4. Tabel Setelah Operasi kolom Pada Iterasi 1

x0

−

(− x4 ) (− x 2 )

28 3

4 3

7 3

1 3

2 3

7 3

x1 x2 x3

1

0 −

x4

8 3

−

0 −

1 3

-1 −

10 3

0

-1 0 8 Langkah 5 : Karena masih ada nilai a30 = − maka kembali ke Langkah 1 3

ITERASI 2 Langkah 1 : Memilih baris pivot 8⎫ 8 ⎧7 Dari tabel diatas diperoleh nilai min {a10 , a 30 } = min = ⎨ , − ⎬ = − 3⎭ 3 ⎩3 jadi baris ketiga sebagai bari pivot.

Langkah 2 : Memilih kolom pivot ⎧⎪ a a ⎫⎪ Dengan memilih nilai rasio terkecil yakni R4 = min ⎨ 01 , 02 ⎬ =min ⎪⎩ a31 a32 ⎪⎭ ⎧⎪ 4 3 7 3 ⎫⎪ 7 , maka kolom kedua akan terpilih sebagai kolom ⎨ ⎬= ⎪⎩ − 1 3 − 10 3 ⎭⎪ 3 pivot.

Langkah 3 : Menggantikan variabel x 2 dengan variabel x3


42

Langkah 4 : Melakukan operasi kolom, sehingga diperoleh tabel baru sebagai berikut Tabel 3.5. Tabel Setelah Operasi kolom Pada Iterasi 2

1

x0

−

(− x4 ) (− x3 )

112 10

11 10

7 10

4 10

2 10

18 10

−

x2

8 10

1 10

−

x3

0

0

-1

x1

3 10

0 -1 0 x4 Langkah 5 : Karena sudah tidak ada a v 0 < 0 maka proses dihentikan. dengan nilai x1 =

18 8 dan x 2 = 10 10

3. Menguji keoptimuman. Dari iterasi kedua telah dapatkan penyelesaian optimum dari masalah program linear, yaitu x1 =

18 8 dan x 2 = , tetapi penyelesaian tersebut belum 10 10

bulat maka penyelesaian dilanjutkan dengan menggunakan metode bidang pemotong.


43

ITERASI 1 Langkah 1 : Memilih baris sumber

Untuk x1 =

18 ⎡18 ⎤ 18 8 18 diperoleh f 10 = a10 − [a10 ] = −⎢ ⎥= −1 = 10 ⎣10 ⎦ 10 10 10

Untuk x 2 =

8 diperoleh f 10

Karena nilai f1 = f 2 =

20

= a 20 − [a 20 ] =

8 ⎡8⎤ 8 8 −⎢ ⎥= −0 = 10 ⎣10 ⎦ 10 10

8 maka tidak ada informasi untuk memilih baris 10

sumber, selanjutnya digunakan cara yang kedua. •

Untuk baris pertama dapat dinyatakan sebagai berikut : 2 (− x3 ) − 4 (− x4 ) ≥ 18 10 10 10

Sehingga

f12 = a12 − [a12 ] = −

•

f11 = a11 − [a11 ] =

diperoleh

2 ⎡2⎤ 2 2 −⎢ ⎥ = −0 = 10 ⎣10 ⎦ 10 10

dan

4 ⎡ 4⎤ 4 6 − ⎢− ⎥ = − − (− 1) = 10 ⎣ 10 ⎦ 10 10

Untuk baris kedua dapat dinyatakan sebagai berikut : −

Sehingga diperoleh f 22 = a 22 − [a 22 ] =

3 (− x3 ) + 1 (− x4 ) ≥ 8 10 10 10

f 21 = a21 − [a21] = −

3 ⎡ 3⎤ 3 7 − ⎢− ⎥ = − − (−1) = dan 10 ⎣ 10⎦ 10 10

1 ⎡1⎤ 1 1 −⎢ ⎥ = − (0) = 10 ⎣10 ⎦ 10 10


44

Dengan demikian, 8 ⎫ ⎧ 8 ⎪⎪ ⎪⎪ 10 ⎧ f10 f 20 ⎫ maks ⎨ , 10 ⎬ , ⎬ = maks ⎨ 2 ⎩ f 11 + f12 f 21 + f 22 ⎭ ⎪ + 6 7 + 1⎪ ⎪⎩ 10 10 10 10 ⎪⎭ ⎧8 8⎫ ⎪⎪ ⎪⎪ = maks ⎨ 10 , 10 ⎬ ⎪8 8⎪ ⎪⎩ 10 10 ⎪⎭ =maks {1,1} =1 Dengan cara yang kedua, nilai maksimum dari rasio tersebut sama, yaitu 1, maka dari kedua persamaan tersebut diambil salah satu. Disini yang akan dipilih sebagai baris sumber adalah persamaan untuk x1 .

Langkah 2 : Menentukan bentuk kendala baru, yakni pembatas sekunder

Perhatikan kembali pertidaksamaan x1 :

Dari Langkah 1 diperoleh f11 =

2 (− x3 ) − 4 (− x4 ) ≥ 18 10 10 10

2 6 8 , f12 = dan f 10 = 10 10 10

Maka persamaan pembatas sekunder yang baru adalah

x5 = −

2 (− x3 ) − 6 (− x 4 ) − 8 ≥ 0 10 10 10


45

Langkah 3 : Tambahkan bentuk pembatas sekunder yang baru dalam tabel simpleks. Tabel 3.6. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 1

(− x 4 ) (− x3 )

1

x0

−

112 10

11 10

7 10

4 10

2 10

18 10

−

x2

8 10

1 10

−

x3

0

0

-1

x4

0

-1

0

8 10

−

x1

x5

−

6 10

3 10

−

2 10

Langkah 4 :Mencari baris pivot Dari tabel koefisien a50 = −

8 pada baris kelima, maka baris kelima 10

menjadi baris pivot

Langkah 5 : Mencari kolom pivot Dari tabel pada kolom pertama dilihat nilai R terkecil, yakni 11 a 01 10 = 11 = a51 6 −6 10


46

Langkah 6 : Menggantikan variabel nonbasis x 4 pada kolom pivot dengan variabel x5 .

Langkah 7 : Melakukan operasi kolom Tabel 3.7. Tabel Setelah Dilakukan Operasi kolom Pada Iterasi 1

1

x0

−

(− x5 ) (− x3 )

76 6

11 6

2 6

4 6

2 6

14 6

−

x2

4 6

1 6

x3

0

0

x4

8 6

−

0

-1

x1

x5

10 6

−

2 6 -1 2 6 0

Langkah 8 :

Karena nilai x1 =

14 4 dan x 2 = yang nilainya belum berupa bilangan 6 6

bulat maka di lanjutkan ke Langkah 1.


Untuk x1 =

14 2 14 ⎡14 ⎤ 14 −⎢ ⎥= diperoleh f 10 = −2= 6 6 6 ⎣6⎦ 6


47

Untuk x 2 =

4 diperoleh f 6

20

=

4 4 ⎡4⎤ 4 − ⎢ ⎥ = −0 = 6 6 ⎣6⎦ 6

⎧2 4⎫ 4 f = maks { f10 , f 20 } = maks ⎨ , ⎬ = ⎩6 6⎭ 6 Jadi baris kedua pada persamaan x 2 terpilih sebagai baris sumber

Langkah 2 : Menentukan bentuk kendala baru, yakni pembatas sekunder Pada tabel untuk baris kedua dapat dinyatakan sebagai berikut −

Sehingga

f

22

diperoleh

= a 22 − [a 22 ] = −

2 (− x3 ) + 1 (− x5 ) ≥ 4 6 6 6

f

21

= a 21 − [a 22 ] =

1 1 ⎡1⎤ 1 − ⎢ ⎥ = −0 = 6 6 ⎣6⎦ 6

dan

4 2 ⎡ 2⎤ 2 − ⎢− ⎥ = − − (− 1) = 6 6 ⎣ 6⎦ 6

Dari langkah sebelumnya didapat f

20

=

4 6

Maka persamaan pembatas sekunder yang baru adalah

x6 = −

4 (− x3 ) − 1 (− x5 ) − 4 ≥ 0 6 6 6

Langkah 3 : Tambahkan bentuk pembatas sekunder yang baru dalam tabel simpleks.


48

Tabel 3.8. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 2

1

x0

(− x5 ) (− x3 )

76 6

−

11 6

2 6

4 6

2 6

14 6

−

x2

4 6

1 6

x3

0

0

x4

8 6

−

0

-1

x1

x5 x6

−

4 6

−

−

-1

10 6

1 6

2 6

2 6 0 −

4 6

Langkah 4 :Mencari baris pivot

Dari tabel, koefisien a 60 = −

4 pada baris keenam, maka baris keenam 6

dipilih sebagai baris pivot.

Langkah 5 : Mencari kolom pivot Dari tabel, pada kolom kedua

dilihat nilai R terkecil, yakni

c02 26 2 = = a62 −4 6 4 Langkah 6 : Menggantikan variabel non basis pada kolom pivot dengan variabel x6 .


49


1

(− x5 ) (− x6 )

x0

− 13

x1

2

x2

1

1 4

−

2 4

x3

1

1 4

−

6 4

7 4

2 4

x4

7 4

2 4

3 4

2 4

−

1

−

x5

0

-1

0

x6

0

0

-1

Langkah 8 : karena nilai a v 0 sudah berupa bilangan bulat maka tabel sudah optimum dengan nilai ( x1 , x 2 ) = (2,1) dengn nilai optimum= -13

Pada masalah program linear bilangan bulat dalam bentuk dualnya dapat diurakan bahwa kendala awal dengan variabel awal x1 dan x 2 adalah − x1 − 4 x 2 ≤ −5

atau x3 = −5 + x1 + 4 x 2

− 3 x1 − 2 x 2 ≤ −7

atau x 4 = −7 + 3 x1 + 2 x 2


50

Kendala bidang pemotong yang didapat pada perhitungan diatas adalah

(i)

x5 = −

8 2 6 − (− x3 ) − (− x 4 ) 10 10 10

x5 = −

8 2 6 + x3 + x 4 10 10 10

x5 = −

6 8 2 + (− 5 + x1 + 4 x 2 ) + (− 7 + 3 x1 + 2 x 2 ) 10 10 10

x5 = −

8 10 2 8 42 18 12 − + x1 + x 2 − + x1 + x 2 10 10 10 10 10 10 10

x5 = −6 + 2 x1 + 2 x 2 4 4 1 (ii) x6 = − − (− x3 ) − (− x5 ) 6 6 6 4 4 1 x 6 = − + x3 + x5 6 6 6 1 4 4 x6 = − + (− 5 + x1 + 4 x 2 ) + (− 6 + 2 x1 + 2 x 2 ) 6 6 6 4 20 4 16 6 2 2 x6 = − − + x1 + x 2 − + x1 + x 2 6 6 6 6 6 6 6

x6 = −5 + x1 + 3 x 2


51

Dari kendala awal dan kendala tambahan dapat digambarkan dengan grafik. x2

4• 3

•

2• •

1• •

1

•

2

x

•

4

3

x5

•

4

x1

•

5

x6 x 3

Gambar 3.2. Penyelesaian Masalah Program Linear Bilangan Bulat Fraksional Dual

Sifat tambahan tentang pembatas sekunder, yakni tabel yang sudah optimum bila diselesaikan kembali dengan metode bidang pemotong yang menggunakan metode simpleks dual akan diperoleh tabel optimum yang bernilai bilangan bulat, yakni semua nilai-nilai di dalam tabel akan berupa bilangan bulat tanpa mengubah nilai optimum dari penyelesaian optimum tersebut. Akan diperlihatkan bahwa suatu pembatas sekunder sama dengan pertaksamaan dalam variabel nonbasis. Diasumsikan tabel awal berpa bilangan bulat.

Teorema 3.1 Setiap pembatas sekunder pada persamaan (3.17) akan menjadi pertaksamaan yang semua variabelnya bernilai bilangan bulat bila dinyatakan dalam suku-suku yang memuat variabel nonbasis pada iterasi sebelumnya.


52

Bukti : Misalkan baris untuk persamaan pertama menjadi

xv = av 0 + ∑ avj (− x J ( j ) ) n

j =1

maka pembatas sekunder yang dihasilkan adalah sebagai berikut x n + m +1 = − f v 0 − ∑ f vj (− x J ( j ) ) n

j =1

[ ]

[ ]

dengan f vj = a vj − a vj atau − f vj = a vj − a vj , j = 0,1, K, n maka

x n + m +1 = − f v 0 − ∑ f vj (− x J ( j ) ) n

j =1

[ ]

= ([a v 0 ] − a v 0 ) − ∑ ( a vj − a vj )(− x J ( j ) ) n

j =1

n n ⎧ ⎫ ⎧ ⎫ = ⎨[av 0 ] + ∑ avj (− x J ( j ) )⎬ − ⎨av 0 + ∑ avj (− x J ( j ) )⎬ j =1 j =1 ⎩ ⎭ ⎩ ⎭

[ ]

Sekarang setiap variabel nonbasis x J ( j ) adalah suatu variabel nonbasis ataupun variabel basis pada masalah awal. Pada kasus sebelumnya diketahui x J ( j ) = x g untuk

g = 1,2, K, n

suatu

dan

pada

kasus

selanjutnya

persamaan

x J ( j ) = a n +i , 0 + ∑ a n +i , j (− x j ) untuk suatu i = 1,2,K, m . Meskipun begitu koefisien n

j =1

pada persamaan terakhir semuanya berupa bilangan bulat karena data awal dari masalah program linear bilangan bulat berupa bilangan bulat maka koefisiennya juga akan berupa bilangan bulat. Oleh karena itu x J ( j ) dapat ditulis sebagai suatu kombinasi linear dari x1 , K , x n . Jadi suku pada ruas kanan dalam tanda kurung pertama adalah suatu bilangan bulat bila dituliskan dalam suku-suku x1 , K , x n .


53

Suku pada ruas kanan dalam tanda kurung kedua sama dengan xv . Variabel ini juga sebuah variabel nonbasis maupun sebagai kombinasi linear dari variabel nonbasis x1 , K , x n . Oleh karena itu x n + m +1 = − f v 0 − ∑ f vj (− x J ( j ) ) ≥ 0 menjadi pertaksamaan n

j =1

yang berupa bilangan bulat bila dinyatakan dalam suku-suku dari variabel nonbasis.■

Akan diperlihatkan dari contoh (3.1) bahwa masalah program linear bilangan bulat yang sudah diperoleh penyelesaian optimum dapat dikerjakan kembali dengan metode bidang pemotong yang menggunakan metode simpleks dual sehingga diperoleh tabel optimum yang semua nilai-nilai dalam tabel berupa bilangan bulat tanpa mengubah nilai optimum dari penyelesaian optimum dari tabel (3.9). Dari iterasi kedua tabel (3.9) sudah ditemukan penyelesaian optimum. Maka contoh soal (3.1) diselesaikan kembali dengan uraian sebagai berikut :

ITERASI 1 Langkah 1 : Memilih baris sumber Baris sumber yang akan diambil adalah baris ke-nol karena nilai a 00 = −13 dan memiliki nilai f 00 = 0

Langkah 2 : Menentukan bentuk kendala baru, yakni pembatas sekunder Pada tabel sebelumnya, untuk baris ke-nol dapat dinyatakan sebagai 7 (− x5 ) + 2 (− x6 ) ≥ −13 4 4


54

3 2 7 ⎡7⎤ 7 2 ⎡2⎤ 2 − ⎢ ⎥ = − (1) = , f 02 = − ⎢ ⎥ = − 0 = 4 4 4 ⎣4⎦ 4 4 ⎣4⎦ 4 = 0 . Maka persamaan pembatas sekunder yang baru adalah

Sehingga diperoleh f 01 = dan f

00

x7 = 0 −

7 (− x5 ) − 2 (− x6 ) ≥ 0 4 4

Langkah 3 : Tambahkan bentuk pembatas sekunder yang baru dalam tabel simpleks. Tabel 3.10. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 3

1

(− x5 ) (− x6 )

x0

− 13

x1

2

x2

1

1 4

−

2 4

x3

1

1 4

−

6 4

7 4

2 4

x4

7 4

2 4

3 4

2 4

−

1

−

x5

0

-1

0

x6

0

0

-1

x7

0

3 4

−


−

2 4


55

Dari tabel koefisien a 70 = 0 pada baris ketujuh, maka baris ketujuh dipilih sebagai baris pivot.

Langkah 5 : Mencari kolom pivot Dari tabel, pada kolom kedua dilihat nilai R terkecil yakni

c02 24 = =1 a72 −2 4

Langkah 6 : Menggantikan variabel non basis pada kolom pivot dengan variabel x7 .


1

x0

− 13

x1

2

x2 x3

x4

(− x5 ) (− x7 ) 1

1

3 2

1

1

1

-1

1

5 2

−3

5 2

1

1

x5

0

x6 x7

−

−

-1

0

0

3 2

-2

0

0

-1


56

Langkah 8 :

karena belum semua nilai berupa bilangan bulat maka kembali ke Langkah 1


Sekarang yang diambil untuk baris sumber adalah baris pertama yakni a10 = 2 dan memiliki nilai f10 = 0 Langkah 2 : Menentukan bentuk kendala baru, yakni pembatas sekunder

Pada tabel sebelumnya, untuk baris pertama dapat dinyatakan sebagai −

3 (− x5 ) + 1(− x7 ) ≥ 2 2

sehingga diperoleh f 01 = −

3 ⎡ 3⎤ 3 1 − ⎢− ⎥ = − − (− 2 ) = dan f 02 = 0 dengan 2 ⎣ 2⎦ 2 2

f 00 = 0 Maka persamaan pembatas sekunder yang baru adalah

x8 = 0 −

1 (− x5 ) + 0(− x6 ) ≥ 0 2

Langkah 3 : Tambahkan bentuk pembatas sekunder yang baru dalam tabel

simpleks.


57

Tabel 3.12. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 4

1

x0

− 13

x1

2

x2 x3

x4

(− x5 ) (− x7 ) 1

1

3 2

1

1

1

-1

1

5 2

−3

5 2

1

1

x5

0

x6

−

−

-1

0

0

3 2

-2

x7

0

0

-1

x8

0

−

1 2

0


Dari tabel, koefisien a80 = 0 pada baris kedelapan, maka baris kedelapan dipilih sebagai baris pivot. Langkah 5 : Mencari kolom pivot

Dari tabel, pada kolom kesatu dilihat nilai R terkecil yakni

c01 1 = =2 a81 −1 2


58

Langkah 6 : Variabel x8 akan menggantikan variabel non basis pada kolom

pivot. Langkah 7 : Melakukan operasi kolom Tabel 3.13. Hasil setelah dilakukan operasi kolom pada iterasi 4

1

x0

− 13

x1

(− x8 ) (− x7 ) 2

1

2

-3

1

x2

1

2

-1

x3

1

5

−3

x4

1

-5

1

x5

0

-2

0

x6

0

3

-2

x7

0

0

-1

x8

0

-1

0

Langkah 8 : karena nilai-nilainya dalam tabel sudah berupa bilangan bulat, maka

telah diperoleh penyelesaian optimum masalah program linear bilangan bulat fraksional dual dengan nilai

,

= (2,1) dengan nilai optimum = -13


59

Program linear bilangan bulat fraksional dual memiliki banyak kelemahan. Dalam menyelesaikan masalah program linear bilangan bulat, perhitungan dilakukan dalam dua tahap yang sangat rumit, yaitu menggunakan metode simpleks dual. Setelah ditemukan penyelesaian optimum harus dilihat dahulu apakah sudah memenuhi penyelesaian optimum bilangan bulat atau belum. Jika belum berupa bilangan bulat maka tabel harus diselesaikan kembali menggunakan metode bidang pemotong sampai ditemukan penyelesaian optimum bilangan bulat, yakni nilai variabelnya berupa bilangan bulat. Lalu pada tahun 1960 Ralph Gomory memperbaiki metode bidang pemotong tersebut, yakni menjadi masalah program linear bilangan bulat dual.


60

BAB IV PROGRAM LINEAR BILANGAN BULAT DUAL

A. Masalah Program linear Bilangan Bulat Dual Dengan Metode Bidang Pemotong

Untuk mencari penyelesaian pada masalah program linear bilangan bulat akan digunakan metode bidang pemotong, yakni dengan menambahkan kendala bidang pemotong. Berikut akan diuraikan bagaimana cara menentukan bentuk kendala bidang pemotong. Jika variabel basis xi pada sembarang persamaan ke-i yang merupakan bilangan bulat maka variabel tersebut dapat dinyatakan sebagai :

xi = ai 0 + ai1 (− x1 ) + ai 2 (− x 2 ) + K + ain (− x n ) atau

xi = ai 0 + ∑ aij (− x J ( j ) ) n

(4.1)

j =1

dengan J ( j ) adalah elemen ke j di dalam J =(1,2,…,n), dan ai 0 < 0 maka baris tersebut disebut sebagai baris sumber. Jika tidak ada maka tabel simpleks sudah optimum. Misalkan a sembarang bilangan dan λ adalah sebuah bilangan positif. Bentuk

f =

⎡a⎤ −⎢ ⎥ λ ⎣λ ⎦

a

(4.2)


61

a ⎡a⎤ dengan ⎢ ⎥ adalah bilangan bulat terbesar yang kurang dari atau sama dengan λ ⎣λ ⎦ maka 0 ≤ f < 1 . Didefinisikan r = λf maka diperoleh

r

λ

=

⎡a⎤ ⎡a⎤ − ⎢ ⎥ atau a = ⎢ ⎥ λ + r . λ ⎣λ ⎦ ⎣λ ⎦

a

(4.3)

Karena 0 ≤ f < 1 dan λ > 0 , maka 0 ≤ λf < λ atau 0 ≤ r < λ . Dari persamaan (4.3) maka koefisien pada persamaan (4.1) dapat ditulis sebagai ⎡ aij ⎤ aij = ⎢ ⎥ λ + rij ⎣λ⎦

( j = 0,1,...n )

⎡1⎤ 1 = ⎢ ⎥λ + r ⎣λ ⎦

dan

(4.4)

(4.5)

dengan λ > 0, 0 ≤ rij < λ dan 0 ≤ r < λ . Substitusikan persamaan (4.4) dan (4.5) ke dalam persamaan (4.1) sehingga diperoleh n ⎛ a ⎞ ⎡ ⎤ ⎡ ai 0 ⎤ ⎡1⎤ ⎜ ⎢ ij ⎥ λ + rij ⎟(− x J ( j ) ) + = λ x rx λ + r + ∑ i0 ⎢λ ⎥ ⎢⎣ λ ⎥⎦ ⎜ ⎟ ⎣ ⎦ j =1 ⎝ ⎣ λ ⎦ ⎠ n ⎛ a ⎞ ⎡ ij ⎤ ⎡a ⎤ = ⎢ i 0 ⎥ λ + ri 0 + ∑ ⎜⎜ ⎢ ⎥ λ (− x J ( j ) ) + rij (− x J ( j ) )⎟⎟ ⎣λ ⎦ j =1 ⎝ ⎣ λ ⎦ ⎠ n n ⎡ aij ⎤ ⎡a ⎤ = ⎢ i 0 ⎥ λ + ri 0 + ∑ ⎢ ⎥ λ (− x J ( j ) ) + ∑ rij (− x J ( j ) ) ⎣λ ⎦ j =1 ⎣ λ ⎦ j =1

atau n ⎡ aij ⎤ ⎡ ai 0 ⎤ ⎡1⎤ r x rx r λ + = + + ∑ ∑ ij J ( j ) i0 ⎢ ⎥ λ (− x J ( j ) ) + ⎢ ⎥ λ (− x) ⎢λ ⎥ ⎣λ ⎦ ⎣ ⎦ j =1 j =1 ⎣ λ ⎦ n

n

∑r x j =1

ij

J ( j)

⎧⎪⎡ a ⎤ n ⎡ aij ⎤ ⎫⎪ ⎡1⎤ + rx = ri 0 + λ ⎨⎢ i 0 ⎥ + ∑ ⎢ ⎥ (− x J ( j ) ) + ⎢ ⎥ (− x)⎬ ⎪⎩⎣ λ ⎦ j =1 ⎣ λ ⎦ ⎪⎭ ⎣λ ⎦

(4.6)


62

Persamaan (4.6) dapat ditulis n

∑r x j =1

ij

J ( j)

+ r x = ri 0 + λ x ′

(4.7)

dengan ⎡a ⎤ n ⎡a j ⎤ ⎡1⎤ x' = ⎢ 0 ⎥ + ∑ ⎢ ⎥ (− x J ( j ) ) + ⎢ ⎥ (− x ) ⎣λ ⎦ ⎣ λ ⎦ j =1 ⎣ λ ⎦

(4.8)

Teorema 4.1 :

Untuk sembarang penyelesaian yang berupa bilangan bulat yang memenuhi persamaan (4.1) dan persamaan (4.7), maka x' haruslah sebuah bilangan bulat tak negatif.

Bukti : x' bilangan bulat karena semua koefisien dalam (4.8) adalah bilangan bulat.

Selanjutnya akan ditunjukan x' adalah tak negatif. Untuk sembarang penyelesaian layak maka ruas kiri persamaan (4.7) nilainya tak negatif. Andaikan x ' adalah bilangan bulat yang negatif. Karena ri 0 < λ maka ruas kanan pesamaan (4.7) yakni ri 0 + λ x ′ adalah negatif. Hal ini kontradiksi dengan pernyataan bahwa penyelesaian layak pada ruas kiri persamaan (4.7) nilainya tak negatif dengan demikian x' adalah bilangan bulat yang tak negatif


63

Jika λ > 1, maka

⎡1⎤ < 1 sehingga ⎢ ⎥ = 0 . Bila nilai tersebut dimasukan pada λ ⎣λ ⎦ 1

persamaan (4.8) akan didapat ⎡ a ⎤ n ⎡ aij ⎤ x' = ⎢ i 0 ⎥ + ∑ ⎢ ⎥ (− x J ( j ) ) ≥ 0 ⎣ λ ⎦ j =1 ⎣ λ ⎦ ⎡a ⎤ Karena ai 0 < 0 berarti ⎢ i 0 ⎥ < 0 . Tambahkan persamaan (4.9) ⎣λ ⎦

(4.9)

pada tabel

simpleks dan dapat dianggap sebagai baris sumber. Untuk λ yang cukup besar maka elemen pivot pada persamaan (4.9) yakni ai 0 ⎡ ai 0 ⎤ ⎢ λ ⎥ = −1 dengan − 1 ≤ λ < 0 . ⎣ ⎦

Metode yang digunakan dalam masalah program linear bilangan bulat dual hampir sama dengan yang digunakan dalam masalah program linear bilangan bulat fraksional dual. Prinsipnya adalah menggunakan metode simpleks dual lexicographic, yakni sebuah metode simpleks dual dengan menggunakan aturan lexicographic. Aturan lexicographic merupakan salah satu prosedur penyelesaian dalam masalah degenerasi, yakni iterasi-iterasinya tidak berulang dan banyaknya basis layak adalah berhingga, serta tidak ada basis yang berulang. Dengan demikian banyaknya iterasi pada metode simpleks adalah berhingga. Dalam aturan ini dibentuk kolom-kolom tabel yang positif secara lexicographic.


64

Definisi 4.1 Positif secara lexicographic

Sebuah vektor v adalah positif secara lexicographic jika v ≠ 0 dan elemen tak nol pertama dari v adalah positif dan sebaliknya disebut minimum secara lexicographic.

Berikut ini akan diberikan contoh positif secara lexicographic Contoh 4.1

Misalkan tedapat vektor

v 1 = (0 0 4 10) v 2 = (1 − 3 0 − 5)

v 3 = (0 3 0 1) v 4 = (0 − 1 10 20)

Maka v 1 , v 2 dan v 3 adalah positif secara lexicographic, sedangkan v 4 bukan positif secara lexicographic melainkan minimum secara lexicographic.

Langkah-langkah metode bidang pemotong pada masalah program linear bilangan bulat dual dengan menggunakan metode simpleks dual adalah sebagai berikut : 1. Mengubah bentuk baku ke dalam bentuk kanonik pada masalah program linear bilangan bulat. 2. Dimulai dengan menyusun tabel awal simpleks untuk bilangan bulat yang berisi penyelesaian layak dual lexicographic. Tabel awal tersebut disajikan sebagai berikut :


65

Tabel 4.1. Tabel Awal Program Linear Bilangan Bulat

Kolom →

α0

Variabel

1

α1

K

αn

(− x1 )

K

(− xn )

↓

x0 = x1 = M xn = x n +1 = M x n +m =

a 00 0 M 0 a n +1, 0

a 01 K −1 K M O 0 K a n +1,1 K

M M a n + m ,0 a n + m ,1

O K

a0 n 0 M −1 a n +1,n M a n + m ,n

Keterangan : ⎛ a0 j ⎞ ⎜ ⎟ α j : komponen n + m + 1 pertama dalam kolom ke – j, yakni α j = ⎜ M ⎟. ⎜ ⎟ ⎝ a n+ m, j ⎠

3. Memilih baris sumber yang tidak layak v, yakni yang memenuhi a v 0 < 0 , v ≠ 0. Jika tidak ada

maka penyelesaian masalah program linear

bilangan bulat sudah optimum, dengan demikian langkah dihentikan. Jika ada baris yang tidak layak v maka dilanjutkan ke Langkah 3. 4. Tandai kolom pivot α p ( p = 1,K, n ) yang terkecil secara lexicographic diantara kolom-kolom yang mempunyai a vj < 0 dan elemen tak nol yang pertama adalah negatif. Jika tidak ada, yakni a vj ≥ 0 ,untuk j = 1,K, n , maka tidak ada penyelesaian layaknya. Jika ada maka dilanjutkan ke langkah berikutnya.


66

Sebelum menentukan bentuk kendala bidang pemotong harus ditemukan sebuah λ yang diperoleh dari baris sumber dan kolom pivot. Jika koefisien baris sumber ditunjukkan dengan b j

( j = 0,1,K, n ) , maka

kolom pivot α p dalam metode simpleks dual lexicographic memenuhi αp − bp

L

αj

p−b

(4.10) j

setiap j (j ≠ 0) dengan b j < 0 untuk setiap iterasi pada masalah program linear bilangan bulat. Dengan b p adalah koefisien kolom α p pada baris v, yakni ⎡ aij ⎤ b p = −1 dan koefisien x pada baris v kolom ke-j adalah ⎢ ⎥ ⎣λ⎦

maka

⎡ aij ⎤ b j = ⎢ ⎥ . Dengan demikian dari persamaan (4.10), kolom pivot haruslah ⎣λ ⎦

memenuhi L

αp p

αj

(4.11)

⎡ aij ⎤ −⎢ ⎥ ⎣λ⎦

⎡ a ij ⎤ ⎡ aij ⎤ untuk setiap j (j ≠ 0) dengan ⎢ ⎥ < 0 . Karena − ⎢ ⎥ adalah bilangan bulat ⎣λ⎦ ⎣λ⎦

positif maka didapat L

αp p

αj ⎡ aij ⎤ −⎢ ⎥ ⎣λ⎦

L

pα

j

(4.12)


67

⎡ aij ⎤ Karena λ>0, maka ⎢ ⎥ < 0 jika hanya jika a ij < 0 sehingga kolom pivot ⎣λ⎦

adalah kolom terkecil secara lexicographic yang memuat sebuah elemen negatif dalam baris sumber. Misalkan u p = 1 dan u j ( j ≠ p ) adalah bilangan bulat terbesar sehingga L

αp p

αj uj

Karena u j adalah bilangan bulat terbesar, persamaan

(4.13)

(4.13) menunjukkan

bahwa ⎡ aij ⎤ − ⎢ ⎥ ≤ uj ⎣λ⎦

(4.14)

Nilai positif terkecil λ yang memenuhi (4.14) adalah

λij =

− aij uj

(4.15)

Maka untuk menjamin persamaan (4.11), atau dengan kata lain untuk mempertahankan kolom positif secara lexicographic α j ( j = 1,K, n ) , maka ⎧⎪ − aij ⎫⎪ haruslah memiliki λ ≥ maks ⎨λij = ⎬. u j ⎪⎭ ⎪⎩

5. Tentukan kendala bidang pemotong yang merupakan pertidaksamaan bilangan bulat dari baris v, yakni


68

⎡ a ⎤ n ⎡ aij ⎤ xv = ⎢ i 0 ⎥ + ∑ ⎢ ⎥ (− x J ( j ) ) ≥ 0 ⎣ λ ⎦ j =1 ⎣ λ ⎦

Tambahkan kendala bidang pemotong dalam tabel, yakni pada baris paling bawah. Kemudian dilakukan operasi kolom agar elemen-elemen pada baris xv bernilai -1 untuk elemen pada kolom pivot dan yang lainnya bernilai 0. Kemudian lanjutkan ke Langkah 3.

B. Penyelesaian Masalah Program Linear Bilangan Bulat Dual

Dari langkah-langkah yang sudah dijabarkan di atas, yaitu cara memilih kolom pivot, aturan memilih λ dan bentuk kendala bidang pemotong, secara umum langkah pertama yang dilakukan dalam menyelesaian masalah program linear bilang bulat adalah mengubah bentuk baku menjadi bentuk kanonik dan menyusun tabel awal kemudian dilanjutkan dengan langkah-langkah sebagai berikut : Langkah 1 :

Memilih baris utama atau baris sumber v, yakni baris dengan a v 0 < 0 , v ≠ 0 dipilih yang paling minimum. Langkah 2 :

Memilih kolom pivot α p , yakni kolom dengan koefisien a vj ( j ≥ 1) dengan elemen tak nol pertama dari baris v adalah negatif dan dipilih yang paling minimum.


69

Langkah 3 :

Menentukan nilai λ dengan langkah-langkah sebagai berikut : i. Untuk setiap a vj < 0 ( j ≠ 0) dan misalkan u p = 1 untuk α p kolom pivot yang dipilih dalam langkah di atas, tentukan u j ( j ≠ p ) , yakni bilangan

⎛ 1 bulat terbesar yang memenuhi ⎜ ⎜u ⎝ j

L ⎞ L ⎟α j f α p dengan u j ≥ 1 dan α p f 0 . ⎟ ⎠

ii. Untuk setiap a vj < 0 ( j ≥ 1) , hitung λij dengan λij =

− avj uj

.

⎧⎪ − aij ⎫⎪ iii. Pilih λ= maks ⎨λij = ⎬ u j ⎪⎭ ⎪⎩ Langkah 4 : Menentukan bentuk kendala bidang pemotong yakni ⎡ a ⎤ n ⎡ a vj ⎤ xv = ⎢ v 0 ⎥ + ∑ ⎢ ⎥ (− x J ( j ) ) ≥ 0 ⎣ λ ⎦ j =1 ⎣ λ ⎦

Langkah 5: Tambahkan bentuk kendala bidang pemotong yang baru ke dalam tabel simpleks untuk menjadi baris sumber yang baru.


70

Langkah 6 : Variabel xv pada baris sumber yang baru akan menggantikan variabel non basis pada kolom pivot. Langkah 7 : Melakukan operasi kolom agar elemen-alemen pada baris

x v bernilai -1

untuk elemen pada kolom pivot dan yang lainnya bernilai 0. Langkah 8 : Jika masih ada nilai a v 0 < 0 , v ≠ 0 maka dilanjutkan ke Langkah 2. Jika sudah tidak ada maka proses dihentikan dan diperoleh tabel optimum.


71

Algoritma masalah program linear bilangan bulat dual diperlihatkan sebagai berikut : Mulai

Menyusun tabel

Pilih baris sumber v dengan a v 0 < 0 Pilih kolom pivot α p , yakni minimum a vj yang positif secara lexicographic Menentukan nilai λ=maks

⎛ ⎜λ ⎜ ⎝

j

=

− a vj ⎞ ⎟ u j ⎟⎠

Menentukan bentuk kendala bidang pemotong, yakni ⎡ a ⎤ n ⎡ a vj ⎤ x v = ⎢ v 0 ⎥ + ∑ ⎢ ⎥ (− x J ( j ) ) ≥ 0 ⎣ λ ⎦ j =1 ⎣ λ ⎦

Tambahkan bentuk kendala bidang pemotong kedalam tabel Mengganti variabel nonbasis dengan variabel xv Melakukan operasi kolom

nilai av 0 < 0 TIDAK

Penyelesaian sudah optimum

Selesai

YA


72

Berikut akan diberikan contoh penyelesaian masalah program linear bilangan bulat yang menggunakan metode bidang pemotong

Contoh 4.2 Selesaikan masalah program linear bilangan bulat berikut : Maksimumkan:

z = −4 x1 − 5 x 2

Dengan kendala:

− x1 − 4 x 2 ≤ −5

( x3 )

− 3 x1 − 2 x 2 ≤ −7

(x4 )

x1 , x 2 ≥ 0

dan

Penyelesaian :

Masalah program linear di atas dapat dibuat ke bentuk kanonik sebagai berikut : Maksimumkan:

z = −4 x1 − 5 x 2

Dengan kendala:

− x1 − 4 x 2 + x3 − 3 x1 − 2 x 2

dan

= −5 + x 4 = −7

x1 , x 2 , x3 , x 4 ≥ 0

Menyusun tabel awal simpleks

Tabel 4.2. Tabel Awal Pada Contoh Masalah Program Linear Bilangan Bulat


73

Kolom →

α0

Variabel

1

(− x1 )

(− x2 )

x0 =

0

4

5

x1 =

0

−1

0

x2 =

0

0

−1

x3 =

−5

−1

−4

x4 =

−7

−3

−2

α1

α2

↓

ITERASI 1 Langkah 1 : Memilih baris sumber. Dalam tabel dilihat koefisien a 40 = −7 adalah nilai yang paling minimum maka baris x 4 adalah baris sumber yang dipilih. Langkah 2 : Memilih kolom pivot. Dalam tabel dapat diperoleh a 41 = −3 dan koefisien a 42 = −2 . Karena nilai a 41 = −3 yang paling minimum maka kolom α 1 adalah kolom pivot yang

dipilih. Langkah 3 : Menentukan nilai λ i.

Karena kolom pivot yang dipilih adalah kolom pertama maka nilai p yang dipilih adalah 1. Jadi nilai u1 = 1 kemudian akan ditentukan u 2 , yakni ⎛ 1 ⎞ L bilangan bulat terbesar yang memenuhi ⎜⎜ ⎟⎟α 2 f α 1 . Dalam tabel terlihat ⎝ u2 ⎠


74

bahwa komponen pertama α 1 = 4 dan

⎛ 1 α 2 = 5 . Jadi ⎜⎜ ⎝ u2

⎞ L ⎟⎟ 5 f 4 maka ⎠

nilai u 2 yang akan didapat adalah 1. ii. Lihat nilai a vj < 0 pada baris sumber adalah a 41 = −3 dan a 42 = −2 maka nilai λ1 dan λ 2 masing-masing adalah sebagai berikut :

dan

λ1 =

− a 41 − (−3) 3 = = =3 u1 1 1

λ2 =

− a 42 − (−2) 2 = = =2 u2 1 1

iii. Memiilih λ = maksimum ( λ1 , λ 2 ) = maksimum ( 3,2) =3 Langkah 4 : Menentukan bentuk kendala bidang pemotong yang baru yakni ⎡ − 7 ⎤ ⎡ − 3⎤ ⎡− 2⎤ x5 = ⎢ ⎥ + ⎢ ⎥ (− x1 ) + ⎢ ⎥ (− x 2 ) ≥ 0 ⎣ 3 ⎦ ⎣ 3 ⎦ ⎣ 3 ⎦ atau x5 = −3 − 1(− x1 ) − 1(− x 2 ) ≥ 0 Langkah 5 : Tambahkan bentuk kendala bidang pemotong yang baru ke dalam tabel simpleks.


75

Tabel 4.3. Tabel Bentuk Kendala Bidang Pemotong Pada Iterasi 1

Kolom →

α0

α1

Variabel

1

(− x1 )

x1 = x2 = x3 = x4 =

0 0 0 −5 −7

4 −1 0 −1 −3

5 0 −1 −4 −2

x5 =

−3

−1

−1

α2

(− x 2 )

↓

x0 =

Langkah 6 : Variabel x5 akan menggantikan variabel x1 . Langkah 7 : Melakukan operasi kolom. Sehingga tabel baru yang diperoleh adalah Tabel 4.4. Tabel Setelah Dilakukan Operasi kolom Pada Iterasi 1

→

Kolom Variabel

α0

α1

α2

1

(− x5 )

(− x2 )

4 −1 0 −1 −3 −1

1 1 −1 −3 1 0

↓

x0 =

x1 = x2 = x3 = x4 = x5 =

− 12 3 0 −2 2 0


76

Langkah 8 : Karena masih ada nilai a v 0 < 0 , v ≠ 0 , yakni a30 = −2 maka dilanjutkan ke Langkah 2.

ITERASI 2 Langkah 1 : Memilih baris sumber. Dalam tabel dilihat koefisien a30 = −2 adalah nilai yang paling minimum maka baris x3 adalah baris sumber yang dipilih. Langkah 2 : Memilih kolom pivot. Dalam tabel diperoleh a31 = −1 dan koefisien a32 = −3 . Karena nilai a32 = −3 yang paling minimum maka kolom α 2 adalah kolom pivot yang dipilih. Langkah 3 : Menentukan nilai λ i.

Karena kolom pivot yang dipilih adalah kolom kedua maka nilai p yang dipilih adalah 2, jadi nilai u 2 = 1 . Kemudian ditentukan u1 , yakni bilangan ⎛1⎞ L bulat terbesar yang memenuhi ⎜⎜ ⎟⎟α 1 f α 2 . Dalam tabel terlihat bahwa ⎝ u1 ⎠ ⎛1⎞ L komponen pertama α1 = 4 dan α 2 = 1 . Jadi ⎜⎜ ⎟⎟ 4 f 1 maka nilai u1 ⎝ u1 ⎠ yang akan didapat adalah 3.


77

ii. Lihat nilai a vj < 0 pada baris sumber adalah a31 = −1 dan a32 = −3 maka diperoleh

dan

λ1 =

− a 41 − (−1) 1 = = u1 3 3

λ2 =

− a 42 − (−3) 3 = = =3 u2 1 1

iii. Memiilih λ

= maksimum ( λ1 , λ 2 ) = maksimum ( 1 ,3) 3 =3

Langkah 4 : Menentukan bentuk kendala bidang pemotong yang baru yakni ⎡ − 2 ⎤ ⎡ − 1⎤ ⎡ − 3⎤ x6 = ⎢ ⎥ + ⎢ ⎥ (− x5 ) + ⎢ ⎥ (− x 2 ) ≥ 0 ⎣ 3 ⎦ ⎣3⎦ ⎣ 3 ⎦ atau x6 = −1 − 1(− x5 ) − 1(− x 2 ) ≥ 0 Langkah 5 : Tambahkan bentuk kendala bidang pemotong yang baru ke dalam tabel simpleks.


78

Tabel 4.5. Tabel Dengan Bentuk Kendala Bidang Pemotong Pada Iterasi 2

Kolom →

α0

Variabel

1

α1

α2

(− x5 )

(− x2 )

↓

x0 =

x1 = x2 = x3 = x4 = x5 =

− 12 3 0 −2 2 0

x6 =

−1

4 −1 0 −1 −3 −1 −1

1 1 −1 −3 1 0 −1

Langkah 6 : Variabel x6 akan menggantikan variabel x 2 . Langkah 7 : Melakukan operasi kolom. Sehingga tabel baru yang diperoleh adalah Tabel 4.6. Tabel Setelah Dilakukan Operasi kolom Pada Iterasi 2

Kolom Variabel

→

α0 1

α1

α2

(− x5 )

(− x6 )

↓

x0 =

x1 = x2 = x3 = x4 = x5 = x6 =

− 13 2 1 1 1 0 0

3 −2 1 2 −4 −1 0

1 1 −1 −3 1 0 −1


79

Langkah 8 : Karena sudah tidak ada nilai a v 0 < 0 , v ≠ 0 maka tabel sudah optimum dengan nilai ( x1 , x 2 ) = (2,1) dan nilai optimum = -13

Pada masalah program linear bilangan bulat dalam bentuk dualnya dapat diurakan bahwa dalam kendala utama yang memiliki variabel awal x1 dan x 2 adalah − x1 − 4 x 2 ≤ −5 − 3 x1 − 2 x 2 ≤ −7

Kendala bidang pemotong yang didapat pada perhitungan diatas adalah x5 = −3 − 1(− x1 ) − 1(− x 2 ) ≥ 0 atau x1 + x 2 ≤ −3 dan x6 = −1 − 1(− x5 ) − 1(− x 2 ) ≥ 0 x6 = −1 − 1(− (− 3 − 1(− x1 ) − 1(− x 2 ))) − 1(− x 2 ) ≥ 0 x6 = −4 − 1(− x1 ) − 2(− x2 ) ≥ 0 atau x1 + 2 x 2 ≤ −4


80

Dari kendala-kendala di atas dapat diilustrasikan ke dalam gambar dibawah ini :

x2 4• 3• 2•

•

1 • •

1

• 2

•

• 4

3

x4

x5

• 5 x 6

x1 x3

Gambar 4.1. Penyelesaian Masalah Program Linear Bilangan Bulat Dual

Dari contoh dimuka terlihat bahwa program linear bilangan bulat dual adalah cara lebih efisien bila dibandingkan dengan masalah program linear bilangan bulat fraktional dual yang menggunakan metode bidang pemotong karena dalam perhitungan lebih cepat mencapai penyelesaian optimum.


81

BAB V PENUTUP

A. Kesimpulan Masalah program linear bilangan bulat dikategorikan menjadi dua masalah, yakni program linear bilangan bulat fraksional dual yang memungkinkan adanya bilangan pecahan dalam perhitungannya, dan program linear bilangan bulat dual dimana dalam perhitungannya harus berupa bilangan bulat. Kedua masalah tersebut dapat diselesaikan dengan metode bidang pemotong yang menggunakan metode simpleks dual. Langkah-langkah metode program linear bilangan bulat fraksional dual adalah sebagai berikut : 1.

Mengubah bentuk baku menjadi bentuk kanonik.

2.

Menyusun tabel awal dari masalah program linear bilangan bulat.

3.

Masalah program linear bilangan bulat ini diselesaikan dahulu sebagai masalah program linear biasa, yakni dengan menggunakan menggunakan metode simpleks dual sampai ditemukan penyelesaian optimum tetapi penyelesaian yang didapat belum tentu berupa bilangan bulat.

4.

Uji optimum. Jika penyelesaian optimum pada langkah sebelumnya belum berupa bilangan bulat maka langkah-langkah penyelesaian dilanjutkan lagi menggunakan metode bidang pemotong dengan menambahkan kendala bidang pemotong yang baru yang memuat variabel pengetat.


82

Langkah-langkah metode program linear bilangan bulat dual adalah sebagai berikut : 1.

Mengubah bentuk baku menjadi bentuk kanonik.

2.

Menyusun tabel awal dari masalah program linear bilangan bulat.

3.

Masalah program linear bilangan bulat diselesaikan menggunakan metode bidang pemotong dengan menambahkan kendala bidang pemotong yang baru yang memuat variabel pengetat. Dalam menyelesaikan masalah program linear bilangan bulat fraksional

dual akan ditemukan kesulitan karena tidak cukup hanya menyelesaikan dengan metode bidang pemotong yang menggunakan metode simpleks dual tetapi harus dicari dahulu penyelesaian menggunakan metode simpleks dual. Tetapi dalam menyelesaikan masalah program linear bilangan bulat dual dengan menggunakan metode bidang pemotong penghitungannya dilakukan secara langsung dengan menambahkan betuk kendala bidang pemotong tanpa harus diselesaikan dengan metode simpleks dual dahulu. Dengan demikian penyelesaian masalah program linear bilangan bulat dual akan lebih efisien dan lebih cepat mendapatkan penyelesaian optimum.

B. Saran Dari pembahasan tentang program linear bilangan bulat dengan metode bidang pemotong, apabila mendapatkan masalah program linear bilangan bulat akan lebih baik bila masalah tersebut dibawa kedalam masalah program linear bilangan bulat dual. Namun hendaknya metode ini dibandingkan dengan metode enumerasi atau metode cabang dan batas.


83

DAFTAR PUSTAKA

Bronson, R (1991) Teori dan Soal-soal Operation Research. Penerbit : Erlangga Chvatal, V. (1983). Linear Programming. Mac Graw Hill Book Company, Inc. Ignizio, J.P. & Cavalier, T.M. (1994). Linear Programming. Mac Graw Hill Book Company, Inc. Salkin, H.M. (1975) Integer Programming. Addison-Wesley Publishing Company, Inc. Salkin, H.M. dan Mathur kamlesh (1989) Foundations of Integer Programming. North-Holland. Supranto, J. M. A. (1980). Linear Programming. Jakarta: Penerbit Fakultas Ekonomi Universitas Indonesia. Susanta, B. (1994). Program Linear. Jakarta: LPTK Depdikbud. Taha, H. A (1996). Riset Operasi. Jakarta: Penerbit Binarupa Aksara Wolsey, L.A (1998) Integer Programming. John Wiley & Sons, New York. Wu, N. & Coppins, R. (1981). Linear Programming And Extensions. Mac Graw Hill Book Company, Inc.

PROGRAM LINEAR BILANGAN BULAT DUAL SKRIPSI

Recommend Documents