BAB 2 LANDASAN TEORI

BAB 2 LANDASAN TEORI

2.1 Program Linier Program linier merupakan suatu teknik perencanaan yang menggunakan model matematika dengan tujuan menemukan beberapa kombinasi alternatif dari pemecahan masalah yang kemudian dipilih mana yang terbaik untuk menyusun strategi dan langkah-langkah kebijakan tentang alokasi sumber daya yang ada agar mencapai tujuan atau sasaran yang diinginkan secara optimal dengan melibatkan variabel-variabel linier.Dalam model program linier dikenal dua macam fungsi, yaitu fungsi objektif (objective function) dan fungsi kendala (constraint function) yang linier.

Bentuk umum dari permasalahan program linier adalah: Tentukan nilai x1 , x 2 , x3 , , x n , yang memaksimumkan atau meminimumkan: 𝑓𝑓�𝑥𝑥1 , 𝑥𝑥2, ⋯ , 𝑥𝑥𝑛𝑛 � = 𝑍𝑍 = 𝑐𝑐1 𝑥𝑥1 + 𝑐𝑐2 𝑥𝑥2 + ⋯ + 𝑐𝑐𝑛𝑛 𝑥𝑥𝑛𝑛

Dengan kendala:

𝑎𝑎11 𝑥𝑥1 + 𝑎𝑎12 𝑥𝑥2 + ⋯ + 𝑎𝑎1𝑛𝑛 𝑥𝑥𝑛𝑛 (=, ≤, ≥)𝑏𝑏1

𝑎𝑎21 𝑥𝑥1 + 𝑎𝑎22 𝑥𝑥2 + ⋯ + 𝑎𝑎2𝑛𝑛 𝑥𝑥𝑛𝑛 (=, ≤, ≥)𝑏𝑏2 …

(2.1)

…

𝑎𝑎𝑚𝑚1 𝑥𝑥1 + 𝑎𝑎𝑚𝑚2 𝑥𝑥2 + ⋯ + 𝑎𝑎𝑚𝑚𝑚𝑚 𝑥𝑥𝑛𝑛 (=, ≤, ≥)𝑏𝑏𝑛𝑛 𝑥𝑥1 , 𝑥𝑥2 , … , 𝑥𝑥𝑛𝑛 ≥ 0

aij dan bi merupakan anggota bilangan real, c j anggota bilangan real positif

karena merupakan koefisien fungsi tujuan sehingga nilainya harus bilangan real positif dan x j merupakan variabel, dengani = 1,2,  ,m danj= 1,2,  , n.

Universitas Sumatera Utara

Persamaan (2.1) dapat ditulis dalam bentuk yang lebih sederhana sebagai berikut (B. Susanta, 1994: 6): Tentukan nilai x j , yang memaksimumkan atau meminimumkan: 𝑛𝑛

Dengan kendala:

𝑓𝑓�𝑥𝑥𝑗𝑗 � = 𝑍𝑍 = � 𝑐𝑐𝑗𝑗 𝑥𝑥𝑗𝑗 𝑗𝑗 =1

𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 (≤, =, ≥)𝑏𝑏𝑖𝑖 𝑗𝑗 =1

𝑥𝑥𝑗𝑗 ≥ 0;

(𝑖𝑖 = 1, 2, ⋯ , 𝑚𝑚); ( 𝑗𝑗 = 1, 2, ⋯ , 𝑛𝑛) Fungsi kendala bisa berbentuk persamaan (=) atau pertidaksamaan (≤) atau (≥). Konstanta (baik sebagai koefisien aij atau c j maupun nilai batas sumber daya (𝑏𝑏𝑖𝑖 )) dalam fungsi kendala maupun pada fungsi tujuan dikatakan sebagai parameter model program linier.

Simbol x1 , x2 , x3 ,  , xn ( x j ) menunjukkanvariabel

keputusan.Jumlah

variabel keputusan ( x j ) tergantung dari jumlah kegiatan atau aktivitas yang dilakukan untuk mencapai tujuan.

Simbol c1 , c 2 , c3 , , c n merupakan kontribusi masing-masing variabel keputusan terhadap tujuan, disebut juga koefisien fungsi tujuan pada model matematiknya. Simbol a11 , a12 , a13 , , a1n , , a mn merupakan penggunaan per unit variabel keputusan akansumber daya yang membatasi atau disebut juga sebagai koefisien fungsi kendala pada model matematiknya.

Simbol b1 , b2 , b3 ,  , bm menunjukkan jumlah masing-masing sumber daya yang ada.Jumlah fungsi kendala tergantung dari banyaknya sumber daya yang


digunakan.Pertidaksamaan (x1 , x 2 , x3 ,  , x n ) ≥ 0 menunjukkan

kendala

non-

negatif.

Program linier juga dapat direpresentasikan dalam bentuk matriks sebagai berikut (B. Susanta, 1994: 7): Tentukan nilai 𝑋𝑋,

yang memaksimumkan atau meminimumkan: 𝑓𝑓 = 𝑍𝑍 = 𝐶𝐶 𝑇𝑇 𝑋𝑋

Dengan kendala:

𝐴𝐴𝐴𝐴(≤, =, ≥)𝐵𝐵 𝑋𝑋 ≥ 0

Dimana: 𝑥𝑥1 𝑥𝑥2 𝑋𝑋 = � ⋮ �, 𝑥𝑥𝑛𝑛

𝑐𝑐1 𝑐𝑐2 𝐶𝐶 = � ⋮ �, 𝑐𝑐𝑛𝑛

𝑏𝑏1 𝑏𝑏2 𝐵𝐵 = � �, ⋮ 𝑏𝑏𝑛𝑛

𝑎𝑎11 𝑎𝑎21 𝐴𝐴 = � ⋮ 𝑎𝑎𝑚𝑚1

𝑎𝑎12 𝑎𝑎22 ⋮ 𝑎𝑎𝑚𝑚2

⋯ ⋯ ⋮ ⋯

𝑎𝑎1𝑛𝑛 𝑎𝑎21 ⋮ � 𝑎𝑎𝑚𝑚𝑚𝑚

Keterangan: 𝑍𝑍 =nilai fungsi tujuan yang dicapai 𝑋𝑋 =vektor variabel,

𝐶𝐶 = vektor biaya (koefisien fungsi tujuan)

𝐴𝐴 = �𝑎𝑎𝑖𝑖𝑖𝑖 �adalah matriks kendala berukuran 𝑚𝑚 × 𝑛𝑛 𝐵𝐵 =vektor nilai batasan sumber.

𝑇𝑇 =transpose matriks.

2.1.1 Sifat Umum Program Linier Semua persoalan program linier mempunyai empat sifat umum yaitu, sebagai berikut (B. Susanta, 1994: 13): 1. Persoalanprogram

linier

bertujuan

untuk

memaksimumkan

atau

meminimumkan pada umumnya berupa laba atau biaya sebagai hasil yang optimal.


2. Adanya kendala atau batasan (constrains) yang membatasi tingkat sampai di mana sasaran dapat dicapai. Oleh karena itu, untuk memaksimumkan atau meminimumkan suatu kuantitas fungsi tujuan bergantung kepada sumber daya yang jumlahnya terbatas. 3. Harus ada beberapa alternatif solusi layak yang dapat dipilih. 4. Tujuan dan batasan dalam permasalahan program linier harus dinyatakan dalam hubungan dengan pertidaksamaan atau persamaan linier.

2.1.2 Asumsi Dasar Program Linier Berikut asumsi-asumsi dasar program linier agar tidak terbentur pada hal-hal yang menyimpang (Asri dan Hidayat, 1984: 21): a) Proportionality Asumsi ini menyatakan bahwa nilai Z dan penggunaan sumber yang tersedia atau fasilitas yang tersedia akan berubah secara sebanding dengan perubahan tingkat aktivitas. b) Nilai tujuan tiap aktivitas tidak saling mempengaruhi

Artinya, di dalam program linier dianggap bahwa kenaikan dari nilai tujuan (Z) yang diakibatkan oleh kenaikan suatu aktivitas dapat ditambahkan tanpa mempengaruhi bagian nilai Z yang diperoleh dari aktivitas lain c) Divisibility

Asumsi ini menyatakan bahwa output yang dihasilkan oleh setiap kegiatan dapat berupa bilangan pecahan. Demikian pula dengan nilai Z yang dihasilkan. d) Deterministic

Asumsi ini menyatakan bahwa semua parameter yang terdapat dalam model program linier dapat diperkirakan dengan pasti meskipun jarang tepat. e) Accountability For Resources

Sumber-sumber yang tersedia harus dapat dihitung, sehingga dapat dipastikan berapa bagian yang terpakai dan sisa. f) Linearity Of Objective Fungsi tujuan dan faktor-faktor pembatasnya harus dinyatakan sebagai fungsi linier.


2.2 Metode Simpleks Salah satu metode untuk menyelesaikan masalah program linier adalah dengan menggunakan metode simpleks yang ditemukan oleh George Dantzig pada tahun

1947 dan telah dikembangkan oleh beberapa ahli lain.Penentuan solusi optimal menggunakan metode simpleks didasarkan pada teknik eleminasi Gauss Jordan.Metode simpleks merupakan prosedur aljabar yang bersifat iteratif yang bergerak selangkah demi selangkah dimulai dari titik ekstrem pada daerah layak menuju ke titik ekstrem yang optimum untuk mencari nilai optimal dari fungsi tujuan dalam masalah optimasi yang terkendala (Hillier dan Lieberman, 1995: 57).

Syarat-syarat yang harus dipenuhi dalam menggunakan metode simpleks untuk menyelesaikan masalah program linier adalah (Muhiddin Sirat, 2007: 3): a) Semua kendala pertidaksamaan harus diubah menjadi bentuk persamaan. b) Sisi kanan dari tanda pertidaksamaan kendala tidak boleh ada yang negatif. c) Semua variabel dibatasi pada nilai non-negatif. Untuk memecahkan masalah program linier dengan menggunakan metode simpleks, masalah program linier harus diubah terlebih dahulu dalam bentuk kanonik.

Bentuk kanonik dari masalah program linier adalah sebagai berikut: Tentukan nilai x j , yang memaksimumkan atau meminimumkan 𝑛𝑛

Dengankendala:

𝑓𝑓�𝑥𝑥𝑗𝑗 � = 𝑍𝑍 = � 𝑐𝑐𝑗𝑗 𝑥𝑥𝑗𝑗 𝑗𝑗 =1

(2.2)

𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 = 𝑏𝑏𝑖𝑖 𝑗𝑗 =1

𝑥𝑥𝑗𝑗 ≥ 0;

(𝑖𝑖 = 1, 2, ⋯ , 𝑚𝑚); (𝑗𝑗 = 1, 2, ⋯ , 𝑛𝑛)


Bentuk kanonik dari masalah program linier seperti persamaan (2.2) dapat diperoleh dengan menambahkan variabel pengetat, yaitu variabel slack dan variabel surplus. a) Variabel Slack Variabel slack adalah variabel yang digunakan untuk mengubah pertidaksamaan dengan tanda ≤’menjadi ‘ persamaan ‘=’. Misalnya kendala masalah program linier berbentuk: 𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 ≤ 𝑏𝑏𝑖𝑖 𝑗𝑗 =1

maka pada ruas kiri disisipkan 𝑦𝑦𝑖𝑖 sehingga kendala menjadi: 𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 + 𝑦𝑦𝑖𝑖 = 𝑏𝑏𝑖𝑖 𝑗𝑗 =1

(2.3)

Variabel y i disebut variabel slack,dengan y i ≥ 0. Besarnya koefisien kontribusi c sama dengan nol.

b) Variabel Surplus Variabel surplus adalah variabel yang digunakan untuk mengubah pertidaksamaan dengan tanda ≥’ ‘ menjadi persamaan ‘=’. Misalnya kendala masalah program linier berbentuk: 𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 ≥ 𝑏𝑏𝑖𝑖 𝑗𝑗 =1

maka pada ruas kiri disisipkan si sehingga kendala menjadi: 𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 − 𝑠𝑠𝑖𝑖 = 𝑏𝑏𝑖𝑖 𝑗𝑗 =1

(2.4)

Variabel si disebut variabel surplus,dengan si ≥ 0.Besarnya koefisien kontribusi 𝑐𝑐 sama dengan nol.


c) Variabel Semu (Artifisial) Variabel semu adalah variabel yang ditambahkan jika dalam persamaan tidak ada variabel yang dapat menjadi basis.Pada persamaan (2.4) tersebut tidak ada variabel dengan koefisien +1 artinya tidak ada variabel yang dapat menjadi basis dalam tabel awal simpleks sehingga perlu ditambahkan qi ≥ 0 pada ruas kiri sehingga persamaan kendala menjadi: 𝑛𝑛

� 𝑎𝑎𝑖𝑖𝑖𝑖 𝑥𝑥𝑗𝑗 − 𝑠𝑠𝑖𝑖 + 𝑞𝑞𝑖𝑖 = 𝑏𝑏𝑖𝑖 𝑗𝑗 =1

Variabel

qi disebut

variabel

(2.5)

semu,dengan si , qi ≥ 0.Besarnya

koefisien

kontribusi𝑐𝑐sama dengan –Muntuk pola memaksimumkan dan Muntuk pola meminimumkan, dengan Madalah bilangan positif sangat besar.

2.2.1 Tabel Simpleks Tabel simpleks menggambarkan persoalan program linier dalam bentuk koefisiennya saja, baik koefisien tujuan maupun koefisien fungsi kendala. Bentuk umum dari tabel simpleks adalah sebagai berikut (Zulian Yamit, 1991: 43): Tabel 2.1 Bentuk Umum Tabel Simpleks Awal 𝑐𝑐𝑗𝑗 cj

𝑐𝑐1

xi

𝑥𝑥𝑗𝑗

𝑥𝑥1

𝑐𝑐1

𝑥𝑥1

𝑎𝑎11

𝑐𝑐2

⋯

𝑎𝑎12

⋯

𝑥𝑥2

𝑐𝑐2

𝑥𝑥2

𝑎𝑎21

𝑎𝑎22

𝑐𝑐𝑚𝑚

𝑥𝑥𝑚𝑚

𝑎𝑎𝑚𝑚1

𝑎𝑎𝑚𝑚2

𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗

𝑍𝑍1 − 𝑐𝑐1

𝑍𝑍2 − 𝑐𝑐2

⋮

⋮

𝑍𝑍𝑗𝑗

⋮

𝑍𝑍1

⋮

𝑍𝑍2

⋯

𝑐𝑐𝑛𝑛

𝑥𝑥𝑛𝑛

𝑎𝑎1𝑛𝑛

𝑏𝑏𝑖𝑖

𝑅𝑅𝑖𝑖

𝑏𝑏1

𝑅𝑅1

⋯

𝑎𝑎2𝑛𝑛

𝑏𝑏2

𝑅𝑅2

⋯

𝑎𝑎𝑚𝑚𝑚𝑚

𝑏𝑏𝑚𝑚

𝑅𝑅𝑚𝑚

⋯

𝑍𝑍𝑛𝑛 − 𝑐𝑐𝑛𝑛

𝑍𝑍

⋯ ⋯

⋮

𝑍𝑍𝑛𝑛

⋮

𝑍𝑍

⋮


Keterangan: 𝑥𝑥𝑗𝑗

: variabel lengkap

𝑏𝑏𝑖𝑖

: nilai ruas kanan (sumber daya)

𝑎𝑎𝑖𝑖𝑖𝑖

: koefisien teknis

𝑐𝑐𝑗𝑗 :koefisien

kontribusirelatif dari fungsi tujuan, untuk variabel slack1dan

surplusbernilai nol sedangkan untuk variabel semu bernilai – 𝑀𝑀 untuk pola memaksimumkan dan 𝑀𝑀 untuk pola meminimumkan.

: variabel yang menjadi variabel basis.

xi

:koefisien

cj

kontribusi

relatif

untuk

variabel

dalambasis x i

padaawalnya1koefisien ini bernilai nol. : hasil kali c j dengan kolom 𝑎𝑎𝑖𝑖𝑖𝑖 ( ∑𝑛𝑛𝑗𝑗=1 𝑐𝑐𝑖𝑖 𝑎𝑎𝑖𝑖𝑖𝑖 )

𝑍𝑍𝑗𝑗

𝑏𝑏

:diperolehdenganrumus𝑅𝑅𝑖𝑖 = 𝑎𝑎 𝑖𝑖 , yang digunakan untukmenentukan

𝑅𝑅𝑖𝑖

𝑖𝑖𝑖𝑖

baris kunci, yaitu dipilih dengan nilai 𝑅𝑅𝑖𝑖 terkecil dengan 𝑎𝑎𝑖𝑖𝑖𝑖 > 0.

: hasil kali kolom c j dan kolom 𝑏𝑏𝑖𝑖 (∑𝑛𝑛𝑗𝑗=1 𝑐𝑐𝑖𝑖 𝑎𝑎𝑖𝑖𝑖𝑖 ).Pada tabel simpleks yang

𝑍𝑍

telah optimal nilai ini merupakan nilai program atau nilai tujuan.

𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 : nilai ini akan memberikan informasi apakah fungsi tujuan telah

optimal atau belum, Jika kita menghadapi persoalan memaksimumkan,

maka tabel telah optimal jika nilai pada baris𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 ≥ 0. 2.2.2

Langkah-Langkah Metode Simpleks

Langkah-langkah metode simpleks secara umum adalah sebagai berikut (Mustafa dan Parkhan, 2000: 57): 1) Merubah fungsi tujuan dan fungsi kendala kebentuk kanonik. 2) Mentabulasikan persamaan-persamaan yang diperoleh langkah satu. 3) Menentukan entering variabel:

Untuk tujuan memaksimumkan jika: a) (𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) < 0; maka hasil belum optimal, lanjutkan iterasi.

b) (𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) ≥ 0; maka hasil sudah optimal, iterasi dihentikan.

c) Entering variabel adalah (𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) dengan nilai negatif terbesar.

Untuk tujuan meminimumkan jika sebaliknya.


4) Menentukan leaving variabel. Baris yang memiliki nilai rasio positif terkecil, dengan rumus sebagai berikut:

𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟𝑟 = 𝑅𝑅𝑖𝑖 =

𝑏𝑏𝑖𝑖 (2.6) 𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 (𝑎𝑎𝑖𝑖𝑖𝑖 )

5) Menentukan persamaan pivot baru Tentukan dahulu elemen pivot yaitu angka pada perpotongan entering variabel dan leaving variabel.

𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 = 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 ×

1 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝

(2.7)

6) Menentukan persamaan-persamaan baru selain persamaan pivot 𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃𝑃 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏 = 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑙𝑙𝑙𝑙𝑙𝑙𝑙𝑙 – (𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘 𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘𝑘 𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒𝑒 × 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝𝑝 𝑏𝑏𝑏𝑏𝑏𝑏𝑏𝑏)

(2.8)

7) Lanjutkan perbaikan-perbaikan, periksa nilai(𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 ): untuk tujuan memaksimumkan jika:

a) (𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) < 0; maka hasil belum optimal, lanjutkan iterasi.

b) (𝑍𝑍𝑗𝑗 − 𝑐𝑐𝑗𝑗 ) ≥ 0; maka hasil sudah optimal, iterasi dihentikan.

untuk tujuan meminimumkan, maka sebaliknya.

2.3 Analisis Sensitivitas Perubahan Kapasitas Sumber Daya (𝒃𝒃𝒊𝒊 )

Setelah ditemukan penyelesaian optimal dari suatu masalah program linier, perlu untuk menganalisa lebih jauh kemungkinan-kemungkinan yang terjadi sebagai akibat perubahan-perubahan koefisien-koefisien didalam model pada saat tabel optimal

telah

diperoleh

sebagai

landasan

perbaikan

untuk

produksi

berikutnya.Analisis sensitivitas dilakukan untuk mengetahui akibat atau pengaruh


dari perubahan yang terjadi terhadap penyelesaian optimal yang telah diperoleh (Faigiziduhu Bu’lolo, 2005: 78).

Analisis sensitivitas akan menjelaskan interval atau batas perubahan dari parameter agar tidak merubah penyelesaian optimal (Siswanto, 2000: 162). Tujuan utama dari analisis sensitivitas selain digunakan untuk pengecekan adalah untuk mengurangi perhitungan-perhitungan dan menghindari penghitungan ulang bila terjadi perubahan koefisien-koefisien pada model program linier setelah dicapai tahap optimal dan juga untuk mengetahui tingkat kesensitifan dari masingmasing parameter sebagai landasan untuk melakukan perubahan-perubahan terhadap parameter-parameter yang ada pada produksi berikutnya.

Analisis sensitivitas dapat dikelompokkan menjadi limaberdasarkan perubahan-perubahan parameter yang terjadi, yaitu: 1. Perubahan koefisien fungsi tujuan (𝑐𝑐𝑗𝑗 )

2. Perubahan koefisien teknologi (𝑎𝑎𝑖𝑖𝑖𝑖 ) atau koefisien teknis, 3. Perubahan kapasitas sumber daya ( 𝑏𝑏𝑖𝑖 )

4. Adanya tambahan fungsi kendala baru, 5. Adanya tambahan

variabel

penambahan kegiatan baru.

pengambilan

keputusan

(𝑥𝑥𝑗𝑗 )atau

adanya

Perubahan yang dimaksud dalam penelitian ini adalah perubahankapasitas sumber daya(𝑏𝑏𝑖𝑖 ). Salah satu aspek pertimbangan dalam penentuan jumlah produksi adalah ketersediaan sumber daya (𝑏𝑏𝑖𝑖 ).Apabila terjadi perubahan (𝑏𝑏𝑖𝑖 ) mengakibatkan semua variabel basis bernilai nonnegatif, maka penyelesaian optimal sebelumnya masih tetap.Namun, apabila ada salah satu variabel basis tersebut bernilai negatif, maka penyelesaian optimal sebelumnya dinyatakan tidak layak (Parlin Sitorus, 1997: 101).


Pengaruh perubahan konstanta ruas kanan terhadap tabel optimal dapat ditentukan dengan menyelidiki perubahan konstanta ruas kanan yang baru pada tabel optimal. Dirumuskan sebagai berikut (Mustafa dan Parkhan, 2000: 91):

bî = B −1bi (2.9) Dengan: 𝐵𝐵ˉ¹ = matriks dibawah variabel basis awal pada tabel optimal bî = menunjukkan nilai baru atau nilai pada tabel optimal

Tabel optimal tetap optimal dan layak jika bî ≥ 0 2.4 Software POM-QM Program POM-QM adalah paket program komputer untuk menyelesaikan persoalan-persoalan metode kuantitatif, manajemen sains atau riset operasi. Program POM-QM juga adalah salah satu software yang dapat digunakan untuk membantu perhitungan masalah program linier.

Gambar 2.1 TampilanCover dari SoftwarePOM-QM

2.5 Teori Himpunan Crisp dan Himpunan Fuzzy Himpunan crispdikenal juga dengan himpunan tegas. Pada himpunan crisp nilai keanggotaan suatu nilai x dalam suatu himpunan Ayang sering ditulis dengan

µ A [x ] , hanya memiliki dua kemungkinan: 1) µ A [x ] = 1, yang berarti bahwa x merupakan anggota dari himpunan A 2) µ A [x ] = 0, yang berarti bahwa x bukan merupakan anggota dari himpunan A


Secara grafis nilai keanggotaan dari himpunan crisp digambarkan sebagai berikut:

Gambar 2.2 Derajat Keanggotaan dari HimpunanCrisp Pada gambar (2.2) dapat diketahui bahwa: 1. Apabila seseorang berusia 34 tahun, maka ia dikatakan MUDA.

µ MUDA [34] = 1. 2. Apabila seseorang berusia 35 tahun, maka ia dikatakan tidak MUDA.

µ MUDA [35] = 0. 3. Apabila seseorang berusia 35 tahun kurang 1 hari, maka iadikatakan tidak PAROBAYA,

µ PAROBAYA [35tahun − 1hari ] =0.

Himpunan fuzzy didasarkan pada gagasan untuk memperluas jangkauan fungsi karakteristik sedemikian hingga fungsi tersebut akan mencakup bilangan real pada interval [0,1]. Nilai keanggotaannya menunjukkan bahwa suatu item dalam semesta pembicaraan tidak hanya berada pada nol atau satu, namun juga nilai yang terletak diantaranya.Secara grafis nilai keanggotaan dari himpunan crisp digambarkan sebagai berikut:

Gambar 2.3 Derajat Keanggotaan dari Himpunan Fuzzy


Pada gambar (2.3) dapat diketahui bahwa: 1. Seseorang yang berumur 40 tahun, termasuk dalam himpunan MUDA dengan

µ MUDA [40] = 0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan µ PAROBAYA [40] = 0,5. 2. Seseorang yang berumur 50 tahun, termasuk dalam himpunan TUA dengan

µ TUA [40] = 0,25; namun dia juga termasuk dalam himpunan PAROBAYA dengan µ PAROBAYA [40] = 0,5.

2.5.1 Domain Himpunan Fuzzy Domain himpunan fuzzy adalah keseluruhan nilai yang diijinkan dalam semesta pembicaraan, dengan kata lain domain biasanya memiliki batas atas dan batas bawah. Domain merupakan himpunan bilangan real yang senantiasa naik (bertambah) secara monoton dari kiri kekanan.Nilai domain dapat berupa bilangan positif maupun negatif.Secara grafis domain himpunan fuzzy digambarkan sebagai berikut:

Gambar 2.4 Domain Himpunan Fuzzy

Dari gambar (2.4) dapat diketahui domainhimpunan fuzzyTua [45, 60]

2.5.2 Nilai Ambang Batas (Alfa-Cut) Nilai ambang (alfa-cut) merupakan nilai ambang batas domain yang didasarkan pada nilai keanggotaan untuk tiap-tiap domain. Himpunan ini berisi semua nilai domain yang merupakan bagian dari himpunan fuzzy dengan nilai keanggotaan lebih besar atau sama dengan alfa(α) ditulis sebagai berikut:


𝜇𝜇(𝑥𝑥) ≥ 𝛼𝛼

(2.10)

Gambar 2.5 Nilai Ambang Batas (Alfa-Cut)

2.5.3 Representasi Himpunan Fuzzy Fungsi keanggotaan (membership function) adalah suatu kurva yang menunjukkan pemetaan titik-titik input data ke dalam nilai keanggotaannya (sering juga disebut dengan derajat keanggotaan) yang memiliki interval antara nol sampai satu. fungsi keanggotaan himpunan fuzzy trapezoidal dengan parameter a, b, c dan ddirepresentasikan sebagai berikut:

Gambar 2.6Representasi HimpunanFuzzyTrapezoidal

Fungsi keanggotaan: 0; ⎧ 𝑥𝑥 − 𝑎𝑎 ; ⎪ 𝑏𝑏 − 𝑎𝑎 𝜇𝜇(𝑥𝑥) = ⎨ 1; ⎪ 𝑑𝑑 − 𝑥𝑥 ⎩ 𝑑𝑑 − 𝑐𝑐 ;

𝑥𝑥 ≤ 𝑎𝑎 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥 ≥ 𝑑𝑑 𝑎𝑎 < 𝑥𝑥 < 𝑏𝑏 𝑏𝑏 ≤ 𝑥𝑥 ≤ 𝑐𝑐

𝑐𝑐 < 𝑥𝑥 < 𝑑𝑑


Fungsi keanggotaan himpunan fuzzy triangular dengan parameter a, b, dan cdirepresentasikan sebagai berikut:

Gambar 2.7 Representasi Himpunan Fuzzy Triangular

Fungsi keanggotaan: 0; ⎧𝑥𝑥 − 𝑎𝑎 ⎪ ; 𝜇𝜇(𝑥𝑥) = 𝑏𝑏 − 𝑎𝑎 ⎨ 𝑐𝑐 − 𝑥𝑥 ⎪ ; ⎩ 𝑐𝑐 − 𝑏𝑏

𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝑥𝑥 ≤ 𝑎𝑎 𝑎𝑎𝑎𝑎𝑎𝑎𝑎𝑎 𝑥𝑥 ≥ 𝑐𝑐

𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝑎𝑎 < 𝑥𝑥 < 𝑏𝑏 𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝑏𝑏 < 𝑥𝑥 < 𝑐𝑐

2.6 Fuzzy Linear Programming Pada fuzzy linear programming bentuk imperatif pada fungsi objektif tidak lagi benar-benar “maksimum” atau “minimum” dan tanda ≤’ ‘ untuk kasus maksimasi dan tanda‘ ≥’ untuk kasus minimasi tidak lagi bermakna

crisp secara

matematis,namun mengalami sedikit pelanggaran makna karena adanya beberapa hal yang perlu dipertimbangkan dalam sistem yang mengakibatkan batasan tidak dapat didekati secara tegas (Kusumadewi, 2002: 220). Dalam fuzzy linear programming akan dicari suatu nilai 𝑍𝑍 yang

merupakan fungsi objektif yang akan dioptimasikan sedemikian hingga tunduk pada batasan-batasan yang dimodelkan dengan menggunakan himpunan fuzzy.


Masalah maksimasi: Tentukan x sedemikian hingga: 𝑐𝑐 𝑇𝑇 𝑥𝑥 ≿ 𝑧𝑧

(2.11)

𝐴𝐴𝐴𝐴 ≾ 𝑏𝑏 𝑥𝑥 ≥ 0

Masalah minimasi: Tentukan x sedemikian hingga: 𝑐𝑐 𝑇𝑇 𝑥𝑥 ≾ 𝑧𝑧

(2.12)

𝐴𝐴𝐴𝐴 ≿ 𝑏𝑏 𝑥𝑥 ≥ 0

Tanda ‘≿’ merupakan bentuk fuzzy dari ≥ ‘ ’ yang menginterpretasikan pada dasarnya lebih dari atau sama dengan, tanda ‘≾’ merupakan bentuk fuzzy dari ‘≤’ yang menginterpretasikan pada dasarnya kurang dari atau samadengan.Bentuk (2.11) dan (2.12) dapat disederhanakan kebentuk berikut:

Tentukan x sedemikian hingga: 𝐵𝐵𝐵𝐵 ≾ 𝑑𝑑 Kasus maksimasi:

𝑥𝑥 ≥ 0

(2.13) −𝑐𝑐 � 𝐴𝐴

𝐵𝐵 = �

Kasus minimasi:

−𝑍𝑍 𝑑𝑑 = � � 𝑏𝑏

𝑐𝑐 � −𝐴𝐴

𝐵𝐵 = � Dimana: 𝑥𝑥1 𝑥𝑥2 𝑥𝑥 = � ⋮ �, 𝑥𝑥𝑛𝑛

𝑏𝑏1 𝑏𝑏 𝑏𝑏 = � 2 �, ⋮ 𝑏𝑏𝑛𝑛

𝑍𝑍 𝑑𝑑 = � � −𝑏𝑏

𝑐𝑐1 𝑐𝑐2 𝑐𝑐 = � ⋮ �, 𝑐𝑐𝑛𝑛

𝑎𝑎11 𝑎𝑎21 𝐴𝐴 = � ⋮ 𝑎𝑎𝑚𝑚1

𝑎𝑎12 𝑎𝑎22 ⋮ 𝑎𝑎𝑚𝑚2

⋯ ⋯ ⋮ ⋯

𝑎𝑎1𝑛𝑛 𝑎𝑎21 ⋮ � 𝑎𝑎𝑚𝑚𝑚𝑚


𝑍𝑍 = nilai fungsi tujuan yang dicapai 𝑥𝑥 = vektor variabel,

𝑐𝑐 =vektor biaya (koefisien fungsi tujuan)

𝐴𝐴 = �𝑎𝑎𝑖𝑖𝑖𝑖 �adalah matriks kendala berukuran 𝑚𝑚 × 𝑛𝑛 𝑏𝑏 = vektor nilai batasan kendala (sumber daya).

Tiap-tiap baris atau batasan (0,1,2, ⋯, m) akan direpresentasikan dengan

himpunan fuzzy, dengan fungsi keanggotaan pada himpunan ke-i adalah µ i [Bi x ]. Direpresentasikan dengan kurva Trapesium sebagai berikut:

Gambar 2.8 Representasi Fungsi Keanggotaan [Bi x ] dengan Kurva Trapesium Dari gambar (2.8) diketahui µ i [Bi x ] =0 jika batasan ke-i benar-benar dilanggar, sebaliknya µ i [Bi x ] = 1 jika batasan ke-i benar-benar dipatuhi. Nilai µ i [Bi x ] akan naik secara monoton pada selang [0, 1], yaitu:

𝜇𝜇𝑖𝑖 [𝐵𝐵𝑖𝑖 𝑥𝑥] = �∈ [0,1];

Fungsi keanggotaan:

𝑖𝑖 = 1, 2, ⋯ , 𝑚𝑚

1;

0;

1; ⎧ 𝐵𝐵𝑖𝑖 𝑥𝑥 − 𝑑𝑑𝑖𝑖 𝜇𝜇𝑖𝑖 [𝐵𝐵𝑖𝑖 𝑥𝑥] = 1 − ; 𝑝𝑝𝑖𝑖 ⎨ 0; ⎩

𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝐵𝐵𝑖𝑖 𝑥𝑥 ≤ 𝑑𝑑𝑖𝑖 𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝑑𝑑𝑖𝑖 < 𝐵𝐵𝑖𝑖 𝑥𝑥 < 𝑑𝑑𝑖𝑖 + 𝑝𝑝𝑖𝑖 𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝐵𝐵𝑖𝑖 𝑥𝑥 ≥ 𝑑𝑑𝑖𝑖 + 𝑝𝑝𝑖𝑖

𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝐵𝐵𝑖𝑖 𝑥𝑥 ≤ 𝑑𝑑𝑖𝑖

𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝑑𝑑𝑖𝑖 < 𝐵𝐵𝑖𝑖 𝑥𝑥 < 𝑑𝑑𝑖𝑖 + 𝑝𝑝𝑖𝑖

𝑗𝑗𝑗𝑗𝑗𝑗𝑗𝑗 𝐵𝐵𝑖𝑖 𝑥𝑥 ≥ 𝑑𝑑𝑖𝑖 + 𝑝𝑝𝑖𝑖

(2.14)

(2.15)


dengan𝑝𝑝𝑖𝑖 adalah toleransi interval yang diperbolehkan untuk melakukan

pelanggaran baik pada fungsi objektif maupun batasan.

Fungsi keanggotaan untuk model ‘keputusan’ himpunan fuzzy dapat dinyatakan sebagai berikut:

µ D [Bx ] = min{µ i [Bi x ]}(2.16) Tentu saja diharapkan akan mendapatkan solusi terbaik, yaitu suatu solusi dengan nilai keanggotaan yang paling besar, dengan demikian solusi yang sebenarnya adalah: max 𝜇𝜇𝐷𝐷 [𝐵𝐵𝐵𝐵] = max min {𝜇𝜇𝑖𝑖 [𝐵𝐵𝑖𝑖 𝑥𝑥]} 𝑥𝑥≥0

(2.17)

𝑖𝑖

𝑥𝑥 ≥0

Substitusi persamaan (2.15) ke (2.17), diperoleh:

max 𝜇𝜇𝐷𝐷 [𝐵𝐵𝐵𝐵] = max min �1 − 𝑥𝑥 ≥0

𝑥𝑥≥0

𝑖𝑖

𝐵𝐵𝑖𝑖 𝑥𝑥 − 𝑑𝑑𝑖𝑖 � 𝑝𝑝𝑖𝑖

(2.18)

Semakin besar nilai domain, maka akan memiliki nilai keanggotaan yang cenderung

semakin

kecil.

Sehingga

untuk

mencari

nilai

λ-cut

dapat

dihitungsebagai: (2.19)

𝜆𝜆 = 1 – 𝑡𝑡

Dengan d i + tp i adalah nilai ruas kanan batasan ke-i.Dengan demikian akan diperoleh bentuk program linier baru sebagai berikut: Maksimumkan: 𝜆𝜆 Dengan batasan:

𝑥𝑥 ≥ 0;

𝜆𝜆𝑝𝑝𝑖𝑖 + 𝐵𝐵𝑖𝑖 𝑥𝑥 ≤ 𝑑𝑑𝑖𝑖 + 𝑝𝑝𝑖𝑖 (2.20)

𝑖𝑖 = 1,2, ⋯ , 𝑚𝑚


BAB 2 LANDASAN TEORI

Recommend Documents