DOĞRUSAL OLMAYAN PROGRAMLAMA: YÖNTEMLER VE ALIŞTIRMALAR - MATEMATIK - 2025

Doğrusal olmayan programlama sırayla kısıtlamalara tabidir birçok bağımsız değişkene bağlıdır bir işlevi optimize süreçtir.

Bir veya daha fazla kısıtlama veya maksimize edilecek veya minimize edilecek fonksiyon (amaç fonksiyonu olarak adlandırılır) değişkenlerin doğrusal bir kombinasyonu olarak ifade edilmezse, doğrusal olmayan bir programlama probleminiz var demektir.

Şekil 1. Doğrusal olmayan programlama problemi (NLP). burada G, kısıtlamalar tarafından belirlenen yeşil bölgede optimize edilecek (doğrusal olmayan) işlevdir. Kaynak: F. Zapata.

Ve bu nedenle doğrusal programlama prosedürleri ve yöntemleri kullanılamaz.

Örneğin, iyi bilinen Simplex yöntemi kullanılamaz, bu yalnızca amaç işlevi ve kısıtlamaların tümü problemdeki değişkenlerin doğrusal kombinasyonları olduğunda geçerlidir.

Doğrusal programlama yöntemleri

Doğrusal olmayan programlama problemleri için kullanılacak ana yöntemler şunlardır:

1.- Grafik yöntemler.

2.- Çözüm bölgesinin sınırlarını keşfetmek için Lagrange çarpanları.

3.- Amaç işlevinin uç noktalarını keşfetmek için gradyanın hesaplanması.

4.- Boş gradyan noktalarını bulmak için azalan adımlar yöntemi.

5.- Lagrange çarpanlarının değiştirilmiş yöntemi (Karush-Kuhn-Tucker koşuluyla).

Grafik yöntemle çözüm örneği

Grafik yöntemle bir çözüm örneği, şekil 2'de görülebilen çözümdür:

Şekil 2. Doğrusal olmayan kısıtlamalara sahip doğrusal olmayan bir problem örneği ve grafiksel çözümü. Kaynak: F. Zapata.

Egzersizler

- Egzersiz 1 (Grafik yöntemi)

Belirli bir şirketin karı G, X ürününün satılan miktarına ve Y ürününün satılan miktarına bağlıdır, ayrıca kar aşağıdaki formülle belirlenir:

G = 2 (X - 2) ² + 3 (Y - 3) ²

X ve Y miktarlarının aşağıdaki kısıtlamalara sahip olduğu bilinmektedir:

X≥0; Y≥0 ve X + Y ≤ 7

Maksimum kazancı sağlayan X ve Y değerlerini belirleyin.

Şekil 3. Bir şirketin karı, doğrusal olmayan programlama kullanılarak maksimum karı bulmak için matematiksel olarak modellenebilir. Kaynak: Pixabay.

Çözüm

Bu problemde amaç işlevi doğrusal değildir, oysa kısıtları tanımlayan eşitsizlikler öyledir. Bu doğrusal olmayan bir programlama problemidir.

Bu problemin çözümü için grafiksel yöntem seçilecektir.

Öncelikle kısıtlamalarla verilen çözüm bölgesi belirlenecektir.

X≥0 olarak; Y≥0, çözüm XY düzleminin ilk çeyreğinde bulunmalıdır, ancak X + Y ≤ 7 olduğu da doğru olması gerektiğinden, çözüm X + Y = 7 doğrusunun alt yarı düzlemindedir.

Çözüm bölgesi, birinci çeyreğin çizginin alt yarı düzlemi ile kesişimidir ve çözümün bulunduğu üçgen bir bölge ile sonuçlanır. Şekil 1'de gösterilen ile aynıdır.

Öte yandan, G kazancı aynı zamanda kartezyen düzlemde de gösterilebilir, çünkü denklemi merkezi (2,3) olan bir elips denklemidir.

Elips, G'nin çeşitli değerleri için Şekil 1'de gösterilmiştir. G'nin değeri ne kadar yüksekse, kazanç o kadar büyük olur.

Bölgeye ait ancak maksimum G değerini vermeyen çözümler var, G = 92.4 gibi diğerleri ise yeşil bölgenin yani çözüm bölgesinin dışında kalıyor.

Daha sonra, X ve Y'nin çözüm bölgesine ait olması için G'nin maksimum değeri şuna karşılık gelir:

X = 7 ve Y = 0 için verilen G = 77 (maksimum kazanç).

İlginç bir şekilde, maksimum kâr, Y ürününün satış miktarı sıfır olduğunda, X ürününün miktarı mümkün olan en yüksek değere ulaştığında ortaya çıkar.

- Egzersiz 2 (Analitik yöntem: Lagrange çarpanları)

G (x, y) = x ² + y ² - 1 = 0 bölgesinde f (x, y) = x ² + 2y ^{2 fonksiyonunu} maksimum yapan çözümü (x, y) bulun .

Çözüm

Hem f (x, y) amaç fonksiyonu hem de g (x, y) = 0 kısıtlaması x ve y değişkenlerinin doğrusal bir kombinasyonu olmadığından, açıkça doğrusal olmayan bir programlama problemidir.

İlk olarak Lagrange fonksiyonu L (x, y, λ) tanımlanmasını gerektiren Lagrange çarpanları yöntemi kullanılacaktır:

L (x, y, λ) = f (x, y) - λ g (x, y) = x ² + 2y ² - λ (x ² + y ² - 1)

Λ, Lagrange çarpanı adı verilen bir parametredir.

G (x, y) = 0 kısıtlaması ile verilen çözüm bölgesinde f amaç fonksiyonunun uç değerlerini belirlemek için şu adımları izleyin:

-Lagrange fonksiyonu L'nin x, y, λ'ya göre kısmi türevlerini bulun.

-Her türevi sıfıra eşitleyin.

İşte bu işlemlerin sırası:

1. ∂L / ∂x = 2x - 2λx = 0
2. ∂L / ∂y = 4y - 2λy = 0
3. ∂L / ∂λ = - (x ² + y ² - 1) = 0

Olası sistem çözümleri

Bu sistemin olası bir çözümü λ = 1'dir, böylece birinci denklem yerine getirilir, bu durumda y = 0, böylece ikincisi karşılanır.

Bu çözüm, üçüncü denklemin karşılanması için x = 1 veya x = -1 olduğunu ima eder. Bu şekilde iki çözüm S1 ve S2 elde edilmiştir:

S1: (x = 1, y = 0)

Ö2: (x = -1, y = 0).

Diğer alternatif, y değerine bakılmaksızın ikinci denklemin karşılanması için λ = 2 olmasıdır.

Bu durumda, ilk denklemin karşılanmasının tek yolu x = 0'dır. Üçüncü denklem göz önüne alındığında, S3 ve S4 olarak adlandıracağımız sadece iki olası çözüm vardır:

Ö3: (x = 0, y = 1)

S4: (x = 0, y = -1)

Bu çözümlerden hangisinin veya hangisinin amaç fonksiyonunu maksimize ettiğini bulmak için, f (x, y) 'de ikame etmeye devam ediyoruz:

Ö1: f (1, 0) = 1 ² + 2.0 ² = 1

Ö2: f (-1, 0) = (-1) ² + 2.0 ² = 1

Ö3: f (0, 1) = 0 ² + 2.1 ² = 2

Ö4: f (0, -1) = 0 ² + 2 (-1) ² = 2

X ve y, g (x, y) = 0 çevresine ait olduğunda f'yi maksimize eden çözümlerin S3 ve S4 olduğu sonucuna varıyoruz.

(X = 0, y = 1) ve (x = 0, y = -1) değer çiftleri, g (x, y) = 0 çözüm bölgesinde f (x, y) 'yi maksimize eder.

- Egzersiz 3 (Boş gradyan)

Amaç işlevi için çözümler (x, y) bulun:

f (x, y) = x ² + 2 y ²

G (x, y) = x ² + y ² - 1 ≤ 0 bölgesinde maksimum olalım .

Çözüm

Bu alıştırma 2. alıştırmaya benzer, ancak çözüm (veya kısıtlama) bölgesi, g (x, y) = 0 çevresinin iç bölgesine, yani g (x, y) ≤ 0 çemberine kadar uzanır. çevreye ve iç bölgesine.

Sınırdaki çözüm zaten 2. tatbikatta belirlendi, ancak iç bölge keşfedilmeyi bekliyor.

Bunu yapmak için, çözüm bölgesindeki uç değerleri bulmak için f (x, y) fonksiyonunun gradyanı hesaplanmalı ve sıfıra eşit ayarlanmalıdır. Bu, f'nin sırasıyla x ve y'ye göre kısmi türevlerini hesaplamaya ve onu sıfıra eşitlemeye eşdeğerdir:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Bu denklem sistemi g (x, y) ≤ 0 çemberine ait tek çözüme (x = 0, y = 0) sahiptir.

Bu değeri f fonksiyonunda değiştirmek:

f (0, 0) = 0

Sonuç olarak, fonksiyonun çözüm bölgesinde aldığı maksimum değer 2'dir ve çözüm bölgesi sınırında, (x = 0, y = 1) ve (x = 0, y = -1) değerleri için .

Referanslar

1. Avriel, M. 2003. Doğrusal Olmayan Programlama. Dover Yayıncılık.
2. Bazaraa. 1979. Doğrusal Olmayan Programlama. John Wiley & Sons.
3. Bertsekas, D. 1999. Doğrusal Olmayan Programlama: 2. baskı. Athena Scientific.
4. Nocedal, J. 1999. Sayısal Optimizasyon. Springer-Verlag.
5. Vikipedi. Doğrusal olmayan programlama. Kurtarıldı: es.wikipedia.com