BİRLİKTE KURALIM Burası sitemizin en dolu yeri olacak. Bir anlamda, elektronik ortamda matematik kütüphanesi kurma çabamızı bu sayfalardan izleyip katkıda bulunabilir, konuların anlatımını üstlenebilirsiniz. Türkçe dilinin matematik aksiklopedisi olma hedefini güdecek bu sayfaların ortak çabanın ve ortak iradenin bir ürünü olabilmesi için biz elimizden gelen gayreti göstereceğiz. Sizlerin katkıları işimizi kolaylaştıracaktır.   MATEMATİK PROGRAMLAMA Yrd. Doç. Dr. Eyüp ÇETİN İstanbul Üniversitesi İşletme Fakültesi Sayısal Yöntemler Anabilim Dalı İnsanoğlu yüzyıllardır bilinçli ya da bilinçsiz olarak yaptığı işlerin tümünde her zaman en iyi yi yapmayı planlamış ve istemiştir. Bu çabalar, bazen bir işçinin belirli bir kuvvetle maksimum yükü kaldırabilmesi, bazen de uçaklardaki sürtünmenin minimum a indirgenmesi olarak karşımıza çıkagelmiştir. Yadsınamaz bir gerçektir ki, her zaman bir eniyileme çabası var olmuştur. Ünlü matematikçi Leonhard Euler'in ifadesiyle "Doğada maksimum ya da minimum duyusunun bulunmadığı hiç bir olay yoktur" [1]. Bir matematik sözlüğü [2] optimizasyon (eniyileme) kavramını, "bir probleme en iyi mümkün çözüm bulma süreci olarak" tanımlamaktadır. Matematikte, bu süreç genellikle bir fonksiyonun değerinin verilen kısıtlar altında maksimize ya da minimize edilmesinden oluşur [2]. Tarihsel Gelişim Bir işin en iyi yolun seçilerek başarılması fikri uygarlık tarihi kadar eskidir. Örneğin, Yunan tarihçisi Herodotus'a göre, Mısırlılar Nil nehrinin her yıl taşması sonucu arazi sınırlarının yeniden belirlenmesi ve yeni sınırlara göre vergilendirme işleminin en iyi yolla yapılabilmesi için çaba sarfetmişlerdir. Bu çabalar, ölçme ve karar verme aracı olarak düzlem geometrisinin temel kavramlarının oluşturulmasına yol açmıştır [3]. Mısırlılar, Nil nehrinin bahar dönemlerindeki yıllık taşmalarında nehir kıyısından toplu halde uzaklaşıp sular çekildiğinde yine büyük topluluklar halinde geri dönüyorlardı. Çekilme işlemi çok kısa sürede yapılamamaktaydı. Bunun için günlerce önceden halk uyarılmalıydı. Bu amaçla, Mısırlılar en iyi çekilme zamanını hesaplayabilmek için bir tür takvim bile geliştirmişlerdi. Söz konusu takvimi de sayma ve geometri konusundaki birikimlerini kullanarak yapmışlardı [1,4]. Newton ve Leibniz tarafından Kalkülüs'ün (Calculus) 17. yüzyılda geliştirilmesi optimizasyon teorisinin gelişiminde önemli bir kilometre taşı olmuştur. Kalkülüs, hem matematiksel bir fonksiyonun hem de fonksiyon oluşturabilen bağımsız değişkenlerin maksimum veya minimum cinsinden optimal koşullarının elde edilmesine olanak sağlamaktadır. Kalkülüs'ün kullanımı düzgün-davranışlı fonksiyonlarla sınırlandırılmıştır. Ancak, Kalkülüs uygulamalarında karşılaşılan cebirsel problemlerin çözümü bazen güç olabilmektedir. Dolayısıyla, Kalkülüs pragmatik anlamda gerçek dünya problemlerinin optimizasyonunda yeterli ve güçlü bir araç olamamaktadır [3]. J.L. Lagrange'ın 1788 yılında Lagrange çarpanları yöntemini bilim dünyasının hizmetine sunması önemli bir adım olmuştur. 1939'da W. Karush'un kısıtlandırılmış problemler için optimallik koşullarını bulması optimizasyon teorisinde yeni bir atılım olmuştur. II. Dünya Savaşı'nın başlamasıyla 1942'de İngiltere ve Amerika Birleşik Devletleri'nin Yöneylem Araştırması gruplarını oluşturması optimizasyon dünyası için bir dönüm noktası olmuştur. Sezgisel optimizasyon araçlarından olan yapay sinir ağları 1943'de W. McCulloch ve W. Pitts tarafından çalışıldı. Ertesi yıl ise, J. Von Neumann ve O. Morgenstern tarafından "Oyun Teorisi ve Ekonomik Davranış" adlı eserle oyun kuramı tanıtıldı [5]. II. Dünya Savaşı'ndan sonra yeni sınıf optimizasyon teknikleri geliştirildi. Sözkonusu teknikler daha karmaşık problemlere başarıyla uygulandı. Bunda, yüksek hızlı dijital bilgisayarların geliştirilmesi ve optimum değerlerin elde edilmesi için nümerik tekniklere matematiksel analizin uygulanması son derece etkili olmuştur. Nümerik teknikler Kalkülüs'ün bir takım zorluklarını ortadan kaldırmıştır [3]. Lineer programların çözümü için Simplex yöntem 1947'de G.B. Dantzig tarafından geliştirildi. Bu, optimizasyon dünyasında gerçekten bir devrim sayılmaktadır. R. Bellman 1950'de dinamik programlama modelini ve çözümünü geliştirdi. 1951'de H. Kuhn ve A. Tucker daha önce Karush'un önerdiği kısıtlandırılmış problemler için optimallik koşullarını tekrar formüle ederek doğrusal olmayan programlama modelleri üzerinde çalıştılar. Yine aynı yıl, J. Von Neumann, G. Dantzig ve A. Tucker primal-dual lineer programlama modellerini geliştirdiler. Yine önemli bir katkı 1955'de stokastik programlama adı altında G. B. Dantzig tarafından yapıldı. Kuadratik programlama 1956'da M. Frank ve P. Wolfe tarafından geliştirildi. 1958'deki önemli bir katkı R. Gomory tarafından tamsayılı programlama olarak adlandırıldı. A. Charnes ve W. Cooper şans kısıtlı programlama modellerini 1959'da optimizasyon dünyasına armağan ettiler. 1960'da sezgisel optimizasyon araçlarından birisi olan yapay zeka ve yöneylem araştırması ilişkilerini içeren çalışmalar yapıldı. Hedef programlama modeli yine A. Charnes ve W. Cooper tarafından 1965 yılında geliştirildi. 1975'de çok amaçlı karar verme teorisinin temelleri M. Zeleny, S. Zionts, J. Wallenius, W. Edwards ve B. Roy tarafından atıldı. L. Khachian lineer programlama modellerinin çözümü için farklı bir algoritma olan elips yöntemini 1979'da geliştirildi. 1984'te, N. Karmarkar lineer programlama için alternatif bir çözüm algoritması olan içnokta algoritmasını geliştirdi. 1992'de J.H. Holland tarafından bir sezgisel optimizasyon tekniği olarak kabul edilen genetik algoritma geliştirildi. Çağdaş optimizasyon dünyasında da her geçen gün artan bir ivmeyle önemli katkılar yapılmakta ve bilimin hizmetine sunulmaktadır [1,5]. Optimizasyon modelleri yukarıda da belirtildiği gibi matematiksel teknikler kullanmaktadır. Daha özel anlamda, optimizasyon modelleme geleneksel olarak matematik programlama olarak adlandırılmaktadır [6]. Diğer bir ifadeyle, matematik programlama, optimizasyon modelinin kurulması ve çözümün elde edilmesi işlemine verilen genel isimdir. Geçmişten gelen bir gelenekle günümüzde de "matematik programlama" ve "optimizasyon" kavramları eşanlamlı olarak kullanılmaktadır [1]. Matematik programlama kavramı, "matematik planlama ve düzenleme" anlamında kullanılmaktadır. "Programlama" sözcüğü İngiliz İngilizcesindeki "programme" kavramının karşılığı olarak kullanılmaktadır. Bilgisayar programcılığı anlamına gelmemektedir. Kaldı ki, "matematik programlama" ifadesi "bilgisayar programcılığı" kavramının ortaya çıkışından önce de kullanılmaktaydı. Matematiksel Tanım Matematik programlama problemi, belirli kısıtlar altında bir amaç fonksiyonunun optimize edilmesinden oluşmaktadır. Diğer bir deyişle, karar değişkenleri olarak nitelendirilen fonksiyon değişkenlerinin kısıtların tümünü sağlayan (uygun çözüm bölgesinde bulunan) ve amaç fonksiyonunu optimize eden sayısal değerlerini bulma problemidir. Tipik bir matematik program aşağıdaki gibi ifade edilebilir; n değişken sayısı ve m kısıt sayısı olmak üzere, Optimum: z = f (x 1, x2,...,xn)         Kısıtlar: g1 (x 1, x2,...,xn)   b1   g2 (x 1, x2,...,xn) b2   ......................... =     gm(x 1, x2,...,xn) bm Bu ifadede, m sayıda farklı kısıt , = , sembollerinden birisini içerebilir. Her gi fonksiyonu ve bi katsayıları sıfır seçilirse kısıtsız matematik programlar elde edilir. Burada, f amaç fonksiyonu ve gi kısıt fonksiyonları lineer (doğrusal) ise matematik program lineer programlama, diğer durumlarda ise lineer olmayan programlama adını alır [7]. Matematik programlama modellerinde, f fonksiyonu optimize edilecek yani maksimize ya da minimize edilecek amaç fonksiyonu dur. Kâr, getiri, fayda ve benzeri gibi kavramlar amaç fonksiyonunda yer alırsa maksimize, maliyet, gider ve benzeri gibi kavramlar yer aldığında da minimize edilir. gi fonksiyonlarının herbiri birer kısıt belirtmektedir. Kısıt sayısında herhangi bir sınır bulunmamaktadır. Kısıtların hepsi birlikte bir uygun çözüm bölgesi belirlerler. Optimal çözüm değeri veya değerleri bu bölgeye ait bir değer olmaktadır. Kısıtlar sınırlayıcı şartların ifadeleridir. İşletme ve ekonomi problemlerinde sınırlayıcı şartların varlığını görebilmek oldukça kolaydır. Örneğin, üretilmesi planlanan ürünler için hammadde, işçilik, makine zamanı, stoklama alanı gibi sınırlamalar kısıtlar olarak ifade edilirler. Sözkonusu kısıtlar genelde doğrusaldırlar. Bazı özel problemlerde amaç fonksiyonu olmayabilmektedir. Optimizasyonun sözkonusu olmadığı böylesi modellerde sadece uygun bir çözümün varlığı yeterli olmaktadır [1]. Uygulama Alanları Matematik programlama teknikleri çok geniş bir yelpazede kullanım alanlarına sahiptirler. Mühendislikten işletme ve ekonomiye, askeri modellerden tarıma, tıp ve ilaç sektöründen spora kadar birbirlerinden çok farklı alanlarda geniş ölçüde kullanılmaktadır. Daha spesifik olarak, örneğin, uydu yörüngelerinin düzenlenmesi, robot kolunun hareketinin optimizasyonu, finansal planlama, taşımacılık problemleri, spor liglerinin optimizasyonu, mamul karışım problemleri, askeri hedeflerin vurulmasında optimal silah karışımının belirlenmesi ve radyoterapide ışınların optimal açı ve yoğunluklarının belirlenmesi bunlardan sadece bir kaçıdır. Matematik Programlama Modellerinin Sınıflandırılması Matematik programlama modelleri çeşitli kriterlere göre sınıflandırılabilmektedir. Matematik programlar fonksiyonlarının tipine göre, yukarıda değinildiği gibi, birinci dereceden fonksiyonlardan oluşuyorlarsa lineer programlama, diğer durumlarda ise lineer olmayan programlama şeklinde sınıflandırılırlar. Karar değişkenlerinin tipine göre, sadece tam sayılı değişkenlerden oluşan problemlere tam sayılı programlama adı verilir. Hem sürekli hem de tam sayılı değişken içeren modeller ise karma tam sayılı programlama adını alırlar. En az bir tane rassal parametre içeren programlar ise stokastik programlar olarak nitelendirilirler. Aksi halde ise model deterministik olarak isimlendirilir. Optimizasyon probleminin çözümü zamanın bir fonksiyonu ise, problem dinamik programlama olarak adlandırılmaktadır. Dinamik programlama da kendi içerisinde deterministik ve stokastik olarak sınıflandırılabilmektedir. Birden fazla amaç fonksiyonuyla başa çıkmak için geliştirilen ve çok kriterli karar verme aracı olan hedef programlama, birbirleriyle çelişebilen amaçları hep birlikte göz önüne almakta ve amaçlardan sapmaları minimize ederek çözüme ulaşmaktadır. Konveks ve kesirli programlama türleri de yine yaygın olarak kullanılabilen optimizasyon modellerindendir. Burada sadece bazılarından söz edilen matematik programlama türlerinin çözümleri için farklı matematiksel yöntemler geliştirilmiştir. Örneğin, lineer programlar için geliştirilen Simplex yöntem tüm lineer modelleri çözme potansiyeline sahipken lineer olmayan programlama modellerinin hepsini çözebilen genel bir çözüm yolu geliştirilememiştir. Lineer olmayan modeller için önerilen algoritmalar bazı özellikleri taşıyan tiplere uygulanabilmektedir. Söz gelimi, eşitlik kısıtlı lineer olmayan modellere Lagrange çarpanları kullanılırken eşitsizlik kısıtlı problemlere de Kuhn-Tucker koşulları uygulanmaktadır. Açıklayıcı Bir Örnek Burada, basit olması açısından ve matematik programlamanın en temel modellerinden sayılması nedeniyle küçük bir lineer programlama problemi verilmiş ve grafik yöntemle çözülmüştür. Lineer programlamada grafik yöntem, en fazla üç karar değişkenli modellere çözüm getirebilmektedir. Oysa ki Simplex yöntemin böyle bir kısıtlaması bulunmamaktadır. Örnek problem aşağıdaki gibi verilmektedir [8]. maks z=3x1 + 4x2 Kısıtlar: 3x1 + 4x2 1 60 (1.kısıt) 2x1 + 6x2 60 (2.kısıt) x 1, x2 0 ( pozitiflik kısıtları) Problem maksimizasyon formundadır. Söz gelimi, bu bir kâr maksimizasyonu olabilir. Birinci tip ürünün birim kârı 3 YTL ve ikinci tip ürünün birim kârı 4 YTL ise ilgili ürünlerden söz konusu kısıtlar altında kaçar tane üretilmelidir ki toplam kâr maksimum olsun? Çözüm için öncelikle, analitik düzlemin eksenleri karar değişkenleri olan x1 ve x2 olarak adlandırılır. Lineer programlarda, çok özel durumlar dışında, karar değişkenlerinin pozitif olması istenir. Bu durumda analitik düzlemin birinci bölgesinde çalışılacaktır. Kısıtların oluşturduğu uygun çözüm bölgesi analitik düzlemde belirtilir. Uygun çözüm bölgesi Şekil 1'de taralı alan ile belirtilmiştir. Amaç doğrusunun eğimi m = - 3/4 olarak elde edilir. Bu eğim amaç doğrusunun uygun çözüm bölgesi üzerinde kaydırılması için gereklidir. Alternatif olarak, amaç fonksiyonu herhangi bir keyfi değere eşitlenerek de (eş kâr doğruları) çizilebilir. Şekilden de görüleceği gibi, amaç denklemi uygun çözüm bölgesi üzerinde kaydırılırsa, en son x1= 18 ve x2= 4 noktasından bölgeyi terketmektedir. Aynı sonuca aşağıdaki yolla da ulaşılabilir: Uygun çözüm bölgesinin köşe noktaları amaç denkleminde yerine konulursa, (0,10) noktası için, z = 3x1+ 4x2 = 3.0 + 4.10 = 40 (20,0) noktası için, z = 3x1+ 4x2 = 3.20 +4.0 = 60 (18,4) noktası için, z = 3x1+ 4x2 = 3.18 +4.4 = 70 (Maksimum kâr! Optimal nokta!) elde edilir. (18,4) noktası maksimum kârı verdiğinden aranılan çözüm noktasıdır. (18,4) noktası, iki kısıt doğrusunun kesim noktası olduğundan her iki kısıtı da sağlamak durumundadır. Bu nokta da iki kısıt denklemlerinin ortak çözümünden elde edilir. İlgili teoreme göre, lineer programların optimal çözümleri konveks uygun çözüm bölgesinin köşe noktalarındadır. Özetle, iki farklı ürün tiplerinden x1= 18 ve x2= 4 birim üretilmeli ki maksimum kâr z = 70 YTL elde edilebilsin. Optimal çözüm Şekil 1'deki grafikte görülmektedir. Şekil 1. Örnek Lineer Programlama Modeli İçin Grafik Çözümü Değişken sayısı arttıkça matematik programlama modellerinin elle çözümü çok zorlaşmakta ve hatta imkansız hale gelmektedir. Bu nedenle, matematik programlama problemlerinin çözümleri için teorik çözüm algoritmalarına dayalı bilgisayar yazılımları geliştirilmiştir. LINDO, LINGO, ABQM ve CPLEX programları bunlardan bazılarıdır. Ayrıca, esnek modelleme yapısı sunan elektronik tablolarla da (örneğin MS Excel) matematik programlama problemleri çözülebilmektedir. Karar bilimlerinin ve yöneylem araştırması disiplinin ayrılmaz bir parçası olan matematik programlama, tüm akademik dünyada lisans, yüksek lisans ve doktora seviyelerinde matematik, istatistik, işletme, ekonomi ve mühendislik bilimlerinde ders olarak okutulmaktadır. Hatta matematik programlama, son yıllarda başlatılan kampanyalarla yöneylem araştırmasının bir bileşeni olarak lise öğrencileriyle de tanıştırılmaya başlanmıştır. Kaynaklar [1] Eyüp Çetin, Stokastik Programlama Yöntemiyle Bir Portföy Optimizasyonu Modelinin Geliştirilmesi, Yayımlanmamış Doktora Tezi, İstanbul, İ.Ü. Sosyal Bilimler Enstitüsü, Sayısal Yöntemler Bilim Dalı, 2004. [2] Christopher Clapham, Coincise Dictionary of Mathematics, 2 nd Edition, New York, Oxford University Press, 1996. [3] Byron S. Gottfried, Joel Weisman, Introduction to Optimization Theory, New Jersey, Prentice Hall Inc.,1973. [4] Roger Cooke, The History of Mathematics: A Brief Course, Canada, John Wiley & Sons Inc., 1997. [5] Saul I. Gass, "Great Moments in History", OR/MS Today, V, 29, October 2002, s. 31. [6] Samuel E. Bodily v.d., Quantitative Business Analysis: Text and Cases, USA, Irwin/ McGraw-Hill, 1998. [7] Richard Bronson, Theory and Problems of Operations Research, Schaum's Outline Series, USA, McGraw-Hill, 1982. [8] John E. Ullmann, Schaum's Outline of Theory and Problems of Quantitative Methods in Management, New York, McGraw-Hill, 1976.
	Bugün 2 ziyaretçi (4 klik) kişi burdaydı!