Ağda Maksimum Akış ve Minimum Kesit

Bir dağıtım ağında her bağlantının ayrı bir sınırı bulunabilir. Kaynaktan çıkan iki hattın kapasitesini toplamak, aynı miktarın hedefe ulaşabildiğini göstermez. Aradaki ortak bir bağlantı daha dar olabilir; bazı kollar hedefe hiç bağlanmayabilir. Maksimum akış hesabı, bütün yönlü bağlantıları aynı anda değerlendirerek kaynak ile hedef arasında taşınabilen en yüksek ortak miktarı bulur. Sonuç, tek bir bağlantının kapasitesi veya listedeki bütün sayıların toplamı değildir. Her ara düğümde gelen miktarın çıkan miktarla dengelenmesi gerekir.

Bu araçta ağı siz tanımlarsınız. Düğümleri anonim kısa etiketlerle, bağlantıları ise başlangıç, hedef ve kapasite olarak yazarsınız. Aynı birim ve aynı dönem bütün bağlantılarda geçerli olmalıdır. Örneğin her kapasiteyi kutu/saat olarak belirlediyseniz sonuç da kutu/saat olur. Bir satıra günlük, diğerine saatlik miktar yazmak sayısal olarak kabul edilebilir görünse bile anlamlı bir model oluşturmaz. Birim dönüştürme veya gerçek kapasite doğrulaması yapılmadığından, bu tutarlılığı hesap öncesinde kurmanız gerekir.

Kaynak, akışın ağa net olarak girdiği düğümdür. Hedef ise akışın net olarak toplandığı düğümdür. Bunların etiketleri farklı olmalıdır. Kaynak veya hedefin bir kenar satırında geçmemesi de mümkündür; böyle bir düğüm ağdan silinmez. Bağlantısız bir kaynak ile hedef için sonuç sıfır olur. Bu durum, girilen kapasite modelinde pozitif taşıma yolu bulunmadığını gösterir. Gerçek işletmenin hiçbir işi yapamayacağı veya bütün fiziksel bağlantılarının kopuk olduğu sonucuna tek başına götürmez.

Kaynağa gelen bir kenar da yazılabilir. Ancak bu kenarın kapasitesi, kaynağın dışarıya gönderebildiği net akışa kendiliğinden eklenmez. Benzer biçimde hedeften çıkan bir kenar, hedefin net aldığı miktarı yapay biçimde büyütmez. Hesap, kaynak için çıkış eksi girişi; hedef için giriş eksi çıkışı kullanır. İki net miktar birbirine eşittir. Bu nedenle kaynak ve hedefe ilişkin sonuçları yalnız bir yönün toplamı gibi okumamak gerekir.

Kaynak ve hedef dışındaki her düğümde toplam giriş ile toplam çıkış eşit tutulur. Ara düğüm bu modelde ürün üretmez, tüketmez veya biriktirmez. Bir düğüme beş birim giriyorsa, aynı çözümde toplam beş birim çıkmalıdır. Girişlerden biri sıfır kullanılabilir; başka bir giriş bütün gereksinimi karşılayabilir. Önemli olan bütün bağlantıların kapasitelerine uyulması ve düğümün net farkının sıfır kalmasıdır. Sonuçta her düğümün net çıkış eksi giriş satırı ayrı gösterilir.

Bu kabul, depolama ve zamanlama içeren sistemleri sınırlar. Bir deponun bugün mal alıp yarın göndermesi, tek dönemli bu ağda kendiliğinden temsil edilmez. Aynı şekilde bir ara noktadaki toplam işleme kapasitesi, yalnız düğüm etiketi yazılarak belirlenmiş olmaz. Araç kenar kapasitelerini çözer; ayrı düğüm kapasitesi veya stok hareketi alanı bulunmaz. Gerçek sorunuz böyle bir özellik gerektiriyorsa, basit düğüm korunumu modelinin yeterli olup olmadığını ayrıca değerlendirin.

Her kenar yalnız yazıldığı yönde gerçek kapasite sağlar. A noktasından B noktasına verilen üç birim, B noktasından A noktasına da üç birim taşınabileceği anlamına gelmez. Gerçekte iki yön varsa iki ayrı satır yazılmalıdır. Bu satırların kapasiteleri aynı olmak zorunda değildir. Karşı yöndeki kapasite ayrı bir kısıttır; toplamından tek bir yönsüz kapasite üretilmez. Yönlerin ters yazılması, ağın ulaşılabilirliğini ve maksimum toplamı tamamen değiştirebilir.

Aynı iki düğüm arasında aynı yönde birden fazla bağlantı da bulunabilir. Araç bu paralel kenarları ayrı satırlar olarak korur. Böylece her özgün bağlantının kapasitesi, atanan akışı ve kalan kapasitesi okunabilir. Ancak aynı fiziksel hattı yanlışlıkla iki kez yazarsanız model o hattı iki ayrı kapasite kabul eder. Paralel satırlar ancak gerçekten ayrı kapasite varsayımını temsil ediyorsa kullanılmalıdır. Aynı düğümden yine kendisine giden kenarlar bu dar giriş kapsamında kabul edilmez.

Kapasite, ilgili kenardan geçmesine izin verdiğiniz en yüksek miktardır. Atanan akış ise bulunan çözümde o kenarın gerçekten kullandığı matematiksel miktardır. Akış sıfır ile kapasite arasında kalır. Bir kenarın boş kapasitesi bulunması, ağın tamamının daha fazla taşıyabileceğini göstermez. O kenara mal getiren önceki bağlantı veya malı hedefe taşıyan sonraki bağlantı sınırlayıcı olabilir. Sonuç tablosunda kalan ileri kapasite, yalnız o özgün kenarın kapasitesinden atanan akışın çıkarılmasıyla bulunur.

Kapasitesi sıfır olan kenar yazılabilir. Böyle bir satırın akışı da sıfır olur ve pozitif taşıma yolu sağlamaz. Sıfır sayısı burada bilinmeyen kapasitenin yerine kullanılmamalıdır. Kapasiteyi bilmiyorsanız, sıfır yazmak gerçek belirsizliği ölçmüş olmaz; yalnız bağlantıyı bu modelde kullanılmaz kabul eder. Bütün kapasite değerleri varsayımsal veya dışarıda belirlenmiş kullanıcı girdileridir. Sonuç, bu sayıların ölçülmüş, güncel veya işletme tarafından onaylanmış olduğunu doğrulamaz.

Bir kesit, düğümleri kaynak bir tarafta ve hedef diğer tarafta kalacak biçimde iki kümeye ayırır. Kesit kapasitesi, kaynak tarafından hedef tarafına geçen özgün yönlü kenar kapasitelerinin toplamıdır. Ters yönde kesiti geçen kenarlar bu toplamdan çıkarılmaz veya bu toplama eklenmez. Kaynaktan hedefe ulaşan her akış, kaynak tarafından en az bir kez ayrılmak zorundadır. Bu nedenle herhangi bir kesitin kapasitesi, mümkün akış için bir üst sınır verir.

Minimum kesit, bu üst sınırlar arasında en küçük kapasiteye sahip olanıdır. Araç bir maksimum akış bulduğunda, akış miktarı ile gösterdiği kesitin kapasitesini karşılaştırır. Değerler eşitse, daha yüksek bir akışın bu kesiti aşması gerekeceği için mevcut çözüm tanımlanan modelde optimumdur. Bu eşitlik, yalnız bir algoritmanın başarılı bittiği mesajından daha açıklayıcı bir denetim sağlar. Hem en yüksek taşımayı hem de aynı miktardaki sınırlayıcı kapasiteyi birlikte okuyabilirsiniz.

Bir bağlantıya ilk aşamada verilen miktar son çözümde aynı kalmak zorunda değildir. Sonraki bir yol, önceki atamanın bir bölümünü azaltıp başka bir kola yönlendirmeyi gerektirebilir. Bu yeniden düzenleme, gerçek hayatta ters yönde yeni bir hat varmış gibi yorumlanmaz. Hesap yalnız önceki matematiksel atamayı geri alabilecek bir düzeltme olanağı tutar. Böylece ilk bulunan yolun bütün sonraki seçenekleri gereksiz biçimde kapatması önlenir.

Bu özellik nedeniyle elle yapılan basit bir yerleştirme, maksimum sonucu bulamayabilir. İlk yol dar bir ortak bağlantıyı kullanıp daha iyi bir dağılımı engelliyormuş gibi görünebilir. Önceki atamayı gerektiğinde azaltabilen çözüm, bütün ağ için daha yüksek toplama ulaşabilir. Araç pozitif kalan kapasite bulunan yollar üzerinden ilerler; hedefe artırılabilir yol kalmadığında durur. Kenarların listedeki sırası süreçteki dağılımı etkileyebilir, fakat doğru kurulmuş aynı ağın maksimum toplamını değiştirmez.

Aynı maksimum miktarı sağlayan farklı kenar planları bulunabilir. İki paralel hat arasında dağılım değişebilir veya ağın simetrik kolları farklı kullanılabilir. Minimum kesit de her ağda tek olmak zorunda değildir. Bu nedenle iki farklı çözümde tek tek akışların farklı görünmesi, toplamlar eşit ve bütün kısıtlar sağlanıyorsa otomatik hata değildir. Karşılaştırırken önce kapasite sınırlarına, ara düğüm korunumu ile kaynak ve hedefin net miktarlarına bakın.

Burada tek bir geçerli optimum plan ve ona bağlı bir minimum kesit gösterilir. Bütün optimum planların listesi, en düşük maliyetli plan veya en az kullanılan bağlantı sayısı aranmaz. Bir kenarın bu çözümde sıfır kullanılması, onun her optimum çözümde gereksiz olduğunu kanıtlamaz. Aynı şekilde gösterilen kesitte bulunması, o fiziksel hattın mutlaka genişletilmesi gerektiği anlamına gelmez. Bir yatırım kararında kapasite dışında fiyat, güvenilirlik ve gerçek talep gibi ayrı bilgiler gerekir.

Düğüm etiketleri harfle başlayan en fazla on altı karakterden oluşur. Etiketlerde İngilizce harf, rakam, alt çizgi ve kısa çizgi kullanılabilir. Büyük ve küçük harf ayrı düğümler oluşturur; A ile a aynı kabul edilmez. Açıklayıcı uzun isimleri ayrı notunuzda tutup hesapta kısa anonim etiketler kullanabilirsiniz. Her dolu kenar satırında başlangıç, hedef ve kapasite noktalı virgülle ayrılır. Boş satırlar atlanır; dolu bir satırdaki eksik veya fazla alan kabul edilmez.

Kaynak ve hedef dahil en fazla otuz farklı düğüm ve yüz yirmi dolu kenar satırı desteklenir. Her kapasite sıfır ile bir milyar arasında ve en fazla üç ondalıklıdır. Nokta ile virgül yalnız ondalık ayırıcı olarak kullanılır; binlik gruplama yazılmaz. Örneğin 1.000 bu girişte bin değil, bir anlamına gelir. Fazla ondalık, üslü yazım ve birim eki sessizce değiştirilmez. Bu teknik sınırlar fiziksel ağ standardı veya doğruluk ölçütü değildir.

İki kapasite senaryosunu karşılaştırırken kaynak, hedef, yönler, düğüm etiketleri ve ortak birim aynı kalmalıdır. Yalnız bir kenarı artırdığınızda toplamın değişmemesi mümkündür; başka bir kesit hâlâ sınırlayıcı olabilir. Birden fazla kenarı aynı anda değiştiriyorsanız sonucu tek bir hattın etkisi gibi adlandırmayın. Araç senaryoları kendiliğinden saklamaz veya gerçek işletme verisi getirmez. Değiştirdiğiniz değerleri kendi notunuzda açıkça ayırarak karşılaştırmanız, aynı sayının farklı varsayımlara bağlanmasını önler.

Kapasitelerin tamamını aynı pozitif katsayıyla çarptığınızda maksimum miktar ve bir kesitin kapasitesi de aynı katsayıyla değişir. Ancak yalnız bir hattın büyütülmesi için böyle basit bir orantı beklenmez. Bir bağlantıyı kaldırmak istiyorsanız kapasitesini sıfır seçmek ile satırı çıkarmak maksimum miktar bakımından aynı olabilir; düğüm ve kenar sayıları ise farklı görünebilir. Özellikle birden fazla optimum çözüm bulunan ağlarda dağılımı değil, önce toplam ve korunum ilişkilerini karşılaştırın.

Önce kenar tablosundaki kapasite, atanan akış ve kalan ileri kapasiteyi birlikte okuyun. Her satırda akış ile kalan kapasitenin toplamı özgün kapasiteye eşit olmalıdır. Aynı yönlü iki satır varsa bunların ayrı kapasiteyi temsil edip etmediğini giriş listenizden kontrol edin. Bu denetim, bir hattın yanlışlıkla iki defa yazılmasını kendi başına bulmaz; hesabın girdiğiniz satırları nasıl kullandığını görmenizi sağlar. Sayısal tutarlılık ile modelin gerçek durumu temsil etmesi ayrı konulardır.

Sonra düğüm net farklarını inceleyin. Ara düğümlerin bütün farkları sıfır, kaynağın farkı pozitif maksimum miktar, hedefin farkı ise aynı miktarın negatif işaretlisi olmalıdır. Sıfır akışta bütün farklar sıfır olabilir. Bu okumada hedef satırındaki negatif işaret bir zarar veya kayıp değildir; satırın çıkış eksi giriş yönünde tanımlanmasının sonucudur. Hedefe net giriş ayrı özet satırında pozitif miktar olarak gösterilir.

Son olarak minimum kesitte Evet yazan özgün kenarların kapasitelerini toplayıp kesit özetiyle karşılaştırabilirsiniz. Bu toplam maksimum akışa eşitse gösterilen sertifikanın anlamı görünür olur. Ancak aynı toplamdan her kenarın eşit ölçüde önemli olduğu sonucu çıkmaz. Farklı bir minimum kesit de bulunabilir; yalnız bir kesitteki tek hattı büyütmek bütün üst sınırları kaldırmayabilir. Yeni senaryoyu yeniden hesaplamak, böyle bir değişimin modeldeki etkisini görmenin doğrudan yoludur.

Bu model aynı anda tek bir ortak akışı taşır. Ayrı ürünlerin birbirinden farklı kısıtlarla taşınması, zaman içinde hareket, kenar maliyeti, kayıp veya arıza olasılığı hesaba katılmaz. Bir borunun kapasitesini yazmak, basınç ve pompa denklemlerini çözmüş olmaz. Bir ulaşım hattının kapasitesini yazmak da yolculuk süresini veya araç çizelgesini belirlemez. Maksimum akış ile en kısa yol farklı sorulardır; yüksek taşıma miktarı en hızlı teslim anlamına gelmez.

MIT ders notları kapasite kısıtı, ara düğüm korunumu, artırılabilir yol ve maksimum akış–minimum kesit ilişkisi için yöntem kaynağıdır. Buradaki Türkçe anlatım, hesap uygulaması ve örnek ağlar özgün hazırlanmıştır. Kaynağın kodu, şekli, alıştırması veya anlatımı aktarılmamıştır. Kaynak atfı, bu aracın MIT tarafından incelendiği veya onaylandığı iddiası değildir. Hesap alanına gerçek kişi, hesap veya sistem kimliği yazmanız gerekmez; anonim düğüm adlarıyla aynı matematiksel soruyu kurabilirsiniz.

Örnek 1 — İki koldan toplam 9 birim

Beş yönlü kenar, ortak birim/dönem kapasitesi. Her kenar aynı döneme aittir.

- Kaynak: S - Hedef: T

Örnek 2 — Paralel ve karşı yönlü kenarlar

Kaynak girişindeki 7 birim karşı yönlü kapasite kaynak çıkışına eklenmez; hedef sınırı 2,5 birimdir.

- Kaynak: S - Hedef: T

Örnek 3 — Hedefe bağlanmayan iki kol

Kaynak tarafındaki 3 birim hedef tarafındaki 4 birime bağlanmaz. Optimum sıfırdır.

- Kaynak: S - Hedef: T

Ortak birimle ilk ağı kurma

1. Önce bütün kapasitelerin ortak birim ve döneme ait olduğunu belirleyin. Kaynak ve hedefe farklı anonim etiketler verin. 2. Her gerçek yönlü bağlantıyı ayrı satıra yazın; paralel satırların aynı kapasiteyi iki kez temsil etmediğini kontrol edin. 3. Sonuçta bütün kenar sınırlarını, iç düğüm net farklarını ve akış–kesit eşitliğini birlikte okuyun. Fiziksel kapasite doğrulamasını ayrı tutun.

Tek kapasite değişikliğini karşılaştırma

1. İlk senaryonun kaynak/hedef, yön ve kapasitelerini not edin; özellikle gösterilen kaynak ve hedef taraflarını ayırın. 2. Aynı ortak birimle yalnız seçtiğiniz gerçek kenarın kapasitesini değiştirin ve yeniden hesaplayın; aynı hattı yeni satırla çoğaltmayın. 3. Önce maksimum toplamı karşılaştırın; değişmiyorsa başka bir kesit sınırlayıcı olabilir. Tekil optimum atamaların farklılaşması tek başına hata değildir.