PENYELESAIAN PROGRAM LINEAR DENGAN MENGGUNAKAN ALGORITMA TITIK INTERIOR DAN METODE SIMPLEKS

PENYELESAIAN PROGRAM LINEAR DENGAN MENGGUNAKAN ALGORITMA TITIK INTERIOR DAN METODE SIMPLEKS

oleh SUPARNO M0101047

SKRIPSI ditulis dan diajukan untuk memenuhi sebagian persyaratan memperoleh gelar Sarjana Sains Matematika

FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SEBELAS MARET SURAKARTA 2009

i

SKRIPSI PENYELESAIAN PROGRAM LINEAR DENGAN MENGGUNAKAN ALGORITMA TITIK INTERIOR DAN METODE SIMPLEKS

yang disiapkan dan disusun oleh SUPARNO M0101047

dibimbing oleh Pembimbing I,

Pembimbing II,

Dra. Diari Indriati, M.Si NIP 131 805 431

Titin Sri Martini, S.Si, M.Kom

Telah dipertahankan di depan Dewan Penguji pada hari Selasa, tanggal 2 Juni 2009 dan dinyatakan telah memenuhi syarat.

Anggota Tim Penguji 1.

Tanda Tangan

Dr. Sutanto, S.Si, DEA NIP 132 149 079

2.

1. ......................

Drs. Siswanto, M.Si NIP 132 000 805

3.

2. ......................

Winita Sulandari, M.Si NIP 132 313 063

3. ......................

Surakarta, 2 Juni 2009

Disahkan oleh Fakultas Matematika dan Ilmu Pengetahuan Alam Dekan,

Ketua Jurusan Matematika,

Prof. Drs. Sutarno, M.Sc., Ph.D NIP 131 649 948

Drs. Kartiko, M.Si NIP 131 569 203

ii

ABSTRAK Suparno, 2009. PENYELESAIAN PROGRAM LINEAR DENGAN MENGGUNAKAN ALGORITMA TITIK INTERIOR DAN METODE SIMPLEKS, Fakultas Matematika dan Ilmu Pengetahuan Alam, Universitas Sebelas Maret

Program linear adalah suatu model yang melibatkan fungsi-fungsi linear dan dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber terbatas secara optimal. Pokok pikiran menggunakan program linear adalah merumuskan masalah dari informasi yang tersedia, kemudian menerjemahkannya dalam bentuk model matematika. Metode simpleks merupakan algoritma yang efisien untuk menyelesaikan permasalahan program linear. Algoritma titik interior merupakan alat baru yang dapat digunakan untuk menyelesaikan masalah-masalah yang sangat besar. Tujuan dari penulisan ini adalah menyelesaikan permasalahan program linear yang memuat n jumlah variabel dan m jumlah kendala dengan menggunakan kedua metode tersebut. Selanjutnya, ditunjukkan keefisienan algoritma titik interior dibandingkan metode simpleks, ditinjau dari banyaknya iterasi untuk menyelesaikan suatu permasalahan. Berdasarkan hasil penelitian, algoritma titik interior lebih efisien jika digunakan setidaknya 93 variabel dan tidak kurang dari 10 kendala untuk kasus maksimisasi dengan semua kendala bertanda kurang dari atau sama dengan (≤).

iii

ABSTRACT

Suparno, 2009. THE LINEAR PROGRAM SETTLEMENT USING INTERIOR POINT ALGORITHM AND SIMPLEX METHOD, Faculty of Mathematics and Natural Sciences, Sebelas Maret University Linear program is a program which involves linear functions and can be used in solving problem of limited source allocation optimally. The main ideas used in linear program is defining problem of information provided, and transforming it into mathematical model. Simplex method is one of efficient algorithm for solving problem of linear programming. Interior point algorithm is a new means which can be used to solve these great problems. The objective of this paper is solving linear programming problem which contain n variables and m constraints using those two methods, then, comparing how efficients method are, by counting the number of iterations for each methods. Based on the result of research, the interior point algorithm is more efficient if used at least 93 variables and not less than 10 constraints for the maximization case with the constraints has less than or equal sign (£).

iv

MOTTO

“Ketika anak kecil berlatih jalan, ia terjatuh lalu bangun, kemudian terjatuh lagi, bangun lagi sampai kemudian ia bisa berjalan dengan sempurna, ia tidak kenal menyerah”

“Sesungguhnya sesudah kesulitan itu ada kemudahan”

v

PERSEMBAHAN

Karya sederhana ini kupersembahkan untuk : Kedua orang tuaku dan orang-orang yang telah menanti kelulusanku

vi

KATA PENGANTAR

Puji syukur penulis panjatkan kehadirat ALLAH SWT, karena dengan rahmat dan hidayah-Nya, penulis dapat menyelesaikan penulisan skripsi ini. Skripsi ini tidak akan dapat tersusun tanpa adanya bantuan dari berbagai pihak. Pada kesempatan ini penulis ingin menyampaikan ucapan terima kasih kepada pihak yang telah membantu penulis dalam penyusunan skripsi ini, terutama kepada : 1. Ibu Dra. Diari Indriati, M.Si, selaku Pembimbing I. 2. Ibu Titin Sri Martini, S.Si, M.Kom, selaku Pembimbing II. Semua pihak yang telah membantu penulisan skripsi ini, yang tidak dapat penulis sebutkan satu persatu. Terlepas dari kekurangan yang ada dalam skripsi ini, semoga memberikan manfaat bagi para pembaca.

Surakarta, Mei 2009

Penulis

vii

DAFTAR ISI

JUDUL ………………………………………………………………………..... i PENGESAHAN ...……………………………………………………………… ii ABSTRAK ...…………………………………………………………………… iii ABSTRACT …………………………………………………………………....... iv MOTTO ...………………………………………………………………………. v PERSEMBAHAN ...…………………………………………………………..... vi KATA PENGANTAR ...……………………………………………………….. vii DAFTAR ISI ...………………………………………………………………… viii DAFTAR TABEL ...……………………………………………………………

x

DAFTAR LAMPIRAN ...……………………………………………………… xi

I. PENDAHULUAN

1

1.1 Latar Belakang Masalah ...…………………………………………….. 1 1.2 Perumusan Masalah ...…………………………………………………. 2 1.3 Batasan Masalah ...…………………………………………………….. 3 1.4 Tujuan ...……………………………………………………………….. 3 1.5 Manfaat ...……………………………………………………………… 3

II. LANDASAN TEORI

4

2.1 Tinjauan Pustaka ...…………………………………………………….. 4 2.1.1 Program Linear …..…………………………………………….... 4 2.1.2 Metode Simpleks ……………………………………...………… 6 2.2 Kerangka Pemikiran ...………………………………………………..... 9

III. METODE PENELITIAN

10

viii

IV. PEMBAHASAN

11

4.1 Algoritma Titik Interior ...…………………………………………....... 11 4.2 Beberapa Contoh Aplikasi Program Linear ……………....…………… 13 4.3 Hasil Eksperimen ...……………………………………………………. 31

V. PENUTUP

32

5.1 Kesimpulan ...………………………………………………………….. 32 5.2 Saran ...………………………………………………………………… 32

DAFTAR PUSTAKA ………………………………………………………… 33

LAMPIRAN ……………………………………………………………………. 34

ix

DAFTAR TABEL

4.1 Iterasi 1 kasus 1 ...………………………………………………………...... 14 4.2 Iterasi 2 kasus 1 ...………………………………………………………….. 14 4.3 Iterasi 3 kasus 1 ...…………………………………………………….......... 15 4.4 Hasil eksperimen ........................................................................................... 31

x

DAFTAR LAMPIRAN

Lampiran 1. Penyelesaian Kasus 2 dengan Metode Simpleks ………………… 34 Lampiran 2. Tabel Nilai Variabel dan Nilai Z pada Tiap Iterasi Kasus 2 dengan Algoritma Titik Interior ...……………………………….... 38 Lampiran 3. Tabel Nilai Variabel dan Nilai Z pada Tiap Iterasi Kasus 3 dengan Metode Simpleks dan Tabel Optimal di Iterasi ke-28 ........ 41 Lampiran 4. Tabel Nilai Variabel dan Nilai Z pada Tiap Iterasi Kasus 3 dengan Algoritma Titik Interior ...………………………………... 43

xi

BAB I PENDAHULUAN

1.1 Latar Belakang Masalah Perkembangan yang pesat di bidang ilmu dan teknologi dewasa ini menuntut adanya kemampuan manusia dalam mempertimbangkan segala kemungkinan sebelum mengambil keputusan atau tindakan. Pertimbanganpertimbangan naluriah atau dengan perkiraan-perkiraan kualitatif yang sederhana pada dasarnya hanya dapat dipertanggungjawabkan untuk keputusan-keputusan sederhana pula. Keputusan-keputusan, terutama di dunia usaha yang mengandung resiko besar tentunya perlu didukung oleh perhitungan-perhitungan yang matang agar resiko kerugian dapat dihindari. Tentu saja pada keadaan tersebut pertimbangan-pertimbangan naluriah saja tidak cukup, sehingga diperlukan peralatan-peralatan, teknik-teknik atau metode-metode kuantitatif yang lebih lengkap untuk memecahkannya. Dalam kehidupan sehari-hari banyak dijumpai permasalahan yang menginginkan suatu penyelesaian secara optimal, hal ini dapat dilihat dari usaha memaksimalkan atau meminimalkan sumber-sumber yang terbatas. Sumbersumber tersebut antara lain mesin, tenaga kerja, bahan baku, peralatan, dan lain sebagainya. Dengan alasan itulah diperkenalkan riset operasi (operation research) yang pada prinsipnya berisi teknik kuantitatif yang banyak dipakai dalam pengambilan keputusan. Riset operasi berusaha menetapkan arah tindakan terbaik (optimal) dari sebuah masalah keputusan dengan pembatasan sumber daya yang terbatas. Istilah riset operasi sering kali diasosiasikan secara eksklusif dengan penggunaan teknikteknik matematika untuk membuat model dan menganalisis masalah keputusan. Sebagai teknik pemecahan masalah, riset operasi harus dipandang sebagai ilmu dan seni. Aspek ilmu terletak dalam penyediaan teknik-teknik matematika dan algoritma untuk memecahkan masalah keputusan dengan tepat. Riset operasi

1 xii

merupakan sebuah seni karena keberhasilan dalam semua tahap sebelum dan sesudah pemecahan dari sebuah model matematika bergantung besar pada kreativitas dan kemampuan pribadi yang menganalisis pengambilan keputusan. Sebuah model keputusan semata-mata merupakan alat untuk meringkaskan sebuah masalah keputusan dengan cara yang memungkinkan identifikasi dan evaluasi yang sistematis terhadap semua alternatif keputusan dari sebuah masalah. Sebuah keputusan dicapai dengan memilih alternatif yang dinilai terbaik diantara semua pilihan yang tersedia. Menurut Bustani (2005) riset operasi merupakan metode untuk menformulasikan dan merumuskan permasalahan sehari-hari ke dalam pemodelan matematika untuk mendapatkan solusi yang optimal. Salah satu alat riset operasi yang efektif untuk menyelesaikan masalah optimasi adalah pemrograman linear. Program linear banyak digunakan untuk menyelesaikan masalah optimasi di bidang industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linear. Bentuk linear berarti bahwa seluruh fungsi dalam model ini merupakan fungsi linear. Pokok pikiran dalam menggunakan program linear adalah dengan merumuskan masalah dari informasi yang tersedia, kemudian menerjemahkannya dalam bentuk model matematika. Pada penulisan ini, dikaji tentang penyelesaian program linear dengan menggunakan algoritma titik interior (interior point) dan metode simpleks dari contoh kasus. Selanjutnya, akan dibandingkan keefisienan kedua metode tersebut ditinjau dari banyaknya iterasi untuk menyelesaikan suatu masalah.

1.2 Perumusan Masalah Berdasarkan latar belakang masalah di atas, permasalahan yang akan dibahas dalam penulisan skripsi ini adalah 1. Bagaimana membuat model matematika dari kasus program linear? 2. Bagaimana menentukan penyelesaian dari model matematika tersebut dengan menggunakan algoritma titik interior dan metode simpleks? 3. Bagaimana membandingkan keefisienan kedua metode tersebut?

xiii

1.3 Batasan Masalah Pembahasan masalah dalam skripsi ini dibatasi oleh hal-hal sebagai berikut 1. Data yang digunakan berupa bilangan bulat. 2. Variabel yang diteliti tidak lebih dari 100. 3. Keefisienan ditinjau dari banyaknya iterasi. 4. Kasus maksimisasi untuk contoh aplikasi.

1.4 Tujuan Tujuan dari penulisn skripsi ini adalah 1. dapat membangun model matematika dari kasus program linear. 2. dapat

menentukan

penyelesaian

dari

model

matematika

dengan

menggunakan algoritma titik interior dan metode simpleks. 3. dapat membandingkan keefisienan kedua metode tersebut.

1.5 Manfaat Dari penulisan skripsi ini diharapkan dapat meningkatkan pemahaman tentang algoritma titik interior dan metode simpleks untuk menyelesaikan suatu permasalahan program linear. Selain itu, hasil kajian ini diharapkan dapat digunakan sebagai salah satu alat bantu dalam studi mengenai persoalan pengalokasian sumber-sumber secara optimal.

xiv

BAB II LANDASAN TEORI

2.1 2.1.1

Tinjauan Pustaka Program Linear

Menurut Subagyo (2000) program linear adalah suatu model umum yang dapat digunakan dalam pemecahan masalah pengalokasian sumber-sumber yang terbatas secara optimal. Program linear mencakup perencanaan kegiatan-kegiatan untuk mencapai hasil yang optimal yaitu suatu hasil yang mencerminkan tercapainya sasaran tertentu yang paling baik (menurut model matematika) diantara alternatif-alternatif yang mungkin dengan menggunakan fungsi linear. Menurut Bustani (2005) dalam program linear terdapat dua macam fungsi linear sebagai berikut a. Fungsi tujuan (objective function) yaitu fungsi yang mengarahkan analis untuk mendeteksi tujuan perumusan masalah. b. Fungsi kendala/ batasan (constraint) yaitu fungsi yang mengarahkan analis untuk mengetahui sumber daya yang tersedia dan permintaan atas sumber daya tersebut. Menurut Bronson (1996) program matematika adalah model optimasi dimana tujuan dan kendala-kendalanya diberikan dalam bentuk fungsi-fungsi matematika dan hubungan fungsional. Bentuk umum program linear yang memiliki n variabel dan m kendala adalah Optimalkan : Z = f(x1,x2,……...,xn)

4 xv

Kendala : g 1 (x 1 , x 2 ,.........., x n ) ü ì b 1 g 2 (x 1 , x 2 ,.........., x n ) ïï ïï b 2 £ . ïï ïï . ý=í . ï³ ï . ï ï . . ï ï g m (x 1 , x 2 ,.........., x n )ïþ ïîb m x 1 , x 2 ......., x n ³ 0

Permasalahan pemrograman linear dalam bentuk matriks diberikan sebagai berikut Optimalkan : Z = C T X æ £ö ç ÷ AXç = ÷ B Kendala : ç ³÷ è ø X³0

Z : fungsi tujuan CT : vektor baris dari koefisien fungsi tujuan X : vektor kolom variabel yang tidak diketahui A : matriks koefisien kendala B : vektor kolom ruas kanan kendala

Bentuk umum program linear tersebut harus berada pada bentuk standar. Perubahan ke bentuk standar dengan cara sebagai berikut 1. Menambahkan variabel slack pada setiap persamaan kendala yang mengandung hubungan fungsional (≤). 2. Mengurangkan variabel surplus pada setiap persamaan kendala yang mengandung hubungan fungsional (≥). 3. Menambahkan variabel buatan pada setiap persamaan yang mengandung hubungan fungsional (≥ atau =).

xvi

Dari bentuk standar, diperoleh tambahan variabel yaitu (xn+1,xn+2,….,xn+m). Dapat didefinisikan suatu variabel baru yaitu

é x1 ù ê x ú ê 2 ú ê . ú ê ú . ú ê ~ X = ê xn ú ê ú ê x n +1 ú ê . ú ê ú ê . ú êx ú ë n +m û permasalahan program linear berubah menjadi ~

optimalkan Z = C T X harus memenuhi kendala ~

AX = B ~

X³0

2.1.2

Metode Simpleks

Program linear adalah suatu alat yang digunakan untuk menyelesaikan masalah optimasi suatu model linear dengan keterbatasan-keterbatasan sumber daya yang tersedia. Masalah program linear berkembang pesat setelah ditemukan suatu metode penyelesaian program linear yaitu metode simpleks yang dikemukakan oleh George Dantzig pada tahun 1947. Selanjutnya berbagai alat dan metode dikembangkan untuk menyelesaikan masalah program linear bahkan sampai pada masalah riset operasi seperti pemrograman dinamik, teori antrian, dan teori persediaan hingga tahun 1950an. Masalah program linear dengan dua variabel dapat diselesaikan dengan menggunakan metode grafik, tetapi untuk model-model dengan tiga variabel atau lebih metode grafik tidak praktis untuk digunakan. Dalam metode grafik diperlihatkan bahwa program linear yang optimal selalu berkaitan dengan titik ekstrim atau titik sudut dari ruang pemecahan, gagasan ini dengan tepat mengatur

xvii

pengembangan metode simpleks. Bagaimana metode simpleks mengidentifikasi titik ekstrim (titik sudut) secara aljabar? Sebagai langkah pertama, metode simpleks mengharuskan setiap batasan/ kendala ditempatkan dalam bentuk standar yang khusus dimana semua kendala diekspresikan sebagai persamaan dengan menambahkan variabel slack atau variabel surplus sebagaimana diperlukan. Dengan tidak adanya ruang pemecahan grafik untuk menuntun kearah titik optimal, maka diperlukan sebuah prosedur yang mengidentifikasi pemecahanpemecahan dasar yang menjanjikan secara cerdas. Apa yang dilakukan oleh metode simpleks adalah mengidentifikasi satu pemecahan dasar awal lalu bergerak secara sistematis ke pemecahan dasar lainnya yang memiliki potensi untuk memperbaiki nilai fungsi tujuan. Pada akhirnya, pemecahan dasar yang bersesuaian dengan nilai optimal akan diidentifikasi dan proses akan berhenti. Pada gilirannya, metode simpleks merupakan prosedur perhitungan yang berulang (iteratif) dimana setiap pengulangan (iterasi) berkaitan dengan satu pemecahan dasar. Berikut diberikan definisi-definisi yang dikutip dari buku Taha (1996) Definisi 2.1.1 Ruang pemecahan adalah daerah pemecahan/ penyelesaian yang memenuhi semua kendala. Definisi 2.1.2 Pemecahan dasar adalah titik sudut atau titik ekstrim dari ruang pemecahan. Definisi 2.1.3 Titik optimal adalah titik sudut dari ruang pemecahan yang menyebabkan nilai fungsi tujuan menjadi optimal. Definisi 2.1.4 Variabel dasar adalah variabel yang nilainya tidak nol dalam tabel simpleks, sebaliknya variabel tidak dasar adalah variabel yang bernilai nol dalam tabel simpleks. Definisi 2.1.5 Entering variable (ev) adalah variabel tidak dasar yang akan menjadi variabel dasar pada iterasi berikutnya. Definisi 2.1.6 Leaving variable (lv) adalah variabel dasar yang akan keluar menjadi variabel tidak dasar pada iterasi berikutnya.

xviii

Definisi 2.1.7 Elemen pivot adalah elemen yang merupakan irisan antara kolom masuk dan persamaan pivot. Definisi 2.1.8 Kondisi optimalitas : variabel masuk dalam maksimisasi (minimisasi) adalah variabel nondasar dengan koefisien negatif terkecil (positif terbesar) dalam persamaan tujuan Z. Definisi 2.1.9 Kondisi kelayakan : untuk masalah maksimisasi maupun minimisasi, variabel keluar adalah variabel dasar yang memiliki titik potong terkecil (rasio minimal dengan penyebut yang positif secara ketat) dalam variabel masuk. Langkah-langkah dalam metode simpleks sebagai berikut Langkah 0 : Dengan menggunakan bentuk standar, ditentukan pemecahan dasar awal yang fisibel. Langkah 1 : Dipilih ev diantara variabel nondasar dengan menggunakan kondisi optimalitas. Langkah 2 : Dipilih lv dari variabel dasar dengan menggunakan kondisi kelayakan. Langkah 3 : Ditentukan nilai variabel dasar yang baru dengan membuat ev tersebut sebagai variabel dasar sedangkan lv sebagai variabel nondasar. Kembali ke langkah 1. Setelah ev dan lv ditemukan, iterasi berikutnya ditentukan dengan metode Gauss-Jordan. Metode ini menyebabkan adanya perubahan dalam variabel dasar dengan menggunakan dua jenis perhitungan : Tipe I (persamaan pivot) Persamaan pivot baru = persamaan pivot lama dibagi elemen pivot Tipe II (untuk semua persamaan) Persamaan baru = persamaan lama dikurangi (koefisien kolom masuk dikalikan persamaan pivot baru)

xix

Menurut Bronson (1996) apabila terdapat fungsi kendala yang mempunyai hubungan fungsional (≥ atau =) maka dikerjakan dengan menggunakan metode M besar (teknik penalti), adapun aturannya sebagai berikut Setelah semua kendala linear ditranformasikan menjadi persamaan dengan memperkenalkan variabel-variabel slack dan surplus sebagaimana diperlukan, perlu ditambahkan lagi sebuah variabel baru, yang disebut variabel buatan (artificial variable) pada ruas kiri dari setiap persamaan kendala yang tidak mengandung variabel slack. Dengan demikian, tiap persamaan kendala akan mengandung variabel slack atau variabel buatan. Dalam pemecahan permasalahan optimasi, variabel-variabel buatan disertakan dalam fungsi tujuan, yaitu dengan koefisien-koefisien negatif yang sangat besar untuk kasus maksimisasi atau dengan koefisien-koefisien positif yang sangat besar untuk kasus minimisasi. Koefisien-koefisien ini dinyatakan oleh +M atau –M, dimana M dipandang sebagai sebuah bilangan positif yang sangat besar, menyatakan hukuman (yang berat) yang dikenakan dalam membuat suatu penetapan satuan pada variabelvariabel buatan. Dalam hal perhitungannya dilakukan secara manual, maka nilainilai hukuman tersebut dibiarkan saja sebagai ±M, tetapi untuk perhitungan dengan komputer, maka harus ditentukan sebuah nilai bagi M, biasanya sebuah bilangan yang tiga atau empat kali lebih besar daripada semua bilangan yang terdapat dalam program tersebut.

2.2 Kerangka Pemikiran Suatu permasalahan program linear tentang pengalokasian sumber-sumber yang terbatas secara optimal dapat diturunkan dalam bentuk model matematika dengan terlebih dahulu mendefinisikan variabel-variabel dan tujuannya. Selanjutnya, model matematika tersebut diselesaikan dengan menggunakan metode simpleks dan algoritma titik interior. Selain itu, akan dibandingkan keefisienan kedua metode tersebut ditinjau dari banyaknya iterasi.

xx

BAB III METODE PENELITIAN

Metode penelitian yang digunakan dalam penulisan skripsi ini adalah studi literatur dan eksperimen. Langkah-langkah yang dilakukan adalah 1. Mengkaji program linear, algoritma titik interior dan metode simpleks. 2. Memberikan beberapa contoh aplikasi program linear. 3. Membuat model matematika, selanjutnya menyelesaikan model tersebut dengan algoritma titik interior dan metode simpleks. 4. Aplikasi dengan software TORA sebagai pembanding. 5. Melakukan eksperimen untuk jumlah variabel dan jumlah kendala yang bervariasi. 6. Melakukan analisis hasil penyelesaian. 7. Menarik kesimpulan.

10 xxi

BAB IV PEMBAHASAN

Pada bab ini dikaji mengenai pembuatan model matematika dari contoh aplikasi program linear, penyelesaian model matematika dengan metode simpleks dan algoritma titik interior. Selanjutnya, dibandingkan keefisienan metode simpleks dan algoritma titik interior.

4.1 Algoritma Titik Interior Menurut Utama (2005) algoritma titik interior yang pertama kali diperkenalkan oleh N. Karmarkar merupakan metode untuk menyelesaikan masalah pemrograman linear. Kemudian metode ini dikembangkan oleh James A. Momoh dengan berdasarkan pada perbaikan kondisi awal sehingga dapat digunakan untuk menyelesaikan permasalahan dengan pemrograman linear maupun kuadratik. Para peneliti mengembangkan masalah-masalah program linear dengan n variabel dimana semua titik ekstrim yaitu 2n ditemukan sebelum pemecahan optimal ditemukan. Usaha-usaha untuk memperoleh prosedur yang efisien dalam perhitungan dan melintasi bagian interior dari ruang pemecahan daripada bergerak secara hati-hati di sepanjang tepi-tepinya seperti yang dilakukan oleh metode simpleks, ketika N. Karmarkar membuat algoritma polinomial waktu, tidak berhasil sampai tahun 1984. Algoritma titik interior menawarkan sebuah pandangan baru terhadap pemecahan program linear dimana iterasi dikembangkan untuk menembus interior dari ruang pemecahan. Gagasan dasar dari algoritma tititk interior adalah memulai dengan mengambil titik interior (tidak ekstrim) dalam daerah fisibel, algoritma proses optimasi menghasilkan nilai-nilai interior fisibel. Langkah paling penting dalam algoritma ini adalah titik awal dapat ditentukan dahulu, kemudian mencari solusi

11 xxii

optimal dalam interior daerah fisibel yang didefinisikan oleh kendala-kendala sampai dicapai titik optimal. Algoritma ini memiliki konsep atau pemikiran dasar sebagai berikut Konsep 1 : bergerak melalui daerah fisibel menuju suatu penyelesaian optimal. Konsep 2 : bergerak dalam arah yang meningkatkan nilai fungsi tujuan dengan tingkat kecepatan yang paling tinggi. Konsep 3 : mengubah daerah layak tersebut untuk menempatkan penyelesaian percobaan yang sekarang sedekat mungkin pada titik pusatnya dan dengan demikian memungkinkan peningkatan yang besar bilamana melaksanakan konsep 2. ~ k

Iterasi dimulai dengan suatu nilai awal ( X ) yang memungkinkan, ~

k

~ k

sedemikian sehingga AX = B dengan X

j

> 0 untuk j = 1,2,….,n+m. Algoritma

proses optimasi menghasilkan nilai-nilai interior fisibel yang berurutan yaitu ~ 1

~ 2

X ,X

~ k

~ k +1

,…….., X , X

,…..

Langkah-langkah algortima titik interior adalah ~ k

Dk+1 := diag( X j ) Ak+1 := A Dk+1 Ck+1 := Dk+1 C Pk +1 := I - A k +1 (A k +1A k +1 ) -1 A k +1 T

T

Cpk+1 := Pk+1 Ck+1 Vk+1 := abs(min(Cpk+1))

é 11 ù ê1 ú ê 2 ú α M k +1 := ê . ú + ( ) Cpk+1 ê ú Vk +1 ê . ú êë1n + m úû ~ k +1

X

:= Dk+1 Mk+1

k : jumlah iterasi I : matriks identitas

xxiii

Proses iterasi akan berhenti apabila kriteria berhenti (stopping criterion) terpenuhi yaitu ~ k +1

Masalah maksimisasi, nilai Z k +1 = C T X

~ k

£ Z k = C T X . Adapun untuk masalah

minimisasi dapat juga diselesaikan dengan algoritma ini, dengan cara membawa masalah minimisasi ke masalah maksimisasi, yaitu dengan menegatifkan fungsi tujuan masalah minimisasi.

4.2 Beberapa Contoh Aplikasi Program Linear Kasus 1 Ani dan Ima membuat kerajinan berupa tas anyaman dari rotan dan bambu. Satu tas anyaman rotan dapat diselesaikan Ani dalam waktu 2 jam, sedangkan Ima selama 1 jam. Satu tas anyaman dari bambu dapat Ani selesaikan dalam waktu 1 jam, sedangkan Ima dalam waktu 3 jam. Ani bekerja maksimal selama 10 jam/hari dan Ima bekerja maksimal selama 15 jam/hari. Apabila tas-tas tersebut dijual Rp.50.000,00 untuk tas anyaman dari rotan dan Rp.40.000,00 untuk tas anyaman dari bambu. Tentukan jumlah tas dan jenisnya sehingga didapatkan keuntungan maksimal? Anggaplah bahwa semua tas yang dibuat dapat dijual.

Tujuannya adalah memaksimalkan keuntungan (dalam rupiah). Dengan memisalkan x1 : jumlah tas anyaman dari rotan yang diproduksi dalam satu hari x2 : jumlah tas anyaman dari bambu yang diproduksi dalam satu hari Tas anyaman dari rotan diproduksi sebanyak (x1) mendatangkan keuntungan 50000x1; tas anyaman dari bambu diproduksi sebanyak (x2) mendatangkan keuntungan 40000x2. Dapat dibentuk formulasi fungsi tujuan sebagai berikut Maksimalkan: Z = 50000x1 + 40000x2 Terdapat kendala-kendala pada jumlah waktu yang tersedia untuk pembuatan tas, yang dimodelkan dengan

xxiv

2x1 + x2 ≤ 10 x1 + 3x2 ≤ 15 Semua variabel tak negatif

(1) (2)

Dengan menambahkan variabel kurang (x3, x4) pada persamaan (1) dan (2) kendala berubah menjadi 2x1 + x2 + x3 = 10 x1 + 3x2 + x4 = 15 Semua variabel tak negatif fungsi tujuan berubah menjadi Maksimalkan: Z = 50000x1 + 40000x2 + 0x3 + 0x4 A. Penyelesaian menggunakan metode simpleks Berdasarkan formulasi pada kasus 1, dibentuk tabel simpleks sebagai berikut Tabel 4.1 Iterasi 1 kasus 1 Variabel dasar Z x3 x4

x1 -50000 2 1

x2 -40000 1 3

x3

Solusi optimal

x4 0 1 0

0 0 1

0 10 15

Tabel di atas memperlihatkan bahwa nilai negatif terkecil pada baris Z terletak pada kolom x1 maka x1 sebagai ev dan kolom x1 sebagai kolom masuk. Rasio pembagian nilai kanan dengan kolom masuk terkecil adalah 5 bersesuaian dengan baris x3, maka x3 sebagai lv dan baris x3 sebagai persamaan pivot. Elemen pivot adalah 2. Dengan menggunakan metode Gauss-Jordan diperoleh hasil Tabel 4.2 Iterasi 2 kasus 1 Variabel dasar Z x1 x4

x1 0 1 0

x2 -15000 1/2 5/2

x3 25000 1/2 -1/2

x4

Solusi optimal 0 250000 0 5 1 10

Berdasarkan tabel di atas maka ev adalah x2 dan lv adalah x4. Hasil perhitungan iterasi selanjutnya sebagai berikut

xxv

Tabel 4.3 Iterasi 3 kasus 1 Variabel dasar Z x1 x2

x1

x2 0 1 0

x3 22000 3/5 -1/5

0 0 1

Solusi x4 optimal 6000 310000 -1/5 3 2/5 4

Karena semua koefisien fungsi tujuan (nilai pada baris Z) tidak ada yang bernilai negatif maka iterasi berhenti (tabel sudah optimal). Diperoleh hasil x1 = 3; x2 = 4; dengan nilai Z = 310000 Untuk mendapatkan keuntungan maksimal maka jumlah tas anyaman dari rotan yang diproduksi dalam satu hari adalah 3 dan jumlah tas anyaman dari bambu yang diproduksi dalam satu hari adalah 4 dengan keuntungan sebesar Rp.310.000,00

B. Penyelesaian menggunakan algoritma titik interior Berdasarkan formulasi pada kasus 1, diperoleh matriks é x1 ù é50000ù êx ú ê40000ú é 2 1 1 0ù é10ù ê ú ; A=ê ; X = ê 2 ú ; B = ê ú; α = 0.95 C= ú êx 3 ú ê 0 ú ë1 3 0 1 û ë15û ê ú ê ú ë 0 û ëx 4 û ~ k +1

Proses berhenti jika nilai Z(X

~ k

) £ Z(X )

Diambil titik awal pemecahan yaitu ~ 0

X = (x 1 , x 2 , x 3 , x 4 ) = (3,3,1,3) ~ 0

Z(X ) = 270000

Iterasi 1 é3 ê0 D1 = diag( X ) = ê ê0 ê ë0 A 1 = A D1 ~ 0

0 0 0ù 3 0 0úú 0 1 0ú ú 0 0 3û

xxvi

é3 ê é2 1 1 0ù ê0 =ê ú ë1 3 0 1û ê0 ê ë0 C1 = D 1 C é3 ê0 =ê ê0 ê ë0

0 0 0ù 3 0 0úú é6 3 1 0ù = 0 1 0ú êë3 9 0 3úû ú 0 0 3û

0 0 0ù é50000 ù é150000ù 3 0 0úú êê40000úú êê120000úú = 0 1 0ú ê 0 ú ê 0 ú úê ú ê ú 0 0 3û ë 0 û ë 0 û

P1 = I - A 1 (A 1A 1 ) -1 A 1 T

é1 ê0 =ê ê0 ê ë0

0 1 0 0

T

0 0 1 0

0 ù é6 0úú êê3 0ú ê1 ú ê 1 û ë0

3ù æ é6 ç ú 9úç é6 3 1 0ù êê3 0úç êë3 9 0 3úû ê1 úç ê 3ûçè ë0

-1

3ù ö ÷ 9úú ÷ é6 3 1 0ù 0ú ÷ êë3 9 0 3úû ú÷ 3û ÷ø

é 19/281 - 21/281 - 51/281 44/281 ù ê- 21/281 38/281 12/281 - 93/281ú ú =ê ê - 51/281 12/281 270/281 15/281 ú ê ú ë 44/281 - 93/281 15/281 235/281û

Cp1 = P1C1 é 19/281 - 21/281 - 51/281 44/281 ù é150000ù ê- 21/281 38/281 12/281 - 93/281ú ê120000ú úê ú =ê ê- 51/281 12/281 270/281 15/281 ú ê 0 ú ê úê ú ë 44/281 - 93/281 15/281 235/281û ë 0 û é 62242/53 ù ê 145516/29 ú ú =ê ê- 309395/14ú ê ú ë - 64911/4 û

V1 = abs(min(Cp1 )) = 309395/14 é1ù ê1ú α M1 = ê ú + Cp1 ê1ú V1 êú ë1û

xxvii

é1ù é 62243/53 ù é 978/931 ù ê1ú ê 145516/29 ú ê1657/1363ú 0,95 ê ú ê ú=ê ú = + ê1ú 309395/14 ê- 309395/14ú ê 1/20 ú êú ê ú ê ú ë1û ë - 64911/4 û ë 313/1035 û ~ 1

X = D1 M 1 é3 ê0 =ê ê0 ê ë0

0 0 0ù é 978/931 ù é 1415/449 ù 3 0 0úú êê1657/1363úú êê5033/1380úú = 0 1 0ú ê 1/20 ú ê 1/20 ú úê ú ê ú 0 0 3û ë 313/1035 û ë 313/345 û

~ 1

Z(X ) = 606913/2 ~ 1

~ 0

Karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 2 0 0 0 ù é1415/449 ê 0 5033/1380 0 0 úú ê D2 = ê 0 0 1/20 0 ú ê ú 0 0 0 313/345û ë A2 = A D2

0 0 0 ù é1415/449 ê 0 5033/1380 0 0 úú é 2 1 1 0ù ê =ê ú 0 0 1/20 0 ú ë1 3 0 1 û ê ê ú 0 0 0 313/345û ë 0 ù é1519/241 5033/1380 1/20 =ê 0 313/345úû ë1415/449 5033/460 C2 = D2 C

0 0 0 é1415/449 ù é50000 ù é315145/2ù ê ú ê40000ú ê 145884 ú 0 5033/1380 0 0 úê ú=ê ú =ê ê úê 0 ú ê ú 0 0 1 / 20 0 0 ê úê ú ê ú 0 0 0 313 / 345û ë 0 û ë 0 ë û

P2 = I - A 2 (A 2 A 2 ) -1 A 2 T

T

xxviii

é 60/17849 - 183/32221 - 191/20165 1598/28125ù ê - 183/32221 65/6647 39/14656 - 317/3228 úú ê = ê- 191/20165 39/14656 10259/10260 25/30859 ú ê ú 25/30859 227/230 û ë1598/28125 - 317/3228 é- 33772/113ù ê 13291/25 ú ú Cp 2 = P2C 2 = ê ê - 36442/33 ú ê ú ë - 42987/8 û

V2 = abs(min(Cp2 )) = 42987/8 é1ù é1201/1268ù ê1ú ê1548/1415ú α ê ú ú M2 = + Cp 2 = ê ê1ú V2 ê 169/210 ú êú ê ú ë1û ë 1/20 û é 2773/929ù ê 395/99 ú 2 ~ ú X = D2 M 2 = ê ê169/4200 ú ê ú ë313/6900 û ~ 2

Z(X ) = 617685/2 ~ 2

~1

Karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 3 0 0 0 é 2773/929 ù ê ú 0 395/99 0 0 ú D3 = ê ê ú 0 0 169/4200 0 ê ú 0 0 0 313/6900û ë 0 é3367/564 395/99 169/4200 ù A3 = ê 0 313/6900úû ë2773/929 395/33 é298493/2ù ê 159596 ú ú C3 = ê ê ú 0 ê ú 0 ë û

xxix

- 5/165929 - 82/10139 61/20072 ù é 5/66978 ê- 5/165929 5/202033 78/38677 - 151/33205 úú ê P3 = ê 61/20072 78/38677 14391/14392 1/29627 ú ê ú 1/29627 33424/33425û ë 61/20072 - 151/33205 é 2001/316 ù ê - 737/1346 ú ú Cp 3 = ê ê - 23900/27 ú ê ú ë- 12521/46 û

V3 = 23900/27 é1037/1030ù ê1701/1702ú ú M3 = ê ê 1/20 ú ê ú ë 899/1270 û é2305/767 ù ê 2564/643ú 3 ~ ú X =ê ê 24/11929 ú ê ú ë 211/6571û ~3

Z(X ) = 309763 ~ 3

~ 2

Karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 4 menghasilkan é 4817/1606 ù ê12207/3052ú ú X =ê ê 47/29883 ú ê ú ë 32/19931 û ~ 4

~ 4

Z(X ) = 309956 ~ 4

~ 3

Karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 5 menghasilkan é15874/5291ù ê 8759/2190 ú ú X =ê ê 6/76297 ú ê ú ë 16/13549 û ~ 5

xxx

~ 5

Z(X ) = 309991 ~ 5

~ 4

karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 6 menghasilkan é122798/40933 ù ê346667/86667 ú ú X =ê ê 5/82784 ú ê ú ë 4/67745 û ~ 6

~ 6

Z(X ) = 929995/3 ~ 6

~ 5

karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 7 menghasilkan é428203/142734ù ê 234851/58713 ú ~ 7 ú X =ê ê 1/331136 ú ê ú ë 38/861879 û ~ 7

Z(X ) = 929999/3 ~ 7

~ 6

karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 8 menghasilkan 3 é ù ê ú 4 ú X =ê ê1/434898ú ê ú ë2/907241û ~ 8

~ 8

Z(X ) = 310000 ~ 8

~ 7

karena nilai Z(X ) ³ Z(X ) maka dilakukan iterasi selanjutnya Iterasi 9 menghasilkan 3 é ù ê ú 4 ê ú X = ê1/8697961ú ê ú ë 1/603538 û ~ 9

~ 9

Z(X ) = 310000

xxxi

~ 9

~ 8

Ternyata nilai Z(X ) £ Z(X ) dan kriteria pemberhentian terpenuhi maka iterasi berhenti. Diperoleh hasil x1 = 3; x2 = 4; dengan nilai Z = 310000 Untuk mendapatkan keuntungan maksimal maka jumlah tas anyaman dari rotan yang diproduksi dalam satu hari adalah 3 dan jumlah tas anyaman dari bambu yang diproduksi dalam satu hari adalah 4 dengan keuntungan sebesar Rp.310.000,00 Kasus 2 Sebuah perusahaan penyulingan minyak Aztec Refining Company memproduksi dua jenis minyak bensin, biasa dan premium yang tidak mengandung timah hitam. Kedua jenis minyak bensin ini dijual ke stasiun-stasiun servisnya dengan harga masing-masing $12/barel dan $14/barel. Keduanya dicampurkan dengan minyak sulingan dalam negeri dan luar negeri dan harus memenuhi spesifikasi-spesifikasi sebagai berikut Tekanan Kadar Permintaan Penawaran Uap Oktan Maksimal Minimal Maksimal Minimal (barel/ minggu) (barel/ minggu) 23 88 100000 50000

Biasa Premium

23

93

20000

5000

Ciri-ciri dari berbagai minyak sulingan dalam persediaan sebagai berikut

Dalam negeri

Tekanan Kadar Investasi Biaya Uap Oktan (barel) $/bbl 25 87 40000 8

Luar negeri

15

98

60000

15

Berapakah banyaknya jumlah dari kedua minyak sulingan di atas yang harus dicampurkan oleh perusahaan Aztec ke dalam kedua jenis bensin di atas agar keuntungan mingguannya maksimal?

Misalkan x1 : jumlah minyak dalam negeri yang dicampurkan ke dalam bensin biasa x2 : jumlah minyak luar negeri yang dicampurkan ke dalam bensin biasa

xxxii

x3 : jumlah minyak dalam negeri yang dicampurkan ke dalam bensin premium x4 : jumlah minyak luar negeri yang dicampurkan ke dalam bensin premium Bensin biasa akan diproduksi sebanyak (x1 + x2) yang akan mendatangkan pendapatan sebesar 12(x1 + x2); bensin premium akan diproduksi sebanyak (x3 + x4) yang akan mendatangkan pendapatan sebesar 14(x3 + x4). Minyak dalam negeri akan digunakan (x1 + x3) yang menghabiskan biaya sebesar 8(x1 + x3); minyak luar negeri akan digunakan (x2 + x4) yang menghabiskan biaya sebesar 15(x2 + x4). Keuntungan total Z adalah pendapatan dikurangi biaya pengeluaran. Jadi fungsi tujuannya adalah Maksimalkan: Z = 12(x1 + x2) + 14(x3 + x4) - 8(x1 + x3) - 15(x2 + x4) = 4x1 – 3x2 + 6x3 – x4

(1)

Terhadap produksi ini dikenakan pembatasan-pembatasan karena permintaan, tersedianya suplai dan rincian-rincian campuran. Pembatasan yang ditinjau dari segi permintaan (dalam ribuan) adalah x1 + x2 ≤ 100

(permintaan maksimal untuk bensin biasa)

(2)

x3 + x4 ≤ 20

(permintaan maksimal untuk bensin premium)

(3)

x1 + x2 ≥ 50

(jumlah minimal bensin biasa yang disyaratkan)

(4)

x3 + x4 ≥

(jumlah minimal bensin premium yang disyaratkan)

(5)

5

Pembatasan yang ditinjau dari segi persediaan (dalam ribuan) adalah x1 + x3 ≤ 40

(minyak dalam negeri)

(6)

x2 + x4 ≤ 60

(minyak luar negeri)

(7)

Unsur-unsur pokok dari suatu campuran menyumbang pada keseluruhan kadar oktan sesuai dengan unsur persentase beratnya masing-masing, demikian pula untuk tekanan uap. Kadar oktan dari bensin biasa adalah

87

x1 x2 + 98 x1 + x 2 x1 + x 2

Persyaratan kadar ini harus sekurang-kurangnya 88, maka memberikan hasil

87

x1 x2 + 98 ³ 88 x1 + x 2 x1 + x 2

xxxiii

atau x1 - 10x2 ≤ 0

(8)

Dengan cara yang sama, diperoleh 6x3 - 5x4 ≤ 0

(kendala oktan bensin premium)

(9)

2x1 - 8x2 ≤ 0

(kendala tekanan uap bensin biasa)

(10)

2x3 - 8x4 ≤ 0

(kendala tekanan uap bensin premium)

(11)

Dengan menggabungkan (1) hingga (11), maka diperoleh program matematika sebagai berikut Maksimalkan : Z = 4x1 – 3x2 + 6x3 – x4 dengan kendala : x1

+ x2 x3

x1

+ x3 x2

x1

+ x4

- 10x2 6x3

2x1

- 5x4

- 8x2 2x3

x1

+ x4

- 8x4

+ x2 x3

+ x4

≤

100

(12)

≤

20

(13)

≤

40

(14)

≤

60

(15)

≤

0

(16)

≤

0

(17)

≤

0

(18)

≤

0

(19)

≥

50

(20)

≥

5

(21)

Semua variabel tak negatif

Dengan mengurangkan variabel surplus (x5, x6) pada persamaan kendala (20), (21) dan menambahkan variabel slack (x7, x8,….....,x14) pada persamaan kendala (12), (13),…….,(19) dan menambahkan variabel buatan (x15, x16) pada persamaan kendala (20), (21) fungsi kendala berubah menjadi x1 + x2 + x7

= 100

x3 + x4 + x8

= 20

x1 + x3 + x9

= 40

xxxiv

x2 + x4 + x10

= 60

x1 - 10x2 + x11

=0

6x3 - 5x4 + x12

=0

2x1 - 8x2 + x13

=0

2x3 - 8x4 + x14

=0

x1 + x2 – x5 + x15 = 50 x3 + x4 – x6 + x16

=5

Fungsi tujuannya menjadi Maksimalkan Z = 4x1 – 3x2 + 6x3 – x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 + 0x12 + 0x13 + 0x14 - Mx15 - Mx16 Setelah mengembangkan pemecahan yang fisibel, harus mengkondisikan masalah tersebut sehingga ketika menempatkannya dalam bentuk tabel, kolom sisi kanan akan memberikan pemecahan awal secara langsung. Ini dilakukan dengan menggunakan persamaan batasan untuk mensubtitusikan keluar x15 dan x16 dalam fungsi tujuan x15 = 50 – x1 – x2 + x5 x16 = 5 – x3 – x4 + x6 Fungsi tujuan berubah menjadi Z = 4x1 – 3x2 + 6x3 – x4 + 0x5 + 0x6 + 0x7 + 0x8 + 0x9 + 0x10 + 0x11 + 0x12 + 0x13 + 0x14 – M(50 – x1 – x2 + x5) – M(5 – x3 – x4 + x6) = (4+M)x1 – (-3+M)x2 + (6+M)x3 – (-1+M)x4 – Mx5 – Mx6 – 55M A. Diselesaikan dengan metode simpleks Berdasarkan

formulasi

pada

kasus

2,

langkah-langkah

penyelesaian

menggunakan metode simpleks (ada sebanyak 7 iterasi) diberikan pada Lampiran 1.

Karena baris Z pada iterasi 7 tidak mengandung nilai negatif maka iterasi berhenti. Diperoleh hasil x1 = 37727,3; x2 = 12272,7; x3 = 2272,7; x4 = 2727,3; dengan nilai Z = 125000

xxxv

Perusahaan Aztec akan menghasilkan x1* + x2* = 50000 barel minyak bensin biasa yang memiliki tekanan uap 22,5 dengan kadar oktan 89,7. Perusahaan akan menghasilkan x3* + x4* = 5000 barel minyak bensin premium yang memiliki tekanan uap 19,5 dan kadar oktan sebesar 93,0. Untuk melakukan usahanya, perusahaan Aztec tersebut akan menggunakan x1* + x3* = 40000 barel dari investasi dalam negeri dan x2* + x4* = 15000 barel dari investasi luar negeri. B. Diselesaikan dengan algoritma titik interior Fungsi tujuan pada kasus 2 adalah Z = (4+M)X1 – (-3+M)X2 + (6+M)X3 – (-1+M)X4 – MX5 – MX6 – 55M Nilai M adalah suatu konstanta yang sangat besar, diambil nilai M = 1000 Berdasarkan model di atas didapatkan matriks é 1004 ù ê 997 ú ê ú ê 1006 ú ê ú ê 999 ú ê- 1000ú ê ú ê- 1000ú ê 0 ú ê ú ê 0 ú C=ê 0 ú ê ú ê 0 ú ê ú ê 0 ú ê 0 ú ê ú ê 0 ú ê 0 ú ê ú ê 0 ú ê 0 ú ë û

xxxvi

1 é1 ê0 0 ê ê1 0 ê 1 ê0 ê1 - 10 A=ê 0 ê0 ê2 - 8 ê 0 ê0 ê1 1 ê êë0 0

1 0 0 0 0 0 0 0 0 0ù 1 1 0 0 0 1 0 0 0 0 0 0 0 0úú 1 0 0 0 0 0 1 0 0 0 0 0 0 0ú ú 0 1 0 0 0 0 0 1 0 0 0 0 0 0ú 0 0 0 0 0 0 0 0 1 0 0 0 0 0ú ú 6 -5 0 0 0 0 0 0 0 1 0 0 0 0ú 0 0 0 0 0 0 0 0 0 0 1 0 0 0ú ú 2 -8 0 0 0 0 0 0 0 0 0 1 0 0ú 0 0 - 1 0 0 0 0 0 0 0 0 0 1 0ú ú 1 1 0 - 1 0 0 0 0 0 0 0 0 0 1úû 0

0

0

0

Diambil titik awal yaitu é 30 ù ê 50 ú ê ú ê 5 ú ê ú ê 7 ú ê 40 ú ê ú ê 10 ú ê 20 ú ê ú ~ 0 ê 8 ú X =ê 5 ú ê ú ê 3 ú ê ú ê470ú ê 5 ú ê ú ê340 ú ê 46 ú ê ú ê 10 ú ê 3 ú ë û ~ 0

Z(X ) = -55989 ~ k +1

Iterasi berhenti jika nilai Z(X

~ k

) £ Z(X )

Langkah-langkah penyelesaian menggunakan algoritma titik interior (ada sebanyak 15 iterasi) diberikan pada Lampiran 2.

xxxvii

~ 15

~ 14

Karena pada iterasi 15 nilai Z(X ) £ Z(X ) maka kriteria pemberhentian terpenuhi. Diperoleh hasil x1 = 38123; x2 =11877,6; x3 = 1876,7; x4 = 3124,6; dengan nilai Z = 125005,9 Perusahaan Aztec akan menghasilkan x1* + x2* = 50000,6 barel minyak bensin biasa yang memiliki tekanan uap 22,6 dengan kadar oktan 89,6. perusahaan akan menghasilkan x3* + x4* = 5001,3 barel minyak bensin premium yang memiliki tekanan uap 18,8 dan kadar oktan sebesar 93,9. Untuk melakukan usahanyanya, perusahaan Aztec akan menggunakan x1* + x3* = 39999,7 barel dari investasi dalam negeri dan x2* + x4* = 15002,2 barel dari investasi luar negeri. Kasus 3 Diberikan suatu permasalahan program linear yang memuat 93 variabel dan 10 kendala untuk kasus maksimisasi dengan semua kendala bertanda kurang dari atau sama dengan, sebagai berikut Maksimalkan : Z = 15x1 + 2x2 + 3x3 + 4x4 + 16x5 + 6x6 + 7x7 + 20x8 + 7x9 - 3x10 + x11 + 2x12 + 3x13 + 4x14 + 5x15 + 6x16 + 7x17 + 8x18 + 26x19 - 6x20 + x21 + 2x22 + 3x23 + 4x24 + 5x25 + 6x26 + 7x27 + 8x28 + 9x29 - 9x30 + x31 + 2x32 + 3x33 + 4x34 + 5x35 + 6x36 + 7x37 + 8x38 + 9x39 - 12x40 + x41 + 2x42 + 3x43 + 4x44 + 75x45 + 20x46 + 7x47 + 8x48 + 9x49 - 3x50 + x51 + 2x52 + 3x53 + 4x54 + 5x55 + 6x56 + 7x57 + 8x58 + 9x59 - 6x60 + 55x61 + 2x62 + 20x63 + 4x64 + 5x65 + 6x66 + 7x67 + 8x68 + 9x69 - 9x70 + x71 + 2x72 + 3x73 + 30x74 + 12x75 + 6x76 + 7x77 + 8x78 + 9x79 - 6x80 + x81 + 2x82 + 3x83 + 4x84 + 5x85 + 6x86 + 2x87 + 8x88 + 9x89 - 3x90 + x91 + 2x92 + 3x93 dengan kendala: 2x1 + x2 + 3x3 + 2x4 - 2x5 + x6 + 2x7 + 3x8 + 6x9 + 4x10 + 2x14 + 25x16 + 25x24 + x25 + 26x26 + 20x35 + 5x43 + 3x44 + 2x46 + 2x47 + 5x48 + 20x49 + 3x50 + 20x54 + 25x74 + 4x90 + 5x91 + 2x92 ≤ 500

(1)

2x4 + 3x6 - x7 + 2x10 + x11 + 2x12 + 5x13 + 6x14 + 2x15 + 3x16 + 4x17 + 6x18 + 5x19 -2x20 + 6x45 + 3x57 + 3x59 + 3x61 + 3x75 + 2x92 ≤ 160

xxxviii

(2)

2x1 + 2x7 + 2x9 + 3x11 + 2x13 + 2x15 + 3x18 + x20 + 2x21 + 3x22 + 4x23 - 3x24 + x25 - 2x26 + 3x27 + 4x28 + 2x29 + x30 + 6x42 - 3x45 + 6x58 + 5x60 + 5x62 + 7x64 + 6x76 - 6x77 + 5x86 ≤ 170

(3)

2x2 + 2x5 + 4x8 + 5x19 + 2x29 + x31 + 2x32 + 3x33 - 3x34 - 2x35 - x36 + 4x37 + 2x38 + 3x39 - 2x40 + 6x45 - 6x57 + 2x61 + 4x63 + 3x75 + 5x77 + 3x79 + 2x86

≤ 150

(4)

x4 + 3x5 + 2x6 + 3x8 + 2x11 + x12 + 2x19 - 2x24 + 2x26 + x40 + 2x41 + 3x42 - 2x43 + 3x44 + 2x45 + x46 - 2x47 + 3x48 + 2x49 + 3x50 + 3x57 + 4x58 + 6x62 + 6x64 + 5x75 + 6x76 + 4x77 + 5x78 - 5x79 + 4x87 ≤ 260

(5)

3x1 - 2x4 + x5 + 3x7 + 2x9 + 2x10 + 3x12 + x17 + 2x27 + x30 + 2x32 + 2x34 + 6x45 - 2x49 + 4x51 + x52 + 2x53 - x54 + 3x55 + 2x56 + 4x57 + 5x58 - 3x59 + 2x60 + 3x61 + 4x75 + 3x77 + 4x78 - 6x79 - 2x87 ≤ 280

(6)

- x1 + 2x3 + 1x6 + 3x7 + 5x8 + 3x10 + 3x19 +3x24 + 3x28 - 2x35 + 3x36 + 3x37 + 8x38 + 5x42 - 2x45 +x59 + 3x60 + 2x61 - x62 - 3x63 + 2x64 + 2x65 + 1x66 + 3x67 + 4x68 - x69 + 2x70 + 5x76 ≤ 295

(7)

2x1 + x2 + 3x4 + 2x8 + 5x17 + 5x23 + 6x25 - 3x26 + 3x29 + 2x31 + 2x37 + 5x38 + 3x41 + 5x45 + 5x69 + 2x71 + x72 + 3x73 - 2x74 + x75 + 3x76 + 5x77 + x78 - 2x79 + 3x80 + 2x87 ≤ 265

(8)

2x2 + x3 + 3x4 - 1x5 + 4x8 - 2x16 + 5x19 - 4x21 + 5x22 + 2x34 + 3x35 + 6x40 + 2x42 + 5x45 + 3x57 + 3x58 + 3x60 + 6x62 + 5x78 + 6x79 - 2x80 + 2x81 + 6x82 + x83 + 3x84 + 4x85 + 2x86 + 1x87 + 3x88 + 2x89 + 3x90 ≤ 1000

(9)

2x1 + 3x3 + 5x5 - 4x7 + 7x41 + 2x45 + 4x59 + 6x60 + 4x61 + x63 + 6x64 + 3x75 -6x76 - 2x89 + 3x90 + x91 + 5x92 + 2x93 ≤ 990

(10)

Semua variabel tak negatif Dengan menambahkan variabel slack (x94, x95, x96,........., x103) pada persamaan (1), (2), (3),..........,(10)

xxxix

kendala berubah menjadi 2x1 + x2 + 3x3 + 2x4 - 2x5 + x6 + 2x7 + 3x8 + 6x9 + 4x10 + 2x14 + 25x16 + 25x24 + x25 + 26x26 + 20x35 + 5x43 + 3x44 + 2x46 + 2x47 + 5x48 + 20x49 + 3x50 + 20x54 + 25x74 + 4x90 + 5x91 + 2x92 + x94 = 500 2x4 + 3x6 - x7 + 2x10 + x11 + 2x12 + 5x13 + 6x14 + 2x15 + 3x16 + 4x17 + 6x18 + 5x19 -2x20 + 6x45 + 3x57 + 3x59 + 3x61 + 3x75 + 2x92 + x95 = 160 2x1 + 2x7 + 2x9 + 3x11 + 2x13 + 2x15 + 3x18 + x20 + 2x21 + 3x22 + 4x23 - 3x24 + x25 - 2x26 + 3x27 + 4x28 + 2x29 + x30 + 6x42 - 3x45 + 6x58 + 5x60 + 5x62 + 7x64 + 6x76 - 6x77 + 5x86 + x96 = 170 2x2 + 2x5 + 4x8 + 5x19 + 2x29 + x31 + 2x32 + 3x33 - 3x34 - 2x35 - x36 + 4x37 + 2x38 + 3x39 - 2x40 + 6x45 - 6x57 + 2x61 + 4x63 + 3x75 + 5x77 + 3x79 + 2x86 + x97 = 150 x4 + 3x5 + 2x6 + 3x8 + 2x11 + x12 + 2x19 - 2x24 + 2x26 + x40 + 2x41 + 3x42 - 2x43 + 3x44 + 2x45 + x46 - 2x47 + 3x48 + 2x49 + 3x50 + 3x57 + 4x58 + 6x62 + 6x64 + 5x75 + 6x76 + 4x77 + 5x78 - 5x79 + 4x87 + x98 = 260 3x1 - 2x4 + x5 + 3x7 + 2x9 + 2x10 + 3x12 + x17 + 2x27 + x30 + 2x32 + 2x34 + 6x45 - 2x49 + 4x51 + x52 + 2x53 - x54 + 3x55 + 2x56 + 4x57 + 5x58 - 3x59 + 2x60 + 3x61 + 4x75 + 3x77 + 4x78 - 6x79 - 2x87 + x99 = 280 - x1 + 2x3 + x6 + 3x7 + 5x8 + 3x10 + 3x19 +3x24 + 3x28 - 2x35 + 3x36 + 3x37 + 8x38 + 5x42 - 2x45 +x59 + 3x60 + 2x61 - x62 - 3x63 + 2x64 + 2x65 + x66 + 3x67 + 4x68 - x69 + 2x70 + 5x76 + x100 = 295 2x1 + x2 + 3x4 + 2x8 + 5x17 + 5x23 + 6x25 - 3x26 + 3x29 + 2x31 + 2x37 + 5x38 + 3x41 + 5x45 + 5x69 + 2x71 + x72 + 3x73 - 2x74 + x75 + 3x76 + 5x77 + x78 - 2x79 + 3x80 + 2x87 + x101 = 265 2x2 + x3 + 3x4 - x5 + 4x8 - 2x16 + 5x19 - 4x21 + 5x22 + 2x34 + 3x35 + 6x40 + 2x42 + 5x45 + 3x57 + 3x58 + 3x60 + 6x62 + 5x78 + 6x79 - 2x80 + 2x81 + 6x82 + x83 + 3x84 + 4x85 + 2x86 + x87 + 3x88 + 2x89 + 3x90 + x102 = 1000

xl

2x1 + 3x3 + 5x5 - 4x7 + 7x41 + 2x45 + 4x59 + 6x60 + 4x61 + x63 + 6x64 + 3x75 -6x76 - 2x89 + 3x90 + x91 + 5x92 + 2x93 + x103 = 990 Semua variabel tak negatif Fungsi tujuan berubah menjadi Z = 15x1 + 2x2 + 3x3 + 4x4 + 16x5 + 6x6 + 7x7 + 20x8 + 7x9 - 3x10 + x11 + 2x12 + 3x13 + 4x14 + 5x15 + 6x16 + 7x17 + 8x18 + 26x19 - 6x20 + x21 + 2x22 + 3x23 + 4x24 + 5x25 + 6x26 + 7x27 + 8x28 + 9x29 - 9x30 + x31 + 2x32 + 3x33 + 4x34 + 5x35 + 6x36 + 7x37 + 8x38 + 9x39 - 12x40 + x41 + 2x42 + 3x43 + 4x44 + 75x45 + 20x46 + 7x47 + 8x48 + 9x49 - 3x50 + x51 + 2x52 + 3x53 + 4x54 + 5x55 + 6x56 + 7x57 + 8x58 + 9x59 - 6x60 + 55x61 + 2x62 + 20x63 + 4x64 + 5x65 + 6x66 + 7x67 + 8x68 + 9x69 - 9x70 + x71 + 2x72 + 3x73 + 30x74 + 12x75 + 6x76 + 7x77 + 8x78 + 9x79 - 6x80 + x81 + 2x82 + 3x83 + 4x84 + 5x85 + 6x86 + 2x87 + 8x88 + 9x89 - 3x90 + x91 + 2x92 + 3x93 + 0x94 + 0x95 + 0x96 + 0x97 + 0x98 + 0x99 + 0x100 + 0x101 + 0x102 + 0x103 A. Diselesaikan dengan metode simpleks Berdasarkan formulasi permasalahan di atas, langkah-langkah penyelesaian menggunakan metode simpleks (ada sebanyak 28 iterasi) diberikan pada Lampiran 3. Karena baris Z pada iterasi 28 tidak mengandung nilai negatif maka iterasi berhenti. Diperoleh hasil x5 = 204,05; x21 = 603,36; x34 = 757,19; x46 = 454,05; x59 = 53,33; x63 = 62,79; x66 = 430,03; x77 = 172,79; x79 = 299,46; x89 = 153,17; untuk variabel lainnya bernilai nol; dengan nilai Z = 25576,83 B. Diselesaikan dengan algoritma titik interior ~ k +1

Proses berhenti jika nilai Z(X

~ k

) £ Z(X )

Berdasarkan formulasi pada kasus 3, langkah-langkah penyelesaian dengan menggunakan algoritma titik interior (ada sebanyak 24 iterasi) diberikan pada Lampiran 4.

xli

~ 24

~ 23

Karena pada iterasi 24 nilai Z(X ) £ Z(X ) maka kriteria pemberhentian terpenuhi. Diperoleh hasil x5 = 115,9; x21 = 854; x34 = 432,8; x46 = 365,3; x59 = 50,6; x63 = 236,7; x66 = 1042,2; x69 = 89; x79 = 92,7; x89 = 14,6; untuk variabel lainnya bernilai nol; dengan nilai Z = 24216.

4.3 Hasil Eksperimen Untuk menunjukkan keefisienan algoritma titik interior, dilakukan 13 percobaan tentang hubungan jumlah variabel dan jumlah kendala dikaitkan dengan jumlah iterasi, diperoleh hasil sebagai berikut Tabel 4.4 Hasil eksperimen Jumlah Iterasi Jumlah Variabel

Jumlah Kendala

Simpleks

Titik Interior

100

10

28

25

99

10

28

25

98

10

28

25

95

10

28

25

94

10

28

25

93

10

28

24

92

10

28

38

90

10

28

39

93

9

23

35

93

11

31

25

93

12

31

25

2

2

3

9

4

10

7

15

Berdasarkan tabel di atas, algoritma titik interior akan efisien dibandingkan metode simpleks jika digunakan variabel setidaknya 93 dan kendala tidak kurang dari 10 untuk kasus maksimisasi dan semua kendala bertanda ≤.

xlii

BAB V PENUTUP

5.1

Kesimpulan

Berdasarkan pembahasan, diperoleh kesimpulan sebagai berikut 1. Algoritma titik interior dan metode simpleks dapat digunakan untuk menyelesaikan permasalahan program linear. 2. Algoritma titik interior lebih efisien dibandingkan metode simpleks jika suatu permasalahan program linear memuat setidaknya 93 variabel dengan kendala tidak kurang dari 10 untuk kasus maksimisasi dan semua kendala bertanda ≤.

5.2

Saran

Dalam penulisan skripsi ini, telah dilakukan 13 percobaan untuk menunjukkan keefisienan algoritma titik interior. Untuk pembahasan lebih lanjut, perlu dilakukan lebih banyak percobaan supaya diperoleh kesimpulan umum tentang keefisienan algoritma titik interior.

32 xliii

DAFTAR PUSTAKA

Bronson, R. Alih Bahasa : Hans J. Waspakrik. (1996). Teori dan Soal-Soal Operations Research. Erlangga. Jakarta. Bustani, H. (2005). Fundamental Operation Research. PT Gramedia Pustaka Utama. Jakarta. Hiller, F.S, and Lieberman, G.J (1990). Introduction to Operation Research. McGraw-Hill, Inc. Singapore. Subagyo, P. (2000). Dasar-Dasar Operation Research. BPFE-Yogyakarta. Taha, H.A. (1996). Riset Operasi : Suatu Pengantar. Binapura Aksara. Jakarta. Utama, S. (2005). Aplikasi Metode Ekstended Quadratic Interior Point (EQIP) untuk economic Dispatch Pembangkit Termal Bali. Universitas Udayana. Bali.

33 xliv

LAMPIRAN 1 Penyelesaian Kasus 2 dengan Metode Simpleks Iterasi 1 Variabel dasar Z x7 x8 x9 x10 x11 x12 x13 x14 x15 x16

x1 -4-M 1 0 1 0 1 0 2 0 1 0

x2 3-M 1 0 0 1 -10 0 -8 0 1 0

x3 -6-M 0 1 1 0 0 6 0 2 0 1

x1 -4-M 1 0 1 0 1 0 2 0 1 0

x2 3-M 1 0 0 1 -10 0 -8 0 1 0

x3 0 0 0 0 0 0 1 0 0 0 0

x1 -4-M 1 0 1 0 1 0 2 0 1 0

x2 3-M 1 0 0 1 -10 0 -8 0 1 0

x4 1-M 0 1 0 1 0 -5 0 -8 0 1

x5 M 0 0 0 0 0 0 0 0 -1 0

x6 M 0 0 0 0 0 0 0 0 0 -1

x7 0 1 0 0 0 0 0 0 0 0 0

x8 0 0 1 0 0 0 0 0 0 0 0

x9 0 0 0 1 0 0 0 0 0 0 0

x10 0 0 0 0 1 0 0 0 0 0 0

x11 0 0 0 0 0 1 0 0 0 0 0

x

Iterasi 2 Variabel dasar Z x7 x8 x9 x10 x11 x3 x13 x14 x15 x16

x4 -4 -11/6M 0 11/6 5/6 1 0 -5/6 0 -19/3 0 11/6

x5 M 0 0 0 0 0 0 0 0 -1 0

x6 M 0 0 0 0 0 0 0 0 0 -1

x7 0 1 0 0 0 0 0 0 0 0 0

x8 0 0 1 0 0 0 0 0 0 0 0

x9 0 0 0 1 0 0 0 0 0 0 0

x10 0 0 0 0 1 0 0 0 0 0 0

x11 0 0 0 0 0 1 0 0 0 0 0

x12 7/11 0 0 -1/11 1/11 0 1/11 0 -10/11 0 -1/11

x11 0 0 0 0 0 1 0 0 0 0 0


x3 0 0 0 0 0 0 1 0 0 0 0

x4 0 0 0 0 0 0 0 0 0 0 1

x5 M 0 0 0 0 0 0 0 0 -1 0

xlv

x6 -24/11 0 1 5/11 6/11 0 -5/11 0 -38/11 0 -6/11

x7 0 1 0 0 0 0 0 0 0 0 0

x8 0 0 1 0 0 0 0 0 0 0 0

x9 0 0 0 1 0 0 0 0 0 0 0

x10 0 0 0 0 1 0 0 0 0 0 0

x13 0 0 0 0 0 0 0 1 0 0 0


x1 0 0 0 0 0 1 0 0 0 0 0

x2 -37 -11M 11 0 10 1 -10 0 12 0 11 0

x3 0 0 0 0 0 0 1 0 0 0 0

x4 0 0 0 0 0 0 0 0 0 0 1

x5 M 0 0 0 0 0 0 0 0 -1 0

x4 0 0 0 0 0 0 0 0 0 0 1

x5 M 0 0 0 0 0 0 0 0 -1 0

x6 -24/11 0 1 5/11 6/11 0 -5/11 0 -38/11 0 -6/11

x6 -31/44 +25/44M -25/44 1 15/22 19/44 5/11

x6 -24/11 0 1 5/11 6/11 0 -5/11 0 -38/11 0 -6/11

x7 0 1 0 0 0 0 0 0 0 0 0

x8 0 0 1 0 0 0 0 0 0 0 0

x9 0 0 0 1 0 0 0 0 0 0 0

x10 0 0 0 0 1 0 0 0 0 0 0

x11 4+M -1 0 -1 0 1 0 -2 0 -1 0

x12 7/11 0 0 -1/11 1/11 0 1/11 0 -10/11 0 -1/11

x


x1 0 0 0 0 0 1 0 0 0 0 0

x2 0 0 0 0 0 0 0 1 0 0 0

x3 0 0 0 0 0 0 1 0 0 0 0

Variabel dasar

x1

x2

x3

x4

x5

Z x7 x8 x11 x10 x1

0 0 0 0 0 1

0 0 0 0 0 0

0 0 0 0 0 0

0 0 0 0 0 0

M 0 0 0 0 0

x7 0 1 0 0 0 0 0 0 0 0 0

x8 0 0 1 0 0 0 0 0 0 0 0

x9 0 0 0 1 0 0 0 0 0 0 0

x10 0 0 0 0 1 0 0 0 0 0 0

x11 -13/6 - 5/6M 5/6 0 2/3 1/6 -2/3 0 -1/6 0 5/6 0

x12 7/11 0 0 -1/11 1/11 0 1/11 0 -10/11 0 -1/11

x13 37/12+11/12M -11/12 0 -5/6 -1/12 5/6 0 1/12 0 -11/12 0

Iterasi 6

xlvi

x7

x8

0 1 0 0 0 0

0 0 1 0 0 0

x9 13/4 + 5/4M -5/4 0 3/2 -1/6 1

x10

x11

0 0 0 0 1 0

0 0 0 1 0 0

x12 15/44 - 5/44M 5/44 0 -3/22 5/44 -1/11

x13 3/8 -1/8M 1/8 0 -5/4 1/8 0

x3 x2 x14 x15 x4

0 0 0 0 0

0 1 0 0 0

1 0 0 0 0

0 0 0 0 1

0 0 0 -1 0

-5/11 5/44 -38/11 -25/44 -6/11

0 0 0 0 0

0 0 0 0 0

0 1/4 0 -5/4 0

0 0 0 0 0

0 0 0 0 0

1/11 -1/44 -10/11 5/44 -1/11

0 -1/8 0 1/8 0

Iterasi 7 Variabel dasar Z x7 x8 x11 x10 x1 x3 x2 x14 x13 X4

x1 0 0 0 0 0 1 0 0 0 0 0

x2 0 0 0 0 0 0 0 1 0 0 0

x3 0 0 0 0 0 0 1 0 0 0 0

x4 0 0 0 0 0 0 0 0 0 0 1

x5 3 1 0 -10 1 0 0 -1 0 -8 0

x6 1 0 1 -5 1 5/11 -5/11 -5/11 -38/11 -50/11 -6/11

xlvii

x7 0 1 0 0 0 0 0 0 0 0 0

x8 0 0 1 0 0 0 0 0 0 0 0

x9 7 0 0 -11 13/12 1 0 -1 0 -10 0

x10 0 0 0 0 1 0 0 0 0 0 0

x11 0 0 0 1 0 0 0 0 0 0 0

x12 0 0 0 1 5/22 -1/11 1/11 1/11 -10/11 10/11 -1/11

x13 0 0 0 0 0 0 0 0 0 1 0

x14 0 0 0 0 0 0 0 0 1 0 0

LAMPIRAN 2 Tabel Nilai Variabel dan Nilai Z pada Tiap Iterasi Kasus 2 dengan Algoritma Titik Interior Iterasi 1

Iterasi 2

Iterasi 3

é 30.1145ù ê 50.0104ú ê ú ê 5.0310ú ê ú 7.0369ú ê ê 30.6249ú ê ú 9.2295ú ê ê 19.8751ú ê ú ~ 1 7.9321ú ê X =ê 4.8545ú ê ú ê 2.9527 ú ê ú ê 469.9894ú ê 4.9983ú ê ú ê 339.8541ú ê 46.2329ú ê ú 0.5000ú ê ê 2.1616úû ë

é 29.9736ù ê 49.7487 ú ê ú ê 5.2547 ú ê ú 7.3032ú ê ê 30.1080ú ê ú 7.6660ú ê ê 20.2777 ú ê ú ~ 2 7.4420ú ê X =ê 4.7717 ú ê ú ê 2.9480ú ê ú ê 467.5137 ú ê 4.9877 ú ê ú ê 338.0426ú ê 47.9164ú ê ú 0.3857 ú ê ê 0.1081úû ë

é 30.1520ù ê 49.6344ú ê ú ê 5.2996ú ê ú 7.3565ú ê ê 29.8057 ú ê ú 7.7355ú ê ê 20.2136ú ê ú ~ 3 7.3438ú ê X =ê 4.5484ú ê ú ê 3.0090ú ê ú ê 466.1924ú ê 4.9849ú ê ú ê 336.7715ú ê 48.2530ú ê ú 0.0193ú ê ê 0.0793úû ë

~ 1

Z(X ) = -2668

Iterasi 6

~ 2

~ 3

Z(X ) = -498.8847

Z(X ) = -102.4273

Iterasi 7

Iterasi 8

xlviii

é 31.2309ù ê 29.7436ú ê ú ê 8.5528ú ê ú ê 11.2201ú ê 10.9751ú ê ú ê 14.7742ú ê 39.0256ú ê ú ~ 6 0.2272ú ê X =ê 0.2163ú ê ú ê 19.0364ú ê ú ê 266.2049ú ê 4.7836ú ê ú ê 175.4869ú ê 72.6549ú ê ú 0.0006ú ê ê 0.0013úû ë ~ 6

é ê ê ê ê ê ê ê ê ê ê ~ 7 ê X =ê ê ê ê ê ê ê ê ê ê ê ê ë

31.2353ù 19.3129úú 8.5631ú ú 11.2096ú 0.5488ú ú 14.7739ú 49.4519ú ú 0.2273ú 0.2017 ú ú 29.4775ú ú 161.8933ú 4.6699ú ú 92.0323ú 72.5510ú ú 0.0006ú 0.0012úû

~ 7

é ê ê ê ê ê ê ê ê ê ê ~ 8 ê X =ê ê ê ê ê ê ê ê ê ê ê ê ë

31.4114ù 18.6156úú 8.5517 ú ú 11.1913ú 0.0274ú ú 14.7434ú 49.9730ú ú 0.2570ú 0.0368ú ú 30.1931ú ú 154.7445ú 4.6464ú ú 86.1019ú 72.4272ú ú 0.0004ú 0.0004úû

~ 8

Z(X ) = 73.8412

Z(X ) = 105.3437

Z(X ) = 109.1634

Iterasi 11

Iterasi 12

Iterasi 13

xlix

é ê ê ê ê ê ê ê ê ê ê ~ 11 ê X =ê ê ê ê ê ê ê ê ê ê ê ê ë ~ 11

37.8395ù 12.1678úú 2.1598ú ú 3.4857 ú 0.0073ú ú 0.6456ú 49.9927 ú ú 14.3544ú 0.0007 ú ú 44.3464ú ú 83.8389ú 4.4697 ú ú 21.6638ú 23.5663ú ú 0.0000ú 0.0000úû

Z(X ) = 124.2888

~ 12

X

é ê ê ê ê ê ê ê ê ê ê ê =ê ê ê ê ê ê ê ê ê ê ê ê ë

~ 12

38.1093ù 11.8977 úú 1.8900ú ú 3.1423ú 0.0071ú ú 0.0323ú 49.9929ú ú 14.9677 ú 0.0007 ú ú 44.9600ú ú 80.8679ú 4.3716ú ú 18.9631ú 21.3583ú ú 0.0000ú 0.0000úû

Z(X ) = 124.9043

l

é ê ê ê ê ê ê ê ê ê ê ~ 13 ê X =ê ê ê ê ê ê ê ê ê ê ê ê ë ~ 13

38.1226ù 11.8800úú 1.8768ú ú 3.1248ú 0.0027 ú ú 0.0016ú 49.9974ú ú 14.9984ú 0.0006ú ú 44.9952ú ú 80.6773ú 4.3636ú ú 18.7947 ú 21.2452ú ú 0.0000ú 0.0000úû

Z(X ) = 124.9716

LAMPIRAN 3 Tabel Nilai Variabel dan Nilai Z pada Tiap Iterasi Kasus 3 dengan Metode Simpleks dan Tabel Optimal di Iterasi ke-28 Z x94 x95 x96 x97 x98 x99 x100 x101 x102 x103

Iterasi 1 = 0.00 = 500.00 = 160.00 = 170.00 = 150.00 = 260.00 = 280.00 = 295.00 = 265.00 = 1000.00 = 990.00

Z x74 x61 x96 x20 x98 x57 x100 x101 x102 x103

Iterasi 8 = 5105.38 = 20.00 = 87.69 = 112.12 = 57.88 = 247.31 = 4.23 = 119.62 = 305.00 = 987.31 = 639.23

Z x46 x61 x79 x20 x38 x57

Iterasi 15 = 14461.55 = 292.13 = 140.68 = 117.08 = 300.85 = 1.70 = 113.22

Iterasi 2 = 1875.00 Z x94 = 500.00 x95 = 10.00 x96 = 245.00 x45 = 25.00 x98 = 210.00 x99 = 130.00 x100 = 345.00 x101 = 140.00 x102 = 875.00 x103 = 940.00

Z x74 x61 x79 x20 x98 x57 x100 x101 x102 x103

Z x46 x61 x79 x20 x36 x57

Z x94 x57 x96 x45 x98 x99 x100 x101 x102 x103

Iterasi 9 = 7258.00 = 20.00 = 127.56 = 43.19 = 170.00 = 358.59 = 39.11 = 39.89 = 391.37 = 623.56 = 79.78

Iterasi 3 = 1966.11 = 500.00 = 1.11 = 248.33 = 26.11 = 204.44 = 118.89 = 347.22 = 134.44 = 866.11 = 937.78

Z x74 x61 x79 x20 x98 x57 x77 x101 x102 x103

Iterasi 16 = 14540.99 = 292.75 = 141.60 = 117.41 = 301.56 = 3.93 = 112.77

li

Z x74 x57 x96 x45 x98 x99 x100 x101 x102 x103

Iterasi 10 = 8618.42 = 20.00 = 147.50 = 89.72 = 264.47 = 399.18 = 82.15 = 15.75 = 405.72 = 215.22 = 400.00

Z x46 x61 x79 x20 x36 x57

Iterasi 17 = 16346.21 = 339.68 = 135.40 = 116.51 = 222.50 = 8.07 = 66.27

Iterasi 4 = 2566.11 = 20.00 = 1.11 = 248.33 = 26.11 = 204.44 = 118.89 = 347.22 = 174.44 = 866.11 = 937.78

Z x74 x61 x79 x20 x98 x57 x77 x101 x45 x103

Z x74 x61 x96 x45 x98 x99 x100 x101 x102 x103

Iterasi 11 = 9185.33 = 20.00 = 151.04 = 112.13 = 311.95 = 416.43 = 103.19 = 21.89 = 402.12 = 3.54 = 378.78

Z x46 x61 x79 x20 x76 x57

Iterasi 18 = 16874.67 = 355.40 = 127.66 = 113.18 = 154.23 = 7.94 = 28.49

Iterasi 5 = 2775.00 = 20.00 = 10.00 = 235.00 = 21.67 = 216.67 = 120.00 = 318.33 = 196.67 = 891.67 = 906.67

Z x74 x61 x79 x20 x98 x57 x77 x101 x63 x103

Z x46 x61 x79 x20 x76 x45

Iterasi = = = = = = = = = = =

Iterasi = = = = = = =

x77 x101 x5 x103

= 21.81 = 381.59 = 42.13 = 216.63

Z x46 x61 x79 x20 x76 x21 x89 x101 x5 x34

Iterasi 22 = 17585.42 = 371.95 = 121.68 = 107.96 = 102.52 = 10.33 = 2.75 = 22.25 = 449.92 = 121.95 = 220.37

x77 x101 x5 x103

= 21.93 = 390.17 = 42.75 = 209.83

Z x46 x61 x79 x20 x38 x21 x89 x101 x5 x34

Iterasi 23 = 18523.63 = 391.92 = 111.46 = 111.53 = 87.19 = 9.01 = 41.41 = 82.71 = 443.02 = 141.92 = 236.46

lii

x77 x101 x5 x34

= 8.75 = 454.26 = 89.68 = 95.92

Z x46 x61 x79 x77 x38 x21 x89 x101 x5 x34

Iterasi 24 = 21362.65 = 448.93 = 53.33 = 229.12 = 89.97 = 23.54 = 354.92 = 108.99 = 155.67 = 198.93 = 512.95

x77 x101 x5 x34

Z x46 x61 x79 x77 x38 x21 x89 x59 x5 x34

= 5.31 = 441.02 = 105.40 = 170.41

Iterasi 25 = 22522.38 = 460.03 = 33.93 = 275.95 = 137.41 = 25.97 = 497.24 = 136.73 = 19.40 = 210.03 = 634.92

x77 x101 x5 x34

= = 118.0 =

Iteras Z x46 x61 x79 x77 x36 x21 x89 x59 x5 x34

LAMPIRAN 4 Tabel Nilai Variabel dan Nilai Z pada Tiap Iterasi Kasus 3 dengan Algoritma Titik Interior Iterasi 0 é1ù ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ~ 0 X = ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú ëû

Iterasi 1 é2.1932ù ê1.1435 ú ê1.2345 ú ê ú ê1.2996 ú ê 2.2673ú ê1.4540 ú ê1.5604 ú ê ú ê2.5624ú ê1.5484 ú ê 0.7341ú ê1.0697 ú ê ú ê1.1405 ú ê1.2027 ú ~ 1 X = ê1.2724 ú ê1.3856 ú ê ú ê1.4167 ú ê1.5239 ú ê1.5960 ú ê3.0086 ú ê ú ê0.5337 ú ê1.0801 ú ê1.1595 ú ê1.2337 ú ê ú ê1.2804 ú ê1.3933 ú ê1.4389 ú ê1.5583 ú ë û

Lanjutan iterasi 0 sampai dengan iterasi 6

liii

Iterasi 2 é2.6506ù ê1.0789 ú ê1.2569 ú ê ú ê1.2077 ú ê 2.5315ú ê1.2860 ú ê1.7571 ú ê ú ê2.6214ú ê1.6321 ú ê0.6745ú ê1.0342 ú ê ú ê1.0493 ú ê0.9494 ú ~ 2 X = ê0.9275ú ê1.3032 ú ê ú ê1.1638 ú ê1.2582 ú ê1.1393 ú ê1.4734 ú ê ú ê0.5446 ú ê1.0900 ú ê1.1808 ú ê1.2645 ú ê ú ê1.2426 ú ê1.4539 ú ê1.4189 ú ê1.6735 ú ë û

Iterasi 3 é3.9869 ù ê0.9929ú ê1.2764 ú ê ú ê0.8638ú ê3.4943ú ê0.6929ú ê2.4026ú ê ú ê3.0833ú ê1.7255 ú ê0.5013ú ê0.8874ú ê ú ê 0.7521ú ê0.3289ú ~ 3 X = ê0.2117 ú ê0.9229ú ê ú ê0.3840ú ê0.5150ú ê0.1470ú ê0.1775ú ê ú ê0.6044ú ê1.1005 ú ê1.2103 ú ê1.3388 ú ê ú ê0.9844ú ê1.6356 ú ê1.1161 ú ê1.9163 ú ë û

Iteras

~ 4

X

é1ù ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú ëû

é1.6395 ù ê1.7037 ú ê0.2770ú ê ú ê1.0708 ú ê1.1441 ú ê1.2198 ú ê1.3389 ú ê ú ê1.3816 ú ê1.4868 ú ê1.5299 ú ê1.6182 ú ê ú ê1.7009 ú ê0.0500ú ê1.0737 ú ê1.1534 ú ê ú ê1.2346 ú ê1.3119 ú ê6.9120ú ê2.5990ú ê ú ê1.5604 ú ê1.6293 ú ê1.6879 ú ê0.7507 ú ê ú ê1.0754 ú ê1.1592 ú ê1.2381 ú ê1.2883 ú ê ú ê1.3973 ú ê1.4787 ú ê1.5715 ú ê1.6292 ú ë û


liv

é 1.7961 ù ê 1.7069 ú ê 0.2722 ú ê ú ê 1.0425 ú ê 1.0788 ú ê 1.1155 ú ê 1.5456 ú ê ú ê 1.4881 ú ê 1.6455 ú ê 1.3566 ú ê 1.5957 ú ê ú ê 1.6182 ú ê 0.0499 ú ê 1.0783 ú ê 1.1764 ú ê ú ê 1.2522 ú ê 1.3479 ú ê10.9438ú ê 3.5047 ú ê ú ê 1.6701 ú ê 1.7477 ú ê 1.7605 ú ê 0.7352 ú ê ú ê 1.0760 ú ê 1.1756 ú ê 1.2651 ú ê 1.2715 ú ê ú ê 1.4555 ú ê 1.5625 ú ê 1.8293 ú ê 1.7632 ú ë û

é2.1168ù ê1.8116 ú ê0.2622ú ê ú ê1.0117 ú ê0.9930ú ê 0.9891ú ê2.0146ú ê ú ê1.4681 ú ê1.9961 ú ê1.1877 ú ê1.6445 ú ê ú ê1.5779 ú ê0.0498ú ê1.1056 ú ê1.1862 ú ê ú ê1.2464 ú ê1.4073 ú ê2.0550ú ê6.8227 ú ê ú ê1.8959 ú ê1.9680 ú ê1.6242 ú ê0.6985ú ê ú ê1.0789 ú ê1.2112 ú ê1.3245 ú ê1.0769 ú ê ú ê1.5888 ú ê1.7584 ú ê1.6450 ú ê 2.0353ú ë û

é1ù ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú êú ê1ú ê1ú ê1ú ê1ú ëû

é1.7022 ù ê0.5140ú ê5.3689 ú ê ú ê1.1520 ú ê 2.5771ú ê1.3110 ú ê1.4001 ú ê ú ê1.4807 ú ê1.5600 ú ê1.6398 ú ê1.7158 ú ê ú ê0.2776ú ê1.0777 ú ê1.1591 ú ê1.2368 ú ê ú ê3.3657 ú ê1.9065 ú ê1.4671 ú ê1.5130 ú ê ú ê1.6288 ú ê1.7163 ú ê0.5154ú ê1.0800 ú ê ú ê1.1599 ú ê1.2405 ú ê1.3205 ú ê1.4006 ú ê ú ê1.4662 ú ê1.1552 ú ê1.6412 ú ê1.7215 ú ë û


lv

é 1.5528 ù ê 0.5031 ú ê11.0350ú ê ú ê 1.1726 ú ê 2.6911 ú ê 1.3638 ú ê 1.4679 ú ê ú ê 1.5717 ú ê 1.6779 ú ê 1.7886 ú ê 1.8891 ú ê ú ê 0.2728 ú ê 1.0842 ú ê 1.1768 ú ê 1.2655 ú ê ú ê 5.1749 ú ê 1.4164 ú ê 1.5580 ú ê 1.2459 ú ê ú ê 1.7527 ú ê 1.6681 ú ê 0.5038 ú ê 1.0880 ú ê ú ê 1.1784 ú ê 1.2724 ú ê 1.3686 ú ê 1.4683 ú ê ú ê 1.4330 ú ê 1.1745 ú ê 1.7901 ú ê 1.9061 ú ë û

é 0.8303 ù ê 0.4750 ú ê40.9152ú ê ú ê 1.2032 ú ê 3.4102 ú ê 1.4375 ú ê 1.6156 ú ê ú ê 1.7805 ú ê 1.9471 ú ê 2.1352 ú ê 2.4063 ú ê ú ê 0.2629 ú ê 1.1076 ú ê 1.2205 ú ê 1.3479 ú ê ú ê10.5166 ú ê 0.5866 ú ê 1.7424 ú ê 1.0649 ú ê ú ê 2.0909 ú ê 1.6496 ú ê 0.4840 ú ê 1.1052 ú ê ú ê 1.2188 ú ê 1.3423 ú ê 1.4766 ú ê 1.6237 ú ê ú ê 1.3850 ú ê 1.2345 ú ê 2.1591 ú ê 2.3774 ú ë û

é 1 ù ê 1 ú ê 1 ú ê ú ê 1 ú ê284ú ê102 ú ê107 ú ê ú ê109 ú ê192 ú ê 231ú ê238ú ê ú ê202ú ê918ú êë948úû

é 0.7591 ù ê 1.0734 ú ê 1.1367 ú ê ú ê 1.2371 ú ê148.2539 ú ê 24.0714 ú ê105.0017 ú ê ú ê 26.9126 ú ê146.1679 ú ê166.7754 ú ê215.1977ú ê ú ê151.6325 ú ê856.7989 ú êë908.6818úû

X = 589

X = 1748

~ 0

Iterasi 7

~ 1

Iterasi 8

é 0.7471 ù ê 1.0723 ú ê 1.0397 ú ê ú ê 1.2627 ú ê105.0470 ú ê 1.2036 ú ê113.0209 ú ê ú ê 4.9818 ú ê139.7541ú ê122.7600 ú ê215.3664ú ê ú ê135.9893 ú ê840.4493ú êë879.4937 úû ~ 2

X = 2408,6

Iterasi 9

lvi

é 0.7229 ù ê 1.0471 ú ê 0.7072 ú ê ú ê 1.3022 ú ê 5.2524 ú ê 0.9932 ú ê 79.2129 ú ê ú ê 3.7845 ú ê155.2226 ú ê 77.7673 ú ê138.4332 ú ê ú ê187.5646 ú ê883.8944ú êë780.7128úû ~ 3

X = 3629,2

Iterasi 10

~

X

Iterasi

é10.4554ù ê 0.6808 ú ê 0.9383 ú ê ú ê 0.3380 ú ê 9.0720 ú ê 0.2406 ú ê11.6093ú ê ú ê 0.6830 ú ê 0.6931 ú ê 0.2198 ú ê 0.4882 ú ê ú ê 0.3149 ú ê 0.1393 ú ~ 7 X = ê 0.1035 ú ê 0.3977 ú ê ú ê 0.1057 ú ê 0.1939 ú ê 0.0919 ú ê 0.1067 ú ê ú ê 1.1849 ú ê 1.1467 ú ê 1.3315 ú ê 1.5633 ú ê ú ê 0.1471 ú ê 2.3510 ú ê 0.1061 ú ê 3.0228 ú ë û

é 0.5228 ù ê 0.5473 ú ê 0.5258 ú ê ú ê 0.2229 ú ê22.1159ú ê 0.1635 ú ê16.9431 ú ê ú ê 0.3179 ú ê 0.2344 ú ê 0.1445 ú ê 0.3518 ú ê ú ê 0.2278 ú ê 0.1072 ú ~ 8 X = ê 0.0785 ú ê 0.3077 ú ê ú ê 0.0466 ú ê 0.1466 ú ê 0.0760 ú ê 0.0864 ú ê ú ê 1.9571 ú ê 1.1831 ú ê 1.4233 ú ê 1.7438 ú ê ú ê 0.0591 ú ê 2.9941 ú ê 0.0534 ú ê 3.9483 ú ë û

é 0.4996 ù ê 0.5015 ú ê 0.4447 ú ê ú ê 0.1917 ú ê106.1829ú ê 0.1424 ú ê 20.7516 ú ê ú ê 0.2783 ú ê 0.2010 ú ê 0.1248 ú ê 0.3079 ú ê ú ê 0.2014 ú ê 0.0952 ú ~ 9 X = ê 0.0697 ú ê 0.2717 ú ê ú ê 0.0395 ú ê 0.1297 ú ê 0.0691 ú ê 0.0789 ú ê ú ê 3.2245 ú ê 1.1773 ú ê 1.3969 ú ê 1.6751 ú ê ú ê 0.0504 ú ê 3.3187 ú ê 0.0454 ú ê 4.4155 ú ë û


lvii

~ 10

X

é 0.4935 ù ê 0.4763 ú ê 0.4267 ú ê ú ê 0.1838 ú ê132.6572ú ê 0.1389 ú ê 19.4709 ú ê ú ê 0.2582 ú ê 0.1962 ú ê 0.1217 ú ê 0.2992 ú ê ú ê 0.1967 ú ê 0.0934 ú = ê 0.0683 ú ê 0.2667 ú ê ú ê 0.0386 ú ê 0.1267 ú ê 0.0680 ú ê 0.0766 ú ê ú ê 3.8402 ú ê 1.3102 ú ê 1.1635 ú ê 1.5988 ú ê ú ê 0.0491 ú ê 3.0917 ú ê 0.0442 ú ê 4.5467 ú ë û

~ 11

X =

é 4.6434 ù ê 1.8330 ú ê 0.2344 ú ê ú ê 0.8755 ú ê 0.7037 ú ê 0.6588 ú ê 9.7877 ú ê ú ê 0.0377 ú ê 5.4224 ú ê 0.7097 ú ê 1.4885 ú ê ú ê 1.2109 ú ê 0.0492 ú ê 0.9551 ú ê 0.9353 ú ê ú ê 0.8649 ú ê 0.7041 ú ê 0.0876 ú ê209.1845ú ê ú ê 3.0950 ú ê 0.3771 ú ê 0.0762 ú ê 0.4306 ú ê ú ê 0.9608 ú ê 1.2860 ú ê 1.4241 ú ê 0.1727 ú ê ú ê 1.8770 ú ê 2.4753 ú ê 0.5524 ú ê 1.2107 ú ë û

é 8.4942 ù ê 2.0251 ú ê 0.2207 ú ê ú ê 0.8316 ú ê 0.6134 ú ê 0.5864 ú ê 34.9973 ú ê ú ê 0.0331 ú ê 11.4226 ú ê 0.6233 ú ê 1.4371 ú ê ú ê 1.1772 ú ê 0.0486 ú ê 0.7422 ú ê 0.6227 ú ê ú ê 0.4518 ú ê 0.3009 ú ê 0.0782 ú ê238.4064ú ê ú ê 3.7744 ú ê 0.2251 ú ê 0.0560 ú ê 0.2487 ú ê ú ê 0.8515 ú ê 1.3064 ú ê 1.4256 ú ê 0.0718 ú ê ú ê 1.9233 ú ê 2.9207 ú ê 0.2723 ú ê 0.4974 ú ë û


lviii

é 12.3837 ù ê 2.1274 ú ê 0.2132 ú ê ú ê 0.8132 ú ê 0.5866 ú ê 0.5665 ú ê181.7453 ú ê ú ê 0.0309 ú ê 25.1720 ú ê 0.6024 ú ê 1.4303 ú ê ú ê 1.2129 ú ê 0.0482 ú ê 0.6744 ú ê 0.5278 ú ê ú ê 0.3748 ú ê 0.2601 ú ê 0.0743 ú ê320.4276ú ê ú ê 3.8122 ú ê 0.1941 ú ê 0.0493 ú ê 0.2148 ú ê ú ê 0.8140 ú ê 1.3259 ú ê 1.4437 ú ê 0.0610 ú ê ú ê 1.9985 ú ê 3.3529 ú ê 0.2282 ú ê 0.4265 ú ë û

é 13.6048 ù ê 2.0236 ú ê 0.2115 ú ê ú ê 0.7972 ú ê 0.5742 ú ê 0.5546 ú ê233.3376ú ê ú ê 0.0305 ú ê 40.8434 ú ê 0.5797 ú ê 1.2992 ú ê ú ê 1.1878 ú ê 0.0478 ú ê 0.6402 ú ê 0.4877 ú ê ú ê 0.3679 ú ê 0.2518 ú ê 0.0726 ú ê348.0689 ú ê ú ê 4.2316 ú ê 0.1884 ú ê 0.0482 ú ê 0.2080 ú ê ú ê 0.8017 ú ê 1.3280 ú ê 1.4418 ú ê 0.0595 ú ê ú ê 1.9997 ú ê 3.4558 ú ê 0.2194 ú ê 0.3936 ú ë û

é 0.3146 ù ê 0.4005 ú ê53.9867 ú ê ú ê 0.7027 ú ê 5.6784 ú ê 0.8102 ú ê 2.3159 ú ê ú ê 2.9250 ú ê 3.6585 ú ê 4.7745 ú ê 7.2652 ú ê ú ê 0.2371 ú ê 1.1602 ú ê 1.3584 ú ê 1.6092 ú ê ú ê 0.1659 ú ê 0.1878 ú ê 0.8949 ú ê 0.4254 ú ê ú ê 0.8760 ú ê 3.3196 ú ê 0.4269 ú ê 1.1603 ú ê ú ê 1.3581 ú ê 1.6085 ú ê 1.9325 ú ê 2.3647 ú ê ú ê 1.1476 ú ê 0.9485 ú ê 5.0888 ú ê 7.1161 ú ë û

é 0.2431 ù ê 0.3640 ú ê57.4763ú ê ú ê 0.3557 ú ê11.5004 ú ê 0.3702 ú ê 2.8896 ú ê ú ê 4.1006 ú ê 5.6457 ú ê 8.5585 ú ê18.7729 ú ê ú ê 0.2242 ú ê 1.1902 ú ê 1.4454 ú ê 1.7889 ú ê ú ê 0.0648 ú ê 0.1254 ú ê 0.3780 ú ê 0.2699 ú ê ú ê 0.4242 ú ê12.4427 ú ê 0.4002 ú ê 1.1921 ú ê ú ê 1.4448 ú ê 1.7941 ú ê 2.2890 ú ê 3.0316 ú ê ú ê 1.1372 ú ê 0.5958 ú ê10.0438 ú ê18.0307 ú ë û


lix

é 0.2153 ù ê 0.3384 ú ê59.9204 ú ê ú ê 0.3054 ú ê32.1723ú ê 0.3153 ú ê 3.4078 ú ê ú ê 5.4415 ú ê 8.3912 ú ê15.6113 ú ê57.8262 ú ê ú ê 0.2175 ú ê 1.1996 ú ê 1.4959 ú ê 1.8876 ú ê ú ê 0.0552 ú ê 0.1105 ú ê 0.3243 ú ê 0.2473 ú ê ú ê 0.3760 ú ê78.6436ú ê 0.3855 ú ê 1.2083 ú ê ú ê 1.4873 ú ê 1.9245 ú ê 2.5609 ú ê 3.6251 ú ê ú ê 1.0816 ú ê 0.5281 ú ê20.8962ú ê58.3729 ú ë û

é 0.2113 ù ê 0.3230 ú ê59.9650 ú ê ú ê 0.2785 ú ê46.0528ú ê 0.2991 ú ê 3.5162 ú ê ú ê 5.9274 ú ê 9.2582 ú ê18.5218 ú ê72.4514ú ê ú ê 0.2158 ú ê 1.1874 ú ê 1.4977 ú ê 1.8603 ú ê ú ê 0.0540 ú ê 0.1071 ú ê 0.3073 ú ê 0.2359 ú ê ú ê 0.3418 ú ê99.6327 ú ê 0.3871 ú ê 1.1429 ú ê ú ê 1.1822 ú ê 1.8725 ú ê 2.1747 ú ê 2.5786 ú ê ú ê 1.0005 ú ê 0.4962 ú ê 1.0448 ú ê 9.2737 ú ë û

é 0.6584 ù ê 0.6765 ú ê 0.2604 ú ê ú ê 1.1212 ú ê 2.9306 ú ê 0.5620 ú ê 42.3483 ú ê ú ê 1.9723 ú ê 2.4370 ú ê 2.6263 ú ê 86.3288 ú ê ú ê152.1257 ú ê882.1378ú êë743.1848úû ~ 7

X = 8323,8

Iterasi 14

é 0.6270 ù ê 0.3657 ú ê 0.1571 ú ê ú ê 0.7696 ú ê 1.4210 ú ê 0.4526 ú ê 45.1048 ú ê ú ê 1.6628 ú ê 1.6809 ú ê 2.3809 ú ê 38.2230 ú ê ú ê132.5904 ú ê759.5137ú êë725.8167úû ~ 8

X = 9833,3

Iterasi 15

é 0.6083 ù ê 0.3096 ú ê 0.1339 ú ê ú ê 0.6655 ú ê 1.2027 ú ê 0.4090 ú ê 21.6364 ú ê ú ê 1.5711 ú ê 1.5094 ú ê 2.2878 ú ê 32.7279 ú ê ú ê 68.6076 ú ê 37.9757 ú êë372.4773úû ~ 9

X = 1557,6

Iterasi 16

lx

é 0.5759 ù ê 0.3016 ú ê 0.1304 ú ê ú ê 0.6494 ú ê 1.1718 ú ê 0.4022 ú ê 20.7345 ú ê ú ê 1.5321 ú ê 1.4545 ú ê 2.2591 ú ê 28.7355 ú ê ú ê 40.7783 ú ê 3.2129 ú êë123.3037úû ~ 10

X

= 1687,3

Iterasi 17

~

X

Iterasi

~ 14

X


~ 15

X


~ 16

X


lxi

é 0.1337 ù ê 0.1782 ú ê 0.1009 ú ê ú ê 0.1484 ú ê139.2427 ú ê 0.1522 ú ê 0.2213 ú ê ú ê 0.0817 ú ê 0.0745 ú ê 0.0676 ú ê 0.4064 ú ê ú ê 0.1700 ú ê 0.1143 ú = ê 0.0707 ú ê 0.3776 ú ê ú ê 0.0190 ú ê 0.1307 ú ê 0.0838 ú ê 0.0694 ú ê ú ê 0.0901 ú ê 68.4741 ú ê 0.3163 ú ê 0.6641 ú ê ú ê 0.0187 ú ê 0.6576 ú ê 0.0191 ú ê 0.7767 ú ë û

~ 17

X

é 0.1259 ù ê 0.1690 ú ê 0.0972 ú ê ú ê 0.1434 ú ê141.8877 ú ê 0.1504 ú ê 0.1981 ú ê ú ê 0.0767 ú ê 0.0708 ú ê 0.0654 ú ê 0.3518 ú ê ú ê 0.1658 ú ê 0.1120 ú = ê 0.0702 ú ê 0.3538 ú ê ú ê 0.0184 ú ê 0.1291 ú ê 0.0821 ú ê 0.0671 ú ê ú ê 0.0889 ú ê 75.7221 ú ê 0.2608 ú ê 0.4441 ú ê ú ê 0.0182 ú ê 0.5757 ú ê 0.0186 ú ê 0.5566 ú ë û

é ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ~ 18 X =ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ê ë

é 7.5678 ù ê 0.7941 ú ê 0.1857 ú ê ú ê 0.5342 ú ê 0.3169 ú ê 0.3496 ú ê288.0802ú ê ú ê 0.0246 ú ê216.4948ú ê 0.2271 ú ê 0.1197 ú ê ú ê 0.6053 ú ê 0.0434 ú ê 0.3326 ú ê 0.2351 ú ê ú ê 0.2259 ú ê 0.1801 ú ê 0.0572 ú ê369.1057 ú ê ú ê 0.2613 ú ê 0.1327 ú ê 0.0352 ú ê 0.1483 ú ê ú ê 0.3820 ú ê 1.0532 ú ê 0.8384 ú ê 0.0402 ú ê ú ê 0.7176 ú ê 1.4610 ú ê 0.1966 ú ê 0.1783 ú ë û

é 4.6316 ù ê 0.7000 ú ê 0.1741 ú ê ú ê 0.4873 ú ê 0.2694 ú ê 0.3242 ú ê 299.4231ú ê ú ê 0.0214 ú ê229.3880ú ê 0.2004 ú ê 0.1082 ú ê ú ê 0.5706 ú ê 0.0437 ú ê 0.1878 ú ê 0.2510 ú ê ú ê 0.1352 ú ê 0.1738 ú ê 0.0607 ú ê372.6824 ú ê ú ê 0.2041 ú ê 0.1205 ú ê 0.0292 ú ê 0.1411 ú ê ú ê 0.2871 ú ê 0.9095 ú ê 0.6430 ú ê 0.0313 ú ê ú ê 0.5077 ú ê 0.9885 ú ê 0.2449 ú ê 0.1813 ú ë û


lxii

é 2.0531 ù ê 0.5929 ú ê 0.1612 ú ê ú ê 0.4384 ú ê 0.2270 ú ê 0.2960 ú ê 324.5561ú ê ú ê 0.0184 ú ê238.6874ú ê 0.1741 ú ê 0.0965 ú ê ú ê 0.5286 ú ê 0.0438 ú ê 0.1331 ú ê 0.2637 ú ê ú ê 0.0967 ú ê 0.1659 ú ê 0.0651 ú ê384.2887 ú ê ú ê 0.1633 ú ê 0.1080 ú ê 0.0242 ú ê 0.1326 ú ê ú ê 0.2221 ú ê 0.7801 ú ê 0.5040 ú ê 0.0248 ú ê ú ê 0.3807 ú ê 0.7280 ú ê 0.3321 ú ê 0.1799 ú ë û

é 0.1027 ù ê 0.4805 ú ê 0.1554 ú ê ú ê 0.4208 ú ê 0.2165 ú ê 0.2827 ú ê328.6142 ú ê ú ê 0.0180 ú ê239.9327 ú ê 0.1642 ú ê 0.0924 ú ê ú ê 0.4987 ú ê 0.0433 ú ê 0.1291 ú ê 0.1992 ú ê ú ê 0.0939 ú ê 0.1600 ú ê 0.0646 ú ê387.1103ú ê ú ê 0.1617 ú ê 0.1042 ú ê 0.0235 ú ê 0.1279 ú ê ú ê 0.2124 ú ê 0.7580 ú ê 0.4837 ú ê 0.0240 ú ê ú ê 0.3639 ú ê 0.6975 ú ê 0.3335 ú ê 0.1466 ú ë û

é 0.2296 ù ê 0.1555 ú ê 52.3943 ú ê ú ê 0.1516 ú ê140.4063ú ê 0.2116 ú ê 2.0648 ú ê ú ê 10.2745 ú ê 0.3150 ú ê 0.6530 ú ê 86.4672 ú ê ú ê 0.1828 ú ê 0.9518 ú ê 1.4355 ú ê 1.2638 ú ê ú ê 0.0364 ú ê 0.0789 ú ê 0.2134 ú ê 0.1085 ú ê ú ê 0.1316 ú ê100.3772ú ê 0.3930 ú ê 0.6025 ú ê ú ê 0.2334 ú ê 1.3140 ú ê 0.5454 ú ê 0.3950 ú ê ú ê 0.4827 ú ê 0.3744 ú ê 0.5671 ú ê 2.5119 ú ë û



lxiii



é 0.2886 ù ê 0.1964 ú ê 0.0971 ú ê ú ê 0.4085 ú ê 0.7785 ú ê 0.3856 ú ê71.3839ú ê ú ê 0.9422 ú ê 1.1641 ú ê 1.2902 ú ê 0.5373 ú ê ú ê 3.6918 ú ê 1.2883 ú êë 4.2074 úû ~ 14

X

= 19527

é 0.2268 ù ê 0.1440 ú ê 0.0775 ú ê ú ê 0.2466 ú ê 0.6041 ú ê 0.4191 ú ê70.0512ú ê ú ê 0.8638 ú ê 1.4317 ú ê 1.0116 ú ê 0.5179 ú ê ú ê 3.0457 ú ê 1.2836 ú êë 0.2104 úû ~ 15

X

= 19956

Iterasi 21

é0.1805ù ê0.1104ú ê0.0626ú ê ú ê0.1767ú ê0.4782ú ê0.4650ú ê3.5026ú ê ú ê0.7799ú ê1.8955 ú ê0.8040ú ê0.4955ú ê ú ê2.5042ú ê1.2636 ú êë0.1987úû ~ 16

X

= 21156

Iterasi 22

lxiv

é0.1728ù ê0.1069ú ê0.0610ú ê ú ê0.1718ú ê0.4626ú ê0.4656ú ê2.2158ú ê ú ê0.7445ú ê1.8492 ú ê0.7708ú ê0.4870ú ê ú ê2.3766ú ê1.1823 ú êë0.1979úû ~ 17

X

= 21428

~

X

Iterasi 23

~ 21

X


~ 22

X


lxv

é0.0000ù ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê 117.7 ú ê 0.0001ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú = ê 0.0001ú ê0.0000ú ê ú ê0.0000ú ê 0.0001ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê 85.4 ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0000ú ë û

é 0.0187 ù ê 0.0191 ú ê 0.0446 ú ê ú ê 0.0985 ú ê 0.0393 ú ê 0.0549 ú ê347.7653ú ê ú ê 0.0079 ú ê 0.3850 ú ê 0.0206 ú ê 0.0171 ú ê ú ê 0.0606 ú ê 0.0276 ú ê 0.0499 ú ê 0.0080 ú ê ú ê 0.0338 ú ê 0.0519 ú ê 0.0527 ú ê397.8640ú ê ú ê 0.1076 ú ê 0.0337 ú ê 0.0086 ú ê 0.0414 ú ê ú ê 0.0399 ú ê 0.2297 ú ê 0.0956 ú ê 0.0081 ú ê ú ê 0.0616 ú ê 0.1109 ú ê 0.6842 ú ê 0.0067 ú ë û

é0.0000ù ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê 425.3 ú ê ú ê0.0000ú ê 0.0001ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê 367.2 ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê 0.0001ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê 3.8 ú ê0.0000ú ë û


lxvi

é0.0000ù ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê 432.8 ú ê ú ê0.0000ú ê 0.0001ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê 365.3 ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê 0.0001ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê0.0016ú ê0.0000ú ë û

é 1.7497 ù ê 0.0070 ú ê 49.7338 ú ê ú ê 0.0099 ú ê110.1767 ú ê 0.0079 ú ê 0.0389 ú ê ú ê620.4942ú ê 0.1288 ú ê 0.0543 ú ê 99.0277 ú ê ú ê 0.0669 ú ê 0.2861 ú ê 0.9685 ú ê 0.2271 ú ê ú ê 0.0071 ú ê 0.0266 ú ê 0.0101 ú ê 0.1331 ú ê ú ê 0.0173 ú ê118.8274 ú ê 0.3003 ú ê 0.0971 ú ê ú ê 0.0297 ú ê 0.3348 ú ê 0.0679 ú ê 0.0508 ú ê ú ê 0.0127 ú ê 0.6944 ú ê 0.0922 ú ê 37.5094 ú ë û

é 45.9 ù ê0.0000ú ê0.0025ú ê ú ê0.0000ú ê 23.01 ú ê0.0000ú ê0.0000ú ê ú ê1023.6 ú ê0.0000ú ê0.0000ú ê 90.1 ú ê ú ê0.0000ú ê 0.0001ú ê0.0005ú ê 0.0001ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0002ú ê ú ê0.0000ú ê 95.5 ú ê0.0003ú ê0.0000ú ê ú ê0.0000ú ê 0.0001ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0009ú ê0.0000ú ê 11.5 ú ë û


lxvii

é 50.6 ù ê0.0000ú ê 0.0001ú ê ú ê0.0000ú ê 236.7 ú ê0.0000ú ê0.0000ú ê ú ê1042.2 ú ê0.0000ú ê0.0000ú ê 89 ú ê ú ê0.0000ú ê 0.0001ú ê0.0005ú ê 0.0001ú ê ú ê0.0000ú ê0.0000ú ê0.0000ú ê0.0002ú ê ú ê0.0000ú ê 92.7 ú ê0.0003ú ê0.0000ú ê ú ê0.0000ú ê 0.0001ú ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0010ú ê0.0000ú ê 14.6 ú ë û

é0.0435ù ê0.0363ú ê0.0264ú ê ú ê0.0670ú ê 0.1511ú ê0.6195ú ê0.0973ú ê ú ê0.1476ú ê1.0075 ú ê 0.1601ú ê0.2292ú ê ú ê 0.4241ú ê0.1736ú êë0.1719úû ~ 21

X

é0.0000ù ê0.0000ú ê0.0000ú ê ú ê0.0000ú ê0.0000ú ê 1.3 ú ê0.0000ú ê ú ê0.0000ú ê0.0004ú ê0.0000ú ê 0.0001ú ê ú ê 0.0001ú ê 0.0001ú êë 0.0001úû ~ 22

= 22829

X

lxviii

= 24121

PENYELESAIAN PROGRAM LINEAR DENGAN MENGGUNAKAN ALGORITMA TITIK INTERIOR DAN METODE SIMPLEKS

Recommend Documents