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.

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.

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.

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.

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.

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.

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; 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

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

Ö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 problemleri kısıt fonksiyonlarının eşitlik ve eşitsizlik biçiminde olduğu problemlerdir.

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.

Yerine Koyma ve Lagrange Çarpanları

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.

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

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

• 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.

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; 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ıtsız doğrusal olmayan programlama problemi olarak adlandırılır.

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.