Scribd
Unggah
12 tayangan12 halaman

Pemrograman Linier Bilangan Bulat

Dokumen ini membahas tentang Integer Linear Programming (ILP), yang merupakan bentuk khusus dari pemrograman linier di mana variabel harus berupa bilangan bulat. Contoh aplikasi ILP termasuk penghitungan jumlah produk, karyawan, dan kendaraan yang tidak dapat berupa pecahan. Algoritma untuk menyelesaikan ILP termasuk Branch and Bound, Cutting Planes, dan Branch and Cut, dengan penekanan pada pemahaman grafis dari solusi optimal.

Diunggah oleh

Gusty Aan
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PDF, TXT atau baca online di Scribd
12 tayangan12 halaman

Pemrograman Linier Bilangan Bulat

Dokumen ini membahas tentang Integer Linear Programming (ILP), yang merupakan bentuk khusus dari pemrograman linier di mana variabel harus berupa bilangan bulat. Contoh aplikasi ILP termasuk penghitungan jumlah produk, karyawan, dan kendaraan yang tidak dapat berupa pecahan. Algoritma untuk menyelesaikan ILP termasuk Branch and Bound, Cutting Planes, dan Branch and Cut, dengan penekanan pada pemahaman grafis dari solusi optimal.

Diunggah oleh

Gusty Aan
Hak Cipta
© All Rights Reserved
Kami menangani hak cipta konten dengan serius. Jika Anda merasa konten ini milik Anda, ajukan klaim di sini.
Format Tersedia
Unduh sebagai PDF, TXT atau baca online di Scribd

Integer Linear Programming

Review
• Bentuk umum
Objective Function
Constrains s.t.

• Variable yang dicari dalam definisi di atas ialah


• Bagaimana bila variable harus bilangan bulat?
Integer LP
Variable terkadang harus bilangan bulat (integer), contohnya:
• Jumlah produk yang diproduksi → tidak bisa setengah barang
(misalnya 2,5 kursi).
• Jumlah orang/karyawan yang dialokasikan → tidak bisa 1,7 orang.
• Jumlah truk/pesawat yang digunakan → tidak bisa 3,2 truk.
Solusi
Algoritma khusus:
•Branch and Bound
•Cutting Planes
•Branch and Cut

Akan tetapi, untuk memahami terlebih dahulu, pada paparan kali ini
akan dibahas secara grafis.
Contoh
5

0 1 2 3 4 5
Contoh
5

4
Geser garis ---
hingga memenuhi
3 daerah feasible

2
Feasible
Region
1

0 1 2 3 4 5
Contoh
5

4 Optimal Solution
X1=1.59
X2=2.73
3
Z=28.65

0 1 2 3 4 5
Contoh
5

Misalnya x1 adalah jumlah orang dan x2 adalah jumlah laptop,


feasible solutionnya berubah; bukan area, tetapi kumpulan titik.
1
Apakah optimal solutionnya dibulatkan ke bawah adalah
solusi dari permasalahan ini?

0 1 2 3 4 5
Contoh
5

Pembulatan ke bawah (rounding down)


x1=1, x2=2, Z=20 → Bukan optimal value. Bisa dicoba dengan 1
menggeser garis dash ---

0 1 2 3 4 5
Contoh
Optimal Solution
5 X1= 0
X2= 4
Z=28
4

Pembulatan ke bawah (rounding down)


x1=1, x2=2, Z=20 → Bukan optimal value. Bisa dicoba dengan 1
menggeser garis dash ---

0 1 2 3 4 5
Contoh
5

2
Di kasus maximization,
Optimal value of integer problem <= Optimal value of regular LP
1
Di kasus minimization,
Optimal value of integer problem >= Optimal value of regular LP
0 1 2 3 4 5
Tugas

x1 dan x2 harus bilangan bulat. Berapakah titik dan nilai optimalnya?


Boleh menggambar menggunakan ppt, excel, matlab, atau manual (penggaris).

Anda mungkin juga menyukai