Good Will Hunting ya da Türkçe adıyla Can Dostum filmi yaşanmış bir olaydan esinlenmiştir. Üstelik bu gerçek hikâye, filmde anlatılan masalsı versiyondan çok daha ilgi çekicidir. Hikâyenin merkezinde, ileride “doğrusal programlamanın babası” olarak anılacak olan George Dantzig yer alır.
İzlemediyseniz filmin en çarpıcı sahnelerinden birini kısaca hatırlatalım. Good Will Hunting’de, Matt Damon’ın canlandırdığı Will Hunting, MIT’de temizlikçi olarak çalışan genç bir adamdır. Bir gün profesörlerden biri, ofisinin dışındaki tahtaya son derece zor bir matematik problemi yazar. Will, herhangi bir üniversite eğitimi almamış olmasına rağmen bu problemi fark edilmeden çözer.
Bunun ardından profesör daha da zor bir soru yazar. Will onu da yine sessizce çözer. Zamanla profesör, çözümlerin arkasındaki kişinin Will olduğunu fark eder ve filmin geri kalanı bu ikili arasındaki ilişki etrafında gelişir. Film, bazı değişiklikler yapsa da, anlatının çıkış noktası gerçek bir olaya dayanır.
George Dantzig, University of California, Berkeley’de yüksek lisans öğrencisiyken bir gün derse geç kaldı. Tahtada yazılı iki problemi hızla defterine geçirdi ve birkaç gün sonra çözümlerini teslim etti. Ancak bu sorular ödev değildi. İstatistik alanında çözülmemiş iki ünlü problemdi. Bu çözümler ona doktora derecesini kazandırdı.
Doğrusal Programlama Nedir?
Doktorasını aldıktan sonra United States Air Force için çalışmaya başladı. Eğitim programları, ikmal dağıtımı ve birliklerin konuşlandırılması gibi planlar hazırladı. Bu faaliyetlere o dönemde “programlama” deniyordu.
Dantzig bu alanda o kadar etkili oldu ki, İkinci Dünya Savaşı’ndan sonra Pentagon’da iyi bir ücretle çalışmaya başladı. Burada askeri planlama sürecini mekanikleştirme görevi üstlendi ve doğrusal programlama adını verdiği son derece başarılı bir yöntem geliştirdi.
Doğrusal programlama, üretim miktarı ya da toplam kâr gibi bir hedefi, eldeki sınırlamalar altında en yüksek düzeye çıkarmayı amaçlar. Bu hedefi amaç fonksiyonu ile ifade ederiz ve onu değişkenler cinsinden doğrusal olarak yazarız.
Sanayide karar verirken hammadde, iş gücü ve kapasite gibi kısıtları dikkate alırız. George Dantzig bu ilişkilerin doğrusal olduğunu varsaydı. Bin ürün için dört ton hammadde gerekiyorsa, iki bin ürün için sekiz ton gerekir. Üretim arttıkça kaynak kullanımı aynı oranda artar. Bu basit orantı, modelin temelini oluşturur.
Gerçek dünyadaki problemler çok sayıda değişken ve kısıt içerir. Bu nedenle en iyi çözümü rastlantıya bırakamayız. Dantzig, bu tür modelleri sistemli biçimde çözmek için simpleks yöntemini geliştirdi. Simpleks, olası çözümler arasında düzenli adımlarla ilerler ve sonunda en iyi sonuca ulaşır.
George Dantzig’in klasik eseri Linear Programming and Extensions şu cümleyle başlar: “Bir kuramın nihai sınavı, onu doğuran problemleri çözme kapasitesidir.” Altı yüz sayfalık bir kitabı böyle bir iddiayla açmak cesur bir tutumdur. Ancak aradan geçen altmış yıl, doğrusal programlama kuramının ve ona eşlik eden simpleks algoritmasının bu sınavı beklentilerin ötesinde geçtiğini defalarca göstermiştir.
Simpleks Algoritması Nedir?
Simpleks algoritması 2000 yılında “Yüzyılın En İyi On Algoritması” arasında gösterildi. Günümüzde de matematiksel optimizasyon alanının temel çalışma aracı olmayı sürdürmektedir.
Algoritmanın adı ilk bakışta İngilizcedeki “simple” sözcüğüyle ilişkiliymiş izlenimi uyandırır. Ancak “simpleks” kelimesi “simple”dan türemiş değildir. Terim, doğrudan geometriye aittir. Geometride simplex, n boyutlu uzayda n+1 köşeye sahip en temel çokyüzlüdür. İki boyutta bu şekil üçgendir. Üç boyutta ise tetrahedron adını alır.
Bir mobilya şirketinin gardırop, yatak ve sandalye ürettiğini düşünelim. Her gardırop bir sandalyeden üç kat, her yatak ise iki kat daha kârlı olsun. Üretim miktarlarını sırasıyla a, b ve c ile gösterirsek toplam kârı 3a + 2b + c ifadesiyle yazarız.
Şirket kârını en yüksek düzeye çıkarmak ister. Ancak bazı kısıtlarla karşılaşır. Ayda en fazla 50 ürün üretebilir. Bu durumda a + b + c ≤ 50 olur. Gardıropların üretimi daha zordur; en fazla 20 adet üretilebilir. Yani a ≤ 20. Sandalyeler özel bir ağaçtan yapılır ve bu malzeme nadirdir. Bu nedenle c ≤ 24 koşulu geçerlidir.
Simpleks yöntemi bu durumu, çok daha fazla değişken içerse bile, geometrik bir probleme dönüştürür. Bu durumda, a, b ve c için yazdığımız kısıtları üç boyutlu bir uzayda düşünürüz. Örneğin a ≤ 20 eşitsizliği, a eksenine dik bir düzlem olur.
Çözüm bu düzlemin üzerinde ya da altında kalmak zorundadır. Diğer kısıtlar da benzer biçimde sınırlar oluşturur. Bu sınırlar birlikte, uzayı çokyüzlü adı verilen karmaşık bir şekle böler. En iyi çözüm bu çokyüzlünün köşelerinden birinde yer alır.
Simpleks algoritmasının baştan sona çalışmasını geometrik olarak düşünürsek, süreç bir köşeden başlayıp en üstteki köşeye ulaşacak bir yol bulmaya benzer. Amaç, en az adımı içeren yolu izlemektir. Bu yol aynı zamanda en az kenardan geçer. Atılan adım sayısı, yani algoritmanın çalışma süresi ya da karmaşıklığı, doğrudan bu uzunlukla ilişkilidir.
Sonuç Olarak
Simpleks algoritması, optimizasyon problemlerinde en iyi çözüme ulaşmak için sistematik bir yol sunduğu için matematik, ekonomi ve işletme gibi birçok alanda önemli bir araç haline gelmiştir. Sonucunda bu da akla bir soru getirir. Ya George Dantzig derse geç kalmasaydı?
Kaynaklar ve İleri Okumalar:
- Researchers Discover the Optimal Way To Optimize. Yayınlanma tarihi: 11 Ekim 2025. Kaynak site: Quanta magazine. Bağlantı: Researchers Discover the Optimal Way To Optimize
- Remembering George Dantzig: The real Will Hunting; Yayınlanma tarihi:29 Mart 2019; Bağlantı: https://bigthink.com
Matematiksel
