Saintia Matematika Vol. XX, No. XX (XXXX), pp. 17–24.
OPTIMASI PROGRAM LINIER PECAHAN DENGAN FUNGSI TUJUAN BERKOEFISIEN INTERVAL
M Khahfi Zuhanda, Syawaluddin, Esther S M Nababan
Abstrak. Beberapa tahun belakangan, telah ditemukan beberapa cara untuk menyelesaikan kasus program linier. Salah satunya adalah progam linier pecahan (PLP). Pada beberapa masalah aplikasi program linier (PL), koefisien pada model seringkali tidak bisa ditentukan secara tepat. Salah satu metode dalam menyelesaikan masalah ini adalah dengan menggunakan pendekatan interval, dimana koefisien tak tentu tersebut diubah menjadi bentuk interval. Program linier pecahan dengan fungsi tujuan berkoefisien interval dapat diselesaikan dengan transformasi yang diperkenalkan oleh Charnes dan Cooper. Metode ini menggunakan kombinasi titik awal dan akhir dari interval yang digunakan sebagai pengganti koefisien selang interval. Hasil kajian ini menunjukkan bahwa persoalan optimasi program linier pecahan dengan koefisien interval dapat ditransformasikan ke dalam bentuk linier dengan menggunakan transformasi Charnes dan Cooper.
Received dd-mm-yyyy, Accepted dd-mm-yyyy. 2013 Mathematics Subject Classification: 62M10 Key words and Phrases: Transformasi Charnes-Cooper, Program Linier Pecahan
1
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
2
1. PENDAHULUAN Dalam beberapa tahun terakhir, para pakar matematika telah banyak mencoba melakukan pendekatan untuk memecahkan permasalahan Program Linier Pecahan (PLP). Dalam tulisan ini akan menjelaskan Program Linier Pecahan merupakan salah satu kasus khusus dari pemrograman non linier, yang umumnya digunakan untuk masalah-masalah kehidupan nyata dengan pemodelan satu atau lebih tujuan seperti keuntungan /biaya, aktual pendapatan / standarisasi, input / karyawan, dan lain-lain. Dan itu diterapkan untuk berbagai disiplin ilmu seperti sebagai teknik, bisnis, keuangan, ekonomi, dan lain-lain. Pemrograman Linier Pecahan (PLP) adalah kelas khusus dari pemrograman non linier yang dapat ditransformasikan menjadi masalah pemrograman linier dengan metode Charnes dan Cooper[8]. Program Linear adalah suatu cara untuk menyelesaikan persoalan pengalokasian sumber-sumber yang terbatas di antara beberapa aktivitas yang bersaing dengan cara terbaik yang mungkin dilakukan. Misalnya pengalokasian fasilitas produksi, sumber daya nasional untuk kebutuhan domestik, penjadwalan produksi dan lain-lain[2]. Pada beberapa masalah aplikasi pemrograman linier (PL), koefisien pada model seringkali tidak bisa ditentukan secara tepat. Salah satu metode dalam menyelesaikan masalah PL ini adalah dengan menggunakan pendekatan interval, dimana koefisien tak tentu tersebut diubah menjadi bentuk interval. Bentuk PL ini dinamakan Linear Programming with Interval Coefficient (LPIC). Koefisien berbentuk interval menandakan perluasan toleransi (atau daerah) dimana parameter konstanta bisa diterima dan memenuhi model LPIC. Masalah LPIC memiliki fungsi objektif dan kendala persamaan atau pertidaksamaan yang berkoefisien interval [4]. Solusi optimum dibagi menjadi dua, yaitu best optimum dan worst optimum. Dalam kasus minimisasi, best optimum adalah solusi yang memiliki nilai fungsi objektif terkecil, sedangkan worst optimum adalah solusi yang memiliki nilai fungsi objektif terbesar. Solusi optimum pada LPIC didapatkan dengan mencari versi khusus dari fungsi objektif dan kendala yang mengoptimumkan model, yaitu dipilih suatu nilai spesifik (nilai ekstrim) pada koefisien interval yang membuat model LPIC tersebut optimum, sehingga pemecahan masalah LPIC diperoleh dengan menyelesaikan PL yang mengoptimumkan model LPIC[5].
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
3
2. LANDASAN TEORI Program Linier merupakan suatu teknik perencanaan yang menggunakan model matematika dengan tujuan menemukan beberapa kombinasi alternatif dari pemecahan masalah yang kemudian dipilih mana yang terbaik untuk menyusun strategi dan langkah-langkah kebijakan tentang alokasi sumber daya yang ada agar mencapai tujuan atau sasaran yang diinginkan secara optimal dengan melibatkan variabel-variabel linear. Dalam model program linear dikenal dua macam fungsi, yaitu fungsi objektif (objective function) dan fungsi kendala (constraint function) yang linear. Winston, W.L, 2003. Operations Research: Applications and Algorithms, menyatakan bahwa bentuk umum model program linier adalah sebagai berikut: M aksimumkan (minimumkan) Kendala
Z = c1 x1 + c2 x2 + ... + cj xj
a11 x1 + a12 x2 + ... + a1j xj ≤ b1 a21 x1 + a22 x2 + ... + a2j xj ≤ b2 .. .. .. . . . ai1 x1 + ai2 x2 + ... + aij xj ≤ bi xj ≥ 0, untuk j = 1, 2, ..., m dan i = 1, 2, ..., n
Dimana : xj cj aij bi
= = = =
Variabel keputusan ke-j. Koefisien fungsi objektif (KFO) dari variabel keputusan ke-j. Koefisien teknologi dari variabel keputusan ke-j pada kendala ke-i. Koefisien ruas kanan pada kendala ke-i
Program Linier Pecahan merupakan kelas khusus dari progam non linier. Charnes dan Cooper [3] memperkenalkan transformasinya untuk mengubah bentuk non linier program linier pecahan kebentuk program linier. Dimana fungsi penyebutnya adalah bernilai 1. Setelah di transformasikan maka fungsi penyebutnya dimasukkan kedalam fungsi kendala. Bentuk umum masalah program linier pecahan adalah sebagai berikut: M aksimumkan Kendala
Z=
a1 x1 + a2 x2 + ... + ak xk + ak+1 c1 x1 + c2 x2 + ... + ck xk + ck+1
A1 x1 + ... + Ak xk ≤ b x1 ≥ 0, ..., xk ≥ 0
(1)
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
4
dimana Ai adalah matriks 1 x m, untuk i = 1, . . . , k dan b adalah m-dimensi konstanta vektor kolom. Maka itu, diasumsikan bahwa: c1 x1 + c2 x2 + · · · + ck xk + ck+1 ≥ 0 untuk semua xT = (x1 , . . . , xk ) ∈ X, Dimana X hasil daerah feasible dari persamaan (1). Untuk menyelesaikan persamaan (1). Transformasi Charnes-Chooper menetapkan untuk: Z=
1 c1 x1 + c2 x2 + ... + ck xk + ck+1
c1 x1 z + c2 x2 z + ... + ck xk z + ck+1 z x1 ≥ 0, ..., xk ≥ 0, z ≥ 0 Sehingga, persamaan (1) ditransformasikan kedalam permasalahan program linier: M aksimumkan Kendala
Z=
a1 x1 + a2 x2 + ... + ak xk + ak+1 c1 x1 + c2 x2 + ... + ck xk + ck+1
A1 x1 + ... + Ak xk ≤ b x1 ≥ 0, ..., xk ≥ 0
(2)
1 Dengan diasumsikan variabel yi = xi c1 x1 +c2 x2 +...+c = xi z untuk k xk +ck+1 i = 1, . . . , k, persamaan (2) dapat direduksi menjadi :
M aksimumkan Kendala
Z = a1 y1 + a2 y2 + ... + ak yk + ak+1 z A1 y1 + ... + Ak yk ≤ bz c1 y1 + c2 y2 + ... + ck yk + ck+1 z = 1 y1 ≥ 0, ..., yk ≥ 0, z ≥ 0
(3)
Pada beberapa masalah aplikasi pemrograman linier (PL), koefisien pada model seringkali tidak bisa ditentukan secara tepat. Salah satu metode dalam menyelesaikan masalah PL ini adalah dengan menggunakan pendekatan interval, dimana koefisien tak tentu tersebut diubah menjadi bentuk interval [1].
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
5
3. METODE PENELITIAN Penelitian ini bersifat studi literatur yang disusun berdasarkan rujukan pustaka dengan langkah-langkah sebagai berikut: 1. Melakukan studi keperpustakaan dengan mengumpulkan bahan yang merujuk pada tulisan ini. 2. Menjelaskan prosedur untuk mereduksi program linier pecahan dengan fungsi tujuan berkoefisien interval. 3. Menyelesaikan contoh numerik permasalahan dalam program linier pecahan dengan fungsi tujuan berkoefisien interval. 4. PEMBAHASAN Program Linier Pecahan (PLP) adalah generalisasi dari Program Linier (PL). Fungsi tujuan dari program linier berbentuk fungsi linier, sedangkan fungsi tujuan dalam program linier pecahan merupakan rasio dari dua fungsi linier. Program linier pecahan merupakan menjadi kelas khusus dari program linier. Dikatakan kelas khusus karena program linier pecahan dapat ditransformasikan kedalam bentuk linier dimana fungsi penyebut pada fungsi tujuan program linier pecahan bernilai 1 dan persamaan penyebut dalam fungsi tujuan dimasukkan kedalam persamaan fungsi kendala. Program linier dan program linier pecahan merupakan masalah optimasi yang menggunakan persamaan dan pertidaksamaan linier dan masingmasing persoalannya memiliki daerah feasible. Pada umumnya, program linier menghitung kebijakan untuk mencari laba maksimum atau biaya minimum. Sedangkan pada program linier pecahan digunakan untuk menghitung rasio efisiensi optimal seperti keuntungan/biaya. Program linier pecahan bertujuan mencari rasio dari 2 buah fungsi tujuan dalam program linier untuk mendapatkan hasil yang optimal. Pada beberapa masalah aplikasi program linier, koefisien pada model seringkali tidak bisa ditentukan secara tepat. Jadi dalam kasus seperti itu, jauh lebih baik untuk memilih koefisien sebagai interval bukan merupakan angka tetap. Sebagai contoh salah satu dari situasi ini terjadi ketika koefisien bilangan fuzzy. Dalam kasus ini jika pengambil keputusan menetapkan α-tingkat kepuasan, maka bilangan fuzzy diubah menjadi interval. Oleh karena itu, dalam berbagai situasi seperti itu untuk menyelesaikan permasalahan dalam bentuk pemrograman matematika dengan koefisien interval [1].
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
6
Sehingga permasalahan optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval merupakan kombinasi persoalan program linier pecahan dengan program linier dengan koefisen interval. Sehingga persamaan persoalan tersebut dapat dituliskan menjadi: M aksimumkan Kendala
Z=
[a1 , b1 ]x1 + [a2 , b2 ]x2 + ... + [aj , bk ]xj + [aj+1 , bj+1 ] [c1 , d1 ]x1 + [c2 , d2 ]x2 + ... + [cj , dk ]xj + [cj+1 , dj+1 ]
A1 x1 + ... + Aj xj ≤ b x1 ≥ 0, ..., xj ≥ 0, untuk(j = 1, 2, 3, ..., n)
(4)
Untuk menyelesaikan permasalahan ini diasumsikan bahwa [c1 , d1 ]x1 + [c2 , d2 ]x2 + · · · + [ck , dk ]xj + [ck+1 , dk+1 ] ≥ 0 untuk semua xT = (x1 , , xk ) ∈ X, dimana X adalah daerah feasible kompak. Untuk menyelesaikan persamaan (4), diasumsikan variabel M aksimumkan
Z = [a1 , b1 ]x1 t + [a2 , b2 ]x2 t + ... + [ak , bk ]xj t + [ak+1 , bk+1 ]t
Kendala
A1 x1 t + ... + Ak xk t ≤ bt [c1 , d1 ]x1 t + [c2 , d2 ]x2 t + ... + [ck , dk ]xk t + [ck+1 , dk+1 ]t = 1 x1 ≥ 0, ..., xk ≥ 0, t ≥ 0 (5)
Dengan diasumsikan variabel 1 = xi t untuk i = 1, . . . , k, ui = xi [c1 ,d1 ]x1 +[c2 ,d2 ]x2 +···+[c k ,dk ]xj +[ck+1 ,dk+1 ] persamaan (5) dapat di reduksi menjadi: M aksimumkan
Z = [a1 , b1 ]u1 + [a2 , b2 ]u2 + ... + [ak , bk ]uk + [ak+1 , bk+1 ]t
Kendala
A1 u1 + ... + Ak uk ≤ bt [c1 , d1 ]u1 + [c2 , d2 ]u2 + ... + [ck , dk ]uk + [ck+1 , dk+1 ]t = 1 u1 ≥ 0, ..., uk ≥ 0, t ≥ 0 (6)
Kombinasi linier dari masing-masing daerah interval mengikuti persamaan: M aksimumkan
Kendala
Z = [α1 a1 + (1 − α1 )b1 ]u1 + [α2 a2 + (1 − α2 )b2 ]u2 + ...+ [αk ak + (1 − αk )bk ]uk + [αk+1 ak+1 + (1 − αk+1 )bk+1 ]t A1 u1 + ... + Ak uk − bt ≤ 0 [β1 c1 + (1 − β1 )d1 ]u1 + [β2 c2 + (1 − β2 )d2 ]u2 + ... + [βk ck
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
7
+(1 − βk )dk ]uk + [βk+1 ck+1 + (1 − βk+1 )dk+1 ]t = 1 u1 ≥ 0, ..., uk ≥ 0, t ≥ 0, 0 ≤ αi ≤ 1, ..., 0 ≤ βi ≤ 1, untuk i = 1, ..., k + 1
(7)
Dari persamaan (7). Pada fungsi kendala dapat di reduksi menjadi: [β1 c1 + (1 − β1 )d1 ]u1 + ... + [βk ck + (1 − βk )dk ]uk + [βk+1 ck+1 + (1 − βk+1 )dk+1 ]t = 1 [β1 c1 u1 + β1 d1 u1 + ... + βk ck u1 + dk uk − βk dk uk + βk+1 ck+1 t + dk+1 t − βk+1 dk+1 t] = 1 [β1 c1 u1 + β1 d1 u1 ] + ... + [βk ck u1 + βk dk uk ] + [βk+1 ck+1 t− βk+1 dk+1 t] + d1 u1 + ... + dk uk + dk+1 t = 1 [β1 u1 (c1 − d1 ) + ... + βk uk (ck − dk ) + βk+1 t (ck+1 − dk+1 )] + d1 u1 + ... + dk uk + dk+1 t = 1
(8)
Karena, uj ≥ 0 untuk j = 1, . . . , k, t ≥ 0, 0 ≤ βi ≤ 1, (di − ci ) ≥ 0 untuk i = 1, . . . , k + 1 Oleh karena itu persamaan (8) dapat ditulis: 1 ≤ 1 + [β1 u1 (d1 − c1 ) + ... + βk uk (dk − ck ) + βk+1 t(dk+1 ck+1 )] ≤ 1 + u1 (d1 − c1 ) + ... + uk (dk − ck ) + t(dk+1 − ck+1 )]
(9)
Dengan mengkombinasikan persamaan (8) dan (9) menghasilkan: 1 ≤ d1 u1 + ... + dk uk + dk+1 t ≤ 1 + u1 (d1 − c1 ) + ... + uk (dk ck ) + t(dk+1 − ck+1 )(10) Yang selanjutnya direduksi menjadi: d1 u1 + ... + dk uk + dk+1 t ≥ 1
(11)
c1 u1 + ... + ck uk + ck+1 t ≤ 1
(12)
Dan
Oleh karena itu, dengan menggunakan persamaan (11) dan (12), persamaan (7) ditransformasikan kedalam persamaan berikut: M aksimumkan
Z = [α1 a1 + (1 − α1 )b1 ]u1 + [α2 a2 + (1 − α2 )b2 ]u2 + ...+
8
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
[αk ak + (1 − αk )bk ]uk + [αk+1 ak+1 + (1 − αk+1 )bk+1 ]t Kendala
c1 u1 + ... + ck uk + ck+1 t ≤ 1 d1 u1 + ... + dk uk + dk+1 t ≥ 1 A1 u1 + ... + Ak uk − bt ≤ 0 u1 ≥ 0, ..., uk ≥ 0, t ≥ 0, 0 ≤ αi ≤ 1 untuk i = 1, ..., k + 1
(13)
Jika (u1 , . . . , uk , t) menjadi titik daerah feasible dari persamaan (13), dengan 0 ≤ αi ≤ 1, (ai − bi ) ≤ 0 untuk i = 1, . . . , k + 1, maka fungsi objektif dalam persamaan (13) dapat ditulis sebagai: α1 u1 (a1 − b1 ) + · · · + αk uk (ak − bk ) + αk+1 t(ak+1 − bk+1 )] + b1 u1 + · · · + bk uk + bk+1 t ≥ u1 (a1 − b1 ) + · · · + uk (ak − bk ) + t(ak+1 − bk+1 )] + b1 u1 + · · · + bk uk + bk+1 t = a1 u1 + · · · + ak uk + ak+1 t Persamaan diatas membuktikan bahwa a1 , a2 , , ak+1 merupakan batas bawah dari koefisien interval pada fungsi tujuan. Maka worst optimum pada persamaan fungsi tujuan adalah Z = a1 u1 + · · · + ak uk + ak+1 t Sehingga bentuk transformasi optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval adalah M aksimumkan Kendala
Z = a1 u1 + ... + ak uk − ak+1 t c1 u1 + ... + ck uk + ck+1 t ≤ 1 d1 u1 + ... + dk uk + dk+1 t ≥ 1 A1 u1 + ... + Ak uk − bt ≤ 0 u1 ≥ 0, ..., uk ≥ 0, t ≥ 0, untuk k = 1, ..., m
Sedangkan untuk memperoleh best optimum maka diambil batas atas dari koefisien interval pada fungsi tujuan. Sehingga bentuk transformasi optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval adalah M aksimumkan Kendala
Z = b1 u1 + ... + bk uk − bk+1 t c1 u1 + ... + ck uk + ck+1 t ≤ 1 d1 u1 + ... + dk uk + dk+1 t ≥ 1 A1 u1 + ... + Ak uk − bt ≤ 0 u1 ≥ 0, ..., uk ≥ 0, t ≥ 0, untuk k = 1, ..., m
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
9
Berikut akan dibuktikan bahwa Program linier pecahan dengan fungsi tujuan berkoefisien interval dibawah ini sama dengan metode Charnes-Cooper. M aksimumkan Kendala
Z=
[a1 , a1 ]x1 + [a2 , a2 ]x2 + ... + [ak , ak ]xj + [ak+1 , ak+1 ] [c1 , c1 ]x1 + [c2 , c2 ]x2 + ... + [ck , ck ]xj + [ck+1 , ck+1 ]
A1 x1 + ... + Ak xk ≤ b x1 ≥ 0, ..., xk ≥ 0 (k = 1, ..., m) dan (j = 1, ..., n)
Bukti : Karena koefisien interval pada pembilang fungsi tujuan memiliki nilai yang sama. Nilai koefisien fungsi tujuan pada best optimum dan worst optimum adalah sama. Maka persoalan optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval diatas dapat ditransformasikan menjadi: M aksimumkan Kendala
Z = a1 u1 + ... + ak uk + ak+1 t c1 u1 + ... + ck uk + ck+1 t ≤ 1 c1 u1 + ... + ck uk + ck+1 t ≥ 1 A1 u1 + ... + Ak uk − bt ≤ 0 u1 ≥ 0, ..., uk ≥ 0, t ≥ 0, untuk k = 1, ..., m
Karena koefisien ruas kiri persamaan pertama dan kedua pada fungsi kendala sama, Maka persamaan pertama dan kedua dikombinasikan, sehingga diperoleh persamaan program liniernya menjadi: M aksimumkan Kendala
Z = a1 u1 + ... + ak uk + ak+1 t c1 u1 + ... + ck uk + ck+1 t = 1 A1 u1 + ... + Ak uk − bt ≤ 0 u1 ≥ 0, ..., uk ≥ 0, t ≥ 0, untuk k = 1, ..., m
Sehingga terbukti bahwa optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval sesuai dengan bentuk transformasi yang diperkenalkan oleh Charnes dan Cooper [1] Contoh Kasus : PT Sayang Anak memproduksi dua jenis mainan yang terbuat dari kayu yang berupa boneka dan kereta api. Boneka dijual dengan harga Rp 27.000
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
10
- 35.000/ lusin yang setiap lusinnya memerlukan biaya material sebesar Rp 10.000-14.000 serta biaya tenaga kerja sebesar Rp 14.000-16.000. Kereta api yang dijual seharga Rp 21.000 -30.000/ lusin memerlukan biaya material sebesar Rp 9.000-12.000 dan biaya tenaga kerja Rp 10.000-13.000. Apabila perusahan dikenai pajak pembuatan sekitar Rp 5000-8000. Untuk membuat boneka dan kereta api ini diperlukan dua kelompok tenaga kerja, yaitu tukang kayu dan tukang poles. Setiap lusin boneka memerlukan 2 jam pemolesan dan 1 jam pekerjaan kayu, sedangkan setiap lusin kereta api memerlukan 1 jam pemolesan dan 1 jam pekerjaan kayu. Meskipun pada setiap minggunya perusahaan ini dapat memenuhi seluruh material yang diperlukan, jam kerja yang tersedia hanya 100 jam untuk pemolesan dan 80 jam untuk pekerjaan kayu. Dari pengamatan pasar selama ini dapat dikatakan bahwa kebutuhan akan kereta api tidak terbatas, tetapi untuk boneka tidak lebih dari 40 lusin yang terjual setiap minggunya. Bagaimanakah formulasi dari persoalan di atas untuk mengetahui berapa lusin jenis mainan masingmasing yang harus dibuat setiap minggu dengan mengoptimalkan efisiensi biaya ? (dikutip dari Buulolo, 2005; dengan modifikasi) Solusi: P endapatan/minggu Ongkosmaterial/minggu Ongkostenagakerja/minggu P ajak
= = = =
[27, 35]x1 + [21, 30]x2 [10, 14]x1 + [9, 12]x2 [14, 16]x1 + [10, 13]x2 [5, 8]
Sehingga yang akan dimaksimumkan adalah : P endapatan = [27, 35]x1 + [21, 30]x2 Biaya = [10 + 14, 14 + 16]x1 + [9 + 10, 12 + 13]x2 + [5, 8] = [24, 30]x1 + [19, 25]x2 + [5, 8]
Fungsi biaya dapat disimbolkan dengan g(x). Sehingga untuk menyatakan persamaan fungsi biaya dapat ditulis: g(x) = [24, 30]x1 + [19, 25]x2 + [5, 8] Keuntungan = P endapatanBiaya = [3, 5]x1 + [2, 5]x2 + [−8, −5] dimana fungsi keuntungan disimbolkan dengan fungsi f (x). Sehingga untuk menyatakan persamaan fungsi tujuan dari keuntungan dapat ditulis:
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
11
Untuk menyatakan nilai fungsi tujuan akan digunakan variabel Z dan dapat ditulis: M aksimumkanf (x) = Z = [3, 5]x1 + [2, 5]x2 + [−8, −5] Sehingga persamaan fungsi tujuan diatas merupakan bentuk fungsi tujuan model LPIC Pembatas merupakan kendala yang dihadapi sehingga kita tidak bisa menentukan harga-harga variabel keputusan secara sembarang. Pada persoalan di atas ada 3 pembatas yang dihadapi yaitu: Pembatas 1 : 2x1 + x2 ≤ 100 Pembatas 2 : x1 + x2 ≤ 80 Pembatas 3 : x1 ≤ 40 Dengan demikian, formulasi lengkap dari persoalan PT Sayang Anak adalah: M aksimumkan Kendala
Z = [3, 5]x1 + [2, 5]x2 + [−8, −5] 2x1 + x2 ≤ 100 x1 + x2 ≤ 80 x1 ≤ 40 x1 ≥ 0, x2 ≥ 0
Setelah dicapai solusi optimum untuk x1 = 20, dan x2 = 60 dan Z = [172, 395]. Sehingga keuntungan maksimum yang diperoleh PT Sayang Anak diantara Rp 172.000 hingga Rp 395.000 dengan modal investasi sebesar 1.625.000 hingga Rp 2.108.000. Sehingga efisiensi dari keuntungan dan biaya PT Sayang Anak adalah 172.000/1.625.000 = 0.1058 pada worst optimum. Sedangkan efisiensi pada best optimum diperoleh sebesar 395.000/2.108.000= 0.1873. Dengan menggunakan optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval dapat meningkatkan rasio dari efisiensi biaya. Maka bentuk persamaan optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval adalah M aksimumkan Kendala
Z=
f (x) [3, 5]x1 + [2, 5]x2 + [−8, −5] = g(x) [24, 30]x1 + [19, 25]x2 + [5, 8]
2x1 + x2 ≤ 100
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
12
x1 + x2 ≤ 80 x1 ≤ 40 x1 ≥ 0, x2 ≥ 0 Transformasi optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval-nya menjadi: M aksimumkan Kendala
Z = [3, 5]u1 + [2, 5]u2 + [−8, −5]t 24u1 + 19u2 + 5t ≤ 1 34u1 + 25u2 + 8t ≥ 1 2u1 + u2 + 100t ≤ 0 u1 + u2 + 80t ≤ 1 u1 + 40t ≤ 0 u1 ≥ 0, u2 ≥ 0, t ≥ 0
Sehingga bentuk persamaan program linier untuk memperoleh efisiensi best optimum-nya adalah M aksimumkan Kendala
Z = 5u1 + 5u2 + 5t 24u1 + 19u2 + 5t ≤ 1 34u1 + 25u2 + 8t ≥ 1 2u1 + u2 + 100t ≤ 0 u1 + u2 + 80t ≤ 1 u1 + 40t ≤ 0 u1 ≥ 0, u2 ≥ 0, t ≥ 0
Dari perhitungan program linier diatas maka diperoleh nilai rasio efisiensi best optimum dari keuntungan dan biaya dengan solusi u1 = 0, u2 = 0.0525, t = 0.0007 dan z = 0.259. Efisiensinya meningkat dari 0.1873 menjadi 0.259. 0.0525 = 75 Dengan memproduksi mainan kereta api sebanyak x2 = ut2 = 0.0007 lusin, biaya modal sebesar Rp 1.883.000 dan keuntungan sebesar Rp 367.000. Sedangkan untuk worst optimum-nya maka bentuk transformasi optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval adalah M aksimumkan
Z = 3u1 + 3u2 + −8t
Kendala
24u1 + 19u2 + 5t ≤ 1 34u1 + 25u2 + 8t ≥ 1 2u1 + u2 + 100t ≤ 0
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
13
u1 + u2 + 80t ≤ 1 u1 + 40t ≤ 0 u1 ≥ 0, u2 ≥ 0, t ≥ 0 Dari persamaan program linier diatas maka diperoleh rasio tertinggi worst optimum untuk efisiensi keuntungan dan biaya dengan solusi u1 = 0.0415, u2 = 0, t = 0.001 dan z = 0.1161. Meningkat dari 0.1058 menjadi 0.1161. Dengan memproduksi mainan boneka sebanyak x1 = ut1 = 0.0415 0.001 = 41 lusin, dengan biaya modal sebesar Rp 992.000 dan keuntungan sebesar Rp 115.000.
5. KESIMPULAN DAN SARAN Kesimpulan Kesimpulan yang dapat diperoleh dari uraian di atas adalah sebagai berikut: 1. Optimasi program linier pecahan dengan fungsi tujuan berkoefisien interval dapat meningkatkan efisiensi biaya. 2. Optimasi program linier pecahan dengan koefisien interval dapat meningkatkan keuntungan dengan biaya minimum. Kesimpulan 1. Program linier pecahan dengan fungsi tujuan berkoefisien interval digunakan dalam menyelesaikan berbagai masalah alokasi sumber daya seperti dalam bidang manufakturing, pemasaran, keuangan, produksi material, dan lain sebagainya.
Daftar Pustaka [1] Borza, M. Solving Linear Fractional Programming Problems with Interval Coefficients in the objective function. Applied Mathematical Sciences, Vol. 6, 2012, no. 69, 3443 3452 [2] Buulolo, F. 2005. Analysis Sensitivitas pada Program Integer Campuran. Jurnal Sistem Teknik Industri (Nomor 4 tahun 2005). Hlm. 78-84.
M KHAHFI ZUHANDA – OPTIMASI PROGRAM LINIER PECAHAN
14
[3] Charnes, A. dan Cooper, W.W. Programming with linear fractional functions, Naval Research Logistics Quaterly, 9 (1962), 181-186. [4] Chinneck, J.W. dan Ramadan, K. 2000. Linear programming with interval coefficients. Journal of the Operational. Research Society, 51:209220, 2000. [5] Farida, A. 2011.Pengoptimuman pada Masalah Pemrograman Linear dengan Koefisien Interval. Sekolah Pascasarjana-IPB. [6] Khaled, R. 1996. Linear programming with interval coefficients. Thesis, Carleton University [7] Saprida, M. 2009. Analisis Sensitivitas dan Ketidakpastian dalam Program Linear. Tesis. Sekolah Pascasarjana-USU. [8] Stancu-Minasian, I.M. 1997. Fractional Programming: Theory, Methods and Applications. Dordrecht: Kluwer Academic Publishers. [9] Winston, W.L,. 2003. Operations Research: Applications and Algorithms, edisi-4, Internasional Thomson Publishing, Belmont, California.
M KHAHFI ZUHANDA: Department of Mathematics, Faculty of Mathematics and
Natural Sciences, University of Sumatera Utara, Medan 20155, Indonesia
E-mail:
Syawaluddin: Department of Mathematics, Faculty of Mathematics and Natural
Sciences, University of Sumatera Utara, Medan 20155, Indonesia
E-mail:
Esther S M Nababan: Department of Mathematics, Faculty of Mathematics and Natural Sciences, University of Sumatera Utara, Medan 20155, Indonesia
E-mail: