Bir optimizasyon modeli eğer sürekli değişkenlere ve tek bir doğrusal amaç fonksiyonuna sahipse ve tüm kısıtlamaları doğrusal eşitlik veya eşitsizliklerden oluşuyorsa, doğrusal (lineer) program olarak adlandırılmaktadır. Doğrusal (lineer) programlama, birçok uygun alternatif arasından belirlenmiş bir hedefe uyan optimal çözümü bulacak aktivitelerin planlanmasını içermektedir.
Doğrusal Programlama (DP) Modelinin Tanımlanması
DP’nın üç temel elemanı vardır:
- Amaç (Optimum yapılacak)
- Karar değişkenleri (Belirlenecek-sürekli ya da kesikli)
- İçinde bulunulan kısıtlar.
Konveks Küme: n boyutlu öklidyen uzayın bir C alt uzayı göz önüne alınsın. Eğer bu C kümesinin her nokta çiftinin herhangi bir konveks kombinasyonu da gene bu C kümesinde ise bu C kümesine konveks küme denir.
Lineer programlama probleminin uygun çözümleri konveks küme oluştururlar.
DP’nin Varsayımları:
DP’nin varsayımları bazı kaynaklarda üç bazılarında dört bazılarında ise beş ana başlık altında toplanmıştır.
- Doğrusallık (Sabit Orantılılık) Varsayımı: İşletmenin girdileri ile çıktıları arasında doğrusal bir ilişkinin olduğunu gösterecektir. Varsayım aynı zamanda etkinlik ölçüsü olarak kullanılan amaç fonksiyon katsayılarının da faaliyet düzeyi ile orantılı olarak arttığını işaret edecektir.
- Pozitiflik (Negatif Olmama) Varsayımı: DP modelinde yer alan tüm değişkenler sıfır ya da sıfırdan büyük değer almalıdır.
- Bölünebilirlik Varsayımı: Bu varsayım her bir değişkenin kesirli değerler almasına izin vermektedir. Ancak DP’nin bir diğer versiyonunda bu varsayım ortadan kalkacak ve değişkenlerin sadece tam sayılı değerler almasına izin verilecektir.
- Toplanabilirlik Varsayımı: DP modelini oluşturan amaç ve kısıt fonksiyonları ilişkin oldukları faaliyetlerin bireysel katkılarından oluşacaktır.
- Kesinlik İlkesi: Modeli oluşturan tüm parametreler modelin hesaplandığı dönem boyunca sabit kaldı ve değişmediği varsayımıdır. Modelin parametrelerinde meydana gelebilecek değişiklikler ise ileri bölümlerde incelenecek olan duyarlılık analizi ile açıklanacaktır.
Çözüm yöntemleri. Pratik olarak üç karar değişkene kadar olan LP problemleri grafik yöntemle çözülebilmektedir.
Genelde kullanılan üç farklı analitik çözüm yöntemi mevcuttur:
- Simplex Yöntem
- Elipsoid Yöntemi
- Karmarkar İç Nokta Algoritması
