PENERAPAN METODE KARMARKAR PADA KOMPUTER UNTUK OPTIMASI KEUNTUNGAN PRODUKSI

PENERAPAN METODE KARMARKAR PADA KOMPUTER UNTUK OPTIMASI KEUNTUNGAN PRODUKSI Rojali1 ABSTRACT To give output in the form of optimal advantage a reliable and careful calculations of some project exist in a company was needed list of some existing mathematical calculation methods, one of them is Karmarkar method. This Method has a special quality, that is a lower complexity compared to other linear programan, (e.g simplex method). Having lower complexity, time to look for optimal result becomes quicker. This method has been applied in the case of optimal advantage of production in a company. To get accurate result of in calculation, a computer program is used. Keywords: optimal, karmarkar method, computer program

ABSTRAK Untuk memberikan output berupa daftar keuntungan yang optimal dari kombinasi projek yang ada di dalam sebuah perusahaan dibutuhkan suatu perhitungan yang cermat dan andal. Dari beberapa metode perhitungan matematis yang ada, salah satunya adalah metode Karmarkar. Metode ini memiliki keunggulan berupa kompleksitas yang lebih rendah dibandingkan metode pemrograman linier lainnya (misal metode simplex). Dengan kompleksitas yang lebih rendah maka waktu untuk mencari hasil optimal menjadi lebih cepat. Metode telah diterapkan dalam hal optimasi keuntungan produksi di sebuah perusahaan. Agar mendapatkan hasil akurat dalam proses perhitungan, digunakan sebuah program komputer. Kata kunci: optimasi keuntungan, metoda karmarkar, program komputer

1

Jurusan Matematika, FMIPA, Universitas Bins Nusantara, Kampus Anggrek, Jln. Kebon Jeruk Raya No. 27, Jakarta Barat 11530, [email protected]

Penerapan Metode Karmarkar … (Rojali)

83

PENDAHULUAN Saat ini, Indonesia sedang mengadakan pembangunan di segala bidang, khususnya dalam bidang industri. Pengembangan industri diikuti oleh persaingan yang semakin ketat, baik dari produk lokal maupun impor. Oleh karena itu, industri di Indonesia harus memiliki daya saing sehingga dapat mempertahankan kelangsungan hidup serta kemajuan perusahaan. Untuk meningkatkan daya saing, setiap industri harus melakukan efisiensi, baik dalam hal biaya maupun dalam pemanfaatan sumber daya yang ada. Selain melakukan efisiensi, industri juga harus memanfaatkan setiap kesempatan yang ada sehingga menghasilkan keuntungan yang maksimal yang selanjutnya berguna bagi pengembangan usaha. Dengan kata lain, untuk memberikan hasil yang optimal, perusahaan harus mengambil alternatif terbaik dari setiap kendala yang dihadapi. Salah satu keputusan yang harus dilakukan oleh pihak perusahaan adalah melakukan pemilihan dari berbagai proyek yang ditawarkan kepada perusahaan. Perusahaan biasanya menghadapi penawaran proyek yang berbeda-beda setiap minggunya. Hal itu membuat pihak perusahaan harus melakukan pengambilan keputusan secara terus-menerus. Perkiraan atau pengalaman dalam pengambilan keputusan itu sangat sulit untuk memberikan hasil yang optimal, apalagi hal itu berhubungan dengan risiko yang cukup tinggi. Selain itu, pemilihan proyek berkaitan erat dengan penentuan tingkat produksi dari setiap jenis barang. Jika terjadi kesalahan dalam pemilihan mengakibatkan berkurangnya keuntungan, bahkan hilangnya kesempatan untuk memperoleh keuntungan yang optimal. Untuk mencapai keuntungan yang maksimal, suatu perusahaan menghadapi berbagai kendala yang disebabkan oleh setiap batasan yang ada, seperti jumlah sumber produksi, jenis produk yang beragam, kapasitas setiap sumber produksi untuk menghasilkan suatu jenis produk, dan target waktu dalam menghasilkan setiap jenis produk. Artikel membahas bagaimana input yang ada dari batasan tersebut dioptimalkan sehingga memberikan keuntungan produksi yang diselesaikan dengan bantuan program komputer, menggunakan metode Karmarkar.

METODE KARMARKAR Metode Karmarkar adalah salah satu metode yang dapat dipakai untuk penyelesaian masalah pemrograman linier. Kelebihan metode itu adalah kompleksitasnya yang lebih rendah jika

(

)

dibandingkan dengan metode lainnya (misal: metode simplex), yaitu O n3,5 L (Taha H.A, 2003), (Will M., 2003). Dengan tingkat kompleksitas yang lebih rendah, masalah pemrograman linier, khususnya yang melibatkan banyak variabel dapat diselesaikan dengan waktu yang lebih singkat. Metode Karmarkar dikembangkan oleh Karmarkar pada tahun 1984. Teknik pendekatan menuju hasil optimal dilakukan dari titik awal yang terletak di dalam himpunan feasible dan bergerak menuju vertex optimal yang memiliki nilai fungsi tujuan lebih kecil atau sama dengan nilai berhenti yang telah ditentukan di awal iterasi. Hal itu menyebabkan metode Karmarkar juga dikenal sebagai metode titik interior (Luenberger, 2003). Untuk menyelesaikan masalah Karmarkar dari masalah pemrograman linier bentuk standar, dilakukan langkah sebagai berikut (Bazarra, 2000).

84

Jurnal Mat Stat, Vol. 8 No. 1, Januari 2008: 83-93

Pertama, perubahan dari bentuk standar ke masalah artifisial Karmarkar. Diberikan masalah pemrograman linier dalam bentuk standar:

c T x, x ∈ R n Ax ≥ b x≥0

minimalkan dengan batasan

Kita dapat membuat bentuk dual yang ekuivalen yang dapat ditulis:

y ∈ Rn

maksimalka n

bT y,

denganbatasan

AT y ≤ c y≥0

Selanjutnya, dapat digunakan kriteria tambahan (kriteria slack dan surplus) untuk mengubah fungsi kendala: • Ax ≥ b ; x ≥ 0 → Ax − v = b ; x, v ≥ 0 •

AT y ≤ c ; y ≥ 0

AT y + u = c ; y , u ≥ 0

→

Dengan menggabungkan bentuk dual dan standar masalah artifisial Karmarkar sebagai berikut:

minimalkan

cT x − bT y

dengan batasan

Ax − v = b AT y + u = c x, y , u, v ≥ 0

Kedua, perubahan dari masalah artifisial Karmarkar ke bentuk kanonikal Karmarkar. Diberikan masalah artifisial Karmarkar sebagai berikut:

c T x, x ∈ R n Ax = b

minimalkan dengan batasan

x≥0 yang akan diubah ke bentuk kanonikal Karmarkar:

c′T y dengan batasan A′y = 0 minimalkan

eT y = 1 y≥0

dan A ∈ R

mxn

, A′ ∈ R

mx ( n +1)

, c ∈ R n , c ′ ∈ R n +1

Ambil titik a = [ a1 ,L , an ] yang merupakan titik interior tegas. T

Untuk mencari titik interior tegas, dapat dilakukan dengan cara: • Dari fungsi kendala pertidaksamaan ≥ Diketahui fungsi kendala sebagai berikut: Ax ≥ b , dimana x, b ∈ R n , B ∈ R mxn dan semua komponen matriks A ≥ 0.

[

]

Titik interior tegasnya adalah: x ∗ L x ∗ ∈ R n dan:


85

(

∗

x∗ = max x1 ,..., xm •

∗

) dan x

∗

i

bi + 1 untuk setiap 1 ≤ i ≤ m Ai ,1 + ... + Ai ,n

=

Dari fungsi kendala pertidaksamaan ≤ Diketahui fungsi kendala sebagai berikut: Ax ≤ b , dimana x, b ∈ R n , B ∈ R mxn dan semua komponen matriks A ≥ 0.

[

]

Titik interior tegasnya adalah: x ∗ L x ∗ ∈ R n dan:

(

∗

∗

)

∗

x∗ = min x1 ,..., xm dan xi =

bi 1 . untuk setiap 1 ≤ i ≤ m Ai ,1 + ... + Ai ,n 2

Misal T = [T1 ,L , Tn +1 ] transformasi proyeksi ke dalam Simplex Δ dalam R n +1 dan: T

xi ai , untuk 1 ≤ i ≤ n x1 a1 + L + xn an + 1

Ti ( x ) =

1 , untuk i = n + 1 x1 a1 + L + xn an + 1

Nilai y pada bentuk kanonikal Karmarkar merupakan fungsi transformasi dari x atau dapat ditulis: y = T ( x ) Untuk menghitung A′ , untuk i = 1, ..., n , kolom ke–i dari A′ sama dengan ai dikalikan dengan kolom ke-i dan sama dengan –b untuk kolom ke–(n+1) dari A′ , atau dapat ditulis:

A ' j ,i =

ai . Aj ,i , untuk 1 ≤ i ≤ n , 1 ≤ j ≤ m -bi , untuk i = n + 1 , 1 ≤ j ≤ m

Untuk menghitung c′ dapat dilakukan sebagai berikut:

c 'i ( x ) =

ai ci , untuk 1 ≤ i ≤ n 0 , untuk i = n + 1

Sedangkan untuk pusat Simplex Δ , a' = T ( a ) = e ( n + 1) = [1 n + 1,L ,1 n + 1]

T

a' ∈

dan

n+1

Untuk mengembalikan nilai hasil algoritma Karmarkar dari bentuk kanonikal Karmarkar ke bentuk standar maka dilakukan transformasi invers dari T, yaitu: T

−1 −1 T −1 = ⎡⎣T1 ,L , Tn ⎤⎦ , dimana Ti −1 ( y ) = ai yi yn +1

Ketiga, melakukan iterasi ke titik optimal dari bentuk kanonikal Karmarkar. Untuk menyelesaikan masalah pemrograman linier yang sudah dalam bentuk kanonikal Karmarkar:

minimalkan cT x dengan batasan Ax = 0 eT x = 1 x≥0

86


maka dilakukan langkah sebagai berikut: • Inisialisasi.

k =0

x( ) = a 0 = e n 0

•

Melakukan update. ¾ Hitung matriks: ⎡ x1( k ) L 0 ⎤ ⎢ ⎥ Dk = ⎢ M O M ⎥ ⎢ (k ) ⎥ ⎣ 0 L xn ⎦ ⎡ AD ⎤ Bk = ⎢ T k ⎥ ⎣ e ⎦

¾ Hitung proyektor orthogonal ke ruang B k :

Pk = I m +1 − B k

T

(B B ) T

k

k

−1

Bk

¾ Hitung proyeksi orthonormal dari c ke ruang B k : k cˆ ( ) =

Pk Dk c Pk Dk c

¾ Hitung vektor arah k k d( ) = − r cˆ ( )

n ( n − 1)

dan r = 1 ¾ Hitung x

x(

k +1)

( k +1)

= a0 + α d(

k)

dan nilai α adalah nilai langkah yang telah ditetapkan sebelumnya, dalam paper-nya Karmarkar merekomendasikan nilai α = 0,25 ¾ Hitung nilai x

x

( k +1)

=U

−1 k

( k +1)

menggunakan transformasi invers U k−1 :

Dk x (

k +1)

( x ) = e D x( ( k +1)

T

k +1)

k

• •

Periksa kriteria berhenti. Jika kondisi cT x ≤ 10- q terpenuhi maka iterasi dihentikan. Iterasi.

k = k +1

Lalu kembali ke langkah b) ( Chong, 1996; Bazarra, 2000)

PROGRAM KOMPUTER Untuk mendapatkan hasil yang akurat, dalam proses perhitungannya digunakan sebuah program komputer. Program komputer optimasi produksi ini dibangun sesuai dengan model perancangan perangkat lunak Waterfall model, yaitu analisis dan penentuan kebutuhan, desain sistem, implementasi dan pengujian, integrasi dan pengujian sistem, serta pengoperasian dan pemeliharaan (Pressman, 2003). Program itu dibuat menggunakan bahasa pemrograman Delphi 6 dengan beberapa modul program, antara lain sebagai berikut.


87

• • • • •

• • • •

88

Modul Inisialisasi Modul itu digunakan untuk memasukkan jumlah proyek dan jumlah sumber produksi. Modul Input Proyek Modul itu digunakan untuk memasukkan jenis dan jumlah barang yang akan diproduksi dan target waktu dari masing-masing proyek yang ditawarkan ke dalam tabel data proyek. Modul Input Kapasitas Modul itu digunakan untuk memasukkan besar kapasitas produksi dari masing-masing sumber untuk setiap jenis barang yang akan diproduksi ke dalam tabel data kapasitas. Modul Input Keuntungan Modul itu digunakan untuk memasukkan besar keuntungan produksi dari masing-masing sumber untuk setiap jenis barang yang akan diproduksi ke dalam tabel data keuntungan. Modul Optimalisasi Modul itu digunakan untuk melakukan perhitungan optimalisasi, mulai dari mengubah data mentah ke dalam masalah pemrograman linier dalam bentuk standar, mengubah dari bentuk standar ke bentuk kanonikal Karmarkar, lalu melakukan perhitungan dan iterasi menggunakan algoritma Karmarkar. Modul Lihat Data Modul itu digunakan untuk menampilkan semua data yang dimasukkan dalam modul input. Modul Lihat Hasil Modul itu digunakan untuk menampilkan hasil optimalisasi, terdiri atas keuntungan maksimal dari setiap kombinasi proyek yang ada dalam bentuk tabel. Modul Detail Modul itu digunakan untuk menampilkan detail penjadwalan produksi secara sederhana dari suatu kombinasi proyek dalam bentuk tabel. Modul Bentuk Pemrograman Linier Modul itu digunakan untuk menampilkan masalah pemrograman linier (fungsi tujuan dan fungsi kendala) dari suatu kombinasi proyek dalam bentuk umum dan dalam bentuk kanonikal Karmarkar.


Untuk proses perhitungan secara keseluruhan, dapat dilihat pada state transition diagram, seperti pada Gambar 1.

Mod ul fo rm _utam a

Klik tombol inisialisas i Pang gil modul inisialisas i

M odul inisia lisasi Klik tom bol input ke untun gan Klik tom bol input proyek Panggil m odul input_proyek

Pang gil m odul inp ut_ke untung an

Klik tom bol input kapa sitas Panggil m odul input_kapas itas

Mo dul input_proye k

M odul input_kapa sitas

Modu l in put_k euntu ngan

Klik tom bol lakukan optim asi

Klik to mbol laku kan o ptima si

Panggil m odul optimasi

Panggil m odul o ptima si Klik tom bol lakuka n optimasi Panggil m odul optimasi M odul optim asi

Proses optim asi selesai Panggil m odul hasil

Klik tombo l lihat d ata Panggil mo dul liha t_data Mo dul liha t_data

Modu l lihat_hasil Klik to mbol lihat has il

Klik tom bol lihat data

Pan ggil modu l lihat_hasil

Panggil m odul lihat_data

Klik to mbol lihat bentuk PL

Klik tombo l lihat s im pan hasil Klik tom bol lihat simpa n has il

Panggil m odul simp an ha sil

Klik tombo l lihat d etail

Panggil mo dul bentuk_PL

Panggil m odul detail

Pang gil modul sim pan hasil M odul detail

M odul bentuk_PL

Mo dul simpa n_hasil

Klik m enu Pangg il m odul menu_ click

Mod ul me nu_click

Gambar 1 State Transition Diagram Modul Form_Utama


89

M odul m enu_click

Sub m enu file

Sub m enu H elp

Input D ata Proyek

Ne w

Ex it

Set Ka rm arkar

Klik N ew

H elp Topics

Klik Set Karm ark ar Tam pil Form Set_Karm arkar

Panggil m odul form_utam a Klik Exit Keluar dari program

Mod ul fo rm _utam a

About

Klik H elp Top ics Tam pil Form H elp

Form Set_ Ka rm arkar

Form H elp

Klik Ab out Load

Tam pil Form Abo ut

Save

Klik Lo ad Pang gil modul load_input

Akhir Program

Klik Save Pang gil modul save_ inpu t

Form About Klik O k / Tutup Form Set_ Ka rm arkar

Klik O k / Tu tup Form About Tam pil La yar Aktif

Tam pil Layar Aktif M odul load_input

Tutu p Form H elp Tam pil Layar Aktif

M odul save_ inpu t

L ayar Aktif

Gambar 2 State Transition Diagram Modul menu_click

STUDI KASUS DAN PEMBAHASAN Untuk melakukan analisis terhadap program yang telah dibuat, dilakukan implementasi pada contoh kasus dari pabrik GARMENT yang datanya diambil pada awal bulan januari 2007 sebagai berikut. a. Jumlah Proyek: 4 buah, Jumlah Sumber Produksi: 2 kelompok, yaitu karyawan lama dan karyawan baru. b. Data proyek yang diterima: Tabel 1 Tabel Proyek Kasus pabrik GARMENT Kapasitas Jenis Barang

Lama Waktu (minggu)

Sumber 1 (Unit)

Sumber 2 (Unit)

Sumber 1 (Rupiah)

Sumber 2 (Rupiah)

Proyek 1

Kemeja

8000

4

1800

1200

3000

2500

Proyek 2

Celana Pendek

5000

4

1300

700

5000

4500

Proyek 3

Jaket A

500

2

450

300

15000

15000

Proyek 4

Jaket B

500

3

400

250

16000

16000

Proyek

90

Keuntungan

Jumlah Barang (Unit)


Setelah user menekan tombol [Lakukan Optimalisasi] maka terjadi proses perhitungan optimasi menggunakan metode Karmarkar, dan dipakai nilai α = 0.25 dan nilai q = 7 (error lebih kecil dari 0,0000007). Setelah proses perhitungan selesai, akan terlihat tabel hasil optimasi yang berisi pasangan kombinasi proyek dan keuntungan optimal sebagai berikut. Beberapa hasil hitungan dengan program, dapat dilihat pada Gambar 3.

Gambar 3 Hasil Hitungan dengan Program

Gambar 4 Hasil Hitungan dengan Program


91

Ringkasan hasil program dapat dilihat dalam Tabel 2, Tabel 3, dan Tabel 4. Tabel 2 Tabel Hasil Optimalisasi Kasus pabrik GARMENT Kombinasi Proyek

Keuntungan Optimal

Kombinasi Proyek

Keuntungan Optimal

Proyek 1

23599974.557

Proyek 2 - 4

32999862.854

Proyek 2

24999975.041

Proyek 3 - 4

15499963.843

Proyek 3

7500202.113

Proyek 1 - 2 - 3

40330409.637

Proyek 4

8000203.135

Proyek 1 - 2 - 4

39830421.888

Proyek 1 - 2

37830710.463

Proyek 1 - 3 - 4

37849310.494

Proyek 1 - 3

31099710.433

Proyek 2 - 3 - 4

40328553.047

Proyek 1 - 4

31599719.759

Proyek 1 - 2 - 3 - 4

41863931.139

Proyek 2 - 3

32499861.350

Tabel 3 Tabel Detail Kombinasi Proyek 2 - 3 - 4 Kasus pabrik GARMENT Proyek & Sumber \ Waktu

Minggu 0 s/d 2

Minggu 2 s/d 3

Minggu 3 s/d 4

Sumber 1

2306.742

1050.937

1299.902

Sumber 2

0.082

0.082

342.234

Sisa

0.022

Proyek 2

Proyek 3 Sumber 1

0.529

0

0

Sumber 2

499.467

0

0

Sisa

0.005

Proyek 4 Sumber 1

89.732

76.605

0

Sumber 2

83.718

249.941

0

Sisa

0.004

Tabel 4 Tabel Detail Kombinasi Proyek 1 - 2 - 3 – 4 Proyek & Sumber \ Waktu

Minggu 0 s/d 2

Minggu 2 s/d 3

Minggu 3 s/d 4

Proyek 1 Sumber 1

0.084

0.084

0.084

Sumber 2

0.052

0.052

614.606

Sisa

7385.038

Proyek 2 Sumber 1

2307.814

1050.524

1299.922

Sumber 2

0.03

0.03

341.466

Sisa

0.214

Proyek 3 Sumber 1

0.044

0

0

Sumber 2

499.933

0

0

Sisa

0.022

Proyek 4 Sumber 1

89.837

76.738

0

Sumber 2

83.361

249.974

0

Sisa

92

0.089


Dengan mempertimbangkan hasil optimalisasi yang dihasilkan program dan detail dari masing-masing kombinasi proyek, pihak pabrik GARMENT memilih untuk mengerjakan proyek 2 – 3 – 4, dengan keuntungan sebesar Rp. 40,328,553.05. Mengapa tidak memilih proyek 1-2-3-4, karena jika memilih kombinasi proyek tersebut berdasarkan Tabel 4 proyek 1 akan diperlukan sumber baru untuk menyelesaikan proyek masih terdapat sisa 7385 unit kemeja yang belum bisa dipenuhi produksinya dengan sumber yang ada.

PENUTUP Contoh penerapan kasus tersebut memperlihatkan bahwa program aplikasi ini telah dapat menghitung keuntungan produksi maksimal suatu perusahaan dengan batasan dan berbagai kendala yang ada, dengan tingkat akurasi perhitungan tinggi ( q=7 atau error kecil dari 0,0000007). Dengan program ini dapat menentukan keuntungan produksi yang optimal.

DAFTAR PUSTAKA Bazarra, MS., JJ. Jarvis, and HD. Sherali. 2000. Linear Programming and Network Flows. 2nd Ed. Chong, EKP and Zak, Sh. 1996. An Introduction to Optimization. New York: John Wiley & Sons, Inc. Luenberger, DG. 2003. Linear and Nonlinear Programming. 2nd Ed. Massachusetts: Addison Wesley Publishing Company. Paul Tseng, 1988. “A Very Simple Polynomial-Time Algorithm for Linear Programming“. Diakses dari http://dspacemit.edu/bitstream/1721.1/3091/1/P-1818-19107243.pdf. Pressman, RS. 2004. Software Engineering: A Practioner’s Approach. 5th Ed. Singapore: McGrawHill Companies, Inc. Taha, HA. 2003. Operation Research: An Introduction. 7th ed. New Jersey: Pearson Education, Inc. Wil Michiels, Jan Korst, Emile Aarts, Jan Van Leeuwen. 2003. “Performance Ratios for the Karmarkar-Karp Differencing Method”. Diakses dari http://alexandria.tue.nl/extra1/wskrap/publichtml/200217.pdf.


93

PENERAPAN METODE KARMARKAR PADA KOMPUTER UNTUK OPTIMASI KEUNTUNGAN PRODUKSI

Recommend Documents