Good Will Hunting ya da Türkçe adıyla Can Dostum filmini muhtemelen izlemişsinizdir. İzlemediyseniz filmin çarpıcı sahnelerinden birini hatırlatalım.
Matt Damon’ın tarafından canlandırılan Will Hunting, MIT’de temizlikçi olarak çalışan, bir gençtir. Bir gün profesörlerden biri, ofisinin dışındaki tahtaya zorlu bir matematik problemi yazar. Will, herhangi bir üniversite eğitimi almamış olmasına rağmen bu soruyu kolayca çözer.
Profesör sonrasında daha da zor bir matematik problemi yazar. Will soruyu yine çözer. Profesör zaman içinde çözümü kimin yaptığını anlar. Filmin devamı ikisinin ilişkileri üzerine kuruludur.
Bir çok kişinin bilmediği şey filmin bu sahnesinin kısmen gerçeğe dayanmasıdır. Filmin amaçları doğrultusunda bir miktar değişiklik olsa da daha sonra ünlü bir matematikçi olacak olan George Dantzig hikayenin asıl kahramanıdır.
Kısaca George Dantzig
George Dantzig, doğrusal programlama problemlerinin çözümünde kullanılan simpleks algoritmasını geliştirmesi ile tanınan ünlü bir matematikçiydi. George Dantzig, bu alandaki çalışmalarını bir gün derse geç kalması sayesinde başarmıştı…
George Dantzig 1936’da Maryland Üniversitesi’nden mezun oldu. 1937’de Michigan Üniversitesi’nden yüksek lisans derecesi aldı ve 1943’de UC Berkeley’de doktorasını tamamladı. 1966 yılında Stanford Üniversitesi fakültesine katıldı ve orada 1990’lara kadar görev aldı.
Dantzig, 1975 yılında Başkan Gerald Ford tarafından Ulusal Bilim Madalyası ödülüne layık görüldü. Yanlışlıkla gelen başarısı esnasında, Dantzig, UC Berkley’in yüksek lisans programında profesör Jerzy Neyman yönetiminde istatistik eğitimi alıyordu. Kendisi ile yapılan bir röportajda Dantzig hikayesini şu biçimde aktaracaktı.
“Her zamanki gibi sınıfa geç girdim ve tahtadaki iki istatistik sorusunu ev ödevi sanarak defterime geçirdim. O akşam, soruların üzerinde çalışırken bunun profesörün verdiği en zor ödev olduğunu düşündüm.
Her gece, başaramasam da sırasıyla her iki problemin üzerinde saatlerce çalıştım. Birkaç saat sonra her iki problemi birden çözdüm. Ertesi gün cevapları okula götürdüm. Profesör, masanın üzerine bırakmamı söyledi. Masanın üzerinde kağıttan bir tepe oluşmuştu. Benim kağıdımın bunların arasında kaynayacağını düşünüp bir sıraya üzgünce oturdum.
Altı hafta sonra bir Pazar sabahı kapının vurulmasıyla uyandım. Kapıda profesörü görünce dondum kaldım. ’Problemi çözmüşsün’ dedi. ‘Tabii ki’ diye cevap verdim.’ Çözmem gerekmiyor muydu?’ diye sordum.
Profesör, tahtaya yazılmış olan o iki problemin ev ödevi olmadığını, dünyanın önde gelen matematikçilerinin şimdiye kadar çözememiş oldukları iki ünlü problem olduğunu açıkladı. Birisi bana onların, iki ünlü çözülememiş problem olduğunu söyleseydi, sanırım onları çözmeyi denemezdim bile.”
Yüksek lisans derecesinde, Dantzig bir tez konusu bulmakta zorlandığında iddiaya göre profesörün önerisi ile bu iki matematik problemi onun tezi olarak sayılacaktı.
Simpleks Algoritması Nedir?
Simpleks algoritması bir problemin birçok boyutta analiz edilmesi gerektiği zamanlarda bize zaman kazandırır. Bu arada hatırlatalım. Az önce kullandığımız boyut kelimesi fiziksel anlamda bildiğimiz 3 ve hatta 4 boyuttan farklıdır.
Bir matematikçi için boyutlar sadece uzayla ilgili değildir. Bir matematikçi, bir problemin çözümü esnasında, dörtten fazla şeyi birbirinden bağımsız olarak değiştirmesi gereken durumlarla sıkça karşılaşır.
Örneğin, öğle yemeği için bir sandviç yaptığınızı varsayalım. Buzdolabınızda değişen miktarlarda kullanılabileceğiniz on malzemeniz olsun. İşte bu on malzeme geometrik olarak ele alınabilen bir sandviç yapma probleminin boyutlarıdır.
Hayatımızda benzer optimizasyon sorunları her yerde ortaya çıkar. Bu sorunlar binlerce, hatta milyonlarca değişken ve kısıtlamayla kısa zamanda karmaşa halini alabilir. Örneğin, bir meyve ithalatçısının başa çıkması gereken 1000 boyutlu bir sorunu olabilir. ( Daha fazla bilgi için: Matematikte Optimizasyon Nedir? Neden Önemlidir?)
Toplam nakliye masraflarını en aza indirirken, hangi merkezlerden hangi mağazalara kaç adet meyve gönderilmelidir? Bu sorun tahmin edeceğinizden çok daha karmaşıktır.
Bir fon yöneticisi, riski ve beklenen getiriyi dengelemek için bir portföyü en uygun şekilde düzenlemek istediği zamanlarda ya da trenlerin en verimli nasıl listeleneceğine karar vermek için bir demiryolu zaman çizelgesi yapıldığı zamanlarda da karşımıza yüzlerce boyutu olan problemler çıkar.
Simpleks Algoritması Nasıl Uygulanır?
Bu tür problemlerin her birini geometrik bir şekil olarak tasvir edebiliriz. Bu şekle bir politop denir. Politop, kenarları düz olan bir geometrik nesneyi belirtir. Bunu çokgenlerin herhangi bir boyuta genelleştirmesi olarak düşünebilirsiniz.
Dantzig’in temel fikri, ‘hedef fonksiyonun’ optimum değerinin – maksimize etmek veya minimize etmek istediğimiz şey, kâr, seyahat süresi veya her neyse – politopun köşelerinden birinde yatacağı idi.
Sonucunda herhangi bir politopta sonsuz sayıda nokta vardır, ancak yalnızca sınırlı sayıda köşe bulunur. Ancak kötü haber şu ki, köşelerin sayısı bazen çok fazla olur. Örneğin farklı uzmanlıkları ve zaman kısıtlamaları olan on kişiye bir çalışma programı yapmaya çalıştığınızda denemeniz gereken birkaç milyar köşe olacaktır.
Simpleks algoritması, her birini sırayla test etmek yerine daha hızlı bir yol bulur. Her köşede bir “pivot kuralı” uygular. Bu genellikle, hedef fonksiyonun en dik indiği kenarı seçmeyi içerir ve her adımın bizi en uygun değere yaklaştırmasını sağlar. Daha fazla inişin mümkün olmadığı bir köşe bulunduğunda, en uygun noktaya geldiğimizi anlarız.
Bu sayede 50 boyutlu sorunu çözmek için gereken milyarlarca adım maksimum birkaç yüz adımda sonuca ulaşırız. Yazının başına geri dönelim. Ya Dantzig en başında tahtadaki problemlerin çözülemez sorular olduğunu bilseydi?
Kaynaklar ve İleri Okumalar:
- The Unsolvable Math Problem; : http://www.snopes.com
- Remembering George Dantzig: The real Will Hunting; Yayınlanma tarihi:29 Mart 2019; Bağlantı: https://bigthink.com
Matematiksel
