Menurut Ayu (1996), metode-metode penyelesaian akhir dalam persoalan transportasi adalah sebagai berikut:
1. Metode Stepping Stone
Pengujian ini didasarkan pada hasil perhitungan perubahan biaya dari setiap siklus yang intinya adalah untuk mencoba mengalokasikan pada kotak kosong (variabel non basis).
2. Metode Modified Distribution (MODI)
Pada pengujian Modi dilakukan penentuan nilai Ui & Vi pada solusi yang layak diperoleh, kemudian dilakukan perhitungan nilai (Cij–Ui–Vi)
Selasa, 29 Desember 2009
Metode Penyelesaian Awal dalam Masalah Transportasi
1. Metode pojok kiri atas (northwest corner)
Metode ini didasarkan aturan pengalokasian normatif dari persediaan dan kebutuhan sumber dalam suatu matriks biaya transportasi tanpa memperhitungkan besaran-besaran ekonomis. Aturan normatif tersebut yakni membebani semaksimal mungkin sampai batas maksimum persediaan maksimum persediaan atau kebutuhan (mana yang tercapai lebih dahulu) pada matrik alokasi pada ujung kiri atas terus menuju ke kanan bawah sedemikian sehingga seluruh kebutuhan akan sumber dapat terpenuhi.
2. Metode ongkos terkecil (least cost)
Berbeda dengan metode pojok kiri atas yang tidak mempertimbangkan faktor ongkos, metode ongkos terkecil memberikan prioritas pengalokasian pada sel yang mempunyai ongkos terkecil.
3. Metode pendekatan Vogel (VAM)
Metode ini merupakan metode terbaik dari kedua metode di atas. Langkah pengerjaan metode VAM adalah dengan menentukan penalti yaitu selisih dua ongkos terkecil dari setiap kolom dan baris. Pilih penalti terbesar, alokasikan sebanyak mungkin kapasitas sumber atau kebutuhan pada sel yang mempunyai ongkos terkecil. Tentukan penalti lagi untuk setiap baris dan kolom sedangkan untuk baris dan kolom dengan kebutuhan dan kapasitas sumber yang mempunyai nilai nol tidak dilakukan perhitungan penalti.
4. Metode aproksimasi Russel (RAM)
Untuk setiap baris ditentukan nilai ui yang merupakan biaya tertinggi pada baris tersebut. Sedangkan untuk setiap kolom ditentukan nilai vj yang merupakan biaya tertinggi pada kolom tersebut. Untuk setiap kotak variabel Xij dilakukan perhitungan nilai ∆ij = cij – ui – vj. Pengalokasian dilakukan pada kotak variabel dengan nilai ∆ij negatif terbesar.
Metode ini didasarkan aturan pengalokasian normatif dari persediaan dan kebutuhan sumber dalam suatu matriks biaya transportasi tanpa memperhitungkan besaran-besaran ekonomis. Aturan normatif tersebut yakni membebani semaksimal mungkin sampai batas maksimum persediaan maksimum persediaan atau kebutuhan (mana yang tercapai lebih dahulu) pada matrik alokasi pada ujung kiri atas terus menuju ke kanan bawah sedemikian sehingga seluruh kebutuhan akan sumber dapat terpenuhi.
2. Metode ongkos terkecil (least cost)
Berbeda dengan metode pojok kiri atas yang tidak mempertimbangkan faktor ongkos, metode ongkos terkecil memberikan prioritas pengalokasian pada sel yang mempunyai ongkos terkecil.
3. Metode pendekatan Vogel (VAM)
Metode ini merupakan metode terbaik dari kedua metode di atas. Langkah pengerjaan metode VAM adalah dengan menentukan penalti yaitu selisih dua ongkos terkecil dari setiap kolom dan baris. Pilih penalti terbesar, alokasikan sebanyak mungkin kapasitas sumber atau kebutuhan pada sel yang mempunyai ongkos terkecil. Tentukan penalti lagi untuk setiap baris dan kolom sedangkan untuk baris dan kolom dengan kebutuhan dan kapasitas sumber yang mempunyai nilai nol tidak dilakukan perhitungan penalti.
4. Metode aproksimasi Russel (RAM)
Untuk setiap baris ditentukan nilai ui yang merupakan biaya tertinggi pada baris tersebut. Sedangkan untuk setiap kolom ditentukan nilai vj yang merupakan biaya tertinggi pada kolom tersebut. Untuk setiap kotak variabel Xij dilakukan perhitungan nilai ∆ij = cij – ui – vj. Pengalokasian dilakukan pada kotak variabel dengan nilai ∆ij negatif terbesar.
TRANSPORTASI
Masalah transportasi adalah masalah pemrograman linier khusu yang dapat dikatakan paling penting. Dasar masalah transportasi ini pertama kali dicetuskan oleh Hitchock dan kemudian dijelaskan dengan lebih mendetail oleh Koopmans. Pendekatan pertama diberikan oleh Kantrovich. Formulasikan pemrograman linier dan metode sistemtisnya pertama kali diberikan oleh Dantzig (Ayu, 1996).
Definisi Transportasi
Menurut Ayu (1996), transportasi adalah masalah pendistribusian barang dari beberapa kelompok tempat penyediaan yang disebut dengan sumber ke beberapa kelompok tempat penerimaan yang disebut dengan tujuan, dalam suatu cara tertentu yang dapat meminimumkan total biaya distribusi.
Jadi, secara umum sumber I (i= 1, 2, ..., m) mempunyai penawaran sejumlah si unit untuk didistribusikan ke sejumlah tempat tujuan, dan tujuan j (j = 1, 2, ..., n) mempunyai permintaan sejumlah dj unit yang dapat diterima dari sejumlah sumber. Asumsi dasarnya adalah biaya distribusi dari sumber I ke tujuan j berbanding lurus dengan jumlah barang yang didistribusikan, dimana cij adalah biaya distribusi per-unit.
Menurut Biegel (1952), Transportasi adalah suatu pengaturan yang berhubungan dengan pelaksanaan pendistribusian yang lebih ekonomis dari produk-produk (barang-barang) yang dihasilkan di beberapa pabrik dan keperluan untuk penempatannya dalam gudang yang lokasinya berbeda. Dengan kata lain, transportasi mempunyai persoalan untuk menetapkan suatu rencana pengiriman bagi distribusi produk antara pabrik dengan gudang dalam satu pabrik terpadu.
Definisi Transportasi
Menurut Ayu (1996), transportasi adalah masalah pendistribusian barang dari beberapa kelompok tempat penyediaan yang disebut dengan sumber ke beberapa kelompok tempat penerimaan yang disebut dengan tujuan, dalam suatu cara tertentu yang dapat meminimumkan total biaya distribusi.
Jadi, secara umum sumber I (i= 1, 2, ..., m) mempunyai penawaran sejumlah si unit untuk didistribusikan ke sejumlah tempat tujuan, dan tujuan j (j = 1, 2, ..., n) mempunyai permintaan sejumlah dj unit yang dapat diterima dari sejumlah sumber. Asumsi dasarnya adalah biaya distribusi dari sumber I ke tujuan j berbanding lurus dengan jumlah barang yang didistribusikan, dimana cij adalah biaya distribusi per-unit.
Menurut Biegel (1952), Transportasi adalah suatu pengaturan yang berhubungan dengan pelaksanaan pendistribusian yang lebih ekonomis dari produk-produk (barang-barang) yang dihasilkan di beberapa pabrik dan keperluan untuk penempatannya dalam gudang yang lokasinya berbeda. Dengan kata lain, transportasi mempunyai persoalan untuk menetapkan suatu rencana pengiriman bagi distribusi produk antara pabrik dengan gudang dalam satu pabrik terpadu.
metode-metode dalam program linier
Metode Grafik
Tujuan dari metode grafik adalah untuk memberikan dasar-dasar dari konsep yang digunakan dalam teknik simpleks. Prosedur umumnya adalah untuk mengubah suatu situasi deskriptif ke dalam bentuk masalah pemrograman linier dengan menentukan variabelnya, konstanta-konstantanya, fungsi obyektifnya dan batas-batasannya (kendala-kendala), sehingga masalah tersebut dapat disajikan dalam bentuk grafik dan diinterpretasikan solusinya. Untuk menggunakan metode grafik, dilalui tahapan-tahapan berikut:
1. Identifikasi variabel keputusan.
2. Identifikasi fungsi obyektif.
3. Identifikasi kendala-kendala.
4. Menggambarkan bentuk grafik dari semua kendala.
5. Identifikasi daerah solusi yang layak pada grafik.
6. Menggambarkan bentuk grafik dari fungsi obyektif dan menentukan titik yang
memberikan nilai obyektif optimal pada daerah solusi yang layak.
7. Mengartikan solusi yang diperoleh.
Metode Simpleks
Metode grafik tersebut hanya dapat digunakan untuk menyelesaikan masalah pemrograman linier yang hanya mempunyai dua variabel, karena untuk pemrograman linier dengan variabel lebih dari dua akan sulit untuk menggambarkan bentuk grafiknya. Untuk mengatasi kesulitan ini, maka pada tahun 1947 diperkenalkan suatu metode yang dapat digunakan untuk menyelesaikan masalah pemrograman linier oleh Geore B. Dantzig yang dinamakan metode simpleks.
Algoritma simpleks ini adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah pemrograman linier yang didasarkan pada proses iterasi. Jadi pada prinsipnya prosedur ini diawali dengan penentuan suatu solusi awal yang secara terus-menerus diperbaiki hingga diperoleh solusi yang optimal.
Langkah-langkah dalam algoritma simpleks untuk mecari solusi optimal dari suatu masalah perograman linier adalah sebagai berikut:
1. Menentukan kolom kerja.
Kolom kerja ditentukan berdasarkan nilai yang paling negatif dari nilai-nilai
yang berada pada baris fungsi obyektif (Z) pada tabel simpleks. Variabel yang
berada pada kolom kerja ini akan menjadi entering variabel menggantikan salah
satu variabel dasar sebelumnya. Variabel dasar mana yang akan digantikan oleh
entering varibel ini ditentukan pada langkah kedua.
2. Membuat nialai perbandingan antara nilai kanan (NK) dengan nilai pada kolom
kerja dari setiap baris, kecuali baris fungsi obyektif.
3. Menrubah nilai pada baris pivot dengan cara membagi setia elemen dari baris
pivot ini dengan nilai pivot elemen. Nilai pivot elemen ini perpotongan antara
baris pivot dengan kolom kerja.
4. Merubah variabel dasar, yang berarti entering variabel masuk menggantikan
leaving variabel.
5. Merubah nilai pada baris selain baris pivot.
6. Memeriksa apakah masih terdapat nilai negatif pada baris fungsi obyektif. Bila
masih ada nilai negatif pada baris tersebut, berarti tabel belum optimal,
sehingga perlu diadakan kembali langkah-langkah penyelesaian di atas hingga
diperoleh solusi yang optimal.
Tujuan dari metode grafik adalah untuk memberikan dasar-dasar dari konsep yang digunakan dalam teknik simpleks. Prosedur umumnya adalah untuk mengubah suatu situasi deskriptif ke dalam bentuk masalah pemrograman linier dengan menentukan variabelnya, konstanta-konstantanya, fungsi obyektifnya dan batas-batasannya (kendala-kendala), sehingga masalah tersebut dapat disajikan dalam bentuk grafik dan diinterpretasikan solusinya. Untuk menggunakan metode grafik, dilalui tahapan-tahapan berikut:
1. Identifikasi variabel keputusan.
2. Identifikasi fungsi obyektif.
3. Identifikasi kendala-kendala.
4. Menggambarkan bentuk grafik dari semua kendala.
5. Identifikasi daerah solusi yang layak pada grafik.
6. Menggambarkan bentuk grafik dari fungsi obyektif dan menentukan titik yang
memberikan nilai obyektif optimal pada daerah solusi yang layak.
7. Mengartikan solusi yang diperoleh.
Metode Simpleks
Metode grafik tersebut hanya dapat digunakan untuk menyelesaikan masalah pemrograman linier yang hanya mempunyai dua variabel, karena untuk pemrograman linier dengan variabel lebih dari dua akan sulit untuk menggambarkan bentuk grafiknya. Untuk mengatasi kesulitan ini, maka pada tahun 1947 diperkenalkan suatu metode yang dapat digunakan untuk menyelesaikan masalah pemrograman linier oleh Geore B. Dantzig yang dinamakan metode simpleks.
Algoritma simpleks ini adalah suatu prosedur matematis untuk mencari solusi optimal dari suatu masalah pemrograman linier yang didasarkan pada proses iterasi. Jadi pada prinsipnya prosedur ini diawali dengan penentuan suatu solusi awal yang secara terus-menerus diperbaiki hingga diperoleh solusi yang optimal.
Langkah-langkah dalam algoritma simpleks untuk mecari solusi optimal dari suatu masalah perograman linier adalah sebagai berikut:
1. Menentukan kolom kerja.
Kolom kerja ditentukan berdasarkan nilai yang paling negatif dari nilai-nilai
yang berada pada baris fungsi obyektif (Z) pada tabel simpleks. Variabel yang
berada pada kolom kerja ini akan menjadi entering variabel menggantikan salah
satu variabel dasar sebelumnya. Variabel dasar mana yang akan digantikan oleh
entering varibel ini ditentukan pada langkah kedua.
2. Membuat nialai perbandingan antara nilai kanan (NK) dengan nilai pada kolom
kerja dari setiap baris, kecuali baris fungsi obyektif.
3. Menrubah nilai pada baris pivot dengan cara membagi setia elemen dari baris
pivot ini dengan nilai pivot elemen. Nilai pivot elemen ini perpotongan antara
baris pivot dengan kolom kerja.
4. Merubah variabel dasar, yang berarti entering variabel masuk menggantikan
leaving variabel.
5. Merubah nilai pada baris selain baris pivot.
6. Memeriksa apakah masih terdapat nilai negatif pada baris fungsi obyektif. Bila
masih ada nilai negatif pada baris tersebut, berarti tabel belum optimal,
sehingga perlu diadakan kembali langkah-langkah penyelesaian di atas hingga
diperoleh solusi yang optimal.
Sejarah dan Definisi Program Linier
Sejarah Program Linier
Penggunaan operasional riset berawal pada perang dunia II. Pada saat itu angkatan perang Inggris membentuk suatu team untuk mempelajari persoalan-persoalan strategi dan taktik sehubungan dengan serangan-serangan pada saat perang dunia II. Tujuannya adalah mengefektifkan sumber-sumber terbatas kemiliteran, yang akhirnya penelitian tentang kemiliteran disebut dengan “penelitian operasional masalah kemiliteran”. Keberhasilan angkatan perang Inggris kemudian diikuti oleh angkatan perang Amerika untuk aktivitas yang sama. Keberhasilan yang dicapai Amerika adalah dalam mensuplai barang-barang eperluan perang, menentukan pola-pola dasar penerbangan yang lebih efisien, serta menentukan pola-pola jaringan bagi operasi-operasi alat-alat elektronik. Setelah berakhirnya perang dunia II, keberhasilan angkatan perang Inggris dan angkatan perang Amerika ilmu operasional riset kemudian berkembang ke orang-orang industri di Amerika, dan sampai sekarangtelah digunakan hamper seluruh egiatan di dunia (Hari, 2004).
Definisi Program Lnier
Program linier adalah merumuskan masalah dengan menggunakan sejumlah informasi yang tersedia kemudian menerjemahkan masalah tersebut dalam bentuk model matematika. Sifat linier mempunyai arti bahwa seluruh fiungsi dalam model ini merupakan fungsi yang linier (Hari, 2004).
Program linier (linear programming) adalah merupakan metode matematik dalam mengalokasikan sumber daya yang langka atau terbatas untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya (Taha, 1993). Sumber daya tersebut dapat berupa sumber daya fisik seperti uang, tenaga ahli, material (bahan dan mesin) ataupun bukan fisik.
Menurut Ayu (1996), pemrograman linier berasal dari kata pemrograman dan linier. Pemrograman disini mempunyai arti kata perencanaan, dan linier ini berarti bahwa fungsi-fungsi yang digunakan merupakan fungsi linier. Secara umum arti dari pemrograman linier adalah suatu teknik perencanaan yang bersifat analisis yang analisis-analisisnya memakai model matematika, dengan tujuan menemukan beberapa kombinasi alternatif pemecahan masalah kemudian dipilih yang terbaik di antaranya dalam rangka menyusun strategi dan langkah-langkah kebijaksanaan lebih lanjut tentang alokasi sumber daya dan dana yang terbatas guna mencapai tujuan dan sasaran yang di inginkan secara optimal.
Penggunaan operasional riset berawal pada perang dunia II. Pada saat itu angkatan perang Inggris membentuk suatu team untuk mempelajari persoalan-persoalan strategi dan taktik sehubungan dengan serangan-serangan pada saat perang dunia II. Tujuannya adalah mengefektifkan sumber-sumber terbatas kemiliteran, yang akhirnya penelitian tentang kemiliteran disebut dengan “penelitian operasional masalah kemiliteran”. Keberhasilan angkatan perang Inggris kemudian diikuti oleh angkatan perang Amerika untuk aktivitas yang sama. Keberhasilan yang dicapai Amerika adalah dalam mensuplai barang-barang eperluan perang, menentukan pola-pola dasar penerbangan yang lebih efisien, serta menentukan pola-pola jaringan bagi operasi-operasi alat-alat elektronik. Setelah berakhirnya perang dunia II, keberhasilan angkatan perang Inggris dan angkatan perang Amerika ilmu operasional riset kemudian berkembang ke orang-orang industri di Amerika, dan sampai sekarangtelah digunakan hamper seluruh egiatan di dunia (Hari, 2004).
Definisi Program Lnier
Program linier adalah merumuskan masalah dengan menggunakan sejumlah informasi yang tersedia kemudian menerjemahkan masalah tersebut dalam bentuk model matematika. Sifat linier mempunyai arti bahwa seluruh fiungsi dalam model ini merupakan fungsi yang linier (Hari, 2004).
Program linier (linear programming) adalah merupakan metode matematik dalam mengalokasikan sumber daya yang langka atau terbatas untuk mencapai tujuan tunggal seperti memaksimumkan keuntungan atau meminimumkan biaya (Taha, 1993). Sumber daya tersebut dapat berupa sumber daya fisik seperti uang, tenaga ahli, material (bahan dan mesin) ataupun bukan fisik.
Menurut Ayu (1996), pemrograman linier berasal dari kata pemrograman dan linier. Pemrograman disini mempunyai arti kata perencanaan, dan linier ini berarti bahwa fungsi-fungsi yang digunakan merupakan fungsi linier. Secara umum arti dari pemrograman linier adalah suatu teknik perencanaan yang bersifat analisis yang analisis-analisisnya memakai model matematika, dengan tujuan menemukan beberapa kombinasi alternatif pemecahan masalah kemudian dipilih yang terbaik di antaranya dalam rangka menyusun strategi dan langkah-langkah kebijaksanaan lebih lanjut tentang alokasi sumber daya dan dana yang terbatas guna mencapai tujuan dan sasaran yang di inginkan secara optimal.
Selasa, 08 Desember 2009
CPM dan PERT
Ketika bekerja pada proyek yang melibatkan sumber daya berharga, setiap manajer senilai garam mereka mencoba memanfaatkan sumber daya tersebut secara optimal untuk sedapat mungkin yang terbaik, sementara, pada saat yang sama, berusaha untuk menyelesaikan proyek sesuai jadwal. Pemikir dan inovator di seluruh dunia telah menempatkan dalam banyak upaya untuk keluar dengan alat yang akan membuat pekerjaan mereka lebih sederhana dan menyenangkan, bukan terburu-buru terus-menerus terhadap tenggat waktu dan tidak efisien pemanfaatan sumber daya yang satu menemukan mereka alami.
The PERT chart merupakan salah satu alat tersebut. Ada ribuan kontraktor dan lembaga yang manajer proyek harus menangani untuk pengembangan Missile Polaris. Proyek-proyek ukuran raksasa tersebut tidak memiliki preseden dalam sejarah manusia. Tidak ada pengalaman manajemen proyek sebelumnya tersedia bagi para manajer untuk menangani mereka. Ingenuity, ditambah dengan tekad untuk sukses melawan rintangan tersebut menimbulkan kopling alat manajemen - semua menggunakan kertas dan pensil rendah hati.
Sebuah PERT Chart adalah alat visual manajemen proyek yang digunakan untuk jadwal, mengatur, dan mengkoordinasikan kegiatan proyek mereka. Dalam setiap proyek, daftar tugas dipecah (cf: Work Breakdown Structure), untuk menyelesaikan dalam urutan tertentu, yang mendefinisikan proyek. Sumber daya yang dibutuhkan untuk menyelesaikan setiap pekerjaan - dalam hal uang, materi, dan tenaga kerja - terdaftar.
Salah satu keuntungan yang terbaik untuk menciptakan sebuah bagan PERT selama perencanaan proyek adalah memberikan wawasan pada Critical Path. Dalam jaringan kami diagram di atas, jalur kritis merupakan jalur terpanjang melintasi dari mulai Node ke Node berakhir, dalam bentuk kalender total waktu yang dibutuhkan untuk mencapai masing-masing Node menengah. Semua kegiatan di Critical Path ini harus diselesaikan pada jadwal proyek selesai tepat waktu. Dilihat dalam terang ini, setiap aktivitas dalam Critical Path adalah sebuah kegiatan penting, diberi perhatian penuh. Sumber dari tugas-tugas yang tidak kritis dapat dialokasikan kembali untuk membantu Critical Path elemen harus permasalahan timbul, atau kondisi tak terduga pasti terjadi. Proses mengelola jalur kritis adalah disebut sebagai Critical Path Manajemen, atau CPM.
sumber teori http://translate.googleusercontent.com/translate_c?hl=id&langpair=en|id&u=http://www.envisionsoftware.com/articles/Pert_Chart.html&rurl=translate.google.co.id&twu=1&usg=ALkJrhhtig6WMQZkC1vD_B4GsYOyoaT3Ow
The PERT chart merupakan salah satu alat tersebut. Ada ribuan kontraktor dan lembaga yang manajer proyek harus menangani untuk pengembangan Missile Polaris. Proyek-proyek ukuran raksasa tersebut tidak memiliki preseden dalam sejarah manusia. Tidak ada pengalaman manajemen proyek sebelumnya tersedia bagi para manajer untuk menangani mereka. Ingenuity, ditambah dengan tekad untuk sukses melawan rintangan tersebut menimbulkan kopling alat manajemen - semua menggunakan kertas dan pensil rendah hati.
Sebuah PERT Chart adalah alat visual manajemen proyek yang digunakan untuk jadwal, mengatur, dan mengkoordinasikan kegiatan proyek mereka. Dalam setiap proyek, daftar tugas dipecah (cf: Work Breakdown Structure), untuk menyelesaikan dalam urutan tertentu, yang mendefinisikan proyek. Sumber daya yang dibutuhkan untuk menyelesaikan setiap pekerjaan - dalam hal uang, materi, dan tenaga kerja - terdaftar.
Critical Path Management (CPM)
Salah satu keuntungan yang terbaik untuk menciptakan sebuah bagan PERT selama perencanaan proyek adalah memberikan wawasan pada Critical Path. Dalam jaringan kami diagram di atas, jalur kritis merupakan jalur terpanjang melintasi dari mulai Node ke Node berakhir, dalam bentuk kalender total waktu yang dibutuhkan untuk mencapai masing-masing Node menengah. Semua kegiatan di Critical Path ini harus diselesaikan pada jadwal proyek selesai tepat waktu. Dilihat dalam terang ini, setiap aktivitas dalam Critical Path adalah sebuah kegiatan penting, diberi perhatian penuh. Sumber dari tugas-tugas yang tidak kritis dapat dialokasikan kembali untuk membantu Critical Path elemen harus permasalahan timbul, atau kondisi tak terduga pasti terjadi. Proses mengelola jalur kritis adalah disebut sebagai Critical Path Manajemen, atau CPM.
sumber teori http://translate.googleusercontent.com/translate_c?hl=id&langpair=en|id&u=http://www.envisionsoftware.com/articles/Pert_Chart.html&rurl=translate.google.co.id&twu=1&usg=ALkJrhhtig6WMQZkC1vD_B4GsYOyoaT3Ow
Sabtu, 05 Desember 2009
PEMROGRAMAN DINAMIS
Pemorograman dinamis adalah metode pemecahan masalah dengan cara menguraikan solusi menjadi sekumpulan langkah (step) atau tahapan (stage) sedemikian sehingga solusi dari persoalan dapat dipandang dari serangkaian keputusan yang saling berkaitan.
Prinsip Optimalitas
Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas. Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal. Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.
Pada metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.
1. Karakteristik Persoalan Program Dinamis
Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.
6 Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.
7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.
8. Prinsip optimalitas berlaku pada persoalan tersebut.
Prinsip Optimalitas
Pada program dinamis, rangkaian keputusan yang optimal dibuat dengan menggunakan Prinsip Optimalitas. Prinsip Optimalitas: jika solusi total optimal, maka bagian solusi sampai tahap ke-k juga optimal. Prinsip optimalitas berarti bahwa jika kita bekerja dari tahap k ke tahap k + 1, kita dapat menggunakan hasil optimal dari tahap k tanpa harus kembali ke tahap awal. Dengan prinsip optimalitas ini dijamin bahwa pengambilan keputusan pada suatu tahap adalah keputusan yang benar untuk tahap-tahap selanjutnya.
Pada metode greedy hanya satu rangkaian keputusan yang pernah dihasilkan, sedangkan pada metode program dinamis lebih dari satu rangkaian keputusan. Hanya rangkaian keputusan yang memenuhi prinsip optimalitas yang akan dihasilkan.
1. Karakteristik Persoalan Program Dinamis
Persoalan dapat dibagi menjadi beberapa tahap (stage), yang pada setiap tahap hanya diambil satu keputusan.
2. Masing-masing tahap terdiri dari sejumlah status (state) yang berhubungan dengan tahap tersebut. Secara umum, status merupakan bermacam kemungkinan masukan yang ada pada tahap tersebut.
3. Hasil dari keputusan yang diambil pada setiap tahap ditransformasikan dari status yang bersangkutan ke status berikutnya pada tahap berikutnya.
4. Ongkos (cost) pada suatu tahap meningkat secara teratur (steadily) dengan bertambahnya jumlah tahapan.
5. Ongkos pada suatu tahap bergantung pada ongkos tahap-tahap yang sudah berjalan dan ongkos pada tahap tersebut.
6 Keputusan terbaik pada suatu tahap bersifat independen terhadap keputusan yang dilakukan pada tahap sebelumnya.
7. Adanya hubungan rekursif yang mengidentifikasikan keputusan terbaik untuk setiap status pada tahap k memberikan keputusan terbaik untuk setiap status pada tahap k + 1.
8. Prinsip optimalitas berlaku pada persoalan tersebut.
Langganan:
Postingan (Atom)