i
PENGOPTIMUMAN PADA MASALAH PEMROGRAMAN LINEAR DENGAN KOEFISIEN INTERVAL
ANA FARIDA
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011
i
ABSTRAK ANA FARIDA. Pengoptimu man pada Masalah Pemrograman Linear dengan Koefisien Interval. Dib imbing o leh PRAPTO TRI SUPRIYO dan NUR A LIATININGTYA S. Pada beberapa masalah aplikasi pemrograman linear (PL), koefisien pada model seringkali tidak bisa ditentukan secara tepat. Salah satu metode dalam menyelesaikan masalah PL in i adalah dengan menggunakan pendekatan interval, dimana koefisien tak tentu tersebut diubah menjadi bentuk interval. Bentuk PL in i dinamakan Linear Programming with Interval Coefficient (LPIC). Koefisien berbentuk interval menandakan perluasan toleransi (atau daerah) dimana parameter konstanta bisa diterima dan memenuhi model LPIC. Pada karya ilmiah in i akan dibahas salah satu metode dalam menyelesaikan LPIC yang telah dikembangkan oleh JW Chinneck dan K Ramadan (2000). Masalah LPIC memiliki fungsi objektif dan kendala persamaan atau pertidaksamaan yang berkoefisien interval. Solusi optimu m dibagi menjad i 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 n ilai fungsi objektif terbesar. Solusi optimu m pada LPIC didapatkan dengan mencari versi khusus dari fungsi objektif dan kendala yang mengoptimu mkan model, yaitu dipilih suatu nilai spesifik (nilai ekstrim) pada koefisien interval yang membuat model LPIC tersebut optimu m, sehingga pemecahan masalah LPIC diperoleh dengan menyelesaikan PL yang mengoptimu mkan model LPIC. Kata kunci: pemrograman linear, koefisien interval, optimisasi.
ii
ABSTRACT ANA FARIDA. Optimization in Linear Programming with Interval Coefficients Problems. Supervised by PRAPTO TRI SUPRIYO and NUR A LIATININGTYA S. On some applications of linear programming problems (LP), the coefficient on the model often can not be determined precisely. One method to solve this LP problem is to use an interval approach, where uncertain coefficients are transformed into the form of intervals. LP form is called Linear Programming with Interval Coefficient (LPIC). Interval coefficient indicates shaped expansion of tolerance (or regions) where the constant parameters can be accepted and fulfilled the LPIC model. One of the methods in solving LPIC has been developed by JW Chinneck and K Ramadan (2000). LPIC prob lems have objective functions and equations or inequalities constraints which their coefficients are intervals. The optimu m solutions are divided into two solutions, best optimu m solution and worst optimu m solution. In the case of minimizat ion, best optimu m is the solution that has the smallest objective function value, wh ile the worst optimu m is the solution that has the largest objective function value. The optimu m solution to the LPIC obtained by seeking a special version of the objective function and constraints that optimize model, which is selected a specific value (extreme value) on the interval coefficients that make LPIC model is optimu m. Therefore, solution is obtained by solving LP that optimize LPIC model. Keywords: linear programming, interval coefficient, optimizat ion.
ii
iii
PENGOPTIMUMAN PADA MASALAH PEMROGRAMAN LINEAR DENGAN KOEFISIEN INTERVAL
ANA FARIDA
Skripsi sabagai salah satu syarat untuk memperoleh gelar Sarjana Sains pada Departemen Matematika
DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM INSTITUT PERTANIAN BOGOR BOGOR 2011
iii
iv
Judul Skripsi
:
Nama NIM
: :
Pengoptimuman pada Masalah Pemrograman Linear dengan Koefisien Interval Ana Farida G54053213
Menyetujui,
Pembimbing I
Pembimbing II
Drs.Prapto Tri Supriyo, M.Kom. NIP. 19630715 199002 1 002
Dra. Nur Aliatiningtyas, MS. NIP. 19610104 198803 2 002
Mengetahui, Ketua Departemen Matematika
Dr. Berlian Setiawaty, MS. NIP 19650505 198903 2 004
Tanggal Lulus:
iv
v
KATA PENGANTAR Puji dan syukur penulis panjatkan kehadirat Allah Subhanallahu ta’ala atas segala nikmat, petunjuk, dan pertolongan-Nya sehingga penulisan skripsi in i berhasil diselesaikan. Tema yang dipilih penulis adalah Riset Operasi dengan judul Pengoptimu man pada Masalah Pemrograman Linear dengan Koefisien Interval. Skripsi ini merupakan syarat untuk menyelesaikan studi pada Departemen Matematika, Fakultas Matematika dan Ilmu Pengetahuan Alam, Institut Pertanian Bogor. Penulis mengucapkan terima kasih kepada: 1. Bapak Drs.Prapto Tri Supriyo, M.Ko m. dan Ibu Dra. Nur Aliatin ingtyas, MS selaku dosen pembimb ing skripsi atas bimbingan, arahan, waktu, kesabaran dan ilmu pengetahuan yang telah diberikan selama penyusunan skrips i in i. 2. Bapak Dr.Ir. A mril Aman, Msc. selaku dosen penguji skripsi atas saran dan masukan yang diberikan kepada penulis. 3. Keluargaku tercinta: bapak, Ibu, kakak, adik dan seluruh keluarga besar yang telah memberikan doa, dukungan dan kasih sayangnya. 4. Seluruh dosen Matematika FM IPA IPB yang telah memberikan ilmu yang bermanfaat bagi penulis. 5. Staf TU Matematika, Pak Yono, Bu Ade, Mas Heri, Bu Susi yang telah mengurusi segala administrasi. 6. Rizky, Nurus dan Fani selaku pembahas yang telah memberikan bantuan, saran dan kritik kepada penulis. 7. Salma, Fitri, Manda dan Lia atas persahabatan, doa, nasihat, semangat dan dukungannya selama ini. 6. Penghuni Nexu z House: Fety, Kak Sirri, Lusi, Devi, Sarah, Indah, Widy, Saly, Citra, Tyas dan Mutia atas kebersamaan, dukungan dan semangat yang diberikan. 7. Teman-teman Math 42: Novi, M ira, Lina, Yun i, Zil, Lela dan seluruh teman -teman lainnya yang tidak bisa disebutkan satu-persatu. 8. Adik-adik Math 43 dan 44 atas segala kebersamaan dan bantuannya. 9. Kak Sri, Sofi, Weni, Era, Mia dan Novy yang telah memberi semangat dan dukungan kepada penulis. Penulis menyadari bahwa dalam tulisan ini masih terdapat kekurangan dan jauh dari kesempurnaan. Oleh karena itu, dibutuhkan krit ik dan saran yang membangun dari pemb aca. Semoga karya ilmiah ini dapat bermanfaat bagi dunia ilmu pengetahuan khususnya matematika dan menjad i inspirasi bagi penelit ian-penelit ian selanjutnya.
Bogor, Oktober 2011
Ana Farida
v
vi
RIWAYAT HIDUP Penulis merupakan anak keempat dari lima bersaudara, puteri dari pasangan Bapak Abdul Ghofar dan Ibu Mahmudah. Penulis dilahirkan di Malang pada tanggal 19 Juli 1987. Pendidikan TK ditempuh pada tahun 1991 di TK Salafiyah Gondanglegi. Pada tahun1993 penulis melanjutkan sekolah di SDI Salafiyah Gondanglegi dan menyelesaikannya pada tahun 1999. Setelah menyelesaikan pendidikan sekolah dasar, penulis melan jutkan pendidikan d i MTsN 3 Malang pada tahun 1999 sampai 2002. Pada tahun 2002 penulis melanjutkan pendidikan menengah atas di MAN 3 Malang. Pada tahun 2005, penulis melan jutkan pendidikan di Institut Pertanian Bogor. Penulis diterima d i Tingkat Persiapan Bersama (TPB) Institut Pertanian Bogor melalu i jalur Seleksi Penerimaan Mahasiswa Baru (SPM B). Pada tahun 2006 penulis diterima di Departemen Geofisika dan Meteorologi, setahun kemudian pindah jurusan ke Departemen Matematika, Fakultas Ilmu Pengetahuan Alam dan Matematika. Selama mengikuti kegiatan perku liahan, penulis men jadi pengajar di b imbinga n belajar d i Bogor. Pada tahun 2009 dan 2010 penulis memperoleh beasiswa Bantuan Belajar Mahasiswa (BBM ).
vi
vii
DAFTAR ISI DAFTAR TABEL
Halaman …………………………………………………………………………. viii ………………………………………………………………………
viii
…………………………………………………………………......
viii
I
PENDAHULUAN ……………………………………………………………………… 1.1 Latar Belakang …………………………………………………………………… 1.2 Tu juan ……………………………………………………………………………….
1 1 1
II
LANDASAN TEORI
…………………………………………………………………
1
III PEMBA HASAN ………………………………………………………………………... 3.1 LPIC dengan kendala pertidaksamaan interval ……………………………………… 3.2 LPIC dengan kendala persamaan interval ……………………………………………
5 7 13
IV STUDI KASUS DA N PENYELESA IANNYA …………………………………………
18
SIMPULAN DAN SA RAN ……………………………………………………………… 5.1 Simpu lan ……………………………………………………………………………… 5.2 Saran …………………………………………………………………………………
23 23 23
………………………………………………………………………..
24
…………………………………………………………………………………
25
DAFTAR GAM BAR DAFTAR LAMPIRAN
V
DAFTAR PUSTA KA LAMPIRA N
vii
viii
DAFTAR TABEL 1 2 3
Halaman Susunan Zat Gizi pada Pakan Ayam dan Kadar Min imu m Zat Gizi ………………… 19 Batasan Pakan dalam Ransum dan Harga Pakan Ayam .............................................. 19 Pemecahan Masalah Pembelian Pakan Ternak Ayam ................................................. 23
DAFTAR GAMBAR 1 2
Halaman Ilustrasi himpunan konveks dan bukan himpunan konveks .......................................... 3 5 S I pada Contoh 3 .........................................................................................................
3 4 5
S II pada Contoh 3 ........................................................................................................ Daerah fisibel C pada Contoh 3 .................................................................................... S I pada Contoh 4 .........................................................................................................
6 6 6
6
6
9
S II pada Contoh 4 ........................................................................................................ Daerah fisibel S I S II pada Contoh 4 ........................................................................ S I dan S II pada Contoh 5 ............................................................................................ Ilustrasi irisan himpunan solusi dua pertidaksamaan ( S ) ..............................................
10
Ilustrasi gabungan himpunan solusi dua pertidaksamaan ( S ) .......................................
8
11 12 13 14 15 16 17 18 19 20
S pada Contoh 6 ........................................................................................................... S pada Contoh 6 ............................................................................................................ Daerah fisibel solusi best optimum pada Contoh 7 ........................................................ Daerah fisibel solusi worst optimum pada Contoh 7 ...................................................... Daerah fisibel LPIC pada Contoh 7 ............................................................................... Daerah fisibel pada Contoh 10 ..................................................................................... Daerah fisibel pada Contoh 11 ..................................................................................... Daerah fisibel solusi best optimum pada Contoh 12 ...................................................... Daerah fisibel solusi worst optimum pada Contoh 12 .................................................... Daerah fisibel LPIC pada Contoh 12 ............................................................................
8 8 11 11 12 13 13 16 18 18
7 8
6 7 8
DAFTAR LAMPIRAN 1 2 3
Halaman Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah LPIC dengan Kendala berbentuk Pertidaksamaan Interval …………………………………………………… 26 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah LPIC dengan Kendala berbentuk Persamaan interval ……………………………………………………… 28 Syntax Program LINGO 8.0 untuk Menyelesaikan Studi Kasus Masalah LPIC …… 29
viii
1
I PENDAHULUAN 1.1 Latar Belakang Pada beberapa masalah aplikasi pemrograman linear (PL), koefisien pada model seringkali t idak bisa ditentukan secara tepat sehingga biasanya dibuat dalam perkiraan. Salah satu metode dalam menyelesaikan masalah PL in i 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. Pada awalnya, LPIC tidak banyak dibahas, penelitian sebelumnya lebih memusatkan pada kasus khusus tertentu, misalkan variabel 0-1 atau kasus PL dengan koefisien interval pada fungsi objektif saja. Topik LPIC ini d iperkenalkan secara luas pada tahun 1960-1980, dimu lai dari model kendala berbentuk upper-bound dan lowerbound ( c1 a1 x1 a2 x2 ... an xn cu ). Meskipun tidak berhubungan dengan LPIC, model in i memiliki kesamaan yaitu model kendala tersebut dibatasi titik ekstrim. Shaocheng (1994) mentransformasikan LPIC menjad i dua PL yang memiliki karakteristik khusus. Salah satu PL memiliki daerah fisibel terbesar (largest possible
feasible region) dan versi terbaik pada fungsi objektif (most favourable version of objective function ) untuk menemukan solusi optimu m terbaik yang mungkin (best possible optimum solution). Sedangkan PL lainnya memiliki daerah fisibel terkecil (smallest possible feasible region) dan versi baik yang terendah pada fungsi objektif (least favourable version of objective function) untuk menemu kan solusi optimu m terburuk yang mungkin (worst possible optimum solution). Metode Shaocheng ini mengatasi masalah LPIC dengan syarat: (1) dibatasi variabel tak negatif saja, dan (2) hanya mengatasi kendala pertidaksamaan saja. Pada karya ilmiah in i akan dibahas salah satu metode dalam menyelesaikan LPIC yang telah dikembangkan oleh JW Ch inneck dan K Ramadan (2000). Metode in i merupakan generalisasi dari metode Shaocheng, yaitu dengan menambahkan kendala persamaan interval dan serta variabel tak positif pada model LPIC. 1.2 Tujuan Tujuan dari karya ilmiah in i adalah mengkaji metode pemecahan masalah LPIC secara teoritis dan mengimplementasikannya dalam kasus nyata.
II LANDASAN TEORI Definisi 1 (Fungsi Linear) Misalkan f ( x1 , x2 ,...., xn )
adalah
fungsi
dalam variabel-variabel x1 , x 2 ,...., x n . Fungsi f ( x1 , x 2 ,...., x n ) dinamakan fungsi linear jika dan hanya jika ada konstanta c1 , c2 ,..., cn , f ( x1 , x2 ,...., xn ) c1 x1 c2 x2 ....cn xn . (Winston, 1995) Sebagai contoh, f ( x1 , x 2 ) x1 2 x 2 adalah fungsi linear, sedangkan f ( x1 , x 2 ) x1 x 22 bukan fungsi linear. Definisi 2 (Persamaan dan Perti daksamaan Linear) Untuk sembarang fungsi linear f ( x1 , x 2 ,...., x n ) dan sembarang bilangan b, suatu persamaan f ( x1, x2 ,...., xn ) b disebut
persamaan linear dan f ( x1 , x2 ,...., xn ) b atau pertidaksamaan f ( x1 , x 2 ,...., xn ) b disebut linear. (Winston, 1995) Pemrograman Li near Pemrograman linear (PL) adalah masalah optimisasi yang memiliki karakteristik sebagai berikut: 1. Tujuan masalah tersebut adalah memaksimu mkan atau memin imu mkan fungsi linear dari seju mlah variabel keputusan. Fungsi tersebut dinamakan fungsi objektif. 2. Nilai variabel-variabel keputusan harus memenuhi kendala, yang berupa persamaan linear atau pertidaksamaan linear.
2
3.
Ada batasan tanda pada tiap variabel. Untuk sembarang variabel xi , pembatasan tanda menentukan xi harus tak negatif xi 0 atau tidak dibatasi tandanya (unrestricted in sign). (Winston, 1995)
Definisi 3 (Bentuk Standar PL) Suatu PL memiliki bentuk sebagai berikut:
standar
min z cT x terhadap kendala Ax b (1 ) b 0 dan x 0 dimana x dan c adalah vektor beru kuran n, vektor b beru kuran m dan A berupa matriks berukuran m x n yang disebut juga matriks kendala dengan m n . (Nash dan Sofer, 1996) Contoh 1 Misalkan diberikan PL standar sebagai berikut: Min z x1 2x 2 terhadap kendala: x1 2 x 2 x 3 3 x1 2 x 2 x 4 8 (2) 2 x1 x 5 10 dengan x1 , x 2 , x3 , x 4 , x5
0 Fungsi objektif adalah z x1 2x 2 Variabel keputusan adalah x1 , x 2 , x3 , x 4 , x5
x
A
x1 x2 x3 , c x4 x5
1 2 0 0 0
1 2 1 0 0 1 2 0 1 0 ,b 2 0 0 0 1
3 8 10
Solusi Pemrograman Linear Suatu masalah PL dapat diselesaikan dalam berbagai tekn ik, salah satunya adalah metode simp leks. Metode ini dapat menghasilkan suatu solusi optimu m bagi masalah PL dan telah dikembangkan Dantzig sejak tahun 1947, dan dalam perkembangannya merupakan metode yang paling u mu m digunakan untuk menyelesaikan PL. Metode ini berupa metode iteratif untuk menyelesaikan PL berbentuk standar. Pada masalah PL (1), vektor x yang memenuhi kendala Ax b disebut solusi PL (1). Misalkan matriks A dapat dinyatakan
sebagai A B N , dengan B adalah matriks taksingular berukuran m x m yang elemennya berupa koefisien variabel basis dan N adalah matriks berukuran m x (n-m) yang elemennya berupa koefisien variabel nonbasis pada matriks kendala. Matriks B disebut matriks basis untuk PL (1). Misalkan x d inyatakan dengan vektor xB , dengan x B adalah vektor variabel x xN basis dan x N adalah vektor variabel nonbasis, maka Ax b dapat dinyatakan sebagai
Ax
B N
xB xN
(3 )
BxB Nx N b Karena matriks B adalah matriks taksingular, maka B memiliki invers, sehingga x B dapat dinyatakan sebagai: (4) x B B 1b B 1Nx N Kemudian, fungsi objektifnya berubah men jadi: min z
cB TxB
cNTxN
Definisi 4 (Solusi Basis) Solusi dimana (n-m) variabel bern ilai nol disebut solusi basis. Variabel yang tidak bernilai nol disebut variabel basis dan variabel yang bernilai nol disebut variabel nonbasis. (Rao,1984) Solusi dari suatu PL disebut solusi basis jika memenuhi syarat berikut: i. solusi tersebut memenuhi kendala PL; ii. kolo m-ko lo m dari matriks kendala yang berpadanan dengan komponen tak nol dari solusi tersebut adalah bebas linear. (Nash dan Sofer, 1996) Definisi 5 (Solusi Fisibel) Sembarang solusi yang memenuhi kendala Ax b dan x 0 disebut solusi fisibel. (Rao,1984) Definisi 6 (Solusi Fisibel B asis) Vektor x disebut solusi fisibel basis jika x merupakan solusi basis dan x 0 . (Nash dan Sofer, 1996) Ilustrasi solusi basis dan solusi fisibel basis diberikan dalam Contoh 2.
3
Contoh 2 Misalkan diberi PL berikut: Min z x1 x 2 terhadap kendala: x1 2 x 2 x 3 3
x1 3x 2
x4
(5 )
8
x1 x 5 10 dengan x1 , x 2 , x3 , x 4 , x5 0 , maka d iperoleh: 1 2 1 0 0 3 A 1 3 0 1 0 ,b 8 10 1 0 0 0 1 Misalkan dip ilih
xN x1 adalah 1 0 B 0 1 0 0
N
x2
T
,
xB
x3
maka
x4
matriks
Ilustrasi himpunan konveks dan bukan himpunan konveks diberikan pada gambar dibawah in i.
x5
T
dan
basisnya
0 0T cB T 1 1 0 T , c N T Dengan menggunakan mat riks basis di atas, maka d iperoleh
0 0
xB
B 1b
(i)
(ii)
(iii)
(i v)
0 0 1
1 2 1 3 1 0
xN
sembarang titik-t itik dalam S seluruhnya termuat dalam S. Dengan kata lain, himpunan S R n disebut himpunan konveks, jika untuk tiap berlaku x1 , x 2 S 0,1 . x1 (1 )x 2 S dengan (Winston, 1995)
T
3 8 10
T
(6 )
Gambar 1. Ilustrasi himpunan konveks dan bukan himpunan konveks. Pada Gambar 1, lingkaran (i) dan persegi (ii) merupakan himpunan konveks, sedangkan bidang (iii) dan cincin (iv) bukan himpunan konveks.
c B T B 1 b 11 Solusi (6) merupakan solusi basis, karena memenuhi kendala pada PL (5) dan kolo mkolo m pada matriks kendala yang berpadanan dengan komponen tak nol dari (6) yaitu B, bebas linear (kolo m yang satu bukan merupakan kelipatan dari kolo m yang lain). Solusi (6) juga merupakan solusi fisibel basis, karena nilai-nilai variabelnya leb ih dari atau sama dengan nol.
Teorema 1 Daerah fisibel dari PL adalah konveks. (Rao,1984)
Definisi 7( Daerah Fisibel) Daerah fisibel suatu PL adalah himpunan semua titik yang memenuhi seluruh kendala PL dan batasan tanda PL . (Winston, 1995)
Ax2 b, x2 0 (2) Jika persamaan (1) dikalikan dengan dan persamaan (2) dikalikan dengan 1 , dan kemudian keduanya 0 1 diju mlahkan, maka didapat: [ Ax 1 ] b
z
Definisi 8 (Solusi Opti mum) Solusi optimu m suatu PL adalah solusi fisibel yang mengoptimu mkan fungsi objektif. (Rao,1984) Definisi 9 ( Hi mpunan Konveks) Misalkan S adalah himpunan titik. Himpunan S disebut himpunan konveks jika segmen garis yang menghubungkan
Bukt i: Daerah fisibel S dari PL standar didefinisikan sebagai S {x | Ax b, x 0} . Misalkan t itik x 1 dan x 2 termasuk dalam himpunan S, maka Ax1 b, x1 0 (1)
(1
)[Ax 2 ]
[ Ax 1 ] (1
(1 )[Ax 2 ]
b (1
A[ x1 (1
)x 2 ] (
A[ x1 (1
)x 2 ] b
Misalkan x
x1
(1
)b
)x 2
(1
)b ))b (3)
4
n
Persamaan (3) dapat ditulis sebagai Ax b. Berdasarkan defin isi, maka x S atau
ajyj
b
ajzj
b
x1 (1 )x 2 S . Jadi S {x | Ax b, x Teorema 1 terbukti.
n
0} adalah konveks. j 1
Definisi 10 (Titik Ekstrim) Titik dari himpunan konveks yang tidak berada di dalam segmen garis yang menghubungkan dua titik lain di dalam himpunan tersebut dinamakan t itik ekstrim. Jika x S adalah titik ekstrim, maka tidak ada x1 , x 2 S sehingga x1 (1 )x 2 S untuk (0,1) . Dengan kata lain, jika x titik ekstrim dan
x1 (1 (0,1) maka x x1 x 2 .
S untuk
)x 2
karena untuk
yj
0 dan
Teorema 2 Semua solusi fisibel basis adalah titik ekstrim dari himpunan konveks dari solusi fisibel. (Rao, 1984) Bukt i: Misalkan x [b1 , b2 ,....,bm , bm 1 ,0,..,0] adalah suatu solusi fisibel basis untuk PL. Dari Teorema 1 diketahui bahwa daerah fisibel adalah himpunan konveks. Misalkan x S bukan tit ik ekstrim, maka ada y, z S dimana y z sedemikian
y [ y1 , y2 ,...., ym , ym 1 ,.., yn ] z [ z1 , z2 ,...., zm , zm 1 ,.., z n ] untuk j m 1 diketahui x j
dimana λ
1
(4)
akan terjadi jika y j
0, z j
ajxj
b
(7.a)
ajyj
b
(7.b )
ajzj
b
(7.c)
j 1 m
j 1
j 1
Jika persamaan (7.b) dikurangi oleh persamaan (7.c) menghasilkan m
m
ajyj
0 dan dari
0 . Selain itu
maka persamaan (5) dapat ditulis sebagai berikut:
ajxj
b
m
a j (y j
zj)
0
j 1
Karena untuk j
m , a j adalah kolo m
dari matriks A yang bersesuaian dengan variabel basis maka a j ( j 1,..., m ) saling bebas linear (Definisi 4). Karena a j saling bebas linear, maka
zj)
0 menyebabkan y j
j,
zj
j 1,..., m . Akibatnya y j
0 zj ,
m.
1
j
yj
Seperti telah diketahui sebelumnya z j 0 untuk m 1 j n , maka
y z . Hal ini kontradiksi dengan fakta yang diasumsikan bahwa y z . Karena itu x haruslah titik ekstrim. Terbukti.
Misalkan a j kolo m ke-j dari matriks A
j 1
0
j 1
(5)
n
ajzj j 1
untuk
karena x, y dan z fisibel maka
Ax b Ay b Az b
maka persamaan (6)
m
a j (y j
0 . Hal ini hanya
0 dan z j
0
0,
m
)z j
0, y j
zj
xj
secara individu dapat ditulis
j 1
sehingga x y (1 )z , 0 Diketahui bahwa x [b1 , b2 ,....,bm , bm 1 ,0,..,0]
m 1 , elemen
j
m
(Rao, 1984)
persamaan (4) xj y j (1
(6)
j 1
5
Definisi 11 (Bilangan Interval) Bilangan interval pada garis bilangan adalah himpunan seluruh titik (bilangan) di antara dua titik u jung tertentu pada garis bilangan . (Jeffrey, 2005)
Definisi 12 (Interval tertutup) Misalkan (a, b) dan a b . Interval tertutup [a, b] dari a ke b adalah
{x
|a
x b} . (Fraleigh,1969)
III PEMBAHASAN Masalah LPIC memiliki koefisien interval, baik pada fungsi objektif maupun kendala. Salah satu cara untuk menyelesaikan masalah LPIC ini adalah dengan menggunakan metode yang dikembangkan oleh JW Chinneck dan K Ramadan (2000). Metode ini merupakan generalisasi dari metode Shaocheng (1994), yaitu diperluas dengan: (i) memasukkan variabel yang tidak memiliki batasan tanda atau variabel urs (unrestricted in sign) pada x0 (variabel yang tidak terkait koefisien interval); (ii) memasukkan variabel tak positif, baik yang terkait dalam interval atau tidak; dan (iii) memasukkan kendala berbentuk persamaan. Tujuan LPIC adalah menentukan solusi best optimum dan worst optimum. Permasalahan LPIC yang akan dibahas hanya masalah min imisasi. Jika model berupa kasus maksimisasi, maka model tersebut diubah men jadi kasus min imisasi dengan cara mengalikan fungsi objektif dengan (-1). Pada kasus min imisasi, best optimum adalah solusi optimu m dengan nilai fungsi objektif terkecil dan worst optimum adalah solusi optimu m dengan nilai fungsi objekt if terbesar. Solusi optimu m pada LPIC didapatkan dengan mencari versi khusus dari fungsi objektif dan kendala yang mengoptimu mkan model, yaitu dipilih suatu nilai spesifik (nilai ekstrim) pada koefisien interval yang membuat model LPIC tersebut optimu m. Suatu kendala berkoefisien interval akan memiliki kendala spesifik (kendala dengan koefisien tentu) berjumlah tak hingga. Jadi untuk memperoleh solusi optimu m, dipilih versi ekstrim kendala yang koefisiennya berupa kombinasi batas bawah dan batas atas koefisien interval. Metode LPIC menyandarkan hubungan antar daerah fisibel dari kendala-kendala spesifik. Misalkan C adalah himpunan kendala dengan koefisien interval, C I dan
yang memenuhi kendala C I disebut S I , sedangkan daerah fisibel yang memenuhi kendala C II disebut S II . Daerah fisibel tersebut memiliki hubungan sebagai berikut: 1. S I S II atau S II S I , yaitu suatu daerah fisibel seluruhnya termuat dalam daerah fisibel lainnya. 2. , yaitu S I S II dan S I S II suatu daerah fisibel memotong sebagian daerah fisibel lainnya. 3. , yaitu tidak ada tumpang S I S II tindih (overlap) pada daerah-daerah fisibel.
C II adalah dua himpunan kendala berbeda yang dibangkitkan dari dengan C menggunakan versi ekstrim C . Daerah fisibel
Gambar 2. S I pada Contoh 3.
Contoh 3: Misalkan C adalah himpunan kendala sebagai berikut: a 2 x1 2 x2 [1,2] . C b x1 x2 [ 2,3] x1 , x2 0 Jadi dapat diambil kendala spesifik C I dan
C II sebagai berikut: CI
aI bI
2 x1 2 x2 2 x1 x2 2 x1 , x2 0
C II
a II bII
2 x1 2 x2 1 x1 x2 3 x1 , x2 0
6
Gambar 3. S II pada Contoh 3.
Gambar 5. S I pada Contoh 4.
maka S II S I , sebagaimana diilustrasikan oleh Gambar 4.
Gambar 6. S II pada Contoh 4. maka S I S II dan S I S II diilustrasikan oleh Gambar 7.
sebagaimana
Gambar 4. Daerah fisibel C pada Contoh 3. Contoh 4: Misalkan C adalah himpunan sebagai berikut: a [1,2]x1 x 2 2 . C b x1 [3,4]x 2 4 x1 , x 2 0
kendala
Jadi dapat diambil kendala spesifik C I dan
C II sebagai berikut: CI
CII
aI bI
aII bII
2 x1 x2 2 x1 3 x2 4 x1 , x2 0
x1 x2 2 x1 4 x2 4 x1, x2 0
Gambar 7. Daerah fisibel Contoh 4.
SI
Contoh 5: Misalkan himpunan kendala C berikut: a [ 1,1]x1 [ 1,1]x 2 1 C b x1 2 c x2 2
S II pada
sebagai
.
Jadi dapat diambil kendala spesifik C I dan
C II sebagai berikut: CI
aI b c
x1 x2 1 x1 2 x2 2
7
a II b c
C II
x1 x2 1 x1 2 x2 2
maka S I S II diilustrasikan pada Gambar 8.
xsi sebagaimana
a ij a ij
maupun variabel urs (unrestricted in sign). = variabel-variabel yang terkait dengan koefisien interval, berupa variabel tak negatif atau variabel tak positif. = batas atas koefisien interval dari variabel ke-j pada kendala ke -i. = batas bawah koefisien interval dari
variabel ke-j pada kendala ke-i. = batas bawah koefisien interval dari bi nilai ruas kanan/RHS (Right Hand Side) pada kendala ke-i. = batas bawah koefisien interval dari bi nilai ruas kanan/RHS pada kendala ke-i. = batas atas koefisien interval variabel cj ke-j pada fungsi objektif. cj = batas bawah koefisien interval variabel ke-j pada fungsi objekt if.
Gambar 8. S I dan S II pada Contoh 5. Permasalahan model LPIC dibagi men jadi dua, yaitu menyelesaikan LPIC dengan kendala berupa pertidaksamaan interval dan menyelesaikan LPIC dengan kendala persamaan interval. 3.1 LPIC deng an kendala perti daksamaan interval Bentuk u mu m model LPIC dengan kendala berupa pertidaksamaan interval adalah sebagai berikut: n
Min Z
c j,c j x j j 1
terhadap: n
a ij , a ij x j
bi , bi ,
untuk i 1,..., m j,
xj
x
xj
x si .
x
si
0
untuk
c j , c j , a ij , a ij , bi , bi
I( )
dan
xj
Misalkan S seluruh
dimana I ( ) adalah himpunan seluruh bilangan interval pada . Keterangan: x = ( x1 , x2 , x3 ,...., xn ) , dimana x j adalah x0
ditransformasikan menjadi 2p pertidaksamaan ekstrim yang berbeda. Pertidaksamaan tersebut diperoleh dengan cara mengo mbinasikan nilai batas atas dan batas bawah koefisien. Solusi optimu m diperoleh dengan memilih satu versi pertidaksamaan ekstrim dari 2p pertidaksamaan ekstrim yang mengoptimu mkan fungsi objektif. Formula pertidaksamaan khusus yang diperoleh dari pengaturan tiap batas bawah atau batas atas koefisien interval dinamakan formula karakteristik. Pandang satu pertidaksamaan ke-i pada (1) dan S k adalah himpunan solusi pertidaksamaan ekstrim ke-k diantara 2 p pertidaksamaan ekstrim yang berbeda dari i.
(1)
j 1
0
Tiap pertidaksamaan i pada (1) yang memiliki p koefisien interval dapat
variabel ke-j. = variabel-variabel yang yang tidak terkait dengan koefisien interval, baik variabel tak negatif ( x j 0 ) atau variabel tak positif ( x j
0)
2p k 1
S k adalah gabungan dari
himpunan
ekstrim dan
S
solusi
pertidaksamaan
2p k 1
S k adalah irisan dari
seluruh himpunan solusi pertidaksamaan ekstrim. Ilustrasi dari pengertian tersebut pada dua pertidaksamaan adalah sebagai berikut:
8
Gambar 9.
Ilustrasi irisan himpunan solusi dua pertidaksamaan ( S ).
Gambar 11. S pada Contoh 6.
Gambar10.
Ilustrasi gabungan himpunan solusi dua pertidaksamaan ( S ).
Definisi 1 Untuk setiap pertidaksamaan kendala pada (1), jika ada suatu versi ekstrim pada formula karakteristik sedemikiran rupa sehingga himpunan solusinya sama dengan S , maka versi in i disebut dengan pertidaksamaan range nilai maksimu m. Sedangkan jika suatu versi ekstrim pada formu la karakteristik sedemikiran rupa sehingga himpunan solusinya sama dengan S , maka versi ini disebut dengan disebut pertidaksamaan range nilai min imu m. Contoh 6: 1,3 x1 [2,5]x2 [4,6] , dimana x1 , x2 0 . Pertidaksamaan interval ini memiliki 3 koefisien interval sehingga dapat dipecah men jadi 23 8 pertidaksamaan ekstrim : (a) x1 2 x 2 4 (e) 3x1 2x2 4 (b) x1 2 x 2 6 (f) 3x1 2x2 6 (c) x1 5x 2 4 (g) 3x1 5x 2 4 (d) x1 5x 2 6 (h) 3x1 5x 2 6
Gambar 12. S pada Contoh 6. Dapat dilihat dari Gambar 11 dan Gambar 12 2 bahwa S x | 3x1 5x 2 4 , sehingga pertidaksamaan 3x1 5x 2 4 (g) disebut pertidaksamaan range nilai maksimu m. 2 Sedangkan S x | x1 2 x 2 6 sehingga pertidaksamaan (b) disebut x1 2 x2 6 pertidaksamaan range nilai minimu m. Teorema 1 Jika ada
pertidaksamaan
interval
n
a j,a j xj
xj
dimana
b, b
x
0
si
x ,
j 1
n
xj
0 untuk x j
x si , maka
a jxj
b
j 1
adalah pertidaksamaan range nilai maksimu m n
a jxj
dan
b
j 1
range nilai minimu m.
adalah
pertidaksamaan
9
Bukt i:
Akibat 1 n
ajxj
Misalkan
b adalah sembarang
j 1
versi khusus pertidaksamaan interval. Maka untuk sembarang solusi khusus x j 0 dimana n
x si ,
xj
kita
mempunyai
Untuk
xj
n
a jxj
b adalah pertidaksamaan range
j 1 n
a jxj
nilai maksimu m dan
a j x j . Misalkan x memenuhi j 1
adalah
pertidaksamaan range nilai minimu m. Bukt i:
n
a jxj
b
j 1
n
ajxj j 1
x si , maka
xj
dimana
0
b,
maka
x
n
memenuhi
ajxj
Misalkan
j 1
b adalah sembarang
j 1
n
ajxj
b
b.
Akibatnya
x
juga
b, b
b.
j 1 n
versi khusus pertidaksamaan interval. Maka untuk sembarang solusi khusus x j 0 dimana
ajxj
memenuhi
b ,untuk
b
n
j 1
Jadi terdapat sebuah titik x yang harus memenuhi seluruh versi pertidaksamaan interval lain secara bersamaan. Akibatnya,
a jxj
b adalah
j 1
pertidaksamaan range nilai minimu m. Untuk sembarang solusi khusus x j dimana n
x si ,
xj
kita
juga
0
memiliki
mempunyai
j 1
a j x j . Misalkan x memenuhi j 1
n
a jxj
b,
ajxj
b
maka
x
juga
memenuhi
j 1 n
b.
Akibatnya
x
juga
j 1 n
ajxj
memenuhi
b ,untuk
b, b
b
b.
j 1
n
a jxj j 1
kita
n
ajxj
n
berdasarkan Defin isi 1,
x si ,
xj
ajxj
b
b.
Misalkan x
j 1 n
ajxj
memenuhi
b,
maka
x
juga
j 1
Jadi terdapat sebuah titik x yang harus memenuhi seluruh versi pertidaksamaan interval lain secara bersamaan. Akibatnya, n
b adalah
j 1
n
memenuhi
a jxj
berdasarkan Defin isi 1,
ajxj
b.
Akibatnya
x
j 1
dimana
n
memenuhi
pertidaksamaan range nilai minimu m. Untuk sembarang solusi khusus x j
a jxj
b,
untuk
n
j 1
b, b b b . Oleh karena itu, solusi x yang memenuhi sembarang versi pertidaksamaan interval juga akan dipenuhi oleh
si
x ,
xj
kita
juga
0
memiliki
n
a jxj j 1
ajxj
b
b.
Misalkan x
j 1 n
ajxj
memenuhi
b,
maka
x
juga
j 1
n
a jxj
b . Jadi berdasarkan Defin isi 1,
n
memenuhi
j 1
ajxj
b.
Akibatnya
x
j 1
n
a jxj
b adalah pertidaksamaan range
j 1
nilai maksimu m.
n
memenuhi
a jxj
b,
untuk
j 1
b, b b b . Oleh karena itu, solusi x yang memenuhi sembarang versi pertidaksamaan interval juga akan dipenuhi oleh
10
n
a jxj
cx1
b . Jadi berdasarkan Defin isi 1,
cx1
cx 2
j 1
cx 2 ....
n
a jxj
b adalah pertidaksamaan range
....
j 1
cx n
nilai maksimu m.
n
c jxj
j 1
n
Jika Z
c j , c j x j adalah fungsi objektif j 1
xj
x si , maka
xj
dimana
0
n
n
c jxj
Teorema 2
untuk
cx n
j 1
n
n
c jxj
Jadi
c j x j berlaku untuk solusi
j 1
j 1
x yang diberikan.
n
c jxj
c jxj
j 1
untuk solusi x yang
j 1
Definisi 2 Untuk masalah min imisasi dengan x j
diberikan.
n
x si ,
xj
c jxj
dinamakan
fungsi objektif terbaik (most
favourable
dimana
Bukt i: Diketahuti
j 1
c
si
x ,
xj
c
dan cx j
maka
0 dimana
xj
cx j .
Untuk
n
c j x j dinamakan
objective function) dan
j 1,2,...,n dapat ditulis: cx1
cx1
cx 2
cx 2
j 1
fungsi objektif terburuk (least favourable objective function) .
.... .... cx n
cx n
n
n
c jxj
c jxj
j 1
j 1
n
n
c jxj
Jadi
c j x j berlaku untuk solusi
j 1
j 1
x yang diberikan. Akibat 2 Untuk x j n
0 , dimana
c jxj j 1
x ,
Teorema 1 dan Teorema 2 menyediakan perhitungan dalam mencari solusi best optimum dan worst optimum LPIC, yaitu dengan mengubah masalah LPIC asli menjadi dua PL. Pemecahan masalah LPIC adalah dengan menggunakan fungsi objektif terbaik dan pertidaksamaan range nilai maksimu m untuk menentukan solusi best optimum. Sedangkan untuk menentukan solusi worst optimum, digunakan fungsi objektif terburuk dan pertidaksamaan range nilai min imu m Algoritma 1: Penyelesaian LPIC dengan kendala berupa perti daksamaan interval. n
Diberikan : min Z
c jxj j 1
Bukt i: Diketahuti xj
x si , maka
xj
n
si
0
n
kendala
a ij , a ij x j
j 1
xj , xj
i 1,..., m dan c
dan
xj
maka
cx j
cx j .
c
0 dimana
Untuk
1.
j 1
c j , c j x j dengan b i , b i , dimana
(x 0
x si ) .
Bentuk LPIC men jadi PL: n
c 'j x j , dimana x j
Min z
j 1,2,...,n dapat ditulis:
x si
j 1
Berdasarkan Teorema 2 cukup dipilih:
c' j terhadap:
cj
, xj
0
cj
, xj
0
11
n
aij' x j
bi ,
, dimana x j
i
x si
j 1
Berdasarkan Teorema 1 cukup dipilih:
a 'ij
4x2
C 3a : x1
x2
C 4 a : 5 x1
x2
, xj
0
C5 : x2
a ij
, xj
0
x1 , x 2
dengan
6x2
C 2 a : x1
a ij
Dicari best optimum menyelesaikan PL diatas. 2.
C1a : 3 x1
6 5 2 6
4 0
Kemudian diselesaikan menggunakan softwere LINGO 8.0 sehingga diperoleh solusi optimu m x1 1, x2 1 dan Z = 3.
Bentuk LPIC men jadi PL: n
c "j x j , dimana x j
Min z
x si
j 1
Berdasarkan Teorema 2 cukup dipilih:
c" j
cj
, xj
0
cj
, xj
0
terhadap: n
a"ij x j
bi ,
, dimana x j
i
x si
j 1
Berdasarkan Teorema 1 cukup dipilih:
a"ij
a ij
, xj
0
a ij
, xj
0
Dicari worst optimum menyelesaikan PL diatas.
dengan
Algorit ma 1 menggambarkan metode umu m untuk mengatasi kasus min imisasi pada LPIC dengan kendala yang memiliki batasan saja. Jika kendala memiliki batasan maka kendala tersebut dikalikan dengan (-1).
Gambar 13.
Sedangkan untuk solusi worst optimum, LPIC tersebut diubah menjadi PL sebagai berikut: Min z 3x1 4 x2 terhadap: C1b : 2 x1
2x2
C 3b : x1
x2
C 4b : 3x1
C1 : [2,3]x1 C 2 : x1
[4,6]x 2
[2,4]x 2
C 3 : x1
x2
C 4 : [3,5]x1 C5 : x2 x1 , x 2
x1 , x 2
kendala
4x2
C 2b : x1
C5 : x 2
Contoh 7: Selesaikan LPIC dengan pertidaksamaan interval berikut: Min Z [1,3]x1 [2,4]x2 terhadap:
Daerah fisibel solusi best optimum pada Contoh 7.
x2
9 5 1 7
4 0
Kemudian diselesaikan menggunakan softwere LINGO 8.0 sehingga diperoleh solusi optimu m x1 1.8, x2 1.6 dan Z = 11.8.
[6,9]
5
[ 2, 1] x2
[6,7]
4 0
Dengan menggunakan Algoritma 1, maka akan didapatkan solusi best optimum dari PL sebagai berikut: Min z x1 2x2 terhadap:
Gambar 14. Daerah fisibel solusi worst optimum pada Contoh 7. Daerah fisibel untuk masalah LPIC di atas diperlihatkan pada gambar berikut:
12
C1 : x1
[2,4]x 2
C 2 : [1,3]x1
x2
1 [5,8]
x1 , x 2 0 Solusi worst optimum pada masalah LPIC d i atas adalah sebagai berikut: Min Z 2 x1 x2 terhadap: C1b : x1 2 x 2 1 C 2b : x1
Gambar 15. Daerah fisibel Contoh 7.
LPIC
pada
Sebagaimana PL b iasa, PL pada Algorit ma 1 memiliki 3 hasil yang mungkin, yaitu: (i) t itik optimu m finite bounded; (ii) unboundedness; atau (iii) infeasibility, akibatnya LPIC memiliki beberapa kemungkinan berikut : Jika solusi best optimum infeasible, maka seluruh LPIC infeasible. Contoh 8: Min Z x1 1,3 x2 terhadap: C1 : x1 x 2 [ 2, 1] C 2 : [1,2]x1 x 2 [5,7] x1 , x 2 0 Solusi best optimum pada masalah LPIC d i atas adalah sebagai berikut: Min Z x1 x2 terhadap: C1a : x1 x 2 2 C 2a : 2 x1 x 2 5 x1 , x 2 0 Dengan menggunakan softwere LINGO 8.0, solusi PL tersebut adalah infeasible, maka seluruh PL dari masalah LPIC di atas juga akan menghasilkan solusi infeasible. Jika solusi worst optimu m unbounded, maka seluruh LPIC unbounded. Contoh 9: Min Z [1,2]x1 terhadap:
x2
x2
8
x1 , x 2 0 Dengan menggunakan softwere LINGO 8.0, solusi PL tersebut adalah unbounded, maka seluruh PL dari masalah LPIC di atas juga akan menghasilkan solusi unbounded.
Jika solusi best optimum feasible dengan nilai z dan worst optimum infeasible, maka LPIC yang optimu m memiliki range antara z dan infeasibility. Contoh 10: Min Z x1 1,3 x2 terhadap: C1 : x1 [1,2]x2 [ 3, 1] C2 : [1,2]x1 x1, x2
x2
[2,7]
0
Pada kendala C1 , koefisien interval pada x 2 bertanda negatif. Oleh karena itu, kendala in i diubah terlebih dahulu men jadi: C1 : x1 [ 2, 1]x 2 [ 3, 1] Solusi best optimum pada masalah LPIC d i atas adalah sebagai berikut: Min Z x1 x2 terhadap: C1a : x1 x2 3 C2 a : 2 x1
x2
2
x1, x2 0 Dengan menggunakan softwere LINGO 8.0, solusi dari PL tersebut adalah x1 1, x2 0 dan z 1 .
Sedangkan solusi worst optimum pada masalah LPIC di atas adalah sebagai berikut: Min Z x1 3x 2 terhadap: C1b : x1 2 x2 1 C2b : x1 x1, x2
x2 0
7
13
Dengan menggunakan softwere LINGO 8.0, solusi dari PL tersebut adalah infeasible. Jadi masalah LPIC tersebut memiliki nilai optimu m yang berada antara z 1 dan infeasibility. Daerah fisibel pada solusi best optimum digambarkan sebagai berikut:
Gambar 16.
Dengan menggunakan softwere LINGO 8.0, solusi dari PL tersebut adalah x1 2.7, x2 1.1 dan z 7 . Jadi masalah LPIC tersebut memiliki nilai optimu m yang berada antara dan z 7 . Daerah fisibel pada solusi worst optimum digambarkan sebagai berikut:
Daerah fisibel pada Contoh 10.
Jika solusi worst optimum feasible dengan nilai z dan best optimum unbounded, maka LPIC yang optimu m memiliki range antara dan z . Contoh 11: Min Z [1,3]x1 x2 terhadap: C1 : [ 2, 1]x1 4 x 2 1 C 2 : 3x1 [ 1,1]x 2 [5,7] x1 , x 2 0 Solusi best optimum pada masalah LPIC d i atas adalah sebagai berikut: Min Z x1 x2 terhadap: C1a : x1 4 x 2 1 C 2 a : 3x1 x 2 5 x1 , x 2 0 Dengan menggunakan softwere LINGO 8.0, solusi dari PL tersebut adalah unbounded. Sedangkan solusi worst optimum pada masalah LPIC d i atas adalah sebagai berikut: Min Z 3x1 x 2 terhadap: C1b : 2 x1 4 x 2 1 C 2b : 3x1 x 2 7 x1 , x 2 0
Gambar 17.
Daerah fisibel Contoh 11.
3.2 LPIC deng an interval
kendal a
pada
persamaan
Bentuk u mu m model ini adalah sebagai berikut: n
Min Z
c j,c j x j j 1
Dengan kendala n
a ij , a ij x j
bi , bi ,
j 1
(1) untuk i 1,..., m j,
xj
xj
x si .
x0
x si
0
untuk
c j , c j , a ij , a ij , bi , bi
I( )
dan
xj
dimana I ( ) adalah himpunan seluruh bilangan interval pada . Pencarian solusi best optimum dapat diperoleh dengan menggunakan Teorema 3. Sedangkan untuk mencari versi khusus kendala persamaan interval yang memiliki solusi best optimum digunakan Algorit ma 2. Pada Teorema 4 men jelaskan metode untuk mencari solusi worst optimum.
14
Teorema 3 Pada kendala persamaan berbentuk interval
n
Misalkan
S1
{x |
a jxj
n
a j,a j xj
b, b
(2)
j 1
maka sepasang berikut:
kendala
pertidaksamaan
x1 , x 2
a' j x j
x
, xj
b
si
a j x 'j
' b , dimana x j
0
(a)
a j x "j
" b , dimana x j
0
(b)
j 1 n
aj aj
a' j
,xj ,xj
0 0
(3)
a" j x j
.
x si
, xj
b
j 1
a" j
j 1
Jika persamaan (a) dikalikan dengan dan persamaan (b) dikalikan dengan 1 , kemudian keduanya 0 1dan diju mlahkan, maka didapat:
n
aj
,xj
0
aj
,xj
0
n
(4)
mendefinisikan daerah konveks dimana tiap titiknya memenuhi sembarang versi khusus kendala persamaan interval.
a j x 'j
b
j 1 n
(1
a j x "j
)
(1
)b
j 1 n
Bukt i: Misalkan x adalah suatu titik yang memenuhi sembarang versi khusus persamaan interval
n
a j x 'j
(1
a j x "j
)
j 1
b (1
)b
j 1
n
n
ajxj
a j ( x 'j
b.
) x "j )
(1
b
j 1
j 1
xj
Untuk
0
n
ajxj
b)
) x1" ,...., x n'
( x1' ,...., x n' )
dan
a jxj
j 1
b b Oleh
( x1' (1
n
(
j 1
x si , maka
xj
dimana
n
a jxj
x 1 (1
j 1
b. karena
itu,
Jadi
S1
{x |
(
j 1
b) b , maka x juga
ajxj
a jxj
a jxj
b.
Selain
adalah
a j x j , maka x juga
j 1
j 1 n
a jxj
a j x j atau
b.
j 1
j 1
memenuhi
n
x2
b, x j
0} dan
dimana
x1
( x1' , x 2' ,..., x n' ) ,
( x1" , x 2" ,..., x n" ) , maka: a j x 'j
' b , dimana x j
0
(d)
a j x "j
" b , dimana x j
0
(e)
n
j 1
a jxj j 1
S
j 1
pertidaksamaan
n
b dan
a jxj
n
n
memenuhi b
{x | j 1
x1 , x 2
n
b)
S2
itu,
j 1 n
a jxj
0}
n
memenuhi
ajxj
b, x j
daerah konveks. Misalkan
n
x
S1
S1
j 1
(
S1
j 1
n
a jxj
) x n" )
)( x1" ,...., x n" )
(1
)x 2
(1
n
n
Jadi
( x1' , x 2' ,..., x n' ) ,
x1
n
j 1
b
dimana
S
( x1" , x 2" ,..., x n" ) , maka:
x2
n
j 1
0} dan
b, x j
j 1
b.
Jika persamaan (d) dikalikan dengan dan persamaan (e) d ikalikan dengan 1 , kemudian keduanya 0 1dan diju mlahkan, maka didapat:
15
n
a j x 'j
b
j 1
)
a j x "j
(1
(1
)
)b
j 1 n
n
a j x 'j
a j x "j
j 1
b (1
) x "j ) b
j 1
( x1' (1
) x1" ,...., x n'
( x1' ,...., x n' ) (1 x 1 (1
) x n" )
(1
)( x1" ,...., x n" )
)x 2
S1
S2
S1
a' ij x j
a jxj
b, x j
adalah
0}
x si .
Berdasarkan Teorema 3, jika model LPIC memiliki kendala persamaan interval maka kendala persamaan tersebut diubah menjadi bentuk pertidaksamaan (3) dan (4). So lusi pada model PL ini menghasilkan nilai fungsi objektif terbaik. Algoritma 2 : menentuk an setting koefisien best optimum untuk kendala persamaan interval. Diberikan k kendala persamaan interval dari n
a j,a j xj
b, b
mengoptimu mkan model. Selesaikan Phase I dari PL untuk himpunan kendala berikut: k
aij
Maks i 1 j 1
bi i 1
n
terhadap
:
x j a ij j 1
i 1,....,k
bi
0 0
0
(5)
n
a"ij x j
b i , dimana
j 1
a"ij
a ij
,xj
0
a ij
,xj
0
,
untuk
(6)
Bukt i: Andaikan titik worst optimum x memenuhi sembarang versi khusus kendala persamaan n
ajxj
interval
b dan
memiliki nilai
j 1
fungsi objektif z . Berdasarkan Teorema 3, titik ini akan berada pada daerah konveks dari solusi yang mungkin, didefinisikan oleh (3) dan (4). Persamaan (5) dan (6) merupakan versi persamaan ekstrim dari (3) dan (4). Misalkan z' adalah nilai fungsi objektif yang ditentukan saat PL yang sama dipecahkan n
dan titik best
optimum x * yang telah diperoleh melalui Torema 3. Dicari a ij dan bi yang
n
,xj ,xj
ajxj
dengan cara mengganti
j 1
k
a ij a ij
atau
daerah konveks. Jadi pertidaksamaan (3) dan (4) merupakan daerah konveks dimana tiap titiknya memenuhi sembarang versi khusus kendala persamaan interval. Pembuktian in i analog untuk x j 0 dimana
bentuk
,
b i , dimana
a ' ij
j 1
xj
bi
j 1
S1
{x |
bi
n
n
Jadi
bi
Teorema 4 Pada saat kendala persamaan interval dari bentuk (2) dimasukkan pada model, maka solusi worst optimum akan terjadi pada salah satu kendala berikut :
n
(1
a ij
)b
j 1
a j ( x 'j
aij
untuk i 1,...., k , j 1,..., n . Pemecahan Algoritma 2 menghasilkan versi khusus kendala persamaan interval yang memiliki solusi best optimum.
n
(1
a ij
b dengan
j 1
(5), dan z" adalah fungsi objektif yang ditentukan saat PL yang sama dipecahkan n
ajxj
dengan cara mengganti
b dengan
j 1
(6). Berdasarkan asumsi bahwa tit ik worst optimum x memiliki nilai fungsi objektif z , maka z z' dan z z" . Namun, dikarenakan konveksitas dari daerah (3) dan (4), d imana (5) dan (6) merupakan versi persamaan ekstrim dari (3) dan (4), maka z maks[ z ' , z" ] . Hal ini menimbu lkan kontradiksi. Jadi pengandaian bahwa titik
16
worst optimum terjadi ketika sembarang versi n
khusus
kendala
ajxj
persamaan
b
j 1
Contoh 12: Selesaikan LPIC dengan kendala berkoefisien interval berikut : Min Z x1 x2 terhadap: C1 : [2,3]x1
x2
[3,4]
C 2 : x1
[1,2]x 2
[1,3]
C 3 : x1
x2
C4 : x2 x1 , x 2
[ 1,2]
3 0
Dengan menggunakan Teorema 3, maka masing-masing kendala persamaan interval C1 dan C 2 diubah menjadi sepasang kendala
x2
3
C1b : 2 x1
x2
4
C2 a : x1 2 x2
1
C2b : x1
dimasukkan pada PL t idak terbukt i. Oleh karena itu, tit ik worst optimum ditemu kan hanya pada saat kendala yang bersesuaian dengan (5) atau (6) d imasukkan pada PL. Teorema 4 menjelaskan bahwa solusi worst optimum akan terjad i pada persamaan (5) atau (6). Sayangnya, diantara kedua persamaan tersebut tidak diketahui mana yang akan menghasilkan worst optimum pada nilai fungsi objektif. Jadi solusi algorit manya adalah memasukkan masing-masing persamaan (5) dan (6) kedalam model sehingga menghasilkan dua model PL yang berbeda, selanjutnya dipilih nilai yang terburuk pada fungsi objektif tersebut. Secara umu m, jika ada k kendala persamaan interval, maka ada 2 k PL yang harus dipecahkan untuk menemu kan solusi worst optimum.
C1a : 3 x1
C4 : x2 x1, x2
1
3 0
best
Dengan menggunakan Algoritma 2, maka akan didapatkan bentuk umum dari best optimum persamaan interval tersebut, yaitu: Maks a11 a22 b1 b2 terhadap: x1a11 x2 a12 b1 0
x1a21
x2 a22 b2
a11
a11
a11
x2
3
a 22
a22
a 22
C1b : 2 x1
x2
4
C 2a : x1
2x2
1
C 2b : x1
x2
C3a : x1 x2 1 Jadi model best optimum pada LPIC d iatas adalah: Min Z x1 x2 terhadap:
3
Gambar 18. Daerah fisibel solusi optimum pada Contoh 12.
C1a : 3x1
Berdasarkan langkah 1 Algorit ma 1, kendala pertidaksamaan interval C3 diubah men jadi:
x2
Kemudian diselesaikan menggunakan softwere LINGO 8.0 sehingga diperoleh solusi optimu m x1 1, x2 0 dan Z = 1.
pertidaksamaan interval, yaitu:
3
x2
C3a : x1
b1
b1
0
b1
b 2 b2 b 2 Keterangan: a11 = koefisien interval dari variabel x1 pada kendala C1
a12 =
koefisien dari variabel kendala C1
x 2 pada
a 21 =
koefisien dari variabel kendala C 2
x1
a 22 =
koefisien interval dari variabel x 2 pada kendala C 2
b1 =
RHS berbentuk interval pada kendala
C1
pada
17
b2 =
RHS berbentuk interval pada kendala C2
a 11 =
batas bawah koefisien interval a11
a11 = a 22 =
batas atas koefisien interval a11 batas bawah koefisien interval a 22
a 22 = b1 =
batas atas koefisien interval a 22 batas bawah RHS b1
b1 = b2 =
batas atas RHS b1 batas bawah RHS b 2
b 2 = batas atas RHS b 2 Diketahui a12 , a21 adalah nilai tentu, yaitu a12 1, a21 1 dan solusi optimu m x1 1, x2 0 . Nilai-nilai tersebut dimasukkan pada bentuk umu m di atas: Maks a11 a22 b1 b2 terhadap: 1.a11
0.(1) b1
1.1 0.a 22 2 a11 1 a 22
b2
0 0
3 2
3 b1
4
1 b2
3
Dengan menggunakan softwere LINGO 8.0, solusinya adalah a11 3, a22 2, b1 3, b2 1 sehingga susunan best optimum pada C1 adalah C1a : 3x1 x 2 3 dan susunan best optimum pada adalah C2 C2a : x1 2x2 1 .
Model 1: Min Z x1 terhadap:
x2
C1a : 3 x1
x2
3
C2 a : x1
2 x2
1
x2
2
C3b : x1 C4 : x2 x1, x2
x2 3 atau C1b : 2 x1 x2 4 . Pada kendala C2 , solusi worst optimum terjad i pada C1a : 3x1
1 atau C2b : x1 x2 3 . diko mbinasikan dengan C2 C1 menghasilkan 4 model worst
pada C2a : x1 2 x2 Kendala sehingga optimum.
Untuk kendala pertidaksamaan interval C3 , berdasarkan langkah 2 Algoritma 1 diubah men jadi: C3b : x1 x2 2 Jadi 4 model worst optimum adalah sebagai berikut:
0
Dengan menggunakan softwere LINGO 8.0, solusi PL d i atas adalah infeasible. Model 2: Min Z x1 terhadap:
x2
C1a : 3 x1
3
x2
C2b : x1
x2
C3b : x1 C 4 : x2 x1 , x2
3
x2
2
3 0
Dengan menggunakan softwere LINGO 8.0, solusi PL di atas adalah x1 0, x2 3 dan Z = 3. Model 3: Min Z x1 terhadap:
x2
C1b : 2 x1
x2
4
C2 a : x1
2 x2
1
C3b : x1
x2
2
C 4 : x2 x1 , x2
Berdasarkan Teorema 4, untuk mempero leh worst optimum maka 2 kendala persamaan interval menghasilkan 2 2 model. Pada kendala C1 , solusi worst optimum terjadi
3
3 0
Dengan menggunakan softwere LINGO 8.0, solusi PL d i atas adalah infeasible. Model 4: Min Z x1 terhadap: C1b : 2 x1 C2b : x1
x2 x2
C3b : x1 C 4 : x2 x1 , x2
x2
x2 4 3 2
3 0
Dengan menggunakan softwere LINGO 8.0, solusi PL d i atas adalah infeasible. Jadi model yang menghasilkan worst optimum adalah model 2 dengan x1 0, x2 3 dan Z = 3.
18
Algoritma 3 : Algori tma lengkap untuk menyelesaikan LPIC Diberikan k kendala persamaan interval. 1.
Gambar 19. Daerah fisibel solusi worst optimum pada Contoh 12. Daerah fisibel untuk masalah LPIC di atas diperlihatkan pada gambar berikut:
Cari best optimum sebagaimana berikut: 1.1 Ubah k kendala persamaan interval men jadi sepasang pertidaksamaan tak interval dengan menggunakan Teorema 3. 1.2 Buat model terbaik dengan menggunakan langkah 1 Algoritma 1. 1.3 Untuk mempero leh solusi: 1.3.1 Z dan x dipero leh dari solusi model terbaik . 1.3.2 Nilai tentu dari koefisien interval pada kendala pertidaksamaan interval dipero leh melalui langkah 1 Algorit ma 1. 1.3.3 Nilai tentu dari koefisien interval pada kendala persamaan interval diberikan melalu i Algorit ma 2. 2. Cari worst optimum sebagaimana berikut: k
Untuk setiap model diantara 2 model yang diperoleh melalui Teorema 4: 2.1.1 Ubah kendala persamaan interval men jadi persamaan tentu berdasarkan Teorema 4. 2.1.2 Selesaikan dengan membangun model terburuk melalu i langkah 2 Algorit ma 1, cari Z dan x. 2.2 Untuk mempero leh solusi: 2.2.1 Cari model yang menyediakan Z terburuk. 2.2.2 Nilai tentu dari koefisien interval pada model diperoleh dari model terburuk pada langkah 2.2.1. 2.1
Gambar 20.
Daerah fisibel Contoh 12.
LPIC
pada
Berikut ini adalah algorit ma untuk menyelesaikan LPIC d imana kendala berupa persamaan dan pertidaksamaan interval. Algorit ma ini merupakan gabungan dari algorit ma dan teorema sebelu mnya.
IV STUDI KASUS DAN PENYELESAIANNYA Permasalahan berikut merupakan modifikasi dari contoh pada jurnal Linear Programming Problem with Interval Coefficients and An Interpretation for Its Constraints (Molai and Khorram, 2007). Suatu peternakan ayam petelur produktif diberikan ransum berupa campuran enam pakan ternak, yaitu jagung, tepung ikan, kacang hijau, bungkil kedelai, bekatul dan dedak padi. Berdasarkan kandungan gizi, kebutuhan dasar pakan ayam dibedakan
men jadi lima ko mponen, yaitu karbohidrat, lemak, protein kalsiu m dan fosfor. Berikut model u mu m LPIC yang berfungsi meminimu mkan biaya pembelian pakan ternak: Min Z terhadap
6 j 1 6 j 1
c j ,c j x j a ij , a ij x j
bi , bi .
19
Keterangan: c j = biaya pada jenis pakan ternak ke -j
Misalkan peternak memiliki 100 ayam. Tiap ayam mengkonsumsi ransum sebesar 33.5 kg/minggu. Untuk memperoleh bobot ayam yang seimbang diperlukan rans um yang memiliki batasan-batasan sebagaimana ditunjukkan pada Tabel 1 dan Tabel 2.
(Rp/ kg ). a ij = kandungan zat gizi pada jenis pakan ternak ke-j pada kendala ke-i (kg). = batasan zat gizi ke-i yang diperlukan bi dalam ransum (kg). x j = banyaknya jenis pakan ternak ke-j yang dibutuhkan dalam ransum (kg).
Tabel 1. Susunan Zat Gizi pada Pakan Ayam dan Kadar Min imu m Zat Gizi Susunan zat pakan ayam/ a ij (per kg)
j
Jenis Pakan Ayam ke-j
1
Karbohidrat ( a1 j )
Lemak ( a2 j )
Protein ( a3 j )
Kalsiu m ( a4 j )
Fosfor ( a5 j )
Jagung
69-74%
3.7-4.1%
8.5-11%
0.02%
0.25-0.3%
2
Tepung ikan
62-65%
7.8-10%
55-62%
3.8-5%
2.8-3.8%
3
Kacang hijau
55-57%
1.1-1.3%
20-25%
0.2%
1.7%
4
Bungkil kedelai
30%
4%
41-50%
0.2-0.3%
0.6-0.68%
5
Bekatul
51-55%
2.9%
11-12%
0.05%
1.27%
6
Dedak padi
29%
4.9-8.2%
6.8-12%
0.1-0.2%
1-1.7%
43-48%
3-5%
15-18%
3-3.5%
0.55%
Kadar Min imu m Zat Gizi Sumber: Suprijatna et al. (2005)
Tabel 2. Batasan Pakan dalam Ransum dan Harga Pakan Ayam
j 1 2 3 4 5 6
Batasan Pakan Minimu m per kg (%)
Batasan Pakan dalam 3-3.5 kg (kg)
Harga/ c j
Jagung
20%
0.6-0.7
3000
Tepung ikan
5%
0.15-0.175
2800-4400
Kacang hijau
7.50%
0.225-0.2625
7000
Bungkil kedelai
20%
0.6-0.7
5000-6000
Bekatul
15%
0.45-0.525
1400-2200
5%
0.15-0.175
1300-1600
Jenis Pakan Ayam ke-j
Dedak padi Sumber: Nawawi dan Nurroh mah (1996)
(Rp/kg)
Berikut model optimisasi LPIC pada masalah minimisasi biaya pakan ternak diatas: Min Z 3000 x1 [2800,4400]x2 7000 x3 [5000,6000]x4 [1400,2200]x5 [1300,1600]x6 Terhadap: x1 x2 x3 x4 x5 x6 [3,3.5] 100 [0.69,0.74]x1 [0.62,0.65]x2
[0.55,0.57]x3
0.3x4
[0.51,0.55]x5
0.29 x6
[0.43,0.48] 100
[0.037,0.041]x1 [0.078,0.1]x2 [0.011,0.013]x3 0.04 x4 0.029 x5 [0.049,0.082]x6 [0.03,0.05] 100 [0.085,0.11]x1 [0.55,0.62]x2 [0.2,0.25]x3 [0.41,0.5]x4 [0.11,0.12]x5 [0.068,0,12]x6 [0.15,0.18] 100 0.0002 x1 [0.038,0.05]x 2 0.002 x3 [0.002,0.003]x 4 0.0005 x5 [0.001,0.002]x6 [0.03,0.035] 100 [0.0025,0.003]x1 [0.028,0.038]x 2 0.017 x3 [0.006,0.0068]x 4 0.0127 x5 [0.01,0.017]x6 0.0055 100 x1
[0.6,0.7] 100, x 2
[0.15,0.175] 100, x 3
x5
[0.45,0.525] 100, x 6
[0.15,0.175] 100
[0.225,0.2625] 100, x 4
[0.6,0.7] 100
20
Penyederhanaan dari bentuk LPIC diatas, yaitu: Min Z 3000 x1 [2800,4400 ]x 2 7000 x3 [5000,6000 ]x 4 Terhadap: C1 : x1 x 2 x3 x 4 x5 x6 [300,350] C 2 : [0.69,0.74]x1
[0.62,0.65]x 2
[0.55,0.57]x3
0.3x 4
[1400,2200]x5
[0.51,0.55]x5
[1300,1600 ]x6
0.29 x6
[43,48]
C3 : [0.037,0.041]x1 [0.078,0.1]x2 [0.011,0.013]x3 0.04 x4 0.029 x5 [0.049,0.082]x6 [3,5] C 4 : [0.085,0.11]x1 [0.55,0.62]x 2 [0.2,0.25]x3 [0.41,0.5]x 4 [0.11,0.12]x5 [0.068,0,12]x6
[15,18]
C5 : 0.0002 x1 [0.038,0.05]x 2 0.002 x3 [0.002,0.003]x 4 0.0005 x5 [0.001,0.002]x6 [3,3.5] C6 : [0.0025,0.003]x1 [0.028,0.038]x 2 0.017 x3 [0.006,0.0068]x 4 0.0127 x5 [0.01,0.017]x6 0.55 C 7 : x1
[60,70], C 8 : x 2
C11 : x 5
[45,52.5], C12 : x 6
[15,17.5], C 9 : x 3
[22.5,26.25], C10 : x 4
[60,70]
[15,17.5]
Untuk menyelesaikan bentuk LPIC d i atas digunakan Algorit ma 3. Langkah 1.1 C1 diubah menjadi dua kendala pertidaksamaan berdasarkan Teorema 3, yaitu: C1a : x1 x 2 x3 x 4 x5 x6 300 C1b : x1 x 2 x3 x 4 x5 x6 350 Langkah 1.2 Model LPIC diubah men jadi model PL yang memiliki solusi best optimum melalu i langkah 1 Algorit ma 1. Min Z 3000 x1 2800 x2 7000 x3 5000 x4 1400 x5 1300 x6 Terhadap: C1a : x1 x 2 C1b : x1 x 2
x3 x3
x4 x4
x5 x5
x6 x6
300 350
C 2 : 0.74 x1 0.65 x 2 0.57 x3 0.3x 4 0.55 x5 0.29 x6 43 C3 : 0.041x1 0.1x2 0.013 x3 0.04 x4 0.029 x5 0.082 x6 3 C 4 : 0.11x1 0.62 x 2 0.25 x3 0.5x 4 0.12 x5 0,12 x6 15 C5 : 0.0002 x1 0.05 x 2 0.002 x3 0.003 x 4 0.0005 x5 0.002 x6 3 C 6 : 0.003 x1 0.038 x 2 0.017 x3 0.0068 x 4 0.0127 x5 0.017 x6 0.55 C 7 : x1 C11 : x 5
60, C 8 : x 2 45, C12 : x 6
15, C 9 : x3
22.5, C10 : x 4
60
15
Langkah 1.3 1.3.1 Model pada langkah 1.2 diselesaikan dengan menggunakan LINGO 8.0. Nilai best optimum berada pada x1 60 , x 2 52.4 , x3 22.5 , x 4 60 , x5 45 , x 6 60.1 dan Z 925359.4 . 1.3.2 Bentuk
best
optimum
pada
kendala
pertidaksamaan
interval
C 2 , C 3 , C 4 , C5 ,
C6 , C7 , C8 , C9 , C10 , C11 dan C12 diberikan pada langkah 1.2, yaitu: C 2 : 0.74 x1
0.65 x 2
0.57 x3
0.3x 4
0.55 x5
0.29 x6
43
C3 : 0.041x1 0.1x2 0.013 x3 0.04 x4 0.029 x5 0.082 x6 3 C 4 : 0.11x1 0.62 x 2 0.25 x3 0.5x 4 0.12 x5 0,12 x6 15 C5 : 0.0002 x1 0.05 x 2 0.002 x3 0.003 x 4 0.0005 x5 0.002 x6 C 6 : 0.003 x1 0.038 x 2 0.017 x3 0.0068 x 4 0.0127 x5 C 7 : x1 60, C 8 : x 2 15, C 9 : x3 22.5, C10 : x 4 60 C11 : x 5
1.3.3
45, C12 : x 6
0.017 x6
3 0.55
15
Bentuk best optimum pada kendala persamaan interval C1 diberikan melalu i Algorit ma 2. Maksimu mkan b terhadap:
21
x1a1
b
b1
x2 a2
x3 a3
x4 a4
x5 a5
x6 a 6
b
0
b
Dari model diketahui bahwa kendala persamaan C1 : x1
x2
x3
x4
x5
x6
[300,350]
memiliki koefisien a1 a2 a3 a4 a5 a6 1 . Sedangkan dari perhitungan langkah 1 Algorit ma 1 dipero leh x1 60 , x 2 52.4 , x3 22.5 , x 4 60 , x5 45 , x 6 60.1 . Nilainilai tersebut dimasukkan pada PL diatas. Maksimu mkan b terhadap:
(60 1) (52.4 1) (22.5 1) (60 1) (45 1) (60.1 1) b
0
300 b 350 Dengan menggunakan softwere LINGO 8.0, solusi LP d iatas adalah b 300 . Jadi versi khusus kendala persamaan interval yang memiliki solusi best optimum adalah x1 x 2 x3 x 4 x5 x6 300 . Langkah 2.1 2.1.1 Berdasarkan Teorema 4, tit ik worst optimum dari kendala persamaan interval C1 : x1 x 2 x3 x 4 x5 x6 [300,350] akan terjadi pada salah satu dari dua kendala spesifik berikut: C1a : x1 x 2 x3 x 4 x5 x6 300 C1b : x1 x 2 x3 x 4 x5 x6 350 Kendala C1 diubah men jadi dua versi kendala yaitu C1a dan C1b yang akan menghasilkan dua model PL baru. Model LPIC yang dimasukkan kendala C1a dinamakan Model A dan model LPIC yang dimasukkan kendala C1b dinamakan Model B. Berikut bentuk LPIC yang diperbaharui : Model A: Min Z 3000 x1 [2800,4400]x 2 7000 x3 [5000,6000]x 4 [1400,2200]x5 [1300,1600]x6 Terhadap: C1 : x1 x 2 x3 x 4 x5 x6 300 C 2 : [0.69,0.74]x1 [0.62,0.65]x 2 [0.55,0.57]x3 0.3x 4 [0.51,0.55]x5 0.29 x6 [43,48] C3 : [0.037,0.041]x1 [0.078,0.1]x2 [0.011,0.013]x3 0.04 x4 0.029 x5 [0.049,0.082]x6 [3,5] C 4 : [0.085,0.11]x1 [0.55,0.62]x 2 [0.2,0.25]x3 [0.41,0.5]x 4 [0.11,0.12]x5 [0.068,0,12]x6 [15,18] C5 : 0.0002 x1 [0.038,0.05]x 2 0.002 x3 [0.002,0.003]x 4 0.0005 x5 [0.001,0.002]x6 [3,3.5] C6 : [0.0025,0.003]x1 [0.028,0.038]x 2 0.017 x3 [0.006,0.0068]x 4 0.0127 x5 [0.01,0.017]x6 C 7 : x1 [60,70], C 8 : x 2 [15,17.5], C 9 : x 3 [22.5,26.25], C10 : x 4 [60,70] C11 : x 5
[45,52.5], C12 : x 6
0.55
[15,17.5]
Model B Min Z 3000 x1 [2800,4400]x 2 7000 x3 [5000,6000]x 4 [1400,2200 ]x5 [1300,1600]x6 Terhadap: C1 : x1 x 2 x3 x 4 x5 x6 350 C 2 : [0.69,0.74]x1 [0.62,0.65]x 2 [0.55,0.57]x3 0.3x 4 [0.51,0.55]x5 0.29 x6 [43,48] C3 : [0.037,0.041]x1 [0.078,0.1]x2 [0.011,0.013]x3 0.04 x4 0.029 x5 [0.049,0.082]x6 [3,5] C 4 : [0.085,0.11]x1 [0.55,0.62]x 2 [0.2,0.25]x3 [0.41,0.5]x 4 [0.11,0.12]x5 [0.068,0,12]x6 [15,18] C5 : 0.0002 x1 [0.038,0.05]x 2 0.002 x3 [0.002,0.003]x 4 0.0005 x5 [0.001,0.002]x6 [3,3.5]
22
C6 : [0.0025,0.003]x1 [0.028,0.038]x 2
0.017 x3 [0.006,0.0068]x 4
C 7 : x1
[60,70], C 8 : x 2
C11 : x 5
[45,52.5], C12 : x 6
2.1.2
Model A dan model B dipecahkan menggunakan langkah 2 A lgorit ma 1.
Model A: Min Z Terhadap: C1 : x1 x 2 C 2 : 0.69 x1
3000 x1 x3
x4
0.65 x 2
[15,17.5], C 9 : x 3
[60,70]
7000 x3
x6
0.57 x3
6000 x 4
2200 x5
1600 x6
300 0.3x 4
0.55 x5
0.29 x6
48
C3 : 0.037 x1 0.078 x2 0.011x3 0.04 x4 0.029 x5 0.049 x6 5 C 4 : 0.085 x1 0.55 x 2 0.2 x3 0.41x 4 0.11x5 0.068 x6 18 C5 : 0.0002 x1 0.038 x 2 0.002 x3 0.002 x 4 0.0005 x5 0.001x6 C6 : 0.0025 x1 0.028 x 2 0.017 x3 C 7 : x1 70, C 8 : x 2 17.5, C 9 : x 3 C11 : x 5
52.5, C12 : x 6
0.55
[15,17.5]
4400 x 2 x5
[22.5,26.25], C10 : x 4
0.0127 x5 [0.01,0.017]x6
0.006 x 4 0.0127 x5 26.25, C10 : x 4 70
0.01x6
3.5
0.55
17.5
Dengan menggunakan softwere LINGO 8.0, solusi PL d iatas adalah infeasible. Model B: Min Z 3000 x1 4400 x 2 7000 x3 Terhadap: C1 : x1 x 2 x3 x 4 x5 x6 350 C 2 : 0.69 x1
0.65 x 2
0.57 x3
0.3x 4
6000 x 4
0.55 x5
2200 x5
0.29 x6
1600 x6
48
C3 : 0.037 x1 0.078 x2 0.011x3 0.04 x4 0.029 x5 0.049 x6 5 C 4 : 0.085 x1 0.55 x 2 0.2 x3 0.41x 4 0.11x5 0.068 x6 18 C5 : 0.0002 x1 0.038 x 2 0.002 x3 0.002 x 4 0.0005 x5 0.001x6 3.5 C6 : 0.0025 x1 0.028 x 2 0.017 x3 0.006 x 4 0.0127 x5 0.01x6 0.55 C 7 : x1 70, C 8 : x 2 17.5, C 9 : x 3 26.25, C10 : x 4 70 C11 : x 5
52.5, C12 : x 6
Dengan x1
70, x 2
17.5
menggunakan 84.8, x3
26.3, x 4
softwere LINGO 8.0, 70 , x5 52.5 , x 6 46.5 dan Z
solusi
PL
diatas
adalah
1376569 .
Langkah 2.2 2.2.1 Model A memiliki solusi infeasible dan Model B memiliki solusi sebesar Z Jadi model yang memberikan solusi worst optimum adalah Model B.
1376569 .
2.2.2 Versi khusus kendala persamaan dan pertidaksamaan interval yang memiliki solusi worst optimum diberikan pada Model B.
23
Jadi pemecahan masalah pembelian pakan ternak untuk 100 ayam dalam seminggu adalah dengan membeli bahan pakan sebagai berikut: Tabel 3. Pemecahan Masalah Pembelian Pakan Ternak Ayam Pembelian Pakan Ternak/ minggu (kg) Jenis Pakan Ayam j ke-j Best optimum (A) Worst optimum (B)
1 2 3 4 5 6
60
70
Tepung ikan
52.4
84.8
Kacang hijau
22.5
26.3
Bungkil kedelai
60
70
Bekatul
45
52.5
60.1
46.5
Rp.925.359,00
Rp 1.376.569,00
Jagung
Dedak padi
Biaya yang dibutuhkan /minggu (Rp)
Peternak akan me mbutuhkan biaya minimu m dalam pembelian pakan ternak jika peternak memilih ko mb inasi A dengan biaya sebesar Rp.925.359,00. Sedangkan jika peternak memilih ko mbinasi B maka d iperlu kan biaya maksimu m, yaitu Rp1.376.569,00
V SIMPULAN DAN SARAN 5.1 Simpul an PL yang memiliki informasi tak pasti atau data yang kurang tepat mengharuskan pembuat model membuatnya dalam perkiraan. Salah satu cara mengatasinya yaitu digunakan pendekatan interval. Masalah PL ini dinamakan LPIC (Linear programming with Interval Coefficients). Masalah LPIC dapat diselesaikan dengan menggunakan metode Chinneck dan K Ramadan. Metode ini merupakan perluasan dari metode Shaocheng, yaitu dengan menambahkan variabel tak positif dan kendala persamaan interval. Dalam kasus min imisasi, best optimum adalah solusi yang memiliki nilai fungsi objektif terkecil, sedangkan worst optimum adalah solusi yang memiliki nilai fungsi objektif terbesar. Pada kendala pertidaksamaan interval, solusi best optimum dipero leh melalu i langkah 1 Algorit ma 1 (Teorema 1 dan Teorema 2). Sedangkan jika kendala berupa persamaan interval, tiap kendala tersebut diubah menjadi dua pertidaksamaan yang membentuk daerah konveks (Teorema 3). Algorit ma 2 digunakan
untuk mempero leh versi khusus persamaan interval yang memiliki solusi best optimum. Pada kendala pertidaksamaan interval, solusi worst optimum diperoleh melalui langkah 2 A lgorit ma 1 (Teorema 1 dan Teorema 2). Sedangkan jika kendala berupa persamaan interval sebanyak k, maka dapat dibentuk 2k model berdasarkan Teorema 4. Solusi worst optimum adalah nilai fungsi objektif terbesar dari 2k model. Metode Chinneck dan K Ramadan dapat diterapkan dalam pemecahan masalah optimisasi model PL yang memiliki informasi berupa kisaran. Pengambil keputusan dapat mengetahui solusi terbaik atau solusi terburuk yang terjadi pada model tersebut. 5.2 Saran Pada karya ilmiah in i telah dibahas penyelesaian masalah LPIC dengan menggunakan metode Chinneck dan K Ramadan. Penulis menyarankan untuk selanjutnya dilaku kan penyelesaian masalah LPIC dengan metode yang lain.
24
DAFTAR PUSTAKA Chinneck JW, Ramadan K. 2000. Linear programming with interval coefficients. Operational Research Society.51(2):209216. Fraleigh JB. 1969. Probability and Calculus. Philippines: Addison-Wesley. Jeffrey A. 2005. Essential of Engineering Mathematics. Ed ke-2. New York: Chap man&Hall. Molai AA, Khorram E. 2007. Linear programming with interval coefficients and an interpretation for its constraints. Iranian Journal of Science and Technology. 31(A4):369-390.
Nash SG, Sofer A. 1996. Linear and Non linear Programming. New York: McGrawHill. Nawawi NT, Nurroh mah S. 1996. Ransum Ayam Kampung. Jakarta: Penebar Swadaya. Rao SS. 1984. Optimization: Theory and Application. Ed ke-2. New Delhi: Wiley Eastern Limited. Suprijatna E, At mo marsono U, Kartasudjana R. 2008. Il mu Dasar Ternak Unggas. Jakarta: Penebar Swadaya. Winston WL. 1995. Introduction to Mathematical Programming. Ed ke-2. New York: Du xbury.
LAMPIRAN
26
Lampiran 1 Syntax Program LINGO 8.0 untuk Menyelesaikan Masal ah LPIC dengan Kendal a berbentuk Perti daksamaan Interval Contoh 7 Min Z [1,3]x1 [2,4]x2 terhadap: C1 : [2,3]x1 C 2 : x1
[4,6]x 2
[2,4]x 2
C 3 : x1
x2
C 4 : [3,5]x1 C5 : x2 x1 , x 2
[6,9]
5
[ 2, 1] x2
[6,7]
4 0
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi best optimum : min=x1+2*x2; 3*x1+6*x2>=6; x1+4*x2>=5; -x1+x2>=-2; 5*x1+x2>=6; x2<=4; x1>=0;x2>=0; end
Hasil yang dipero leh: Global optimal solution found at iteration: 0 Objective value: 3.000000 Variable Value Reduced Cost X1 1.000000 0.000000 X2 1.000000 0.000000 Row Slack or Surplus Dual Price 1 3.000000 -1.000000 2 3.000000 0.000000 3 0.000000 -0.4736842 4 2.000000 0.000000 5 0.000000 -0.1052632 6 3.000000 0.000000 7 1.000000 0.000000 8 1.000000 0.000000 Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi worst optimum : min=3*x1+4*x2; 2*x1+4*x2>=9; x1+2*x2>=5; -x1+x2>=-1; 3*x1+x2>=7; x2<=4; x1>=0;x2>=0; end
Hasil yang dipero leh: Global optimal solution found at iteration: 4 Objective value: 11.80000 Variable Value Reduced Cost X1 1.800000 0.000000 X2 1.600000 0.000000 Row Slack or Surplus Dual Price 1 11.80000 -1.000000 2 1.000000 0.000000 3 0.000000 -1.800000 4 0.8000000 0.000000 5 0.000000 -0.4000000 6 2.400000 0.000000 7 1.800000 0.000000 8 1.600000 0.000000 Contoh 8: Min Z x1 Terhadap: C1 : x1 x 2 C 2 : [1,2]x1 x1 , x 2
1,3 x 2 [ 2, 1] x2
[5,7]
0
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi best optimum: min=x1+x2; -x1-x2>=-2; 2*x1+x2>=5; x1>=0;x2>=0; end Hasil yang diperoleh adalah LP memiliki solusi infeasible.
Contoh 9: Min Z [1,2]x1 Terhadap:
x2
27
C1 : x1
[2,4]x 2
C 2 : [1,3]x1 x1 , x 2
x2
1 [5,8]
0
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi worst optimum : min=2*x1-x2; -x1+2*x2>=-1; x1+x2>=8; x1>=0;x2>=0; end
min=x1+3*x2; -x1-2*x2>=-1; x1+x2>=7; x1>=0;x2>=0; Hasil yang diperoleh adalah LP memiliki solusi infeasible.
Hasil yang diperoleh adalah LP memiliki solusi unbounded. Jadi LPIC memiliki solusi antara z infeasible. Contoh 11: Min Z [1,3]x1 x2 Terhadap: C1 : [ 2, 1]x1 4 x 2 Contoh 10: Min Z x1 1,3 x2 Terhadap: C1 : x1 [1,2]x 2 [ 3, 1] C 2 : [1,2]x1 x1 , x 2
x2
[2,7]
0
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi best optimum : min=x1+x2; -x1-x2>=-3; 2*x1+x2>=2; x1>=0;x2>=0; Hasil yang dipero leh: Global optimal solution found at iteration: 2 Objective value: 1.000000 Variable Value Reduced Cost X1 1.000000 0.000000 X2 0.000000 0.5000000 Row Slack or Surplus Dual Price 1 1.000000 -1.000000 2 2.000000 0.000000 3 0.000000 -0.5000000 4 1.000000 0.000000 5 0.000000 0.000000 Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi worst optimum :
C 2 : 3x1 x1 , x 2
[ 1,1]x 2
1 dan
1 [5,7]
0
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi best optimum : min=x1-x2; -x1+4*x2>=-1; 3*x1+x2>=5; x1>=0;x2>=0; end Hasil yang diperoleh adalah LP memiliki solusi unbounded.
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi worst optimum : min=3*x1-x2; -2*x1+4*x2>=-1; 3*x1-x2>=7; x1>=0;x2>=0; end Hasil yang dipero leh: Global optimal solution found at iteration: 2 Objective value: 7.000000
28
Variable Value Reduced Cost X1 2.700000 0.000000 X2 1.100000 0.000000 Row Slack or Surplus Dual Price 1 7.000000 -1.000000 2 0.000000 0.000000
3 4 5
0.000000 2.700000 1.100000
-1.000000 0.000000 0.000000
Jadi LPIC memiliki solusi antara antara dan z 7 .
Lampiran 2 Syntax Program LINGO 8.0 untuk Menyelesaikan Masal ah LPIC dengan Kendal a berbentuk Persamaan interval. Contoh 12: Min Z x1 terhadap: C1 : [2,3]x1
x2 x2
[3,4]
C 2 : x1
[1,2]x 2
[1,3]
C 3 : x1
x2
C4 : x2 x1 , x 2
[ 1,2]
3 0
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi best optimum : min=x1+x2; 3*x1+x2>=3; 2*x1+x2<=4; x1+2*x2>=1; x1+x2<=3; -x1+x2>=-1; x2<=3; x1>=0;x2>=0; end Hasil yang dipero leh: Global optimal solution found at iteration: 6 Objective value: 1.000000 Variable Value Reduced Cost X1 1.000000 0.000000 X2 0.000000 0.000000 Row Slack or Surplus Dual Price 1 1.000000 -1.000000 2 0.000000 -0.2000000 3 2.000000 0.000000 4 0.000000 -0.4000000 5 2.000000 0.000000 6 0.000000 0.000000 7 3.000000 0.000000 8 1.000000 0.000000 9 0.000000 0.000000
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi worst optimum : a) Model 1 min=x1+x2; 3*x1+x2=3; x1+2*x2=1; -x1+x2>=2; x2<=3; x1>=0;x2>=0; end Hasil yang diperoleh: So lusi pada Model 1 adalah infeasible.
b) Model 2 min=x1+x2; 3*x1+x2=3; x1+x2=3; -x1+x2>=2; x2<=3; x1>=0;x2>=0; end Hasil yang dipero leh: Global optimal solution found at iteration: 3 Objective value: 3.000000 Variable Value Reduced Cost X1 0.000000 0.000000 X2 3.000000 0.000000 Row Slack or Surplus Dual Price 1 3.000000 -1.000000 2 0.000000 0.000000
29
3 4 5 6 7
0.000000 1.000000 0.000000 0.000000 3.000000
c)
Model 3 min=x1+x2; 2*x1+x2=4; x1+2*x2=1; -x1+x2>=2; x2<=3; x1>=0;x2>=0; end
-1.000000 0.000000 0.000000 0.000000 0.000000
d) Model 4 min=x1+x2; 2*x1+x2=4; x1+x2=3; -x1+x2>=2; x2<=3; x1>=0;x2>=0; end Hasil yang diperoleh: So lusi pada Model 4 adalah infeasible.
Hasil yang diperoleh: So lusi pada Model 3 adalah infeasible.
Lampiran 3. Syntax Program LINGO 8.0 untuk Menyelesaikan Studi Kasus Masalah LPIC. Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi best optimum : min=3000*x1+2800*x2+7000*x3+5000*x4+1400*x5+1300*x6; x1+x2+x3+x4+x5+x6>=300; x1+x2+x3+x4+x5+x6<=350; 0.74*x1+0.65*x2+0.57*x3+0.3*x4+0.55*x5+0.29*x6>=43; 0.041*x1+0.1*x2+0.013*x3+0.04*x4+0.029*x5+0.082*x6>=3; 0.11*x1+0.62*x2+0.25*x3+0.5*x4+0.12*x5+0.12*x6>=15; 0.0002*x1+0.05*x2+0.002*x3+0.003*x4+0.0005*x5+0.002*x6>=3; 0.003*x1+0.038*x2+0.017*x3+0.0068*x4+0.0127*x5+0.017*x6>=0.55; x1>=60; x2>=15; x3>=22.5; x4>=60; x5>=45; x6>=15; end Hasil yang dipero leh: Global optimal solution found at iteration: Objective value:
Variable X1 X2 X3 X4 X5 X6
Value 60.00000 52.40625 22.50000 60.00000 45.00000 60.09375
10 925359.4
Reduced Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000
30
Row 1 2 3 4 5 6 7 8 9 10 11 12 13 14
Slack or Surplus 925359.4 0.000000 50.00000 108.4663 13.62581 72.32812 0.000000 4.005031 0.000000 37.40625 0.000000 0.000000 0.000000 45.09375
Dual Price 1.000000 1237.500 0.000000 0.000000 0.000000 0.000000 31250.00 0.000000 -1756.250 0.000000 -5700.000 -3668.750 -146.8750 0.000000
Syntax program LINGO 8.0 untuk mencari LPIC yang memiliki solusi worst optimum : a)
Model A
min=3000*x1+4400*x2+7000*x3+6000*x4+2200*x5+1600*x6; x1+x2+x3+x4+x5+x6=300; 0.69*x1+0.65*x2+0.57*x3+0.3*x4+0.55*x5+0.29*x6>=48; 0.037*x1+0.078*x2+0.011*x3+0.04*x4+0.029*x5+0.049*x6>=5; 0.085*x1+0.55*x2+0.2*x3+0.41*x4+0.11*x5+0.068*x6>=18; 0.0002*x1+0.038*x2+0.002*x3+0.002*x4+0.0005*x5+0.001*x6>=3.5; 0.0025*x1+0.028*x2+0.017*x3+0.006*x4+0.0127*x5+0.01*x6>=0.55; x1>=70; x2>=17.5; x3>=26.25; x4>=70; x5>=52.5; x6>=17.5; end Hasil yang dipero leh adalah LP memiliki solusi infeasible.
b)
Model B
min=3000*x1+4400*x2+7000*x3+6000*x4+2200*x5+1600*x6; x1+x2+x3+x4+x5+x6=350; 0.69*x1+0.65*x2+0.57*x3+0.3*x4+0.55*x5+0.29*x6>=48; 0.037*x1+0.078*x2+0.011*x3+0.04*x4+0.029*x5+0.049*x6>=5; 0.085*x1+0.55*x2+0.2*x3+0.41*x4+0.11*x5+0.068*x6>=18; 0.0002*x1+0.038*x2+0.002*x3+0.002*x4+0.0005*x5+0.001*x6>=3.5; 0.0025*x1+0.028*x2+0.017*x3+0.006*x4+0.0127*x5+0.01*x6>=0.55; x1>=70; x2>=17.5; x3>=26.25;
31
x4>=70; x5>=52.5; x6>=17.5; end Hasil yang dipero leh: Global optimal solution found at iteration: Objective value:
Variable
Value
X1
70.00000
X2
84.75676
X3
26.25000
X4
70.00000
X5
52.50000
X6
46.49324
6 1376569.
Reduced
Cost 0.000000 0.000000 0.000000 0.000000 0.000000 0.000000 Row 1 2 3 4 5 6 7 8 9 10 11 12 13
Slack or Surplus 1376569. 0.000000 133.7124 11.09045 77.45276 0.000000 3.996122 0.000000 67.25676 0.000000 0.000000 0.000000 28.99324
Dual Price -1.000000 -1524.324 0.000000 0.000000 0.000000 -75675.68 0.000000 -1460.541 0.000000 -5324.324 -4324.324 -637.8378 0.000000
32
