OPTIMALISALI KASUS PEMROGRAMAN LINEAR DENGAN METODE GRAFIK DAN SIMPLEKS

OPTIMALISALI KASUS PEMROGRAMAN LINEAR DENGAN METODE GRAFIK DAN SIMPLEKS RISNAWATI IBNAS Jurusan Matematika, Fakultas Sains dan Teknologi, UINAM [email protected]

ABSTRAK Info: Jurnal MSA Vol. 2 No. 1 Edisi: Januari – Juni 2014 Artikel No.: 1 Halaman: 1 - 8 ISSN: 2355-083X Prodi Matematika UINAM

Metode grafik dan Metode simpleks merupakan suatu teknik penyelesaian dalam program linear yang digunakan sebagai teknik pengambilan keputusan dalam masalah yang berhubungan dengan masalah pengalokasian sumber daya yang optimal. Metode Grafik digunakan untuk mencari nilai optimal program linear khusus untuk dua variabel sedangkan untuk metode simpleks melibatkan banyak contrains (pembatas) dan mampu menyelesaian dua atau lebih variabel. Kata Kunci: metode grafik, metode simplex, maksimum, minimum, pemrograman linear

1. PENDAHULUAN

yaitu fungsi objektif (objective function) dan fungsi kendala (constraint function) yang linear.

Dalam kehidupan sehari-hari, ilmu mengenai riset operasi banyak digunakan dan diterapkan oleh manusia, terutama diterapkan pada bidang ekonomi yaitu pada dunia usaha. Setiap pelaku usaha atau pelaku ekonomi pasti melakukan apa yang disebut dengan prinsip ekonomi, yaitu dengan usaha atau modal yang sedikit mampu menghasilkan keuntungan yang besar, sehingga muncullah masalah optimisasi. Masalah optimisasi tersebut meliputi meminimumkan biaya atau memaksimumkan keuntungan dengan kapasitas sumber daya yang ada agar mampu mendapatkan hasil yang optimal.

Penyelesaian dengan metode grafik atau geometri dilakukan dengan jalan menggambarkan fungsi-fungsinya (fungsi kendala maupun fungsi tujuan) pada sistem sepasang sumbu silang, di mana sumber-sumber horizontal dan vertikal masing-masing mencerminkan jumlah setiap keluaran. Metode grafik hanya dapat digunakan dalam pemecahan masalah program linear yang berdimensi 2 × n atau m × 2, karena keterbatasan kemampuan suatu grafik dalam menyampaikan sesuatu.

Untuk mendapatkan penyelesaian optimal dari masalah tersebut, dikembangkanlah suatu cara yang disebut dengan program linear. Program linear merupakan suatu teknik perencanaan yang menggunakan model matematika dengan tujuan menemukan beberapa kombinasi alternatif dari pemecahan masalah yang kemudian dipilih mana yang terbaik untuk menyusun strategi dan langkah-langkah kebijakan tentang alokasi sumber daya yang ada agar mencapai tujuan atau sasaran yang diinginkan secara optimal dengan melibatkan variabel-variabel linear. Dalam model program linear dikenal dua macam fungsi,

Metode simpleks adalah sebuah cara untuk meneruskan dari suatu pemecahan dasar yang mungkin ke pemecahan dasar yang berdekatan yang mungkin sedemikian rupa, sehingga nilai fungsi obyektifnya tidak pernah berkurang. Hal ini biasanya menghasilkan sebuah pemecahan dasar yang mungkin untuk mana nilai fungsi obyektifnya adalah sebesar mungkin. Seperti halnya dengan metode aljabar, metode simpleks juga terlebih dahulu harus dilakukan standarisasi rumusan model, sebelum tahap penyelesaian awal dikerjakan. Fungsi-fungsi kendala yang masih berbentuk pertidaksamaan harus diubah dulu menjadi berbentuk persamaan dan prasyarat dari metode simpleks adalah eliminasi Gauss.

1

Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 Penelitian ini memaparkan penyelesaian masalah program linear dengan dengan metode grafik apabila suatu masalah program linear hanya mengandung dua variabel keputusan saja, tetapi apabila melibatkan lebih dari dua kegiatan maka metode grafik tidak dapat digunakan lagi, sehingga diperlukan metode simpleks. Metode simpleks merupakan suatu cara yang lazim digunakan untuk menentukan kombinasi optimal atau minimal dari tiga variabel atau lebih. Penelitian ini dibuat setelah mengkaji beberapa literatur dari beberapa buku dan jurnal yang telah terbit dengan tujuan agar pembaca mampu membentuk model matematika dari kasus program linear, Sebagai salah satu alat bantu dalam studi mengenai persoalan pengalokasian sumber-sumber secara optimal dan mencari keuntungan maksimum masalah program linear dengan metode grafik dan metode simpleks.

2. TINJAUAN PUSTAKA Konsep Dasar Program Linear Pemrograman linear merupakan bagian dari riset operasional. Riset operasional adalah proses pencarian cara untuk menentukan tindakan yang terbaik atau optimal dari suatu pengambilan keputusan dalam situasi sumbersumber daya yang terbatas. Menurut Frederick S. Hilter dan Gerald J. Lieberman, pemrogram linear merupakan suatu model matematis untuk menggambarkan masalah yang dihadapi. Linear berarti bahwa semua fungsi matematis dalam model ini harus merupakan fungsi linear. Programming merupakan sinonim untuk kata perencanaan. Dengan demikian membuat rencana kegiatan— kegiatan untuk memperoleh hasil yang optimal, ialah suatu hasil untuk mencapai tujuan yang ditentukan dengan cara yang paling baik (sesuai dengan model matematis) diantara semua alternatif yang mungkin. Model Pemrograman linear mempunyai tiga unsur utama, yaitu :

2

a) Variabel Keputusan, adalah variabel persoalan yang akan mempengaruhi nilai tujuan yang hendak dicapai. Didalam proses pemodelan, penemuan variabel keputusan tersebut harus dilakukan terlebih dahulu sebelum merumuskan fungsi tujuan dan kendalakendalanya. b) Fungsi Tujuan. Dalam model pemrograman linear, tujuan yang hendak dicapai harus diwujudkan kedalam sebuah fungsi matematika linear. Selanjutnya, fungsi ini dimaksimumkan atau diminumkan terhadap kendala-kendala yang ada. Beberapa contoh tujuan yang hendak dicapai didalam pabrik manajemen adalah Pemaksimuman laba perusahaan, peminimuman biaya distribusi, dan lain sebagainya. c) Kendala Kendala fungsional. Manajemen menghadapi berbagai kendala untuk 3 mewujudkan tujuantujuannya. Bentuk umum tabel linear programming : SUMBER DAYA 1 2 ⋮ m Z/unit Tingkat Kegiatan

1 a11 a11 ⋮ am1 C1 X1

Kegiatan 2 ... a12 ... a11 ... ⋮ ⋮ am1 ... C2 ... X2 ...

KAPASITAS N a1n a21

⋮ amn Cn X3

b1 b2 ⋮ bm

Model Matematis Secara umum model matematis untuk kondisi maksimal dan minimasi terdapat perbedaan pada kendala. Untuk kasus maksimasi umumnya kendala berbentuk pertidaksamaan ≤, sedangkan kasus minimasi berbentuk 1 pertidaksamaan ≥. a. Kasus Maksimasi Maksimum : 𝑍 = 𝐶1 𝑋1 + 𝐶2 𝑋2 + ⋯ + 𝐶𝑛 𝑋𝑛 𝑎11 𝑋1 + 𝑎12 𝑋2 + ⋯ + 𝑎1𝑛 𝑋𝑛 ≤ 𝑏1 𝑎21 𝑋1 + 𝑎22 𝑋2 + ⋯ + 𝑎2𝑛 𝑋𝑛 ≤ 𝑏2 ⋮ 𝑎𝑚1 𝑋1 + 𝑎𝑚2 𝑋2 + ⋯ + 𝑎𝑚𝑛 𝑋𝑛 ≤ 𝑏2 𝑋1 , 𝑋2 , … , 𝑋𝑛 ≥ 0

Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 b. Kasus Minimum 𝑍 = 𝐶1 𝑋1 + 𝐶2 𝑋2 + ⋯ + 𝐶𝑛 𝑋𝑛 𝑎11 𝑋1 + 𝑎12 𝑋2 + ⋯ + 𝑎1𝑛 𝑋𝑛 ≤ 𝑏1 𝑎21 𝑋1 + 𝑎22 𝑋2 + ⋯ + 𝑎2𝑛 𝑋𝑛 ≤ 𝑏2 ⋮ 𝑎𝑚1 𝑋1 + 𝑎𝑚2 𝑋2 + ⋯ + 𝑎𝑚𝑛 𝑋𝑛 ≤ 𝑏2 𝑋1 , 𝑋2 , … , 𝑋𝑛 ≥ 0

AsumsiAsumsi dalam Program Linear Menurut Frederick S. Hilter dan Gerald J. Lieberman, terdapat empat asumsi dalam program linear, yaitu : a) Proporsionalitas, naik atau turunnya nilai Z dan penggunaan sumber daya yang tersedia akan berubah berbanding lurus dengan perubahan tingkat kegiatan (X) b) Aditivitas, bahwa untuk setiap fungsi, nilai fungsi total dapat diperoleh dengan menjumlahkan kontribusi-kontribusi individual masing-masing kegiatan. c) Divisibilitas, Kadang-kadang variabelvariabel keputusan yang dihasilkan oleh setiap kegiatan tidak selalu menghasilkan angka fisik yang bulat (integer) tetai juga dapat berupa bilangan pecahan (noninteger). d) Kepastian, semua parameter model nilainilai (dalam program linear) merupakan konstanta-konstanta yang diketahui. Dalam praktek, asumsi ini jarang dipenuhi secara tepat. Model program linear biasanya dirumuskan untuk memilih tindakan dimasa yang akan datang, sedangkan kondisi yang akan datang itu sendiri membawa kepastian.4 3. HASIL DAN PEMBAHASAN Metode Grafik Dalam program linear, salah satu teknik yang dapat digunakan untuk memecahkan permasalahan program linear. Metode ini menggunakan pendekatan grafik dalam pengambilan keputusannya, dimana seluruh

fungsi kendala dibuat dalam satu bagian gambar kemudian diambil keputusan melalui grafik tersebut untuk menentukan nilai variabel keputusan yang optimum. Metode ini terbatas pada pemakaian untuk dua variabel. Langkah-langkah pengerjaan untuk metode grafik : a) Mengidentifikasikan variabel keputusan dan memformulasikan dalam simbol matematis. b) Mengidentifikasikan tujuan yang akan dicapai dan kendala-kendala yang terjadi. c) Memformulasikan tujuan dan kendala ke dalam fungsi model matematis d) Membuat grafik untuk kendala-kendala yang ada dalam satu bagian. Untuk membuat grafik fungsi kendala yang berbentuk pertidaksamaan (≤ 𝑑𝑎𝑛 ≥) diubah terlebih dahulu kedalam bentuk persamaan (=) e) Menentukan area kelayakan solusi pada grafik tersebut. Area layak dapat dilihat dari pertidaksamaan pada kendala. Apabila kendala berbentuk ≤, maka daerah arsiran/layak terjadi pada bagian kiri/bawah/kiri bawah, tetapi apabila bentuk pertidaksamaan ≥, maka pengarsiran dilakukan kekanan/atas/kanan atas. Apabila berbentuk persamaan (=), maka daerah layak terjadi di garis tersebut (berimpit). f) Menentukan titik-titik variabel keputusan pada area layak tersebut. g) Memilih variabel keputusan dan titik-tiik tersebut.  Pergeseran garis tujuan, yaitu dengan membuat sebarang nilai tujuan (Z) dan membuat garis tujuan dari nilai tersebut kemudian dilakukan pergeseran. Untuk masalah maksimasi, pergeseran dilakukan dengan memilih titik terjauh dari titik origin, sedangkan untuk masalah minimasi dipilih titik terdekat dari titik origin.  Metode trial error, yaitu dengan melakukan perhitungan terhadap 3

Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 keseluruhan titik-titik variabel keputusan pada area layak kemudian dipilih hasil yang optimum (untuk maksimasi dipilih Flowchart Metode Grafik

hasil tertinggi untuk minimasi dipilih hasil terendah).

MULAI

Identifikasi tujuan dari kendala

Formulasikan dalam model matematis

Membuat grafik kendala dalam satu gambar

Menentukan daerah layak dan titik koordinat

Memilih Variabel keputusan

Pergeseran garis tujuan

TIDAK

Ya Metode trial error

Menentukan nilai optimum

SELESAI

Contoh soal : ( Siswanto, 2007. “ Latihan soal”) Sebuah perusahaan angkutan nasional menggunakan 3 macam ban yaitu radial, standard dan umum. Setiap tahun pemasok ban A mampu memasok 600 ban radial, 400 ban standard dan 200 ban umum. Sedangkan pemasok B setiap tahun mampu memasok 300 ban radial, 600 ban

4

standard, dan 200 ban umum. Kebutuhan minimum masing-masing jenis ban itu setiap tahun adalah 18000ban radial, 24000 ban standard dan 10000 ban umum. Biaya pesan yang harus dibayar oleh perusahaan kepada pemasok A dan B masing-masing Rp.4000 dan Rp. 30000,- untuk setiap kali pesan. Dengan menggunakan pendekatan geometri (metode

Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 grafik), tentukan jumlah pesanan ke masingmasing pemasok tersebut. Solusi : Model matematis

Setelah memilih variabel keputusan dari titiktitik daerah feasible (daerah solusi), diperoleh biaya minimum sebesar 𝑅𝑝. 160.000 yang terjadi dengan memesan 10 unit ke pemasok jenis A dan 40 unit ke pemasok jenis B. Metode Simpleks Metode simpleks merupakan bagian dari program linear yang digunakan sebagai alat untuk memecahkan permasalahan yang menyangkut dua variabel keputusan atau lebih. Metode ini menggunakan pendekatan tabel yang dinamakan tabel simpleks. Proses eksekusi untuk mendapatkan hasil optimum dengan mengubahubah tabel simpleks sampai diperoleh hasil positif di seluruh elemen nilai baris 𝐶𝑗 − 𝑍𝑗 . Kelebihan dari metode ini mampu menghitung dua atau lebih variabel keputusan apabila dibandingkan dengan metode grafik yang hanya mampu mengaplikasikan dua variabel keputusan.

Fungsi Tujuan : 𝑀𝑖𝑛 4000𝑥 + 3000𝑦 600𝑥 + 300𝑦 ≥ 18000 400𝑥 + 600𝑦 ≥ 24000 200𝑥 + 200𝑦 ≥ 10000 𝑥, 𝑦 ≥ 0

Langkah-langkah pengerjaan metode simpleks : a) Mengidentifikasikan variabel keputusan dan memformulasikan dalam simbol matematis. b) Mengidentifikasikan tujuan yang akan dicapai dan kendala-kendala yang terjadi. c) Memformulasikan tujuan dan kendala ke dalam fungsi model matematis d) Mengubah pertidaksamaan " ≤ " pada kendala menjadi “=” dengan menambahkan variabel slack (S). e) Memasukkan data fungsi tujuan dan kendalakendala yang telah diubah tersebut kedalam tabel simpleks. Disamping itu juga menentukan nilai 𝐶𝑗 , yaitu angka pada masing-masing kolom yang akan dicari dikalikan dengan koefisien dasar (kd) dan kemudian mencari nilai 𝐶𝑗 − 𝑍𝑗 . f) Mencari kolom kunci : negatif terbesar pada baris 𝐶𝑗 − 𝑍𝑗 . g) Mencari baris kunci : positif terkecil pada indeks (indekss = 𝑏𝑗 pada masing-masing 5

Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 baris dibagi angka pada kolom kunci di masing-masing baris). a)

Mencari angka kunci : pertemuan antara kolom kunci dan baris kunci. b) Mengubah variabel keputusan pada baris kunci dengan variabel keputusan pada kolom kunci dan kemudian mengubah seluruh elemen pada baris kunci dengan cara membagi seluruh elemen tersebut dengan angka kunci. c) Mengubah nilai-nilai pada baris lain (di luar baris kunci) dengan menggunakan pendekatan nilai baris yang baru=nilai-nilai baris yang lama dikurangi nilai-nilai pada

baris baru yang telah dikalikan dengan koefisien kolom kunci pada baris awal tersebut. d) Memastikan seluruh elemen pada baris 𝐶𝑗 − 𝑍𝑗 tidak ada yang bernilai negatif, apabila masih terdapat nilai negatif maka diulangi melalui langkah ke-f dan seterusnya. e) Apabila seluruh elemen pada baris 𝐶𝑗 − 𝑍𝑗 tidak ada bernilai negatif maka proses eksekusi telah selesai, nilai Z optimum dan besarnya variabel keputusan berada pada kolom tersebut (𝑍𝑗 𝑑𝑎𝑛 𝑏𝑗 ).

Flowchard Metode Simpleks Mulai Identifikasi Tujuan dari kendala

Mencari kolom kunci

Formulasikan dalam model matematis

Mencari baris kunci

Seluruh elemen C(j)-Z(j)

Merubah pertidaksamaan pada kendala

Mencari angka kunci

Ya

Melakukan perubahan pada baris kunci

Proses eksekusi selesai, Nilai Z dan variabel keputusan ada pada Z(j) dan b(j)

Memasukan kendala dalam tabel simpleks

Melakukan perubahan pada baris yang lain

Contoh soal : ( Wijaya Andi, 2012. “ Latihan soal”) 1. TSR Co. Adalah perusahaan yang bergerak di bidang penghasil telepon genggam dengan model dan fitur yang serupa dengan Blackberry. Saat ini ada 3 produk yang diproduksi oleh TSR Co., yaitu : Toy Phone; Style Phone dan Ready Phone. Dimana harga untuk Toy Phone adalah Rp. 3.500.000., Stryle Phone adalaha Rp. 4.500.000., dan Rp.

6

Tidak

Selesai

4.000.000., untuk Ready Phone. Untuk memproduksi sebuh Toy Phone dibutuhkan 2 unitt microchip R. Dan untuk memproduksi Ready Phone membutuhkan 2 unit microchip T; 1 unit microchip S dan 3 unit microchip R. Jumlah microchip yang tersedia untuk microchip T adalah sebanyak 20 unit; microchip S sebanyak 25 unit; dan microchip R sebanyak 30 unit. Dari data diatas, bantulah perusahaan untuk menentukan kombinasi

Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 2𝑥 + 2𝑦 + 3𝑧 ≤ 30

produk agar tercapai pendapatan maksimal, dan besarnya pendapatan maksimal tersebut. Solusi : Model matematis :

𝑥, 𝑦, 𝑧 ≤ 0 Dari fungsi kendala diatas, berubah menjadi :

Maksimumkan (dalam jutaan) :

2𝑥 + 𝑦 + 2𝑧 + 𝑆1 = 20

𝑍 = 3.5𝑥 + 4.5𝑦 + 4𝑧

3𝑥 + 2𝑦 + 𝑧 + 𝑆2 = 25

Kendala-kendala :

2𝑥 + 2𝑦 + 3𝑧 + 𝑆3 = 30

2𝑥 + 𝑦 + 2𝑧 ≤ 20

3𝑥 + 2𝑦 + 𝑧 ≤ 25 Fungsi tujuan menjadi : 𝑍 = 3,5 𝑋 + 4,5𝑌 + 4𝑍 + 0𝑆1 + 0𝑆2 + 0𝑆3 Tebel simpleks : Iterasi pertama :

𝑪𝒋 0 0 0

Variabel Dasar 𝑺𝟏 𝑺𝟐 𝑺𝟑 𝑪𝒋 𝑪𝒋 − 𝒁𝒋

𝒁𝒋 𝒃𝒋 20 25 30 0 0

3,5 x 2 3 2 0 -3.5

4,5 y 1 2 2 0 -4.5

4 z 2 1 3 0 -4

0 𝑺𝟏 1 0 0 0 0

0 𝑺𝟐 0 1 0 0 0

0 𝑺𝟑 0 0 1 0 0

Indeks -

Iterasi terakhir :

𝑪𝒋

Variabel Dasar

0 4,5 4

𝑺𝟏 𝑦 z 𝑪𝒋 𝑪𝒋 − 𝒁𝒋

𝒁𝒋 𝒃𝒋 3,75 11,25 2,5 60,625 60,625

3,5 x 1,25 1,75 -0,5 5,875 0

4,5 y 0 1 0 4,5 0

Kesimpulan : Karena seluruh elemen pada baris 𝑪𝒋 − 𝒁𝒋 tidak ada yang bernilai negatif, maka penyelesaian telah optimal. Besarnya keuntungan maksimal perusahaan TSR Co. Adalah Rp. 60.625.000.dengan tingkat produksi Style Phone 11,25 unit dan Ready Phone sebanyak 2,5 unit. Dari tabel diatas seluruh sumber daya habis terpakai (scarce) dan tidak ada sumber daya yang berlebihan (aboundanmt).

4 z 0 0 1 4 0

0 𝑺𝟏 1 0 0 0 0

0 𝑺𝟐 0,25 0,75 -0,5 1,375 1,375

0 𝑺𝟑 -0,75 -0,25 0,5 0.875 0.875

Indeks -

4. KESIMPULAN Berdasarkan pembahasan dari penelitian diatas dapat diambil kesimpulan bahwa : 1. Metode Grafik, hanya dapat dilakukan untuk masalah program linear dengan dua variabel, sedangkan 2. Metode simpleks, dapat dilakukan untuk masalah program linear baik untuk dua atau lebih variabel, dengan langkah awal yaitu memformulasikan masalah kedalam

7

Jurnal MSA Vol. 2 No. 1 Ed. Jan-Juni 2014 program linear, menambahkan variabel slack atau surplus pada kendala untuk memperoleh bentuk standar, kemudian lakukan-langkah metode simpleks. 5. DAFTAR PUSTAKA Hiller, Frederick, R. And Lieberen, Gerald. 1994. “Introduction to Opertions Research” USA : McGrow-Hill Companies

8

Lusiana, 2006. Penyelesaian Program Linier dengan Metode Simpleks. Skripsi S-1 Metematika UNAND, tidak diterbitkan. Siswanto, 2007. Operation Research, Erlangga, Jakarta. Taha Hamdy A., 1996. Riset Operasi Suatu Pengantar” Jilid 1.Bina Rupa Aksara ,Jakarta. Wijaya Andi, 2012, Pengantar Riset Operasi Edisi 2. Mitra Wicana Media, Jakarta.