Karar Modelleri Dersi 6. Ünite Sorularla Öğrenelim

Doğrusal ve Doğrusal Olmayan Programlama Modelleri Arasındaki Farklılıklar nelerdir?

Doğrusal ve doğrusal olmayan programlama modelleri arasındaki temel farklılıklar aşağıdaki gibi özetlenebilir:
• Daha önce de ifade edildiği gibi iki tür model arasındaki en temel fark, doğrusal modelde amaç ve kısıt fonksiyonlarının tamamı doğrusal fonksiyonlar iken, doğrusal olmayan modellerde amaç veya kısıt fonksiyonlarından en az biri doğrusal olmayan bir fonksiyon formundadır.
• Doğrusal bir modelde en iyi çözüm daima uygun çözüm bölgesinin uç noktası olurken, bu durum doğrusal olmayan modeller için geçerli değildir. Bazı doğrusal olmayan modellerin en iyi çözümü, uygun çözüm bölgesinin içinde yer alan bir iç noktadır.
• Doğrusal olmayan programlama modellerinin kurulumu genellikle doğrusal programlama modellerinin kurulumuna göre daha zordur. Çoğunlukla, doğrusal olmayan modellerde amaç veya kısıt fonksiyonlarının matematiksel şekli bilinmez. Bu durumda modelin kurulabilmesi için eldeki veriye en uygun fonksiyon formunun
belirlenmesi gerekebilir.
• Doğrusal programlama modeli için en iyi çözümü bulmada kullanılacak birden çok algoritma bulunmaktadır. Doğrusal olmayan programlama modelleri için amaç ve kısıt fonksiyonlarının matematiksel formuna göre geliştirilmiş algoritmalar bulunmakla birlikte, analitik yöntemlerle çözülemeyen doğrusal olmayan modeller için yaklaşık çözüm teknikleri kullanılmaktadır.

Bir işletme K birim hammadde ve L birim iş gücü kullanarak toplam KL adet ürün üretmektedir. Birim ürün başına hammadde maliyeti 4 TL ve iş gücü maliyeti ise 1 TL’dir. Bu üretim için işletmenin ayırdığı toplam bütçe 8 TL’dir. İşletme üretim miktarını maksimum yapan girdi (hammadde ve iş gücü) miktarlarını bulmak istemektedir. Probleme ilişkin karar modeli nedir?

Probleme ilişkin doğrusal olmayan karar modelini oluşturabilmek için doğrusal programlamada yapıldığı gibi öncelikle karar değişkenleri tanımlanır. Örneğimizde işletme, toplam üretimi maksimum (en büyük) yapan girdi miktarlarını belirlemek istediğine göre, probleme ilişkin karar değişkenleri;
K: hammadde miktarı, L: iş gücü miktarı olarak tanımlanabilir. Bu karar değişkenleriyle probleme ilişkin doğrusal olmayan karar modeli; 4K + L ? 8 K ? 0, L ? 0 kısıtları altında Max Z = KL biçiminde yazılır. Görüldüğü üzere, problemin kısıt fonksiyonu doğrusal olmakla birlikte amaç fonksiyonu doğrusal değildir.

Uygun Çözüm Bölgesi ne demektir?

Doğrusal olmayan programlama problemine ait uygun çözüm bölgesi, problemdeki m tane kısıtı sağlayan (x1
, x2 ,..., xn ) noktalarının kümesidir. Uygun çözüm bölgesindeki bir nokta uygun nokta, uygun çözüm bölgesinde yer almayan bir nokta ise uygun olmayan nokta olarak adlandırılır.

Asal minör ne demektir?

n x n boyutlu bir kare matriste (n – i) satır ile (n – i) sütun silindiğinde elde edilen i x i boyutlu matrisin determinantına matrisin i’inci asal minörü denir.

Başta Gelen Asal Minör ne demektir?

n x n boyutlu bir kare matriste son (n – k) satır ile son (n – k) sütun silindiğinde elde edilen k x k boyutlu matrisin determinantına matrisin k’ıncı başta gelen asal minörü denir. Bir Hessian matrisinin k’ıncı başta gelen asal minörünün (x1 , x2 ,..., xn ) noktasındaki değeri Hk (x1 , x2 ,..., xn ) ile gösterilir.

Matris Belirliliği ne demektir?

Bir A matrisi n x n boyutlu ve simetrik bir matris olsun.
• A matrisinin tüm k. başta gelen asal minörleri sıfırdan büyük (> 0) ise A matrisi pozitif belirlidir.
• A matrisinin tüm k. başta gelen asal minörleri negatif değil (? 0) ise A matrisi pozitif yarı-belirlidir.
• A matrisinin tüm k. başta gelen asal minörü sıfırdan farklı ve (–1)k ile aynı işarete sahip ise (asal minörlerin işareti –, +, –, +, ... şeklinde ise) A matrisi negatif belirlidir.
• A matrisinin her tek sıralı k. başta gelen asal minörü pozitif değil (? 0) ise ve her çift sıralı k. başta gelen asal minörü negatif değil (? 0) ise aynı zamanda sıfırdan farklı her asal minörünün işareti (–1)k ile aynı işarete sahip ise A matrisi negatif yarı belirlidir.
• Yukarıdaki durumların dışında A matrisi belirsizdir.

 Konveks ve konkav fonksiyonları açıklayınız. 

Doğrusal olmayan programlama problemlerinde konveks ve konkav fonksiyonlar önemli bir yere sahiptir. Konveks ve konkav fonksiyonların tanımına geçmeden önce, konveks küme tanımına değinelim. S ? IRn kümesindeki her x', x" ? S ve 0 ? ? ? 1 değeri için, ?x' + (1 – ?) x" ? S oluyor ise S kümesine konveks küme denir. f(X) = (x1 , x2 ,..., xn ), konveks bir S kümesinin tüm X = (x1 , x2 ,..., xn ) noktaları için tanımlı bir fonksiyon olsun. S konveks kümesindeki herhangi iki x' ? S ve x" ? S noktası ve 0 ? ? ? 1 değeri için, f(?x' + (1 – ?)x") ? ?f(x') + (1 – ?)f(x") oluyorsa, f fonksiyonuna S kümesi üzerinde bir konveks fonksiyon denir. Eğer f(?x' + (1 – ?)x") < ?f(x') + (1 – ?)f(x") ise, f fonksiyonuna S kümesi üzerinde kesin konveks fonksiyon denir. Konveks fonksiyon tanımını daha anlaşılır kılmak için grafiği Şekil 6.3’de verilen tek değişkenli bir y = f(x) fonksiyonunu ele alalım. y = f(x) eğrisi üzerinde yer alan herhangi iki noktayı birleştiren doğru parçası daima fonksiyonun büküm noktasının üzerinde kalıyorsa y = f(x) fonksiyonu konvekstir.

Doğrusal olmayan programlama problemleri nasıl incelenir?

Doğrusal olmayan programlama problemleri; problemin kısıtlarının olup olmamasına, amaç fonksiyonu ve kısıtların yapısına, amaç ve kısıt fonksiyonlarının ayrılabilir fonksiyonlar cinsinden ifade edilip edilmediklerine göre farklı sınıflarda incelenir

 Doğrusal olmayan programlama problemleri nasıl sınıflandırılır?

• Kısıtsız Optimizasyon
• Kısıtlı Optimizasyon

Tek değişkenli modellerin en iyi çözümü nasıl bulunur?

Öncelikle tek değişkenli kısıtsız bir modelde, verilen tanım kümesinde amaç fonksiyonunun maksimum ve minimum noktaları araştırılsın.
Max(Min)f(x) x ? [a, b] fonksiyonunun maksimum ve minimum noktalarının araştırılmasında izlenecek yol aşağıdaki adımlardan oluşmaktadır:
1. Tek değişkenli bir fonksiyonda f'(x* ) = 0 olan x = x* noktasına kritik nokta denir. Öncelikle tek değişkenli f fonksiyonunda kritik nokta araştırılır. Eğer x*? [a, b] ise
2. adıma geçilir. Aksi takdirde, verilen aralıkta fonksiyonu maksimum veya minimum yapan nokta bulunmamaktadır. 2. Tek değişkenli bir f fonksiyonunun yerel optimallik için gerekli ve yeterli şartları ikinci türev testi yardımıyla bulunur:

• x* kritik noktasında f"(x* ) > 0 ise, x* bir yerel minimum,
• kritik noktasında f"(x* ) < 0 ise, x* bir yerel maksimum noktasıdır.
• kritik noktasında f"(x* ) = 0 ise, x* ne bir yerel maksimum ne de bir yerel minimum noktasıdır.
3. Fonksiyonun yerel maksimum ve minimum noktalarının birer mutlak maksimum ve minimum olması için gerekli ve yeterli optimallik şartları ise aşağıdaki gibidir:
• x* noktası f fonksiyonunun bir yerel minimum noktası olsun. Eğer f fonksiyonu konveks ise bu durumda x* fonksiyonun bir mutlak minimum noktası,
• x* noktası f fonksiyonunun bir yerel maksimum noktası olsun. Eğer f fonksiyonu konkav ise bu durumda x* fonksiyonun bir mutlak maksimum noktasıdır.

Kısıtlı optimizasyon ne demektir?

Kısıtlı optimizasyon problemleri kısıt fonksiyonlarının eşitlik ve eşitsizlik biçiminde olduğu problemlerdir.

Kısıtlı optimasyonda yerine koyma yönteminin amacını açıklayınız. 

Bu yöntemin amacı, verilen modeli öncelikle kısıtsız biçime dönüştürmek ve sonra indirgenmiş modeli bilinen tekniklerle çözmektir (Doğan, 1995, s.224). Bu yöntem, doğrusal olmayan programlama problemlerinin çözümünde kullanılan en kolay yöntemlerden biri olmakla birlikte kısıt denkleminde bir değişkenin diğer bir değişken cinsinden yazılarak çözülmesini içermektedir. Bir değişkenin diğer bir değişken cinsinden yazılarak kısıt denkleminin yeni elde edilen biçiminin amaç fonksiyonunda yerine yazılmasıyla kısıt elimine edilmektedir. Diğer bir ifadeyle, kısıtlı doğrusal olmayan model, kısıtsız doğrusal olmayan modele dönüştürülmektedir.

Kısıtları eşitlik formunda olan doğrusal olmayan programlama problemlerinin analitik çözüm yöntemleri nelerdir?

Yerine Koyma ve Lagrange Çarpanları

Lagrange çarpanının yorumu nası yapılır?

Lagrange çarpanları yöntemindeki ?, doğrusal programlama problemindeki dual (ikil) değişkenlere benzer. Kısıt denkleminin sağ taraf sabitindeki bir birimlik değişimin amaç fonksiyonu değerinde ne kadarlık bir değişim yarattığını ifade eder. Eğer doğrusal olmayan modelde i’inci kısıtın sağ taraf sabiti olan bi değerinde ? kadarlık bir değişim meydana gelirse bu değişim artış ya da azalış biçiminde olabilir. Bu durumda amaç fonksiyonu değerinde ?i? kadarlık bir değişim meydana gelecektir.

Kısıtsız optimizasyon ve analitik çözüm teknikleri nelerdir?

Tek Değişkenli Modellerin En İyi Çözümünün Bulunması

Çok Değişkenli Modellerin En İyi Çözümünün Bulunması

Konveks ve konkav fonksiyonların sahip olduğu özellikler nelerdir?

• Doğrusal bir fonksiyon hem konveks hem de konkavdır.
• Konveks fonksiyonların toplamı konveks, konkav fonksiyonların toplamı da yine konkav bir fonksiyondur.
• f(x) konveks iken –f(x) konkav, f(x) konkav iken –f(x) konveks bir fonksiyondur.
• Bir fonksiyon tanım kümesinin bir alt kümesinde konveks iken, tanım kümesinin
diğer bir alt kümesinde konkav olabilir.

Gradyan Vektörü nedir?

S ? Rn kümesi üzerinde tanımlı ve gerçel değerli bir f(X) = (x1 , x2
,..., xn ) fonksiyonu ikinci dereceden türevlenebilir bir fonksiyon olmak üzere, f fonksiyonunun birinci dereceden kısmi türevlerinin yer aldığı vektöre Gradyan Vektörü denir.

Doğrusal olmayan programlama problemlerinin çözüm yaklaşımlarında yer alan temel kavramlar nelerdir?

Doğrusal olmayan programlama problemlerinin çözüm yaklaşımlarında yer alan temel kavramlar; uygun çözüm bölgesi, en iyi çözüm, mutlak ve yerel en iyi noktalar, Gradyan Vektörü, Hessian Matrisi, asal minör, matris belirliliği biçiminde sıralanabilir. İzleyen kesimde bu kavramların ayrıntılarına yer verilmiştir.

Kısıtları bulunmayan doğrusal olmayan programlama problemi nasıl adlandırılır?

Kısıtsız doğrusal olmayan programlama problemi olarak adlandırılır.

Hessian Matrisi ne demektir?

S ? Rn kümesi üzerinde tanımlı ve gerçel değerli bir f fonksiyonu ikinci dereceden türevlenebilir bir fonksiyon olmak üzere, f fonksiyonunun ikinci dereceden kısmi türevlerinin oluşturduğu n x n boyutlu kare matrise f fonksiyonunun Hessian Matrisi denir.