Linear Programming, Queue Theory, Simulation, Decision Tree & Decision Analysis

Pemograman Linier

Difinisi Pemograman Linier
Setiap perusahaan atau organisasi memiliki keterbatasan atas sumber dayanya, baik keterbatasan dalam jumlah bahan baku, mesin dan peralatan, ruang tenaga kerja, jam kerja, maupun modal. Dengan keterbatasan ini, perusahaan perlu merencanakan strategi yang dapat mengoptimalkan hasil yang ingin dicapai, baik itu berupa keuntungan maksimal atau biaya minimal. Berbagai cara lain telah ditemukan untuk tujuan itu, salah satu diantaranya pemrograman linear (Eddy, 2008).
Pemprograman linier adalah metode matematik dalam mengalokasikan sumber daya yang terbatas untuk mencapai suatu tujuan seperti memaksimalkan keuntungan atau meminimumkan biaya. Program linier berkaitan dengan penjelasan suatu kasus dalam dunia nyata sebagai suatu model matematik yang terdiri dari sebuah fungsi tujuan linier dengan beberapa kendala linier (Taha, 1993).
Program linier banyak digunakan untuk menyelesaikan masalah optimal didalam industri, perbankan, pendidikan, dan masalah-masalah lain yang dapat dinyatakan dalam bentuk linier.



Sifat-sifat dasar atau Karakteristik Pemrograman Linear adalah sebagai berikut :

1.    Sifat linieritas suatu kasus dapat ditentukan dengan menggunakan beberapa cara. Secara statistik, cara ini dapat diperiksa kelinearan menggunakan grafik (diagram pencar).
2.    Sifat proposional dipenuhi jika kontribusi setiap variabel pada fungsi tujuan atau penggunaan sumber daya yang membatasi proposional terhadap level nilai variabel. Jika harga per unit produk misalnya adalah sama berapapun jumlah yang dibeli, maka sifat proporsional dipenuhi. Atau dengan kata lain, jika pembelian dalam jumlah besar mendapatkan diskon, maka sifat proporsional tidak dipenuhi. Jika penggunaan sumber daya per unitnya tergantung dari jumlah yang diproduksi, maka sifat proporsionalitas tidak dipenuhi.
3.    Sifat additivitas mengasumsikan bahwa tidak ada bentuk perkalian silang diantara berbagai aktivitas, sehingga tidak dapat ditemukan bentuk perkalian silang pada model. Sifat aditivitas berlaku baik bagi fungsi tujuan maupun pembatas (kendala). Sifat aditivitas dipenuhi jika fungsi tujuan merupakan penambahan langsung kontribusi masing-masing variabel keputusan.
4.    Sifat divisiabel berarti unit aktivitas dapat dibagi dalam sembarang level fraksional, sehingga nilai variabel keputusan non integer dimungkinkan.
5.    Sifat kepastian menunjukkan bahwa semua parameter model berupa konstanta. Artinya koefisien fungsi tujuan maupun fungsi pembatas merupakan suatu nilai pasti, bukan merupakan nilai dengan peluang tertentu.


Model Pemograman Linier

Model matematis perumusan masalah umum pengalokasian sumberdaya untuk berbagai kegiatan, disebut sebagai model pemrograman linear. Model pemrogram linear ini merupakan bentuk dan susunan dalam menyajikan masalah-masalah yang akan dipecahkan dengan teknik pemrogram linear.

Masalah pemrograman linear secara umum dapat ditulis dalam bentuk umum sebagai berikut :








Persamaan (2. 1) dan (2. 2) bisa dikatakan sebagai model standar dari masalah pemrograman linear. Sebuah formulasi matematika yang sesuai dengan model ini adalah masalah program linier batas normal (Hiller, 1990).
Umumnya terminologi untuk model program linier sekarang dapat diringkas. Fungsi objektif, c1x1 + c2x2+ … + cnxn, dengan kendala sebagai pembatas. Batasan m (dengan fungsi semua variabel a11x1 + a12x2 + … + a1nxn) kadang-kadang disebut fungsi pembatas. Sama halnya dengan kendala xj ≥ 0 disebut pembatas non negatif.
Beberapa hal yang perlu diperhatikan dalam penerapan linear programming adalah:
1.    Fungsi tujuan dan persamaan setiap batasan harus linear. Ini mencakup pengertian bahwa perubahan nilai z dan penggunaan sumber daya terjadi secara proporsional dengan tingkat perubahan kegiatan
2.    Parameter-parameter harus dapat diketahui/ diperkirakan dengan pasti (deterministic)
3.    Variabel-variabel keputusan harus dapat dibagi ini berarti bahwa suatu penyelesaian “feasible” dapat berupa bilangan pecahan.
Beberapa aturan bentuk program linear baku/standar (Aminudin, 2005) :
1.    Semua batasan/kendala adalah persamaan (dengan sisi kanan yang non-negatif).
2.    Semua variabel keputusan adalah non-negatif.
3.    Fungsi tujuan dapat berupa maksimasi atau minimasi.
Formulasi Permasalahan
    Masalah keputusan yang sering dihadapi analisis adalah alokasi optimum sumber daya.
    Sumber daya dapat berupa uang, tenaga kerja, bahan mentah, kapasitas mesin, waktu, ruangan atau teknologi.
    Tugas analisis adalah mencapai hasil terbaik dengan keterbatasan sumber daya itu.
    Setelah masalah diidentifikasikan, tujuan ditetapkam, langkah selanjutnya adalah formulasi model matematika.
Formulasi model matematika ada 3 tahap :
1.    Tentukan variabel yang tidak diketahui dan dinyatakan dalam simbol.
2.    Membentuk fungsi tujuan yang ditunjukkan sebagai suatu hubungan linier dari variabel keputusan.
3.    Menentukan semua kendala masalah tersebut dan mengekspresikannya dalam persamaan atau pertidaksamaan.
Dasar-dasar umum Linear Programing meliputi bentuk model dan prosedur penyelesaian yang dibagi atas dua pemecahan masalah, yaitu :


A.    Metode Grafik (Grafical Method)
Metode grafik adalah metode yang digunakan untuk memecahkan masalah linear programming yang menyangkut dua variabel keputusan.
Didalam penerapan metode grafik, ada langkah-langkah yang harus ditempuh adalah sebagai berikut:
 Menyusun permasalahan yang ada
 Menetukan fungsi tujuan yang akan dicapai
 Mengidentifikasi kendala-kendala, yang berlaku dalam bentuk ketidaksamaan menjadi bentuk persamaan
 Menggambarkan masing-masing garis pembatas dalam satu system koordinat.
 Menentukan daerah (area) yang memenuhi batasan-batasan tersebut. Daerah ini disebut dengan “daerah Feasible”.


B. Metode Simpleks (Simplex Method)
Metode Simpleks digunakan untuk memecahkan masalah linear programming yang menyangkut dua atau lebih variabel keputusan. Metode simpleks merupakan algoritma untuk memecahkan masalah umum linear programming.

Metode simpleks adalah metode aljabar yang digunakan untuk memecahkan masalah-masalah linear yang terdiri dari tiga variabel atau lebih. Pedoman langkah-langkah penyelesaian metode simplek dapat disusun sebagai berikut :

1. Menentukan fungsi objective atau fungsi tujuan yang akan dicapai.
2. Mengidentifikasi kendala-kendala (constrain) dalam bentuk ketidaksamaan.
3. Merubah ketidaksamaan dari kendala-kendala yang ada menjadi bentuk persamaan, dengan cara menambahkan unsur-unsur slack variable kedalamnya. Suatu variable “slack” menyajikan secara perhitungan jumlah yang diperlukan untuk merubah tanda ketidaksamaan (<) menjadi persamaan (=) sehingga semua variable ditunjukan dalam persamaan, setiap variable slack yang tidak berhubungan dengan salah satu persamaan batasan diberi koefisien nol dan ditambahkan ke persamaan itu.
4. Memasukan atau menyusun fungsi tujuan dan kendala yang ada ke dalam table simpleks pertama.
5. Mencari nilai Zj, nilai Zj menunjukan jumlah laba kotor yang dihasilkan melalui pemasukan satu unit variable ke dalam penyelesaian.
6. Menemukan kolom kunci, baris kunci, dan nomor kunci. Kolom kunci ditentukan dengan cara memilih nilai baris Cj – Zj yang positif terbesar. Dipilih positif terbesar karena permasalahanya adalah maksimisasi. Untuk menentukan baris kunci, terlebih dahulu harus dicari angka-angka pengganti. Angka-angka pengganti merupakan angka-angka hasil bagi antara angka pada kolom kuantitas dengan angka pada kolom kunci yang bersesuaian. Selanjutnya baris kunci dipilih, yaitu baris yang mempunyai angka pengganti yang merupakan positif terkecil.
7. Mengganti angka-angka pada baris kunci dengan angka-angka baru. Angka-angka baru diperoleh dengan cara membagi semua angka yang ada pada baris kunci dengan nomor kunci.
8. Mengganti angka-angka baru pada baris lain dengan rumus sebagai berikut :


9. Memasukan atau menyusun angka-angka baru tersebut ke dalam tabel simpleks yag kedua, kemudian mencari nilai Zj yang baru dan mencari nlai Cj – Zj masih ada angka positif (lebih besar sama dengan nol), maka dilakukan lagi langkah-langkah dari langkah 6. Jika angka-angka pada baris Cj –Zj sudah tidak ada lagi yang positif (lebih kecil sama dengan nol) berarti bahwa kombinasi yang dicari sudah optimum.

Queueing Theory atau Teori Antrian


Adalah teori yang menjelaskan bagaimana  fenomena antrian terjadi dan kemudian mencari solusi optimal terhadap fenomena tersebut.
Fenomena Antrian pertama kali diamati oleh Agner Krarup Erlang[1] Meskipun fenomena awal antrian itu diamati di kantor telp manual pada abad 18, namun untuk memudahkan pemahaman terhadap fenomena antrian tersebut bisa digambarkan melalui model berikut :






 Antrian terjadi kaena sistem sedang sibuk. Mereka yang antri adalah mereka yang mengharpkan proses dalm sistem. Ada kemungkinan populasi pelanggan sistem datang dan melihat antrian lalu pergi atau balking tidak diprhitungkan sebagai antri. Oleh karena itu, mereka yang ada dalam Sistem Antrian adalah mereka yang sedang antri dan mereka yang sedang dalam proses.
Ada dua variabel yang terlibat dalam Teori Antrian, yaitu λ atau tingkat kedatangan, dan μ atau tingkat pelayanan. Asumsi: Fenomena antrian terjadi ketika λ > μ. Bila kondisi ini tidak terpenuhi maka antrian tidak terjadi. Memang tidak seluruh waktu akan tterjadi antrian, namun seperti digambarkan oleh proses Poisson diatas, selalu ada traffic jam pada interval waktu tertentu. Maka, tingkat kedatangan atau λ mengikuti proses Poisson adalah asumsi yang lain. Oleh karena itu, Queueing System Equilibrium mengikuti konsep sbb :







Model Sistem Antrian dalam gambar diatas adalah model antrian dasar. Ada empat  konfigurasi model antrian :
1.    Fase Tunggal Kanal Tunggal atau Single Phase Single Channel
2.    Fase Tnggal Multi Kanal atau Single Phase Multi Channel
3.    Multi Fase Kanal Tunggal atau Multi Phase Sngle Channel
4.    Multi Fase Multi Kanal atau Multi Phase Multi Channel
Fenomena antrian, mungkin sering mngundang penjelasan mengenai teori dasar terbentuknya antrian. Erlang menggunakan proses Poisson untuk memodelkan terbentuknya antrian sbb :






Arrival rate atau tingkat kedatangan, dengan notasi λ terdistribusi secara Poisson. Dalam model di atas, tampak waktu yang diobsrvasi di bagi ke dalam beberpa interval waktu yang sama. Ternyata, ada interval waktu yang kosong dan ada yang banyak penggunanya. Demikianlah fenomena yang diamati dalam fenomena tersebut yang melahirkan Teori Antrian. Fenomena serupa juga terjadi pada traffic light sekitar jam 07:00 namun sangat sepi pada malam hari biasa.
Berikut adalah gambaran bagaimana λ diturunklan dari Poisson process :