pengoptimuman pada masalah pemrograman linear … · kata kunci: pemrograman linear, koefisien...

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. Pengoptimuman pada Masalah Pemrograman Linear dengan Koefisien Interval.

Dib imbing o leh PRAPTO TRI SUPRIYO dan NUR ALIATININGTYAS.

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 optimum 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

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.

Kata kunci: pemrograman linear, koefisien interval, optimisasi.

ii

ii

ABSTRACT

ANA FARIDA. Optimization in Linear Programming with Interval Coefficients Problems.

Supervised by PRAPTO TRI SUPRIYO and NUR ALIATININGTYAS.

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 optimum solutions are divided into two solutions, best

optimum solution and worst optimum solution. In the case of minimizat ion, best optimum is the

solution that has the smallest objective function value, while the worst optimum is the solution that

has the largest objective function value. The optimum 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 optimum.

Therefore, solution is obtained by solving LP that optimize LPIC model.

Keywords: linear programming, interval coefficient, optimizat ion.

iii

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

iv

iv

Judul Skripsi : Pengoptimuman pada Masalah Pemrograman Linear dengan

Koefisien Interval Nama : Ana Farida

NIM : G54053213

Menyetujui,

Pembimbing I Pembimbing II

Drs.Prapto Tri Supriyo, M.Kom. Dra. Nur Aliatiningtyas, MS.

NIP. 19630715 199002 1 002 NIP. 19610104 198803 2 002

Mengetahui,

Ketua Departemen Matematika

Dr. Berlian Setiawaty, MS.

NIP 19650505 198903 2 004

Tanggal Lulus:

v

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 Pengoptimuman 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.Kom. dan Ibu Dra. Nur Aliatin ingtyas, MS selaku dosen

pembimbing skripsi atas bimbingan, arahan, waktu, kesabaran dan ilmu pengetahuan yang

telah diberikan selama penyusunan skrips i in i.

2. Bapak Dr.Ir. Amril 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 FMIPA 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 Nexuz 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, Mira, Lina, Yuni, 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

vi

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 (SPMB). 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 menjadi pengajar di b imbingan belajar d i

Bogor. Pada tahun 2009 dan 2010 penulis memperoleh beasiswa Bantuan Belajar Mahasiswa

(BBM).

vii

vii

DAFTAR ISI

Halaman

DAFTAR TABEL …………………………………………………………………………. viii

DAFTAR GAMBAR ……………………………………………………………………… viii

DAFTAR LAMPIRAN …………………………………………………………………...... viii

I PENDAHULUAN ……………………………………………………………………… 1

1.1 Latar Belakang …………………………………………………………………… 1

1.2 Tujuan ………………………………………………………………………………. 1

II LANDASAN TEORI ………………………………………………………………… 1

III PEMBAHASAN ………………………………………………………………………... 5

3.1 LPIC dengan kendala pertidaksamaan interval ……………………………………… 7

3.2 LPIC dengan kendala persamaan interval …………………………………………… 13

IV STUDI KASUS DAN PENYELESAIANNYA ………………………………………… 18

V SIMPULAN DAN SARAN ……………………………………………………………… 23

5.1 Simpulan ……………………………………………………………………………… 23

5.2 Saran ………………………………………………………………………………… 23

DAFTAR PUSTAKA ……………………………………………………………………….. 24

LAMPIRAN ………………………………………………………………………………… 25

viii

viii

DAFTAR TABEL

Halaman

1 Susunan Zat Gizi pada Pakan Ayam dan Kadar Min imum Zat Gizi ………………… 19

2 Batasan Pakan dalam Ransum dan Harga Pakan Ayam .............................................. 19 3 Pemecahan Masalah Pembelian Pakan Ternak Ayam ................................................. 23

DAFTAR GAMBAR

Halaman

1 Ilustrasi himpunan konveks dan bukan himpunan konveks .......................................... 3

2 IS pada Contoh 3 ......................................................................................................... 5

3 IIS pada Contoh 3 ........................................................................................................ 6

4 Daerah fisibel C pada Contoh 3 .................................................................................... 6

5 IS pada Contoh 4 ......................................................................................................... 6

6 IIS pada Contoh 4 ........................................................................................................ 6

7 Daerah fisibel III SS pada Contoh 4 ........................................................................ 6

8 IS dan IIS pada Contoh 5 ............................................................................................ 7

9 Ilustrasi irisan himpunan solusi dua pertidaksamaan ( S ) .............................................. 8

10 Ilustrasi gabungan himpunan solusi dua pertidaksamaan ( S ) ....................................... 8

11 S pada Contoh 6 ................................................................ ........................................... 8

12 S pada Contoh 6 ............................................................................................................ 8

13 Daerah fisibel solusi best optimum pada Contoh 7 ........................................................ 11

14 Daerah fisibel solusi worst optimum pada Contoh 7 ...................................................... 11

15 Daerah fisibel LPIC pada Contoh 7 ....................................................... ........................ 12

16 Daerah fisibel pada Contoh 10 ..................................................................................... 13

17 Daerah fisibel pada Contoh 11 ..................................................................................... 13

18 Daerah fisibel solusi best optimum pada Contoh 12 ...................................................... 16

19 Daerah fisibel solusi worst optimum pada Contoh 12 .................................................... 18

20 Daerah fisibel LPIC pada Contoh 12 ............................................................................ 18

DAFTAR LAMPIRAN

Halaman

1 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah LPIC dengan Kendala

berbentuk Pertidaksamaan Interval …………………………………………………… 26

2 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah LPIC dengan Kendala

berbentuk Persamaan interval ……………………………………………………… 28

3 Syntax Program LINGO 8.0 untuk Menyelesaikan Studi Kasus Masalah LPIC …… 29

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, dimulai dari model

kendala berbentuk upper-bound dan lower-

bound ( unn cxaxaxac ...22111 ).

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 optimum

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 menemukan

solusi optimum 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 Chinneck 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 ),....,,( 21 nxxxf adalah fungsi

dalam variabel-variabel nxxx ,....,, 21. Fungsi

),....,,( 21 nxxxf dinamakan fungsi linear jika

dan hanya jika ada konstanta nccc ,...,, 21 ,

nnn xcxcxcxxxf ....),....,,( 221121 .

(Winston, 1995)

Sebagai contoh, 2121 2),( xxxxf

adalah fungsi linear, sedangkan 22121 ),( xxxxf bukan fungsi linear.

Definisi 2 (Persamaan dan Pertidaksamaan

Linear)

Untuk sembarang fungsi linear

),....,,( 21 nxxxf dan sembarang bilangan b,

suatu persamaan bxxxf n ),....,,( 21 disebut

persamaan linear dan bxxxf n ),....,,( 21 atau

bxxxf n ),....,,( 21disebut pertidaksamaan

linear.

(Winston, 1995)

Pemrograman Linear

Pemrograman linear (PL) adalah masalah

optimisasi yang memiliki karakteristik sebagai

berikut:

1. Tujuan masalah tersebut adalah

memaksimumkan atau memin imumkan

fungsi linear dari sejumlah 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 ix ,

pembatasan tanda menentukan ix harus

tak negatif 0ix atau tidak dibatasi

tandanya (unrestricted in sign).

(Winston, 1995)

Definisi 3 (Bentuk Standar PL)

Suatu PL memiliki bentuk standar

sebagai berikut:

min xcTz

terhadap kendala bAx (1 )

0b dan 0x

dimana x dan c adalah vektor berukuran n,

vektor b berukuran m dan A berupa matriks

berukuran m x n yang disebut juga matriks

kendala dengan nm .

(Nash dan Sofer, 1996)

Contoh 1

Misalkan diberikan PL standar sebagai

berikut:

Min 21 2xxz

terhadap kendala:

10282

32

51

421

321

xxxxx

xxx (2)

dengan 0,,,, 54321 xxxxx

Fungsi objektif adalah 21 2xxz

Variabel keputusan adalah 54321 ,,,, xxxxx

1083

,

10002

01021

00121

0

00

21

,

5

4

3

2

1

bA

cx

x

x

x

x

x

Solusi Pemrograman Linear

Suatu masalah PL dapat diselesaikan

dalam berbagai tekn ik, salah satunya adalah

metode simpleks. Metode ini dapat

menghasilkan suatu solusi optimum bagi

masalah PL dan telah dikembangkan Dantzig

sejak tahun 1947, dan dalam

perkembangannya merupakan metode yang

paling umum digunakan untuk menyelesaikan

PL. Metode ini berupa metode iteratif untuk

menyelesaikan PL berbentuk standar.

Pada masalah PL (1), vektor x yang

memenuhi kendala bAx disebut solusi PL

(1). Misalkan matriks A dapat dinyatakan

sebagai NBA , 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

N

B

x

xx , dengan Bx adalah vektor variabel

basis dan Nx adalah vektor variabel nonbasis,

maka bAx dapat dinyatakan sebagai

bNxBx

x

xNBAx

NB

N

B

(3 )

Karena matriks B adalah matriks taksingular,

maka B memiliki invers, sehingga Bx dapat

dinyatakan sebagai:

N11

B NxBbBx (4)

Kemudian, fungsi objektifnya berubah

menjadi:

min NT

NBT

B xcxcz

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. kolom-kolom dari matriks kendala yang

berpadanan dengan komponen tak nol

dari solusi tersebut adalah bebas linear.


Definisi 5 (Solusi Fisibel)

Sembarang solusi yang memenuhi

kendala bAx dan 0x disebut solusi

fisibel.

(Rao,1984)

Definisi 6 (Solusi Fisibel Basis)

Vektor x disebut solusi fisibel basis jika x

merupakan solusi basis dan 0x .


Ilustrasi solusi basis dan solusi fisibel basis

diberikan dalam Contoh 2.

3

Contoh 2

Misalkan diberi PL berikut:

Min 21 xxz

terhadap kendala:

10

83

32

51

421

321

xx

xxx

xxx

(5 )

dengan 0,,,, 54321 xxxxx ,

maka d iperoleh:

1083

,

10001

01031

00121

bA

Misalkan dip ilih T

543 xxxBx dan

T21 xxNx , maka matriks basisnya

adalah

100010001

B

0

32

1

11

N

TT011Bc ,

TT00Nc

Dengan menggunakan matriks basis di atas,

maka d iperoleh T

00Nx

T1083bBx

1B (6 )

11bBc1T

Bz

Solusi (6) merupakan solusi basis, karena

memenuhi kendala pada PL (5) dan kolom-

kolom pada matriks kendala yang berpadanan

dengan komponen tak nol dari (6) yaitu B,

bebas linear (kolom yang satu bukan

merupakan kelipatan dari kolom yang lain).

Solusi (6) juga merupakan solusi fisibel basis,

karena nilai-nilai variabelnya leb ih dari atau

sama dengan nol.

Definisi 7( Daerah Fisibel)

Daerah fisibel suatu PL adalah himpunan

semua titik yang memenuhi seluruh kendala

PL dan batasan tanda PL .

(Winston, 1995)

Definisi 8 (Solusi Optimum)

Solusi optimum suatu PL adalah solusi

fisibel yang mengoptimumkan fungsi objektif.

(Rao,1984)

Definisi 9 ( Himpunan Konveks)

Misalkan S adalah himpunan titik.

Himpunan S disebut himpunan konveks jika

segmen garis yang menghubungkan

sembarang titik-t itik dalam S seluruhnya

termuat dalam S. Dengan kata lain, himpunan nRS disebut himpunan konveks, jika

untuk tiap Sxx 21, berlaku

Sxx 21 )1( dengan 1,0 .

(Winston, 1995)

Ilustrasi himpunan konveks dan bukan

himpunan konveks diberikan pada gambar

dibawah in i.

(i) (ii)

(iii) (iv)

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.

Teorema 1

Daerah fisibel dari PL adalah konveks.

(Rao,1984)

Bukt i:

Daerah fisibel S dari PL standar

didefinisikan sebagai }0,|{ xbAxxS .

Misalkan t itik 1x dan 2x termasuk dalam

himpunan S, maka

0, 11 xbAx (1)

0, 22 xbAx (2)

Jika persamaan (1) dikalikan dengan

dan persamaan (2) dikalikan dengan 1 ,

10 dan kemudian keduanya

dijumlahkan, maka didapat:

(3) ])1([

))1((])1([

)1(])[1( ][

)1( ])[1(

][

21

21

21

2

1

bxxA

bxxA

bbAxAx

bAx

bAx

Misalkan 21 )1( xxx

4

Persamaan (3) dapat ditulis sebagai bAx .

Berdasarkan defin isi, maka Sx atau

Sxx 21 )1( .

Jadi }0,|{ xbAxxS adalah konveks.

Teorema 1 terbukti.

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 Sx adalah titik ekstrim, maka tidak

ada Sxx 21, sehingga Sxx 21 )1(

untuk )1,0( . Dengan kata lain, jika x

titik ekstrim dan Sxx 21 )1( untuk

)1,0( maka 21 xxx .

(Rao, 1984)

Teorema 2

Semua solusi fisibel basis adalah titik ekstrim

dari himpunan konveks dari solusi fisibel.

(Rao, 1984)

Bukt i:

Misalkan ]0,..,0,,,....,,[ 121 mm bbbbx

adalah suatu solusi fisibel basis untuk PL.

Dari Teorema 1 diketahui bahwa daerah

fisibel adalah himpunan konveks.

Misalkan Sx bukan tit ik ekstrim, maka

ada Szy, dimana zy sedemikian

sehingga zyx )1( , 10 (4)

Diketahui bahwa

]0,..,0,,,....,,[ 121 mm bbbbx

],..,,,....,,[ 121 nmm yyyyyy

],..,,,....,,[ 121 nmm zzzzzz

untuk 1mj diketahui 0jx dan dari

persamaan (4)

jjj zyx )1(

dimana 0,0,0λ jj zy . Hal ini hanya

akan terjadi jika 0jy dan 0jz . Selain itu

karena x, y dan z fisibel maka

bAx

bAy (5)

bAz

Misalkan ja kolom ke-j dari matriks A

maka persamaan (5) dapat ditulis sebagai

berikut:

ba j j

n

j

x

1

ba j j

n

j

y

1

(6)

ba j j

n

j

z

1

karena untuk 1mj , elemen 0jx ,

0jy dan 0jz maka persamaan (6)

secara individu dapat ditulis

ba j j

m

j

x

1

(7.a)

ba j j

m

j

y

1

(7.b )

ba j j

m

j

z

1

(7.c)

Jika persamaan (7.b) dikurangi oleh

persamaan (7.c) menghasilkan

0)(

0

1

11

jj

m

j

j

m

j

j

m

j

zy

zy

j

jj

a

aa

Karena untuk mj , ja adalah kolom

dari matriks A yang bersesuaian dengan

variabel basis maka ja ( mj ,...,1 ) saling

bebas linear (Definisi 4).

Karena ja saling bebas linear, maka

0)(

1

jj

m

j

zyja menyebabkan 0jj zy

untuk mjj ,...,1, . Akibatnya jj zy ,

mj1 .

Seperti telah diketahui sebelumnya

0jj zy untuk njm 1 , maka

zy . Hal ini kontradiksi dengan fakta yang

diasumsikan bahwa zy . Karena itu x

haruslah titik ekstrim. Terbukti.

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 ),( ba dan ba . Interval

tertutup ],[ ba dari a ke b adalah

}|{ bxax .

(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

menjadi kasus min imisasi dengan cara

mengalikan fungsi objektif dengan (-1). Pada

kasus min imisasi, best optimum adalah solusi

optimum dengan nilai fungsi objektif terkecil

dan worst optimum adalah solusi optimum

dengan nilai fungsi objekt if 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.

Suatu kendala berkoefisien interval akan

memiliki kendala spesifik (kendala dengan

koefisien tentu) berjumlah tak hingga. Jadi

untuk memperoleh solusi optimum, 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, IC dan

IIC adalah dua himpunan kendala berbeda

yang dibangkitkan dari C dengan

menggunakan versi ekstrim C . Daerah fisibel

yang memenuhi kendala IC disebut IS ,

sedangkan daerah fisibel yang memenuhi

kendala IIC disebut IIS . Daerah fisibel

tersebut memiliki hubungan sebagai berikut:

1. III SS atau III SS , yaitu suatu

daerah fisibel seluruhnya termuat

dalam daerah fisibel lainnya.

2. III SS dan III SS , yaitu

suatu daerah fisibel memotong

sebagian daerah fisibel lainnya.

3. III SS , yaitu tidak ada tumpang

tindih (overlap) pada daerah-daerah

fisibel.

Contoh 3:

Misalkan C adalah himpunan kendala

sebagai berikut:

0,

]3,2[

]2,1[22

21

21

21

xx

xxb

xxa

C .

Jadi dapat diambil kendala spesifik IC dan

IIC sebagai berikut:

0,

2

222

21

21

21

xx

xxb

xxa

C I

I

I

0,

3

122

21

21

21

xx

xxb

xxa

C II

II

II

Gambar 2. IS pada Contoh 3.

6

Gambar 3. IIS pada Contoh 3.

maka III SS , sebagaimana diilustrasikan

oleh Gambar 4.

Gambar 4. Daerah fisibel C pada Contoh 3.

Contoh 4:

Misalkan C adalah himpunan kendala

sebagai berikut:

0,

4]4,3[

2]2,1[

21

21

21

xx

xxb

xxa

C .



0,

43

22

21

21

21

xx

xxb

xxa

C I

I

I

0,

44

2

21

21

21

xx

xxb

xxa

C II

II

II

Gambar 5. IS pada Contoh 4.

Gambar 6. IIS pada Contoh 4.

maka III SS dan III SS sebagaimana

diilustrasikan oleh Gambar 7.

Gambar 7. Daerah fisibel III SS pada

Contoh 4.

Contoh 5:

Misalkan himpunan kendala C sebagai

berikut:

2

2

1]1,1[]1,1[

2

1

21

xc

xb

xxa

C .



2

2

1

2

1

21

xc

xb

xxa

CI

I

7

2

2

1

2

1

21

xc

xb

xxa

CII

II

maka III SS sebagaimana

diilustrasikan pada Gambar 8.

Gambar 8. IS dan IIS pada Contoh 5.

Permasalahan model LPIC dibagi

menjadi dua, yaitu menyelesaikan LPIC

dengan kendala berupa pertidaksamaan

interval dan menyelesaikan LPIC dengan

kendala persamaan interval.

3.1 LPIC dengan kendala pertidaksamaan

interval

Bentuk umum model LPIC dengan

kendala berupa pertidaksamaan interval

adalah sebagai berikut:

Min

n

j

jjj xccZ

1

,

terhadap: n

j

iijijij bbxaa

1

, , , (1)

untuk mi ,...,1

,jsi0 xxjx

dan 0jx

untuk

sixjx . )(,,,,, Ibbaacc iiijijjj dimana )(I adalah himpunan seluruh

bilangan interval pada .

Keterangan:

x = ),....,,,( 321 nxxxx , dimana jx adalah

variabel ke-j.

x0

= variabel-variabel yang yang tidak

terkait dengan koefisien interval,

baik variabel tak negatif ( 0jx )

atau variabel tak positif ( 0jx )

maupun variabel urs (unrestricted in

sign).

xsi

= variabel-variabel yang terkait dengan

koefisien interval, berupa variabel

tak negatif atau variabel tak positif.

ija = batas atas koefisien interval dari

variabel ke-j pada kendala ke-i.

ija = batas bawah koefisien interval dari

variabel ke-j pada kendala ke-i.

ib = batas bawah koefisien interval dari

nilai ruas kanan/RHS (Right Hand Side)

pada kendala ke-i.

ib = batas bawah koefisien interval dari

nilai ruas kanan/RHS pada kendala

ke-i.

jc = batas atas koefisien interval variabel

ke-j pada fungsi objektif.

jc = batas bawah koefisien interval

variabel ke-j pada fungsi objekt if.

Tiap pertidaksamaan i pada (1) yang

memiliki p koefisien interval dapat

ditransformasikan menjadi p2

pertidaksamaan ekstrim yang berbeda.

Pertidaksamaan tersebut diperoleh dengan

cara mengombinasikan nilai batas atas dan

batas bawah koefisien. Solusi optimum

diperoleh dengan memilih satu versi

pertidaksamaan ekstrim dari p2

pertidaksamaan ekstrim yang

mengoptimumkan 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 kS adalah himpunan solusi

pertidaksamaan ekstrim ke-k diantara p2

pertidaksamaan ekstrim yang berbeda dari i.

Misalkan p

kkSS

2

1 adalah gabungan dari

seluruh himpunan solusi pertidaksamaan

ekstrim dan p

kkSS

2

1adalah 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 ).

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 maksimum. Sedangkan jika suatu versi

ekstrim pada formula karakteristik

sedemikiran rupa sehingga himpunan

solusinya sama dengan S , maka versi ini

disebut dengan disebut pertidaksamaan range

nilai min imum.

Contoh 6:

]6,4[]5,2[3,1 21 xx , dimana 0, 21 xx .

Pertidaksamaan interval ini memiliki 3

koefisien interval sehingga dapat dipecah

menjadi 823 pertidaksamaan ekstrim :

(a) 42 21 xx (e) 423 21 xx

(b) 62 21 xx (f) 623 21 xx

(c) 45 21 xx (g) 453 21 xx

(d) 65 21 xx (h) 653 21 xx

Gambar 11. S pada Contoh 6.

Gambar 12. S pada Contoh 6.

Dapat dilihat dari Gambar 11 dan Gambar 12

bahwa 453| 212 xxxS , sehingga

pertidaksamaan 453 21 xx (g) disebut

pertidaksamaan range nilai maksimum.

Sedangkan 62| 212 xxxS

sehingga

pertidaksamaan 62 21 xx (b) disebut

pertidaksamaan range nilai minimum.

Teorema 1

Jika ada pertidaksamaan interval

bbxaa j

n

j

jj , ,

1

dimana si0

xxjx ,

0jx untuk

sixjx , maka bxa j

n

j

j

1

adalah pertidaksamaan range nilai maksimum

dan

n

j

jj bxa

1

adalah pertidaksamaan

range nilai minimum.

9

Bukt i:

Misalkan

n

j

jj bxa

1

adalah sembarang

versi khusus pertidaksamaan interval. Maka

untuk sembarang solusi khusus 0jx

dimana sixjx , kita mempunyai

n

j

n

j

jjjj xaxa

1 1

. Misalkan x memenuhi

n

j

jj bxa

1

, maka x memenuhi

n

j

jj bbxa

1

. Akibatnya x juga

memenuhi

n

j

jj bxa

1

,untuk

bbbb, .

Jadi terdapat sebuah titik x yang harus

memenuhi seluruh versi pertidaksamaan

interval lain secara bersamaan. Akibatnya,

berdasarkan Defin isi 1,

n

j

jj bxa

1

adalah


Untuk sembarang solusi khusus 0jx

dimana sixjx , kita juga memiliki

n

j

n

j

jjjj bbxaxa

1 1

. Misalkan x

memenuhi

n

j

jj bxa

1

, maka x juga

memenuhi

n

j

jj bxa

1

. Akibatnya x

memenuhi

n

j

jj bxa

1

, untuk

bbbb, . Oleh karena itu, solusi x yang

memenuhi sembarang versi pertidaksamaan

interval juga akan dipenuhi oleh n

j

jj bxa

1

. Jadi berdasarkan Defin isi 1,

n

j

jj bxa

1

adalah pertidaksamaan range

nilai maksimum.

Akibat 1

Untuk 0jx

dimana sixjx , maka

bxa j

n

j

j

1


nilai maksimum dan

n

j

jj bxa

1

adalah


Bukt i:

Misalkan

n

j

jj bxa

1

adalah sembarang

versi khusus pertidaksamaan interval. Maka

untuk sembarang solusi khusus 0jx

dimana sixjx , kita mempunyai

n

j

n

j

jjjj xaxa

1 1

. Misalkan x memenuhi

n

j

jj bxa

1

, maka x juga memenuhi

n

j

jj bbxa

1

. Akibatnya x juga

memenuhi

n

j

jj bxa

1

,untuk

bbbb, .

Jadi terdapat sebuah titik x yang harus

memenuhi seluruh versi pertidaksamaan

interval lain secara bersamaan. Akibatnya,

berdasarkan Defin isi 1,

n

j

jj bxa

1

adalah


Untuk sembarang solusi khusus 0jx

dimana sixjx , kita juga memiliki

n

j

n

j

jjjj bbxaxa

1 1

. Misalkan x

memenuhi

n

j

jj bxa

1

, maka x juga

memenuhi

n

j

jj bxa

1

. Akibatnya x

memenuhi

n

j

jj bxa

1

, untuk

bbbb, . Oleh karena itu, solusi x yang

memenuhi sembarang versi pertidaksamaan

interval juga akan dipenuhi oleh

10

n

j

jj bxa

1

. Jadi berdasarkan Defin isi 1,

n

j

jj bxa

1


nilai maksimum.

Teorema 2

Jika j

n

j

jj xccZ

1

, adalah fungsi objektif

untuk 0jx dimana sixjx , maka

n

j

n

j

jjjj xcxc

1 1

untuk solusi x yang

diberikan.

Bukt i:

Diketahuti cc

dan 0jx dimana

sixjx , maka

jj xcxc . Untuk

nj ,...,2,1 dapat ditulis:

n

j

n

j

jjjj

nn

xcxc

xcxc

xcxc

xcxc

1 1

22

11

....

....

Jadi

n

j

n

j

jjjj xcxc

1 1

berlaku untuk solusi

x yang diberikan.

Akibat 2

Untuk 0jx , dimana sixjx , maka

n

j

n

j

jjjj xcxc

1 1

Bukt i:

Diketahuti cc

dan 0jx dimana

sixjx , maka

jj xcxc . Untuk

nj ,...,2,1 dapat ditulis:

n

j

n

j

jjjj

nn

xcxc

xcxc

xcxc

xcxc

1 1

22

11

....

....

Jadi

n

j

n

j

jjjj xcxc

1 1

berlaku untuk solusi

x yang diberikan.

Definisi 2

Untuk masalah min imisasi dengan 0jx

dimana sixjx

,

n

j

jj xc

1

dinamakan

fungsi objektif terbaik (most favourable

objective function) dan

n

j

jj xc

1

dinamakan

fungsi objektif terburuk (least favourable

objective function) .

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 maksimum

untuk menentukan solusi best optimum.

Sedangkan untuk menentukan solusi worst

optimum, digunakan fungsi objektif terburuk

dan pertidaksamaan range nilai min imum

Algoritma 1: Penyelesaian LPIC dengan

kendala berupa pertidaksamaan interval.

Diberikan : min n

jjjj xccZ

1 , dengan

kendala n

jiijijij bbxaa

1,, , dimana

mi ,...,1 dan jx , )xx( 0 sijx .

1. Bentuk LPIC menjadi PL:

Min

n

j

jj xcz

1

', dimana

sixjx

Berdasarkan Teorema 2 cukup dipilih:

0,

0,'

jj

jj

jxc

xcc

terhadap:

11

n

j

iijij bxa

1

' , , dimana sixjx


0,

0,'

jij

jij

ijxa

xaa

Dicari best optimum dengan

menyelesaikan PL diatas.

2. Bentuk LPIC menjadi PL:

Min

n

j

jj xcz

1

" , dimana sixjx


0,

0,"

jj

jj

jxc

xcc

terhadap:

n

j

iijij bxa

1

," , dimana sixjx


0,

0,"

jij

jij

ijxa

xaa

Dicari worst optimum dengan

menyelesaikan PL diatas.

Algoritma 1 menggambarkan metode

umum untuk mengatasi kasus min imisasi pada

LPIC dengan kendala yang memiliki batasan

saja. Jika kendala memiliki batasan

maka kendala tersebut dikalikan dengan (-1).

Contoh 7:

Selesaikan LPIC dengan kendala

pertidaksamaan interval berikut:

Min 21 ]4,2[]3,1[ xxZ

terhadap:

0,

4:

]7,6[]5,3[:

]1,2[:

5]4,2[:

]9,6[]6,4[]3,2[:

21

25

214

213

212

211

xx

xC

xxC

xxC

xxC

xxC

Dengan menggunakan Algoritma 1, maka

akan didapatkan solusi best optimum dari PL

sebagai berikut:

Min 21 2xxz

terhadap:

0,

4:

65:

2:

54:

663:

21

25

214

213

212

211

xx

xC

xxC

xxC

xxC

xxC

a

a

a

a

Kemudian diselesaikan menggunakan

softwere LINGO 8.0 sehingga diperoleh solusi

optimum 1,1 21 xx dan Z = 3.

Gambar 13. Daerah fisibel solusi best

optimum pada Contoh 7.

Sedangkan untuk solusi worst optimum, LPIC

tersebut diubah menjadi PL sebagai berikut:

Min 21 43 xxz

terhadap:

0,

4:

73:

1:

52:

942:

21

25

214

213

212

211

xx

xC

xxC

xxC

xxC

xxC

b

b

b

b



optimum 6.1,8.1 21 xx dan Z = 11.8.

Gambar 14. Daerah fisibel solusi worst


Daerah fisibel untuk masalah LPIC di atas

diperlihatkan pada gambar berikut:

12

Gambar 15. Daerah fisibel LPIC pada

Contoh 7.

Sebagaimana PL b iasa, PL pada

Algoritma 1 memiliki 3 hasil yang mungkin,

yaitu: (i) t itik optimum 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 21 3,1 xxZ

terhadap:

0,

]7,5[]2,1[:

]1,2[:

21

212

211

xx

xxC

xxC

Solusi best optimum pada masalah

LPIC d i atas adalah sebagai berikut:

Min 21 xxZ

terhadap:

0,

52:

2:

21

212

211

xx

xxC

xxC

a

a

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 optimum unbounded,

maka seluruh LPIC unbounded.

Contoh 9:

Min 21]2,1[ xxZ

terhadap:

0,

]8,5[]3,1[:

1]4,2[:

21

212

211

xx

xxC

xxC

Solusi worst optimum pada masalah


Min 212 xxZ

terhadap:

0,

8:

12:

21

212

211

xx

xxC

xxC

b

b


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 optimum memiliki

range antara z dan infeasibility.

Contoh 10:

Min 21 3,1 xxZ

terhadap:

0,

]7,2[]2,1[:

]1,3[]2,1[:

21

212

211

xx

xxC

xxC

Pada kendala 1C , koefisien interval

pada 2x bertanda negatif. Oleh karena itu,

kendala in i diubah terlebih dahulu

menjadi:

]1,3[]1,2[: 211 xxC



Min 21 xxZ

terhadap:

0,

22:

3:

21

212

211

xx

xxC

xxC

a

a


8.0, solusi dari PL tersebut adalah

0,1 21 xx dan 1z .

Sedangkan solusi worst optimum

pada masalah LPIC di atas adalah sebagai

berikut:

Min 21 3xxZ

terhadap:

0,

7:

12:

21

212

211

xx

xxC

xxC

b

b

13



infeasible.

Jadi masalah LPIC tersebut memiliki

nilai optimum yang berada antara 1z

dan infeasibility. Daerah fisibel pada

solusi best optimum digambarkan sebagai

berikut:

Gambar 16. Daerah fisibel pada Contoh

10.

Jika solusi worst optimum feasible

dengan nilai z dan best optimum

unbounded, maka LPIC yang optimum

memiliki range antara dan z .

Contoh 11:

Min 21]3,1[ xxZ

terhadap:

0,

]7,5[]1,1[3:

14]1,2[:

21

212

211

xx

xxC

xxC



Min 21 xxZ

terhadap:

0,

53:

14:

21

212

211

xx

xxC

xxC

a

a



unbounded. Sedangkan solusi worst

optimum pada masalah LPIC d i atas

adalah sebagai berikut:

Min 213 xxZ

terhadap:

0,

73:

142:

21

212

211

xx

xxC

xxC

b

b



1.1,7.2 21 xx dan 7z .

Jadi masalah LPIC tersebut memiliki

nilai optimum yang berada antara

dan 7z . Daerah fisibel pada solusi

worst optimum digambarkan sebagai

berikut:

Gambar 17. Daerah fisibel pada

Contoh 11.

3.2 LPIC dengan kendala persamaan

interval

Bentuk umum model ini adalah sebagai

berikut:

Min

n

j

jjj xccZ

1

,

Dengan kendala n

j

iijijij bbxaa1

, , ,

(1)

untuk mi ,...,1

,jsi0 xxjx

dan 0jx

untuk

sixjx . )(,,,,, Ibbaacc iiijijjj 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 Algoritma 2.

Pada Teorema 4 menjelaskan metode untuk

mencari solusi worst optimum.

14

Teorema 3

Pada kendala persamaan berbentuk interval

n

j

jjj bbxaa

1

,, (2)

maka sepasang kendala pertidaksamaan

berikut:

n

j

jj bxa

1

' , sixjx

0,

0,'

jj

jj

j xa

xaa (3)

.

n

j

jj bxa

1

"

, sixjx

0,

0,"

jj

jj

jxa

xaa (4)

mendefinisikan daerah konveks dimana tiap

titiknya memenuhi sembarang versi khusus


Bukt i:

Misalkan x adalah suatu titik yang memenuhi

sembarang versi khusus persamaan interval

n

j

jj bxa

1

.

Untuk

0jx dimana sixjx , maka

n

j

n

j

n

j

jjjjjj xabxaxa

1 1 1

)(

dan

bbb .

Oleh karena itu, n

j

n

j

jjjj bbxaxa

1 1

)( , maka x juga

memenuhi

n

j

jj bxa

1

. Selain itu,

n

j

n

j

jjjj xabxab

1 1

)( , maka x juga

memenuhi

n

j

jj xab

1

atau

n

j

jj bxa

1

.

Jadi x memenuhi pertidaksamaan n

j

jj bxa

1

dan

n

j

jj bxa

1

.

Misalkan }0,|{

1

1 j

n

j

jj xbxaS x dan

S21 x,x dimana ),...,,( ''2

'1 nxxx1x ,

),...,,( ""2

"1 nxxx2x , maka:

n

j

jj bxa

1

' , dimana 0'jx (a)

n

j

jj bxa

1

" , dimana 0"jx (b)

Jika persamaan (a) dikalikan dengan dan

persamaan (b) dikalikan dengan 1 ,



))1((

)1()1(

)1()1(

1

"'

1 1

"'

1

"

1

'

bxxa

bbxaxa

bxa

bxa

n

j

jjj

n

j

n

j

jjjj

n

j

jj

n

j

jj

1"'"

1'1 ))1(,....,)1(( Sxxxx nn

1""

1''

1 ),....,)(1(),....,( Sxxxx nn

1)1( S21 xx

Jadi }0,|{

1

1 j

n

j

jj xbxaS x adalah

daerah konveks.

Misalkan }0,|{

1

2 j

n

j

jj xbxaS x dan

S21 x,x dimana ),...,,( ''2

'1 nxxx1x ,

),...,,( ""2

"1 nxxx2x , maka:

n

j

jj bxa

1

' , dimana 0'jx (d)

n

j

jj bxa

1

" , dimana 0"jx (e)

Jika persamaan (d) dikalikan dengan dan

persamaan (e) d ikalikan dengan 1 ,



15

))1((

)1()1(

)1()1(

1

"'

1 1

"'

1

"

1

'

bxxa

bbxaxa

bxa

bxa

n

j

jjj

n

j

n

j

jjjj

n

j

jj

n

j

jj

1"'"

1'1 ))1(,....,)1(( Sxxxx nn

1""

1''

1 ),....,)(1(),....,( Sxxxx nn

1)1( S21 xx

Jadi }0,|{

1

2 j

n

j

jj xbxaS x adalah

daerah konveks.

Jadi pertidaksamaan (3) dan (4)

merupakan daerah konveks dimana tiap

titiknya memenuhi sembarang versi khusus


Pembuktian in i analog untuk 0jx dimana

sixjx .

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

bentuk

n

j

jjj bbxaa

1

,, dan titik best

optimum *x yang telah diperoleh melalui

Torema 3. Dicari ija dan ib yang

mengoptimumkan model.

Selesaikan Phase I dari PL untuk himpunan

kendala berikut:

Maks

k

i

n

j

k

i

iij ba

1 1 1

terhadap :

n

j

iijj bax

1

0 , untuk

ki ,....,1

iii

ijijij

bbb

aaa ,

untuk njki ,...,1,,....,1 .

Pemecahan Algoritma 2 menghasilkan

versi khusus kendala persamaan interval yang

memiliki solusi best optimum.

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

j

ijij bxa1

' , dimana

0,

0,'

jij

jij

ij xa

xaa (5)

atau n

j

ijij bxa1

" , dimana

0,

0,"

jij

jij

ijxa

xaa (6)

Bukt i:

Andaikan titik worst optimum x memenuhi

sembarang versi khusus kendala persamaan

interval

n

j

jj bxa

1

dan memiliki nilai

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

dengan cara mengganti

n

j

jj bxa

1

dengan

(5), dan "z adalah fungsi objektif yang

ditentukan saat PL yang sama dipecahkan

dengan cara mengganti

n

j

jj bxa

1

dengan

(6). Berdasarkan asumsi bahwa tit ik worst

optimum x memiliki nilai fungsi objektif z ,

maka 'zz dan "zz . Namun, dikarenakan

konveksitas dari daerah (3) dan (4), d imana

(5) dan (6) merupakan versi persamaan

ekstrim dari (3) dan (4), maka

][ ",' maks zzz . Hal ini menimbulkan

kontradiksi. Jadi pengandaian bahwa titik

16

worst optimum terjadi ketika sembarang versi

khusus kendala persamaan

n

j

jj bxa

1

dimasukkan pada PL t idak terbukt i. Oleh

karena itu, tit ik worst optimum ditemukan

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 algoritmanya

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

umum, jika ada k kendala persamaan interval,

maka ada k2 PL yang harus dipecahkan untuk

menemukan solusi worst optimum.

Contoh 12:

Selesaikan LPIC dengan kendala berkoefisien

interval berikut :

Min 21 xxZ

terhadap:

0,

3:

]2,1[:

]3,1[]2,1[:

]4,3[]3,2[:

21

24

213

212

211

xx

xC

xxC

xxC

xxC

Dengan menggunakan Teorema 3, maka

masing-masing kendala persamaan interval

1C dan 2C diubah menjadi sepasang kendala

pertidaksamaan interval, yaitu:

3:

12:

42:

33:

212

212

211

211

xxC

xxC

xxC

xxC

b

a

b

a

Berdasarkan langkah 1 Algoritma 1, kendala

pertidaksamaan interval 3C diubah menjadi:

1: 213 xxC a

Jadi model best optimum pada LPIC d iatas

adalah:

Min 21 xxZ

terhadap:

0,

3:

1:

3:

12:

42:

33:

21

24

213

212

212

211

211

xx

xC

xxC

xxC

xxC

xxC

xxC

a

b

a

b

a



optimum 0,1 21 xx dan Z = 1.

Gambar 18. Daerah fisibel solusi best


Dengan menggunakan Algoritma 2, maka

akan didapatkan bentuk umum dari best

optimum persamaan interval tersebut, yaitu:

Maks 212211 bbaa

terhadap:

222

111

222222

111111

2222211

1122111

0

0

bbb

bbb

aaa

aaa

baxax

baxax

Keterangan:

11a = koefisien interval dari variabel 1x

pada kendala 1C

12a = koefisien dari variabel 2x pada

kendala 1C

21a = koefisien dari variabel 1x pada

kendala 2C

22a = koefisien interval dari variabel 2x

pada kendala 2C

1b = RHS berbentuk interval pada kendala

1C

17

2b = RHS berbentuk interval pada kendala

2C

11a = batas bawah koefisien interval 11a

11a = batas atas koefisien interval 11a

22a = batas bawah koefisien interval 22a

22a = batas atas koefisien interval 22a

1b = batas bawah RHS 1b

1b = batas atas RHS 1b

2b = batas bawah RHS 2b

2b = batas atas RHS 2b

Diketahui 2112 , aa adalah nilai tentu,

yaitu 1 ,1 2112 aa dan solusi optimum

0,1 21 xx . Nilai-nilai tersebut dimasukkan

pada bentuk umum di atas:

Maks 212211 bbaa

terhadap:

31

43

21

32

0.01.1

0)1.(0.1

2

1

22

11

222

111

b

b

a

a

ba

ba

Dengan menggunakan softwere LINGO 8.0,

solusinya adalah 1 ,3 ,2 ,3 212211 bbaa

sehingga susunan best optimum pada 1C

adalah 33: 211 xxC a dan susunan

best optimum pada 2C adalah

12: 212 xxC a .

Berdasarkan Teorema 4, untuk mempero leh

worst optimum maka 2 kendala persamaan

interval menghasilkan 22 model.

Pada kendala 1C , solusi worst optimum terjadi

pada 33: 211 xxC a atau 42: 211 xxC b .

Pada kendala 2C , solusi worst optimum terjad i

pada 12: 212 xxC a atau 3: 212 xxC b .

Kendala 1C dikombinasikan dengan

2C

sehingga menghasilkan 4 model worst

optimum.

Untuk kendala pertidaksamaan interval 3C ,

berdasarkan langkah 2 Algoritma 1 diubah

menjadi:

2: 213 xxC b

Jadi 4 model worst optimum adalah sebagai

berikut:

Model 1:

Min 21 xxZ

terhadap:

0,

3:

2:

12:

33:

21

24

213

212

211

xx

xC

xxC

xxC

xxC

b

a

a


solusi PL d i atas adalah infeasible.

Model 2:

Min 21 xxZ

terhadap:

0,

3:

2:

3:

33:

21

24

213

212

211

xx

xC

xxC

xxC

xxC

b

b

a


solusi PL di atas adalah 3,0 21 xx dan

Z = 3.

Model 3:

Min 21 xxZ

terhadap:

0,

3:

2:

12:

42:

21

24

213

212

211

xx

xC

xxC

xxC

xxC

b

a

b



Model 4:

Min 21 xxZ

terhadap:

0,

3:

2:

3:

42:

21

24

213

212

211

xx

xC

xxC

xxC

xxC

b

b

b



Jadi model yang menghasilkan worst optimum

adalah model 2 dengan 3,0 21 xx dan Z = 3.

18

Gambar 19. Daerah fisibel solusi worst


Daerah fisibel untuk masalah LPIC di atas

diperlihatkan pada gambar berikut:

Gambar 20. Daerah fisibel LPIC pada

Contoh 12.

Berikut ini adalah algoritma untuk

menyelesaikan LPIC d imana kendala berupa

persamaan dan pertidaksamaan interval.

Algoritma ini merupakan gabungan dari

algoritma dan teorema sebelumnya.

Algoritma 3 : Algori tma lengkap untuk

menyelesaikan LPIC

Diberikan k kendala persamaan interval.

1. Cari best optimum sebagaimana berikut:

1.1 Ubah k kendala persamaan interval

menjadi 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 Algoritma 1.


pada kendala persamaan interval

diberikan melalu i Algoritma 2.

2. Cari worst optimum sebagaimana berikut:

2.1 Untuk setiap model diantara k2

model yang diperoleh melalui

Teorema 4:

2.1.1 Ubah kendala persamaan

interval menjadi persamaan

tentu berdasarkan Teorema 4.

2.1.2 Selesaikan dengan membangun

model terburuk melalu i langkah

2 Algoritma 1, cari Z dan x.

2.2 Untuk mempero leh solusi:

2.2.1 Cari model yang menyediakan Z

terburuk.


pada model diperoleh dari model

terburuk pada langkah 2.2.1.

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

menjadi lima komponen, yaitu karbohidrat,

lemak, protein kalsium dan fosfor.

Berikut model umum LPIC yang

berfungsi meminimumkan biaya pembelian

pakan ternak:

Min 6

1,

jjjj xccZ

terhadap 6

1,,

jiijijij bbxaa .

19

Keterangan:

jc = biaya pada jenis pakan ternak ke -j

(Rp/ kg).

ija = kandungan zat gizi pada jenis pakan

ternak ke-j pada kendala ke-i (kg).

ib = batasan zat gizi ke-i yang diperlukan

dalam ransum (kg).

jx = banyaknya jenis pakan ternak ke-j yang

dibutuhkan dalam ransum (kg).

Misalkan peternak memiliki 100 ayam.

Tiap ayam mengkonsumsi ransum sebesar 3-

3.5 kg/minggu. Untuk memperoleh bobot

ayam yang seimbang diperlukan ransum yang

memiliki batasan-batasan sebagaimana

ditunjukkan pada Tabel 1 dan Tabel 2.

Tabel 1. Susunan Zat Gizi pada Pakan Ayam dan Kadar Min imum Zat Gizi

j Jenis Pakan Ayam ke-j

Susunan zat pakan ayam/ ija (per kg)

Karbohidrat

( ja1 )

Lemak

( ja2 )

Protein

( ja3 )

Kalsium

( ja4 )

Fosfor

( ja5 )

1 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%

Kadar Min imum Zat Gizi 43-48% 3-5% 15-18% 3-3.5% 0.55%

Sumber: Suprijatna et al. (2005)

Tabel 2. Batasan Pakan dalam Ransum dan Harga Pakan Ayam

j Jenis Pakan Ayam

ke-j

Batasan Pakan

Minimum per kg (%)

Batasan Pakan dalam

3-3.5 kg (kg)

Harga/ jc

(Rp/kg)

1 Jagung 20% 0.6-0.7 3000

2 Tepung ikan 5% 0.15-0.175 2800-4400

3 Kacang hijau 7.50% 0.225-0.2625 7000

4 Bungkil kedelai 20% 0.6-0.7 5000-6000

5 Bekatul 15% 0.45-0.525 1400-2200

6 Dedak padi 5% 0.15-0.175 1300-1600

Sumber: Nawawi dan Nurrohmah (1996)

Berikut model optimisasi LPIC pada masalah minimisasi biaya pakan ternak diatas:

Min 654321 ]1600,1300[]2200,1400[]6000,5000[7000]4400,2800[3000 xxxxxxZ

Terhadap:

100]5.3,3[654321 xxxxxx

100]48.0,43.0[29.0]55.0,51.0[3.0]57.0,55.0[]65.0,62.0[]74.0,69.0[ 654321 xxxxxx

100]05.0,03.0[]082.0,049.0[029.004.0]013.0,011.0[]1.0,078.0[]041.0,037.0[ 654321 xxxxxx

100]18.0,15.0[]12,0,068.0[]12.0,11.0[]5.0,41.0[]25.0,2.0[]62.0,55.0[]11.0,085.0[ 654321 xxxxxx

100]035.0,03.0[]002.0,001.0[0005.0]003.0,002.0[002.0]05.0,038.0[0002.0 654321 xxxxxx

1000055.0]017.0,01.0[0127.0]0068.0,006.0[017.0]038.0,028.0[]003.0,0025.0[ 654321 xxxxxx

100]175.0,15.0[,100]525.0,45.0[

100]7.0,6.0[,100]2625.0,225.0[,100]175.0,15.0[,100]7.0,6.0[

65

4321

xx

xxxx

20

Penyederhanaan dari bentuk LPIC diatas, yaitu:

Min 654321 ]1600,1300[]2200,1400[]6000,5000[7000]4400,2800[3000 xxxxxxZ

Terhadap:

]350,300[: 6543211 xxxxxxC

]48,43[29.0]55.0,51.0[3.0]57.0,55.0[]65.0,62.0[]74.0,69.0[: 6543212 xxxxxxC

]5,3[]082.0,049.0[029.004.0]013.0,011.0[]1.0,078.0[]041.0,037.0[: 6543213 xxxxxxC

]18,15[]12,0,068.0[]12.0,11.0[]5.0,41.0[]25.0,2.0[]62.0,55.0[]11.0,085.0[: 6543214 xxxxxxC

]5.3,3[]002.0,001.0[0005.0]003.0,002.0[002.0]05.0,038.0[0002.0: 6543215 xxxxxxC

55.0]017.0,01.0[0127.0]0068.0,006.0[017.0]038.0,028.0[]003.0,0025.0[: 6543216 xxxxxxC

]5.17,15[:],5.52,45[:

]70,60[:],25.26,5.22[:],5.17,15[:],70,60[:

612511

410392817

xCxC

xCxCxCxC

Untuk menyelesaikan bentuk LPIC d i atas digunakan Algoritma 3.

Langkah 1.1

1C diubah menjadi dua kendala pertidaksamaan berdasarkan Teorema 3, yaitu:

300: 6543211 xxxxxxC a

350: 6543211 xxxxxxC b

Langkah 1.2

Model LPIC diubah menjadi model PL yang memiliki solusi best optimum melalu i langkah 1

Algoritma 1.

Min 654321 130014005000700028003000 xxxxxxZ

Terhadap:

300: 6543211 xxxxxxC a

350: 6543211 xxxxxxC b

4329.055.03.057.065.074.0: 6543212 xxxxxxC

3082.0029.004.0013.01.0041.0: 6543213 xxxxxxC

1512,012.05.025.062.011.0: 6543214 xxxxxxC

3002.00005.0003.0002.005.00002.0: 6543215 xxxxxxC

55.0017.00127.00068.0017.0038.0003.0: 6543216 xxxxxxC

15:,45:

60:,5.22:,15:,60:

612511

410392817

xCxC

xCxCxCxC

Langkah 1.3

1.3.1 Model pada langkah 1.2 diselesaikan dengan menggunakan LINGO 8.0. Nilai best optimum

berada pada 601x , 4.522x , 5.223x , 604x , 455x , 1.606x dan 925359.4Z .

1.3.2 Bentuk best optimum pada kendala pertidaksamaan interval 2C ,

3C ,54 ,CC ,

11109876 ,,,,, CCCCCC dan 12C diberikan pada langkah 1.2, yaitu:

4329.055.03.057.065.074.0: 6543212 xxxxxxC

3082.0029.004.0013.01.0041.0: 6543213 xxxxxxC

1512,012.05.025.062.011.0: 6543214 xxxxxxC

3002.00005.0003.0002.005.00002.0: 6543215 xxxxxxC

55.0017.00127.00068.0017.0038.0003.0: 6543216 xxxxxxC

15:,45:

60:,5.22:,15:,60:

612511

410392817

xCxC

xCxCxCxC

1.3.3 Bentuk best optimum pada kendala persamaan interval 1C diberikan melalu i Algoritma 2.

Maksimumkan b

terhadap:

21

0665544332211 baxaxaxaxaxax

bbb 1

Dari model diketahui bahwa kendala persamaan ]350,300[: 6543211 xxxxxxC

memiliki koefisien 1654321 aaaaaa . Sedangkan dari perhitungan langkah

1 Algoritma 1 dipero leh 601x , 4.522x , 5.223x , 604x , 455x , 1.606x . Nilai-

nilai tersebut dimasukkan pada PL diatas.

Maksimumkan b

terhadap:

0)11.60()145()160()15.22()14.52()160( b

350300 b

Dengan menggunakan softwere LINGO 8.0, solusi LP d iatas adalah 300b .

Jadi versi khusus kendala persamaan interval yang memiliki solusi best optimum adalah

300654321 xxxxxx .

Langkah 2.1

2.1.1 Berdasarkan Teorema 4, tit ik worst optimum dari kendala persamaan interval

]350,300[: 6543211 xxxxxxC akan terjadi pada salah satu dari dua kendala

spesifik berikut:

300: 6543211 xxxxxxC a

350: 6543211 xxxxxxC b

Kendala 1C diubah menjadi dua versi kendala yaitu

aC1dan

bC1 yang akan menghasilkan

dua model PL baru. Model LPIC yang dimasukkan kendala aC1

dinamakan Model A dan

model LPIC yang dimasukkan kendala bC1

dinamakan Model B.

Berikut bentuk LPIC yang diperbaharui :

Model A:

Min 654321 ]1600,1300[]2200,1400[]6000,5000[7000]4400,2800[3000 xxxxxxZ

Terhadap:

300: 6543211 xxxxxxC

]48,43[29.0]55.0,51.0[3.0]57.0,55.0[]65.0,62.0[]74.0,69.0[: 6543212 xxxxxxC

]5,3[]082.0,049.0[029.004.0]013.0,011.0[]1.0,078.0[]041.0,037.0[: 6543213 xxxxxxC

]18,15[]12,0,068.0[]12.0,11.0[]5.0,41.0[]25.0,2.0[]62.0,55.0[]11.0,085.0[: 6543214 xxxxxxC

]5.3,3[]002.0,001.0[0005.0]003.0,002.0[002.0]05.0,038.0[0002.0: 6543215 xxxxxxC

55.0]017.0,01.0[0127.0]0068.0,006.0[017.0]038.0,028.0[]003.0,0025.0[: 6543216 xxxxxxC

]5.17,15[:],5.52,45[:

]70,60[:],25.26,5.22[:],5.17,15[:],70,60[:

612511

410392817

xCxC

xCxCxCxC

Model B

Min 654321 ]1600,1300[]2200,1400[]6000,5000[7000]4400,2800[3000 xxxxxxZ

Terhadap:

350: 6543211 xxxxxxC

]48,43[29.0]55.0,51.0[3.0]57.0,55.0[]65.0,62.0[]74.0,69.0[: 6543212 xxxxxxC

]5,3[]082.0,049.0[029.004.0]013.0,011.0[]1.0,078.0[]041.0,037.0[: 6543213 xxxxxxC

]18,15[]12,0,068.0[]12.0,11.0[]5.0,41.0[]25.0,2.0[]62.0,55.0[]11.0,085.0[: 6543214 xxxxxxC

]5.3,3[]002.0,001.0[0005.0]003.0,002.0[002.0]05.0,038.0[0002.0: 6543215 xxxxxxC

22

55.0]017.0,01.0[0127.0]0068.0,006.0[017.0]038.0,028.0[]003.0,0025.0[: 6543216 xxxxxxC

]5.17,15[:],5.52,45[:

]70,60[:],25.26,5.22[:],5.17,15[:],70,60[:

612511

410392817

xCxC

xCxCxCxC

2.1.2 Model A dan model B dipecahkan menggunakan langkah 2 A lgoritma 1.

Model A:

Min 654321 160022006000700044003000 xxxxxxZ

Terhadap:

300: 6543211 xxxxxxC

4829.055.03.057.065.069.0: 6543212 xxxxxxC

5049.0029.004.0011.0078.0037.0: 6543213 xxxxxxC

18068.011.041.02.055.0085.0: 6543214 xxxxxxC

5.3001.00005.0002.0002.0038.00002.0: 6543215 xxxxxxC

55.001.00127.0006.0017.0028.00025.0: 6543216 xxxxxxC

5.17:,5.52:

70:,25.26:,5.17:,70:

612511

410392817

xCxC

xCxCxCxC

Dengan menggunakan softwere LINGO 8.0, solusi PL d iatas adalah infeasible.

Model B:

Min 654321 160022006000700044003000 xxxxxxZ

Terhadap:

350: 6543211 xxxxxxC

4829.055.03.057.065.069.0: 6543212 xxxxxxC

5049.0029.004.0011.0078.0037.0: 6543213 xxxxxxC

18068.011.041.02.055.0085.0: 6543214 xxxxxxC

5.3001.00005.0002.0002.0038.00002.0: 6543215 xxxxxxC

55.001.00127.0006.0017.0028.00025.0: 6543216 xxxxxxC

5.17:,5.52:

70:,25.26:,5.17:,70:

612511

410392817

xCxC

xCxCxCxC

Dengan menggunakan softwere LINGO 8.0, solusi PL diatas adalah

,3.26,8.84,70 321 xxx 704x , 5.525x , 5.466x dan 1376569Z .

Langkah 2.2

2.2.1 Model A memiliki solusi infeasible dan Model B memiliki solusi sebesar 1376569Z .

Jadi model yang memberikan solusi worst optimum adalah Model B.

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

j Jenis Pakan Ayam

ke-j

Pembelian Pakan Ternak/minggu (kg)

Best optimum (A) Worst optimum (B)

1 Jagung 60 70

2 Tepung ikan 52.4 84.8

3 Kacang hijau 22.5 26.3

4 Bungkil kedelai 60 70

5 Bekatul 45 52.5

6 Dedak padi 60.1 46.5

Biaya yang dibutuhkan

/minggu (Rp) Rp.925.359,00 Rp1.376.569,00

Peternak akan membutuhkan biaya minimum dalam pembelian pakan ternak jika peternak

memilih kombinasi A dengan biaya sebesar Rp.925.359,00. Sedangkan jika peternak memilih

kombinasi B maka d iperlukan biaya maksimum, yaitu Rp1.376.569,00

V SIMPULAN DAN SARAN

5.1 Simpulan 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 Algoritma 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). Algoritma 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 lgoritma 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 dilakukan 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):209-

216.

Fraleigh JB. 1969. Probability and Calculus.

Philippines: Addison-Wesley.

Jeffrey A. 2005. Essential of Engineering

Mathematics. Ed ke-2. New York:

Chapman&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: McGraw-

Hill.

Nawawi NT, Nurrohmah 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, Atmomarsono U, Kartasudjana

R. 2008. Ilmu Dasar Ternak Unggas. Jakarta:

Penebar Swadaya.

Winston WL. 1995. Introduction to

Mathematical Programming. Ed ke-2.

New York: Duxbury.

LAMPIRAN

26

Lampiran 1

Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah LPIC dengan Kendala

berbentuk Pertidaksamaan Interval

Contoh 7

Min 21 ]4,2[]3,1[ xxZ

terhadap:

0,

4:

]7,6[]5,3[:

]1,2[:

5]4,2[:

]9,6[]6,4[]3,2[:

21

25

214

213

212

211

xx

xC

xxC

xxC

xxC

xxC

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


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 21 3,1 xxZ

Terhadap:

0,

]7,5[]2,1[:

]1,2[:

21

212

211

xx

xxC

xxC


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 21]2,1[ xxZ

Terhadap:

27

0,

]8,5[]3,1[:

1]4,2[:

21

212

211

xx

xxC

xxC


LPIC yang memiliki solusi worst optimum :

min=2*x1-x2;

-x1+2*x2>=-1;

x1+x2>=8;

x1>=0;x2>=0;

end


solusi unbounded.

Contoh 10:

Min 21 3,1 xxZ

Terhadap:

0,

]7,2[]2,1[:

]1,3[]2,1[:

21

212

211

xx

xxC

xxC


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


Cost

X1 1.000000 0.000000

X2 0.000000 0.5000000


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



min=x1+3*x2;

-x1-2*x2>=-1;

x1+x2>=7;

x1>=0;x2>=0;


solusi infeasible.

Jadi LPIC memiliki solusi antara 1z dan

infeasible.

Contoh 11:

Min 21]3,1[ xxZ

Terhadap:

0,

]7,5[]1,1[3:

14]1,2[:

21

212

211

xx

xxC

xxC



min=x1-x2;

-x1+4*x2>=-1;

3*x1+x2>=5;

x1>=0;x2>=0;

end


solusi unbounded.



min=3*x1-x2;

-2*x1+4*x2>=-1;

3*x1-x2>=7;

x1>=0;x2>=0;

end


at iteration: 2

Objective value:

7.000000

28


Cost

X1 2.700000 0.000000

X2 1.100000 0.000000


Price

1 7.000000 -1.000000

2 0.000000 0.000000

3 0.000000 -1.000000

4 2.700000 0.000000

5 1.100000 0.000000

Jadi LPIC memiliki solusi antara antara

dan 7z .

Lampiran 2 Syntax Program LINGO 8.0 untuk Menyelesaikan Masalah LPIC dengan Kendala

berbentuk Persamaan interval.

Contoh 12:

Min 21 xxZ

terhadap:

0,

3:

]2,1[:

]3,1[]2,1[:

]4,3[]3,2[:

21

24

213

212

211

xx

xC

xxC

xxC

xxC



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


at iteration: 6

Objective value:

1.000000


Cost

X1 1.000000 0.000000

X2 0.000000 0.000000


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



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


at iteration: 3

Objective value:

3.000000


Cost

X1 0.000000 0.000000

X2 3.000000 0.000000


Price

1 3.000000 -1.000000

2 0.000000 0.000000

29

3 0.000000 -1.000000

4 1.000000 0.000000

5 0.000000 0.000000

6 0.000000 0.000000

7 3.000000 0.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


adalah infeasible.

d) Model 4 min=x1+x2;

2*x1+x2=4;

x1+x2=3;

-x1+x2>=2;

x2<=3;

x1>=0;x2>=0;

end


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: 10

Objective value: 925359.4

Variable Value Reduced Cost

X1 60.00000 0.000000

X2 52.40625 0.000000

X3 22.50000 0.000000

X4 60.00000 0.000000

X5 45.00000 0.000000

X6 60.09375 0.000000

30

Row Slack or Surplus Dual Price

1 925359.4 1.000000

2 0.000000 1237.500

3 50.00000 0.000000

4 108.4663 0.000000

5 13.62581 0.000000

6 72.32812 0.000000

7 0.000000 31250.00

8 4.005031 0.000000

9 0.000000 -1756.250

10 37.40625 0.000000

11 0.000000 -5700.000

12 0.000000 -3668.750

13 0.000000 -146.8750

14 45.09375 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: 6

Objective value: 1376569.


Cost

X1 70.00000

0.000000

X2 84.75676

0.000000

X3 26.25000

0.000000

X4 70.00000

0.000000

X5 52.50000

0.000000

X6 46.49324

0.000000

Row Slack or Surplus Dual Price

1 1376569. -1.000000

2 0.000000 -1524.324

3 133.7124 0.000000

4 11.09045 0.000000

5 77.45276 0.000000

6 0.000000 -75675.68

7 3.996122 0.000000

8 0.000000 -1460.541

9 67.25676 0.000000

10 0.000000 -5324.324

11 0.000000 -4324.324

12 0.000000 -637.8378

13 28.99324 0.000000

pengoptimuman pada masalah pemrograman linear … · kata kunci: pemrograman linear, koefisien...

Documents