7

BAB IITINJAUAN PUSTAKA

Dalam pelaksanaan penelitian ini terdapat beberapa teori atau referensi yang

nantinya digunakan untuk menjadi dasar dalam pengerjaan penelitian ini. Oleh karena

itu, pada bab II akan menjelaskan tentang beberapa teori atau literatur yang mendukung

penelitian ini. Untuk lebih jelasnya akan dipaparkan dibawah ini.

2.1 Penelitian Terdahulu

1. Simanjuntak (2010). Pada skripsi ini membahas tentang penentuan jumlah

produksi CPO dan Kernel yang optimal guna mendapatkan keuntungan

maksimum. Permasalahan akan dibahas dengan penerapan model program linier

yang penyelesaiannya menggunakan teknik program dinamik. Dengan adanya

model program linier ini diharapkan dapat mencari hasil yang optimal dari

permasalahan yang terjadi pada case yang terjadi. Program dinamik ditujukan

untuk melihat hasil yang telah dicapai (optimum) dari perhitungan model program

linier dengan melihat fungsi tujuan yang telah tercapai dan dapat mencari

alternatif yang terbaik pada kondisi optimum

2. Gultom (2013). Pada penelitian ini membahas tentang penentuan kondisi optimal

pada PT.XYZ terhadap sumberdaya yang ada yaitu berupa mesin, bahan baku, dan

waktu kerja. Dengan adanya Primal-Dual dengan menggunakan software LINDO

maka olahan dari program linier tersebut dapat terselesaikan dengan melihat

dengan kondisi yang optimal. Dan pada Primal-Dual dapat mengetahui masalah

yang menyebabkan kondisi pada sumberdaya yang tidak optimal, sehingga dengan

adanya Primal-Dual maka masalah optimalisasi dapat terselesaikan.

3. Praharsi (2011). Pada penelitian ini membahas tentang optimalisasi suatu

pemrograman nonlinier dengan menggunakan Excel report untuk melakukan

perhitungannya dan mencari titik optimasi pada pemrograman nonlinier tersebut.

Pada hasil akhir yang didapatkan dari Excel report tersebut dilakukan analisis

dengan menggunakan analisis sensitivitas.

Dari hasil komparasi secara teoritis beberapa metode tersebut dan hasil studi

pendahuluan di lapangan, metode yang akan digunakan pada penelitian

PT.PERTAMINA (Persero) Surabaya adalah Metode Pemrograman Linier untuk

mengetahui optimasi yang didapat.

8

Perbandingan penelitian terdahulu dengan penelitian yang dilakukan sekarang

dapat dilihat pada Tabel 2.1.

Tabel 2.1 Tabel Perbandingan Penelitian TerdahuluSumber Objek Penelitian Metode Hasil Penelitian

Simanjuntak (2010)

Turangir Oil Mill Program Linier dengan Program Dinamik

Dari hasil pengolahan data, maka didapatkan optimasi pada jumlah produksi CPO dan Kamel, dan didapatkan perbedaan selisih pendapatan berdasarkan pola produksi perusahaan

Gultom(2013)

PT.XYZ Program Linier dengan Primal-Dual

Dengan analisis yang dilakukan, terdapat sumberdaya yang belum digunakan secara optimaldilihat dari hasil pengolahan dengan software LINDO

Praharsi(2011)

- Program nonlinear dengan Excel report dan analisis sensitvitas

Dari hasil pengolahan yang dilakukan dapat menunjukkan beberapa karakteristik optimisasi dan analisis sensitivitas pada ketiga kemungkinan yang ada.

Penelitian ini(2014)

PT. PERTAMINASurabaya-Jawa Timur

Program Linier dengan ILP dan kombinasi optimasi lokal

Dari hasil analisis yang dilakukan maka dapat diketahui jumlah gentry yang optimal untuk memenuhi permintaan yang ada dengan menggunakan dua model matematis yang nantinya juga dapat diketahui jumlah pemenuhan permintaan sebelum dan sesudah penambahan gentry.

2.2 Pengujian Kecukupan Data

Uji kecukupan data dilakukan untuk melihat apakah data yang diambil sudah

mewakili data populasi dan sesuai dengan tingkat ketelitian yang diinginkan atau tidak.

Menurut Barnes (1980) rumus perhitungan kecukupan data dapat dilihat pada

persamaan (2-1) berikut ini.

? = �? ? ?? ? ?? � (2-1)

9

Dimana :

n = banyaknya data yang harus diambilZ = ? ? 2? = 1,96? = standar deviasi

= ? Σ(Xi−X? )2n−1? = tingkat ketelitian?? = waktu rata-rata2.3 Pemrograman Linier

Pemrograman Linier merupakan metode matematik dalam mengalokasikan

sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimumkan

keuntungan dan meminimumkan biaya. Pemrograman linier banyak diterapkan dalam

masalah ekonomi, industri, militer, social dan lain-lain. Pemrograman linier berkaitan

dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang

terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier (Siringoringo,

2005).

Gaspersz (1998) menyebutkan terdapat lima karakteristik utama dalam masalah

program linier (linear programming) adalah sebagai berikut :

1. Masalah linear programming berkaitan dengan upaya memaksimumkan (pada

umumnya keuntungan) atau meminimumkan (pada umumnya biaya). Upaya

optimasi (maksimum atau minimum) ini disebut sebagai fungsi tujuan (objective

function) dari linear programming. Fungsi tujuan ini terdiri dari variabel-variabel

keputusan (desicion variable).

2. Terdapat kendala-kendala atau keterbatasan, yang membatasi pencapaian tujuan

yang dirumuskan dalam linear programming. Kendala-kendala ini dirumuskan

dalam fungsi-fungsi kendala (constraint’s function), terdiri dari variabel-variabel

keputusan yang menggunakan sumber-sumber daya yang terbatas itu. Dengan

demikian yang akan diselesaikan dalam linear programming adalah mencapai

fungsi tujuan (maksimum keuntungan atau minimum biaya) dengan memperhatikan

fungsi-fungsi kendala (keterbatasan atau kendala) sumber-sumber daya yang ada.

3. Memiliki sifat linearitas. Sifat linearitas ini berlaku untuk semua fungsi tujuan dan

fungsi-fungsi kendala.

10

4. Memiliki sifat homogenitas. Sifat homogenitas ini berkaitan dengan kesamaan

sumber-sumber daya yang digunakan dalam proses produksi.

5. Memiliki sifat divisibility. Sifat divisibility diperlukan, karena linear programming

mengasumsikan bahwa nilai dari variabel-variabel keputusan maupun penggunaan

sumber-sumber daya dapat dibagi ke dalam pecahan-pecahan. Jika pembagian ini

tidak mungkin dilakukan terhadap variabel keputusan, misalnya industri mobil,

furnitur, dan lain-lain, karena nilai kuantitas produksi diukur dalam bilangan bulat,

maka modifikasi terhadap LP harus dilakukan. Bentuk modifikasi dari LP ini

disebut dengan integer linear programming.

2.3.1 Asumsi Dasar Program Linier

Menurut Hiller dan Lieberman (1990) terdapat 5 (lima) asumsi yang melandasi

program linier dimana asumsi tersebut merupakan suatu dasar dalam membentuk model

matematis yang akan dioptimalkan (maksimasi atau minimasi) yaitu:

1. Linearitas berarti bahwa semua fungsi matematis pada model program linier harus

merupakan fungsi-fungsi linier.

2. Proporsionalitas berarti bahwa tingkat perubahan atau kecondongan fungsi adalah

konstan. Oleh karena itu, perubahan dari ukuran tertentu pada nilai variabel

keputusan (xj) akan menghasilkan perubahan yang relatif sama pada nilai fungsi (Z).

3. Aditivitas berarti bahwa untuk setiap fungsi, nilai fungsi total dapat diperoleh

dengan menjumlahkan kontribusi-kontribusi individual (untuk fungsi tujuan dan

untuk suatu fungsi kendala) dari masing-masing kegiatan.

4. Divisibilitas berarti bahwa unit-unit kegiatan dapat dibagi kedalam bagian sekecil-

kecilnya, sehingga nilai-nilai variabel keputusan tidak harus integer (hanya 0 dan 1

atau bilangan bulat) tetapi diperbolehkan non integer (misalnya 875.38;58.0;21).

5. Deterministik berarti bahwa semua parameter pada model program linier (yaitu

nilai-nilai Cj , aij dan bj) konstan dan diketahui atau ditentukan secara pasti.

2.3.2 Formulasi Model Program Linier

Didalam menyusun model program linier, langkah-langkah yang dilakukan adalah

mengidentifikasi masalah, menetapkan tujuan dan membentuk formulasi model

matematik yang meliputi tiga tahap yakni:

1. Menentukan variabel keputusan

11

2. Membentuk fungsi tujuan yang ditujukan sebagai suatu hubungan linier dari

variabel keputusan

3. Menentukan semua kendala masalah tersebut dan mengekspresikan dalam

persamaan atau pertidaksamaan, yang juga merupakan hubugan linier dari variabel

keputusan yang mencerminkan keterbatasan sumber daya masalah itu.

Secara matematik, model umum dari pemograman linier yang terdiri dari

sekumpulan variabel keputusan X1, X2, ....., Xn dapat dirumuskan sesuai dengan

persamaan (2-2) sebagai berikut :

Maksimum atau Minimum Z = C1X1 + C2X2 + .... + CnXn (2-2)

Dengan kendala :

A11X1 + A12X2 + .... + A1nXn ≤ B1

A21X1 + A22X2 + .... + A2nXn ≤ B2

Am1X1 + Am2X2 + .... + AmnXn ≤ Bm

X1 ≤ D1

Xn ≤ Dn

X1, X2, ...., Xn ≥ 0

Dimana pada penelitian ini dalam mengelola stasiun kerja, konstanta yang

digunakan untuk mencapai tujuan menentukan banyaknya gentry dengan adalah :

X1, X2, ...., Xn = jumlah masing-masing truk tangki sesuai dengan kapasitas

C1, C2, ...., Cn = masing-masing tipe kapasitas (Kiloliter)

Am1, Am2, ...., Am = waktu proses masing-masing kapasitas truk pada tiap

gentry

B1, B2, ...., Bm = kapasitas yang tersedia di masing-masing gentry (Kiloliter)

D1, D2, ...., Dn = banyaknya masing-masing kapasitas truk tangki

2.3.3 Integer Linear Programming (ILP)

Menurut Sitompul (2006) Integer Linear Programming pada intinya berkaitan

dengan program linier dimana beberapa atau semua variabel memiliki nilai integer

(bulat). Program integer dibagi atas tiga jenis, yaitu:

1. Program integer murni (Pure Integer Programming), semua variabel keputusannya

adalah integer.

12

2. Program integer campuran (Mixed Integer Programming), sebagian keputusannya

adalah integer.

3. Program integer 0-1 (Zero One Integer Programming), variabel keputusannya

hanya memiliki nilai 0 dan 1.

Model matematis untuk pemograman linier integer serupa dengan model

pemograman linier, perbedaannya hanya pada penambahan 1 kendala bahwa

variabelnya harus berupa bilangan bulat. Pada dasarnya integer programming

merupakan analisis pasca optimal pemrograman linier. Jika program linier

menghasilkan bilangan pecahan maka untuk mendapatkan bilangan bulat yang optimal

dilakukan dengan menggunakan integer linier programming (ILP).

Metode yang biasa diterapkan adalah metode percabangan dan pembatasan (branch

and bound) serta algoritma bidang pemotong (cutting plane). Menurut Taha (1996)

metode cutting plane tidak dapat digunakan secara efektif untuk memecahkan masalah

integer umum tetapi gagasan dari metode itu dapat meningkatkan efektivitas jenis

teknik pemecahan lainnya. Jadi, bila terdapat pilihan antara metode cutting plane dan

metode branch and bound, maka metode branch and bound umumnya terbukti lebih

baik.

2.3.3.1 Metode Branch and Bound

Menurut Siswanto (2006) metode branch and bound adalah sebuah metode untuk

menghasilkan penyelesaian optimal pemrograman linier yang menghasilkan variabel-

variabel keputusan bilangan bulat. Sesuai dengan namanya, metode ini membatasi

penyelesaian optimal yang akan menghasilkan bilangan pecahan dengan cara membuat

cabang batas atas dan bawah bagi masing-masing variabel keputusan yang bernilai

pecahan agar bernilai bulat sehingga setiap pembatasan akan menghasilkan cabang

baru.

Langkah-langkah penyelesaian masalah program linier menggunakan metode

cabang batas, yaitu :

1. Metode ini diawali dengan metode simpleks sampai terdapat penyelesaian optimal.

Kemudian untuk basis Xj* variabel yang nilainya real dirubah menjadi integer Xj

yang batasnya Xj*≤Xj≤Xj*+1. Tetapi karena range tersebut tidak memberikan

penyelesaian integer, maka konsekuensinya nilai integer Xj harus memenuhi salah

satu syarat dibawah ini: Xj≥Xj* atau Xj≤Xj*+1.

13

2. Kemudian persoalan pemrograman linier yang awal dengan kendala tambahan

Xj≥Xj* atau Xj≤Xj*+1 diselesaikan sampai diperoleh keadaan optimum. Dengan

demikian setiap Xj akan menghasilkan dua cabang yang berbeda, dengan nilai basis

dan nilai fungsi tujuan optimum yang berbeda. Basis yang sudah integer tetapi

menghasilkan nilai fungsi tujuan yang lebih rendah dari basis yang integer di

cabang lain, harus dibuang dan cabang tersebut tidak perlu dilanjutkan

penyelusurannya.

3. Nilai Xj yang integer lalu dimasukkan ke dalam basis sampai semua variabel basis

yang diinginkan menjadi integer, setiap Xj yang baru akan menghasilkan dua

cabang yang baru, kecuali cabang yang tidak fisibel. Cabang yang tidak fisibel

langsung dapat dibuang.

Dengan cara demikian akan dapat diketahui semua nlai variable basis yang integer

dan memberikan penyelesaian optimum yang fisibel.