BAB 2 Studi Literatur

BAB II

STUDI LITERATUR

2.1.    Pemrograman Dinamis      

          Program dinamis adalah suatu teknik dalam metoda kuantitatif yang sering kali beruna dalam menentukan urutan keputusan-keputusan yang saling berhubungan. Program dinamis merupakan suatu pendekatan yang sifatnya umum dan memecahkan persoalan yang ada, dan persamaan-persamaan khusus yang digunakan harus dikembangkan sesuai dengan permasalahannya. Oleh karena itu, perlu diketahui struktur umum dari persoalan program dinamis untuk dapat mengenali apakah suatu persoalan dapat diselesaikan dengan prosedur program dinamis serta bagaimana pemecahannya (Dimyati, 2006). 

2.1.1  Pengertian Pemrograman Dinamis

Program dinamis adalah suatu teknik matematis yang biasanya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Tujuan utama model ini yaitu untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu. Program dinamis berbeda dengan program linier, pada persoalan program dinamis tidak ada formulasi matematis yang standar. Persamaan-persamaan yang terpilih untuk digunakan harus dikembangkan agar dapat memenuhi masing-masing situasi yang dihadapi (Dimyati, 2006).

Program dinamis dapat juga disebut multi stage programming yang berciri memecah persoalan menjadi bagian yang lebih kecil (sub problem atau stage) dimana keputusan dibuat secara berurutan. Multi stage programming memperlakukan persoalan dimana keputusan pada suatu tahap dapat mempengaruhi keputusan pada tahap berikutnya. Penemu dan orang yang bertanggung jawab atas kepopuleran program dinamis adalah Richard Bellman. Sebagai suatu konsep, program dinamis  lebih luwes dibanding kebanyakn model dan metode matematika dalam OR. Penerapan pendekatan program dinamis telah dikabarkan mampu untuk menyelesaikan berbagai masalah seperti alokasi, muatan (knapsack), capital budgeting, pengawasan persediaan dan sebagainya (Mulyono, 2007).

2.1.2  Karakteristik Persoalan Program Dinamis

          Persoalan program dinamis memiliki beberapa karakteristik. Berikut ini diberikan beberapa gambaran dasar yang menandai persoalan program dinamis (Dimyati, 2006):

1.        Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada masing-masing tahap diperlukan adanya satu keputusan.

2.        Masing-masing stage terdiri atas sejumlah state yang berhubungan dengan stage  yang bersangkutan. Jumlah state ini bisa terbatas, bisa pula tidak terbatas.

3.        Hasil dari keputusan yang diambil pada setiap stage ditransformasikan dari state yang bersangkutan ke state yang berikutnya  pada satge yang berikutnya pula.

4.        Keputusan terbaik pada suatu stage bersifat independen terhadap keputusan yang dilakukan pada stage sebelumnya.

5.        Prosedur pemecahan persoalan dimulai dengan mendapatkan cara atau keputusan terbaik untuk setiap state dari stage terakhir.

6.        Ada suatu hubungan timbal balik yang mengidentifikasi keputusan terbaik untuk setiap state pada stage (n+1). Oleh karena itu, untuk mendapat keputusan terbaik jikan akan bergerak dari state s pada stage n, terlebih dahulu harus didapatkan nilai terbaik dari x_n pada stage (n+1).

Dalam hal ini ditetapkanlah:

a.         Variabel x_n sebagai variabel keputusan pada stage n (n = 1,2, ..., N).

b.         f_n (s, x_n) sebagai nilai fungsi tujuan yang akan dimaksimumkan atau diminimumkan, dengan catatan bahwa sistem akan berawal dari state s pada stage n dan x_n telah terpilih sehingga f_n (s, x_n) = Csx_n + f_n+1 (x_n).

c.          fn(s) sebagai nilai maksimum atau minimum dari  f_n (s, x_n) untuk seluruh nilai x_n yang mungkin.

7.        Dengan menggunakan hubungan timbal balik, prosedur penyelesaian persoalan bergerak mundur stage demi stage, pada setiap stage berusaha diperoleh keputusan optimum untuk masing-masing state hingga akhirnya diperoleh keputusan optimum yang menyeluruh, mulai dari stage awal.

2.1.3  Ciri-Ciri Pokok Masalah Program dinamis

          Program dinamis adalah suatu pendekatan matematika tentang optimasi proses banyak tahap. Konsep dasarnya diungkapkan dalam Principle of Optimality oleh Bellman. Ciri-ciri dasar suatu masalah program dinamis adalah (Mulyono, 2007):

1.        Dalam masalah program dinamis, keputusan tentang suatu masalah ditandai dengan optimasi pada tahap berikutnya, bukan keserentakan. Ini berati jika suatu masalah akan diselesaikan dengan program dinamis ia harus dipisahkan menjadi n sub problem.

2.        Program dinamis berkaitan dengan masalah-masalah dimana pilihan atau keputusan dibuat pada masing-masing tahap. Seluruh kemungkinan pilihan dicerminkan, diatur keduanya, oleh sistem status pada setiap tahap.

3.        Berkaitan dengan setiap keputusan pada setiap tahap adalah return function yang mengevaluasi pilihan yang dibuat dalam arti sumbangan yang diberikan kepada tujuan keseluruhan (maksimasi ayau minimasi).

4.        Setiap tahap proses keputusan dihubungkan dengan tahap berdekatan melalui fungsi transisi. Fungsi ini dapat berupa kuantitas yang diskrit maupun kontinu tergantung pada sifat-sifat masalah.

5.        Suatu hubungan rekursif digunakan untuk menghubungkan kebijaksanaan optimum pada tahap n dengan n-1. Ada dua macam prosedur rekursif yaitu forward atau secara maju dan backward atau secara mundur. Hubungan itu adalah:

a.       Forward recursive equation (perhitungan dari depan kebelakang).

b.      Backward recursive equation (perhitungan dari belakang ke depan).

Perbedaan pokok antara metode forward dan backward adalah terletak dalam cara mendefinisikan state.

6.        Dengan menggunakan hubungan rekursif ini, prosedur penyelesaian bergerak dari tahap ke tahap sampai kebijaksanaan optimum tahap terakhir ditemukan. Sekali kebijaksanaan optimum tahap n telah ditemukan, n komponen keputusan dapat ditemukan kembali dengan melacak balik melalui fungsi transisi tahap n.

2.1.4  Prinsip Optimalitas

          Rangkaian keputusan yang optimal dibuat dengan menggunakan prinsip optimalitas pada program dinamis. Prinsip optimalitas berbunyi jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal, pada program dinamis rangkaian keputusan yang optimal dibuat dengan menggunakan prinsip optimalitas. Prinsip optimalitas berati bahwa jika kita bekerja dari tahap k ke tahap k+1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ketahap awal.  Ongkos pada tahap k+1 = (ongkos yang dihasilkan pada tahap k) + (ongkos dari tahap k ke tahap k+1).

Prinsip optimalitas ini menjamin bahwa pengambilan keputusan pada suau tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.  Terdapat dua metode yaitu metode greedy yang mana pada metode ini hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan yang dihasilkan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.

            Pengembangan algoritma terdapat dalam program dinamis. Berikut terdapat empat langkah-langkah dalam melakukan pengembangan algoritma pada program dinamis :

1.        Karakteristikkan struktur solusi optimal.

2.        Hitung nilai solusi optimal secara maju atau mundur.

3.        Definisikan secara rekursif nilai solusi optimal.

4.        Konstruksi solusi optimal.

2.1.5  Program Dinamis Deterministik

          Cara untuk mengkategorikan persoalan program dinamis deterministik ini adalah dengan melihat bentuk fungsi tujuannya. Contohnya, fungsi tujuannya mungkin meminimumkan jumlah kontribusi dari masing-masing stage atau dapat pula memaksimumkannya atau meminimumkan hasil perkaliannya. Cara pengkategorian yang lain didasarkan pada keadaan dari kumpulan (set) state pada suatu stage. Artinya, apakah state Sn dapat direpresentasikan sebagai variabel state diskrit atau kontinu, atau mungkin diperlukan suatu vektor state (lebih dari satu variabel). Program dinamis deterministik dapat diterangkan dengan diagram berikut (Dimyati, 2006):

         stage n                                                               stage n+1

       state:       

                                                                 kontribusi dari Xn

                  f_n (Sn, Xn)                                                                     f*n+1 (Sn+1)

Gambar 2.7 Diagram Program Dinamis Deterministik

2.1.6  Program Dinamis Probabilistik

          Berbeda dengan program dinamis deterministik, pada program dinamis probabilistikini stage berikutnya tidak dapat seluruhnya ditentukan oleh state dan keputusan pada stage saat ini, tetapi ada suatu distribusi kemungkinan mengenai apa yang akan terjadi. Namun, distribusi kemungkinan ini masih seluruhnya ditentukan oleh state dan keputusan pada stage saat ini. Struktur program dinamis probabilistik ini dapat digambarkan sebagai berikut (Dimyati, 2006):

                                                                                                  stage n+1

                                                                                                     s_n+1

                                                                                                                 f_n*+ 1 (1)

 

  state:                                                                                                       f_n*+ 1 (2)

 

    f_n ( Sn, Xn)

                                                                                                                                               f_n*+1 (N)

Gambar 2.8 Diagram Program Dinamis Probabilistik

            Gambar diatas apabila diperluas sehingga mencakup seluruh state dan keputusan pada seluruh stage yang mungkin, maka gambar tersebut akan membentuk pohon keputusan. Jika pohon keputusan ini tidak terlalu lebar, maka akan dapat digunakan sehingga cara untuk membuat ikhtisar dari berbagai kemungkinan dapat terjadi. Akibat struktur probabilistik, maka hubungan antara f_n (s_n, x_n) dengan f_n*+1 (s_n + 1) menjadi lebih rumit dari pada untuk program dinamis deterministik. Bentuk yang tepat untuk hubungan ini akan bergantung pada bentuk fungsi tujuan secara keseluruhan (Dimyati, 2006).   

       

2.1.7    Knapsack

Knapsack adalah tas atau karung yang digunakan untuk memasukkan sesuatu, tetapi tidak semua barang bisa ditampung kedalam karung tersebut. Karung tersebut hanya dapat menyimpan beberapa objek dengan total ukurannya (weight) lebih kecil atau sama dengan ukuran kapasitas karung. Knapsack memiliki tiga jenis persoalan-persoalan yang harus diselesaikan, diantaranya Knapsack 0/1 merupakan sesuatu yang dimasukkan kedalam karung dimensinya harus dimasukkan semua atau tidak sama sekali. Knapsack bounded adalah sesuatu yang dimasukkan kedalam karung dimensinya bisa dimasukkan sebagaian atau seluruhnya (Wahab, 2005).

Knapsack problem bisa diselesaikan dengan berbagai cara. Ada beberapa strategi algoritma yang bisa menghasilkan solusi optimal, diantaranya adalah brute force. Strategi ini tidak efisien, jadi knapsack problem pada laporan ini akan diselesaikan dengan greedy algorithm yaitu solusi yang mencari nilai optimum. Algoritma ini memecahkan permasalahan langkah per langkah, pada setiap langkah (Wahab, 2005):

1.    Mengambil pilihan terbaik yang bisa diperoleh saat itu juga tanpa memperatikan konsekuensi kedepan (prinsip “take what you can get now!”).

2.    Berharap bahwa dengan memilih optimum lokal pada setiap langkah akan berakhir dengan optimum global.

Greedy Algorithm memiliki beberapa strategi yang digunakan untuk memilih objek yang akan dimasukkan kedalam knapsack. Berikut adalah strategi-strategi yang digunakan (Wahab, 2005):

1.    Greedy By Profit

Langkah dalam greedy by profit, knapsack diisi dengan objek yang mempunyai keuntungan terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang paling menguntungkan terlebih dahulu. Pertama kali yang dilakukan adalah mengurutkan secara menurun objek-objek berdasarkan profit-nya.

2.    Greedy by weight

Langkah greedy by weight, knapsack diisi dengan objek yang mempunyai berat paling ringan. Strategi ini mencoba memaksimumkan keuntungan dengan memasukkan sebanyak mungkin objek ke dalam knapsack. Pertama kali yang dilakukan adalah mengurutkan secara menaik objek-objek berdasarkan beratnya, kemudian baru diambil satu-persatu objek yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.

3.    Greedy by density

Langkah greedy by density, knapsack diisi dengan objek yang mempunyai densitas terbesar. Strategi ini mencoba memaksimumkan keuntungan dengan memilih objek yang mempunyai keuntungan per unit berat terbesar. Pertama kali yang dilakukan adalah mencari nilai profit per unit (density) dari tiap-tiap objek, kemudian objek-objek tersebut diurutkan berdasarkan densitynya. Objek selanjutnya diambil satu persatu yang dapat ditampung oleh knapsack sampai knapsack penuh atau sudah tidak ada objek lagi yang bisa dimasukkan.

Pemilihan objek berdasarkan salah satu dari ketiga strategi di atas tidak menjamin akan memberikan solusi optimal. Berbeda dengan strategi brute force yang selalu dapat memberikan hasil yang optimal. Tetapi greedy mengurangi jumlah langkah (kompleksitas) pencarian (Wahab, 2005).

    

BAB 1 Proposal Penelitian Ilmiah ( Revisi 1 )

Judul Penelitian :

Pengaruh distribusi terhadap keuntungan produk air minum PT Air Abadi

1.                  Latar Belakang    

Distribusi merupakan suatu hal yang sangat fundamental dalam kehidupan kita sehari-hari. Secara tidak langsung distribusi akan mempengaruhi keuangan suatu perusahaan. Perusahaan membutuhkan solusi untuk meminimalkan kerugian atau memaksimalkan keuntungan dalam distribusi produk. Dampak distribusi mengakibatkan keuntungan produk air minum tidak optimal. Dibutuhkan suatu metode yang dapat mengoptimalkan distribusi air minum, metode tersebut adalah program dinamis. Program dinamis merupakan suatu teknik matematis yang biasannya digunakan untuk membuat suatu keputusan dari serangkaian keputusan yang saling berkaitan. Tujuan utama model ini adalah untuk mempermudah penyelesaian persoalan optimasi yang mempunyai karakteristik tertentu

            Jika tidak diperbaiki perlahan-lahan perusahaan akan mengalami kerugian secara kontinu walaupun tidak terlalu besar. Alasan menggunakan program dinamis karena dapat memperbaiki system pengambilan keputusan.  Penerapanya pemrograman dinamis banyak digunakan pada proses optimalisasi masalah. Program dinamis merupakan sebuah algoritma pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah atau tahapan sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan. Harapan penggunaan metode program dinamis adalah perusahaan dapat menentukan produk yang didistribusikan dengan tepat.  

2.         Rumusan Masalah

            Perumusan masalah merupakan perumusan yang digunakan untuk mengidentifikasi permasalahan yang terdapat dalam suatu penelitian. Perusahaan ingin memilih produk dengan profit terbesar dan pemilihan jalur distribusi pada produk air minumnya sehingga keuntungan perusahaan dapat meningkat. Terdapat beberapa rumusan masalah yang didasarkan pada latar belakang penelitian ini :

1.         Bagaimana cara memilih produk dengan keuntungan yang optimal?

2.         Bagaimana cara menentukan jalur distribusi yang optimal dengan biaya minimum ?      

3.                  Tujuan Penelitian

Tujuan penelitian merupakan tujuan yang ingin dicapai peneliti guna menyelesaikan penelitian. Berikut adalah tujuan penelitian yang ingin dicapai :

1.         Mengetahui produk yang dapat diangkut dengan keuntungan optimal

2.         Menngetahui jalur distribusi yang tepat dengan biaya minimum

4.                  Batasan Penelitian     

            Batasan penelitian dilakukan agar pembahasan yang dilakukan tidak menyimpang dari ketentuan yang ada. Berikut ini merupakan pembatasan masalah dari penelitian ini :

1.         Penelitian hanya dilakukan pada produk air minum.

2.         Metode yang digunakan hanya progam dinamis.

3.         Penelitian dilakukan di PT Air Abadi dan PT tujuan distribusi.

4.         Software yang digunakan adalah QM.  

5.         Metode Penelitian     

1.            Sumber Data

Data yang diteliti diperoleh dari Laporan Data PT Air Abadi  dari laporan hasil pengiriman produk air minum setiap bulan dan Laporan keuntungan dan kerugian PT Air Abadi.

2.             Jenis Data

Jenis data yang digunakan adalah air minum, surat penjualan, nominal penjualan, nominal pengiriman dan transportasi pengiriman produk.

3.                  Tipe Data

Data yang diteliti merupakan data sekunder yang dikumpulkan berupa data

runtun waktu (time series). Data-data tersebut diterbitkan secara berkala oleh PT Air Abadi dalam bentuk buletin dan laporan triwulan atau tahunan, dengan demikian keabsahan data tersebut merupakan tanggung jawab perusahaan itu.

-          Objek Penelitian

Objek penelitian dalam penulisan ini adalah PT Air Abadi.

-          Periode Penelitian

Data yang digunakan merupakan data bulan agustus 2012 sampai dengan januari 2014.

1.6       Rencana Waktu Penelitian   

No	Deskripsi	Bulan Ke
	Kegiatan	1	2	3	4	5	6
1	Penyusunan Proposal PI
2	Kerja Praktek
3	Pengambilan Data
4	Pengolahan Dan Analisis
5	Pembuatan PI

           

7.         Daftar Pustaka  

            Jhon Hendri. 2009. “Pengaruh Nilai Tukar Rupiah Dan Suku Bunga Riil Terhadap  Cadangan Primer Dan Kredit Untuk Nasabah Bank Mandiri”. Tesis Universitas Gunadarma. Jakarta.