PEMROGRAMAN NONLINIER: METODE DAN LATIHAN - MATEMATIKA - 2025

The pemrograman nonlinier adalah proses mengoptimalkan fungsi yang tergantung pada beberapa variabel independen, yang pada gilirannya tunduk pada pembatasan.

Jika satu atau lebih batasan, atau jika fungsi dimaksimalkan atau diminimalkan (disebut fungsi tujuan), tidak dinyatakan sebagai kombinasi linear dari variabel, maka Anda memiliki masalah pemrograman nonlinier.

Gambar 1. Masalah pemrograman nonlinier (NLP). di mana G adalah fungsi (non-linier) untuk mengoptimalkan di wilayah hijau, ditentukan oleh batasan. Sumber: F. Zapata.

Dan oleh karena itu prosedur dan metode pemrograman linier tidak dapat digunakan.

Misalnya, metode Simplex yang terkenal tidak dapat digunakan, yang hanya berlaku jika fungsi tujuan dan batasan adalah kombinasi linier dari variabel dalam soal.

Metode pemrograman linier

Untuk masalah pemrograman non-linier metode utama yang akan digunakan adalah:

1.- Metode grafis.

2.- Pengganda Lagrange untuk menjelajahi batas wilayah solusi.

3.- Perhitungan gradien untuk mengeksplorasi ekstrem dari fungsi tujuan.

4.- Metode langkah menurun, untuk menemukan titik gradien nol.

5.- Metode pengali Lagrange yang dimodifikasi (dengan kondisi Karush-Kuhn-Tucker).

Contoh solusi dengan metode grafis

Contoh solusi dengan metode grafis adalah yang dapat dilihat pada gambar 2:

Gambar 2. Contoh masalah non-linier dengan batasan non-linier dan solusi grafisnya. Sumber: F. Zapata.

Latihan

- Latihan 1 (Metode grafik)

Keuntungan G suatu perusahaan tergantung dari jumlah penjualan produk X dan jumlah penjualan produk Y, selain itu keuntungan ditentukan dengan rumus sebagai berikut:

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

Jumlah X dan Y diketahui memiliki batasan berikut:

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

Tentukan nilai X dan Y yang menghasilkan gain maksimal.

Gambar 3. Laba suatu perusahaan dapat dimodelkan secara matematis untuk mencari laba maksimum dengan menggunakan program nonlinier. Sumber: Pixabay.

Larutan

Dalam soal ini fungsi tujuan adalah non-linier, sedangkan pertidaksamaan yang menentukan batasan adalah. Ini adalah masalah pemrograman nonlinier.

Untuk solusi dari masalah ini, metode grafis akan dipilih.

Pertama, wilayah solusi akan ditentukan, yang diberikan oleh batasan.

Sebagai X≥0; Y≥0, penyelesaian harus ditemukan di kuadran pertama bidang XY, tetapi karena harus benar juga bahwa X + Y ≤ 7, penyelesaiannya berada di setengah bidang bawah dari garis X + Y = 7.

Daerah penyelesaian adalah perpotongan dari kuadran pertama dengan setengah bidang garis bawah, yang menghasilkan daerah segitiga tempat penyelesaian ditemukan. Ini sama seperti yang ditunjukkan pada gambar 1.

Di sisi lain, penguatan G juga dapat direpresentasikan dalam bidang Cartesian, karena persamaannya adalah elips dengan pusat (2,3).

Elips ditunjukkan pada Gambar 1 untuk berbagai nilai G. Semakin tinggi nilai G, semakin besar keuntungannya.

Ada solusi yang masuk ke wilayah tersebut, tetapi tidak memberikan nilai G maksimum, sedangkan solusi lainnya seperti G = 92,4 berada di luar zona hijau, yaitu zona solusi.

Kemudian, nilai maksimum G, sehingga X dan Y berada di wilayah solusi sesuai dengan:

G = 77 (penguatan maksimum), yang diberikan untuk X = 7 dan Y = 0.

Menariknya, keuntungan maksimum terjadi ketika jumlah penjualan produk Y nol, sedangkan jumlah produk X mencapai nilai tertinggi.

- Latihan 2 (Metode analisis: Pengganda Lagrange)

Temukan solusi (x, y) yang membuat fungsi f (x, y) = x ² + 2y ² maksimum di daerah g (x, y) = x ² + y ² - 1 = 0.

Larutan

Ini jelas merupakan masalah pemrograman non-linier, karena baik fungsi tujuan f (x, y) dan batasan g (x, y) = 0, bukanlah kombinasi linier dari variabel x dan y.

Metode pengali Lagrange akan digunakan, yang pertama membutuhkan pendefinisian fungsi Lagrange L (x, y, λ):

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

Dimana λ merupakan parameter yang disebut pengali Lagrange.

Untuk menentukan nilai ekstrim dari fungsi tujuan f, di daerah solusi yang diberikan oleh batasan g (x, y) = 0, ikuti langkah-langkah berikut:

-Cari turunan parsial dari fungsi Lagrange L, terhadap x, y, λ.

-Kualifikasi setiap turunan menjadi nol.

Berikut urutan operasi tersebut:

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

Solusi sistem yang memungkinkan

Solusi yang mungkin dari sistem ini adalah λ = 1 sehingga persamaan pertama terpenuhi, dalam hal ini y = 0 sehingga persamaan kedua terpenuhi.

Solusi ini menyiratkan bahwa x = 1 atau x = -1 agar persamaan ketiga terpenuhi. Dengan cara ini, dua solusi S1 dan S2 telah diperoleh:

S1: (x = 1, y = 0)

S2: (x = -1, y = 0).

Alternatif lainnya adalah λ = 2 sehingga persamaan kedua terpenuhi, berapapun nilai y.

Dalam hal ini, satu-satunya cara agar persamaan pertama terpenuhi adalah dengan x = 0. Mempertimbangkan persamaan ketiga, hanya ada dua solusi yang mungkin, yang akan kita sebut S3 dan S4:

S3: (x = 0, y = 1)

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

Untuk mengetahui solusi mana atau yang mana yang memaksimalkan fungsi tujuan, kita lanjutkan dengan mengganti f (x, y):

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

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

S3: f (0, 1) = 0 ² + 2,1 ² = 2

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

Kami menyimpulkan bahwa solusi yang memaksimalkan f, ketika x dan y termasuk dalam keliling g (x, y) = 0 adalah S3 dan S4.

Pasangan nilai (x = 0, y = 1) dan (x = 0, y = -1) maksimalkan f (x, y) di daerah solusi g (x, y) = 0.

- Latihan 3 (Gradien nol)

Temukan solusi (x, y) untuk fungsi tujuan:

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

Membiarkan menjadi maksimum di daerah g (x, y) = x ² + y ² - 1 ≤ 0.

Larutan

Latihan ini mirip dengan latihan 2, tetapi daerah penyelesaian (atau batasan) meluas ke daerah interior keliling g (x, y) = 0, artinya lingkaran g (x, y) ≤ 0. Ini termasuk ke lingkar dan wilayah dalamnya.

Solusi di perbatasan telah ditentukan dalam latihan 2, tetapi wilayah pedalaman masih harus dieksplorasi.

Untuk melakukan ini, gradien fungsi f (x, y) harus dihitung dan ditetapkan sama dengan nol, untuk menemukan nilai ekstrem di wilayah solusi. Ini sama dengan menghitung turunan parsial dari f yang masing-masing berkaitan dengan x dan y dan menetapkannya sama dengan nol:

∂f / ∂x = 2 x = 0

∂f / ∂y = 4 y = 0

Sistem persamaan ini memiliki satu-satunya solusi (x = 0, y = 0) yang termasuk dalam lingkaran g (x, y) ≤ 0.

Mengganti nilai ini dalam hasil fungsi f:

f (0, 0) = 0

Kesimpulannya, nilai maksimum fungsi yang diambil di wilayah solusi adalah 2 dan terjadi di batas wilayah solusi, untuk nilai (x = 0, y = 1) dan (x = 0, y = -1) .

Referensi

1. Avriel, M. 2003. Pemrograman Nonlinier. Penerbitan Dover.
2. Bazaraa. 1979. Pemrograman Nonlinier. John Wiley & Sons.
3. Bertsekas, D. 1999. Pemrograman Nonlinier: Edisi ke-2. Athena Scientific.
4. Nocedal, J. 1999. Optimasi Numerik. Springer-Verlag.
5. Wikipedia. Pemrograman nonlinier. Diperoleh dari: es.wikipedia.com