Pemodelan dengan
Pemrograman Linier
Ke l o m p o k 1
Adennia Oktaviana F Ahmad Rizyaldi
1 F0219002 2 F0219004
Ambrosius Farel I Ari Nurmiyati
3 F0219011
4 F0219020
Pemrograman linear (PL) ialah salah satu teknik dari riset operasi untuk memecahkan persoalan
optimasi (maksimum atau minimum) dengan menggunakan persamaan dan pertidaksamaan linear
dalam rangka untuk mencari pemecahan yang optimal dengan memperhatikan pembatasan-
pembatasan yang ada (Johannes Supranto, 1991 : 43).
Fungsi linear yang harus terpenuhi dalam optimisasi fungsi tujuan, dapat berbentuk persamaan
maupun pertidaksamaan yang disebut fungsi kendala (Dumairy, 2012 : 344).
• Variabel keputusan
Variabel keputusan adalah variabel yang mempengaruhi nilai tujuan yang hendak dicapai.
• Fungsi tujuan
Fungsi tujuan pada model pemrograman linear haruslah berbentuk linear.
• Fungsi kendala
Fungsi kendala adalah suatu kendala yang dapat dikatakan sebagai suatu pembatas terhadap
variabel-variabel keputusan yang dibuat.
• Fungsi non-negative
Fungsi yang menyatakan bahwa setiap variabel yang terdapat di dalam model pemrograman linear
tidak boleh negatif.
1. Model LP Dua-Variabel Contoh 2.1-1
(Perusahaan Reddy Mikks)
Reddy Mikks ingin menentukan bauran produk yang optimal (terbaik)
untuk interior dan eksterior cat yang memaksimalkan total keuntungan
harian. Semua model OR, termasuk LP, terdiri dari tiga komponen dasar:
• Variabel keputusan yang ingin kita tentukan.
• Objective (tujuan) yang perlu kita optimalkan (maximize or minimize).
• Batasan yang harus dipenuhi oleh solusi.
Untuk masalah Reddy Mikks
Variabel model didefinisikan sebagai:
x1 = Ton cat eksterior yang diproduksi setiap hari
x2 = Ton cat interior yang diproduksi setiap hari
Total keuntungan harian dinyatakan dalam variabel x1 dan x2 sebagai:
Keuntungan dari cat luar = 5x1 ribuan dollar Model matematis Reddy Mikks yang lengkap adalah
Keuntungan dari cat interior = 4x2 ribuan dollar
Subtitle Maksimumkan z = 5x1 + 4x2
Maksimumkan z = 5x1 + 4x2 dengan batasan
Batasan bahan mentah:
6x1 + 4x2 ≤ 24
6x1 + 4x2 ≤ 24 (Bahan mentah M1) x1 + 2x2 ≤ 6
x1 + 2x2 ≤ 6 (Bahan mentah M2) -x1 + x2 ≤ 1
x2 ≤ 2
x1 x2 ≥ 0
,
2. SOLUSI LP GRAFIK
A. Solusi dari Model Maksimalisasi
Contoh 2.2-1. Contoh ini memecahkan model Reddy Mikks dari Contoh 2.1-1.
➢ Langkah 1. Penentuan Ruang Solusi yang Layak:
Pertimbangkan batasan non negatif x1 ≥ 0 dan x2 ≥ 0.
Ganti setiap pertidaksamaan dengan persamaan, dan kemudian grafik
garis lurus yang dihasilkan dengan menempatkan dua titik yang berbeda.
Selanjutnya, perhatikan arah (> atau <) dari pertidaksamaan.
➢ Langkah 2. Penentuan Solusi Optimal:
Pemecahan yang optimum terjadi di titik C karena itu adalah titik layak di
ruang solusi di mana setiap peningkatan lebih lanjut akan membuat tidak
layak. Nilai x1 dan x2 yang terkait dengan titik C optimum ditentukan
dengan memecahkan persamaan yang terkait dengan garis (1) dan (2):
6x1 + 4x2 = 24
x1 + 2x2 = 6
x1 = 3 dan x2 = 1,5 dengan z = (5 x 3) + (4 x 1,5) = 21. Jadi, pemecahan
tersebut menyatakan bahwa produksi harian 3 ton cat eksterior dan 1,5
ton cat interior. Penghasilan yang terkait adalah $21.000.
B. Solusi dari Model Minimalisasi
Contoh 2.2-2 (Masalah diet).
Persyaratan diet pakan khusus minimal 30% protein dan paling banyak 5%
serat. Tujuannya adalah untuk menentukan campuran pakan dengan
biaya minimum harian.
Variabel keputusan model adalah:
x1 = Ib jagung dalam campuran harian
x2 = lb bungkil kedelai dalam campuran harian
Minimumkan z = .3x1 + .9x2
Jumlah protein yang termasuk dalam x1 lb jagung dan x2 lb bungkil kedelai
adalah (.09x1 + .6x2) lb. Kuantitas ini harus sama dengan setidaknya 30%
dari total campuran pakan (x1 + x2) lb yaitu,
.09x1 + .6x2 ≥ .3 (x1 + x2)
Dengan cara yang sama, kebutuhan serat paling banyak 5%
direpresentasikan sebagai:
.02x1 + .06x2 ≤ .05 (x1 + x2)
Model lengkapnya adalah
Minimumkan z = .3x1 + .9x2
dengan batasan
x1 + x2 ≥ 800
.21x1 - .30x2 ≤ 0
.03x1 - .01x2 ≥ 0
x1, x2 ≥ 0
Gambar 2.3 memberikan solusi grafik dari model
Penentuan setengah ruang yang layak dari dua batasan ini membutuhkan
penggunaan titik referensi selain (0, 0) [misalnya, (100, 0) atau (0, 100)].
Solusinya adalah model meminimalkan nilai fungsi tujuan dengan
mengurangi z ke arah yang ditunjukkan pada Gambar 2.3.
Solusi optimum adalah perpotongan dua garis
x1 + x2 = 800 dan .21x1 - .3x2 = 0,
yang menghasilkan
x1 = 470,6 lb dan x2 = 329,4 lb.
Biaya pakan minimum campurannya adalah
z = .3 x 470.6 + .9 x 329.4 = $437.64 per hari.
3. Solusi Komputer Dengan SOLVER dan AMPL
Model LP khas mungkin melibatkan ribuan variabel dan kendala, komputer
adalah satu-satunya tempat yang layak untuk memecahkan masalahnya.
AMPL adalah bahasa pemodelan aljabar yang sama seperti semua bahasa
pemrograman tingkat tinggi, membutuhkan lebih banyak keahlian. AMPL,
dan bahasa serupa, menawarkan fleksibilitas pemodelan yang luar biasa.
Meskipun presentasi di bagian ini berkonsentrasi pada LPs, baik AMPL dan
Solver dapat menangani masalah bilangan bulat dan nonlinier.
A. Solusi LP dengan Excel Solver
Gambar ini menunjukkan tata letak data untuk model Reddy Mikks. Bagian
atas gambar mencakup empat jenis informasi:
➢ sel data input (B5:C9 dan F6:F9)
➢ sel yang mewakili variabel dan fungsi tujuan (B13:D13)
➢ definisi aljabar dari fungsi tujuan dan sisi kiri kendala (sel D5:D9)
➢ sel yang menyediakan nama atau simbol penjelas (opsional)
Solver membutuhkan tiga jenis pertama saja. Jenis keempat meningkatkan
keterbacaan tetapi tidak melayani tujuan lain.
Bagaimana Solver menautkan ke data spreadsheet?
Pertama, diberikan definisi "aljabar" dari fungsi tujuan dan sisi kiri kendala menggunakan data input dan fungsi dan juga variabel tujuan.
Selanjutnya, menempatkan rumus yang dihasilkan dengan tepat di sel D5:D9, seperti yang ditunjukkan tabel berikut:
Rumus eksplisit yang baru saja dijelaskan tidak praktis untuk besar LPs. Sebagai gantinya, rumus di sel D5 dapat ditulis secara ringkas sebagai:
=SUMPRODUCT(B5:C5,$B$13:$C$13)
Rumus baru kemudian dapat disalin ke dalam sel D6:D9.
Untuk menjalankan model, klik Solver dari bilah menu spreadsheet untuk mengakses kotak dialog parameter Solver. Selanjutnya, perbarui kotak
dialog sebagai berikut:
Set Target Cell: $D$5
Equal To: ⊙Max
By Changing Cells: $B$13:$C$13
Informasi ini memberi tahu Solver bahwa variabel LP (sel $B$13 dan $C$13) ditentukan dengan memaksimalkan fungsi tujuan di sel $D$5.
Untuk mengatur Constraint, kik Add, masukkan sisi kiri, jenis pertidaksamaan, dan sisi kanan kendala sebagai:
$D$6:$D$9 <= $F$6:$F$9
Untuk pembatasan non-negatif, klik Add sekali lagi dan masukkan
$B$13:$C$13 > = 0
Cara lain untuk memasukkan batasan non-negatif SubtitlNama rentang Excel deskriptif dapat digunakan
adalah dengan mengklik Opsi di kotak Parameter Solver untuk meningkatkan keterbacaan. Gambar dibawah
untuk mengakses Opsi Solver. Pengaturan default yang memberikan rincian dengan ringkasan nama rentang
tersisa di Opsi Solver tidak perlu diubah. yang digunakan dalam model. Model harus
dikontraskan dengan file sebelumnya untuk melihat
bagaimana rentang digunakan dalam rumus.
B. Solusi LP dengan AMPL (Reddy Mikks Problem—A Rudimentary Model)
AMPL menyediakan fasilitas untuk memodelkan LP dalam format tulisan tangan
yang belum sempurna. Kode baru diperlukan setiap kali data input diubah.
AMPL meringankan kesulitan ini dengan merancang kode yang membagi
masalah menjadi dua komponen:
➢ Model aljabar umum untuk kelas masalah tertentu yang berlaku untuk
sejumlah variabel dan kendala.
➢ Data untuk menggerakkan model aljabar. implementasi kedua poin ini
dibahas di bagian berikut dengan menggunakan masalah Reddy Mikks.
Gambar 2.8 mencantumkan pernyataan model (file [Link]). File harus
benar-benar teks (ASCII). Simbol # menunjukkan awal dari komentar penjelasan.
Komentar dapat muncul pada baris terpisah atau mengikuti titik koma di akhir
pernyataan. Bahasanya peka huruf besar/kecil, dan semua kata kuncinya,
dengan sedikit pengecualian, menggunakan huruf kecil. Model aljabar di AMPL
melihat masalah LP umum dengan n variabel dan m kendala dalam format
umum berikut :
Model dikembangkan dalam hal parameter dan variabel dengan cara berikut. Fungsi tujuan dan batasan membawa nama yang berbeda diikuti oleh
titik dua (:). Pernyataan objektif adalah terjemahan langsung dari maximize
maximize z : sum{j in 1..n} c[j]*x[j];
Batasan i diberi restr nama root (arbitrary) yang diindeks di atas set {1..m}:
restr{i in 1..m}:sum{j in 1..n}a[i,j]*x[j]<=b[i];
4. Aplikasi Pemrograman Linear
A. Investasi
Bank One akan merancang mengenai kebijakan pinjaman di mana akan melibatkan $12.000.000
Subtitle
B. Production Planing and Inventory Control
Singel-period production model
Multiple period production-inventory model
ke kuantitas Biaya
1 100 $50
2 250 $45
3 190 $55
4 140 $48
5 220 $52
6 110 $50
Storage cost : $8/month/unit
Multiperiod production smoothing model
Bulan Permintaan unit
Biaya mempekerjakan karyawan : $200
Maret 520 unit Biaya memecat karyawan : $400.
pekerja tetap :12 unit/bulan,
April 720 unit Pekerja sementara :10 unit/bulan.
Mei 520 unit biaya penyimpanan : $50/unit/bulan.
Juni 620 unit
C. Workforce Planning
Bus Scheduling Model
D. Perencanaan Pembangunan Kota
Perencanaan kota berkaitan dengan 3 area umum:
➢ Membangun perumahan baru
➢ Meningkatkan perumahan dan area rekreasi dalam kota yang memburuk
➢ Perencanaan fasilitas umum (seperti sekolah dan bandara).
Kendala yang terkait dengan proyek-proyek ini adalah ekonomi (lahan, konstruksi, dan pembiayaan) dan sosial (sekolah, taman, dan tingkat
pendapatan). Tujuan dalam perencanaan kota berbeda-beda. Dalam pembangunan perumahan baru, keuntungan biasanya menjadi motif untuk
menjalankan proyek tersebut. Dalam 2 kategori yang tersisa, tujuan melibatkan pertimbangan sosial, politik, ekonomi dan budaya.
Model Pembaruan perkotaan
Kota Erstville menghadapi kekurangan anggaran yang parah. Mencari solusi jangka panjang, dewan kota memutuskan untuk meningkatkan basis
pajak dengan mengutuk kawasan perumahan dalam kota dan menggantinya dengan pembangunan modern. Proyek ini melibatkan 2 fase:
➢ Menghancurkan rumah di bawah standar untuk menyediakan lahan untuk pengembangan baru
➢ Membangun perkembangan baru
Ringkasan situasinya:
➢ Sebanyak 300 rumah di bawah standar bisa dibongkar. Setiap rumah menempati tanah seluas 0,25 hektar. Biaya untuk menghancurkan rumah
yang dikutuk adalah $2000.
➢ Ukuran lot untuk rumah (unit) keluarga tunggal, ganda, rangkap tiga, dan empat kali lipat baru masing-masing adalah .18, .28, .4, dan .5. Jalan,
ruang terbuka, dan kemudahan utilitas menyumbang 15% dari luas yang tersedia.
➢ Dalam pengembangan baru, unit triple dan quadruple menyumbang setidaknya 25% dari total. Unit tunggal harus minimal 20% dari semua unit,
dan unit ganda minimal 10%.
➢ Pajak yang dikenakan per unit untuk unit tunggal, ganda, rangkap tiga, dan empat kali lipat masing-masing adalah $1000, $1900, $2700, dan
$3400.
➢ Biaya konstruksi per unit untuk rumah keluarga tunggal, ganda, rangkap tiga, dan empat kali lipat masing-masing adalah $50.000, $70.000,
$130.000, dan $160.000.
➢ Pembiayaan melalui bank lokal dibatasi hingga $15 juta.
➢ Berapa unit masing-masing jenis harus dibangun untuk memaksimalkan pengumpulan pajak?
Model matematika:
➢ Variabel masalah dapat didefinisikan sebagai berikut:
𝑥_1 = Jumlah unit rumah keluarga tunggal
𝑥_2 = Jumlah unit rumah keluarga ganda
𝑥_3 = Jumlah unit rumah tiga keluarga
𝑥_4 = Jumlah unit rumah keluarga empat kali lipat
𝑥_5 = Jumlah rumah terkutuk yang akan dibongkar
➢ Maksimal z = 1.000𝑥_1 + 1.900𝑥_2 + 2.700𝑥_3 + 3.400𝑥_4
➢ Areal yang digunakan untuk pembangunan rumah baru ≤ Luas bersih yang tersedia
➢ Luas tanah yang dibutuhkan untuk rumah baru = .18𝑥_1 + .28𝑥_2 + .4𝑥_3 + .5𝑥_4
➢ Untuk menentukan areal yang tersedia, setiap rumah yang dibongkar menempati sebidang tanah seluas .25 acre, dengan demikian menjadi .85
(.25𝑥_5) = .2125𝑥_5. Batasan yang dihasilkan menjadi:
.18𝑥_1 + .28𝑥_2 + .4𝑥_3 + .5𝑥_4 ≤ .2125𝑥_5
.18𝑥_1 + .28𝑥_2 + .4𝑥_3 + .5𝑥_4 - .2125𝑥_5 ≤ 0
➢ Selanjutnya, kita menambahkan batasan yang membatasi jumlah unit setiap tipe rumah:
(Jumlah unit tunggal) ≥ (20% dari semua unit)
𝑥_1 ≥ .2 (𝑥_1 + 𝑥_2 + 𝑥_3 + 𝑥_4)
(Jumlah unit ganda) ≥ (10% dari semua unit)
𝑥_2 ≥ .1 (𝑥_1 + 𝑥_2 + 𝑥_3 + 𝑥_4)
(Jumlah unit triple dan quadruple) ≥ (25% dari semua unit)
𝑥_3 + 𝑥_4 ≥ .25 (𝑥_1 + 𝑥_2 + 𝑥_3 + 𝑥_4)
➢ Satu-satunya kendala yang tersisa berkaitan dengan menjaga biaya pembongkaran/konstruksi dalam anggaran yang diizinkan:
• Biaya konstruksi dan pembongkaran ≤ Modal yang tersedia
(50𝑥_1 + 70𝑥_2 + 130𝑥_3 + 160𝑥_4) - 2𝑥_5 ≤ 1.000
18𝑥_1 + .28𝑥_2 + .4𝑥_3 + .5𝑥_4 - .2125𝑥_5 ≤ 0
𝑥_5 ≤ 300
-.8𝑥_1 + .2𝑥_2 + .2𝑥_3 + .2𝑥_4 ≤ 0
.1𝑥_1 - .9𝑥_2 + .1𝑥_3 + .1𝑥_4 ≤ 0
.25𝑥_1 + .25𝑥_2 - .75𝑥_3 - .75𝑥_4 ≤ 0
50𝑥_1 + 70𝑥_2 + 130𝑥_3 + 160𝑥_4 + 2𝑥_5 ≤ 15.000
𝑥_1, 𝑥_2, 𝑥_3, 𝑥_4, 𝑥_5 ≥ 0
➢ Solusi:
Total pemungutan pajak = z = $343, 965
Jumlah rumah tunggal = 𝑥_1 = 35,83 36 unit
Jumlah rumah dobel = 𝑥_2 = 98,53 99 unit
Jumlah rumah rangkap tiga = 𝑥_3 = 44,79 45 unit
Jumlah rumah empat kali lipat = 𝑥_4 = 0 unit
Jumlah rumah yang dibongkar = 𝑥_5 = 244,49 245 unit
E. Pencampuran & Pemurnian
Sejumlah aplikasi LP (linear programming) berurusan dengan pencampuran bahan masukan yang berbeda untuk memproduksi produk yang
memenuhi spesifikasi tertentu sambil meminimalkan biaya atau memaksimalkan keuntungan.
Bagian ini juga menyajikan model (disederhanakan) untuk penyulingan minyak. Prosesnya dimulai dengan penyulingan minyak mentah untuk
menghasilkan stok bensin menengah, dan kemudian mencampur stok ini untuk menghasilkan produk bensin akhir.
Salah satu tujuan dari model ini adalah untuk menentukan bauran produk akhir yang optimal yang akan memaksimalkan fungsi keuntungan yang
sesuai.
C O N TO H S OA L
Shale Oil, yang terletak di pulau Aruba, memiliki kapasitas 1.500.000 bbl minyak mentah per hari. Produk akhir dari kilang tersebut antara lain 3 jenis
bensin tanpa timbal dengan angka oktan (ON) berbeda:
• Reguler dengan ON = 87
• Premium dengan AKTIF = 89
• Super dengan ON = 92
Proses pemurnian meliputi 3 tahap:
• Sebuah menara distilasi yang menghasilkan bahan baku 1ON = 822 dengan laju .2 bbl per bbl minyak mentah
• Unit cracker yang menghasilkan stok bensin 1ON = 982 dengan menggunakan sebagian bahan baku yang dihasilkan dari menara distilasi dengan
laju 0,5 bbl per bbl bahan baku
• Unit blender yang memadukan stok bensin dari unit cracker dan bahan baku dari menara distilasi.
Perusahaan memperkirakan laba bersih per barel dari 3 jenis bensin masing-masing adalah:
• $6,70
• $7,20
• $8,10
Kapasitas input unit cracker adalah 200.000 bbl bahan baku sehari. Batas permintaan untuk bensin:
• Reguler = 50.000 bbl
• Premium = 30.000 bbl
• Super = 40.000 bbl, per hari
Kembangkan model untuk menentukan jadwal produksi optimal untuk kilang.
PENYELESAIAN
Menggunakan definisi ini, kita memiliki:
▪ Produksi harian bensin reguler = 𝑥_11 + 𝑥_21 bbl/hari
▪ Produksi harian bensin premium = 𝑥_12 + 𝑥_22 bbl/hari
▪ Produksi harian bensin super = 𝑥_13 + 𝑥_23 bbl/hari
▪ Output harian unit blender= Produksi reguler harian + Produksi premium harian + Produksi super harian =
(𝑥_11 + 𝑥_21) + (𝑥_12 + 𝑥_22) + (𝑥_13 + 𝑥_23)
• Bahan baku harian untuk blender = 𝑥_11 + 𝑥_12 + 𝑥_13 bbl/hari
• Umpat unit cracker harian ke blender = 𝑥_21 + 𝑥_22 + 𝑥_23 bbl/hari
• Bahan baku harian ke cracker = 2 (𝑥_21 + 𝑥_22 + 𝑥_23) bbl/hari
• Minyak mentah harian yang digunakan di kilang = 5 (𝑥_11 + 𝑥_12 + 𝑥_13) + 10 (𝑥_21 + 𝑥_22 + 𝑥_23) bbl/hari
• Jadi model lengkapnya dapat diringkas sebagai:
Maksimal z = 6,70 (𝑥_11 + 𝑥_21) + 7,20 (𝑥_12 + 𝑥_22) + 8,10 (𝑥_13 + 𝑥_23)
Dengan batasan
5 (𝑥_11 + 𝑥_12 + 𝑥_13) + 10 (𝑥_21 + 𝑥_22 + 𝑥_23) ≤ 1.500.000
2 (𝑥_21 + 𝑥_22 + 𝑥_23) ≤ 200.000
𝑥_11 + 𝑥_21 ≤ 50.000
𝑥_12 + 𝑥_22 ≤ 30.000
𝑥_13 + 𝑥_23 ≤ 40.000
〖82𝑥〗_11 + 〖98𝑥〗_21 ≥ 87 (𝑥_11 + 𝑥_21)
〖82𝑥〗_12 + 〖98𝑥〗_22 ≥ 87 (𝑥_12 + 𝑥_22)
〖82𝑥〗_13 + 〖98𝑥〗_23 ≥ 87 (𝑥_13 + 𝑥_23)
𝑥_11, 𝑥_12, 𝑥_13, 𝑥_21, 〖 𝑥〗_22, 𝑥_23 ≥ 0
Solusi optimum adalah
z = 875.000, 𝑥_11 = 34.375, 𝑥_21 = 15.625, 𝑥_12 = 16.875, 〖 𝑥〗_22 = 13.125, 𝑥_13 = 15.000, 𝑥_23 = 25.000
Yang menjadi:
• Profit harian = $875.000
• Jumlah harian bensin biasa = 𝑥_11 + 𝑥_21 = 34.275 + 13.125 = 30.000 bbl/hari
• Jumlah harian bensin premium = 𝑥_12 + 𝑥_22 = 16.875 + 13.125 = 30.000 bbl/hari
• Jumlah harian bensin super = 𝑥_13 + 𝑥_23 = 15.000 +25.000 = 40.000 bbl/hari
Solusi tersebut menunjukkan bahwa produksi bensin reguler kurang 20.000 bbl/hari untuk memenuhi permintaan maksimum. Permintaan untuk 2 kelas
yang tersisa dipenuhi.
TERIMA KASIH