Penyusun: Ade Vicidian Sugiharto Putra (5107100615) Pembimbing I: Yudhi Purwananto, S.Kom, M.Kom. Pembimbing II: Victor Hariadi, S.Si, M.Kom.
PENDAHULUAN
Permasalahan pengalokasian sumber-sumber yang terbatas diantara beberapa aktivitas yang bersaing yang harus diselesaikan dengan cara yang terbaik (optimal) yang mungkin untuk dilakukan Untuk menyelesaikan permasalahan tersebut digunakanlah linier programming (LP) Jika permasalahan yang seluruh variabelnya adalah integer sehingga harus digunakan integer linier programming(ILP) untuk menyelesaikannya Kemudian dicari solusi optimal yang lain atau solusi alternatifnya, salah satu cara yang digunakan adalah menggunakan model general integer cut
Untuk membuat aplikasi solusi alternatif pada general ILP yang berfungsi menemukan semua solusi alternatif yang mungkin dari sebuah general ILP Mengusulkan general integer cut untuk meniadakan solusi sebelumnya dan merepresentasikan sebuah algoritma untuk mengidentifikasi semua solusi optimal dari ILP berdasarkan model yang dikembangkan oleh Tsai, Lin dan Hu
Bagaimana mendapatkan general integer cut Bagaimana mendapatkan himpunan solusi alternatif yang mungkin dari sebuah permasalahan general ILP
Implementasi untuk aplikasi menggunakan LINGO 8.0 Permasalahan yang akan digunakan pada uji coba merupakan permasalahan yang sudah terepresentasi dalam bentuk model matematis
Permasalahan yang dibahas hanya permasalahan ILP Solusi alternatif optimal ditulis selama nilai objektif yang dihasilkan setelah menambahkan fungsi kendala baru (general integer cut baru) harus sama dengan nilai objektif awal yaitu sebelum menambahkan fungsi kendala baru
TINJAUAN PUSTAKA
Dibutuhkan keputusan/variabel yang harus dilakukan dalam bentuk bilangan bulat Salah satu cara yang dapat digunakan untuk menyelesaikan permasalahan ILP adalah dengan menggunakan model branch and bound
Dibutuhkan variebel keputusan tertentu yang harus dilakukan dalam bentuk bilangan bulat, jadi tidak semua variabelnya adalah bilangan bulat
PERANCANGAN DAN IMPLEMENTASI
General Integer Cut • dapat digunakan untuk menemukan semua solusi alternatif dari masalah ILP yang berisi variabel biner maupun non- biner • dengan cara menambahkan sebuah general integer cut pada
model asli untuk membuat model sebelumnya menjadi tidak layak (infeasible) • sehingga menghasilkan model baru dengan nilai objektif yang
sama
Model 1 (teknik absolut)
Model 2-1 (teknik IP konvensional)
• Model diatas untuk permasalahan ILP yang mengandung
variabel biner
Model 2-2 (teknik IP konvensional)
• Model diatas untuk permasalahan ILP yang hanya mengandung
variabel non-biner
Langkah 1 • Menentukan sebuah solusi optimal dari permasalahan ILP
Langkah 2 • Temukan semua solusi alternatif optimal untuk f(X)=Q • Misalkan j=j+1, tambahkan fungsi kendala:
• (dapat diganti dengan model (2) sehingga dapat diselesaikan
menggunakan teknik IP yang konvensional) • Ulangi terus langkah 2 selama kondisi f(X)=Q (nilai objektif yang baru dihasilkan masih sama dengan nilai objektif awal) • Jika kondisi f(X)≠Q (nilai objektif baru tidak sama dengan nilai objektif awal), maka solusi yang digunakan hanya solusi-solusi yang sebelumnya dan langsung menuju langkah 3
Langkah 3 • Yang harus dilakukan pada langkah 3 ini adalah menulis seluruh solusi optimal
Alur Proses
Data Permasalahan 1
Data Permasalahan 2
Implementasi input dari data Permasalahan 1
Output implementasi dari data permasalahan 1 Nilai objektif = 76
• X1 = 23, • X2 = 53, • X3 = 0, • Y1 = 1, • Y2 = 1
Implementasi general integer cut model (1)
Implementasi general integer cut model (2)
UJICOBA DAN ANALISIS
Menggunakan 2 skenario, skenario 1 untuk data permasalahan 1 dan skenario 2 untuk data permasalahan 2 1 Skenario menggunakan 3 ujicoba yaitu: • Menggunakan model (1) teknik absolut • Menggunakan model (2) teknik konvensional dengan M=100 • Menggunakan model (2) teknik konvensional dengan
M=100000
Skenario 1 Ujicoba 1 Hasil ujicoba sebagai berikut :
• Dari data permasalahan 1 dihasilkan 6 solusi optimal dengan
nilai objektif 76
Skenario 1 Ujicoba 2 Hasil ujicoba sebagai berikut :
• Dari data permasalahan 1 dihasilkan 5 solusi alternatif dengan
nilai objektif 76
Skenario 1 Ujicoba 3 Hasil ujicoba sebagai berikut :
• Dari data permasalahan 1 dihasilkan 5 solusi alternatif dengan
nilai objektif 76
Analisis skenario 1 • Dengan menggunakan model general integer cut dapat dihasilkan suatu hasil optimal alternatif selain hasil optimal awal pada suatu permasalahan ILP yang mengandung variabel integer dan variabel biner • Hasil ujicoba 1 lebih baik dari hasil ujicoba 2 dan 3 karena
menghasilkan lebih banyak solusi alternatif • Hasil ujicoba 2 dan ujicoba 3 menunjukkan bahwa dengan
dengan dilakukannya penambahan general integer cut dapat menghasilkan jumlah solusi alternatif yang sama namun berbeda urutan solusi optimalnya bergantung pada besarnya M yang diinputkan
Skenario 2 Ujicoba 1 Hasil ujicoba sebagai berikut :
• Dari data permasalahan 2 dihasilkan 2 solusi alternatif dengan
nilai objektif 4516
Skenario 2 Ujicoba 2 Hasil ujicoba sebagai berikut :
• Dari data permasalahan 2 dihasilkan 2 solusi alternatif dengan
nilai objektif 4516
Skenario 2 Ujicoba 3 Hasil ujicoba sebagai berikut :
• Dari data permasalahan 2 dihasilkan 2 solusi alternatif dengan
nilai objektif 4516
Analisis skenario 2 • Dengan menggunakan model general integer cut dapat dihasilkan suatu hasil optimal alternatif selain hasil optimal awal pada suatu permasalahan ILP yang hanya mengandung variabel non-biner • Seluruh ujicoba menghasilkan 2 solusi alternatif dan nilai
objektif yang sama • Perbedaan besarnya M yang diinputkan tidak terlihat pada
ujicoba 2 dan 3 dikarenakan data permasalahan tersebut jika diselesaikan menggunakan general integer cut hanya menghasilkan dua buah solusi optimal
KESIMPULAN DAN SARAN
Model general integer cut yang dikembangkan Tsai, Lin dan Hu dapat digunakan untuk mencari solusi alternatif lain diluar solusi optimal awal, dimana general integer cut tersebut didapatkan dengan cara memformulasikan ulang solusi optimal yang didapat sebelumnya sehingga menghasilkan solusi alternatif baru dengan menghilangkan kemungkinan kemunculan solusi yang sudah ada sebelumnya Solusi alternatif dari sebuah permasalahan ILP yang didapatkan dengan menggunakan model general integer cut haruslah solusi optimal yang memiliki nilai objektif yang sama dengan solusi optimal awal yaitu pada saat sebelum ditambahkannya fungsi kendala baru yang berupa general integer cut
Dengan menggunakan model general integer cut dapat dihasilkan suatu hasil optimal alternatif selain hasil optimal awal pada suatu permasalahan ILP yang hanya mengandung variabel non-biner maupun juga permasalahan ILP yang mengandung variabel biner Pada model general integer cut, perbedaan besarnya M yang diinputkan akan terlihat jika suatu permasalahan ILP dapat menghasilkan lebih dari 1 solusi alternatif. Karena besarnya M akan mengakibatkan perbedaan urutan solusi alternatif optimal yang ditemukan
Model general integer cut ini dapat membantu pengambil keputusan pada suatu badan atau perusahaan untuk mengkombinasikan variabel-variabel keputusan yang berbeda komposisinya yang dianggap sesuai dengan kondisi teraktual perusahaan namun tetap menghasilkan keuntungan yang sama optimalnya, hal ini dikarenakan kemampuan general integer cut dalam memberikan banyak pilihan solusi alternatif
Model general integer cut ini seharusnya dapat dikembangkan lebih lanjut karena menjadikan lebih banyak pilihan untuk mencapai keuntungan yang sama Kesulitan dalam melakukan riset yaitu kesulitan dalam menemukan contoh-contoh permasalahan ILP yang menghasilkan lebih dari satu solusi optimal dan juga sedikit sekali riset-riset tentang pencarian solusi alternatif di bidang linier programming
Mengacu pada saat terjadi kondisi keuntungan atau nilai objektif yang didapat kemungkinan menjadi lebih besar daripada sebelumnya dapat terjadi, keputusan-keputusan yang harus diambil dan metode-metode yang digunakan untuk mengambil keputusan tersebut belum dapat terjawab sehingga perlu dikembangkan lebih lanjut karena hal tersebut diluar model general integer cut yang hanya menangani permasalahan dengan nilai objektif yang sama
Terima Kasih
