program linear bi langan bulat dual skripsi

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

PLAGIAT MERUPAKAN TINDAKAN TIDAK TERPUJI

ii


iii


iv

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.


v


vi

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.


vii

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.


viii

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),


ix

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.


x

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


xi

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


xii

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


xiii

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


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) :

nnxcxcxcz +++= K2211 (2.1)


6

dengan kendala-kendala :

⎪⎪⎭

⎪⎪⎬

⎫

≥=≤+++

≥=≤+++≥=≤+++

mnmnmm

nn

nn

bxaxaxa

bxaxaxabxaxaxa

},,{

},,{},,{

2211

22222121

11212111

K

MOOM

K

K

(2.2)

njx j ,,2,1,0 K=≥ (2.3)

Rumus di atas dapat diringkas sebagai berikut :

Minimumkan ( atau maksimumkan) :

∑=

=n

jjj xcz

1

(2.4)

dengan kendala

∑=

=≥=≤n

jijij mibxa

1

,,2,1,),,( K (2.5)

njx j ,,2,1,0 K=≥ (2.6)

2. Bentuk Matriks Masalah Program linear :

Minimumkan (atau maksimumkan) : cx=z (2.7)


{0

},,≥

≥=≤x

bAx (2.8)

dengan :

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=

mnmm

n

n

aaa

aaaaaa

K

MOM

K

K

21

22221

11211

A ,

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=

nx

xx

M2

1

x ,

⎥⎥⎥⎥

⎦

⎤

⎢⎢⎢⎢

⎣

⎡

=

nb

bb

M2

1

b , ( )nccc ,,, 21 K=c


7

Definisi 2.1 Fungsi sasaran atau fungsi tujuan

Fungsi sasaran masalah program linear berbentuk

∑=

=p

jjj xcz

1

dengan p merupakan banyaknya variabel, jx merupakan variabel ke- j , dan jc

merupakan koefisien ongkos dari variabel ke- j .

Definisi 2.2 Kendala utama dan kendala tak negatif

Persamaan atau pertidaksamaan dalam masalah program linear

( ) ,,,1

,∑=

≥=≤n

jijji bxa mi ,...,2,1=

disebut kendala utama, dengan m merupakan banyaknya kendala, dan jia ,

(koefisien teknis) merupakan koefisien kendala ke- i dari variabel ke- j dan ib

menyatakan konstanta di ruas kanan untuk kendala ke- i .

Sedangkan ;0≥jx pj ,...,2,1= 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 ix 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 0x ≥ .

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 ( )21 , xx 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 ( )21 , xx 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

0 1x

2x

A

B

D

C

z

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 :

knknkk bxaxaxa ≤+++ K2211

maka kendala tersebut dapat diubah ke bentuk persamaan dengan menambah

variabel pengetat 1+nx dengan 01 >+nx . Dengan demikian , persamaan untuk

kendala tersebut adalah

0, 112211 >=++++ ++ nknnknkk xbxxaxaxa K .


11

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

berbentuk pertidaksamaan :

knknkk bxaxaxa ≥+++ K2211

dapat diubah ke bentuk persamaan dengan mengurangi pertidaksamaan tersebut

dengan variabel pengetat 1+nx dengan 01 >+nx

knnknkk bxxaxaxa =−+++ +12211 K , 01 >+nx

Untuk menyesuaikan dengan bentuk kendala baru, fungsi sasaran yang

semula berbentuk nnxcxcxcz +++= K2211 diubah menjadi

pnnjxxcxcxcxcz pnjnn ,,2,1,)( 12211 KKK ++=++++++= +

dengan 021 ==== ++ pnn ccc K dan pnnixi ,,2,1, K++= adalah variabel

pengetat.

Dengan demikian masalah yang telah diubah kedalam bentuk kanonik

akan menjadi seperti ini :

Minimumkan ( atau maksimumkan ) :

∑=

=n

jjj xcz

1

(2.9)

dengan kendala

∑=

==n

jijij mibxa

1

,,2,1, K (2.10)

njx j ,,2,1,0 K=≥ (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 : 321 52010 xxxz +−=

dengan kendala

102

8

321

321

≤+−≤+−

xxxxxx

Penyelesaian :

Pada masing-masing kendala yang masih berbentuk pertidaksamaan ditambahkan

satu variabel pengetat, misalkan 4x dan 5x sehingga masala program linear di

atas menjadi :

Maksimumkan : 54321 0052010 xxxxxz +++−=

Dengan kendala :

1028

5321

4321

=++−=++−

xxxxxxxx

Soal ini sudah berbentuk kanonik dan berpola maksimum, dengan 321 ,, xxx

variabel asli dan 54 , xx 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 Mazz −= , sedangkan fungsi sasaran yang baru untuk pola minimum

berbentuk Mazz += 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 0≥ib sehingga memenuhi bentuk baku program linear.

Langkah 2 :

Menyusun tabel awal seperti dalam tabel berikut ( Tabel 2.1 )

Tabel 2.1 Tabel Awal Simpleks

jc nccc K21

ic ji xx \ nxxx K21 ib iR

mc

c

c

M2

1

mx

x

x

M2

1

mnmm

n

n

aaa

aaaaaa

K

MOM

K

K

21

22221

11211

mb

bb

M

2

1

mR

RR

M

2

1

jz nzzz K21 z

jj cz − z

Keterangan :

jx : variabel-variabel keputusan

ija : koefisien teknis

ib : suku tetap (tak negatif)

jc : koefisien ongkos

ix : variabel yang menjadi basis dalam tabel yang ditinjau

nn czczcz −−− K2211


15

ic : koefisien ongkos milik variabel basis ix

jz : ∑=

m

iijiac

1

z : ∑=

m

iiibc

1

jj cz − : selisih jz dengan jc

iR : ik

i

ab

hanya untuk 0≥ia

Langkah 3 :

Menguji keoptimuman, dengan memperhatikan nilai jj cz − . Untuk masalah

dengan pola maksimum, tabel dikatakan optimum bila nilai 0≥− jj cz

untuk semua j. Sedangkan untuk masalah dengan pola minimum tabel

dikatakan optimum bila nilai 0≤− jj cz 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 jj cz − terkecil atau

paling minimum. Untuk masalah yang berpola maksimum adalah dengan

memilih nilai jj cz − terbesar atau paling maksimum. Setelah ditemukan


16

kolom pivot maka selanjutnya dicari nilai rasio ( iR ) untuk setiap baris,

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

berbeda untuk pola maksimum dan pola minimum, dipilih nilai iR terkecil

atau ⎟⎟⎠

⎞⎜⎜⎝

⎛=

ik

ii a

bR min . Baris dengan iR terkecil kemudian menjadi baris

pivot. Setelah baris pivot dan kolom pivot terpilih, maka perpotongan antara

baris pivot dan kolom pivot ( )rsa 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 rsa 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 4321 226 xxxxz +−+=

dengan kendala 102234 4321 ≥+−+ xxxx

18428 4321 ≥+++ xxxx

dan 0,,, 4321 ≥xxxx

Penyelesaian :

Masalah dual

Maksimumkan 21 1810 yyg +=

dengan kendala 684 21 ≤+ yy

23 21 ≤+ yy

122 21 −≤+− yy

242 21 ≤+ yy

dan 0, 21 ≥yy


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 cx=z

memenuhi bAx ≤ ( semua berbentuk ≤ )

Pola minimum baku :

Minimumkan cx=z

memenuhi bAx ≥ ( 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) cx=z (2.12)

yang memenuhi bAx = (2.13)


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 0≥ib sehingga memenuhi bentuk baku program

linear.

Langkah 2 :

Menyusun tabel awal dual simpleks yang disajikan sebagai berikut

Tabel 2.2 Tabel Awal Simpleks Dual

ic nccc K21

jc ji xx \ nxxx K21 ib

mc

c

c

M2

1

mx

x

x

M2

1

mnmm

n

n

aaa

aaaaaa

K

MOM

K

K

21

22221

11211

mb

bb

M

2

1

jz nzzz K21 z

jj cz − z

iR nRRR K21

Keterangan :

ij

jji a

czR

−= , hanya untuk 0<ija

nn czczcz −−− K2211


20

Langkah 3 :

Memilih baris pivot, yakni dengan memilih baris i yang mempunyai nilai ib

paling minimum dengan )0( <ib

Jika ada nilai ib yang sama maka dipilih sembarang ib .

Langkah 4 :

Memilih kolom pivot, yakni mencari nilai rasio. Nilai rasio iR diperoleh

dengan membagi jj cz − dan nilai mutlak dari koefisien teknis yang

berkoefisien negatif atau iR ⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −=

ij

jj

a

cz dengan 0<ija . Untuk masalah

yang berpola minimum dipilih nilai rasio yang terkecil atau iR

⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −=

ij

jj

a

czmin , sedangkan masalah yang berpola maksimum dipilih nilai

rasio ija yang terkecil atau iR ⎟⎟

⎠

⎞

⎜⎜

⎝

⎛ −=

ij

jj

a

czmin . Jika koefisien teknis ija

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 ( rsa ) yang disebut elemen pivot ini bernilai 1 dan yang lainnya

bernilai 0.


21

Langkah 6 :

Menguji keoptimuman. Jika semua 0≥ib 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 ( )ija tetapi dalam

masalah dualnya berbentuk tranpose dari matriks tersebut, yakni ( ) .tija

4. ib dalam masalah program linear yang berbentuk primal disebut suku tetap

tetapi dalam bentuk dualnya ib menjadi koefisien ongkos.

5. jc dalam masalah program linear yang berbentuk primal disebut koefisien

ongkos tetapi dalam bentuk dualnya jc 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 ) :

nn xcxcxcZ +++= K2211 (2.14)


⎪⎪⎭

⎪⎪⎬

⎫

≥=≤+++

≥=≤+++≥=≤+++

mnmnmm

nn

nn

bxaxaxa

bxaxaxabxaxaxa

},,{

},,{},,{

2211

22222121

11212111

K

MOOM

K

K

(2.15)

njx j ,,2,1,0 K=≥ (2.16)

dan jx bilangan bulat.


23

Rumus di atas dapat diringkas sebagai berikut :

Maksimumkan (atau minimumkan)

∑=

=n

jjj xcZ

1 (2.17)

dengan kendala :

( )∑=

≥=≤n

jijij bxa

1,, (2.18)

.,,2,1,,,2,1

,0

njmi

bulatbilanganxx jj

KK ==

≥ (2.19)

2. Bentuk baku masalah program linear bilangan bulat campuran.

Maksimumkan (atau minimumkan) :

∑ ∑= =

+=n

j

p

kkkjj ydxcZ

1 1

(2.20)

dengan kendala :

.,,2,1,,,2,1,,,2,1

,0,011

pknjmi

bulatbilanganxyx

batauygxa

jkj

i

p

kkik

n

jjij

KKK ===

≥≥

≥≤∑∑==

(2.21)

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 0≥′x

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 0≥′′x ditambahkan agar menghapus titik F dari daerah layak

sehingga diperoleh daerah layak yang baru adalah ABCGHIE. Dalam


m

p

G

d

b

l

b

s

menyelesaik

penyelesaian

Gambar 3.1. b

Perb

dengan masa

bernilai -1.

Perh

linear bilang

berpola mak

sebagai berik

kan kembali

n optimum b

Ilustrasi Penybidang pemoto

edaan metod

alah program

atikan kemb

gan bulat. S

ksimum dap

kut :

masalah pr

bilangan bula

yelesaian Masaong

de simpleks

m linear bila

bali pada b

ecara umum

pat dinyataka

rogram linea

at, yakni titi

alah Program

dual yang su

angan bulat a

bab sebelum

m masalah pr

an dalam be

ar bilangan

ik H.

Linear Bilang

udah dibahas

adalah pada

mnya menge

rogram linea

entuk kanon

bulat akan

gan Bulat den

s pada bab s

elemen pivo

enai masalah

ar bilangan

nik dan bent

26

ditemukan

ngan metode

ebelumnya

otnya yaitu

h program

bulat yang

tuk matriks


27

1. Bentuk kanonik masalah program linear bilangan bulat :

Maksimumkan :

nn xcxcxcz +++= K2211 (3.1)


⎪⎪⎭

⎪⎪⎬

⎫

++++

=++++=++++

+

+

+

mmnnmnmm

nnn

nnn

bxxaxaxa

bxxaxaxabxxaxaxa

K

MOOM

K

K

2211

222222121

111212111

(3.2)

njx j ,,2,1,0 K=≥ (3.3) dan jx bilangan bulat.

2. Bentuk matriks masalah program linear bilangan bulat :

Maksimumkan :

cx = z (3.4)


A x ≤ b (3.5)

x ≥ 0 dan komponen-komponen x adalah bilangan bulat. (3.6)

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

Bentuk kanonik pada masalah program linear bilangan bulat disusun

ke dalam bentuk seperti dibawah ini :

Maksimumkan :

( ) ( )( ) ( )( )nn xcxcxcz −−++−−+−−= K2211 )( (3.7)


28


( )( ) ( )( ) ( )( )( )( ) ( )( ) ( )( )

( )( ) ( )( ) ( )( ) mmnnmnmm

nnn

nnn

bxxaxaxa

bxxaxaxabxxaxaxa

=+−−++−−+−−

=+−−++−−+−−=+−−++−−+−−

+

+

+

K

MMMOOM

K

K

2211

222222121

111212111

(3.8)

njx j ,,2,1,0 K=≥

dan jx bilangan bulat.

Bentuk kanonik di atas dapat diubah ke dalam bentuk seperti dibawah ini :

Maksimumkan :

( ) ( ) ( )nn xaxaxaax −++−+−+= 0202101000 K (3.9)


( )( )

( )⎪⎪⎭

⎪⎪⎬

⎫

−−=

−−=−−=

nn xx

xxxx

1

11

22

11

OM (3.10)

( ) ( ) ( )

( ) ( ) ( )⎪⎭

⎪⎬

⎫

−++−+−+=

−++−+−+=

+++++

+++++

nnmnmnmnmnmn

nnnnnnn

xaxaxaax

xaxaxaax

,22,11,0,

,122,111,10,11

K

MOOOOM

K

(3.11)

dengan mnjx j +=≥ ,,2,1,0 K

dan jx bilangan bulat untuk mnj += ,,1,0 K .

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 jj acazx 0000 ,0, −=== , ( nj ,,1K= ), 0,ini ab +=

( )mi ,,1K= , dan ( )njmiaa jinij ,,11;,,1, KK ==== + .

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 ( )1x− K ( )jx− K ( )nx−

=0x 00a 01a K ja0 K na0

0

0

0

M

M

0

0

1

M

M

−

K

O

L

O

K

0

1

0

M

M

−

K

O

L

O

K

1

0

0

−M

M

=

=

+

+

mn

n

x

xM

1

0,

0,1

mn

n

a

a

+

+

M

1,

1,1

mn

n

a

a

+

+

M

K

O

K

jmn

jn

a

a

,

,1

+

+

M K

O

K

Keterangan :

jj acazx 0000 ,0, −=== , ( nj ,,1K= ), 0,ini ab += ( mi ,,1K= ), dan

( )njmiaa jinij ,,11;,,1, KK ==== + , ),,1(0 mnixi +=≥ K .

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 0va paling minimum dengan 00 <va , 0≠v

=

=

=

n

j

x

x

x

M

M1

nmn

nn

a

a

,

,1

+

+

M


31

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

paling minimum dan nilai rasio = ⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

vj

j

aa0min

Langkah 3 : Mengganti variabel nonbasis pada kolom pivot dengan variabel

vx , yakni variabel pada baris pivot.

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

kolom pivot bernilai -1 dan yang lain bernilai 0.

Langkah 5 : Bila nilai 0va 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 kmnx ++ . 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 ( )1x− K ( )jx− K ( )nx−

=0x 00a 01a K ja0 K na0

=

=

+

+

mn

n

x

xM

1

0

0

0

M

M

0,

0,1

mn

n

a

a

+

+

M

0

0

1

M

M

−

K

O

L

O

K

0

1

0

M

M

−

K

O

L

O

K

1

0

0

−M

M

1,

1,1

mn

n

a

a

+

+

M

K

O

K

jmn

jn

a

a

,

,1

+

+

M K

O

K

=++ kmnx 0,kmna ++ 1,kmna ++ K jkmna ,++ K nkmna ,++

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.

=

=

=

n

j

x

x

x

M

M1

nmn

nn

a

a

,

,1

+

+

M


33

Jika variabel basis ix pada persamaan ke-i bukan merupakan bilangan bulat

maka variabel tersebut dapat dinyatakan sebagai :

( )( ) 01

ijJ

n

jiji axax =−−∑

=

(3.12)

Keterangan : 0ia bukan bernilai bilangan bulat

ija dapat berbentuk bilangan bulat

J adalah himpunan indeks variabel nonbasis

J(j) adalah elemen j di dalam J

( )jJx adalah variabel nonbasis j di dalam J

Persamaan (3.12) dapat ditulis sebagai berikut

( )( )jJ

n

jijii xaax −+= ∑

=10 (3.13)

Setiap persamaan seperti di atas dinyatakan sebagai baris sumber (source

row).

Misalkan :

[ ] iii faa += 00

dan

[ ] ijijij faa += (3.14)

dengan :


34

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

dan

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

maka 10 << if dan 10 <≤ ijf

Ada dua cara untuk memilih baris sumber yaitu :

1. Baris dengan nilai 0if yang paling maksimum.

2. Baris dengan nilai

⎪⎪⎭

⎪⎪⎬

⎫

⎪⎪⎩

⎪⎪⎨

⎧

∑=

n

jij

i

f

f

1

0 yang paling maksimum.

Jika nilai 0if atau

⎪⎪⎭

⎪⎪⎬

⎫

⎪⎪⎩

⎪⎪⎨

⎧

∑=

n

jij

i

f

f

1

0 untuk setiap baris selalu sama maka dapat dipilih

sebarang baris untuk menjadi baris sumber.

b. Menentukan bentuk kendala bidang pemotong

Dari uraian pemilihan baris sumber, dengan persamaan (3.13) akan

menjadi :


35

[ ] [ ]( ) ( )( )jJ

n

jijijiii xfafax −+++= ∑

=10

[ ] [ ] ( )( ) ( )( )jJ

n

jijjJ

n

jijii xfxafa −+−++= ∑∑

== 110

atau

( )( ) [ ] [ ] ( )( )jJ

n

jijiijJ

n

jiji xaaxxff −−−=−+ ∑∑

== 10

1

(3.15)

Supaya nilai ix dan ( )( )jJx− 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 0≥ijf dan

( )( ) 0≤− jJx untuk setiap nilai i dan j , maka

( )( ) 01

≤−∑=

jJ

n

jij xf

dengan demikian ( )( ) ijJ

n

jiji fxff ≤−+∑

=1

.

Karena 1<if maka ( )( ) 11

<−+∑=

jJ

n

jiji xff (3.16)

atau

( )( )jJ

n

jiji xff −−< ∑

=11


36

Karena ruas kiri persamaan (3.15) harus bernilai bilangan bulat, maka

berdasarkan persamaan (3.15), haruslah

( )( ) 01

≤−+∑=

jJ

n

jiji xff

Jika bentuk di atas ditambahkan dengan variabel pengetat kmnx ++ dengan

0≥++ kmnx bilangan bulat, maka didapat :

( )( ) 01

=+−+ ++=∑ kmnjJ

n

jiji xxff

atau

( )( ) ijJ

n

jijkmn fxfx −−−= ∑

=++

1 (3.17)

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 ( )( ) 0=− jJx sehingga ikmn fx =++ , 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 vx dengan dua cara di bawah ini :

1. Baris dengan nilai 0vf yang paling maksimum.

2. Baris dengan nilai

⎪⎪⎭

⎪⎪⎬

⎫

⎪⎪⎩

⎪⎪⎨

⎧

∑=

n

jvj

v

f

f

1

yang paling maksimum.

Langkah 2 :

Menentukan bentuk kendala bidang pemotong yang baru, yakni pembatas

sekunder seperti persamaan (3.17)

( )( ) vjJ

n

jvjkmn fxfx −−−= ∑

=++

1

Langkah 3 :

Tambahkan bentuk pembatas sekunder yang baru dalam tabel simpleks.


38

Langkah 4 :

Mencari baris pivot dengan melihat nilai koefisien 0va yang bernilai negatif

dan dipilih yang paling minimum

Langkah 5 :

Mencari kolom pivot dengan melihat niali R=vj

j

a

a0 yang terkecil.

Langkah 6 :

Menggantikan variabel non basis pada kolom pivot dengan Variabel vx .

Langkah 7 :

Melakukan operasi kolom agar elemen-elemen baris vx pada kolom pivot

bernilai -1 dan yang lainnya bernilai 0.

Langkah 8 :

Jika masih ada nilai vx 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: 21 54 xxz −−=

Dengan kendala: 54 21 −≤−− xx

723 21 −≤−− xx

dan 0, 21 ≥xx

Penyelesaian :

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


Dengan kendala: 54 321 −=+−− xxx

723 421 −=+−− xxx

dan 0,,, 4321 ≥xxxx


40

1. Menyusun tabel awal simpleks.

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

1 ( )1x− ( )2x−

0x 0 4 5

4

3

2

1

xxxx

75

00

−−

3101

−−

−

2410

−−−

2. Menyelesaikan dengan metode simpleks dual.

ITERASI 1

Langkah 1 : Memilih baris pivot

Dari tabel awal diperoleh nilai 530 −=a dan 740 −=a maka nilai

min{ }=4030 ,aa min{ } 77,5 −=−− . Jadi baris empat sebagai baris pivot.

Langkah 2 : Memilih kolom pivot

Dengan memilih nilai rasio terkecil yakni =4R min⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

42

02

41

01 ,aa

aa

= min34

25,

34

=⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

−−. Jadi kolom pertama akan terpilih sebagai kolom

pivot.

Langkah 3 : Menggantikan variabel 1x dengan variabel 4x

Langkah 4 : Melakukan operasi kolom, sehingga diperoleh tabel baru berikut


41

Tabel 3.4. Tabel Setelah Operasi kolom Pada Iterasi 1

1 ( )4x− ( )2x−

0x 328

− 34

37

4

3

2

1

x

x

x

x37

0

38

−

0

31

− 32

0 -1

31

− 3

10−

-1 0

Langkah 5 : Karena masih ada nilai 38

30 −=a maka kembali ke Langkah 1

ITERASI 2

Langkah 1 : Memilih baris pivot

Dari tabel diatas diperoleh nilai min { }3010 ,aa = min 38

38,

37

−=⎭⎬⎫

⎩⎨⎧ −=

jadi baris ketiga sebagai bari pivot.

Langkah 2 : Memilih kolom pivot

Dengan memilih nilai rasio terkecil yakni =4R min⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

32

02

31

01 ,aa

aa

=min

37

31037,

3134

=⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

−− maka kolom kedua akan terpilih sebagai kolom

pivot.

Langkah 3 : Menggantikan variabel 2x dengan variabel 3x


42

Langkah 4 : Melakukan operasi kolom, sehingga diperoleh tabel baru

sebagai berikut

Tabel 3.5. Tabel Setelah Operasi kolom Pada Iterasi 2

1 ( )4x− ( )3x−

0x 10

112−

1011

107

2x

3x

4x

1018

108

0

0

104

− 102

101

0 -1

-1 0

Langkah 5 : Karena sudah tidak ada 00 <va maka proses dihentikan.

dengan nilai 1018

1 =x dan 108

2 =x

3. Menguji keoptimuman.

Dari iterasi kedua telah dapatkan penyelesaian optimum dari masalah

program linear, yaitu1018

1 =x dan 108

2 =x , tetapi penyelesaian tersebut belum

bulat maka penyelesaian dilanjutkan dengan menggunakan metode bidang

pemotong.

1x

103

−


43

ITERASI 1

Langkah 1 : Memilih baris sumber

Untuk 1018

1 =x diperoleh [ ]1081

1018

1018

1018

101010 =−=⎥⎦⎤

⎢⎣⎡−=−= aaf

Untuk 108

2 =x diperoleh [ ]1080

108

108

108

202020 =−=⎥⎦⎤

⎢⎣⎡−=−= aaf

Karena nilai 108

21 == ff maka tidak ada informasi untuk memilih baris

sumber, selanjutnya digunakan cara yang kedua.

• Untuk baris pertama dapat dinyatakan sebagai berikut :

( ) ( )1018

104

102

43 ≥−−− xx

Sehingga diperoleh [ ]1020

102

102

102

111111 =−=⎥⎦⎤

⎢⎣⎡−=−= aaf dan

[ ] ( )1061

104

104

104

121212 =−−−=⎥⎦⎤

⎢⎣⎡−−−=−= aaf

• Untuk baris kedua dapat dinyatakan sebagai berikut :

( ) ( )108

101

103

43 ≥−+−− xx

Sehingga diperoleh [ ] ( )1071

103

103

103

212121 =−−−=⎥⎦⎤

⎢⎣⎡−−−=−= aaf dan

[ ] ( )1010

101

101

101

222222 =−=⎥⎦⎤

⎢⎣⎡−=−= aaf


44

Dengan demikian,

maks⎭⎬⎫

⎩⎨⎧

++ 2221

20

1211

10 ,ff

fff

f = maks

⎪⎪⎭

⎪⎪⎬

⎫

⎪⎪⎩

⎪⎪⎨

⎧

++101

107

108

,

106

102

108

= maks

⎪⎪⎭

⎪⎪⎬

⎫

⎪⎪⎩

⎪⎪⎨

⎧

108

108

,

108

108

=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 1x .

Langkah 2 : Menentukan bentuk kendala baru, yakni pembatas sekunder

Perhatikan kembali pertidaksamaan 1x : ( ) ( )1018

104

102

43 ≥−−− xx

Dari Langkah 1 diperoleh 102

11 =f ,106

12 =f dan 108

10 =f

Maka persamaan pembatas sekunder yang baru adalah

( ) ( ) 0108

106

102

435 ≥−−−−−= xxx


45

Langkah 3 : Tambahkan bentuk pembatas sekunder yang baru dalam tabel

simpleks.

Tabel 3.6. Tabel Dengan Bentuk Pembatas Sekunder Pada Iterasi 1

1 ( )4x− ( )3x−

0x 10112

− 1011

107

2x

3x

4x

1018

108

0

0

104

− 102

101

0 -1

-1 0

5x 108

− 106

− 102

−

Langkah 4 :Mencari baris pivot

Dari tabel koefisien 108

50 −=a pada baris kelima, maka baris kelima

menjadi baris pivot

Langkah 5 : Mencari kolom pivot

Dari tabel pada kolom pertama dilihat nilai R terkecil, yakni

611

10610

11

51

01 =−

=aa

1x

103

−


46

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

variabel 5x .

Langkah 7 : Melakukan operasi kolom

Tabel 3.7. Tabel Setelah Dilakukan Operasi kolom Pada Iterasi 1

1 ( )5x− ( )3x−

0x 676

− 6

11 62

2x

3x

4x

5x

614

64

0

68

0

64

− 62

61

62

−

0 -1

610

− 62

-1 0

Langkah 8 :

Karena nilai 6

141 =x dan

64

2 =x yang nilainya belum berupa bilangan

bulat maka di lanjutkan ke Langkah 1.

ITERASI 2


Untuk 6

141 =x diperoleh

622

614

614

614

10 =−=⎥⎦⎤

⎢⎣⎡−=f

1x


47

Untuk 64

2 =x diperoleh 640

64

64

64

20 =−=⎥⎦⎤

⎢⎣⎡−=f

=f maks{ }=2010 , ff maks ⎭⎬⎫

⎩⎨⎧

64,

62 =

64

Jadi baris kedua pada persamaan 2x terpilih sebagai baris sumber


Pada tabel untuk baris kedua dapat dinyatakan sebagai berikut

( ) ( )64

61

62

53 ≥−+−− xx

Sehingga diperoleh [ ]610

61

61

61

222121 =−=⎥⎦⎤

⎢⎣⎡−=−= aaf dan

[ ] ( )641

62

62

62

222222 =−−−=⎥⎦⎤

⎢⎣⎡−−−=−= aaf

Dari langkah sebelumnya didapat 64

20 =f


( ) ( ) 064

61

64

536 ≥−−−−−= xxx


simpleks.


48


1 ( )5x− ( )3x−

0x 676

− 6

11 62

2x

3x

4x

5x

6x

614

64

0

68

0

64

−

64

− 62

61

62

−

0 -1

610

− 62

-1 0

61

− 64

−


Dari tabel, koefisien 64

60 −=a pada baris keenam, maka baris keenam

dipilih sebagai baris pivot.


Dari tabel, pada kolom kedua dilihat nilai R terkecil, yakni

42

6462

62

02 =−

=ac

Langkah 6 :

Menggantikan variabel non basis pada kolom pivot dengan variabel 6x .

1x


49



1 ( )5x− ( )6x−

0x 13−

47

42

1x

2x

3x

4x

5x

6x

2

1

1

1

0

0

43

− 42

41

42

−

41

46

−

47

− 4

2

-1 0

0 -1

Langkah 8 :

karena nilai 0va sudah berupa bilangan bulat maka tabel sudah optimum

dengan nilai ( )21 , xx = ( )1,2 dengn nilai optimum= -13

Pada masalah program linear bilangan bulat dalam bentuk dualnya dapat

diurakan bahwa kendala awal dengan variabel awal 1x dan 2x adalah

54 21 −≤−− xx atau 213 45 xxx ++−=

723 21 −≤−− xx atau 214 237 xxx ++−=


50

Kendala bidang pemotong yang didapat pada perhitungan diatas adalah

(i) ( ) ( )435 106

102

108 xxx −−−−−=

435 106

102

108 xxx ++−=

( ) ( )21215 23710645

102

108 xxxxx ++−+++−+−=

21215 1012

1018

1042

108

102

1010

108 xxxxx ++−++−−=

215 226 xxx ++−=

(ii) ( ) ( )536 61

64

64 xxx −−−−−=

536 61

64

64 xxx ++−=

( ) ( )21216 2266145

64

64 xxxxx ++−+++−+−=

21216 62

62

66

616

64

620

64 xxxxx ++−++−−=

216 35 xxx ++−=


51

Dari kendala awal dan kendala tambahan dapat digambarkan dengan grafik.

1 2 3 4 5

1

2

3

4

• • • •

•

•

•

•

•

1x

2x

3x4x 5x6x

•

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

( )( )jJ

n

jvjvv xaax −+= ∑

=10

maka pembatas sekunder yang dihasilkan adalah sebagai berikut

( )( )jJ

n

jvjvmn xffx −−−= ∑

=++

101

dengan [ ]vjvjvj aaf −= atau [ ] vjvjvj aaf −=− , nj ,,1,0 K=

maka ( )( )jJ

n

jvjvmn xffx −−−= ∑

=++

101

[ ]( ) [ ]( ) ( )( )∑=

−−−−=n

jjJvjvjvv xaaaa

100

[ ] [ ] ( )( ) ( )( )⎭⎬⎫

⎩⎨⎧

−+−⎭⎬⎫

⎩⎨⎧

−+= ∑∑==

n

jjJvjv

n

jjJvjv xaaxaa

10

10

Sekarang setiap variabel nonbasis ( )jJx adalah suatu variabel nonbasis ataupun

variabel basis pada masalah awal. Pada kasus sebelumnya diketahui ( ) gjJ xx =

untuk suatu ng ,,2,1 K= dan pada kasus selanjutnya persamaan

( ) ( )j

n

jjininjJ xaax −+= ∑

=++

1,0, untuk suatu mi ,,2,1 K= . Meskipun begitu koefisien

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 ( )jJx dapat ditulis sebagai suatu

kombinasi linear dari .,,1 nxx K Jadi suku pada ruas kanan dalam tanda kurung

pertama adalah suatu bilangan bulat bila dituliskan dalam suku-suku .,,1 nxx K


53

Suku pada ruas kanan dalam tanda kurung kedua sama dengan vx .

Variabel ini juga sebuah variabel nonbasis maupun sebagai kombinasi linear dari

variabel nonbasis .,,1 nxx K

Oleh karena itu ( )( ) 01

01 ≥−−−= ∑=

++ jJ

n

jvjvmn xffx menjadi pertaksamaan

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


Baris sumber yang akan diambil adalah baris ke-nol karena nilai 1300 −=a dan

memiliki nilai 000 =f


Pada tabel sebelumnya, untuk baris ke-nol dapat dinyatakan sebagai

( ) ( ) 1342

47

65 −≥−+− xx


54

Sehingga diperoleh ( )431

47

47

47

01 =−=⎥⎦⎤

⎢⎣⎡−=f ,

420

42

42

42

02 =−=⎥⎦⎤

⎢⎣⎡−=f

dan 000 =f . Maka persamaan pembatas sekunder yang baru adalah

( ) ( ) 042

470 657 ≥−−−−= xxx


simpleks.


1 ( )5x− ( )6x−

0x 13−

47

42

1x

2x

3x

4x

5x

6x

2

1

1

1

0

0

43

− 42

41

42

−

41

46

−

47

− 4

2

-1 0

0 -1

7x 0 43

− 42

−



55

Dari tabel koefisien 070 =a pada baris ketujuh, maka baris ketujuh dipilih

sebagai baris pivot.


Dari tabel, pada kolom kedua dilihat nilai R terkecil yakni 142

42

72

02 =−

=ac

Langkah 6 :

Menggantikan variabel non basis pada kolom pivot dengan variabel 7x .



1 ( )5x− ( )7x−

0x 13− 1 1

1x

x2

3x

4x

x5

6x

7x

2

1

1

1

0

0

0

23

− 1

1 -1

25 3−

25

− 1

-1 0

23 -2

0 -1


56

Langkah 8 :

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

ITERASI 2


Sekarang yang diambil untuk baris sumber adalah baris pertama yakni 210 =a

dan memiliki nilai 010 =f


Pada tabel sebelumnya, untuk baris pertama dapat dinyatakan sebagai

( ) ( ) 2123

75 ≥−+−− xx

sehingga diperoleh ( )212

23

23

23

01 =−−−=⎥⎦⎤

⎢⎣⎡−−−=f dan 002 =f dengan

000 =f


( ) ( ) 00210 658 ≥−+−−= xxx


simpleks.


57


1 ( )5x− ( )7x−

0x 13− 1 1

1x

x2

3x

4x

x5

6x

7x

2

1

1

1

0

0

0

23

− 1

1 -1

25 3−

25

− 1

-1 0

23 -2

0 -1

8x 0

21

− 0


Dari tabel, koefisien 080 =a pada baris kedelapan, maka baris kedelapan

dipilih sebagai baris pivot.


Dari tabel, pada kolom kesatu dilihat nilai R terkecil yakni 221

1

81

01 =−

=ac


58

Langkah 6 : Variabel 8x akan menggantikan variabel non basis pada kolom

pivot.


Tabel 3.13. Hasil setelah dilakukan operasi kolom pada iterasi 4

1 ( )8x− ( )7x−

0x 13− 2 1

1x

2x

3x

4x

5x

6x

7x

8x

2

1

1

1

0

0

0

0

-3 1

2 -1

5 3−

-5 1

-2 0

3 -2

0 -1

-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 ix pada sembarang persamaan ke-i yang merupakan

bilangan bulat maka variabel tersebut dapat dinyatakan sebagai :

( ) ( ) ( )niniiii xaxaxaax −++−+−+= K22110

atau

( )( )∑=

−+=n

jjJijii xaax

10 (4.1)

dengan )( jJ adalah elemen ke j di dalam J =(1,2,…,n),

dan 00 <ia 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

⎥⎦⎤

⎢⎣⎡−=λλaaf (4.2)


61

dengan ⎥⎦⎤

⎢⎣⎡λa adalah bilangan bulat terbesar yang kurang dari atau sama dengan

λa

maka 10 <≤ f . Didefinisikan fr λ= maka diperoleh

⎥⎦⎤

⎢⎣⎡−=λλλaar atau raa +⎥⎦

⎤⎢⎣⎡= λλ

. (4.3)

Karena 10 <≤ f dan 0>λ , maka λλ <≤ f0 atau λ<≤ r0 . Dari persamaan

(4.3) maka koefisien pada persamaan (4.1) dapat ditulis sebagai

( )njra

a ijij

ij ,...1,0=+⎥⎦

⎤⎢⎣

⎡= λ

λ (4.4)

dan r+⎥⎦⎤

⎢⎣⎡= λλ11 (4.5)

dengan λλ <≤> ijr0,0 dan λ<≤ r0 . Substitusikan persamaan (4.4) dan

(4.5) ke dalam persamaan (4.1) sehingga diperoleh

( )( )jJ

n

jij

iji

i xra

ra

rxx −⎟⎟⎠

⎞⎜⎜⎝

⎛+⎥

⎦

⎤⎢⎣

⎡++⎥⎦

⎤⎢⎣⎡=+⎥⎦

⎤⎢⎣⎡ ∑

=10

01 λλ

λλ

λλ

( )( ) ( )( )∑=

⎟⎟⎠

⎞⎜⎜⎝

⎛−+−⎥

⎦

⎤⎢⎣

⎡++⎥⎦

⎤⎢⎣⎡=

n

jjJijjJ

iji

i xrxa

ra

10

0 λλ

λλ

( )( ) ( )( )∑ ∑= =

−+−⎥⎦

⎤⎢⎣

⎡++⎥⎦

⎤⎢⎣⎡=

n

j

n

jjJijjJ

iji

i xrxa

ra

1 10

0 λλ

λλ

atau

∑ ∑= =

−⎥⎦⎤

⎢⎣⎡+−⎥

⎦

⎤⎢⎣

⎡+⎥⎦

⎤⎢⎣⎡+=+

n

jjJ

n

j

ijiijJij xx

aarrxxr

1)(

1

00)( )(1)( λ

λλ

λλ

λ

∑ ∑= = ⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧

−⎥⎦⎤

⎢⎣⎡+−⎥

⎦

⎤⎢⎣

⎡+⎥⎦

⎤⎢⎣⎡+=+

n

jjJ

n

j

ijiijJij xx

aarrxxr

1)(

1

00)( )(1)(

λλλλ (4.6)


62

Persamaan (4.6) dapat ditulis

∑=

′+=+n

jijJij xrxrxr

10)( λ (4.7)

dengan

( )( ) ( )xxaa

x jJ

n

j

j −⎥⎦⎤

⎢⎣⎡+−⎥

⎦

⎤⎢⎣

⎡+⎥⎦

⎤⎢⎣⎡= ∑

= λλλ1'

1

0 (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 λ<0ir maka ruas kanan

pesamaan (4.7) yakni xri ′+ λ0 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 11<

λ sehingga 01

=⎥⎦⎤

⎢⎣⎡λ

. Bila nilai tersebut dimasukan pada

persamaan (4.8) akan didapat

( )( ) 0'1

0 ≥−⎥⎦

⎤⎢⎣

⎡+⎥⎦

⎤⎢⎣⎡= ∑

=jJ

n

j

iji xaa

xλλ

(4.9)

Karena 00 <ia berarti 00 <⎥⎦⎤

⎢⎣⎡λia

. Tambahkan persamaan (4.9) pada tabel

simpleks dan dapat dianggap sebagai baris sumber. Untuk λ yang cukup besar

maka elemen pivot pada persamaan (4.9) yakni

10 −=⎥⎦⎤

⎢⎣⎡λia

dengan 01 0 <≤−λia

.

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 0≠v 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 )10400(1 =v

)5031(2 −−=v

)1030(3 =v

)201010(4 −=v

Maka 1v , 2v dan 3v adalah positif secara lexicographic, sedangkan 4v 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 → nααα K10

Variabel

=0x=1x

M=nx

( ) ( )nxx −− K11

naaa 00100 K 010 K− MOMM 100 −K

=+1nxM=+mnx

nnnn aaa ,11,10,1 +++ K MOMM

nmnmnmn aaa ,1,0, +++ K Keterangan :

jα : komponen 1++ mn pertama dalam kolom ke – j, yakni⎟⎟⎟

⎠

⎞

⎜⎜⎜

⎝

⎛

=

+ jmn

j

j

a

a

,

0

Mα .

3. Memilih baris sumber yang tidak layak v, yakni yang memenuhi

.0,00 ≠< vav 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α ( np ,,1K= ) yang terkecil secara lexicographic

diantara kolom-kolom yang mempunyai 0<vja dan elemen tak nol yang

pertama adalah negatif. Jika tidak ada, yakni 0≥vja ,untuk nj ,,1K= , 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 ( )njbj ,,1,0 K= , maka

kolom pivot pα dalam metode simpleks dual lexicographic memenuhi

j

jL

p

p

bb −−

ααp (4.10)

setiap j (j≠ 0) dengan 0<jb untuk setiap iterasi pada masalah program linear

bilangan bulat. Dengan pb adalah koefisien kolom pα pada baris v, yakni

1−=pb dan koefisien x pada baris v kolom ke-j adalah ⎥⎦

⎤⎢⎣

⎡λ

ija maka

⎥⎦

⎤⎢⎣

⎡=

λij

j

ab . Dengan demikian dari persamaan (4.10), kolom pivot haruslah

memenuhi

⎥⎦

⎤⎢⎣

⎡−

λij

jL

p aα

α p (4.11)

untuk setiap j (j≠ 0) dengan 0<⎥⎦

⎤⎢⎣

⎡λ

ija . Karena ⎥

⎦

⎤⎢⎣

⎡−

λija

adalah bilangan bulat

positif maka didapat

j

L

ij

jL

p aα

αα pp

⎥⎦

⎤⎢⎣

⎡−

λ

(4.12)


67

Karena λ>0, maka 0<⎥⎦

⎤⎢⎣

⎡λ

ija jika hanya jika 0<ija sehingga kolom pivot

adalah kolom terkecil secara lexicographic yang memuat sebuah elemen

negatif dalam baris sumber.

Misalkan 1=pu dan ( )pju j ≠ adalah bilangan bulat terbesar

sehingga

j

jL

p uα

α p (4.13)

Karena ju adalah bilangan bulat terbesar, persamaan (4.13) menunjukkan

bahwa

jij u

a≤⎥

⎦

⎤⎢⎣

⎡−

λ (4.14)

Nilai positif terkecil λ yang memenuhi (4.14) adalah

j

ijij u

a−=λ (4.15)

Maka untuk menjamin persamaan (4.11), atau dengan kata lain untuk

mempertahankan kolom positif secara lexicographic ( )njj ,,1K=α , maka

haruslah memiliki ≥λ maks ⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧ −

=j

ijij u

aλ .

5. Tentukan kendala bidang pemotong yang merupakan pertidaksamaan bilangan

bulat dari baris v, yakni


68

( )( ) 01

0 ≥−⎥⎦

⎤⎢⎣

⎡+⎥⎦

⎤⎢⎣⎡= ∑

=jJ

n

j

ijiv x

aax

λλ

Tambahkan kendala bidang pemotong dalam tabel, yakni pada baris paling

bawah. Kemudian dilakukan operasi kolom agar elemen-elemen pada baris vx

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 0,00 ≠< vav

dipilih yang paling minimum.

Langkah 2 :

Memilih kolom pivot pα , yakni kolom dengan koefisien vja ( )1≥j 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 0<vja ( )0≠j dan misalkan 1=pu untuk pα kolom pivot

yang dipilih dalam langkah di atas, tentukan ( )pju j ≠ , yakni bilangan

bulat terbesar yang memenuhi p

L

jju

αα f⎟⎟⎠

⎞⎜⎜⎝

⎛ 1 dengan 1≥ju dan 0L

p fα .

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

vjij u

a−=λ .

iii. Pilih λ= maks ⎪⎭

⎪⎬⎫

⎪⎩

⎪⎨⎧ −

=j

ijij u

aλ

Langkah 4 :

Menentukan bentuk kendala bidang pemotong yakni

( )( )∑=

≥−⎥⎦

⎤⎢⎣

⎡+⎥⎦

⎤⎢⎣⎡=

n

jjJ

vjvv x

aax

1

0 0λλ

Langkah 5:

Tambahkan bentuk kendala bidang pemotong yang baru ke dalam tabel

simpleks untuk menjadi baris sumber yang baru.


70

Langkah 6 :

Variabel vx pada baris sumber yang baru akan menggantikan variabel non

basis pada kolom pivot.

Langkah 7 :

Melakukan operasi kolom agar elemen-alemen pada baris vx bernilai -1

untuk elemen pada kolom pivot dan yang lainnya bernilai 0.

Langkah 8 :

Jika masih ada nilai 0,00 ≠< vav 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

Menentukan bentuk kendala bidang pemotong, yakni

( )( )∑=

≥−⎥⎦

⎤⎢⎣

⎡+⎥⎦

⎤⎢⎣⎡=

n

jjJ

vjvv x

aax

1

0 0λλ

nilai 00 <va

Pilih baris sumber v dengan 00 <va

Pilih kolom pivot pα , yakni minimum vja yang positif secara lexicographic

Menentukan nilai λ=maks ⎟⎟⎠

⎞⎜⎜⎝

⎛ −=

j

vjj u

aλ

Melakukan operasi kolom

Tambahkan bentuk kendala bidang pemotong kedalam tabel

Mengganti variabel nonbasis dengan variabel vx

YA

TIDAK

Penyelesaian sudah optimum

Selesai


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 :


Dengan kendala: 54 21 −≤−− xx ( )3x

723 21 −≤−− xx ( )4x

dan 0, 21 ≥xx

Penyelesaian :

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


Dengan kendala: 54 321 −=+−− xxx

723 421 −=+−− xxx

dan 0,,, 4321 ≥xxxx

Menyusun tabel awal simpleks

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


73

Kolom → 210 ααα

Variabel

=0x

=2x

=3x

=4x

( ) ( )211 xx −−

540

010 −

100 −

415 −−−

237 −−−

ITERASI 1

Langkah 1 : Memilih baris sumber.

Dalam tabel dilihat koefisien 740 −=a adalah nilai yang paling minimum maka

baris 4x adalah baris sumber yang dipilih.

Langkah 2 : Memilih kolom pivot.

Dalam tabel dapat diperoleh 341 −=a dan koefisien 242 −=a . Karena nilai

341 −=a 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 11 =u kemudian akan ditentukan 2u , yakni

bilangan bulat terbesar yang memenuhi 122

1 ααL

uf⎟⎟

⎠

⎞⎜⎜⎝

⎛. Dalam tabel terlihat

↓

=1x


74

bahwa komponen pertama 4α1 = dan 52 =α . Jadi 451

2

L

uf⎟⎟

⎠

⎞⎜⎜⎝

⎛ maka

nilai 2u yang akan didapat adalah 1.

ii. Lihat nilai 0<vja pada baris sumber adalah 341 −=a dan 242 −=a maka

nilai 1λ dan 2λ masing-masing adalah sebagai berikut :

313

1)3(

1

411 ==

−−=

−=

ua

λ

dan 212

1)2(

2

422 ==

−−=

−=

ua

λ

iii. Memiilih λ = maksimum ( 21,λλ )

= maksimum ( 3,2)

= 3

Langkah 4 : Menentukan bentuk kendala bidang pemotong yang baru yakni

( ) ( ) 032

33

37

215 ≥−⎥⎦⎤

⎢⎣⎡−+−⎥⎦

⎤⎢⎣⎡−+⎥⎦

⎤⎢⎣⎡−= xxx

atau

( ) ( ) 0113 215 ≥−−−−−= xxx

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


Variabel

=0x

=2x=3x=4x

( ) ( )211 xx −−

540 010 − 100 − 415 −−− 237 −−−

=5x 113 −−−

Langkah 6 : Variabel 5x akan menggantikan variabel 1x .

Langkah 7 : Melakukan operasi kolom. Sehingga tabel baru yang diperoleh

adalah



Variabel

=0x

=2x=3x=4x=5x

( ) ( )251 xx −−

1412− 113 − 100 − 312 −−− 132 − 010 −

↓

=1x

↓

=1x


76

Langkah 8 :

Karena masih ada nilai 0,00 ≠< vav , yakni 230 −=a maka dilanjutkan ke

Langkah 2.

ITERASI 2

Langkah 1 : Memilih baris sumber.

Dalam tabel dilihat koefisien 230 −=a adalah nilai yang paling minimum maka

baris 3x adalah baris sumber yang dipilih.

Langkah 2 : Memilih kolom pivot.

Dalam tabel diperoleh 131 −=a dan koefisien 332 −=a . Karena nilai 332 −=a

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 12 =u . Kemudian ditentukan 1u , yakni bilangan

bulat terbesar yang memenuhi 211

1 ααL

uf⎟⎟

⎠

⎞⎜⎜⎝

⎛. Dalam tabel terlihat bahwa

komponen pertama 41 =α dan 12 =α . Jadi 141

1

L

uf⎟⎟

⎠

⎞⎜⎜⎝

⎛ maka nilai 1u

yang akan didapat adalah 3.


77

ii. Lihat nilai 0<vja pada baris sumber adalah 131 −=a dan 332 −=a maka

diperoleh

31

3)1(

1

411 =

−−=

−=

ua

λ

dan 313

1)3(

2

422 ==

−−=

−=

ua

λ

iii. Memiilih λ = maksimum ( 21,λλ )

= maksimum ( 31 ,3)

= 3

Langkah 4 : Menentukan bentuk kendala bidang pemotong yang baru yakni

( ) ( ) 033

31

32

256 ≥−⎥⎦⎤

⎢⎣⎡−+−⎥⎦

⎤⎢⎣⎡−+⎥⎦

⎤⎢⎣⎡−= xxx

atau

( ) ( ) 0111 256 ≥−−−−−= xxx

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


Variabel

=0x

=2x=3x=4x=5x

( ) ( )251 xx −−

1412− 113 − 100 − 312 −−−

132 − 010 −

=6x 111 −−−

Langkah 6 : Variabel 6x akan menggantikan variabel 2x .

Langkah 7 : Melakukan operasi kolom. Sehingga tabel baru yang diperoleh

adalah



Variabel

=0x

=2x=3x=4x=5x=6x

( ) ( )651 xx −−

1313− 122 −

111 − 321 −

141 − 010 −

100 −

↓

=1x

↓

=1x


79

Langkah 8 :

Karena sudah tidak ada nilai 0,00 ≠< vav maka tabel sudah optimum

dengan nilai ( )21 , xx = ( )1,2 dan nilai optimum = -13

Pada masalah program linear bilangan bulat dalam bentuk dualnya dapat

diurakan bahwa dalam kendala utama yang memiliki variabel awal 1x dan 2x

adalah

54 21 −≤−− xx

723 21 −≤−− xx

Kendala bidang pemotong yang didapat pada perhitungan diatas adalah

( ) ( ) 0113 215 ≥−−−−−= xxx atau 321 −≤+ xx

dan ( ) ( ) 0111 256 ≥−−−−−= xxx

( ) ( )( )( ) ( ) 0111311 2216 ≥−−−−−−−−−−= xxxx

( ) ( ) 0214 216 ≥−−−−−= xxx atau 42 21 −≤+ xx


80

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

1 2 3 4 5

1

2

3

4

1x

2x

•

• • • • •

•

•

•

•

3x5x 6x4x

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 bi langan bulat dual skripsi

Documents