Yöneylem Araştırması: Simpleks, Ulaşım ve Optimizasyon Algoritmaları

Tarihçe ve Tanım

Yöneylem Araştırması (Operations Research — OR), karmaşık sistemlerdeki karar problemlerine matematiksel ve analitik yöntemler uygulayan disiplindir. II. Dünya Savaşı döneminde (1939–1945) askeri operasyonları optimize etmek üzere İngiliz ve Amerikan bilim insanlarından oluşan takımlar tarafından geliştirildi.

Savaş sonrasında bu yöntemler sivil alana taşındı. 1947'de George Dantzig Simpleks Algoritması'nı geliştirdi — bu algoritma 20. yüzyılın en önemli algoritmalarından biri olarak tarihe geçti. Bugün YA şu alanlarda kullanılmaktadır:

Doğrusal Programlama Formülasyonu

Doğrusal Programlama (DP / Linear Programming), hem amaç fonksiyonu hem de kısıtların doğrusal (lineer) olduğu optimizasyon problemidir. Standart formülasyon:

Grafik Çözüm Yöntemi

İki karar değişkenli problemler grafik olarak çözülebilir. Uygunluk bölgesinin köşe noktaları (corner points) amaç fonksiyonunun en iyi değerini veren adaylardır. Temel Ekstrem Noktalar Teoremi: DP'nin optimal çözümü mutlaka uygunluk bölgesinin bir köşe noktasında bulunur.

Köşe Noktası B'nin Doğrulanması (Denklem Sistemi):

Simpleks Yöntemi — Teori

George Dantzig'in 1947'de geliştirdiği Simpleks Algoritması, grafik yönteminun 2+ değişkenli problemlere genellemesidir. Temel fikir: Uygunluk bölgesinin köşe noktalarını sistematik biçimde dolaş, her adımda amaç fonksiyonunu iyileştiren komşu köşeye geç, iyileştirme mümkün değilse op timale ulaşılmıştır.

Simpleks Algoritması — Adım Adım Tam Çözüm

Aynı mobilya fabrikası problemini Simpleks yöntemiyle çözüyoruz. Önce standardize edilmiş forma getirelim:

Başlangıç bazı: s₁, s₂, s₃ (köşe noktası: x₁=0, x₂=0, Z=0)

Pivot İşlemi: Pivot satırını (s₃ satırı) pivot elemana (3) böleceğiz, ardından diğer satırları sıfırlayacağız.

Yeni baz: s₁, s₂, x₂ → Z = 4.000 ₺ (x₁=0, x₂=8)

Duyarlılık Analizi

Simpleks çözümü bulunduktan sonra, parametrelerdeki değişikliklerin optimal çözümü nasıl etkilediğini araştıran analizdir. İki temel soru:

Ulaşım Problemi

Ulaşım problemi, m tedarik noktasından n talep noktasına mal taşıma maliyetini minimize eden özel bir DP formülasyonudur. Pratikte çok yaygın karşılaşılan bir problem türü.

Atama Problemi

Atama problemi, n işin n işçiye (ya da makineye) minimum maliyetle atanması problemidir. Ulaşım probleminin özel durumudur (her hücrede kapasite ve talep = 1). Macar Algoritması (Hungarian Method) pratikte kullanılan en yaygın çözüm yöntemidir.

Tamsayılı Programlama ve Branch & Bound

Bazı problemlerde değişkenler tam sayı (integer) olmalıdır: Kaç kamyon satın alınmalı Kaç fabrika açılmalı Hangi projeler seçilmeli (0/1 kararı) Bu tür problemlere Tamsayılı Programlama (Integer Programming — IP) denir.

Excel Solver ve Python PuLP ile Çözüm

from pulp import * # Problem tanımı

prob = LpProblem("Mobilya_Fabrikasi", LpMaximize) # Karar değişkenleri

x1 = LpVariable("Sandalye", lowBound=0)

x2 = LpVariable("Masa", lowBound=0) # Amaç fonksiyonu

prob += 300*x1 + 500*x2, "Kar_Maksimizasyonu" # Kısıtlar

prob += 2*x1 + 4*x2 <= 40, "Agac_Isleme"

prob += 3*x1 + 2*x2 <= 36, "Boyama"

prob += x1 + 3*x2 <= 24, "Montaj" # Çöz

prob.solve() # Sonuçlar

print(f"Durum: {LpStatus[prob.status]}")

print(f"Sandalye (x1): {value(x1)}")

print(f"Masa (x2): {value(x2)}")

print(f"Maksimum Kâr: {value(prob.objective)} TL")

# Çıktı:

# Durum: Optimal

# Sandalye (x1): 4.0

# Masa (x2): 8.0

# Maksimum Kâr: 5200.0 TL

from scipy.optimize import linprog # linprog minimizasyon yapar, negatif katsayı

c = [-300, -500] # Maks için negatife çevir

A = [[2,4],[3,2],[1,3]]

b = [40, 36, 24]

bounds = [(0,None),(0,None)] res = linprog(c, A_ub=A, b_ub=b, bounds=bounds)

print(f"x1={res.x[0]:.2f}, x2={res.x[1]:.2f}")

print(f"Z_max = {-res.fun:.2f} TL")

# x1=4.00, x2=5.14... → Sayısal hassasiyet farkı

# PuLP daha uygun LP kütüphane

Endüstri Uygulamaları