Yöneylem Araştırması

Yöneylem araştırması, karar değişkenleri ve kısıtlar altında hesaplanabilir optimum çözümlerin bulunmasını konu alır. Doğrusal, tamsayılı ve doğrusal olmayan modellerin çözücü algoritmaları; matematiksel optimalite koşulları ve sayısal doğrulama ile birlikte incelenir. Yazılım sistemlerindeki kaynak tahsisi, zamanlama ve akış problemleri kuramsal yöntemlerin hesaplamalı uygulamalarıdır.

Ünite 1: Optimizasyon Problemlerinin Matematiksel Modellenmesi

1.1. Karar Değişkenleri ve Uygulanabilir Küme

Karar değişkeni, amaç fonksiyonu ve kısıt ayrı matematiksel nesnelerdir. Uygulanabilir küme, tüm kısıtların birlikte sağlandığı noktalardan oluşur; amaç değeri bu küme üzerinde karşılaştırılır. Parametreler gözlenen verileri, değişkenler ise algoritmanın belirleyeceği kararları temsil eder. Ölçek birimleri ve işaret kısıtları model kurulurken belirlenir.

1.2. Kısıtların Sayısal Gösterimi

Bir görevin sunucuya atanmasında ikili xᵢⱼ değişkeni, görev i için sunucu j seçilirse 1 olur. Her görev için tek seçim, her sunucu için kapasite sınırı yazılır. Girdi doğrulaması, karar değişkenlerinin türlerini ve kısıtların boyutlarını çözümden önce denetler. Modelleme hatası, çözücünün matematiksel olarak doğru fakat mühendislik açısından geçersiz sonuç üretmesine neden olabilir.

min[x∈ℱ] cᵀx;   ℱ = {x : Ax ≤ b, x ∈ X}

1.3. Model Tutarlılığı ve Birim Denetimi

Önce küçük örneklerde tüm olası kararlar taranarak uygulanabilir küme ve en iyi çözüm doğrulanır. Ardından ölçek büyütüldüğünde uygulanabilirlik, amaç değeri ve çözücü toleransları ayrı raporlanır. Amaç fonksiyonunun en küçük değeri ile çözücünün bulduğu en iyi geçerli üst sınır karıştırılmamalıdır.

1.4. Sayısal ve Algoritmik Örnek

Üç görevin iki sunucu arasında dağıtımında birinci sunucunun iki, ikincinin bir birim kapasitesi olsun. xᵢⱼ ikili atama değişkeniyle altı karar değişkeni kurulur. Her görevin tam olarak bir kez atanması ve iki kapasite kısıtının sağlanması gerekir. Maliyetlerin her görev için sabit olduğu durumda bütün uygulanabilir atamalar karşılaştırılabilir.

1.5. Kısıt Matrislerinin Yapısal Özellikleri

Modelin Ax ≤ b gösterimine indirgenmesi yalnızca cebirsel düzenleme değildir. A matrisinin seyrekliği, satırların ölçekleri ve değişkenlerin türleri çözücünün bellekte tutacağı veri yapısını ve faktörizasyon maliyetini belirler. Atama probleminde her görev için tam bir seçim kısıtı, her kaynak için kapasite kısıtı gerekir. Bir maliyet katsayısının süre, enerji veya parasal maliyet olarak hangi birimle ölçüldüğü kaydedilmelidir. Boyutsal tutarsızlık, matematiksel olarak uygulanabilir görünen çözümü fiziksel açıdan anlamsız hâle getirir.

A ∈ ℝᵐˣⁿ;  ℱ = {x ∈ X : Ax ≤ b}

1.6. Uygulanabilirlik ile Optimalitenin Ayrılması

İlk doğrulama, amaç fonksiyonu dikkate alınmadan kısıtları sağlayan en az bir noktanın varlığını araştırır. Uygulanabilirlik, modelde çelişen zorunluluklar bulunup bulunmadığını belirler; optimalite ise uygun noktalar arasındaki karşılaştırmayı gerektirir. İkili değişkenli küçük modellerde tüm atamaların taranması, karmaşık çözücüye karşı bağımsız bir doğrulama referansı sağlar. Büyük modellerde ise önce kısıt ihlalleri ve değişken sınırları, daha sonra amaç değeri incelenmelidir.

1.7. Veri İndeksleme ve Model Üretimi

Görev, sunucu ve zaman kümeleri açık ve değişmez indekslerle modellenmelidir. Eksik maliyet girdileri sıfır maliyet varsayılarak doldurulmaz; uygulanamayacak eşleşmeler değişken alanından çıkarılır veya açık kısıtla yasaklanır. Model üretiminde aynı kısıtın tekrarlanması çözümü değiştirmese de hazırlık ve çözüm maliyetini artırabilir. Bu nedenle oluşturulan satır ve sütun sayıları, sıfır olmayan katsayı miktarı ve kullanılan veri sürümü yeniden üretilebilir biçimde tutulmalıdır.

1.8. Hesaplamalı Örnek ve Çözüm

Üç görev, iki sunucu ve sırasıyla iki ve bir görev kapasiteli bir atama örneğinde altı ikili değişken kullanılır. Her görevin tam bir sunucuya atanması, iki kapasitenin aşılmaması ve toplam atanan görev sayısının üç olması eşzamanlı zorunludur.

∑ⱼxᵢⱼ = 1;  ∑ᵢxᵢ₁ ≤ 2;  ∑ᵢxᵢ₂ ≤ 1

1.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Küçük modelde bütün 2³ olası atama bağımsız taranabilir. Verinin sunucu sayısı değiştiğinde indeks sınırlarının sabit varsayılmaması, gerçekleme doğruluğu için ayrıca sınanır.

Ünite 2: Doğrusal Programlama ve Uygulanabilir Çözüm Uzayı

2.1. Doğrusallık ve Dışbükey Geometri

Doğrusal programlamada amaç ve kısıt fonksiyonları doğrusaldır. Kısıtların kesişimi dışbükey çokyüzlü oluşturur; uygulanabilir küme boş, sınırsız veya sınırlı olabilir. Bir temel uygulanabilir çözüm, bağımsız aktif kısıtlar üzerinden temsil edilir. Optimal çözüm varsa ve uygun köşe noktası mevcutsa bir köşede de optimum bulunabilir.

2.2. Standart Forma Dönüştürme

Standart forma dönüştürmede gevşeklik değişkenleri eklenir ve serbest değişkenler pozitif/negatif bileşenlere ayrılabilir. Modelin sınırsızlığı ile algoritmanın henüz sınır bulamaması farklı durumlardır. İki değişkenli küçük modeller geometriyle, yüksek boyutlu modeller matris gösterimiyle incelenir.

min cᵀx;   Ax = b;   x ≥ 0

2.3. Köşe Noktaları ve Sayısal Koşulluluk

Düşük boyutlu örneklerde köşe noktaları hesaplanarak amaç değerleri karşılaştırılır; aktif kısıtların doğrusal bağımsızlığı sayısal koşulluluk açısından kontrol edilir. Çok küçük katsayılarla çok büyük katsayıların birlikte kullanılması kararsızlığa yol açabilir.

2.4. Sayısal ve Algoritmik Örnek

İki değişkenli x+y≤6, 2x+y≤8, x,y≥0 modelinde (2,4) uygulanabilir köşe noktasıdır. Amaç 3x+2y ençoklanıyorsa bu noktada değer 14 olur; diğer köşe değerleri ayrıca karşılaştırılmadan optimum denemez. Doğrusal amaç dışında bir katsayıyla aynı köşe optimum olmayabilir.

2.5. Polihedral Geometri ve Uç Noktalar

Doğrusal eşitsizliklerin kesişimi dışbükey çokyüzlüdür. Sınırlı ve boş olmayan doğrusal programda optimum en az bir uç noktada elde edilebilir; buna karşılık uygun küme doğrusal bir alt uzay içeriyorsa köşe noktasının bulunması garanti değildir. Dejenerasyon bir uç noktada beklenenden fazla aktif kısıt bulunmasıyla ilişkilidir. Geometrik anlatım, genel boyutlu modellerde temel matris ve doğrusal bağımsızlık kavramlarına aktarılmalıdır.

x* ∈ arg min{x∈ℱ} cᵀx

2.6. Birinci Aşama ve Uygulanamazlık Sertifikaları

Başlangıç temel uygun çözüm bulunamadığında yapay değişkenli birinci aşama kurulabilir. Yardımcı amaç fonksiyonunun optimumunun sıfırdan büyük olması, kurulan standart modelin uygun olmadığını gösterir; tolerans seçimi sayısal belirsizliği etkiler. Doğrusal eşitsizlikler için Farkas önermesi, uygun çözümün bulunmaması hâlinde bunu doğrulayan bir ayrım vektörünün varlığını karakterize eder. Çözücünün “infeasible” durumu ile zaman sınırı nedeniyle çözüm bulunamaması ayrılmalıdır.

2.7. Ölçekleme ve Seyrek Doğrusal Cebir

Katsayı büyüklükleri arasında çok büyük fark bulunması, pivot seçimini ve artık hesaplarını olumsuz etkileyebilir. Satır ve sütun ölçeklemesi matematiksel çözüm kümesini uygun dönüşümler altında korurken sayısal davranışı değiştirebilir. Çözücü, seyrek matris gösterimiyle yalnız sıfır olmayan katsayıları saklamalıdır. Ölçeklenmiş modelde bulunan çözüm, orijinal birimlere döndürüldükten sonra kısıtların artık değerleri yeniden hesaplanarak doğrulanmalıdır.

2.8. Hesaplamalı Örnek ve Çözüm

Maksimizasyon modeli 3x+2y, x+y≤6, 2x+y≤8 ve x,y≥0 ile tanımlansın. Uygun köşe noktaları (0,0), (0,6), (2,4), (4,0) olup amaç değerleri sırasıyla 0, 12, 14 ve 12’dir. Bu nedenle (2,4) küresel optimumdur.

max 3x+2y = 14   at (x,y)=(2,4)

2.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Aynı örnekte katsayıların biri değiştirilirse optimum köşe değişebilir. Programatik karşılaştırma doğrusal kısıtları önce değerlendirip yalnız uygun köşelerde amaç değeri hesaplamalıdır.

Ünite 3: Simplex ve İç Nokta Yöntemleri

3.1. Temel Çözümler ve İndirgenmiş Maliyetler

Simplex yöntemi uygun temel çözümler arasında indirgenmiş maliyetlere göre pivot yapar. Revize Simplex, tüm tabloyu tutmak yerine temel matrisin çarpanlaştırılmasını kullanarak bellek maliyetini azaltır. Dejenerasyon sıfır uzunluklu pivotlara, kötü kural seçimi ise döngü riskine yol açabilir.

3.2. Pivot ve Primal-Dual İterasyonlar

İç nokta yöntemleri çokyüzlünün içindeki iterasyonlarla primal ve dual artıkların azaltılmasına dayanır. Newton yönü ve adım uzunluğu seçimi, faktörizasyon maliyetini belirler. Yöntem karşılaştırmasında yalnız iterasyon sayısı değil seyrek matris yapısı, tolerans ve toplam süre birlikte değerlendirilir.

c̄[N] = c[N] − A[N]ᵀ (A[B]ᵀ)⁻¹ c[B]

3.3. Çözüm Artıkları ve Yakınsama Ölçütleri

Küçük modellerde Simplex temel çözümleri ile iç nokta çözümlerinin amaç değeri ve kısıt artıkları karşılaştırılabilir. Aynı tolerans altında uygunluk, optimalite ve tamamlayıcılık artıklarının ayrı izlenmesi gerekir.

3.4. Sayısal ve Algoritmik Örnek

Standart biçimde B temel matrisi seçildiğinde dual vektör Bᵀy=c[B] çözümünden bulunur. İndirgenmiş maliyetlerin işaretleri optimaliteyi denetler; hesaplama sırasında bütün yoğun ters matrisi kurmak gerekli değildir. İç nokta yönteminde ise primal/dual artıklar ve tamamlayıcılık aynı anda küçültülür.

3.5. Revize Simplex ve Temel Matris İşlemleri

Revize Simplex, her iterasyonda tam Simplex tablosunu yeniden kurmak yerine temel matrisin seyrek çarpanlaştırılmasını günceller. İndirgenmiş maliyetler dual fiyatlar yardımıyla hesaplanır; giren değişkenin seçimi fiyatlandırma stratejisine bağlıdır. Çıkan değişken oran testiyle belirlenirken sıfıra yakın pivotlar koşulluluk sorunu yaratabilir. Çözücünün iterasyon sayısının küçük olması tek başına düşük hesaplama maliyetini göstermez; çarpanlaştırma ve yeniden fiyatlandırma işlemleri de ölçülmelidir.

Bᵀy = cᴮ;   rᴺ = cᴺ − (Aᴺ)ᵀy

3.6. Primal-Dual İç Nokta Sistemleri

Primal ve dual uygunluk artıklarına ek olarak tamamlayıcılık hatası birlikte küçültülür. Newton sistemi oluşturulduğunda matrisin normal denklem veya artırılmış KKT sistemi biçiminde çözülmesi sayısal ve bellek gereksinimlerini etkiler. Bariyer parametresi çok hızlı azaltılırsa adım uzunluğu küçülerek ilerleme durabilir. İç nokta çözümü köşe çözümü gerektiren sonraki işlemler için crossover algoritmasıyla temel çözüme dönüştürülebilir.

3.7. Sonlandırma Ölçütlerinin Bağımsız Denetimi

Çözücü raporundaki optimum durumunu değerlendirmek için orijinal Ax=b kısıtları, değişken sınırları, indirgenmiş maliyetler ve primal-dual amaç farkı yeniden hesaplanır. Farklı algoritmaların çözüm süreleri yalnızca eşit uygunluk ve optimalite toleranslarında karşılaştırılmalıdır. Ölçümlere matris hazırlama, presolve, çözüm ve son işleme süreleri ayrı dâhil edilirse matematiksel algoritma maliyetiyle yazılım altyapısı maliyeti ayrıştırılabilir.

3.8. Hesaplamalı Örnek ve Çözüm

İki değişkenli standart biçimde temel sütunların oluşturduğu B matrisi seçilir; Bᵀy=cᴮ çözülerek dual fiyatlar, ardından indirgenmiş maliyetler hesaplanır. Tüm sütunlar için yoğun ters matris kurmak yerine doğrusal sistem çözümü kullanmak sayısal olarak daha uygundur.

Bᵀy = cᴮ;   rⱼ = cⱼ − Aⱼᵀy

3.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Basit örneğin çözümü her pivot sonrasında temel olmayan değişkenlerin işareti ve primal uygulanabilirlik açısından doğrulanır. İç nokta çözücüsüyle elde edilen değer aynı orijinal amaç ölçeğinde karşılaştırılır.

Ünite 4: Dualite Teorisi ve Duyarlılık Analizi

4.1. Primal ve Dual Modeller

Primal ve dual problemler aynı optimizasyon olgusunun birbirine bağlı iki gösterimidir. Zayıf dualite, minimizasyon için her dual uygulanabilir değerin primal değere alt sınır verdiğini ifade eder. Uygun koşullarda güçlü dualite optimum değerleri eşitler; tamamlayıcı gevşeklik aktif kısıtların yorumlanmasını sağlar.

4.2. Gölge Fiyatlar ve Parametre Değişimi

Dual çarpanlar, sağ taraf kapasitesindeki küçük değişimlerin optimum üzerindeki yerel etkisini temsil edebilir. Bu türev yorumu, çözüm tabanı veya aktif küme değiştiğinde geçerliliğini yitirebilir. Duyarlılık analizinde katsayı aralıkları ile gerçek yeniden optimizasyon sonuçları birbirinden ayrılmalıdır.

cᵀx − bᵀy ≥ 0;   Aᵀy ≤ c;   y ∈ ℝᵐ

4.3. Dualite Açığı ve Tamamlayıcı Gevşeklik

Primal ve dual aday çözümler ayrı doğrulanır. Hesaplanan dualite açığı küçük olsa da kısıt ihlalleri büyükse optimumluk sonucu çıkarılamaz; normalleştirilmiş artıklara ihtiyaç vardır.

4.4. Sayısal ve Algoritmik Örnek

Primal modelde bir kapasitenin bir birim artırılmasıyla optimum maliyet yerel olarak yᵢ kadar değişebilir. Yorum yalnız etkin parametre aralığı için geçerlidir. Kapasite iki farklı değerle değiştirilip problem yeniden çözülerek gölge fiyat kestiriminin hangi aralıkta doğru kaldığı gözlenir.

4.5. Zayıf ve Güçlü Dualite

Primal minimizasyon problemi için dual uygun bir y vektörü, amaç değerinin alt sınırını sağlayabilir. Zayıf dualite bu sınır ilişkisinin her uygun primal-dual çift için geçerli olduğunu söyler. Uygun koşullarda güçlü dualite, iki optimum değerin eşitliğini garanti eder. Bu ayrım, tamsayılı problemlerde doğrusal gevşetmeden bulunan alt sınırların yorumlanması için de temel sağlar; ancak tamsayılı problemin kendisine doğrusal güçlü dualite doğrudan uygulanmaz.

bᵀy ≤ cᵀx;   Aᵀy ≤ c;   Ax = b;   x ≥ 0

4.6. Gölge Fiyatların Geçerlilik Aralığı

Bir kaynak kısıtının sağ tarafındaki küçük değişimin optimum amaç değerine yerel etkisi dual fiyatla açıklanabilir. Ancak bu türev yorumu yalnız aynı aktif temel veya uygun düzenlilik koşulları geçerliyken kullanılmalıdır. Kaynak miktarı büyük ölçüde değiştiğinde temel değişebilir ve duyarlılık doğrusal kalmayabilir. Yazılım kapasite kararlarında gölge fiyat, gerçek satın alma veya işletme maliyetinin yerine doğrudan geçirilemez.

4.7. Parametrik Yeniden Optimizasyon

Yeni talep, maliyet veya kapasite bilgisi geldiğinde tüm modelin sıfırdan çözülmesi her zaman gerekli değildir. Sıcak başlangıçla mevcut temel veya çözüm bilgisi korunabilir; bunun geçerliliği kısıt ve değişken yapısının nasıl değiştiğine bağlıdır. Parametre senaryoları karşılaştırılırken giriş verisi sürümü, çözüm durumu, geçerli alt-üst sınırlar ve hesaplama süresi birlikte raporlanır. Sadece amaç değerinin değişmesi, değişimin nedenini açıklamaz.

4.8. Hesaplamalı Örnek ve Çözüm

Minimizasyon biçimindeki bir doğrusal program için primal uygun x ve dual uygun y bulunduğunda cᵀx ile bᵀy arasındaki fark negatif olamaz. Farkın sıfıra yakın olması, uygunluk artıkları da küçükse optimuma ulaşıldığını destekler.

gap = cᵀx − bᵀy ≥ 0

4.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Duyarlılık deneyinde sağ taraf tek bir kaynak için değiştirilir; dual fiyatın öngördüğü yerel amaç farkı ile gerçekten yeniden çözülen model arasındaki fark incelenir.

Ünite 5: Tamsayılı ve Karma Tamsayılı Programlama

5.1. Ayrık Kararlar ve Doğrusal Gevşetme

Tamsayılı değişkenler, ayrık kaynak seçimi ve mantıksal kararların doğrudan modellenmesini sağlar. Doğrusal gevşetmenin uygun kümesi daha büyük olduğundan minimizasyon problemlerinde alt sınır üretir. İkili değişkenlerin anlamı, kapsam sınırları ve big-M katsayıları modelin sayısal güvenilirliğini belirler.

5.2. Atama ve Mantıksal Kısıtlar

Görev atamada her görevin bir sunucuya verilmesi ve her sunucunun kaynak bütçesinin aşılmaması doğrusal kısıtlarla ifade edilir. Koşullu etkinleşen bir kısıt için büyük sabit kullanılıyorsa en küçük geçerli sınır hesaplanmalıdır; keyfî derecede büyük değer seçilmez.

xⱼ ∈ {0,1};   ∑[j] xᵢⱼ = 1;   ∑[i] rᵢxᵢⱼ ≤ Cⱼ

5.3. Uygulanabilirlik ve Optimalite Sertifikası

Bir çözücünün uygun çözüm bulması optimalite ispatı değildir. Bulunan en iyi tamsayılı değer ile gevşetme alt sınırı arasındaki göreli fark ayrı raporlanır.

5.4. Sayısal ve Algoritmik Örnek

Üç görev için ikili atama modelinde doğrusal gevşetme kesirli değerler üretebilir. Bu değerler fiziksel görev yerleşimi olarak kullanılamaz. Örneğin iki sunucuya yarımşar atanmış bir görev, gerçek sistemde bölünemiyorsa ikili koşul zorunludur; gevşetmenin düşük maliyeti yalnız alt sınırdır.

5.5. Mantıksal Kısıtların Doğrusal Modellenmesi

İkili değişkenler aç/kapat, atama ve seçim kararlarını kodlar. Örneğin bir sunucu kullanılmıyorsa ona iş atanmasını önlemek için atama toplamı kapasiteyle ilişkilendirilir. Büyük-M yaklaşımında M değeri geçerli bir üst sınırdan türetilmelidir; keyfî büyük katsayılar zayıf gevşetmeye ve sayısal kararsızlığa neden olur. Uygun durumda gösterge kısıtları ve daha sıkı formülasyonlar tercih edilir.

∑ᵢ xᵢⱼ ≤ Cⱼyⱼ;   xᵢⱼ,yⱼ ∈ {0,1}

5.6. Doğrusal Gevşetme ve Bütünlük Boşluğu

Tamsayılı koşullar kaldırıldığında bulunan LP optimumu, minimizasyon için genellikle geçerli bir alt sınır üretir. Bütünlük boşluğu, gevşetmenin gerçek ayrık çözümden ne kadar uzak olabileceğini gösterir. İyi formülasyon daha çok satır içerse bile sınır kalitesini artırarak arama ağacını küçültebilir. Karşılaştırmada yalnız değişken sayısı değil kök düğüm sınırı, çözülen düğüm sayısı ve toplam süre kaydedilmelidir.

5.7. Doğrulanabilir Ayrık Çözüm

Çözücünün döndürdüğü kayan noktalı değerler doğrudan tam sayıya yuvarlanıp kullanılmamalıdır. Önce çözümün bütünlük toleransı, ardından yuvarlanmış adayın orijinal kısıtları kontrol edilir. Kaynak atamada tek bir görevin iki sunucuya atanması, amaç değeri iyi görünse de hatalı sonuçtur. Kesin doğrulama gerektiğinde tam sayılı katsayılarla bağımsız kısıt değerlendirmesi yapılabilir.

5.8. Hesaplamalı Örnek ve Çözüm

Ağırlıkları 2, 3 ve 4; faydaları 4, 5 ve 7 olan üç nesne, kapasitesi 5 olan çantaya yerleştirilsin. İlk iki nesnenin birlikte seçimi 9 fayda sağlar; yalnız üçüncü nesne 7, birinci ile üçüncünün birlikte seçimi kapasite ihlali doğurur.

max 4x₁+5x₂+7x₃ = 9;  2x₁+3x₂+4x₃ ≤ 5

5.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Sekiz ikili seçimden uygun olanlar taranarak optimum 9 bağımsız doğrulanır. Aynı test, bütünlük koşulları kaldırılmış LP gevşetmesinin ayrık optimumdan farklı olabileceğini gösterir.

Ünite 6: Dal-Sınır ve Kesme Düzlemi Yöntemleri

6.1. Dallanma Ağacı ve Budama Koşulları

Dal-sınır algoritması çözüm uzayını alt problemlere böler. Her düğümde hesaplanan iyimser sınır, eldeki uygulanabilir çözümden daha iyi sonuç vaat etmiyorsa alt ağaç budanır. Dallanma değişkeninin seçimi, üst/alt sınır kalitesi ve düğüm yönetimi toplam maliyeti belirler.

6.2. Geçerli Eşitsizlikler ve Kesme Düzlemleri

Kesme düzlemleri, geçerli tamsayılı çözümleri korurken gevşetmedeki kesirli noktaları çıkarır. Geçerliliği ispatlanmamış bir kesme yanlış optimum üretebilir. Branch-and-cut yöntemi iki mekanizmayı birleştirir ve güçlü alt sınırlar elde etmeye çalışır.

gap = |z[inc] − z[bound]| / max(1, |z[inc]|)

6.3. Sınır Kalitesi ve Durdurma Koşulları

İlerleme kayıtlarında düğüm sayısı, en iyi bulunan değer, en iyi sınır ve dualite açığı izlenir. Zaman sınırında elde edilen sonuç matematiksel garanti seviyesiyle birlikte sunulur.

6.4. Sayısal ve Algoritmik Örnek

Bir düğümde tamsayılı olması gereken x=2.4 bulunursa x≤2 ve x≥3 alt problemleri oluşturulabilir. Her iki alt problem çözüm uzayını örtmeden kapsar. Eğer ilgili alt sınır eldeki uygulanabilir değerden kötü ise dal güvenle budanır.

6.4.1. Açıklayıcı Sözde Kod

best = +infinity; bound = -infinity
push(root relaxation)
while open_nodes:
    node = select(open_nodes)
    if infeasible(node) or lower_bound(node) >= best: continue
    if integral(node.solution): best = min(best, objective(node)); continue
    branch_on_fractional_variable(node)

6.5. Düğüm Sınırları ve Dallanma Stratejileri

Dal-sınır yöntemi, ayrık kararları alt problemlere ayırırken her düğümde geçerli bir gevşetme sınırı hesaplar. En iyi düğüm seçimi, derinlik öncelikli seçim ve en iyi sınır seçimi bellek ile erken uygun çözüm bulma arasında farklı dengeler kurar. Kesirli değişkenin hangi noktadan dallandırılacağı güçlü dallanma veya sözde maliyet tahminiyle belirlenebilir. Geçerli alt sınırla mevcut uygun üst sınır karıştırılmamalıdır.

LB ≤ z* ≤ UB;   bağıl boşluk = (UB − LB) / max(1, |UB|)

6.6. Geçerli Eşitsizlikler ve Kesme Düzlemleri

Bir kesme düzlemi mevcut kesirli LP çözümünü dışlamalı ancak hiçbir tamsayılı uygun çözümü çıkarmamalıdır. Gomory, kapak ve problem yapısına özel kesmeler farklı alt çokyüzlüleri sıkılaştırır. Kesmelerin tamamını sınırsız eklemek faktörizasyon maliyetini artırır; ayrım mekanizması kuvvet ve sayısal güvenilirlik bakımından değerlendirilir. Geçersiz tek bir kesme, raporlanan optimaliteyi bütünüyle bozabilir.

6.7. Zaman Sınırında Çözüm Raporlama

Zaman sınırında algoritma sonlandığında geçerli bir uygun çözüm varsa bunun değeri raporlanabilir; fakat bulunan çözümün optimum olduğu ancak boşluk kapanmışsa ileri sürülebilir. Açık düğümlerin sınırları ve kesme düzlemleri nihai global sınıra katkı sağlar. Rapor; en iyi aday, kanıtlanmış sınır, mutlak/bağıl boşluk, ziyaret edilen düğümler ve kesilme nedenini birlikte içermelidir.

6.8. Hesaplamalı Örnek ve Çözüm

Bir minimizasyon aramasında eldeki uygun çözüm 93, bütün açık düğümlerden türetilen geçerli global alt sınır 82 olsun. Algoritma sonlandığında mutlak boşluk 11, tanımlanan normalize boşluk yaklaşık yüzde 11,83 olur. Bu durumda optimum kanıtlanmış değildir.

absolute gap = 93 − 82 = 11;  relative gap = 11/93 ≈ 0.1183

6.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Raporda alt sınırın tek bir düğümden değil bütün aktif düğümlerin geçerli sınırlarıyla oluşturulduğu doğrulanır. Süre limiti durumuna “optimum” yazılmaz.

Ünite 7: Taşıma ve Atama Problemleri

7.1. Arz-Talep Dengesi ve Taşıma Modeli

Taşıma modeli arz ve talep düğümleri arasındaki akışı maliyetle ilişkilendirir. Dengeli modellerde toplam arz ve talep eşittir; dengesiz modellerde açık talep veya fazla arz uygun yapay düğümle temsil edilebilir. Her taşıma kenarı için miktar değişkeni tanımlanır.

7.2. İki Parçalı Eşleştirme Algoritmaları

Atama problemi iki parçalı çizgede bire bir eşleştirme olarak yazılabilir. Maliyet matrisinde yasak atamalar açık biçimde modellenmelidir. Macar yöntemi ve min-cost flow yöntemleri problemi farklı veri yapıları üzerinden çözer.

min ∑[i,j] cᵢⱼxᵢⱼ;   ∑[j] xᵢⱼ = sᵢ;   ∑[i] xᵢⱼ = dⱼ

7.3. Akış Korunumu ve Model Doğruluğu

Kapasite ve talep dengesi, her düğüm için korunum denklemleriyle sınanır. Sıfır maliyetli yapay kenarlar yanlış kullanılınca anlamı olmayan optimum elde edilebilir.

7.4. Sayısal ve Algoritmik Örnek

İki kaynak ve iki hedef için arz (3,2), talep (2,3) seçilsin. Toplamlar eşit olduğundan model dengelidir. xᵢⱼ akışları her arz düğümünde ilgili toplamı, her talep düğümünde hedef toplamını sağlamalıdır. Bir düğümde bir birim fazla akış, amaç maliyeti düşük olsa da çözümü geçersiz kılar.

7.5. Taşıma Modelinin Ağ Gösterimi

Taşıma problemi, arz düğümlerinden talep düğümlerine akan miktarlara maliyet atayan iki parçalı ağ olarak modellenebilir. Toplam arzla talep eşit değilse sanal düğüm eklenmesi matematiksel denge sağlayabilir; bu düğümün maliyeti gerçek işletme varsayımını temsil etmelidir. Uygun çözümde tüm düğümlerin akış dengesi ve değişkenlerin negatif olmama koşulu denetlenir. Toplam unimodüler yapı mevcutsa tamsayılı kapasite ve taleple LP çözümü tamsayılı köşe çözümleri sağlayabilir.

min ∑ᵢ∑ⱼ cᵢⱼxᵢⱼ;   ∑ⱼxᵢⱼ = sᵢ;   ∑ᵢxᵢⱼ = dⱼ

7.6. Macar Algoritması ve Eşleştirme

Kare maliyet matrisi için atama problemi minimum ağırlıklı tam eşleştirme olarak çözülebilir. Macar algoritması dual etiketler ve sıfır indirgenmiş maliyetli kenarlardan uygun eşleştirme oluşturur. Dikdörtgen durumlarda sanal satır veya sütunların anlamı ayrıca tanımlanmalıdır. Atamanın kalitesi yalnız toplam maliyetle değil, zorunlu eşleşme yasaklarının ve bire-bir kapasitenin sağlanmasıyla doğrulanır.

7.7. Veri Ölçekleri ve Çözücü Seçimi

Yoğun bir atama matrisinin bellek gereksinimi, seyrek izinli eşleşmelerden farklıdır. Binlerce görev için tüm görev-kaynak çiftlerini üretmek çoğu durumda gereksizdir; erişilemeyen veya uygunsuz kenarlar modelden çıkarılabilir. Genel amaçlı MILP çözücüsü ile özel amaçlı minimum maliyetli akış algoritması aynı problemde farklı başarım gösterebilir. Karşılaştırma sırasında aynı maliyet ve uygunluk koşullarının kullanıldığı bağımsız olarak denetlenmelidir.

7.8. Hesaplamalı Örnek ve Çözüm

Arzlar 3 ve 2, talepler 2 ve 3 olsun. Maliyet matrisi satır sırasıyla (1,3) ve (2,1) değerlerini taşısın. Birinci kaynaktan iki birim ilk hedefe ve bir birim ikinci hedefe, ikinci kaynaktan iki birim ikinci hedefe aktarılırsa toplam maliyet 7 olur.

cost = 2·1 + 1·3 + 2·1 = 7

7.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Her kaynak ve hedef düğümünde toplam akış denge kısıtlarıyla sınanır. Birimlerin farklı taşınma maliyetleri ve yasaklı rotalar modelde açık tanımlanmalıdır.

Ünite 8: Ağ Akışları ve Ağ Optimizasyonu

8.1. Düğüm Dengeleri ve Kenar Kapasiteleri

Ağ akışında düğüm dengeleri ve kenar kapasiteleri birlikte değerlendirilir. Maksimum akış yalnız gönderilebilecek miktarı, minimum maliyetli akış ise belirli bir akış miktarını en düşük maliyetle gerçekleştirmeyi hedefler. Negatif maliyetli çevrimlerin varlığı ve kapasite sınırları modelin yorumunu etkiler.

8.2. Artık Ağlar ve Artıran Yol Yöntemleri

Artık ağda ileri ve geri kenarlar yer alır. Artıran yol algoritmaları artık kapasiteyi günceller; Dinic bloklayan akışlarla çalışır. En kısa yol ve potansiyel tabanlı algoritmalar minimum maliyetli akışa uygulanabilir.

max |f|;   0 ≤ f[u,v] ≤ c[u,v];   ∑[u] f[u,v] = ∑[w] f[v,w]

8.3. Maksimum Akış-Minimum Kesit Doğrulaması

Kesit kapasitesi ile akış miktarının eşitliği maksimum akış için doğrulama sertifikasıdır. Akış miktarı, her düğümün korunumu ve maliyet hesabı ayrı test edilmelidir.

8.4. Sayısal ve Algoritmik Örnek

Kapasiteleri s→a:3, a→t:2, s→t:1 olan ağda toplam 3 birim akış kurulabilir. s kaynak kesitinin kapasitesi 4 olsa da {s,a} kesitinin kapasitesi 3 olduğundan maksimum akış değeri 3 tür. Akış-kesit eşitliği sertifika sağlar.

8.4.1. Açıklayıcı Sözde Kod

build_residual_graph(flow, capacities)
while exists_augmenting_path(source, sink):
    delta = minimum_residual_capacity(path)
    augment_forward_and_reverse_arcs(path, delta)
check_flow_conservation()
check_minimum_cut_certificate()

8.5. Artık Ağ ve Ters Kenarların Anlamı

Artık ağdaki ileri kapasite daha fazla akış gönderme olanağını, ters kenar kapasitesi ise önceki akış kararını geri alma olanağını temsil eder. Yalnız ileri kenarlardan yol aramak, başlangıçta yapılan hatalı atamaları düzeltemediği için maksimum akışa ulaşmayı engelleyebilir. Akış korunumu her ara düğümde sağlanmalıdır. Kapasite sıfır olduğunda kenar artık yol aramasından çıkarılır; veri yapısında orijinal kenarın bilgisi yine korunabilir.

cʳ(u,v) = c(u,v) − f(u,v);   cʳ(v,u) = f(u,v)

8.6. Maksimum Akış ve Minimum Kesit Sertifikası

Bir akışın maksimum olduğuna ilişkin bağımsız kanıt, artırılabilir yol bulunmaması ve erişilebilir düğümlerden oluşturulan kesitin kapasitesiyle akış değerinin eşit olmasıdır. Edmonds–Karp yol seçiminde BFS kullanırken Dinic, düzey ağı ve bloklayan akışlarla daha elverişli karmaşıklık sınırları sağlar. Ağ boyutları, kapasite dağılımı ve seyrekliği hangi yöntemin pratikte üstün olduğunu belirler.

8.7. Minimum Maliyetli Akışın Ayrı Optimizasyon Hedefi

Maksimum akış yalnız taşınan miktarı büyütür; minimum maliyetli akış miktarı veya düğüm dengeleri sabitken maliyeti en aza indirir. Negatif maliyetli kenarlar içeren artık ağda uygun potansiyel veya çevrim denetimi gerekir. Düğüm talepleri ve toplam akış hedefi açık tanımlanmadan iki problem birbirine indirgenemez. Sonuçta toplam gönderilen akış, her kenarın kapasitesi ve amaç değeri ayrı doğrulanır.

8.8. Hesaplamalı Örnek ve Çözüm

s→a kenarında kapasite 3, a→t kenarında 2 ve s→t kenarında 1 olsun. s→a→t yoluyla 2, doğrudan s→t yoluyla 1 gönderilerek toplam 3 akış elde edilir. {s,a} kümesinden t tarafına kesit kapasitesi de 3 olduğundan bu akış maksimumdur.

max flow = min cut = 3

8.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Artık ağda ters kenarlar eklenerek önceki yönlendirmelerin düzeltilebildiği sınanır. Düğüm akış korunumu, kesit kapasitesi ve tüm kenar sınırları bağımsız testlerdir.

Ünite 9: Doğrusal Olmayan ve Konveks Optimizasyon

9.1. Konvekslik ve Yerel-Küresel Optimum

Konveks amaç ve konveks uygulanabilir küme birlikte olduğunda her yerel minimum küresel minimumdur. Doğrusal olmayan kısıtlar için uygulanabilirlik geometrisi ve türev bilgisi belirlenmelidir. Gradyan, Hessian ve koşul sayısı algoritmanın yakınsama davranışını etkiler.

9.2. Gradyan Yöntemleri ve KKT Koşulları

Gradyan tabanlı yöntemlerde adım büyüklüğü, durma koşulları ve projeksiyon mekanizması tanımlanır. KKT koşulları uygun düzenlilik varsayımlarında gerekli optimalite şartlarını verir; konveks modellerde uygun koşullarda yeterli hale gelebilir.

∇f(x*) + ∑[i] λᵢ∇gᵢ(x*) = 0;   λᵢgᵢ(x*) = 0

9.3. Durağanlık ve Sayısal Ölçekleme

Başlangıç noktasına duyarlılık yalnız nonkonveks problemlerde değil kötü ölçeklenmiş konveks modellerde de sayısal sorun yaratabilir. Primal uygunluk ve istasyonerlik artıkları birlikte izlenir.

9.4. Sayısal ve Algoritmik Örnek

Amaç f(x)=(x−3)² ve kısıt x≥0 olduğunda türev 2(x−3) sıfıra x=3 noktasında ulaşır. İkinci türev pozitiftir, nokta uygulanabilirdir ve küresel minimum elde edilir. Aynı çözüm mantığı konveks olmayan fonksiyona koşulsuz taşınamaz.

9.5. Konvekslik ve Küresel Optimum Garantisi

Türevlenebilir konveks fonksiyon, teğet düzlemin üzerinde kalır; bu özellik birinci derece optimalite koşullarını küresel sonuçlara bağlar. Negatif olmayan Hessian, iki kez türevlenebilir fonksiyonlar için konveksliğin yeterli karakterizasyonunu sağlar; sınırlı bölgede yerel bilgiyle doğrulama yapılırken bölge şartları unutulmamalıdır. Konveks olmayan problemlerde KKT koşulunu sağlayan bir nokta yerel minimum, maksimum veya eyer noktası olabilir.

f(y) ≥ f(x) + ∇f(x)ᵀ(y − x)

9.6. KKT Koşulları ve Düzenlilik

Eşitsizlik kısıtlarının çarpanları için işaret ve tamamlayıcılık koşulları zorunludur. KKT sisteminin gerekli olması uygun bir kısıt düzenlilik koşuluna bağlıdır; dışbükey problemde uygun ek varsayımlarla yeterli koşul elde edilir. Çarpanların ekonomik yorumu ancak model, ölçek ve aktif kısıt bilgileriyle birlikte yapılabilir. Sayısal algoritma raporundaki “stationary” durumu küresel optimum kanıtı olarak sunulmamalıdır.

9.7. Gradyan Yöntemleri ve Sayısal Türevler

Gradyan inişi, Newton ve yarı-Newton yöntemleri arasında iterasyon maliyeti, Hessian erişimi, bellek ve yakınsama hızı bakımından fark vardır. Otomatik türev doğru hesaplama grafiği için analitik türeve yakın sonuç verir; sonlu fark yaklaşımında adım çok küçük seçildiğinde yuvarlama, çok büyük seçildiğinde kesme hatası artar. Uygun sonlandırma ölçütleri gradyan normu, adım büyüklüğü ve kısıt ihlallerini birlikte ele almalıdır.

9.8. Hesaplamalı Örnek ve Çözüm

f(x)=(x−3)² ve x≥0 problemi, x=3 noktasında sıfır maliyetle optimuma ulaşır. Gradyan 2(x−3), Hessian 2 olduğundan amaç güçlü dışbükeydir. x=0 noktası uygulanabilir olsa da gradyan yönü ve KKT koşulları optimum olmadığını gösterir.

f′(x)=2(x−3);  f″(x)=2>0;  x*=3

9.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Sayısal çözücü farklı başlangıç noktalarından aynı x=3 çözümüne yakınsamalıdır. Toleransla küçük artıkları tam sıfır kabul etmekten kaçınılır.

Ünite 10: Dinamik Programlama ve Çok Aşamalı Optimizasyon

10.1. Durum, Eylem ve Bellman Bağıntısı

Dinamik programlama, optimum alt yapıdan yararlanan bir değer fonksiyonunu durumlar üzerinden tanımlar. Durum değişkeni gelecekteki maliyeti belirlemek için yeterli bilgiyi taşımalıdır; gereksiz geçmiş bilgisi durum uzayını büyütür. Bellek maliyeti durum sayısı ve geçiş sayısına bağlıdır.

10.2. Aşamalı Kaynak Tahsisi

Aşamalı kaynak tahsisinde karar, mevcut kaynağın bir kısmını tüketip yeni duruma geçer. Geriye doğru değer iterasyonu ufuk sonundan başlar. Çevrimli veya sonsuz ufuklu modellerde yakınsama ve iskonto varsayımları ayrıca açıklanmalıdır.

Vₜ(s) = min[a∈A(s)] {cₜ(s,a) + Vₜ₊₁(T(s,a))}

10.3. Durum Uzayı ve Doğrulama

Basit örnekler tam aramayla doğrulanır. Durum sıkıştırmasının optimal sonucu koruması için, eşlenen durumların gelecekte aynı karar kümesine ve maliyet yapısına sahip olması gerekir.

10.4. Sayısal ve Algoritmik Örnek

Dört aşamalı kaynak tahsisinde durum kalan kapasite, eylem o aşamadaki tahsis olsun. Terminal değer sıfır seçilip değer fonksiyonu geriye doğru hesaplanır. Durumda birikmiş maliyet saklamak gerekmez; bugüne kadarki toplam kararın gelecekteki uygulanabilirlik üzerinde etkisi yalnız kalan kapasiteyle temsil edilebiliyorsa bu sıkıştırma doğrudur.

10.5. Bellman İlkesinin Matematiksel Varsayımları

Dinamik programlama, gelecekteki en iyi kararın geçmişin tamamına değil, yeterli durum gösterimine bağlı olduğu ilkeye dayanır. Durum tanımı gelecekteki maliyet ve geçiş için gereken bilgileri taşımıyorsa Bellman yinelemesi doğru sonuç vermez. Ayrık zamanlı sonlu ufukta geriye doğru hesaplama uygun olur; sonsuz ufukta iskonto ve yakınsama koşulları gerekir. Aynı isimdeki dinamik programlama yöntemleri karar modeli, grafik ve dizisel algoritmalarda farklı durum tanımlarıyla kullanılabilir.

Vₜ(s) = minₐ [cₜ(s,a) + Vₜ₊₁(T(s,a))]

10.6. Durum Patlaması ve Ayrıştırma

Durum uzayı kaynak sayıları, zaman adımları ve önceki kararları birlikte kodladığında üstel büyüyebilir. Bellek tasarrufu için yalnız gerekli komşu aşamaların durumları tutulabilir; seyrek erişilen durumlarda sözlük tabanlı memoization avantajlıdır. Bununla birlikte durumu yaklaşık bir gösterime sıkıştırmak çözüm doğruluğunu değiştirebilir. Durum sayısı, geçiş sayısı ve bellek kullanımı aynı örnek kümesinde ölçülerek algoritma maliyeti belirlenir.

10.7. Politika Yeniden Oluşturma ve Optimum İz

Yalnız optimum değer tablosu saklandığında seçilen kararların dizisi kaybolabilir. Her durum için argmin eyleminin veya öncül işaretçisinin tutulması izlenebilir bir karar politikası üretir. Eşit değerde birden fazla en iyi eylem varsa sabit bağlama kuralı deterministik sonuç sağlayabilir. Üretilen politika, başlangıç durumundan uygulanarak birikimli maliyeti ve son kısıtları yeniden denetlemelidir.

10.8. Hesaplamalı Örnek ve Çözüm

İki aşamalı karar sürecinde her aşamada 0 veya 1 birim kaynak kullanılsın. Bir aşamanın seçimi kalan bütçeyi azalttığı için durum değişkeni zaman ile kalan bütçe çiftinden oluşmalıdır. Bütçe durumdan çıkarılırsa aynı görünen iki durum farklı gelecek eylem kümelerine sahip olur.

state = (stage, remaining budget)

10.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Yeniden kurulan karar dizisinin her aşamada bütçeyi aşmadığı test edilir. Bellek kısıtlı uygulamada yalnız komşu değer tabloları tutulsa da politika izleri gerekiyorsa öncül bilgisi korunmalıdır.

Ünite 11: Belirsizlik Altında ve Sağlam Optimizasyon

11.1. Belirsizlik Kümeleri ve Şans Kısıtları

Belirsiz parametreler tek tahminle temsil edildiğinde çözüm kırılganlaşabilir. Sağlam optimizasyon, belirlenen belirsizlik kümesindeki tüm parametreler için kısıt geçerliliğini arar; şans kısıtları ise olasılıksal güven düzeyini kullanır. İki yaklaşımın güvence anlamları farklıdır.

11.2. İki Aşamalı Stokastik Programlama

Senaryo tabanlı stokastik programlama kararları birinci aşama ve gözlem sonrası telafi kararları olarak ayırır. Gelecek bilgiye erişimi varsayan model sahada uygulanabilir değildir. Beklenen maliyet minimizasyonu kuyruk gecikmesi gibi kuyrukta ağır kuyruklu sonuçları tek başına sınırlamaz.

min[x] max[u∈𝒰] f(x,u);   P(g(x,ξ) ≤ 0) ≥ 1 − α

11.3. Örnek Dışı Geçerleme

Belirsizlik kümesinin veriye dayalı kalibrasyonu, örnek dışı denemeler ve duyarlılık senaryoları birlikte incelenir. Sağlam modelin her koşulda en düşük maliyeti vereceği iddia edilmez.

11.4. Sayısal ve Algoritmik Örnek

Talebin [8,12] aralığında olduğu kapasite planlamasında sağlam model en kötü durumu dikkate alarak en az 12 birim hizmet kapasitesi isteyebilir. Sadece beklenen talebe göre kurulan model 10 birim seçebilir. Hangisinin uygun olduğu maliyet ve hizmet seviyesi varsayımlarına bağlıdır.

11.5. Belirsizlik Kümeleri ve Sağlam Kararlar

Sağlam optimizasyonda karar değişkenleri belirlenmeden önce gerçekleşmemiş parametrelerin bir belirsizlik kümesinden gelebileceği kabul edilir. Kutusal ve elipsoidal kümeler farklı korumacılık dereceleri ve çözücü yapıları doğurur. Çok büyük küme aşırı maliyetli temkinli çözümlere, küçük küme ise yetersiz korumaya yol açabilir. Belirsizlik kümesi veri kaynağı ve ölçüm hatası gerekçelendirilmeden seçilmemelidir.

minₓ maxᵤ∈𝒰 f(x,u)

11.6. Şans Kısıtları ve Senaryo Yaklaşımları

Şans kısıtı, bir eşitsizliğin önceden belirlenen olasılıkla sağlanmasını talep eder. Olasılık dağılımı yanlış modellenmişse görünürde yüksek güvenilirlik gerçek performansı garanti etmez. Senaryo örneklemesinde eğitim senaryolarında uygun kalmak, örnek dışı başarısızlık olasılığının düşük olduğuna tek başına kanıt değildir. Bağımsız test senaryoları, güven aralıkları ve ihlal oranları birlikte raporlanmalıdır.

11.7. Çok Amaçlı Çözümler ve Pareto Üstünlüğü

Gecikme, enerji ve maliyet aynı anda iyileştirilmeye çalışıldığında tek bir mutlak optimum bulunmayabilir. Pareto üstünlüğü, en az bir amaçta daha iyi ve diğerlerinde daha kötü olmayan çözümleri ayırır. Ağırlıklı toplam yönteminde ağırlıklar birimleri ve normalizasyonu değiştirdiği için yorum dikkat gerektirir; konveks olmayan Pareto cephesinin bazı noktaları bu yöntemle bulunamayabilir. Çözümler karar uzayına geri taşınarak uygunluk bakımından kontrol edilmelidir.

11.8. Hesaplamalı Örnek ve Çözüm

Talebin [8,12] aralığında olabileceği ve tek kararla kapasite seçileceği kabul edilsin. Tüm talepler için kesintisiz hizmet şartı varsa 12 birim kapasite, bu aralık için uygulanabilir en küçük seçimdir. Ortalama talebe göre 10 birim seçilmesi ise sağlamlık şartını karşılamaz.

capacity ≥ max(demand) = 12

11.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Belirsizlik kümesinin neden [8,12] olduğu gerekçelendirilmeden “garantili” ifadesi kullanılmaz. Şans kısıtı için ayrıca talep dağılımı tanımlanmalıdır.

Ünite 12: Optimizasyon Çözücüleri ve Çözüm Doğrulaması

12.1. Model-Çözücü Arayüzü ve Ön İşleme

Modelleme katmanı değişkenleri, kısıtları ve amaç fonksiyonunu çözücüden bağımsız olarak tanımlamalıdır. Ön işleme aşaması sabit değişkenleri kaldırabilir, gereksiz kısıtları ayıklayabilir ve ölçekleyebilir. Çözücü çıktısı optimal, uygulanabilir, uygulanamaz, sınırsız veya zaman sınırına takılmış olabilir.

12.2. Çözüm Durumları ve Bağımsız Kontrol

Bir yazılım bileşeni çözücü sonucunu ham durumuyla tutmalı, uygulanabilir çözümü bağımsız doğrulamalı ve sayısal toleransları raporlamalıdır. Optimalite sertifikası bulunmayan sonuç yalnız uygulanabilir adaydır. Model sürümü ve giriş verileri kayıt altına alınır.

rₚ = ‖Ax − b‖;   r[d] = ‖Aᵀy + s − c‖;   ε[gap] = |cᵀx − bᵀy|

12.3. Tekrarlanabilir Başarım Deneyleri

Başarım karşılaştırmaları aynı donanım, tek çekirdek/çok çekirdek ayarları, rastgele tohum ve zaman bütçesiyle tekrarlanır. Geometrik ortalama hızlanma kullanılacaksa başarısız çözümler için sansürleme kuralı önceden açıklanmalıdır.

12.4. Sayısal ve Algoritmik Örnek

Çözücü x=(2,4) sonucunu optimum olarak bildirdiğinde uygulama Ax≤b denetimini ham veri üzerinden tekrar yapar. Daha sonra primal amaç, dual sınır ve toleranslar raporlanır. Durum kodu “time limit” ise bulunan değer yalnız uygulanabilir en iyi aday olabilir.

12.4.1. Açıklayıcı Sözde Kod

assert validate_dimensions(model)
result = solver.solve(model, limits, tolerances)
assert result.status in declared_statuses
if result.has_candidate:
    assert validate_original_constraints(result.x, model)
    report(result.objective, result.bound, result.gap)

12.5. Çözücü Durumlarının Semantik Ayrımı

OPTIMAL, FEASIBLE, INFEASIBLE, UNBOUNDED, TIME_LIMIT ve NUMERICAL_ISSUE gibi durumlar aynı anlama gelmez. Özellikle zaman aşımı, matematiksel uygulanamazlık kanıtı değildir. Bir çözücü hem sınır hem aday raporladığında doğrulama için iki bilginin de saklanması gerekir. Durumlar uygulamaya aktarılırken çözücünün sürümüne özgü kodlar genel bir anlam tablosuna çevrilmeli ve bilinmeyen durum sessizce optimum kabul edilmemelidir.

feasibility residual ≤ εₚ;   relative gap ≤ εₒ

12.6. Çözüm Sertifikalarının Bağımsız Denetimi

Üretilen aday çözüm orijinal değişken alanlarında sınanır; girdi dönüşümleri, presolve ve ölçekleme nedeniyle iç çözümün doğrudan kullanılmaması gerekir. Primal uygunluk ve dual sınır farklı kanıt katmanlarıdır. Tam sayılı modellerde adayın kısıtları sağladığı bağımsız kontrol edilebilirken küresel optimum iddiası geçerli sınır ve kapanmış boşluk ister. Test verileri küçük tam taranabilir örnekler, dejenere problemler ve koşulluluğu kötü matrisler içermelidir.

12.7. Deneysel Başarım ve Tekrar Üretilebilirlik

Ders kapsamında iki algoritmanın kıyaslanması aynı donanım, problem sürümü, presolve politikası ve toleranslarla yapılmalıdır. Ortalama süre yanında dağılım, zaman aşımında kalan örnek sayısı ve çözüm kalitesi gösterilmelidir. Tek örnekten genellenen hızlandırma iddiası yeterli değildir. Rastgele tohum, model dosyası, çözücü sürümü ve kaynak kullanım sınırı arşivlenirse deney yeniden çalıştırılabilir.

12.8. Hesaplamalı Örnek ve Çözüm

İki değişkenli bir model çözücü tarafından “optimal” döndürülse bile çözüm orijinal kısıt matrisiyle yeniden değerlendirilmelidir. Örneğin x=2, y=4 noktasında x+y≤6 ve 2x+y≤8 eşitlikte sağlanır; farklı sayısal ölçeklerde bu artıklara tolerans uygulanır.

r₁ = 6−(2+4)=0;  r₂ = 8−(2·2+4)=0

12.9. Bağımsız Doğrulama ve Gerçekleme Sınırları

Regresyon testi; uygulanamaz, sınırsız, çok optimumlu ve sayısal koşulluluğu zayıf örnekleri de içermelidir.

Kaynakça

• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. 2024 Release. McGraw Hill, 2024. ISBN 9781266933226.