Optimizasyon Problemi Nasıl Kurulur ve Çözülür?

Karar değişkeni, amaç fonksiyonu ve kısıt nasıl ayrılır?

Bir optimizasyon modelinin ilk adımı karar değişkenlerini tanımlamaktır. Karar değişkeni, değerini problem çözücünün belirlediği büyüklüktür. Bir fabrikanın iki ürününden kaç birim üretileceği için $x_1$ ve $x_2$ kullanılabilir. Bu değişkenlerin negatif olması fiziksel olarak anlamsızsa $x_1 \ge 0$ ve $x_2 \ge 0$ koşulları ayrıca yazılır.

Amaç fonksiyonu, hangi ölçütün iyileştirileceğini belirtir. Maliyet azaltılıyorsa minimizasyon, kâr artırılıyorsa maksimizasyon yazılır. Örneğin birim maliyetler sırasıyla 4 ve 7 ise toplam maliyet $4x_1+7x_2$ biçiminde ifade edilebilir. Ancak yalnızca birim maliyetin düşük olması, ilk ürünün sınırsız üretilmesi gerektiği anlamına gelmez; kapasite, talep veya başka kaynak kısıtları sonucu belirler.

Kısıtlar, kabul edilebilir kararları sınırlar. Bir makinenin toplam çalışma süresi 100 saat ve ürünlerin birim süreleri 2 ile 5 saat ise $2x_1+5x_2 \le 100$ yazılır. Bir siparişin karşılanması gerekiyorsa $x_1+x_2 \ge 20$ gibi bir talep kısıtı kullanılabilir. Eşitlik kısıtları ise bir koşulun tam olarak sağlanmasını ifade eder: örneğin iki değişkenin toplamı sabitse $x_1+x_2=30$.

Bu ayrımın karar kuralı şudur: Bir ifade, seçilecek değeri temsil ediyorsa değişkendir; neyin iyileştirileceğini gösteriyorsa amaç fonksiyonudur; izin verilen alanı daraltıyorsa kısıttır. Bir kısıtı amaç fonksiyonuyla karıştırmak, bütün çözüm yöntemini yanlış kurar.

Uygun bölge ve köşe noktası neden çözümün anahtarıdır?

Kısıtları aynı anda sağlayan tüm noktaların kümesine uygun bölge denir. Bir noktanın yalnızca tek bir kısıtı sağlaması yeterli değildir; bütün eşitsizlikleri, eşitlikleri ve değişken işaret koşullarını karşılaması gerekir. Uygun bölge boşsa problem için uygulanabilir çözüm yoktur. Uygun bölge sınırsızsa amaç fonksiyonunun sonlu bir optimumu bulunmayabilir.

İki değişkenli doğrusal programlamada her kısıt önce sınır doğrusu olarak çizilir. Eşitsizliğin hangi tarafının seçileceği bir test noktasıyla belirlenir. Daha sonra tüm yarı düzlemlerin ortak kısmı uygun bölgeyi verir. Doğrusal amaç fonksiyonu uygun bölge üzerinde değerlendirildiğinde, sonlu bir optimum varsa bu optimumun köşe noktalarından birinde veya bir köşe kenarı boyunca ortaya çıkması beklenir. Sınavda bu özellik, grafik yöntemin temel gerekçesidir.

Fakat her problemde yalnızca köşeleri kontrol etmek doğru değildir. Bu kural, amaç ve kısıtların doğrusal olduğu uygun bölge için kullanılır. Doğrusal olmayan amaç veya kısıtlar varsa iç noktalar, sınırdaki kritik noktalar ve ayrı ayrı sınır durumları incelenebilir. Ayrıca doğrusal problemde amaç doğrusu bir kenara paralelse aynı optimum değeri veren birden fazla çözüm bulunabilir.

Bir aday noktanın amaç değerini hesaplamak da yeterli son kontrol değildir. Önce noktanın bütün kısıtları sağlayıp sağlamadığı, sonra uygun adaylarla karşılaştırıldığında en iyi amaç değerini verip vermediği kontrol edilir. Bu iki aşama, 'matematiksel olarak elde edilen nokta' ile 'gerçekten uygulanabilir optimum' arasındaki farkı gösterir.

Türev, gradyan ve Hessian hangi durumda kullanılır?

Kısıtsız tek değişkenli bir problemde iç bölgede yer alan yerel optimum adayları için gerekli koşul $f'(x^*)=0$ biçimindedir. Bu koşul yalnızca aday üretir; türevin sıfır olması tek başına minimum veya maksimum kanıtı değildir. Örneğin kritik nokta bir yerel maksimum, yerel minimum ya da daha yüksek boyutta eyer noktası olabilir. Uç noktalar varsa ayrıca incelenmelidir.

İkinci türev, tek değişkenli durumda sınıflandırma için kullanılır: $f''(x^*)>0$ ise nokta yerel minimum, $f''(x^*)<0$ ise yerel maksimum adayıdır. $f''(x^*)=0$ olduğunda bu test karar vermeye yetmez; fonksiyonun daha yüksek dereceli davranışı veya komşu değerleri incelenmelidir.

Çok değişkenli problemlerde birinci türevlerin oluşturduğu vektör gradyandır: $\nabla f(x^*)=0$. Hessian matrisi, ikinci kısmi türevlerden oluşur. Hessian pozitif tanımlıysa kritik nokta yerel minimum, negatif tanımlıysa yerel maksimum olarak sınıflandırılır. Belirsiz durumda yalnızca gradyanın sıfır olmasına dayanarak sonuç ilan edilemez.

Kısıt bulunduğunda doğrudan $\nabla f=0$ yazmak genellikle yeterli değildir; optimum sınır üzerinde olabilir. Eşitlik kısıtları için Lagrange fonksiyonu $L(x,\mu)=f(x)+\sum_j\mu_jh_j(x)$ kurulur ve uygun düzenlilik koşulları altında $\nabla_xL=0$ ile $h_j(x)=0$ birlikte çözülür. Eşitsizliklerde KKT koşulları devreye girer. KKT, her durumda otomatik olarak yeterli değildir: konvekslik gibi ek koşullar altında uygunluk ve optimalite yorumu güçlenir.

Doğrusal ve doğrusal olmayan problemde yöntem seçimi

Amaç fonksiyonu ve bütün kısıtlar karar değişkenlerinde birinci dereceden ifadelerse problem doğrusal programlama problemidir. İki değişkenli küçük örnekler grafikle çözülebilir; daha genel problemlerde simpleks veya iç nokta yöntemleri kullanılabilir. Yöntem seçimi, yalnızca değişken sayısına değil, modelin doğrusal olup olmamasına ve uygun bölgenin yapısına bağlıdır.

Amaç veya kısıtlardan en az biri doğrusal değilse problem doğrusal olmayan programlama sınıfına girer. Türev tabanlı yöntemler, fonksiyonun yeterince düzgün olduğu durumlarda kullanılabilir. Gradyan inişte güncelleme genel olarak $x_{k+1}=x_k-\alpha_k\nabla f(x_k)$ biçimindedir. Burada $\alpha_k$ adım boyudur; çok büyük seçilirse yöntem kararsızlaşabilir, çok küçük seçilirse ilerleme yavaşlayabilir. Başlangıç noktası da özellikle konveks olmayan problemlerde hangi yerel çözüme ulaşılacağını etkileyebilir.

Konveks bir problemde amaç fonksiyonu konveks ve uygun bölge konveks olduğunda, bulunan yerel minimum global minimumdur. Bu önemli bir güvencedir; konveks olmayan problemde aynı güvence genellikle yoktur. Newton ve eşlenik gradyan gibi yöntemler, türev bilgisine ve problem yapısına göre farklı hız ve bellek gereksinimleri taşır.

Çok amaçlı problemlerde tek bir 'en iyi' ölçüt bulunmayabilir. Maliyet azalırken kalite düşebilir; hız artarken enerji tüketimi yükselebilir. Bu durumda amaçlar ağırlıklandırılabilir veya Pareto-optimal çözümler aranabilir. Pareto-optimal bir çözümde, en az bir amacı daha iyi yaparken diğer amaçların hiçbirini kötüleştirmeyen başka bir uygun çözüm bulunmaz. Amaçların yönü (maksimizasyon veya minimizasyon) bu karşılaştırmada dikkate alınmalıdır. Bu, tek bir çözüm garantisi değil, karar verene alternatif dengeler sunan bir yaklaşımdır.

Çözümlü örnek: doğrusal programlamada köşe noktalarını karşılaştırma

Verilenler: $x$ ve $y$ negatif olmayan iki ürün miktarı olsun. Amaç, $Z=3x+2y$ kârını maksimize etmektir. Kaynak kısıtları $x+y\le 4$ ve $2x+y\le 5$ olsun. İstenen, uygun bölgedeki en yüksek kârı bulmaktır.

1. Değişken ve amaç: $x\ge0$, $y\ge0$ ürün miktarlarını; $Z=3x+2y$ toplam kârı gösterir.

2. Sınırları bulma: $x+y=4$ doğrusunun eksen kesişimleri $(4,0)$ ve $(0,4)$; $2x+y=5$ doğrusunun kesişimleri $(2{,}5,0)$ ve $(0,5)$ noktalarıdır. Birinci bölgede ve iki doğrunun altında kalan ortak alan uygun bölgedir.

3. Kesişim noktası: $x+y=4$ ve $2x+y=5$ birlikte çözülür. İkinci denklemden birinci denklem çıkarıldığında $x=1$ bulunur. Böylece $y=3$ olur; doğruların kesişimi $(1,3)$'tür.

4. Köşe adaylarını denetleme: Eksenlerle birlikte uygun köşeler $(0,0)$, $(2{,}5,0)$, $(1,3)$ ve $(0,4)$ olur. Bunların amaç değerleri sırasıyla $0$, $7{,}5$, $9$ ve $8$'dir.

5. Sonuç: En yüksek değer $Z=9$ olduğundan optimum çözüm $(x,y)=(1,3)$'tür. Bu nokta iki kaynak kısıtını da eşitlikle sağlar: $1+3=4$ ve $2(1)+3=5$. Sonuç, yalnızca en yüksek kâr hesabıyla değil, noktanın bütün kısıtları sağlamasıyla geçerlidir.

Çözümlü örnek: kısıtsız tek değişkenli minimum

Verilenler: $f(x)=x^2-6x+11$ fonksiyonunun gerçek sayılar üzerindeki minimumu isteniyor.

1. Kritik nokta: Türev $f'(x)=2x-6$ olur. Gerekli koşuldan $2x-6=0$ yazılır ve $x=3$ bulunur.

2. Noktanın türü: İkinci türev $f''(x)=2$ olduğundan $f''(3)>0$'dır. Bu nedenle $x=3$ yerel minimumdur.

3. Değer hesaplama: $f(3)=3^2-6\cdot3+11=9-18+11=2$.

4. Global yorum: Fonksiyonun ikinci derecesi pozitif olduğundan parabol yukarı açılır; bu özel problemde yerel minimum aynı zamanda global minimumdur. Sonuç olarak minimum nokta $x=3$, minimum değer $2$'dir.

Buradaki kritik ayrım şudur: Türev koşulu yalnızca aday noktayı verdi. Minimum sonucunu ikinci türev ve fonksiyonun yapısı destekledi. Eğer problemde $x$ için bir aralık kısıtı olsaydı, $x=3$ aralıkta değilse uç noktalar da hesaplanacak ve sonuç yeniden karşılaştırılacaktı.

Sık yapılan hatalar ve karıştırılan kavramlar

1. Modelleme ile optimizasyonu eş anlamlı kullanmak: Modelleme, gerçek problemi değişkenler ve denklemlerle ifade etme aşamasıdır; optimizasyon, bu modelde en iyi uygun çözümü arar. Model yanlışsa gelişmiş algoritma doğru gerçek dünya kararını garanti etmez.

2. Kritik noktayı doğrudan minimum sanmak: $f'(x)=0$ yalnızca gerekli koşuldur. İkinci türev testi, uç nokta incelemesi veya doğrudan karşılaştırma yapılmalıdır.

3. Kısıtların işaretini ters yazmak: 'En fazla 100' ifadesi $\le 100$, 'en az 20' ifadesi $\ge 20$ anlamına gelir. Birimlerin de tutarlı olması gerekir; saat ile dakika veya kilogram ile gram karıştırılırsa modelin sayısal sonucu anlamını kaybeder.

4. Uygun olmayan köşeyi değerlendirmek: İki sınır doğrusunun kesişmesi, tek başına uygun nokta demek değildir. Kesişim bütün kısıtlarda yerine konularak test edilmelidir.

5. Yerel ve global optimumu karıştırmak: Yerel minimum yalnızca yakın çevresindeki uygun noktalardan daha iyidir. Global minimum bütün uygun bölgede en küçük amaç değerini verir. Konvekslik, yerel çözümün globale eşitlenebildiği önemli koşullardan biridir; bu sonuç konveks olmayan problemlere taşınamaz.

6. Maksimizasyon ve minimizasyonu yanlış yorumlamak: Bir maliyet fonksiyonu için büyük değer değil küçük değer aranır. Kâr, fayda veya üretim miktarı gibi hedeflerde ise problem ifadesine göre maksimum aranabilir.

7. Sayısal algoritmanın durmasını optimum kanıtı sanmak: Bir iteratif yöntem belirli tolerans içinde durmuş olabilir; bu, özellikle konveks olmayan problemde global optimum bulunduğunu tek başına göstermez. Amaç değeri, kısıt ihlalleri, başlangıç noktası ve yakınsama ölçütü birlikte raporlanmalıdır.

8. Pareto-optimal çözümü tek kazanan sanmak: Çok amaçlı optimizasyonda Pareto kümesi, amaçlar arasındaki ödünleşimleri gösterir. Karar vericinin tercihleri belirtilmeden bu çözümlerden birini evrensel olarak en iyi ilan etmek doğru değildir.