Pemrograman Linear: Menyelesaikan Masalah Optimisasi Dunia Nyata

Manajer operasional menghadapi tantangan berulang: terlalu banyak keputusan, terlalu banyak kendala, dan tidak ada cara yang jelas untuk menemukan solusi terbaik. Jaringan distribusi perlu meminimalkan biaya bahan bakar di puluhan rute sambil tetap mematuhi jendela pengantaran, kapasitas kendaraan, dan jadwal pengemudi.

Kedua masalah ini memiliki struktur matematis yang sama. Saat tujuan dan kendala Anda dapat dinyatakan sebagai hubungan linear, Anda sedang mengerjakan masalah pemrograman linear. Kita peduli pada pemrograman linear karena metode ini menemukan solusi optimal saat Anda bekerja dengan sumber daya terbatas dan persyaratan yang saling bertentangan.

Kekuatan pemrograman linear ada pada jaminannya: jika solusi layak ada, algoritma akan menemukan yang optimal. Tentu saja, penerapan dunia nyata jarang persis seperti contoh buku teks, tetapi memahami kerangka inti membantu Anda mengenali kapan optimisasi dapat menggantikan perkiraan.

Panduan ini membawa Anda dari dasar hingga implementasi Python yang dapat dijalankan. Kita akan bergerak dari masalah dua variabel sederhana yang dapat divisualisasikan secara geometri ke skenario kompleks yang memerlukan solusi algoritmik. Anda akan memahami teori matematika yang membuat optimisasi bekerja sekaligus keterampilan praktis untuk mengimplementasikan solusinya sendiri.

Apa Itu Pemrograman Linear?

Pemrograman linear mengoptimalkan fungsi objektif linear dengan subjek kendala linear. Dalam proyek perutean distribusi yang saya kerjakan, tujuannya adalah meminimalkan total jarak tempuh sambil mematuhi kendala seperti kapasitas kendaraan dan jendela waktu pengantaran.

Memahami struktur dasar

Setiap masalah pemrograman linear memiliki tiga komponen: variabel keputusan, fungsi objektif, dan kendala.

Variabel keputusan merepresentasikan pilihan yang Anda buat. Dalam masalah perutean, variabel biner dapat menunjukkan kendaraan mana yang mengunjungi lokasi mana. Dalam perencanaan produksi, variabel dapat merepresentasikan kuantitas manufaktur.

Fungsi objektif menentukan apa yang Anda optimalkan. Fungsi ini harus berupa kombinasi linear dari variabel keputusan Anda. Kendala mendefinisikan aturan dan batasan masalah Anda. Bentuknya ada tiga: persamaan, pertidaksamaan kurang-dari-atau-sama-dengan, atau lebih-besar-dari-atau-sama-dengan.

from scipy.optimize import linprog

c = [10, 15]
A_ub = [[1, 0], [0, 1]]
b_ub = [100, 80]
A_eq = [[1, 1]]
b_eq = [150]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, A_eq=A_eq, b_eq=b_eq, 
                 bounds=bounds, method='highs')

print(f"Optimal solution: Truck 1 = {result.x[0]:.1f}, Truck 2 = {result.x[1]:.1f}")
print(f"Total cost: ${result.fun:.2f}")Didukung oleh

Kode di atas meminimalkan total biaya untuk dua variabel keputusan, dengan subjek batasan individual dan persyaratan cakupan total. Koefisien objektif [10, 15] merepresentasikan biaya per unit, kendala pertidaksamaan membatasi rentang setiap variabel, dan kendala persamaan memastikan cakupan total.

Interpretasi geometri

Memahami pemrograman linear secara geometri mengubah cara saya memandang optimisasi. Setiap kendala mendefinisikan setengah-ruang, dan persilangannya membentuk wilayah layak. Wilayah ini selalu berupa politope cembung, artinya garis apa pun antara dua titik interior tetap berada di dalamnya.

Inilah wawasan pentingnya: solusi optimal selalu terjadi di titik sudut wilayah layak. Bergerak sepanjang sisi akan memperbaiki objektif Anda atau tidak, jadi Anda terus bergerak hingga mencapai sudut. Sifat ini membuat algoritma pemrograman linear efisien.

import numpy as np
import matplotlib.pyplot as plt

x = np.linspace(0, 8, 400)
y1 = (10 - x) / 2
y2 = 12 - 2*x

plt.figure(figsize=(10, 8))
plt.plot(x, y1, 'r-', label='x + 2y ≤ 10', linewidth=2)
plt.plot(x, y2, 'b-', label='2x + y ≤ 12', linewidth=2)

y_feasible = np.minimum(y1, y2)
y_feasible = np.maximum(y_feasible, 0)
plt.fill_between(x, 0, y_feasible, where=(y_feasible >= 0), 
                 alpha=0.3, color='green', label='Feasible region')

vertices = [(0, 0), (0, 5), (14/3, 8/3), (6, 0)]
for v in vertices:
    plt.plot(v[0], v[1], 'ko', markersize=10)
    obj_value = 3*v[0] + 4*v[1]
    plt.annotate(f'({v[0]:.1f}, {v[1]:.1f})\nObj: {obj_value:.1f}',
                 xy=v, xytext=(v[0]+0.3, v[1]+0.3))

plt.xlim(-0.5, 8)
plt.ylim(-0.5, 8)
plt.xlabel('x')
plt.ylabel('y')
plt.legend()
plt.grid(True, alpha=0.3)
plt.title('Geometric View: Optimal Solution at Vertex (4.7, 2.7)')
plt.show()Didukung oleh

Visualisasi ini menunjukkan solusi optimal di titik sudut (4,7, 2,7) tempat dua kendala berpotongan. Wilayah layak yang cembung menjamin tidak ada lembah tersembunyi yang membuat algoritma macet, memastikan optimum lokal sama dengan optimum global.

Mentransformasikan masalah dunia nyata

Bagian tersulit bukan menyelesaikan matematikanya, melainkan menerjemahkan masalah yang berantakan menjadi formulasi yang rapi. Mendefinisikan variabel dan kendala sering memakan waktu lebih lama daripada menjalankan optimisasinya sendiri.

Mendefinisikan variabel keputusan memerlukan identifikasi pilihan yang mendasar. Untuk perutean, Anda dapat menggunakan variabel biner untuk penugasan kendaraan-lokasi, atau menambahkan variabel kontinu untuk urutan kunjungan demi menyederhanakan kendala.

Menyusun kendala berarti menerjemahkan aturan bisnis menjadi pertidaksamaan. Ini mengungkap asumsi tersembunyi. Saat manajer berkata "setiap lokasi perlu satu pengantaran," apakah itu berarti persis satu atau minimal satu? Detail ini mengubah formulasi secara keseluruhan.

Berikut contoh formulasi menggunakan PuLP:

from pulp import *

prob = LpProblem("Food_Bank_Routing", LpMinimize)

trucks = ['Truck_A', 'Truck_B', 'Truck_C']
centers = ['North', 'South', 'East', 'West', 'Central']

x = LpVariable.dicts("route", 
                     [(i, j) for i in trucks for j in centers],
                     cat='Binary')

distances = {
    ('Truck_A', 'North'): 15, ('Truck_A', 'South'): 20,
    ('Truck_A', 'East'): 10, ('Truck_A', 'West'): 25,
    ('Truck_A', 'Central'): 5,
    ('Truck_B', 'North'): 18, ('Truck_B', 'South'): 15,
    ('Truck_B', 'East'): 12, ('Truck_B', 'West'): 22,
    ('Truck_B', 'Central'): 8,
    ('Truck_C', 'North'): 20, ('Truck_C', 'South'): 25,
    ('Truck_C', 'East'): 15, ('Truck_C', 'West'): 18,
    ('Truck_C', 'Central'): 10,
}

prob += lpSum([distances[i, j] * x[i, j] 
               for i in trucks for j in centers])

for j in centers:
    prob += lpSum([x[i, j] for i in trucks]) == 1

max_stops = {'Truck_A': 3, 'Truck_B': 2, 'Truck_C': 3}
for i in trucks:
    prob += lpSum([x[i, j] for j in centers]) <= max_stops[i]

prob.solve()

print(f"Status: {LpStatus[prob.status]}")
print(f"Total distance: {value(prob.objective)} miles")
for i in trucks:
    route = [j for j in centers if value(x[i, j]) == 1]
    print(f"{i} visits: {', '.join(route)}")Didukung oleh

Formulasi di atas menggunakan variabel biner untuk penugasan truk-pusat, meminimalkan total jarak, memastikan setiap pusat mendapatkan tepat satu pengantaran, dan menghormati batas kapasitas truk.

Pola masalah klasik menyediakan templat. Masalah diet meminimalkan biaya sambil memenuhi kebutuhan nutrisi. Masalah transportasi meminimalkan biaya pengiriman. Yang satu ini langsung saya terapkan pada tantangan perutean saya sendiri. Mengenali pola ini mempercepat formulasi karena jarang sekali Anda menyelesaikan masalah yang benar-benar baru.

Pemrograman linear menemukan solusi optimal di titik sudut wilayah layak yang ditentukan oleh kendala. Gambar oleh Penulis

Metode Solusi dan Pendekatan Algoritmik

Memahami cara kerja algoritma mengubah apresiasi saya saat memanggil linprog(). Ini bukan kotak hitam, melainkan prosedur matematika yang elegan.

Algoritma simplex

Algoritma simplex, dikembangkan oleh George Dantzig pada 1947, adalah titik awal. Wawasannya: menelusuri secara sistematis dari satu titik sudut ke titik sudut yang berdekatan, selalu meningkatkan objektif, hingga mencapai optimum.

Algoritma mempertahankan sebuah tabel (tableau) dan melakukan operasi pivot untuk berpindah antar titik sudut. Setiap iterasi meningkatkan objektif atau menentukan optimalitas dengan memilih elemen pivot dan memperbarui melalui operasi baris.

from scipy.optimize import linprog
import numpy as np

c = [-3, -2]
A_ub = [[2, 1], [2, 3], [3, 1]]
b_ub = [18, 42, 24]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Optimal solution: x1 = {result.x[0]:.2f}, x2 = {result.x[1]:.2f}")
print(f"Maximum value: {-result.fun:.2f}")
print(f"Iterations: {result.nit}")Didukung oleh

Kode di atas menunjukkan cara menyelesaikan masalah maksimisasi dengan metode simplex dengan menegasikan koefisien objektif. Solver bergerak secara sistematis antar titik sudut wilayah layak yang ditentukan oleh kendala, mencapai solusi optimal hanya dalam beberapa iterasi. Pada masalah yang lebih besar, metode simplex dapat menemukan optimum dalam jauh lebih sedikit langkah dibanding jumlah titik sudut layak, sering kali di bawah 20 iterasi bahkan dengan ribuan kemungkinan.

Metode titik interior

Sementara simplex menelusuri batas, metode titik interior menavigasi melalui interior wilayah layak. Untuk masalah optimisasi portofolio besar dengan ratusan aset, simplex bisa melambat sementara metode titik interior menyelesaikannya dalam hitungan detik.

Keunggulan kuncinya adalah kompleksitas waktu polinomial. Algoritma Karmarkar (1984) membuat metode titik interior praktis, menyeimbangkan perbaikan objektif dengan tetap jauh dari batas kendala. Solver modern seperti Gurobi secara otomatis memilih antara simplex dan titik interior berdasarkan karakteristik masalah.

Metode grafis untuk dua variabel

Untuk masalah dua variabel, saya selalu menyelesaikannya secara grafis terlebih dahulu. Ini membangun intuisi yang dapat ditransfer ke dimensi lebih tinggi. Plot kendala, identifikasi wilayah layak, dan temukan sudut mana yang mengoptimalkan objektif.

from scipy.optimize import linprog

c = [-30, -40]
A_ub = [[2, 1], [1, 2]]
b_ub = [100, 80]
bounds = [(0, None), (0, None)]

result = linprog(c, A_ub=A_ub, b_ub=b_ub, bounds=bounds, method='highs')

print(f"Bread loaves: {result.x[0]:.0f}")
print(f"Cakes: {result.x[1]:.0f}")
print(f"Maximum profit: ${-result.fun:.0f}")Didukung oleh

Masalah produksi toko roti ini memaksimalkan keuntungan dari roti dan kue, dengan subjek batasan jam oven dan dekorasi. Solusinya mengungkap titik sudut mana yang optimal secara geometri, membuat perilaku lompatan antar titik sudut dari algoritma menjadi nyata.

Aplikasi di Berbagai Industri

Pemrograman linear menerapkan kerangka matematika yang sama untuk menyelesaikan masalah di berbagai domain yang sangat berbeda.

Manufaktur dan produksi

Perencanaan produksi adalah aplikasi serius pertama saya. Masalah bauran produksi menentukan kuantitas manufaktur, dengan variabel merepresentasikan produksi, objektif memaksimalkan keuntungan, dan kendala menangkap keterbatasan sumber daya.

from pulp import *

products = ['Phone', 'Tablet', 'Laptop']

profits = {'Phone': 120, 'Tablet': 200, 'Laptop': 350}
assembly_time = {'Phone': 2, 'Tablet': 3, 'Laptop': 5}
testing_time = {'Phone': 1, 'Tablet': 1.5, 'Laptop': 2}

assembly_available = 500
testing_available = 200
min_production = {'Phone': 50, 'Tablet': 30, 'Laptop': 20}

model = LpProblem("Production_Planning", LpMaximize)
production = LpVariable.dicts("produce", products, lowBound=0, cat='Integer')

model += lpSum([profits[p] * production[p] for p in products])
model += lpSum([assembly_time[p] * production[p] for p in products]) <= assembly_available
model += lpSum([testing_time[p] * production[p] for p in products]) <= testing_available

for p in products:
    model += production[p] >= min_production[p]

model.solve()

print(f"Status: {LpStatus[model.status]}")
for p in products:
    print(f"{p}: {production[p].varValue:.0f} units")
print(f"Total profit: ${value(model.objective):,.0f}")Didukung oleh

Model di atas mengoptimalkan produksi elektronik di tiga lini produk, menyeimbangkan kapasitas perakitan dan pengujian dengan persyaratan produksi minimum.

Masalah pencampuran mengoptimalkan campuran yang memenuhi spesifikasi dengan biaya minimum, misalnya mencampur bahan makanan untuk memenuhi kebutuhan nutrisi sambil meminimalkan biaya.

Transportasi dan logistik

Masalah transportasi adalah contoh yang banyak dipelajari. Strukturnya yang klasik memiliki sumber dengan pasokan dan tujuan dengan permintaan, meminimalkan total biaya pengiriman.

warehouses = ['Warehouse_A', 'Warehouse_B', 'Warehouse_C']
supply = {'Warehouse_A': 300, 'Warehouse_B': 400, 'Warehouse_C': 200}

customers = ['Customer_1', 'Customer_2', 'Customer_3', 'Customer_4']
demand = {'Customer_1': 200, 'Customer_2': 150, 'Customer_3': 250, 'Customer_4': 200}

costs = {
    ('Warehouse_A', 'Customer_1'): 8,  ('Warehouse_A', 'Customer_2'): 6,
    ('Warehouse_A', 'Customer_3'): 10, ('Warehouse_A', 'Customer_4'): 7,
    ('Warehouse_B', 'Customer_1'): 9,  ('Warehouse_B', 'Customer_2'): 12,
    ('Warehouse_B', 'Customer_3'): 8,  ('Warehouse_B', 'Customer_4'): 11,
    ('Warehouse_C', 'Customer_1'): 14, ('Warehouse_C', 'Customer_2'): 7,
    ('Warehouse_C', 'Customer_3'): 10, ('Warehouse_C', 'Customer_4'): 12,
}

model = LpProblem("Transportation", LpMinimize)

routes = [(w, c) for w in warehouses for c in customers]
shipments = LpVariable.dicts("ship", routes, lowBound=0)

model += lpSum([costs[i, j] * shipments[i, j] for (i, j) in routes])

for w in warehouses:
    model += lpSum([shipments[w, c] for c in customers]) <= supply[w]

for c in customers:
    model += lpSum([shipments[w, c] for w in warehouses]) >= demand[c]

model.solve()Didukung oleh

Masalah aliran jaringan menggeneralisasi transportasi ke graf dengan simpul transit. Saya membaca bahwa maskapai banyak menggunakannya untuk penjadwalan kru dan perutean pesawat.

Layanan keuangan dan kesehatan

Dalam aplikasi keuangan, penganggaran modal memilih proyek yang memaksimalkan imbal hasil dengan subjek kendala anggaran:

projects = {
    'Project_A': {'return': 25000, 'cost': 100000, 'staff': 5},
    'Project_B': {'return': 30000, 'cost': 150000, 'staff': 7},
    'Project_C': {'return': 20000, 'cost': 80000, 'staff': 4},
}

budget = 300000
staff_available = 15

model = LpProblem("Capital_Budgeting", LpMaximize)
select = LpVariable.dicts("select", projects.keys(), cat='Binary')

model += lpSum([projects[p]['return'] * select[p] for p in projects])
model += lpSum([projects[p]['cost'] * select[p] for p in projects]) <= budget
model += lpSum([projects[p]['staff'] * select[p] for p in projects]) <= staff_available

model.solve()Didukung oleh

Sistem kesehatan menghadapi tantangan optimisasi tanpa akhir. Saya pernah berkonsultasi untuk masalah penjadwalan klinik yang menugaskan perawat ke shift sambil menghormati persyaratan keterampilan dan keseimbangan beban kerja.

Aplikasi teknologi modern

Pemrograman linear juga muncul secara tak terduga dalam pembelajaran mesin. Pemilihan fitur dapat diformulasikan sebagai meminimalkan galat dengan subjek kendala kejarangan. Komputasi awan menggunakannya untuk alokasi sumber daya di sistem terdistribusi.

Kompleksitas Komputasional dan Kinerja

Kompleksitas menjadi penting saat masalah meningkat dari contoh sederhana ke sistem produksi.

Kompleksitas algoritma simplex

Simplex memiliki tingkat kompleksitas yang menarik. Terburuknya bersifat eksponensial namun kinerja rata-ratanya sangat baik. Kasus patologis seperti kubus Klee-Minty memaksanya memeriksa setiap titik sudut, tetapi masalah tipikal hanya memeriksa sebagian kecil, dengan skala kira-kira kuadratik.

Saya mengujinya dengan menyelesaikan masalah yang dihasilkan secara acak dengan ukuran yang meningkat:

import time
import numpy as np
from scipy.optimize import linprog

def benchmark_simplex(num_vars, num_constraints):
    c = np.random.randn(num_vars)
    A_ub = np.random.randn(num_constraints, num_vars)
    b_ub = np.random.rand(num_constraints) * 10
    
    start = time.time()
    result = linprog(c, A_ub=A_ub, b_ub=b_ub, method='simplex')
    elapsed = time.time() - start
    
    return elapsed, result.nit

problem_sizes = [(10, 20), (50, 100), (100, 200), (200, 400)]

for n_vars, n_const in problem_sizes:
    times, iterations = [], []
    for _ in range(10):
        t, it = benchmark_simplex(n_vars, n_const)
        times.append(t)
        iterations.append(it)
    print(f"{n_vars}x{n_const}: {np.mean(times):.4f}s, {np.mean(iterations):.1f} iterations")Didukung oleh

Benchmark saya menunjukkan bahwa menggandakan ukuran masalah meningkatkan waktu kurang dari 4x, mengonfirmasi perilaku mendekati polinomial untuk distribusi tipikal.

Peningkatan kinerja

Solver modern mencapai kinerja luar biasa melalui prapemrosesan, pemrosesan paralel, dan pemilihan algoritma otomatis. Prapemrosesan dapat mengurangi ukuran masalah 30% atau lebih secara otomatis sebelum penyelesaian.

Degenerasi terjadi saat beberapa kendala ketat pada optimum, yang berpotensi menyebabkan siklus. Saya mengalaminya ketika dua rute memiliki biaya identik. Solver menggunakan teknik gangguan (perturbation) untuk menghindari siklus, meskipun masalah degenerat diselesaikan lebih lambat.

Ketidakstabilan numerik muncul pada masalah yang skala angkanya buruk. Mencampur jumlah moneter (ribuan dolar) dengan kuantitas (satuan) menyebabkan peringatan solver. Mengubah skala langsung memperbaikinya.

Perbandingan kinerja solver: solusi komersial unggul pada masalah skala besar. Gambar oleh Penulis

Perangkat Lunak dan Implementasi

Pilihan alat sangat memengaruhi produktivitas. Saya berkembang dari menulis simplex secara manual hingga menggunakan solver profesional yang menangani masalah jauh lebih besar.

Solver komersial dan bahasa pemodelan

CPLEX dan Gurobi mendominasi optimisasi industri, menawarkan kinerja berlipat ganda lebih baik daripada alternatif sumber terbuka untuk masalah besar. Saya menggunakan lisensi akademik Gurobi untuk pekerjaan rantai pasok. Masalah yang memakan waktu menit dengan SciPy terselesaikan dalam hitungan detik.

PuLP adalah andalan saya di Python. Perpustakaan ini menyediakan API bersih untuk merumuskan model yang dapat diselesaikan oleh berbagai backend:

from pulp import *

model = LpProblem("my_problem", LpMaximize)

x = LpVariable("x", lowBound=0)
y = LpVariable("y", lowBound=0)

model += 3*x + 2*y
model += x + y <= 100
model += 2*x + y <= 150

model.solve()

print(f"Used solver: {model.solver}")
print(f"Status: {LpStatus[model.status]}")Didukung oleh

Lapisan abstraksi ini membuat kode bebas ketergantungan solver yang dapat berjalan di sistem berbeda. Pyomo menawarkan fitur lebih lanjut untuk optimisasi kompleks, termasuk pemrograman nonlinier dan stokastik.

Alternatif cloud dan sumber terbuka

Platform cloud menawarkan optimization-as-a-service untuk masalah besar yang tidak rutin. Anda mengunggah data masalah dan menerima solusi melalui API. Arsitektur tanpa server ini elegan meski lebih lambat daripada solver lokal untuk masalah kecil.

GLPK (GNU Linear Programming Kit) adalah andalan sumber terbuka yang andal. Saya menggunakannya untuk pengajaran dan proyek pribadi. HiGHS adalah solver baru yang menunjukkan kinerja mengesankan. SciPy baru-baru ini mengadopsi HiGHS sebagai backend default, dan benchmark saya menunjukkan hasilnya menyaingi Gurobi pada banyak masalah.

Contoh Pemrograman Linear

Mengerjakan contoh lengkap membangun pemahaman lebih baik daripada teori semata.

Contoh 1: Masalah diet

Masalah diet klasik meminimalkan biaya sambil memenuhi kebutuhan nutrisi:

from pulp import *

foods = {
    'Oatmeal': {'cost': 0.50, 'calories': 110, 'protein': 4, 'vitamin': 2},
    'Chicken': {'cost': 2.50, 'calories': 250, 'protein': 30, 'vitamin': 0},
    'Eggs':    {'cost': 0.80, 'calories': 155, 'protein': 13, 'vitamin': 1},
    'Milk':    {'cost': 1.20, 'calories': 150, 'protein': 8, 'vitamin': 4},
    'Bread':   {'cost': 0.30, 'calories': 80, 'protein': 3, 'vitamin': 0}
}

min_calories, min_protein, min_vitamin = 2000, 50, 10

model = LpProblem("Diet_Optimization", LpMinimize)
servings = LpVariable.dicts("servings", foods.keys(), lowBound=0)

model += lpSum([foods[f]['cost'] * servings[f] for f in foods])
model += lpSum([foods[f]['calories'] * servings[f] for f in foods]) >= min_calories
model += lpSum([foods[f]['protein'] * servings[f] for f in foods]) >= min_protein
model += lpSum([foods[f]['vitamin'] * servings[f] for f in foods]) >= min_vitamin

model.solve()

print(f"Total cost: ${value(model.objective):.2f}")
for food in foods:
    if servings[food].varValue > 0.01:
        print(f"{food}: {servings[food].varValue:.2f} servings")Didukung oleh

Formulasi di atas menemukan kombinasi makanan termurah yang memenuhi kebutuhan nutrisi harian. Ini menunjukkan bahwa solusi LP optimal tidak selalu praktis tanpa kendala tambahan untuk variasi, selera, atau preferensi diet.

Kerangka yang sama juga dapat menjadi dasar keputusan bisnis seperti mengoptimalkan jadwal produksi atau mengalokasikan anggaran pemasaran.

Contoh 2: Perencanaan multi-periode

Perencanaan multi-periode mempertimbangkan bagaimana tingkat persediaan memengaruhi kebutuhan masa depan di beberapa periode waktu:

days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']

centers = {
    'North': {'daily_demand': [100, 80, 90, 110, 85], 'capacity': 250},
    'South': {'daily_demand': [120, 100, 95, 105, 130], 'capacity': 300},
}

delivery_cost = {'Monday': 50, 'Tuesday': 50, 'Wednesday': 50,
                 'Thursday': 50, 'Friday': 70}

model = LpProblem("Multiperiod_Routing", LpMinimize)

deliveries = LpVariable.dicts("deliver",
                              [(c, d) for c in centers for d in days],
                              lowBound=0)
inventory = LpVariable.dicts("inventory",
                            [(c, d) for c in centers for d in days],
                            lowBound=0)

model += lpSum([delivery_cost[d] * deliveries[c, d] 
                for c in centers for d in days])

for c in centers:
    for i, day in enumerate(days):
        if i == 0:
            model += inventory[c, day] == deliveries[c, day] - centers[c]['daily_demand'][i]
        else:
            prev_day = days[i-1]
            model += (inventory[c, day] == inventory[c, prev_day] + 
                     deliveries[c, day] - centers[c]['daily_demand'][i])
        model += inventory[c, day] <= centers[c]['capacity']

model.solve()Didukung oleh

Model multi-periode meningkatkan ukuran masalah namun membuka optimisasi yang lebih canggih. Model ini mengkonsolidasikan pengantaran pada hari yang lebih murah, menggunakan kapasitas penyimpanan untuk menurunkan biaya keseluruhan.

Pemrograman Integer Campuran

Banyak masalah melibatkan keputusan diskret: membangun fasilitas atau tidak, menugaskan pekerja atau tidak. Ini memerlukan pemrograman integer campuran (MIP), memperluas pemrograman linear dengan variabel integer dan biner.

Pengantar dan branch-and-bound

Masalah perutean memerlukan keputusan integer. Variabel biner x[i][j] menunjukkan apakah kendaraan i mengunjungi lokasi j. Kendaraan tidak bisa melakukan kunjungan fraksional.

Branch-and-bound menelusuri ruang solusi diskret secara sistematis dengan menyelesaikan relaksasi LP kontinu:

from pulp import *

model_continuous = LpProblem("Continuous", LpMaximize)
x_cont = LpVariable("x", lowBound=0)
y_cont = LpVariable("y", lowBound=0)

model_continuous += 3*x_cont + 4*y_cont
model_continuous += x_cont + 2*y_cont <= 10
model_continuous += 2*x_cont + y_cont <= 12

model_continuous.solve()
print(f"Continuous: x={x_cont.varValue:.2f}, y={y_cont.varValue:.2f}")

model_integer = LpProblem("Integer", LpMaximize)
x_int = LpVariable("x", lowBound=0, cat='Integer')
y_int = LpVariable("y", lowBound=0, cat='Integer')

model_integer += 3*x_int + 4*y_int
model_integer += x_int + 2*y_int <= 10
model_integer += 2*x_int + y_int <= 12

model_integer.solve()
print(f"Integer: x={x_int.varValue:.0f}, y={y_int.varValue:.0f}")Didukung oleh

Solusi integer berbeda dari hasil pembulatan solusi kontinu. Branch-and-bound menemukan solusi integer optimal, tetapi dengan biaya komputasi yang jauh lebih tinggi.

Kapan menggunakan pemrograman integer

Gunakan variabel integer saat keputusan bersifat intrinsik diskret: membuka fasilitas, menugaskan pekerja, perutean kendaraan. Optimisasi di pasar obligasi sering memerlukan solusi integer campuran. Variabel kontinu dapat menghasilkan penugasan fraksional yang tidak masuk akal, sementara variabel biner menghasilkan solusi yang dapat diimplementasikan.

Namun, pemrograman integer jauh lebih mahal. Masalah dengan ratusan variabel integer dapat memakan waktu berjam-jam dibanding detik untuk LP kontinu. Jika kuantitas produksi besar, integrality kurang penting karena pembulatan nyaris tidak memengaruhi solusi. Selalu selesaikan relaksasi kontinu terlebih dahulu untuk memeriksa batas sebelum beralih ke pemrograman integer penuh.

Kesimpulan

Pemrograman linear mengubah cara Anda menghadapi masalah optimisasi. Kerangka matematika yang sama berlaku di berbagai domain yang sangat berbeda, dari perutean hingga perencanaan produksi hingga manajemen portofolio.

Mulailah dengan masalah dua variabel sederhana yang dapat Anda visualisasikan secara geometri. Implementasikan simplex dasar untuk memahami apa yang dilakukan solver komersial di balik layar. Kerjakan formulasi nyata, menerjemahkan persyaratan bisnis menjadi kendala matematika.

Untuk memperdalam keahlian Anda, jelajahi kursus Introduction to Optimization in Python dan Linear Algebra for Data Science kami untuk memperkuat dasar matematika Anda. Machine Learning Scientist di jalur karier Python kami juga merupakan pilihan yang bagus.