Doğrusal olmayan programlama - Nonlinear programming

In matematik , doğrusal olmayan programlama ( NLP ) bir çözme sürecidir optimizasyon problemi kısıtlamaları veya amaç fonksiyonu bazılarıdır doğrusal olmayan . Bir optimizasyon problemi bir ekstremumlar (maxima, minima ya da sabit noktalar) hesaplanması biridir amaç fonksiyonu bir bilinmeyen kümesinin üzerine reel değişkenlerin bir tatmin edecek şekilde ve koşullu sistemin içinde eşitlikler ve eşitsizlikler , toplu olarak adlandırılan kısıtlamalar . Doğrusal olmayan problemlerle ilgilenen matematiksel optimizasyonun alt alanıdır .

uygulanabilirlik

Tipik bir dışbükey olmayan problem, çeşitli bağlantı ve kapasite kısıtlamaları ile bir veya daha fazlası ölçek ekonomisi sergileyen bir dizi ulaşım yönteminden seçim yaparak ulaşım maliyetlerini optimize etmektir . Bir örnek, boru hattı, demiryolu tankeri, karayolu tankeri, nehir mavnası veya kıyı tank gemisi seçimi veya kombinasyonu verilen petrol ürünü taşımacılığı olabilir. Ekonomik parti boyutu nedeniyle, maliyet fonksiyonlarında yumuşak değişikliklere ek olarak süreksizlikler olabilir.

Deneysel bilimde, bazı basit veri analizleri (bilinen konum ve şekle sahip ancak bilinmeyen büyüklükteki tepe noktalarının toplamına sahip bir spektrum uydurmak gibi) doğrusal yöntemlerle yapılabilir, ancak genel olarak bu problemler de doğrusal değildir. Tipik olarak, çalışılan sistemin içinde değişken parametreler bulunan teorik bir modeli ve bilinmeyen parametrelere sahip olabilecek deney veya deneylerin bir modeli vardır. Sayısal olarak en uygun olanı bulmaya çalışır. Bu durumda, kişi genellikle sonucun kesinliğinin bir ölçüsünün yanı sıra kendisine en uygun olanı ister.

Tanım

Let n , m ve p pozitif tamsayı olmak. Let X, bir alt kümesi R n izin f , g i ve h J edilebilir fonksiyonları gerçek değerli ile X her biri için i içinde { 1 , ..., m }, her j içinde { 1 , ..., p }, de sahip en az bir f , g i ve h j olmak doğrusal olmayan.

Doğrusal olmayan bir minimizasyon problemi, formun bir optimizasyon problemidir .

Doğrusal olmayan bir maksimizasyon problemi benzer şekilde tanımlanır.

Olası kısıtlama seti türleri

Uygun küme veya uygun bölge olarak da bilinen kısıt kümesinin doğası için birkaç olasılık vardır .

Bir olanaksız sorun seçim değişkenleri tatmin için değerlerin belirlenmiş tüm kısıtlamaları için biridir. Yani, kısıtlamalar karşılıklı olarak çelişkilidir ve hiçbir çözüm yoktur; uygun küme boş kümedir .

Bir uygulanabilir sorun tüm kısıtları sağlayan seçim değişkenler için değerler en az bir takımı vardır kendisi için biridir.

Bir sınırsız sorun amaç fonksiyonu, herhangi bir sonlu değer daha iyi olacak şekilde yapılmıştır edilebildiği için uygun bir sorundur. Bu nedenle optimal bir çözüm yoktur, çünkü her zaman verilen herhangi bir önerilen çözümden daha iyi bir amaç fonksiyonu değeri veren uygun bir çözüm vardır.

Sorunu çözme yöntemleri

Amaç fonksiyonu içbükey (maksimizasyon problemi) veya dışbükey (minimizasyon problemi) ve kısıt seti dışbükey ise , program dışbükey olarak adlandırılır ve çoğu durumda dışbükey optimizasyondan genel yöntemler kullanılabilir.

Amaç fonksiyonu ikinci dereceden ve kısıtlar doğrusal ise, ikinci dereceden programlama teknikleri kullanılır.

Amaç fonksiyonu bir içbükey ve bir dışbükey fonksiyonun oranıysa (maksimizasyon durumunda) ve kısıtlar dışbükey ise, o zaman problem kesirli programlama teknikleri kullanılarak dışbükey bir optimizasyon problemine dönüştürülebilir .

Konveks olmayan problemleri çözmek için çeşitli yöntemler mevcuttur. Bir yaklaşım, doğrusal programlama problemlerinin özel formülasyonlarını kullanmaktır. Diğer bir yöntem, programın dışbükey (minimizasyon problemi) veya alt bölüm içindeki toplam maliyet üzerinde bir alt sınır oluşturan doğrusal yaklaşımlarla çözülecek alt sınıflara ayrıldığı dal ve sınır tekniklerinin kullanımını içerir . Sonraki bölmelerle, bir noktada, maliyeti yaklaşık çözümlerden herhangi biri için elde edilen en iyi alt sınıra eşit olan gerçek bir çözüm elde edilecektir. Bu çözüm, muhtemelen benzersiz olmasa da optimaldir. Algoritma ayrıca, mümkün olan en iyi çözümün bulunan en iyi noktadan bir tolerans dahilinde olduğu güvencesiyle erken durdurulabilir; bu noktalara ε-optimal denir. ε-optimal noktalara sonlandırma, genellikle sonlu sonlandırmayı sağlamak için gereklidir. Bu özellikle, belirsizliğin uygun bir güvenilirlik tahmini ile tahmin edilebildiği büyük, zor problemler ve belirsiz maliyetler veya değerler içeren problemler için kullanışlıdır.

Altında türevlenebilirlik ve kısıtlama nitelikleri , Karush-KuhnTucker (KKT) koşullarında bir çözelti optimal olduğu için gerekli koşulları sağlar. Dışbükeylik altında bu koşullar da yeterlidir. İşlevlerin olmayan bazı türevlenebilir ise, Subdiferansiyel sürümleri Karush-Kuhn-Tucker (KKT) koşullar mevcuttur.

Örnekler

2 boyutlu örnek

Mavi bölge uygulanabilir bölgedir . Teğetlik uygulanabilir bölgesi ile hattın bir çözümü temsil etmektedir. Çizgi, elde edilebilecek en iyi kontur çizgisidir (belirli bir amaç fonksiyonu değerine sahip yer).

Basit bir problem (şemada gösterilmiştir) kısıtlamalarla tanımlanabilir

x 1 ≥ 0
x 2 ≥ 0
x 1 2 + x 2 2 ≥ 1
x 1 2 + x 2 2 ≤ 2

maksimize edilecek bir amaç fonksiyonu ile

f ( x ) = x 1 + x 2

burada x = ( x 1 , x 2 ).

3 boyutlu örnek

Merkezdeki kısıtlı boşluk ile üst yüzeyin teğetliği çözümü temsil eder.

Başka bir basit problem (şemaya bakınız) kısıtlamalarla tanımlanabilir

x 1 2 − x 2 2 + x 3 2 ≤ 2
x 1 2 + x 2 2 + x 3 2 ≤ 10

maksimize edilecek bir amaç fonksiyonu ile

f ( x ) = x 1 x 2 + x 2 x 3

burada x = ( x 1 , x 2 , x 3 ).

Ayrıca bakınız

Referanslar

daha fazla okuma

Dış bağlantılar