Tujuan pembelajaran. Setelah menyelesaikan bab ini, kita akan mampu: 1. Membedakan linear programming (LP), integer programming (IP), dan mixed-integer programming (MIP). 2. Memformulasikan binary programming untuk keputusan ya/tidak—pemilihan pelanggan, lokasi fasilitas, dan penjadwalan. 3. Menerapkan logical constraints (jika-maka, saling eksklusif, ketergantungan) dalam model optimasi. 4. Menerapkan nonlinear programming untuk hubungan yang tidak linear—diminishing returns, economies of scale. 5. Menyelesaikan model dengan PuLP (untuk integer) dan SciPy (untuk nonlinear). 6. Menafsirkan solusi integer dan memahami gap antara solusi LP-relaxation dan solusi integer. 7. Memilih teknik optimasi yang tepat berdasarkan struktur masalah.
Di Bab 14, kita mengasumsikan variabel keputusan dapat berupa pecahan. Tetapi banyak keputusan bisnis bersifat diskrit:
Integer programming memperluas LP untuk menangani variabel bilangan bulat. Binary programming (kasus khusus integer dengan nilai 0/1) memungkinkan kita memodelkan keputusan ya/tidak.
Mengapa tidak sekadar membulatkan solusi LP? Ini adalah pertanyaan yang sangat umum. Membulatkan solusi LP sering menghasilkan solusi yang tidak layak (melanggar kendala) atau jauh dari optimal.
Contoh: jika LP menghasilkan \(x_1 = 2,5\) dan \(x_2 = 2,5\) dengan kendala \(x_1 + x_2 \leq 5\), membulatkan ke \(x_1 = 3, x_2 = 3\) akan melanggar kendala. Membulatkan ke \(x_1 = 2, x_2 = 3\) layak tetapi mungkin bukan optimal.
Integer programming menyelesaikan masalah ini secara eksak—tetapi dengan biaya komputasi yang lebih tinggi.
| Tipe | Variabel | Contoh keputusan |
|---|---|---|
| Pure Integer (IP) | Semua variabel integer | Berapa unit setiap produk diproduksi? |
| Binary (0/1) | Variabel 0 atau 1 | Apakah gudang ini dibuka? Apakah pelanggan ini diintervensi? |
| Mixed-Integer (MIP) | Sebagian integer, sebagian kontinu | Berapa pelanggan diintervensi (integer) dan berapa anggaran dialokasikan (kontinu)? |
Perbedaan penting antara LP dan IP adalah kompleksitas:
Untuk masalah kecil (puluhan variabel), IP diselesaikan dalam hitungan detik. Untuk masalah besar (ribuan variabel), bisa memakan jam atau hari. Karena itu, teknik seperti branch-and-bound, cutting planes, dan heuristics sangat penting.
Aturan praktis: - Jika jumlah variabel integer < 100: IP biasanya diselesaikan cepat. - Jika 100–1.000: MIP masih bisa diselesaikan dengan solver modern (CBC, GLPK) dalam hitungan menit. - Jika > 1.000: Pertimbangkan LP relaxation + heuristic, atau solver komersial (Gurobi, CPLEX) yang jauh lebih cepat.
Binary programming adalah bentuk integer programming yang paling banyak dipakai dalam keputusan bisnis. Variabel keputusan hanya bernilai 0 atau 1—mewakili keputusan ya/tidak.
Setiap binary variable \(x_i \in \{0, 1\}\) mewakili: \(x_i = 1\) jika alternatif \(i\) dipilih, \(x_i = 0\) jika tidak.
Contoh: - \(x_i = 1\) jika pelanggan \(i\) diintervensi. - \(x_j = 1\) jika gudang \(j\) dibuka. - \(x_{ij} = 1\) jika karyawan \(i\) ditugaskan ke shift \(j\).
Ini adalah perluasan langsung dari Bab 14—tetapi kali ini kita memilih pelanggan secara individual, bukan segmen. Setiap pelanggan adalah binary: diintervensi atau tidak.
import sys
sys.path.insert(0, ".")
import pandas as pd
import numpy as np
import matplotlib.pyplot as plt
import warnings
warnings.filterwarnings("ignore")
from pulp import (
LpProblem, LpVariable, LpMaximize, LpMinimize, LpStatus,
lpSum, value, PULP_CBC_CMD,
LpBinary, LpInteger, LpContinuous,
)
np.random.seed(42)# Simulasi 200 pelanggan dengan probabilitas churn dan LTV berbeda
n = 200
np.random.seed(42)
pelanggan = pd.DataFrame({
"id": [f"P{i:03d}" for i in range(n)],
"prob_churn": np.random.beta(2, 5, n),
"ltv": np.random.uniform(300_000, 2_000_000, n),
})
# Intervensi: biaya Rp 100.000, efektivitas 30% (relatif)
BIAYA_INTERVENSI = 100_000
EFEKTIVITAS = 0.30
pelanggan["expected_benefit"] = (
pelanggan["prob_churn"] * EFEKTIVITAS * pelanggan["ltv"]
)
pelanggan["net_benefit"] = pelanggan["expected_benefit"] - BIAYA_INTERVENSI
print(f"Total pelanggan : {len(pelanggan)}")
print(f"Pelanggan dengan net benefit positif: {(pelanggan['net_benefit'] > 0).sum()}")
print(f"Total net benefit jika semua diintervensi: "
f"Rp {pelanggan['net_benefit'].sum():,.0f}")
print(f"Total biaya jika semua diintervensi: "
f"Rp {len(pelanggan) * BIAYA_INTERVENSI:,.0f}")
pelanggan.head()Total pelanggan : 200
Pelanggan dengan net benefit positif: 80
Total net benefit jika semua diintervensi: Rp -1,235,346
Total biaya jika semua diintervensi: Rp 20,000,000| id | prob_churn | ltv | expected_benefit | net_benefit | |
|---|---|---|---|---|---|
| 0 | P000 | 0.353677 | 7.983511e+05 | 84707.448901 | -15292.551099 |
| 1 | P001 | 0.248558 | 1.823771e+06 | 135993.889727 | 35993.889727 |
| 2 | P002 | 0.415959 | 3.221033e+05 | 40194.534661 | -59805.465339 |
| 3 | P003 | 0.159968 | 4.453645e+05 | 21373.163943 | -78626.836057 |
| 4 | P004 | 0.550283 | 6.534066e+05 | 107867.584093 | 7867.584093 |
Variabel keputusan: \(x_i \in \{0, 1\}\) untuk setiap pelanggan \(i\).
Fungsi tujuan: maksimalkan total net benefit.
\[\max \, Z = \sum_i \text{net\_benefit}_i \cdot x_i\]
Kendala: - Anggaran: \(\sum_i \text{biaya} \cdot x_i \leq \text{BUDGET}\) - Kapasitas tim: \(\sum_i x_i \leq \text{CAPACITY}\) - Binary: \(x_i \in \{0, 1\}\)
BUDGET = 10_000_000 # Rp 10 juta
CAPACITY = 80 # 80 pelanggan bisa dihubungi
model = LpProblem("pemilihan_pelanggan", LpMaximize)
# Binary variables
x = LpVariable.dicts(
"pilih", pelanggan["id"].tolist(), cat=LpBinary,
)
# Fungsi tujuan
model += lpSum(
pelanggan.loc[i, "net_benefit"] * x[pid]
for i, pid in enumerate(pelanggan["id"])
), "Total_Net_Benefit"
# Kendala anggaran
model += lpSum(
BIAYA_INTERVENSI * x[pid] for pid in pelanggan["id"]
) <= BUDGET, "Anggaran"
# Kendala kapasitas
model += lpSum(x[pid] for pid in pelanggan["id"]) <= CAPACITY, "Kapasitas"
# Selesaikan
model.solve(PULP_CBC_CMD(msg=False))
selected = [pid for pid in pelanggan["id"] if value(x[pid]) > 0.5]
print(f"Status : {LpStatus[model.status]}")
print(f"Total Net Benefit: Rp {value(model.objective):,.0f}")
print(f"Pelanggan terpilih: {len(selected)} / {len(pelanggan)}")
print(f"Biaya total : Rp {len(selected) * BIAYA_INTERVENSI:,.0f} / Rp {BUDGET:,.0f}")
print(f"\nContoh 10 pelanggan terpilih:")
hasil = pelanggan[pelanggan["id"].isin(selected)].nlargest(10, "net_benefit")
hasil[["id", "prob_churn", "ltv", "net_benefit"]].round(2)Status : Optimal
Total Net Benefit: Rp 4,782,835
Pelanggan terpilih: 80 / 200
Biaya total : Rp 8,000,000 / Rp 10,000,000
Contoh 10 pelanggan terpilih:| id | prob_churn | ltv | net_benefit | |
|---|---|---|---|---|
| 10 | P010 | 0.54 | 1689654.05 | 175481.27 |
| 188 | P188 | 0.47 | 1906044.44 | 166420.25 |
| 115 | P115 | 0.41 | 1979035.61 | 142618.08 |
| 157 | P157 | 0.49 | 1657931.50 | 141602.36 |
| 37 | P037 | 0.65 | 1193673.31 | 133569.26 |
| 164 | P164 | 0.43 | 1785251.09 | 132362.49 |
| 67 | P067 | 0.80 | 961802.54 | 131257.69 |
| 21 | P021 | 0.39 | 1912370.62 | 123755.58 |
| 113 | P113 | 0.65 | 1132022.44 | 119513.96 |
| 116 | P116 | 0.38 | 1904900.88 | 116285.46 |
Perhatikan: Binary programming memilih tepat 80 pelanggan dengan net benefit tertinggi (karena anggaran Rp 10 juta = 100 × Rp 100.000, dan kapasitas = 80). Ini adalah solusi eksak—bukan pembulatan.
Salah satu analisis penting dalam integer programming adalah LP-relaxation: menyelesaikan masalah yang sama dengan variabel kontinu, lalu melihat seberapa dekat solusinya dengan solusi integer.
# Selesaikan LP-relaxation (variabel kontinu 0-1)
model_lp = LpProblem("pemilihan_lp", LpMaximize)
x_lp = LpVariable.dicts(
"pilih_lp", pelanggan["id"].tolist(), lowBound=0, upBound=1, cat=LpContinuous,
)
model_lp += lpSum(
pelanggan.loc[i, "net_benefit"] * x_lp[pid]
for i, pid in enumerate(pelanggan["id"])
), "Total_Net_Benefit"
model_lp += lpSum(
BIAYA_INTERVENSI * x_lp[pid] for pid in pelanggan["id"]
) <= BUDGET, "Anggaran"
model_lp += lpSum(x_lp[pid] for pid in pelanggan["id"]) <= CAPACITY, "Kapasitas"
model_lp.solve(PULP_CBC_CMD(msg=False))
lp_obj = value(model_lp.objective)
ip_obj = value(model.objective)
gap = (lp_obj - ip_obj) / lp_obj * 100
print(f"LP-relaxation objective : Rp {lp_obj:,.0f}")
print(f"Integer objective : Rp {ip_obj:,.0f}")
print(f"Gap : {gap:.2f}%")
print()
print("Gap = seberapa jauh solusi integer dari batas atas LP.")
print("Untuk masalah ini, gap kecil berarti LP-relaxation cukup dekat")
print("dengan solusi optimal yang sesungguhnya.")LP-relaxation objective : Rp 4,782,835
Integer objective : Rp 4,782,835
Gap : 0.00%
Gap = seberapa jauh solusi integer dari batas atas LP.
Untuk masalah ini, gap kecil berarti LP-relaxation cukup dekat
dengan solusi optimal yang sesungguhnya.LP-relaxation adalah alat penting dalam integer programming:
Batas atas (untuk maksimisasi): solusi LP selalu ≥ solusi integer. Ini memberi kita batas atas untuk mengevaluasi kualitas solusi integer.
Mengukur gap: jika gap kecil (<1%), solusi LP mungkin cukup untuk diimplementasikan (dengan pembulatan yang hati-hati). Jika gap besar, kita perlu integer programming yang sesungguhnya.
Dasar branch-and-bound: solver integer modern menggunakan LP-relaxation sebagai bagian dari algoritmanya—mereka menyelesaikan LP relaxation, lalu “bercabang” pada variabel yang bernilai pecahan.
Untuk masalah kita, gap kemungkinan sangat kecil karena masalahnya sederhana—semua pelanggan memiliki biaya sama, sehingga solusi optimal adalah memilih 80 pelanggan dengan net benefit tertinggi.
# Kasus B: biaya intervensi BERBEDA per pelanggan
np.random.seed(42)
pelanggan["biaya_intervensi"] = np.random.uniform(50_000, 300_000, n)
pelanggan["net_benefit_het"] = (
pelanggan["prob_churn"] * EFEKTIVITAS * pelanggan["ltv"]
- pelanggan["biaya_intervensi"]
)
# Model integer dengan biaya heterogen
model_het = LpProblem("pemilihan_heterogen", LpMaximize)
x_het = LpVariable.dicts("pilih_het", pelanggan["id"].tolist(), cat=LpBinary)
model_het += lpSum(
pelanggan.loc[i, "net_benefit_het"] * x_het[pid]
for i, pid in enumerate(pelanggan["id"])
), "Total_Net_Benefit"
model_het += lpSum(
pelanggan.loc[i, "biaya_intervensi"] * x_het[pid]
for i, pid in enumerate(pelanggan["id"])
) <= BUDGET, "Anggaran"
model_het += lpSum(x_het[pid] for pid in pelanggan["id"]) <= CAPACITY, "Kapasitas"
model_het.solve(PULP_CBC_CMD(msg=False))
# LP-relaxation untuk kasus B
model_het_lp = LpProblem("pemilihan_heterogen_lp", LpMaximize)
x_het_lp = LpVariable.dicts(
"pilih_het_lp", pelanggan["id"].tolist(), lowBound=0, upBound=1, cat=LpContinuous,
)
model_het_lp += lpSum(
pelanggan.loc[i, "net_benefit_het"] * x_het_lp[pid]
for i, pid in enumerate(pelanggan["id"])
), "Total_Net_Benefit"
model_het_lp += lpSum(
pelanggan.loc[i, "biaya_intervensi"] * x_het_lp[pid]
for i, pid in enumerate(pelanggan["id"])
) <= BUDGET, "Anggaran"
model_het_lp += lpSum(x_het_lp[pid] for pid in pelanggan["id"]) <= CAPACITY, "Kapasitas"
model_het_lp.solve(PULP_CBC_CMD(msg=False))
lp_het = value(model_het_lp.objective)
ip_het = value(model_het.objective)
gap_het = (lp_het - ip_het) / lp_het * 100
print(f"Kasus B — biaya heterogen:")
print(f" LP-relaxation : Rp {lp_het:,.0f}")
print(f" Integer : Rp {ip_het:,.0f}")
print(f" Gap : {gap_het:.2f}%")
# Berapa variabel yang pecahan di solusi LP?
n_fractional = sum(
1 for pid in pelanggan["id"]
if 0.01 < value(x_het_lp[pid]) < 0.99
)
print(f" Variabel pecahan di LP-relaxation: {n_fractional} (dari {n} pelanggan)")Kasus B — biaya heterogen:
LP-relaxation : Rp 2,409,226
Integer : Rp 2,409,226
Gap : 0.00%
Variabel pecahan di LP-relaxation: 0 (dari 200 pelanggan)Kasus A (sekarang): Biaya seragam → gap 0%
Pertahankan blok yang ada, tetapi tambahkan catatan:
Mengapa gap = 0%? Karena semua pelanggan memiliki biaya intervensi yang sama (Rp 100.000), masalahnya tereduksi menjadi “pilih top-80 pelanggan dengan net benefit tertinggi”—dan LP-relaxation untuk masalah ini selalu menghasilkan solusi integer. Ini adalah kasus khusus, bukan aturan umum untuk integer programming.
Lihat Kasus B di bawah untuk melihat gap yang sesungguhnya.
Kasus B (baru): Biaya bervariasi → gap > 0
Hasil yang diharapkan: gap beberapa persen (biasanya 2–10%), dan LP-relaxation akan memiliki beberapa variabel bernilai pecahan (mis. x_i = 0,73)—yang tidak dapat diimplementasikan secara langsung.
Dengan dua kasus ini, kita akan memahami:
n_positive = (pelanggan["net_benefit_het"] > 0).sum()
total_cost_positive = pelanggan.loc[pelanggan["net_benefit_het"] > 0, "biaya_intervensi"].sum()
print(f"Pelanggan dengan net benefit positif : {n_positive} / {n}")
print(f"Total biaya pelanggan positif : Rp {total_cost_positive:,.0f}")
print(f"BUDGET : Rp {BUDGET:,.0f}")
print(f"CAPACITY : {CAPACITY}")
print()
print(f"→ Budget {'MENGIKAT' if total_cost_positive > BUDGET else 'TIDAK mengikat'}")
print(f"→ Capacity {'MENGIKAT' if n_positive > CAPACITY else 'TIDAK mengikat'}")Pelanggan dengan net benefit positif : 43 / 200
Total biaya pelanggan positif : Rp 4,280,268
BUDGET : Rp 10,000,000
CAPACITY : 80
→ Budget TIDAK mengikat
→ Capacity TIDAK mengikatAgar LP-relaxation menghasilkan solusi pecahan (dan gap > 0), kita perlu dua kondisi (ini kita perlukan sebagai contoh untuk solusi yg mendekati):
np.random.seed(42)
# Biaya lebih rendah → lebih banyak pelanggan dengan net benefit positif
pelanggan["biaya_intervensi"] = np.random.uniform(50_000, 200_000, n)
# Efektivitas lebih tinggi (0,50) → expected benefit meningkat
pelanggan["net_benefit_het"] = (
pelanggan["prob_churn"] * 0.50 * pelanggan["ltv"]
- pelanggan["biaya_intervensi"]
)
# Budget lebih ketat → memaksa trade-off
BUDGET_B = 5_000_000
CAPACITY_B = 80
n_pos = (pelanggan["net_benefit_het"] > 0).sum()
cost_pos = pelanggan.loc[pelanggan["net_benefit_het"] > 0, "biaya_intervensi"].sum()
print(f"Pelanggan positif : {n_pos} / {n}")
print(f"Total biaya positif: Rp {cost_pos:,.0f} | Budget: Rp {BUDGET_B:,.0f}")
print(f"→ Budget {'MENGIKAT' if cost_pos > BUDGET_B else 'tidak mengikat'} ✓")
print(f"→ Capacity {'MENGIKAT' if n_pos > CAPACITY_B else 'tidak mengikat'}")Pelanggan positif : 115 / 200
Total biaya positif: Rp 12,833,686 | Budget: Rp 5,000,000
→ Budget MENGIKAT ✓
→ Capacity MENGIKAT# --- Model Integer ---
model_het = LpProblem("pemilihan_heterogen", LpMaximize)
x_het = LpVariable.dicts("pilih_het", pelanggan["id"].tolist(), cat=LpBinary)
model_het += lpSum(
pelanggan.loc[i, "net_benefit_het"] * x_het[pid]
for i, pid in enumerate(pelanggan["id"])
), "Total_Net_Benefit"
model_het += lpSum(
pelanggan.loc[i, "biaya_intervensi"] * x_het[pid]
for i, pid in enumerate(pelanggan["id"])
) <= BUDGET_B, "Anggaran"
model_het += lpSum(x_het[pid] for pid in pelanggan["id"]) <= CAPACITY_B, "Kapasitas"
model_het.solve(PULP_CBC_CMD(msg=False))
# --- LP-Relaxation ---
model_het_lp = LpProblem("pemilihan_heterogen_lp", LpMaximize)
x_het_lp = LpVariable.dicts(
"pilih_het_lp", pelanggan["id"].tolist(),
lowBound=0, upBound=1, cat=LpContinuous,
)
model_het_lp += lpSum(
pelanggan.loc[i, "net_benefit_het"] * x_het_lp[pid]
for i, pid in enumerate(pelanggan["id"])
), "Total_Net_Benefit"
model_het_lp += lpSum(
pelanggan.loc[i, "biaya_intervensi"] * x_het_lp[pid]
for i, pid in enumerate(pelanggan["id"])
) <= BUDGET_B, "Anggaran"
model_het_lp += lpSum(x_het_lp[pid] for pid in pelanggan["id"]) <= CAPACITY_B, "Kapasitas"
model_het_lp.solve(PULP_CBC_CMD(msg=False))
# --- Bandingkan ---
lp_het = value(model_het_lp.objective)
ip_het = value(model_het.objective)
gap_het = (lp_het - ip_het) / lp_het * 100
n_fractional = sum(
1 for pid in pelanggan["id"]
if 0.01 < value(x_het_lp[pid]) < 0.99
)
print(f"Kasus B — biaya heterogen + budget ketat:")
print(f" LP-relaxation : Rp {lp_het:,.0f}")
print(f" Integer : Rp {ip_het:,.0f}")
print(f" Gap : {gap_het:.2f}%")
print(f" Variabel pecahan: {n_fractional} (dari {n} pelanggan)")Kasus B — biaya heterogen + budget ketat:
LP-relaxation : Rp 9,633,383
Integer : Rp 9,625,504
Gap : 0.08%
Variabel pecahan: 1 (dari 200 pelanggan)Mengapa gap berubah dari 0% ke belasan persen?
| Kasus | Biaya | Budget | Gap |
|---|---|---|---|
| A — biaya seragam | Semua Rp 100k | Rp 10 juta | 0% |
| B — biaya heterogen + budget ketat | Rp 50k–200k | Rp 5 juta | > 0% |
Ketika biaya seragam, masalahnya tereduksi menjadi “pilih top-K by net benefit”—dan LP-relaxation selalu integral. Ketika biaya heterogen dan budget mengikat, LP harus memilih berdasarkan rasio net benefit per rupiah—dan item terakhir di batas budget menjadi pecahan yang tidak dapat diimplementasikan.
Inilah alasan integer programming diperlukan: - LP-relaxation memberi batas atas (upper bound) pada nilai optimal yang sesungguhnya. - Gap mengukur harga dari diskritasi—berapa banyak nilai yang hilang karena kita harus memilih “ya/tidak”, bukan “sebagian”. - Semakin besar gap, semakin penting menggunakan IP yang sesungguhnya, bukan sekadar membulatkan solusi LP.
# Tampilkan variabel pecahan di LP-relaxation
fractional_items = [
(pid, value(x_het_lp[pid]))
for pid in pelanggan["id"]
if 0.01 < value(x_het_lp[pid]) < 0.99
]
print(f"Variabel pecahan di LP-relaxation ({len(fractional_items)} item):")
for pid, val in fractional_items:
cost = pelanggan.loc[pelanggan["id"] == pid, "biaya_intervensi"].iloc[0]
benefit = pelanggan.loc[pelanggan["id"] == pid, "net_benefit_het"].iloc[0]
print(f" {pid}: x = {val:.3f} "
f"(biaya: Rp {cost:,.0f}, net benefit: Rp {benefit:,.0f})")
print(f"\nInterpretasi: LP 'memilih' item {fractional_items[0][0]} sebesar "
f"{fractional_items[0][1]*100:.1f}%.")
print("Dalam praktik, kita tidak bisa mengintervensi pelanggan sebagian—")
print("harus 0% atau 100%. Inilah yang disebut 'harga dari diskritasi'.")Variabel pecahan di LP-relaxation (1 item):
P116: x = 0.794 (biaya: Rp 170,551, net benefit: Rp 189,925)
Interpretasi: LP 'memilih' item P116 sebesar 79.4%.
Dalam praktik, kita tidak bisa mengintervensi pelanggan sebagian—
harus 0% atau 100%. Inilah yang disebut 'harga dari diskritasi'.Mengapa hanya ada SATU variabel pecahan?
LP-relaxation dari masalah 0-1 knapsack memiliki sifat matematis yang sudah terbukti: solusi optimalnya paling banyak memiliki satu variabel pecahan—disebut critical item. LP memilih item berdasarkan rasio net_benefit per rupiah dari yang tertinggi ke terendah, dan “berhenti” di item ke-K ketika budget habis.
Item ke-K inilah yang menjadi pecahan—misalnya x = 0.68. Kita tidak bisa mengintervensi pelanggan ini “sebagian”. Harus 0 atau 1. Inilah yang membuat solusi integer berbeda dari solusi LP.
Gap 0,08% sangat kecil, tetapi konsepnya penting: LP-relaxation memberi kita batas atas (upper bound), dan gap mengukur “harga dari diskritasi”. Untuk masalah dengan gap besar (mis. facility location, scheduling), IP yang sesungguhnya bisa menghasilkan solusi yang jauh lebih baik daripada pembulatan LP.
Salah satu keunggulan binary programming adalah kemampuannya mengekspresikan logika. Ini membuka pintu untuk keputusan yang jauh lebih kaya daripada LP murni.
| Pola | Kendala | Interpretasi |
|---|---|---|
| Saling eksklusif | \(x_1 + x_2 \leq 1\) | Pilih salah satu, tidak keduanya |
| Jika-maka | \(x_1 \leq x_2\) | Jika \(x_1 = 1\), maka \(x_2\) harus 1 |
| Ketergantungan | \(x_1 \leq x_2 + x_3\) | Jika \(x_1 = 1\), maka salah satu dari \(x_2, x_3\) harus 1 |
| Batas minimal | \(\sum_i x_i \geq k\) | Pilih setidaknya \(k\) alternatif |
Ini adalah masalah klasik dalam binary programming: di mana membuka gudang untuk meminimalkan biaya?
# 5 calon lokasi gudang, 20 toko yang harus dilayani
np.random.seed(42)
n_gudang = 5
n_toko = 20
gudang = pd.DataFrame({
"id": [f"G{i}" for i in range(n_gudang)],
"biaya_buka": np.random.randint(5_000_000, 15_000_000, n_gudang),
"kapasitas": np.random.randint(500, 1500, n_gudang),
})
toko = pd.DataFrame({
"id": [f"T{i}" for i in range(n_toko)],
"permintaan": np.random.randint(50, 200, n_toko),
})
# Biaya transportasi gudang → toko
biaya_transport = pd.DataFrame(
np.random.randint(10_000, 100_000, (n_gudang, n_toko)),
index=gudang["id"],
columns=toko["id"],
)
print(f"Total permintaan toko: {toko['permintaan'].sum()} unit")
print(f"Total kapasitas gudang (jika semua dibuka): {gudang['kapasitas'].sum()} unit")
print()
gudangTotal permintaan toko: 2398 unit
Total kapasitas gudang (jika semua dibuka): 3846 unit
| id | biaya_buka | kapasitas | |
|---|---|---|---|
| 0 | G0 | 11423388 | 830 |
| 1 | G1 | 11550634 | 958 |
| 2 | G2 | 9304572 | 587 |
| 3 | G3 | 7234489 | 872 |
| 4 | G4 | 14958614 | 599 |
Variabel keputusan: - \(y_j \in \{0, 1\}\) = 1 jika gudang \(j\) dibuka - \(x_{ij} \geq 0\) = jumlah unit dari gudang \(j\) ke toko \(i\)
Fungsi tujuan: minimalkan total biaya (buka + transportasi)
\[\min \, Z = \sum_j \text{biaya\_buka}_j \cdot y_j + \sum_{i,j} \text{biaya\_transport}_{ij} \cdot x_{ij}\]
Kendala: - Setiap toko harus terpenuhi: \(\sum_j x_{ij} = \text{permintaan}_i\) - Kapasitas gudang: \(\sum_i x_{ij} \leq \text{kapasitas}_j \cdot y_j\) (MIP linking) - \(y_j \in \{0, 1\}\), \(x_{ij} \geq 0\)
Kendala x_{ij} ≤ kapasitas_j · y_j adalah kunci. Ini adalah linking constraint yang menghubungkan variabel kontinu (x) dengan variabel binary (y). Jika gudang \(j\) tidak dibuka (\(y_j = 0\)), maka aliran \(x_{ij}\) dari gudang itu harus nol. Inilah yang membuat model menjadi MIP—dan inilah yang membuatnya powerful.
facility_model = LpProblem("facility_location", LpMinimize)
# Binary: buka gudang?
y = LpVariable.dicts("buka", gudang["id"].tolist(), cat=LpBinary)
# Continuous: aliran dari gudang j ke toko i
x_flow = LpVariable.dicts(
"alir", [(g, t) for g in gudang["id"] for t in toko["id"]],
lowBound=0, cat=LpContinuous,
)
# Fungsi tujuan: biaya buka + biaya transportasi
facility_model += (
lpSum(gudang.loc[j, "biaya_buka"] * y[gudang.loc[j, "id"]]
for j in range(n_gudang)) +
lpSum(biaya_transport.loc[g, t] * x_flow[(g, t)]
for g in gudang["id"] for t in toko["id"])
), "Total_Biaya"
# Setiap toko harus terpenuhi
for t in toko["id"]:
permintaan_t = toko.loc[toko["id"] == t, "permintaan"].iloc[0]
facility_model += lpSum(x_flow[(g, t)] for g in gudang["id"]) == permintaan_t, f"Permintaan_{t}"
# Kapasitas gudang (linking constraint)
for j, row in gudang.iterrows():
facility_model += (
lpSum(x_flow[(row["id"], t)] for t in toko["id"]) <= row["kapasitas"] * y[row["id"]]
), f"Kapasitas_{row['id']}"
# Selesaikan
facility_model.solve(PULP_CBC_CMD(msg=False))
print(f"Status : {LpStatus[facility_model.status]}")
print(f"Total biaya : Rp {value(facility_model.objective):,.0f}")
print(f"\nGudang yang dibuka:")
for j in gudang["id"]:
if value(y[j]) > 0.5:
print(f" {j} (kapasitas {gudang.loc[gudang['id']==j, 'kapasitas'].iloc[0]})")Status : Optimal
Total biaya : Rp 111,328,329
Gudang yang dibuka:
G0 (kapasitas 830)
G1 (kapasitas 958)
G3 (kapasitas 872)Binary programming juga sangat berguna untuk penjadwalan—memilih kombinasi shift yang memenuhi kebutuhan staf.
# Kebutuhan staf per hari (dalam shift pagi, siang, malam)
kebutuhan = pd.DataFrame({
"hari": ["Sen", "Sel", "Rab", "Kam", "Jum", "Sab", "Min"],
"pagi": [8, 7, 9, 8, 10, 6, 4],
"siang": [6, 6, 7, 7, 8, 5, 3],
"malam": [4, 4, 5, 5, 6, 3, 2],
})
# Alternatif shift: setiap shift mencakup 3 hari berturut-turut
shifts = {
"S1": ["Sen", "Sel", "Rab"],
"S2": ["Sel", "Rab", "Kam"],
"S3": ["Rab", "Kam", "Jum"],
"S4": ["Kam", "Jum", "Sab"],
"S5": ["Jum", "Sab", "Min"],
"S6": ["Sab", "Min", "Sen"],
"S7": ["Min", "Sen", "Sel"],
}
print("Kebutuhan staf per hari:")
kebutuhanKebutuhan staf per hari:| hari | pagi | siang | malam | |
|---|---|---|---|---|
| 0 | Sen | 8 | 6 | 4 |
| 1 | Sel | 7 | 6 | 4 |
| 2 | Rab | 9 | 7 | 5 |
| 3 | Kam | 8 | 7 | 5 |
| 4 | Jum | 10 | 8 | 6 |
| 5 | Sab | 6 | 5 | 3 |
| 6 | Min | 4 | 3 | 2 |
schedule_model = LpProblem("penjadwalan", LpMinimize)
# Variabel: berapa karyawan ditugaskan ke setiap pola shift
n_karyawan = LpVariable.dicts("shift", shifts.keys(), lowBound=0, cat=LpInteger)
# Minimalkan total karyawan
schedule_model += lpSum(n_karyawan[s] for s in shifts), "Total_Karyawan"
# Setiap hari, jumlah karyawan yang bekerja >= kebutuhan (per shift hari itu)
for hari in kebutuhan["hari"]:
# Shift yang mencakup hari ini
shift_hari_ini = [s for s, days in shifts.items() if hari in days]
for periode in ["pagi", "siang", "malam"]:
kebutuhan_hari = kebutuhan.loc[kebutuhan["hari"] == hari, periode].iloc[0]
schedule_model += (
lpSum(n_karyawan[s] for s in shift_hari_ini) >= kebutuhan_hari
), f"Kebutuhan_{hari}_{periode}"
schedule_model.solve(PULP_CBC_CMD(msg=False))
print(f"Status : {LpStatus[schedule_model.status]}")
print(f"Total karyawan : {value(schedule_model.objective):.0f}")
print(f"\nAlokasi per shift:")
for s in shifts:
print(f" {s}: {value(n_karyawan[s]):.0f} karyawan")Status : Optimal
Total karyawan : 18
Alokasi per shift:
S1: 5 karyawan
S2: 0 karyawan
S3: 4 karyawan
S4: 5 karyawan
S5: 1 karyawan
S6: 0 karyawan
S7: 3 karyawanPerhatikan struktur masalah penjadwalan. Kita tidak memilih kombinasi hari—kita memilih pola shift yang masing-masing mencakup beberapa hari. Variabel binary di sini adalah “berapa karyawan ditugaskan ke pola S1, S2, dst”—yang merupakan integer (bukan binary, karena bisa lebih dari 1).
Ini adalah pure integer programming: semua variabel harus bilangan bulat, tetapi tidak terbatas pada 0/1. Solusinya memberi kita jumlah minimum karyawan yang dibutuhkan untuk memenuhi kebutuhan.
Sampai di sini, semua model kita adalah linear—baik fungsi tujuan maupun kendala. Tetapi banyak hubungan bisnis tidak linear:
Nonlinear programming (NLP) menangani hubungan seperti ini. Berbeda dari LP/IP, NLP tidak memiliki jaminan solusi global—solusi yang ditemukan bisa berupa local optimum, bukan global optimum.
Sebuah perusahaan memiliki Rp 100 juta untuk anggaran iklan di tiga channel. Efektivitas iklan di setiap channel mengikuti diminishing returns:
\[\text{Revenue}_i = a_i \cdot \sqrt{\text{Anggaran}_i}\]
dengan \(a_i\) adalah koefisien efektivitas channel \(i\).
Fungsi tujuan: maksimalkan total revenue.
\[\max \, Z = a_1 \sqrt{x_1} + a_2 \sqrt{x_2} + a_3 \sqrt{x_3}\]
Kendala: \(x_1 + x_2 + x_3 \leq 100.000.000\)
from scipy.optimize import minimize
# Koefisien efektivitas channel
a = np.array([200, 150, 180]) # channel 1, 2, 3
BUDGET = 100_000_000
# Fungsi tujuan: negatif karena scipy.optimize.minimize
def objective(x):
return -np.sum(a * np.sqrt(x + 1)) # +1 untuk hindari sqrt(0)
# Kendala: total anggaran
constraints = [
{"type": "ineq", "fun": lambda x: BUDGET - x.sum()}, # total ≤ BUDGET
]
bounds = [(0, BUDGET)] * 3 # setiap channel ≥ 0
# Initial guess
x0 = np.array([BUDGET / 3] * 3)
# Selesaikan
result = minimize(objective, x0, method="SLSQP", bounds=bounds, constraints=constraints)
print(f"Status : {result.message}")
print(f"Optimal revenue: {(-result.fun) * 1000:,.0f} (dalam satuan ribuan)")
print(f"\nAlokasi anggaran optimal:")
for i, (channel, alloc) in enumerate(zip(["Channel 1", "Channel 2", "Channel 3"], result.x)):
print(f" {channel}: Rp {alloc:,.0f} ({alloc/BUDGET*100:.1f}%)")
print(f"\nTotal dialokasikan: Rp {result.x.sum():,.0f} / Rp {BUDGET:,.0f}")Status : Optimization terminated successfully
Optimal revenue: 3,059,956,473 (dalam satuan ribuan)
Alokasi anggaran optimal:
Channel 1: Rp 33,333,333 (33.3%)
Channel 2: Rp 33,333,333 (33.3%)
Channel 3: Rp 33,333,333 (33.3%)
Total dialokasikan: Rp 100,000,000 / Rp 100,000,000fig, axes = plt.subplots(1, 2, figsize=(11, 4))
# Kurva diminishing returns
x_range = np.linspace(0, BUDGET, 100)
for i, (coef, color) in enumerate(zip(a, ["#4C72B0", "#DD8452", "#55A868"])):
axes[0].plot(x_range / 1e6, coef * np.sqrt(x_range) / 1e3,
color=color, linewidth=2, label=f"Channel {i+1} (a={coef})")
axes[0].set_xlabel("Anggaran (Rp juta)")
axes[0].set_ylabel("Revenue (ribu)")
axes[0].set_title("Diminishing Returns per Channel")
axes[0].legend()
axes[0].grid(True, alpha=0.3)
# Alokasi optimal
axes[1].bar(["Channel 1", "Channel 2", "Channel 3"], result.x / 1e6,
color=["#4C72B0", "#DD8452", "#55A868"])
axes[1].set_ylabel("Anggaran (Rp juta)")
axes[1].set_title("Alokasi Optimal (Diminishing Returns)")
for i, v in enumerate(result.x / 1e6):
axes[1].text(i, v + 0.5, f"Rp {v:.1f}M", ha="center", fontsize=10)
plt.tight_layout()
plt.show()
Perhatikan perbedaan alokasi. Dengan diminishing returns (fungsi \(\sqrt{x}\)), alokasi optimal tidak merata—channel dengan koefisien efektivitas tertinggi mendapat porsi terbesar. Ini berbeda dengan kasus linear, di mana kita akan mengalokasikan semua anggaran ke channel dengan ROI tertinggi.
Diminishing returns adalah alasan matematis mengapa diversifikasi anggaran masuk akal—bahkan ketika satu channel lebih efektif dari yang lain. Setiap tambahan Rp ke channel yang sama memberikan pengembalian yang semakin kecil.
| Situasi | Contoh |
|---|---|
| Diminishing returns | Anggaran iklan, R&D, pelatihan |
| Economies of scale | Biaya produksi per unit menurun dengan volume |
| Risk-return trade-off | Portofolio investasi (variance sebagai fungsi kuadratik) |
| Physical constraints | Panjang, luas, volume dalam desain produk |
| Machine learning | Fungsi loss (MSE, cross-entropy) diminimalkan |
NLP tidak memiliki jaminan global optimum. Berbeda dari LP (yang selalu menemukan global optimum), NLP bisa terjebak di local optimum. Solusi yang ditemukan sangat bergantung pada: - Titik awal (initial guess). - Metode optimasi yang dipilih. - Struktur fungsi (convex vs non-convex).
Untuk fungsi convex (seperti diminishing returns dengan \(\sqrt{x}\)), local optimum = global optimum. Untuk fungsi non-convex, kita mungkin perlu mencoba beberapa titik awal atau menggunakan global optimization methods (basin-hopping, differential evolution).
Berikut adalah pohon keputusan untuk memilih teknik optimasi:
flowchart TD
A[Apakah variabel keputusan diskrit?] -->|Ya| B[Apakah binary 0/1?]
A -->|Tidak| C[Apakah hubungan linear?]
B -->|Ya| D[Binary Programming]
B -->|Tidak| E[Integer Programming]
C -->|Ya| F[Linear Programming]
C -->|Tidak| G[Nonlinear Programming]
D --> H[PuLP / OR-Tools]
E --> H
F --> H
G --> I[SciPy / CVXPY]flowchart TD
A[Apakah variabel keputusan diskrit?] -->|Ya| B[Apakah binary 0/1?]
A -->|Tidak| C[Apakah hubungan linear?]
B -->|Ya| D[Binary Programming]
B -->|Tidak| E[Integer Programming]
C -->|Ya| F[Linear Programming]
C -->|Tidak| G[Nonlinear Programming]
D --> H[PuLP / OR-Tools]
E --> H
F --> H
G --> I[SciPy / CVXPY]
| Tipe masalah | Teknik | Library |
|---|---|---|
| Variabel kontinu, hubungan linear | LP | PuLP, SciPy |
| Variabel integer, hubungan linear | IP/MIP | PuLP, OR-Tools |
| Variabel binary (0/1) | Binary Programming | PuLP, OR-Tools |
| Variabel kontinu, hubungan nonlinear | NLP | SciPy, CVXPY |
| Variabel integer + nonlinear | MINLP | Pyomo, Gurobi (komersial) |
Latihan 15.1 — Binary programming untuk pemilihan fitur. kita memiliki 10 fitur dengan biaya pengumpulan data yang berbeda dan nilai prediktif yang berbeda. Formulasikan binary programming untuk memilih subset fitur yang memaksimalkan nilai prediktif di bawah anggaran pengumpulan data Rp 5 juta. (Petunjuk: setiap fitur adalah binary—dipilih atau tidak.)
Latihan 15.2 — Facility location dengan batasan. Modifikasi model facility location dengan menambahkan kendala: maksimal 3 gudang yang boleh dibuka. Bagaimana solusi berubah? Berapa kenaikan biaya total?
Latihan 15.3 — Penjadwalan dengan preferensi. Modifikasi model penjadwalan dengan menambahkan preferensi karyawan: setiap shift memiliki biaya preferensi yang berbeda (mis. shift malam lebih mahal). Formulasikan ulang fungsi tujuan untuk meminimalkan total biaya (gaji + preferensi).
Latihan 15.4 — Logical constraints. Dalam model facility location, tambahkan kendala: jika G1 dibuka, maka G2 tidak boleh dibuka. Formulasikan dengan binary programming dan selesaikan ulang. Bagaimana solusi berubah?
Latihan 15.5 — Nonlinear dengan multiple optima. Untuk model optimasi iklan, coba titik awal yang berbeda: x0 = [BUDGET, 0, 0], x0 = [0, BUDGET, 0], x0 = [BUDGET/3, BUDGET/3, BUDGET/3]. Apakah solusi akhirnya sama? Jika ya, mengapa? (Petunjuk: fungsi \(\sqrt{x}\) bersifat convex.)
Latihan 15.6 — Perbandingan LP vs IP. Untuk model pemilihan pelanggan (Aplikasi 1), bandingkan solusi LP-relaxation dengan solusi integer. Berapa gap? Apakah solusi LP-relaxation dapat dibulatkan untuk mendapatkan solusi integer yang layak? Jika tidak, mengapa?
Petunjuk Latihan 15.4. Untuk “jika G1 dibuka maka G2 tidak boleh dibuka”, formulasinya adalah: \(y_{G1} + y_{G2} \leq 1\). Ini juga berfungsi sebagai mutual exclusion—jika kita ingin keduanya tidak boleh dibuka bersamaan. Jika kita hanya ingin satu arah (G1 → G2 tidak dibuka), gunakan \(y_{G1} \leq 1 - y_{G2}\), yang setara.
Jembatan. Bab ini telah memperluas kemampuan optimasi kita dari tiga arah:
Tetapi tiga keterbatasan penting masih tersisa:
Bab 16—Network & Multi-Objective Optimization—akan menangani dua keterbatasan pertama: jaringan (dengan network flow models) dan multi-objective (dengan Pareto frontier). Ini akan menyiapkan kita untuk Bab 17, di mana kita menggabungkan semuanya dengan simulasi keputusan.
Dalam bab ini kita telah:
Kita telah memperluas LP ke keputusan diskrit (integer), keputusan ya/tidak (binary), dan hubungan nonlinear. Tetapi ada dua dimensi keputusan yang belum kita tangani:
Struktur jaringan. Banyak keputusan melibatkan aliran melalui jaringan—barang dari gudang ke toko, karyawan dari rumah ke kantor, informasi dari server ke pengguna. Model network flow dapat menyelesaikan masalah ini jauh lebih efisien daripada LP umum.
Tujuan ganda. Keputusan nyata sering melibatkan trade-off antara tujuan yang bertentangan—profit vs. risiko, biaya vs. kualitas, efisiensi vs. keadilan. Multi-objective optimization memberi kita Pareto frontier—seperangkat solusi yang tidak dapat diperbaiki dalam satu tujuan tanpa mengorbankan tujuan lain.
Bab 16 akan memperkenalkan kedua topik ini—dan menyiapkan kita untuk Bab 17, di mana kita menggabungkan optimasi dan simulasi untuk keputusan di bawah ketidakpastian.