Doğrusal Programlama

Doğrusal Programlamanın Tanımı

Doğrusal programlama (DP), sınırlı kaynakların, birbiriyle rekabet eden faaliyetler arasında, belirli bir amacı en iyileyecek (optimize edecek) şekilde dağıtılmasını sağlayan bir yöneylem araştırması tekniğidir. Amaç fonksiyonu ve kısıtların tamamı doğrusal denklemlerle ifade edilir. Yöntem, II. Dünya Savaşı sırasında askerî lojistik sorunlar için geliştirilmiş; George Dantzig 1947'de simpleks yöntemini bulmuştur.

Modelin Bileşenleri

• Karar değişkenleri: Değeri belirlenecek bilinmeyenler (her üründen üretilecek miktar: x₁, x₂).
• Amaç fonksiyonu: En büyüklenecek (maksimizasyon — kâr, gelir) veya en küçüklenecek (minimizasyon — maliyet, süre) doğrusal fonksiyon. Örnek: Max Z = 30x₁ + 20x₂.
• Kısıtlar: Kaynakların (hammadde, işgücü, makine saati, bütçe) sınırlılığını ifade eden doğrusal eşitsizlik veya eşitlikler. Örnek: 2x₁ + x₂ ≤ 100.
• Negatif olmama kısıtı: Karar değişkenleri negatif olamaz (x₁, x₂ ≥ 0).

Varsayımlar

• Doğrusallık (oransallık): Amaç fonksiyonu ve kısıtlardaki katkılar karar değişkenleriyle doğru orantılıdır.
• Toplanabilirlik: Değişkenlerin katkıları birbirinden bağımsızdır ve toplanabilir.
• Bölünebilirlik: Karar değişkenleri kesirli değerler alabilir (alamıyorsa tam sayılı programlama kullanılır).
• Kesinlik (belirlilik): Modeldeki katsayılar kesin olarak bilinir.

Çözüm Yöntemleri

• Grafik yöntem: Yalnız iki karar değişkenli problemlerde kullanılır. Kısıtların sağlandığı ortak bölge uygun (olurlu) çözüm bölgesidir ve dışbükey bir çokgen oluşturur. Optimal çözüm, uygun bölgenin köşe noktalarından birinde yer alır (köşe noktası teoremi). Köşe noktalarında amaç fonksiyonu değerleri hesaplanarak veya eş kâr (eş maliyet) doğrusu kaydırılarak en iyi nokta bulunur.
• Simpleks yöntemi: Çok değişkenli problemlerde kullanılan cebirsel ve iteratif yöntem; uygun bölgenin köşe noktaları arasında amaç fonksiyonunu iyileştirerek ilerler. Eşitsizlikler aylak (boş) değişkenler (≤ kısıtlarında) ve artık değişkenler (≥ kısıtlarında) eklenerek eşitliğe dönüştürülür; gerektiğinde yapay değişkenler (Büyük M yöntemi, iki aşamalı yöntem) kullanılır.

Özel Durumlar

• Uygun çözümün olmaması: Kısıtların ortak bir bölgesi yoktur (çelişen kısıtlar).
• Sınırsız çözüm: Amaç fonksiyonu kısıtlarca sınırlanmaz ve sonsuza gider.
• Alternatif (çoklu) optimal çözüm: Amaç fonksiyonu doğrusu bir kısıta paralelse birden fazla optimal nokta bulunur.
• Bozulma (dejenerasyon): Simpleks iterasyonlarında temel değişkenlerden birinin sıfır değer alması.
• Gereksiz (fazla) kısıt: Uygun bölgeyi etkilemeyen kısıt.

Duyarlılık Analizi ve Dualite

Duyarlılık analizi, modeldeki katsayılar (kâr katkıları, kaynak miktarları) değiştiğinde optimal çözümün nasıl etkileneceğini inceler. Her doğrusal programlama probleminin (primal) bir dual (eş) problemi vardır; dual değişkenler kaynakların gölge fiyatlarını (bir kaynağın bir birim artırılmasının amaç fonksiyonuna marjinal katkısı) verir. Primal ve dual problemlerin optimal amaç fonksiyonu değerleri eşittir.

Uygulama Alanları ve Özel Modeller

Üretim planlaması (ürün karması), karışım (diyet, yem) problemleri, yatırım ve portföy seçimi, personel çizelgeleme. Özel yapılı modeller: ulaştırma problemi (kaynaklardan hedeflere en düşük maliyetli taşıma; kuzeybatı köşe, en küçük maliyet, Vogel yaklaşım yöntemleri) ve atama problemi (işlerin kişilere en etkin atanması; Macar yöntemi).