Doğrusal Programlama: Gerçek Dünya Optimizasyon Problemlerini Çözmek

Operasyon yöneticileri yinelenen bir zorlukla karşı karşıya: çok fazla karar, çok fazla kısıt ve en iyi çözümü bulmanın bariz bir yolu yok. Bir dağıtım ağı, teslimat zaman pencerelerine, araç kapasitelerine ve sürücü programlarına uyarak düzinelerce rota arasında yakıt maliyetlerini en aza indirmelidir.

Bu iki problem ortak bir matematiksel yapıyı paylaşır. Amaçlarınız ve kısıtlarınız doğrusal ilişkilerle ifade edilebiliyorsa, doğrusal programlama problemiyle çalışıyorsunuz demektir. Doğrusal programlamayı önemsiyoruz çünkü sınırlı kaynaklar ve birbiriyle yarışan gereksinimlerle çalışırken optimal çözümler bulur.

Doğrusal programlamayı güçlü kılan şey vaadidir: uygulanabilir bir çözüm varsa, algoritma optimal olanı bulur. Elbette, gerçek dünya uygulamaları nadiren ders kitabı örneklerine kusursuzca uyar, ancak temel çerçeveyi anlamak, ne zaman sezgisel tahmin yerine optimizasyon kullanabileceğinizi fark etmenize yardımcı olur.

Bu rehber sizi temellerden çalışan Python uygulamalarına götürür. Geometrik olarak görselleştirebileceğiniz iki değişkenli basit problemlerden, algoritmik çözümler gerektiren karmaşık senaryolara ilerleyeceğiz. Optimizasyonun nasıl çalıştığını açıklayan matematiksel teoriyi ve çözümleri kendiniz uygulamak için gerekli pratik becerileri anlayacaksınız.

Doğrusal Programlama Nedir?

Doğrusal programlama, doğrusal kısıtlar altında doğrusal bir amaç fonksiyonunu optimize eder. Üzerinde çalıştığım bir dağıtım rotalama projesinde hedef, araç kapasitesi ve teslimat zaman pencereleri gibi kısıtlara uyarak toplam sürüş mesafesini en aza indirmekti.

Temel yapıyı anlamak

Her doğrusal programlama probleminin üç bileşeni vardır: karar değişkenleri, bir amaç fonksiyonu ve kısıtlar.

Karar değişkenleri, verdiğiniz seçimleri temsil eder. Rotalama problemlerinde, ikili değişkenler hangi aracın hangi lokasyonu ziyaret ettiğini gösterebilir. Üretim planlamasında, değişkenler üretim miktarlarını temsil edebilir.

Amaç fonksiyonu, neyi optimize ettiğinizi tanımlar. Karar değişkenlerinizin doğrusal bir kombinasyonu olmalıdır. Kısıtlar, probleminizin kurallarını ve sınırlamalarını tanımlar. Üç biçimdedirler: eşitlikler, küçük-eşit veya büyük-eşit eşitsizlikler.

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}")Altyapı:

Yukarıdaki kod, iki karar değişkeni için, bireysel sınırlar ve toplam kapsama gereksinimi altında toplam maliyeti en aza indirir. Amaç katsayıları [10, 15] birim başına maliyeti temsil eder, eşitsizlik kısıtları her değişkenin aralığını sınırlar ve eşitlik kısıtı toplam kapsama alanını garanti eder.

Geometrik yorum

Doğrusal programlamayı geometrik olarak anlamak, optimizasyon hakkındaki düşüncemi dönüştürdü. Her kısıt bir yarı-uzayı tanımlar ve bunların kesişimi uygulanabilir bölgeyi oluşturur. Bu bölge her zaman bir konveks politop'tur; yani içteki iki nokta arasındaki herhangi bir doğru parçası içerde kalır.

İşte kritik içgörü: optimal çözümler her zaman uygulanabilir bölgenin köşelerinde ortaya çıkar. Bir kenar boyunca ilerlemek ya amacınızı iyileştirir ya da iyileştirmez; bu yüzden bir köşeye çarpana kadar ilerlemeye devam edersiniz. Bu özellik, doğrusal programlama algoritmalarını verimli kılar.

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()Altyapı:

Bu görselleştirme, iki kısıtın kesiştiği (4.7, 2.7) köşesindeki optimal çözümü gösterir. Konveks uygulanabilir bölge, algoritmaların takılıp kalabileceği gizli vadilerin olmadığını garanti eder; yerel optimumların küresel optimumlara eşit olmasını sağlar.

Gerçek dünya problemlerini dönüştürmek

En zor kısım matematiği çözmek değil, dağınık problemleri temiz formülasyonlara çevirmektir. Değişkenleri ve kısıtları tanımlamak genellikle optimizasyonun çalıştırılmasından daha uzun sürer.

Karar değişkenlerini tanımlamak, temel seçimleri belirlemeyi gerektirir. Rotalama için, araç-lokasyon atamaları için ikili değişkenler kullanabilir ya da kısıtları basitleştirmek için ziyaret sıralaması için sürekli değişkenler ekleyebilirsiniz.

Kısıtlar oluşturmak, iş kurallarını eşitsizliklere çevirmek demektir. Bu da gizli varsayımları ortaya çıkarır. Bir yönetici "her konum bir teslimat gerektirir" dediğinde, bu tam olarak bir mi demek yoksa en az bir mi? Bu ayrıntılar formülasyonu tamamen değiştirir.

İşte PuLP kullanılarak yapılmış örnek bir formülasyon:

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)}")Altyapı:

Yukarıdaki formülasyon, kamyon-merkez atamaları için ikili değişkenler kullanır, toplam mesafeyi en aza indirir, her merkezin tam olarak bir teslimat almasını sağlar ve kamyon kapasite sınırlarına uyar.

Klasik problem kalıpları şablonlar sunar. Diyet problemi beslenme gereksinimlerini karşılarken maliyeti en aza indirir. Taşıma problemleri nakliye maliyetlerini en aza indirir. Bu kalıp, kendi rotalama zorluğuma doğrudan uygulanmıştı. Bu kalıpları tanımak, nadiren gerçekten yeni problemler çözdüğünüz için formülasyonu hızlandırır.

Doğrusal programlama, kısıtların tanımladığı uygulanabilir bölgelerin köşelerinde optimal çözümleri bulur. Görsel: Yazar

Çözüm Yöntemleri ve Algoritmik Yaklaşımlar

Algoritmaların nasıl çalıştığını anlamak, linprog() çağrısına bakışımı değiştirdi. Bunlar kara kutular değil, zarif matematiksel prosedürler.

Simplex algoritması

1947'de George Dantzig tarafından geliştirilen simplex algoritması başlangıç noktasıdır. İçgörüsü: düzenli biçimde bir köşeden komşu köşeye geçerek, her seferinde amacı iyileştirip optimuma ulaşana kadar ilerlemek.

Algoritma bir tabloyu (tableau) tutar ve köşeler arasında hareket etmek için pivot işlemleri uygular. Her yineleme, bir pivot elemanı seçip satır işlemleriyle güncelleyerek amacı iyileştirir ya da optimalliği belirler.

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}")Altyapı:

Yukarıdaki kod, amaç katsayılarını negatifleyerek simplex yöntemiyle bir maksimizasyon probleminin çözümünü gösterir. Çözücü, kısıtların tanımladığı uygulanabilir bölgenin köşeleri arasında sistematik olarak ilerler ve sadece birkaç yinelemede optimal çözüme ulaşır. Daha büyük problemler için simplex, uygulanabilir köşe sayısından çok daha az adımda, çoğu zaman binlerce olasılık olsa bile 20'den az yinelemeyle optimumu bulabilir.

İç nokta yöntemleri

Simplex sınırlar boyunca ilerlerken, iç nokta yöntemleri uygulanabilir bölgenin içinden gezinir. Yüzlerce varlığa sahip büyük portföy optimizasyonlarında, simplex yavaşlayabilirken iç nokta yöntemleri saniyeler içinde çözebilir.

Temel avantaj, polinomsal zaman karmaşıklığıdır. Karmarkar'ın algoritması (1984) iç nokta yöntemlerini pratik hale getirdi; amacı iyileştirirken kısıt sınırlarından uzak kalmayı dengeler. Gurobi gibi modern çözücüler, problem özelliklerine göre simplex ve iç nokta arasında otomatik seçim yapar.

İki değişken için grafiksel yöntem

İki değişkenli problemleri önce daima grafiksel olarak çözerim. Bu, daha yüksek boyutlara aktarılan bir sezgi oluşturur. Kısıtları çizin, uygulanabilir bölgeyi belirleyin ve hangi köşenin amacı optimize ettiğini bulun.

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}")Altyapı:

Bu fırın üretim problemi, fırın ve süsleme saatleri sınırları altında ekmek ve kekten elde edilen kârı maksimize eder. Çözüm, hangi köşe noktasının geometrik olarak optimal olduğunu ortaya koyar ve algoritmanın köşeden köşeye sıçrama davranışını somutlaştırır.

Sektörler Arası Uygulamalar

Doğrusal programlama, çok farklı alanlardaki problemleri çözmek için aynı matematiksel çerçeveyi uygular.

Üretim ve imalat

Üretim planlaması ilk ciddi uygulamamdı. Ürün karması problemi, üretim miktarlarını belirler; değişkenler üretimi temsil eder, amaçlar kârı maksimize eder ve kısıtlar kaynak sınırlamalarını yakalar.

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}")Altyapı:

Yukarıdaki model, üç ürün hattı boyunca elektronik üretimini optimize eder; montaj ve test kapasitesini asgari üretim gereksinimleriyle dengeler.

Harmanlama problemleri, maliyeti en aza indirirken şartnameleri karşılayan karışımları optimize eder; örneğin, beslenme gereksinimlerini karşılarken maliyeti minimize eden gıda harmanları.

Taşımacılık ve lojistik

Taşıma problemi bir diğer iyi incelenmiş örnektir. Klasik yapıda arzı olan kaynaklar ve talebi olan varış noktaları bulunur; amaç toplam nakliye maliyetini en aza indirmektir.

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()Altyapı:

Ağ akışı problemleri, taşımayı, aktarım düğümlerine sahip grafiklere geneller. Havayollarının bunu mürettebat çizelgeleme ve uçak rotalaması için kapsamlı biçimde kullandığını okudum.

Finansal hizmetler ve sağlık

Finansal uygulamalarda, sermaye bütçeleme, bütçe kısıtları altında getiriyi maksimize edecek projeleri seçer:

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()Altyapı:

Sağlık sistemleri bitmek bilmeyen optimizasyon zorluklarıyla karşılaşır. Becerileri ve iş yükü dengesini gözeterek hemşireleri vardiyalara atayan bir klinik çizelgeleme probleminde danışmanlık yaptım.

Modern teknoloji uygulamaları

Doğrusal programlama, makine öğrenimi içinde de beklenmedik şekilde karşımıza çıkar. Özellik seçimi, seyrekliğe ilişkin kısıtlar altında tahmin hatasını minimize edecek şekilde formüle edilebilir. Bulut bilişim, dağıtık sistemler genelinde kaynak tahsisi için bunu kullanır.

Hesaplama Karmaşıklığı ve Performans

Karmaşıklık, problemler oyuncak örneklerden üretim sistemlerine ölçeklendiğinde önem kazanır.

Simplex algoritması karmaşıklığı

Simplex'in büyüleyici bir karmaşıklık seviyesi vardır. En kötü durumda üstel, ancak ortalama durumda mükemmel performans gösterir. Klee-Minty küpü gibi patolojik vakalar her köşeyi incelemeye zorlar, fakat tipik problemler yalnızca küçük bir kısmını inceler; yaklaşık olarak karesel ölçeklenir.

Bunu, boyutu artan rastgele üretilmiş problemleri çözerek test ettim:

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")Altyapı:

Karşılaştırmalarım, problem boyutunun iki katına çıkmasının sürede 4 kattan daha az artışa yol açtığını gösterdi; bu da tipik dağılımlar için polinomiyale yakın davranışı doğrular.

Performans iyileştirmeleri

Modern çözücüler, ön işleme, paralel işleme ve otomatik algoritma seçimiyle dikkat çekici performans elde eder. Ön işleme, çözmeden önce problem boyutunu otomatik olarak yüzde 30 veya daha fazla azaltabilir.

Dejenerasyon, optimumda birden fazla kısıtın eşit derecede sıkı olduğu durumlarda meydana gelir ve döngüye neden olabilir. İki rotanın aynı maliyete sahip olduğu bir durumda bununla karşılaştım. Çözücüler döngüyü önlemek için pertürbasyon teknikleri kullanır; yine de dejenere problemler daha yavaş çözülebilir.

Sayısal dengesizlik, kötü ölçeklendirilmiş problemlerle ortaya çıkar. Parasal tutarları (binlerce dolar) adetlerle (birkaç birim) karıştırmak çözücü uyarılarına yol açtı. Yeniden ölçeklendirme bunu anında çözdü.

Çözücü performans karşılaştırması: ticari çözümler büyük ölçekli problemler üzerinde üstün. Görsel: Yazar

Yazılım Araçları ve Uygulama

Araç seçimi, üretkenliği dramatik biçimde etkiler. El ile simplex kodlamaktan, çok daha büyük problemleri ele alan profesyonel çözücüler kullanmaya geçtim.

Ticari çözücüler ve modelleme dilleri

CPLEX ve Gurobi endüstriyel optimizasyona hakimdir; büyük problemler için açık kaynak alternatiflerinden kat kat daha iyi performans sunarlar. Tedarik zinciri çalışmalarımda Gurobi'nin akademik lisansını kullandım. SciPy ile dakikalar süren problemler saniyelerde çözüldü.

PuLP Python'da ilk tercihim. Çeşitli arka uçlar tarafından çözülen modelleri formüle etmek için temiz bir API sunar:

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]}")Altyapı:

Soyutlama katmanı, farklı sistemlerde çalışan çözücüden bağımsız kod anlamına gelir. Pyomo, doğrusal olmayan ve stokastik programlama dahil karmaşık optimizasyonlar için daha gelişmiş özellikler sunar.

Bulut ve açık kaynak alternatifleri

Bulut platformları, düzensiz büyük ölçekli problemler için hizmet olarak optimizasyon sunar. Problem verilerini yüklersiniz ve çözümü API üzerinden alırsınız. Sunucusuz mimari zariftir; ancak küçük problemler için yerel çözücülerden daha yavaştır.

GLPK (GNU Linear Programming Kit) güvenilir bir açık kaynak iş atıdır. Öğretimde ve kişisel projelerde kullanırım. HiGHS, etkileyici performans gösteren daha yeni bir çözücüdür. SciPy yakın zamanda HiGHS'i varsayılan arka ucu olarak benimsedi ve karşılaştırmalarım, birçok problemde Gurobi ile başa baş olduğunu gösterdi.

Doğrusal Programlama Örnekleri

Tam örnekler üzerinde çalışmak, tek başına teoriden daha iyi bir anlayış kazandırır.

Örnek 1: Diyet problemi

Klasik diyet problemi, beslenme gereksinimlerini karşılarken maliyeti minimize eder:

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")Altyapı:

Yukarıdaki formülasyon, günlük beslenme gereksinimlerini karşılayan en ucuz gıda kombinasyonunu bulur. Bu, ek çeşitlilik, lezzet veya diyet tercihi kısıtları getirilmedikçe optimal DP çözümlerinin her zaman pratik olmayabileceğini gösterir.

Aynı çerçeve, üretim programlarını optimize etmek veya pazarlama bütçelerini tahsis etmek gibi iş kararları için de temel oluşturabilir.

Örnek 2: Çok dönemli planlama

Çok dönemli planlama, stok seviyelerinin birden çok zaman diliminde gelecekteki ihtiyaçları nasıl etkilediğini dikkate alır:

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()Altyapı:

Çok dönemli modeller problem boyutunu artırır ancak gelişmiş optimizasyon imkânı sunar. Model, daha ucuz günlerde teslimatları birleştirir; depo kapasitesini kullanarak toplam maliyeti düşürür.

Karma Tamsayılı Programlama

Birçok problem ayrık kararlar içerir: bir tesisi inşa et ya da etme, bir çalışanı ata ya da atama. Bu, doğrusal programlamayı tamsayılı ve ikili değişkenlerle genişleten karma tamsayılı programlama (MIP) gerektirir.

Giriş ve dal-sınır

Rotalama problemleri tamsayılı kararlara ihtiyaç duyar. İkili x[i][j] değişkeni, i aracının j konumunu ziyaret edip etmediğini gösterir. Araçlar kesirli ziyaretler yapamaz.

Dal-sınır yöntemi, sürekli DP gevşetmelerini çözerek ayrık çözüm uzayını sistematik biçimde arar:

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}")Altyapı:

Tamsayılı çözüm, sürekli çözümün yuvarlanmasından farklıdır. Dal-sınır, önemli ölçüde daha yüksek hesaplama maliyetiyle optimal tamsayılı çözümü bulur.

Ne zaman tamsayılı programlama kullanılmalı

Kararlar doğası gereği ayrık olduğunda tamsayılı değişkenler kullanın: tesis açma, çalışan atama, konumları ziyaret edip etmeme gibi araç rotalama. Tahvil piyasasındaki optimizasyonlar sıklıkla karma tamsayılı çözümler gerektirir. Sürekli değişkenler, anlamlı olmayan kesirli atamalar üretebilirken, ikili değişkenler uygulanabilir çözümler sunar.

Bununla birlikte, tamsayılı programlama dramatik biçimde daha pahalıdır. Yüzlerce tamsayılı değişkene sahip problemler saniyeler süren sürekli DP'lere kıyasla saatler alabilir. Üretim miktarları büyükse, tam sayılılık daha az önemlidir çünkü yuvarlama çözümleri pek etkilemez. Tam tamsayılılığa geçmeden önce her zaman önce sürekli gevşetmeyi çözerek sınırları kontrol edin.

Sonuç

Doğrusal programlama, optimizasyon problemlerine yaklaşımınızı dönüştürür. Aynı matematiksel çerçeve, rotalamadan üretim planlamaya, portföy yönetimine kadar çok farklı alanlarda geçerlidir.

Geometrik olarak görselleştirebileceğiniz basit iki değişkenli problemlerle başlayın. Ticari çözücülerin perde arkasında ne yaptığını anlamak için temel simplex'i uygulayın. İş gereksinimlerini matematiksel kısıtlara çevirerek gerçek formülasyonlarla çalışın.

Uzmanlığınızı derinleştirmek için, matematiksel temellerinizi güçlendirmek amacıyla Python ile Optimizasyona Giriş ve Veri Bilimi için Doğrusal Cebir kurslarımızı keşfedin. Python'da Makine Öğrenimi Bilimcisi kariyer yolumuz da başka bir harika seçenektir.