Pengertian Program
Dinamik
1. Masalah
alokasi
Model
alokasi dalam permasalahan program linear merupakan aplikasi yang paling praktis.
Semua model alokasi biasanya mencoba untuk mengalokasi-kan suatu sumber daya
yang terbatas supaya mengoptimalkan hasil dari alokasi itu. Sumber daya yang
terbatas itu dapat berupa lahan, bahan baku, tenaga kerja, mesin, modal, waktu,
dan lain lain. Alokasi ini dilakukan untuk memaksimalkan laba atau memperkecil biaya,
atau mengoptimalkan ukuran-ukuran efisiensi lain yang ditetapkan oleh keputusan
pembuat.
2. Masalah Muatan (Cargo – Loading)
Masalah knapsack muncul pada tahun 1957 yang dikemukakan oleh Dantzig.
Munculnya permasalahan ini adalah dari seorang tentara yang akan berangkat ke
medan tempur. Ia membawa sebuah ransel yang mempunyai kapasitas volume
tertentu. Ransel tersebut akan diisi berbagai perlengkapan yaitu senjata,
pakaian, makanan, obat-obatan dan lain-lain. Masing-masing perlengkapan memberikan
suatu nilai yang berarti baginya. Tentara tersebut akan memilih perlengkapan
apa saja yang akan dimasukkan ke dalam ransel tanpa melanggar kapasitas volume
tetapi jumlahan nilai yang diberikan maksimum.
Masalah knapsack merupakan masalah pemrograman bilangan bulat yang
sederhana, tetapi mempunyai aplikasi yang cukup banyak dalam bidang industri.
Contohnya adalah cargo loading, cutting
stock, pemilihan proyek (project selection),dan budget control.
Keluarga masalah knapsack menghendaki subset item yang memaksimalkan
keuntungan tanpa melanggar kapasitas knapsack. Menurut Pisinger (1995) jenis
masalah knapsack dibedakan menurut distribusi item dan knapsack, yaitu:
- Masalah knapsack baku atau knapsack 0-1 (MKB)
- Masalah knapsack terbatas (Bounded Knapsack Problem)
- Masalah knapsack pemilihan ganda (Multiple choice Knapsack Problem)
- Masalah knapsack ganda (Multiple Knapsack Problem)
Sumber:
maukar.staff.gunadarma.ac.id/Downloads/files/46049/Program+Dinamis.ppt
eprints.umpo.ac.id/312/1/ARTIKEL.pdf
stta.ac.id/data_lp3m/Jurnal%20Yuli%20TF%20STTA%20Final.doc
