Optimizasyon & Matematik

Zor

Sedgewick

Kısıtlı doğrusal denklemlere dayalı optimizasyon problemlerini Simplex tabloları, Bland döngü önleme kuralı ve gradyan inişi (Steepest Descent) ile çözer.

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Algoritması

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Açıklaması

Doğrusal Programlama (LP), doğrusal eşitlik veya eşitsizlik kısıtları altında doğrusal bir amaç fonksiyonunu (objective function) maksimize veya minimize etme problemidir.

George Dantzig tarafından geliştirilen Simpleks Yöntemi (Simplex Method), kısıtların oluşturduğu dış bükey politopun (convex polytope) köşeleri arasında dolaşarak en iyi değeri arar. Bir köşeden komşu köşeye geçmek için Simplex pivot işlemleri (satır işlemleri) yapılır.

Bland Döngü Önleme Yöntemi (Bland's Anti-cycling Rule), pivot adımlarında aynı köşeler arasında sonsuz döngüye (cycling) girilmesini engellemek için en küçük indisli değişkeni seçme kuralıdır. En Dik İniş (Steepest Descent / Gradient Descent) ise gradyan yönünde adım atarak fonksiyonun yerel minimumunu arayan ardışık bir optimizasyon metodudur.

Kaynak Notları

Simpleks yöntemi pratikte son derece hızlı çalışmasına rağmen, Klee-Minty küpü gibi yapay kısıtlarda üstel ($O(2^d)$) adım sürebilir.
Modern çözücüler hem Simpleks hem de polinomsal zamanda koşan İç Nokta Yöntemlerini (Interior Point Methods) kullanır.

Çalışma Prensibi

Simpleks Tablosunun Hazırlanması:
Eşitsizlik kısıtlarını gevşek değişkenler (slack variables) ekleyerek eşitliğe dönüştür.
Amaç fonksiyonunu tablonun en alt satırına yerleştir (Tablo matrisi).
Simplex Döngüsü (Pivoting):
Alt satırdaki en negatif katsayıya sahip sütunu seç (Entering variable).
Bland kuralı aktifse: birden fazla negatif varsa en küçük indisli değişken sütununu seç.
Her kısıt satırı için: sağ taraftaki sabitin, seçilen sütundaki katsayıya oranını hesapla.
Pozitif oranlar içindeki en küçük oranı veren satırı seç (Leaving variable / Pivot Row).
Pivot elemanını (satır ve sütunun kesişimi) satır işlemleriyle 1 yap.
Diğer satırlardaki pivot sütun elemanlarını yok etmek (0 yapmak) için Gauss-Jordan satır işlemleri uygula.
Alt satırda hiç negatif katsayı kalmayana kadar adımları tekrarla.
En alt satırın sağ köşesindeki değer maksimum sonucu verir.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Algoritması - TypeScript

1export function simplexPivot(
2  tableau: number[][],
3  pivotRow: number,
4  pivotCol: number
5): void {
6  const R = tableau.length;
7  const C = tableau[0].length;
8  const pivotVal = tableau[pivotRow][pivotCol];
9  
10  // Normalize pivot row
11  for (let j = 0; j < C; j++) {
12    tableau[pivotRow][j] /= pivotVal;
13  }
14  
15  // Reduce other rows
16  for (let i = 0; i < R; i++) {
17    if (i !== pivotRow) {
18      const factor = tableau[i][pivotCol];
19      for (let j = 0; j < C; j++) {
20        tableau[i][j] -= factor * tableau[pivotRow][j];
21      }
22    }
23  }
24}

Kendi Verilerinizle Test Edin

Kısıtlı doğrusal denklemleri matris tablosuna dökerek Simplex pivot adımlarını ve Bland kuralını izleyin.

Simplex Optimizasyon Simülatörü

Kısıtlı doğrusal denklemleri matris tablosuna dökerek Simplex pivot adımlarını ve Bland kuralını izleyin.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(d) - Köşeler arasında doğrudan geçiş yapıldığında

Ortalama Durum: Polinomsal - O(R * C) pivot adımı

En Kötü Durum: O(2^d) - Klee-Minty küpü gibi üstel durumlar

Alan Karmaşıklığı

O(R * C) - Simplex tablosu matrisi saklama - Bu algoritmanın karmaşıklığı belirtilmemiş.

Simpleks Politop Optimizasyonu

Dış bükey politopun her bir köşesi doğrusal denklemlerin temel bir çözümüne (Basic Feasible Solution) karşılık gelir.
Bland Döngü Önleme kuralı, pivot seçiminde kararsız kalındığında en düşük indise sahip sütunu/satırı seçerek tablonun kısır döngüye (cycling) girip kilitlenmesini kesin olarak engeller.
En Dik İniş (Steepest Descent), doğrusal olmayan optimizasyonlarda gradyan vektörünün tersi yönünde ($-\nabla f$) hareket ederek lokal minimumu arar.

Avantajlar ve Dezavantajlar

Avantajlar

Doğrusal programlama problemlerinde pratik veri setleri için son derece hızlı çalışır.
Kesin optimal sonucu ve amaç fonksiyonunu maksimum yapan değişkenlerin değerlerini verir.
Duyarlılık analizi (sensitivity analysis) yapmaya imkan tanır.

Dezavantajlar

Teorik olarak en kötü durumda üstel sürede çalışır (NP-Zor gibi davranabilir).
Doğrusal olmayan (non-linear) kısıtlar barındıran problemlere uygulanamaz.
Sayısal hassasiyet (floating point rounding) hatalarına karşı duyarlıdır.

İlgili Algoritmalar

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Gauss-Jordan Eliminasyonu

Doğrusal denklem sistemlerini çözen ve Simplex pivotlarında kullanılan matris indirgeme tekniği.

Steepest Descent

Doğrusal kısıtı olmayan sürekli fonksiyonlarda gradyan bazlı arama yöntemi.

Yükleniyor // RUNTIME_INITIALIZINGAlgoritma ve bileşen ağacı hazırlanıyor...

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Algoritması

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Açıklaması

Doğrusal Programlama (LP), doğrusal eşitlik veya eşitsizlik kısıtları altında doğrusal bir amaç fonksiyonunu (objective function) maksimize veya minimize etme problemidir.

Kaynak Notları

Simpleks yöntemi pratikte son derece hızlı çalışmasına rağmen, Klee-Minty küpü gibi yapay kısıtlarda üstel ($O(2^d)$) adım sürebilir.
Modern çözücüler hem Simpleks hem de polinomsal zamanda koşan İç Nokta Yöntemlerini (Interior Point Methods) kullanır.

Çalışma Prensibi

Simpleks Tablosunun Hazırlanması:
Eşitsizlik kısıtlarını gevşek değişkenler (slack variables) ekleyerek eşitliğe dönüştür.
Amaç fonksiyonunu tablonun en alt satırına yerleştir (Tablo matrisi).
Simplex Döngüsü (Pivoting):
Alt satırdaki en negatif katsayıya sahip sütunu seç (Entering variable).
Bland kuralı aktifse: birden fazla negatif varsa en küçük indisli değişken sütununu seç.
Her kısıt satırı için: sağ taraftaki sabitin, seçilen sütundaki katsayıya oranını hesapla.
Pozitif oranlar içindeki en küçük oranı veren satırı seç (Leaving variable / Pivot Row).
Pivot elemanını (satır ve sütunun kesişimi) satır işlemleriyle 1 yap.
Diğer satırlardaki pivot sütun elemanlarını yok etmek (0 yapmak) için Gauss-Jordan satır işlemleri uygula.
Alt satırda hiç negatif katsayı kalmayana kadar adımları tekrarla.
En alt satırın sağ köşesindeki değer maksimum sonucu verir.

Kod Örnekleri

Aşağıdaki uygulamalar PDF kaynaklarındaki pseudo kod akışını modern veri yapılarıyla ifade eder. Kenar durumları görünür bırakıldığı için örnekler doğrudan test edilebilir.

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Algoritması - TypeScript

1export function simplexPivot(
2  tableau: number[][],
3  pivotRow: number,
4  pivotCol: number
5): void {
6  const R = tableau.length;
7  const C = tableau[0].length;
8  const pivotVal = tableau[pivotRow][pivotCol];
9  
10  // Normalize pivot row
11  for (let j = 0; j < C; j++) {
12    tableau[pivotRow][j] /= pivotVal;
13  }
14  
15  // Reduce other rows
16  for (let i = 0; i < R; i++) {
17    if (i !== pivotRow) {
18      const factor = tableau[i][pivotCol];
19      for (let j = 0; j < C; j++) {
20        tableau[i][j] -= factor * tableau[pivotRow][j];
21      }
22    }
23  }
24}

Kendi Verilerinizle Test Edin

Kısıtlı doğrusal denklemleri matris tablosuna dökerek Simplex pivot adımlarını ve Bland kuralını izleyin.

Simplex Optimizasyon Simülatörü

Kısıtlı doğrusal denklemleri matris tablosuna dökerek Simplex pivot adımlarını ve Bland kuralını izleyin.

Girdi

Sonuç

Henüz çalıştırılmadı

Algoritma Analizi

Zaman ve Alan Karmaşıklığı

Zaman Karmaşıklığı

En İyi Durum: O(d) - Köşeler arasında doğrudan geçiş yapıldığında

Ortalama Durum: Polinomsal - O(R * C) pivot adımı

En Kötü Durum: O(2^d) - Klee-Minty küpü gibi üstel durumlar

Alan Karmaşıklığı

O(R * C) - Simplex tablosu matrisi saklama - Bu algoritmanın karmaşıklığı belirtilmemiş.

Simpleks Politop Optimizasyonu

Dış bükey politopun her bir köşesi doğrusal denklemlerin temel bir çözümüne (Basic Feasible Solution) karşılık gelir.
Bland Döngü Önleme kuralı, pivot seçiminde kararsız kalındığında en düşük indise sahip sütunu/satırı seçerek tablonun kısır döngüye (cycling) girip kilitlenmesini kesin olarak engeller.
En Dik İniş (Steepest Descent), doğrusal olmayan optimizasyonlarda gradyan vektörünün tersi yönünde ($-\nabla f$) hareket ederek lokal minimumu arar.

Avantajlar ve Dezavantajlar

Avantajlar

Doğrusal programlama problemlerinde pratik veri setleri için son derece hızlı çalışır.
Kesin optimal sonucu ve amaç fonksiyonunu maksimum yapan değişkenlerin değerlerini verir.
Duyarlılık analizi (sensitivity analysis) yapmaya imkan tanır.

Dezavantajlar

Teorik olarak en kötü durumda üstel sürede çalışır (NP-Zor gibi davranabilir).
Doğrusal olmayan (non-linear) kısıtlar barındıran problemlere uygulanamaz.
Sayısal hassasiyet (floating point rounding) hatalarına karşı duyarlıdır.

İlgili Algoritmalar

Doğrusal Programlama / Simpleks (Linear Programming / Simplex) Algoritması ile benzer veya alternatif olarak değerlendirilebilecek diğer başlıklar:

Gauss-Jordan Eliminasyonu

Doğrusal denklem sistemlerini çözen ve Simplex pivotlarında kullanılan matris indirgeme tekniği.

Steepest Descent

Doğrusal kısıtı olmayan sürekli fonksiyonlarda gradyan bazlı arama yöntemi.