9. Pemilik Consolidated Machine Shop memiliki $ 10.

000 yang tersedia untuk membeli

mesin bubut, mesin press, penggiling, atau beberapa kombinasinya. Model pemrograman
linier bilangan bulat 0–1 berikut telah dikembangkan untuk menentukan mana dari tiga mesin
(mesin bubut, pengepres, atau penggiling,) yang harus dibeli untuk memaksimalkan
keuntungan tahunan:

14. Texas Consolidated Electronics Company sedang mempertimbangkan program penelitian

dan pengembangan yang mencakup delapan proyek penelitian. Perusahaan dibatasi untuk
memulai semua proyek dengan jumlah ilmuwan manajemen yang tersedia (40) dan anggaran
yang tersedia untuk proyek R&D ($ 300.000). Selanjutnya, jika proyek 2 dipilih, proyek 5
juga harus dipilih (tetapi tidak sebaliknya). Berikut adalah kebutuhan sumber daya dan
perkiraan keuntungan untuk setiap proyek:

Dalam model pemrograman linier yang dirumuskan dan diselesaikan pada bab-bab
sebelumnya, asumsi implisit adalah bahwa solusi dapat berupa bilangan pecahan atau
bilangan real (yaitu, non-bilangan bulat). Namun, solusi non-integer tidak selalu praktis. Jika
hanya solusi bilangan bulat yang praktis atau logis, terkadang diasumsikan bahwa nilai solusi
bukan bilangan bulat dapat "dibulatkan" ke nilai bilangan bulat terdekat yang layak. Metode
ini tidak akan menimbulkan banyak kekhawatiran jika, misalnya, paku dibulatkan menjadi
8.000 paku karena paku hanya berharga beberapa sen untuk masing-masing paku. Namun,
jika kita mempertimbangkan produksi pesawat jet dan pesawat jet, pembulatan dapat
mempengaruhi keuntungan (atau biaya) jutaan dolar. Dalam hal ini kita perlu menyelesaikan
masalah tersebut sehingga solusi integer yang optimal terjamin. Dalam bab ini berbagai
bentuk model pemrograman linier bilangan bulat disajikan.

Integer Programming Models

Ada tiga tipe dasar model pemrograman linier bilangan bulat — model bilangan bulat total,
model bilangan bulat 0–1, dan model bilangan bulat campuran. Dalam model bilangan bulat
total, semua variabel keputusan harus memiliki nilai solusi bilangan bulat. Dalam model
bilangan bulat 0–1, semua variabel keputusan memiliki nilai bilangan bulat nol atau satu.
Akhirnya, dalam model bilangan bulat campuran, beberapa variabel keputusan (tetapi tidak
semua) harus memiliki solusi bilangan bulat. Tiga contoh berikut menunjukkan jenis model
pemrograman integer ini.

A Total Integer Model Example / Model Bilangan Bulat Total

Pemilik toko mesin berencana untuk melakukan ekspansi dengan membeli beberapa
mesin baru — mesin press dan mesin bubut. Pemilik memperkirakan bahwa setiap pers yang
dibeli akan meningkatkan keuntungan sebesar $ 100 per hari dan setiap mesin bubut akan
meningkatkan keuntungan sebesar $ 150 setiap hari. Jumlah mesin yang dapat dibeli oleh
pemilik dibatasi oleh biaya mesin dan ruang lantai yang tersedia di toko. Harga beli mesin
dan kebutuhan tempat adalah sebagai berikut:

Mesin press : 15 ruang lantai 8000

Mesin bubuk : 30 ruang lantai 4000
 Pemilik memiliki anggaran $ 40.000 untuk membeli mesin dan 200 kaki persegi
ruang lantai yang tersedia. Pemilik ingin mengetahui berapa banyak dari setiap jenis mesin
yang akan dibeli untuk memaksimalkan peningkatan keuntungan harian. Model
pemrograman linier untuk masalah pemrograman bilangan bulat dirumuskan dengan cara
yang persis sama seperti contoh pemrograman linier di Bab 2, 3, dan 4. Satu-satunya
perbedaan adalah bahwa dalam masalah ini, variabel keputusan dibatasi pada nilai bilangan
bulat karena pemiliknya tidak dapat membeli sebagian, atau sebagian, dari sebuah mesin.
Model pemrograman linier berikut:

Variabel keputusan dalam model ini dibatasi untuk seluruh mesin. Fakta bahwa kedua
variabel keputusan, dan dapat mengasumsikan nilai bilangan bulat apa pun yang lebih besar
dari atau sama dengan nol adalah yang memberi model ini penunjukannya sebagai model
bilangan bulat total.

A 0–1 Integer Model Example / Model Bilangan Bulat 0-1

Dewan komunitas harus memutuskan fasilitas rekreasi mana yang akan dibangun di
komunitasnya. Empat fasilitas rekreasi baru telah diusulkan — kolam renang, pusat tenis,
lapangan atletik, dan gimnasium. Dewan ingin membangun fasilitas yang akan
memaksimalkan penggunaan sehari-hari yang diharapkan oleh warga masyarakat, tunduk
pada batasan lahan dan biaya. Penggunaan harian yang diharapkan dan biaya serta kebutuhan
lahan untuk setiap fasilitas adalah sebagai berikut:

Kolam renang : 300 penggunaan, biaya 35.000, lahan 4 hektar

Pusat tenis : 90 penggunaan, biaya 10.000, lahan 4 hektar
Lapangan atletik : 400 penggunaan, biaya 25.000, lahan 4 hektar
gimnasium : 150 penggunaan, biaya 90.000, lahan 4 hektar

Dalam model ini, variabel keputusan dapat memiliki nilai solusi nol atau satu. Jika
fasilitas tidak dipilih untuk konstruksi, variabel keputusan yang mewakilinya akan memiliki
nilai nol. Jika fasilitas dipilih, variabel keputusannya akan bernilai satu.

Kendala terakhir, x1+x2 <= 0 mencerminkan kemungkinan bahwa baik kolam renang
(x1) atau pusat tenis (x2) dapat dibangun, tetapi tidak keduanya. Agar jumlah (x1) dan (x2)
kurang dari atau sama dengan satu, salah satu variabel bisa bernilai satu, atau kedua variabel
bisa sama dengan nol. Ini juga disebut sebagai kendala yang saling eksklusif.

Jika komunitas telah menentukan bahwa baik kolam renang (x1) atau pusat tenis (x2)
harus dibangun, tetapi tidak keduanya, maka kendala terakhir akan menjadi persamaan,
x1+x2 = 1. Ini akan menghasilkan solusi yang akan mencakup atau tetapi keduanya tidak
akan sama (juga tidak akan keduanya sama dengan nol). Dengan cara ini, model memaksakan
pilihan antara dua fasilitas. Karena alasan ini, ini sering disebut batasan pilihan ganda

Variasi dari batasan pilihan ganda dapat digunakan untuk merumuskan situasi di
mana sejumlah fasilitas tertentu dari total harus dibangun. Misalnya, jika dewan komunitas
telah menetapkan bahwa tepat dua dari empat fasilitas harus dibangun, batasan ini akan
dirumuskan sebagai x1+x2+x3+x4 = 2.
 Jika, sebagai alternatif, dewan telah menetapkan bahwa tidak lebih dari dua fasilitas
harus dibangun, maka batasannya adalah x1+x2+x3+x4 <= 2.

Tipe lain dari batasan model 0–1 adalah batasan bersyarat. Dalam batasan bersyarat,
pembangunan satu fasilitas bergantung pada pembangunan fasilitas lainnya. Misalkan,
misalnya, proyek hewan peliharaan dari ketua dewan komunitas adalah kolam renang, dan
dia juga percaya bahwa pusat tenis itu sembrono. Ketua dewan sangat berpengaruh, sehingga
anggota dewan yang lain tahu bahwa pusat tenis tidak memiliki peluang untuk dipilih jika
kolam tidak dipilih terlebih dahulu. Namun, meskipun kolam dipilih, tidak ada jaminan
bahwa pusat tenis juga akan dipilih. Dengan demikian, pusat tenis bergantung pada
pembangunan kolam renang. Kondisi ini dirumuskan sebagai x2<=x1.

Perhatikan bahwa pusat tenis tidak bisa sama dengan satu (yaitu, dipilih) kecuali
kolam sama dengan satu. Jika pool sama dengan nol (yaitu, tidak dipilih), maka pusat tenis
juga harus sama dengan nol. Namun, kondisi ini memungkinkan pool sama dengan satu dan
dipilih dan tennis center sama dengan nol dan tidak dipilih. Variasi dari jenis batasan
bersyarat ini adalah batasan inti yang diinginkan, di mana jika satu fasilitas dibangun,
fasilitas lainnya juga akan dibangun dan sebaliknya. Sebagai contoh, misalkan dewan
membuat kesepakatan politik di antara mereka sendiri, di mana jika pool diterima, pusat tenis
juga harus dipilih dan sebaliknya. Batasan ini ditulis sebagai x2=x1.

Batasan ini membuat dan menyamai nilai yang sama, baik nol atau satu.