George Dantzig: Simplex Algoritmasının Mucidi ve "Berkeley'de Derse Geç Gelen Öğrenci"

Modern operasyon araştırmasının ve uygulamalı matematiğin en etkili figürlerinden biri George Dantzig (1914–2005)'tir. Onun 1947'de yazdığı Simplex algoritması, lineer programlama problemlerini çözmek için bilgisayar biliminin en sık çalıştırılan algoritmalarından biri haline geldi. Modern hava yolu çizelgeleme, lojistik optimizasyon, üretim planlaması, finansal portföy yönetimi — hepsi onun yöntemine dayanır.

Ama Dantzig'in ününün diğer bir kaynağı, bilim tarihindeki en ünlü hikâyelerden biridir.

"Berkeley'nin geç gelen öğrencisi" hikâyesi

1939 yılı, University of California, Berkeley. George Dantzig, Jerzy Neyman'ın istatistik doktora programında bir öğrenci. Bir gün derse geç geldi. Tahta üzerinde iki matematik problemi yazıyordu. Dantzig, ödevi sandığı bu iki problemi defterine kopyaladı.

Birkaç gün uğraştı; her ikisini de çözdü. Çözümlerini Profesör Neyman'a bıraktı. "Geç verdiğim için özür dilerim" diye not bıraktı.

Altı hafta sonra Neyman heyecanlı biçimde Dantzig'in evinin kapısına geldi. "Şu problemler ödev değildi! Onlar istatistiğin çözülmemiş ünlü açık problemleriydi!"

Dantzig'in çözümleri, Annals of Mathematical Statistics dergisinde yayımlandı (1940). Bu, onun doktora tezinin temelini oluşturdu.

Bu hikâye, sonraki yıllarda popüler kültürün bir parçası oldu. "Good Will Hunting" (1997) filminde Matt Damon'ın canlandırdığı karakterin tahtadaki problemleri çözmesi sahnesi, doğrudan bu Dantzig hikâyesinden esinlendi.

Tehlikeli okuma alışkanlıkları

Dantzig, hikâye hakkında yıllar sonra şöyle anlattı:

"Eğer Neyman'ın bana verdiği problemlerin ünlü açık problemler olduğunu bilseydim, muhtemelen onlara dokunmazdım. Ama 'sadece ev ödevi' olduğunu sandığım için, fazla düşünmeden çözmeye giriştim."

Bu, "zorluk hakkındaki bilgi, sıkça karşılaştığımız bir engeldir" gerçeğinin güzel bir örneğidir. Bir problemin "çözülemez" olduğunu bilmek, bizi denemekten alıkoyabilir.

II. Dünya Savaşı: askeri lojistik

Dantzig doktorasını bitirdikten sonra, II. Dünya Savaşı sırasında ABD Hava Kuvvetleri için çalıştı. Görevi: dev ölçekli askeri lojistik optimizasyonu yapmak.

Soru şuydu: yüzlerce uçak filomuz var, binlerce farklı hedef, milyonlarca farklı tedarik kalemi. Bu kaynakları en verimli biçimde nasıl dağıtırız?

O dönemde böyle problemler el ile çözülürdü; her görev için ayrı bir hesap. Süreç uzun ve hataya açıktı. Dantzig, problemin matematiksel yapısını analiz etti ve şu önemli gözlemi yaptı:

"Bu problemler özünde lineer kısıtlamalı lineer optimizasyon problemleridir. Yani 'şu kadar yakıttan fazla kullanma', 'her uçak en az şu görevi yapsın' gibi tüm kısıtlamalar lineer (doğrusal) eşitsizliklerdir; amaç fonksiyonu (toplam maliyet, toplam süre) da lineerdir."

Bu görüş, lineer programlama denilen yeni bir matematik dalının doğum belgesidir.

Simplex algoritması (1947)

Lineer programlama problemini formüle etmek bir şeydir; çözmek başka. Standart matematik teknikleri (örneğin tüm köşeleri kontrol etme) kombinatorik patlama yaşar; binlerce değişkenli bir problem trilyonlarca olası köşeye sahip olabilir.

Dantzig, 1947'de Simplex algoritmasını geliştirdi. Mantığı:

1. Olası bir başlangıç köşesi bul.
2. Komşu köşelere bak; eğer biri daha iyiyse oraya geç.
3. Komşulardan hiçbiri daha iyi değilse, dur: bu köşe optimumdur.

Bu basit "komşu köşeleri tara" stratejisi şaşırtıcı biçimde etkilidir. Teorik olarak en kötü durumda üstel zaman alabilir (çok özel kötü tasarlanmış örneklerde); ama pratikte hemen hemen her zaman polinom zamanda çalışır.

Bu pratik etkinlik, Simplex'i 20. yüzyılın en çok çalıştırılan algoritmalarından biri yapmıştır. Modern operasyon araştırması yazılımları (CPLEX, Gurobi, GLPK) hâlâ Simplex'in geliştirilmiş varyantlarını çalıştırır.

Berlin Hava Köprüsü (1948-49)

Simplex algoritmasının ilk büyük pratik uygulaması, Berlin Hava Köprüsü sırasında gerçekleşti.

1948'de Sovyet Rusya, Batı Berlin'i kara yollarından izole etti. ABD ve İngiltere, bir yıl boyunca uçaklarla her şeyi (yiyecek, kömür, ilaç) hava yoluyla taşımak zorunda kaldı. Bu, modern tarihin en büyük lojistik operasyonlarından biri.

Dantzig ve diğer matematikçiler, hangi uçağın ne taşıyacağını, hangi rotayı izleyeceğini, hangi havaalanına ineceğini Simplex tabanlı modellerle optimize etti. Sonuç: yaklaşık 15 ay boyunca, günde ortalama 8000 ton yük Berlin'e taşındı. Sovyet ablukası başarısız oldu.

Bu olay, operasyon araştırmasının modern bir disiplin olarak doğuşunun da sembolüdür. II. Dünya Savaşı'nda askeri amaçlar için geliştirilen teknikler, savaş sonrası endüstriyel uygulamalara taşındı.

Modern uygulamalar

Lineer programlama ve Simplex algoritması, bugün dünya genelinde milyarlarca dolar ekonomik değer üretir:

Üretim planlaması

Bir fabrika hangi ürünü ne kadar üretsin ki kâr maksimum, kısıtlamalar (işçi saati, hammadde, makine kapasitesi) ihlal edilmesin? Klasik lineer programlama problemi.

Hava yolu çizelgeleme

Bir havayolu hangi uçağı hangi rotaya, hangi pilotu hangi uçağa, hangi yolcuyu hangi koltuğa atasın? Devasa kombinatorik problem; Simplex tabanlı modellerle çözülür.

Finansal portföy

Sınırlı sermaye, farklı yatırım seçenekleri, farklı risk-getiri profili. Markowitz portföy teorisi (Nobel ekonomi ödülü 1990), lineer programlamanın doğrudan uygulamasıdır.

Yatırım planlama

Bir sermayedar hangi projeyi finanse etsin ki risk düşük, getiri yüksek?

Beslenme problemi

Sınırlı bütçe, hangi yiyecekleri al ki günlük besin gereksinimlerini karşıla ve toplam maliyet minimum? Dantzig'in 1947'deki ilk somut uygulamalarından biri. Sonuç enteresan: matematiksel optimum, "çok az çeşitlilik, çoğunlukla buğday + süt + lahana" gibi pratik olmayan diyetler veriyordu. Bu, "matematiksel optimumun her zaman insan pratiği için anlamlı olmadığı" konusunda klasik bir derstir.

Telekomünikasyon ağ tasarımı

Hangi şehirden hangi şehre kabloları nasıl döşeyelim ki toplam maliyet minimum, kapasite gereksinimleri karşılansın? Tipik lineer programlama.

Akıllı şehirler

Trafik akışını optimize etmek, enerji şebekesini dengelemek, hastane yataklarını dağıtmak — hepsi.

Modern bir hava limanı, bir hafta içinde milyonlarca Simplex çözümü çalıştırır. Modern bir lojistik şirket (FedEx, Amazon), her gün trilyonlarca lineer programlama problemi çözer.

Karmarkar'ın iç nokta yöntemi

1984'te Hint matematikçi Narendra Karmarkar, Simplex'e alternatif yeni bir yöntem geliştirdi: iç nokta algoritması. Karmarkar'ın algoritması, teorik olarak polinom zaman garantili (Simplex'in en kötü durum üstel olmasının aksine).

Pratikte: bazı çok büyük problemler için iç nokta yöntemleri daha hızlı; bazıları için Simplex hâlâ tercih edilir. Modern yazılımlar her ikisinin de hibritini kullanır.

Dantzig'in diğer katkıları

Dantzig sadece Simplex ile sınırlı değildir:

• Stochastik programlama: Belirsizlik altında lineer optimizasyon.
• Dantzig-Wolfe ayrıştırması: Büyük lineer programları daha küçük alt problemlere bölme.
• Talmud önemi: Sosyal sorunlara lineer programlama uygulamaları.

Hayatı boyunca 6 doktora tezi yönetti; öğrencileri arasında günümüzün önemli operasyon araştırmacıları var.

Stanford yılları

Dantzig, 1966'da Stanford Üniversitesi'ne profesör olarak geçti. Sonraki 40 yılını burada geçirdi. Stanford'un Operations Research programının kurucu babası oldu.

Yıllar boyunca pek çok ödül aldı:

• John von Neumann Theory Prize (1975)
• Bilim Madalyası (US National Medal of Science, 1975)
• Harvey Prize (1985)

Ama paradoksal biçimde, Nobel Ekonomi Ödülü kazanamadı. 1975'te lineer programlamanın iki çağdaşı olan Leonid Kantorovich ve Tjalling Koopmans, "kaynak optimum tahsisi" ile Nobel ödülü aldı; Dantzig'in adı listede yoktu. Ekonomistler bunu modern bilim tarihinin önemli bir adaletsizliği olarak değerlendirir.

91 yaşında ölüm

George Dantzig, 13 Mayıs 2005'te Stanford'da, 91 yaşında öldü. Hayatının sonuna kadar matematik araştırmaya devam etti.

Bir hayat dersi

Dantzig'in hikâyesi, bilim tarihinin iki güzel dersini verir:

1. "Berkeley'nin geç gelen öğrencisi" hikâyesi: zorluk hakkında önyargısız olmak, çoğu zaman pratik avantajdır. "Bu çok zor" düşüncesi, bizi denemekten alıkoyabilir.

2. Simplex algoritmasının başarı hikâyesi: pratik etkinlik, teorik mükemmeliyetten daha önemli olabilir. Simplex teorik olarak "en kötü durumda üsteldir"; ama pratikte hemen hemen her zaman çok hızlıdır. Bu, modern operasyon araştırmasının ana dersi.

Bir sonraki sefer bir uçağa binerken, ya da bir paket FedEx ile sipariş ederken, ya da bir bankanın hangi yatırımı yapacağını düşündüğünüzde — perde arkasında 1947'de bir genç matematikçinin yazdığı bir algoritmanın çalıştığını hatırlayabilirsiniz. George Dantzig, modern dünyanın sessiz ama her yerde olan optimizasyoncularından biridir.