Doğrusal Programlama

Doğrusal programlama — matematiksel programlamanın bir dalı ve yaygın olarak kullanılan bir yöneylem araştırması yöntemidir; doğrusal kısıtlar altında bir doğrusal fonksiyonun ekstremumunu (maksimum veya minimum) bulmaya yönelik teorinin ve çözüm yöntemlerinin geliştirilmesiyle ilgilenir.

Doğrusal programlama, ekonomi, yönetim, planlama, lojistik ve diğer alanlardaki optimizasyon problemlerinin çözümünde en güçlü ve sık kullanılan araçlardan biridir.

Konu ve Amaç

Doğrusal programlamanın temel problemi — hem amacın hem de kaynakların kullanımına ilişkin kısıtların doğrusal bağıntılarla ifade edilebildiği durumlarda, belirli bir hedefe ulaşmak için kısıtlı kaynakların en iyi (optimal) şekilde dağıtılmasını bulmaktır.

• Doğrusal programlama aşağıdaki gibi pratik problemlerin çözülmesine olanak tanır:
• Üretimin optimal planlanması.
• Taşıma akışlarının optimizasyonu (ulaştırma problemi).
• Yatırımların optimal dağıtımı.
• Malzemelerin optimal biçimde kesilmesi. Atama problemi.

Doğrusal Programlama Probleminin Matematiksel Formülasyonu

Standart doğrusal programlama problemi şu şekilde ifade edilir:

Bir doğrusal amaç fonksiyonunu maksimize eden veya minimize eden karar değişkenlerinin değerlerinin bulunması gerekmektedir. Bu sırada karar değişkenlerine, doğrusal eşitlik ve/veya doğrusal eşitsizliklerden oluşan bir sistem biçiminde kısıtlar uygulanır. Kural olarak, karar değişkenlerinin negatif olmama koşulu eklenir (değerleri sıfırdan büyük veya sıfıra eşit olmalıdır); bu durum çoğunlukla problemin fiziksel veya ekonomik anlamından kaynaklanır.

Matematiksel açıdan bu, doğrusal fonksiyonlar ve doğrusal denklem/eşitsizlik sistemleriyle çalışmak anlamına gelir.

Doğrusal Programlamanın Temel Kavramları

• Karar değişkenleri (Kontrol değişkenleri): Problemin çözüm sürecinde değerlerinin belirlenmesi gereken büyüklükler (örneğin, çeşitli ürünlerin üretim hacimleri, farklı amaçlara yönlendirilen kaynak miktarları).
• Amaç fonksiyonu: Değerinin maksimize edilmesi veya minimize edilmesi gereken, karar değişkenlerinin doğrusal bir fonksiyonu. Problemin hedefini sayısal olarak ifade eder (örneğin, toplam kâr, toplam maliyetler).
• Kısıtlar: Karar değişkenlerinin sağlaması gereken doğrusal eşitlik ve/veya eşitsizlikler sistemi. Kısıtlar, kaynak limitlerini, teknolojik gereksinimleri, planlama hedeflerini ve problemin diğer koşullarını yansıtır.
• Uygun çözümler bölgesi (UÇB): Problemin tüm kısıtlarını sağlayan karar değişkenleri değer kümelerinin tamamı. Geometrik olarak çok boyutlu uzayda UÇB, sınırsız veya boş olması mümkün olan bir dışbükey çokyüzlü (poliedre) oluşturur.
• Uygun çözüm: Değişkenlerin UÇB'ye ait herhangi bir değer kümesi.
• Optimal çözüm: Amaç fonksiyonunun ekstremal (maksimum veya minimum) değerine ulaştığı uygun çözüm. Optimal çözüm mevcutsa, her zaman UÇB'nin sınırında, en az UÇB'nin dışbükey çokyüzlüsünün bir köşesinde bulunur (doğrusal programlamanın temel teoremi).

Doğrusal Programlama Problemlerinin Çözüm Yöntemleri

Doğrusal programlama problemlerini çözmek için birkaç temel yöntem mevcuttur:

• Grafik yöntemi: İki karar değişkenli problemlere uygulanır. UÇB'yi ve amaç fonksiyonunu düzlem üzerinde görsel olarak çizmeye ve UÇB'nin köşelerini analiz ederek ya da amaç fonksiyonunun eşdeğer doğrusunu kaydırarak optimal çözümü bulmaya olanak tanır.
• Simpleks yöntemi: George Dantzig tarafından geliştirilen evrensel iteratif bir algoritmadır. Yöntem, optimal çözüm bulunana kadar her adımda amaç fonksiyonunun değerini iyileştirerek UÇB'nin bir köşesinden komşu köşeye sıralı biçimde geçer. Doğrusal programlama problemlerinin çözümünde klasik ve en iyi bilinen yöntemdir.
• İç nokta yöntemleri: Simpleks yönteminden sonra ortaya çıkan alternatif bir algoritma sınıfıdır. Bu yöntemler, optimal çözüme sınır boyunca değil, UÇB'nin içinden hareket ederek ulaşır. Söz konusu yöntemler, çok büyük boyutlu doğrusal programlama problemlerinin çözümünde özellikle etkilidir.

Doğrusal Programlamada İkililik

Her doğrusal programlama problemine (primal problem olarak adlandırılır) ikil problem adı verilen başka bir doğrusal programlama problemi eşleştirilebilir. Primal ve ikil problemler birbirleriyle yakından ilişkilidir:

Bir problemin çözümü, diğer problemin çözümüne ilişkin bilgi verir. Her iki problemdeki amaç fonksiyonlarının optimal değerleri (mevcutsa) birbirine eşittir. İkil problemin değişkenleri önemli bir ekonomik yoruma sahiptir — bunlar kaynakların gölge fiyatlarına (veya ikil değerlendirmelerine) karşılık gelir ve primal problemdeki amaç fonksiyonunun optimal değerinin, ilgili kaynağa ait kısıtın küçük bir değişimi durumunda ne kadar değişeceğini gösterir.

Doğrusal Programlamanın Uygulama Alanları

Doğrusal programlama şu alanlarda geniş uygulama bulmaktadır:

• Ekonomi ve iş dünyası (üretim planlaması, lojistik, finans, pazarlama).
• Sanayi (teknolojik süreçlerin optimizasyonu, stok yönetimi, malzeme kesimi).
• Ulaştırma (güzergâhların ve tarifelerin optimizasyonu). Tarım (ekim alanlarının, hayvan yem rasyonlarının optimizasyonu).
• Enerji (üretim kapasitelerinin yük optimizasyonu).

Ayrıca bakınız

• Yöneylem araştırması
• Optimizasyon
• Amaç fonksiyonu
• Kısıtlar
• Uygun çözümler bölgesi
• Optimal çözüm

Kaynakça

• Dantzig, G. Линейное программирование, его применения и обобщения. — М.: Прогресс, 1966.
• Yudin D. B., Goldstein E. G. Линейное программирование (теория, методы и приложения). — М.: Наука, 1969.
• Taha, Hamdy A. Operations Research: An Introduction. — Pearson. (10th ed., 2017)
• Hillier, Frederick S.; Lieberman, Gerald J. Introduction to Operations Research. — McGraw-Hill Education. (11th ed., 2021)